Salsa20

Salsa20 — система потокового шифрування, розроблена Деніелом Бернштейном. Алгоритм був представлений на конкурсі «eSTREAM», метою якого було створення європейських стандартів для шифрування даних, переданих поштовими системами. Алгоритм став переможцем конкурсу в першому профілі (потокові шифри для програмного застосування з великою пропускною здатністю).

Шифр Salsa20 використовує наступні операції:

• додавання 32-бітних чисел;
• побітове додавання по модулю 2 (xor);
• зсув бітів.

Алгоритм використовує геш-функцію з 20 циклами. Основні її перетворення нагадують алгоритм AES.

Опис алгоритму

Поняття

Словом далі будемо називати елемент множини {0,1,...,2³²-1} і записувати його в шістнадцятковому вигляді з префіксом 0х.

Операцію додавання двох слів по модулю 2³² будемо позначати символом «$+$».

Виключне або (побітове додавання) будемо позначати символом «$\oplus$»

$c$ -бітовий циклічний зсув вліво слова $u$, який будемо позначати $u\lll c$. Якщо $u$ представити як $u=\sum _{i=0}2^{i}u_{i}$, тоді

$u\lll c=\sum _{i=0}2^{i+c\mod 32}u_{i}$

Функції, які використовуються в алгоритмі

$quarterround(y_{0},y_{1},y_{2},y_{3})$

quarterround(y)

Основним блоком системи є перетворення $quarterround(y)$ над чотирма словами. З нього будуються далі описані більш загальні перетворення. Його суть полягає в тому, що для кожного слова ми складаємо два попередніх, зсуваємо (циклічно) суму на певну кількість біт і побітово підсумовуємо результат з вибраним словом. Подальші операції проводяться з новими значеннями слів.

Припустимо, що $y$ — послідовність слів 4 $y=(y_{0},y_{1},y_{2},y_{3})$. Тоді функція $quarterround(y)=(z_{0},z_{1},z_{2},z_{3})$ де

$z_{1}=y_{1}\oplus ((y_{0}+y_{3})\lll 7),$

$z_{2}=y_{2}\oplus ((z_{1}+y_{0})\lll 9),$

$z_{3}=y_{3}\oplus ((z_{2}+z_{1})\lll 13),$

$z_{0}=y_{0}\oplus ((z_{3}+z_{2})\lll 18).$

Наприклад:

quarterround(0x00000001; 0x00000000; 0x00000000; 0x00000000) = (0x08008145; 0x00000080; 0x00010200; 0x20500000)

Можна розглядати цю функцію перетворення слів y₀, y₁, y₂ y₃. Кожне з таких перетворень оборотне, як і функція в цілому.

rowround(y)

$y={\begin{pmatrix}y_{0}&y_{1}&y_{2}&y_{3}\\y_{4}&y_{5}&y_{6}&y_{7}\\y_{8}&y_{9}&y_{10}&y_{11}\\y_{12}&y_{13}&y_{14}&y_{15}\end{pmatrix}}$ В цьому перетворенні ми беремо 16 слів. Представимо їх у вигляді матриці 4х4. Беремо кожен рядок цієї матриці і перетворимо слова цієї матриці функцією $quarterround(y)$. Слова з рядка беруться за порядком, починаючи з i-го для i-го рядка, де i={0,1,2,3}.

Нехай $y=(y_{0},y_{1},y_{2},...,y_{15})$ — послідовність 16 слів, тоді $rowround(y)=(z_{0},z_{1},z_{2},...,z_{15})$ — також послідовність 16 слів де

$(z_{0},z_{1},z_{2},z_{3})=quarterround(y_{0},y_{1},y_{2},y_{3}),$

$(z_{5},z_{6},z_{7},z_{4})=quarterround(y_{5},y_{6},y_{7},y_{4}),$

$(z_{10},z_{11},z_{8},z_{9})=quarterround(y_{10},y_{11},y_{8},y_{9}),$

$(z_{15},z_{12},z_{13},z_{14})=quarterround(y_{15},y_{12},y_{13},y_{14}).$

columnround(y)

Тут ми беремо стовпці такої ж матриці. Перетворимо їх функцією $quarterround(y)$ за аналогією підставляючи в неї значення, починаючи з j-го для j-го стовпця, де j={0,1,2,3}.

Функція columnround(y)=(z) теж оперує послідовністю 16 слів так, що

