- Długość klucza = 32 bajtów
Salsa20 jest nowoczesnym i wydajnym strumieniowym szyfrem symetrycznym. Został on zaprojektowany w 2005 roku przez Daniela Bernsteina, profesora informatyki na Uniwersytecie Illinois w Chicago.
Zastosowanie
Szyfr Salsa20 został zgłoszony do projektu eSTREAM, mającego miejsce w latach 2004 do 2008, który miał na celu spopularyzowanie szyfrów strumieniowych i doprowadził do opublikowania kilku nowych szyfrów strumieniowych przyzwoitej jakości. Salsa20 jest uważany za dobrze zaprojektowany i efektywny algorytm. Nie są znane żadne skuteczne ataki na szyfry z rodziny Salsa20.
Algorytm
Salsa20 jest szyfrem strumieniowym, który operuje na blokach danych o wielkości 64 bajtów.
Szyfrowanie
Dla każdego 64-bajtowego bloku danych, algorytm wywołuje funkcję rozszerzającą Salsa20. Danymi wejściowymi do funkcji są: sekretny klucz (który może mieć 32 lub 16 bajtów) oraz 8-bajtowy , połączony dodatkowo z numerem aktualnie szyfrowanego bloku. Wartości numerów bloków zmieniają się od 0 do 264-1 (jest więc zapisany na 8 bajtach). Każde wywołanie funkcji rozszerzającej zwiększa wartość numeru bloku o jeden.
Rdzeniem algorytmu Salsa20 jest funkcja haszująca, która otrzymuje 64 bajty z funkcji rozszerzającej, następnie miesza je, a na koniec zwraca inne 64 bajty danych, z powrotem do funkcji rozszerzającej. Funkcja haszująca jako dane wejściowe przyjmuje ciąg bajtów, na który składają się:
- sekretny klucz.
- nonce wraz z dodatkowym numerem bloku.
- cztery stałe wektory, każdy składający się z 4 bajtów, określone przez funkcję rozszerzającą, o wartościach zależących od długości używanego sekretnego klucza.
Funkcja haszująca operuje na danych podzielonych na słowa (słowa maszynowe, ang. words). Każde słowo składa się z 4 bajtów i może zawierać liczbę z przedziału od 0 do 232-1. Wynika z tego, że blok danych wejściowych ma 16 słów długości, sekretny klucz zawiera 8 lub 4 słowa, natomiast nonce ma 2 słowa.
Wyjście z funkcji rozszerzającej szyfru Salsa20 jest dodawane XOR do 64-bajtowego bloku danych. Wynikiem tego działania jest 64-bajtowy blok zaszyfrowanego tekstu.
Deszyfrowanie
W celu odszyfrowania otrzymanego szyfrogramu, należy wykorzystać ten sam algorytm. Dane powinny zostać podzielone w ten sam sposób.
Wyjście z funkcji rozszerzającej szyfru Salsa20 powinno być dodane XOR do 64-bajtowego bloku zaszyfrowanego tekstu. Wynikiem tego sumowania jest 64-bajtowy blok tekstu jawnego.
Inne szyfry oparte na Salsa20
Istnieje kilka odmian szyfru Salsa20. Bazują one na tym samym algorytmie, ale różnią się pewnymi detalami w implementacji.
- Salsa20/8 i Salsa20/12 - działają dokładnie na tej samej zasadzie, co oryginalny algorytm Salsa20. Jedynie zamiast wykonania 10 powtórzeń funkcji podwójnej rundy wewnątrz funkcji haszującej, przeprowadzają one odpowiednio 4 lub 6 powtórzeń.
- rodzina szyfrów ChaCha - opublikowane przez Bernsteina w 2008 roku. Zapewniają lepszą jakość zabezpieczeń dzięki użyciu nieco innych funkcji haszujących. Dane wejściowe są przekazywane w innej kolejności dla umożliwienia bardziej efektywnej implementacji.
Schemat blokowy algorytmu Salsa20
Matematyka
Operacje wykonywane w ramach algorytmu szyfrującego Salsa20 zostały przedstawione od funkcji najniższego poziomu, do zbudowanych z nich funkcji wyższego poziomu.
Suma dwóch słów
Dodawanie dwóch 4-bajtowych słów jest przedstawione w opisie algorytmu jako a + b. Wynik dodawania jest dzielony modulo przez 232 (czyli przez maksymalną wartość słowa 4-bajtowego).
Suma dwóch słów a i b jest równa a+b mod 232. Wynik ma 4 bajty długości.
XOR dwóch słów
Operacja XOR na dwóch 4-bajtowych słowach jest przedstawiona w opisie algorytmu jako a XOR b.
Aby dodać XOR dwa 4-bajtowe słowa, należy obie liczby porównać bit po bicie i dla każdej takiej pary bitów wykonać działanie XOR. Otrzymany wynik ma również 4 bajty długości.
Rotacja bitów w lewo
Rotacja w lewo o a bitów 4-bajtowego słowa w jest przedstawiona w opisie algorytmu jako w <<< a. Podczas rotacji, a najbardziej skrajnych lewych bitów przechodzi na prawą stronę słowa.
Rotacja bitów w lewo w <<< a 4-bajtowego słowa w może być przedstawiona jako operacja mnożenia:
2a·w mod(232-1)
Otrzymany wynik jest poprawnym słowem, o długości 4 bajtów.
Funkcja ćwiartki rundy
(ang. Quarterround Function)Funkcja Ćwiartki Rundy pobiera 4 słowa danych wejściowych. Zwracany ciąg ma również długość 4 słów.
Jeżeli x jest wejściem do funkcji o długości 4 słów:
x = (x0, x1, x2, x3)
to Funkcja Ćwiartki Rundy może być zdefiniowana następująco:
quarterround(x) = (y0, y1, y2, y3)
gdzie:
y1 = x1 XOR ((x0 + x3) <<< 7)
y2 = x2 XOR ((y1 + x0) <<< 9)
y3 = x3 XOR ((y2 + y1) <<< 13)
y0 = x0 XOR ((y3 + y2) <<< 18)
Funkcja Ćwiartki Rundy może wykonywać się w miejscu, to znaczy bez potrzeby przydzielania dodatkowej pamięci. Najpierw x1 zamienia się na y1, potem x2 przekształca się w y2, następnie x3 przekształca się w y3, a na końcu x0 zamienia się na y0. Funkcja Ćwiartki Rundy jest odwracalna, ponieważ wszystkie powyższe operacje są odwracalne.
Funkcja rundy wierszy
(ang. Rowround Function)Funkcja Rundy Wierszy pobiera 16 słów wejściowych, przekształca je i zwraca ciąg o długości również 16 słów.
Funkcja ta jest bardzo podobna do Funkcji Rundy Kolumn, ale operuje na słowach w innej kolejności.
Jeżeli x jest 16-bajtowym ciągiem przekazanym do funkcji:
x = (x0, x1, x2, ..., x15)
to Funkcja Rundy Wierszy może być zdefiniowana następująco:
rowround(x) = (y0, y1, y2, ..., y15)
gdzie:
(y0, y1, y2, y3) = quarterround(x0, x1, x2, x3)
(y5, y6, y7, y4) = quarterround(x5, x6, x7, x4)
(y10, y11, y8, y9) = quarterround(x10, x11, x8, x9)
(y15, y12, y13, y14) = quarterround(x15, x12, x13, x14)
Dane wejściowe do funkcji składające się z 16 słów mogą być przedstawione za pomocą macierzy:
| x0 | x1 | x2 | x3 |
| x4 | x5 | x6 | x7 |
| x8 | x9 | x10 | x11 |
| x12 | x13 | x14 | x15 |
Wiersze w macierzy są modyfikowane równocześnie. Każdy z nich jest przetwarzany za pomocą Funkcji Ćwiartki Rundy.
Słowa w pierwszym wierszu są zmieniane w następującej kolejności:
- x1
- x2
- x3
- x0
Słowa w drugim wierszu są zmieniane w następującej kolejności:
- x6
- x7
- x4
- x5
W trzecim wierszu, słowa zmieniane w kolejności:
- x11
- x8
- x9
- x10
W ostatnim, czwartym wierszu, słowa są zmieniane w kolejności:
- x12
- x13
- x14
- x15
Funkcja rundy kolumn
(ang. Columnround Function)Funkcja Rundy Kolumn pobiera 16 słów wejściowych i zwraca ciąg o długości również 16 słów.
Jeżeli x jest wejściem do funkcji o długości 16 słów:
x = (x0, x1, x2, ..., x15)
to funkcja rundy kolumn może być zdefiniowana następująco:
columnround(x) = (y0, y1, y2, ..., y15)
gdzie:
(y0, y4, y8, y12) = quarterround(x0, x4, x8, x12)
(y5, y9, y13, y1) = quarterround(x5, x9, x13, x1)
(y10, y14, y2, y6) = quarterround(x10, x14, x2, x6)
(y15, y3, y7, y11) = quarterround(x15, x3, x7, x11)
Dane wejściowe składające się z 16 słów mogą być przedstawione za pomocą macierzy:
| x0 | x1 | x2 | x3 |
| x4 | x5 | x6 | x7 |
| x8 | x9 | x10 | x11 |
| x12 | x13 | x14 | x15 |
Kolumny w macierzy mogą być przekształcane równocześnie. Każda z nich jest modyfikowana za pomocą Funkcji Ćwiartki Rundy.
W pierwszej kolumnie, słowa są zmieniane w następującej kolejności:
- x4
- x8
- x12
- x0
W drugiej kolumnie, słowa są zmieniane w kolejności:
- x9
- x13
- x1
- x5
W trzeciej kolumnie, słowa są zmieniane w następującej kolejności:
- x14
- x2
- x6
- x10
W ostatniej, czwartej kolumnie, słowa są zmieniane w kolejności:
- x3
- x7
- x11
- x15
Funkcja podwójnej rundy
(ang. Doubleround Function)Funkcja Podwójnej Rundy pobiera 16 słów wejściowych, przekształca je, a na koniec zwraca ciąg o długości również 16 słów.
Jeżeli x jest wejściem do funkcji o długości 16 słów, to Funkcja Podwójnej Rundy może być zdefiniowana następująco:
doubleround(x) = rowround(columnround(x))
Funkcja zmiany porządku bajtów
(ang. Littleendian Function)Otrzymane 4 bajty są zwracane w odwrotnej kolejności.
Jeśli b jest ciągiem 4 bajtów:
b = (b0, b1, b2, b3)
to przekształcenie może być zdefiniowane następująco:
littleendian(b) = b0 + 28b1 + 216b2 + 224b3
Zamiana ta jest odwracalna. Powtórne użycie tej funkcji na otrzymanych danych powoduje powrót do stanu pierwotnego.
Funkcja haszująca Salsa20
Funkcja Haszująca Salsa20 pobiera 64 bajty wejściowe i zwraca również ciąg o długości 64 bajtów.
Najpierw, Funkcja Haszująca tworzy 16 słów bazując na otrzymanych 64 bajtach wejściowych. Jeżeli input jest ciągiem 64 bajtów:
input =(b0, b1, b2, ..., b63)
to 16 słów jest tworzonych następująco:
w0 = littleendian(b0, b1, b2, b3)
w1 = littleendian(b4, b5, b6, b7)
[...]
w15 = littleendian(b60, b61, b62, b63)
Następnie, wszystkie 16 słów jest modyfikowanych w trakcie 10 iteracji Funkcji Podwójnej Rundy:
(x0, x1, ..., x15) = doubleround10(w0, w1, ..., w15)
Na końcu, otrzymane na wejściu 16 słów jest dodawanych (tak jak to opisano powyżej) do 16 zmodyfikowanych słów i zamienianych na 64 bajty przy użyciu Funkcji Zmiany Porządku Bajtów. Otrzymane w wyniku 64 bajty są wyjściem (output) z Funkcji Haszującej Salsa20:
output = littleendian-1(x0+w0) + littleendian-1(x1+w1) + ... + littleendian-1(x15+w15)
Funkcja rozszerzająca Salsa20
Funkcja Rozszerzająca Salsa20 pobiera dwa ciągi bajtów. Pierwszy ciąg może mieć 16 lub 32 bajty. Drugi ciąg ma 16 bajtów długości. Funkcja zwraca ciąg o długości 64 bajtów.
Jeżeli pierwszy ciąg ma długość 32 bajtów, to jest on dzielony na dwa ciągi o długości 16 bajtów każdy (k0 i k1). Funkcja Rozszerzająca Salsa20 jest wtedy definiowana za pomocą Funkcji Haszującej Salsa20 w następujący sposób:
Salsa20Expansionk0, k1(n) = Salsa20Hash(a0, k0, a1, n, a2, k1, a3)
gdzie:
a0 = (101, 120, 112, 97)
a1 = (110, 100, 32, 51)
a2 = (50, 45, 98, 121)
a3 = (116, 101, 32, 107)
Jeżeli pierwszy ciąg ma długość 16 bajtów (k), to wtedy Funkcja Rozszerzająca Salsa20 jest definiowana za pomocą Funkcji Haszującej Salsa20 w sposób przedstawiony poniżej:
Salsa20Expansionk(n) = Salsa20Hash(b0, k, b1, n, b2, k, b3)
gdzie:
b0 = (101, 120, 112, 97)
b1 = (110, 100, 32, 49)
b2 = (54, 45, 98, 121)
b3 = (116, 101, 32, 107)
Wartości wektora (a0, a1, a2, a3) oznaczają "expand 32-byte k", zapisane w kodzie ASCII. Wartości wektora (b0, b1, b2, b3) oznacza "expand 16-byte k" w kodzie ASCII.
Nonce (ang. number used once) to dowolna liczba (często losowa lub pseudolosowa), używana tylko raz w danej komunikacji kryptograficznej. Zapewnia bezpieczeństwo szyfrów strumieniowych (strumień klucza jest inny dla każdej wiadomości) i uniemożliwia ponowne wykorzystanie starych wiadomości w atakach powtórzeniowych.