Salsa20

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

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

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

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

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

Поняття

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

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

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

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

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

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

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

quarterround(y)

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

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

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

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

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

${\displaystyle 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)

${\displaystyle 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. Беремо кожен рядок цієї матриці і перетворимо слова цієї матриці функцією ${\displaystyle quarterround(y)}$. Слова з рядка беруться за порядком, починаючи з i-го для i-го рядка, де i={0,1,2,3}.

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

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

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

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

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

columnround(y)

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

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

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

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

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

${\displaystyle (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()

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

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

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

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

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

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

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

…

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

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

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

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

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

Розширення перетворює 32-байтний або 16-байтний ключ k і 16-байтний номер n  в 64-байтну послідовність ${\displaystyle Salsa20_{k}(n)}$.
Для розширення k використовуються константи ${\displaystyle \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 і

${\displaystyle \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-байтові послідовності, тоді
${\displaystyle Salsa20_{k_{0},k_{1}}(n)=Salsa20(\sigma _{0},k_{0},\sigma _{1},n,\sigma _{2},k_{1},\sigma _{3})}$.

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

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

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

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

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

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

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

Де ${\displaystyle 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 виглядає наступним чином

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

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

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

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

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

Примітки

1. Daniel J. Bernstein. (PDF). cr.yp.to (англ.). Архів оригіналу (PDF) за 15 грудня 2017. Процитовано 10 квітня 2018.
2. Daniel J. Bernstein (4 лютого 2011). (PDF). cr.yp.to (англ.). Архів оригіналу (PDF) за 18 вересня 2018. Процитовано 10 квітня 2018.
3. Daniel J. Bernstein ? (28 січня 2008). (PDF). cr.yp.to (англ.). Архів оригіналу (PDF) за 2 травня 2018. Процитовано 10 квітня 2018.

Посилання

• 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.]