$(z_{0},z_{4},z_{8},z_{12})=quarterround(y_{0},y_{4},y_{8},y_{12}),$

$(z_{5},z_{9},z_{13},z_{1})=quarterround(y_{5},y_{9},y_{13},y_{1}),$

$(z_{10},z_{14},z_{2},z_{6})=quarterround(y_{10},y_{14},y_{2},y_{6}),$

$(z_{15},z_{3},z_{7},z_{11})=quarterround(y_{15},y_{3},y_{7},y_{11}).$

doubleround(y)

Функція doubleround(y) є послідовним застосуванням функцій columnround а потім rowround: doubleround(y) = rowround(columnround(y))

Salsa20()

Даний алгоритм використовує запис слова, що починається з молодшого байта. Для цього тут введено перетворення $littleendian(b)$

Нехай $b=(b_{0},b_{1},b_{2},b_{3})$ — 4-байтова послідовність, тоді $littleendian(b)$ — слово, таке, що

$littleendian(b)=b_{0}+2^{8}b_{1}+2^{16}b_{2}+2^{24}b_{3}$

Підсумкове перетворення — це побітове додавання вихідної послідовності і результату 20 раундів почергових перетворень стовпців і рядків.

$Salsa20(x)=x\oplus doubleround^{10}(x)$де $x=(x[0],x[1],...,x[63]),$

$x_{0}=littleendian(x[0],x[1],x[2],x[3]),$

$x_{1}=littleendian(x[4],x[5],x[6],x[7]),$

…

$x_{15}=littleendian(x[60],x[61],x[62],x[63]).$

x[i] — байти x, а x_j — слова, які використовуються в описаних вище функціях.

Якщо
$(z_{0},z_{1},...,z_{15})=doubleround^{10}(x_{0},x_{1},...,x_{15})$,

тоді Salsa20(x) є послідовністю результатів
$littleendian^{-1}(z_{0}+x_{0}),...,littleendian^{-1}(z_{15}+x_{15})$

Розширення ключа для Salsa20

Розширення перетворює 32-байтний або 16-байтний ключ k і 16-байтний номер n  в 64-байтну послідовність $Salsa20_{k}(n)$.
Для розширення k використовуються константи $\sigma _{0}=(101,120,112,97),~\sigma _{1}=(110,100,32,51),~\sigma _{2}=(50,45,98,121),~\sigma _{3}=(116,101,32,107)$

для 32-бітного k і

$\tau _{0}=(101;120;112;97),~\tau _{1}=(110;100;32;49),~\tau _{2}=(54;45;98;121),~\tau _{3}=(116;101;32;107)$
для 16-бітного k. Це записи «expand 32-byte k» і «expand 16-byte k» ASCII-коді.

Нехай k₀,k₁,n — 16-байтові послідовності, тоді
$Salsa20_{k_{0},k_{1}}(n)=Salsa20(\sigma _{0},k_{0},\sigma _{1},n,\sigma _{2},k_{1},\sigma _{3})$.

Якщо у нас тільки одна 16-байтові послідовність k то
$Salsa20_{k}(n)=Salsa20(\tau _{0},k,\tau _{1},n,\tau _{2},k,\tau _{3})$

Функція шифрування Salsa20

Шифром $l$-байтної послідовності $m$, для $l\in \{0,1,...2^{70}\}$ буде $Salsa20_{k}(v)\oplus m$
$v$ — унікальний 8-байтовий номер (nonce). Шифротекст буде розміром $l$ байт, так само, як вихідний текст.

Salsa20_k(v) — послідовність у 2⁷⁰ байт.

$Salsa20_{k}(v,{\underline {0}}),Salsa20_{k}(v,{\underline {1}}),Salsa20_{k}(v,{\underline {2}}),...,Salsa20_{k}(v,{\underline {2^{64}-1}})$

Де ${\underline {i}}$ — унікальна послідовність у 8 байт $(i_{0},i_{1},...,i_{7})$ така що $i=i_{0}+2^{8}i_{1}+...+2^{56}i_{7}$ Відповідно

$Salsa20_{k}(v)\oplus (m[0],m[1],..,m[l-1])=(c[0],c[1],...,c[l-1])$

Де $c[i]=m[i]\oplus Salsa20_{k}(v,{\mathcal {b}}{\underline {i/64}}{\mathcal {c}})[i\mod 64]$

Продуктивність

Завдяки тому, що перетворення кожного стовпця і кожного рядка не залежать один від одного, обчислення, необхідні для шифрування, легко розпаралелюються. Це дає суттєвий виграш у швидкості для більшості сучасних платформ.

Алгоритм практично не має накладних обчислень, необхідних для запуску циклу шифрування. Це так само відноситься до зміни ключа. Велика кількість шифросистем розраховує на попередні обчислення, результати яких повинні зберігатися в кеші першого рівня (L1) процесора. Так як вони залежать від ключа, обчислення доведеться проводити заново. У Salsa20 ж достатньо просто завантажити ключ в пам'ять.

Варіанти Salsa20/8 і Salsa20/12

Salsa20/8 і Salsa20/12 - це шифросистеми, що використовують той же механізм, що і Salsa20, але з 8 і 12 раундами шифрування, відповідно, замість 20 оригінальних. Salsa20 був зроблений з великим запасом стійкості. Тоді як Salsa20/8 показує хороші результати у швидкодії, обганяючи в більшості випадків багато інших шифросистем, в тому числі AES і RC4

Варіант XSalsa20

Існує варіант алгоритму Salsa20, також запропонований Даніелем Бернштейном, в якому довжина nonce збільшена з 64 до 192 біт. Цей варіант називається XSalsa20. Збільшений розмір nonce дозволяє використовувати для його генерації криптографічно стійкого генератора псевдовипадкових чисел, в той час як для безпечного шифрування з 64-бітним nonce необхідне використання лічильника через високу ймовірність колізій..

Криптоаналіз

У 2005 році Paul Crowley оголосив про атаки на Salsa20/5 з розрахунковою складністю по часу 2¹⁶⁵. Ця і наступні атаки засновані на урізаному диференціальному криптоаналізі (truncated differential криптоаналіз). За цей криптоаналіз він отримав нагороду в 1000$ від автора Salsa20.

B 2006, Fischer, Meier, Berbain, Biasse, і Robshaw повідомили про атаку на Salsa/6 зі складністю 2¹¹⁷, і про атаку з пов'язаними ключами на Salsa20/7 зі складністю 2²¹⁷

B 2008 році Aumasson, Fischer, Khazaei, Meier і Rechberger повідомили про атаку на Salsa20/7 зі складністю 2¹⁵³ і про першу атаку на Salsa20/8 зі складністю 2²⁵¹.

Поки що не було публічних повідомлень про атаки на Salsa20/12 і повну Salsa20/20.

ChaCha

Варіант ChaCha функції quarterround(a, b, c, d)

У 2008 році Даніель Берштейн опублікував споріднене сімейство потокових шифрів під назвою ChaCha, метою якого було поліпшення перемішування даних за один раунд і, ймовірно, поліпшення криптостійкості при тій же, або навіть трохи більшій швидкості.

ChaCha20 описаний в RFC 7539 (травень 2015).

Основний блок системи тут працює інакше. Тепер кожна операція змінює одне з слів. Зміни відбуваються циклічно «у зворотний бік», починаючи з 0-го слова. Чергуються операції додавання побітової суми разом із зсувом, кожне слово складається з попереднім.

Функція quarterround(a, b, c, d), де a, b, c, d-слова, в ChaCha виглядає наступним чином

$a+=b;~~d\oplus =a;~~d\lll =16;$

$c+=d;~~b\oplus =c;~~b\lll =12;$

$a+=b;~~d\oplus =a;~~d\lll =8;$

$c+=d;~~b\oplus =c;~~b\lll =7;$

Тут використовуються ті ж самі арифметичні операції, але кожне слово змінюється два рази за перетворення замість одного.

Посилання

• Salsa20 Домашня сторінка [Архівовано 14 травня 2011 у Wayback Machine.]
• Специфікація [Архівовано 15 грудня 2017 у Wayback Machine.]
• Salsa20/8 і Salsa20/12 [Архівовано 15 грудня 2017 у Wayback Machine.]
• Сторінка Salsa20 на eSTREAM [Архівовано 5 квітня 2016 у Wayback Machine.]
• Сімейство шифрів ChaCha [Архівовано 7 грудня 2020 у Wayback Machine.]
• Salsa20 speed [Архівовано 25 серпня 2017 у Wayback Machine.]