Crypto-IT

• Długość klucza = 32 bajtów

Salsa20 jest nowoczesnym i wydajnym strumieniowym szyfrem symetrycznym. Został on zaprojektowany w 2005 roku przez Daniela Bernstein'a, profesora informatyki na Uniwersytecie Illinois w Chicago.

Szyfr Salsa20 został zgłoszony do projektu eSTREAM, mającego miejsce w latach 2004 to 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.

Salsa20 jest szyfrem strumieniowym, który operuje na blokach danych o wielkości 64 bajtów.

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 nonce, połączony dodatkowo z numerem aktualnie szyfrowanego bloku. Wartości numerów bloków zmieniają się od 0 do 2⁶⁴-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 bajty 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 2³²-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.

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 jest powinno być dodane XOR do 64-bajtowego bloku zaszyfrowanego tekstu. Wynikiem tego sumowania jest 64-bajtowy blok tekstu jawnego.

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 Bernstein'a w 2008 roku. Zapewniają lepsza 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

Operacje wykonywane w ramach algorytmu szyfrującego Salsa20 zostały przedstawione od funkcji najniższego poziomu, do zbudowanych z nich funkcji wyższego poziomu.

Dodawanie dwóch 4-bajtowych słów jest przedstawione w opisie algorytmu jako a + b. Wynik dodawania jest dzielony modulo przez 2³² (czyli przez maksymalną wartość słowa 4-bajtowego).

Suma dwóch słów a i b jest równa a+b mod 2³². Wynik ma 4 bajty długości.

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 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:
2^a·w mod(2³²-1)
Otrzymany wynik jest poprawnym słowem, o długości 4 bajtów.

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 = (x₀, x₁, x₂, x₃)
to Funkcja Ćwiartki Rundy może być zdefiniowana następująco:
    quarterround(x) = (y₀, y₁, y₂, y₃)
gdzie:
    y₁ = x₁ XOR ((x₀ + x₃) <<< 7)
    y₂ = x₂ XOR ((y₁ + x₀) <<< 9)
    y₃ = x₃ XOR ((y₂ + y₁) <<< 13)
    y₀ = x₀ XOR ((y₃ + y₂) <<< 18)

Funkcja Ćwiartki Rundy może wykonywać się w miejscu, to znaczy bez potrzeby przydzielania dodatkowej pamięci. Najpierw x₁ zamienia się na y₁, potem x₂ przekształca się w y₂, następnie x₃ przekształca się w y₃, a na końcu x₀ zamienia się na y₀. Funkcja Ćwiartki Rundy jest odwracalna, ponieważ wszystkie powyższe operacje są odwracalne.

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 = (x₀, x₁, x₂, ..., x₁₅)
to Funkcja Rundy Wierszy może być zdefiniowana następująco:
    rowround(x) = (y₀, y₁, y₂, ..., y₁₅)
gdzie:
    (y₀, y₁, y₂, y₃) = quarterround(x₀, x₁, x₂, x₃)
    (y₅, y₆, y₇, y₄) = quarterround(x₅, x₆, x₇, x₄)
    (y₁₀, y₁₁, y₈, y₉) = quarterround(x₁₀, x₁₁, x₈, x₉)
    (y₁₅, y₁₂, y₁₃, y₁₄) = quarterround(x₁₅, x₁₂, x₁₃, x₁₄)

Dane wejściowe do funkcji składające się z 16 słów mogą być przedstawione za pomocą macierzy:

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:

1. x₁
2. x₂
3. x₃
4. x₀

Słowa w drugim wierszu są zmieniane w następującej kolejności:

1. x₆
2. x₇
3. x₄
4. x₅

W trzecim wierszu, słowa zmieniane w kolejności:

1. x₁₁
2. x₈
3. x₉
4. x₁₀

W ostatnim, czwartym wierszu, słowa są zmieniane w kolejności:

1. x₁₂
2. x₁₃
3. x₁₄
4. x₁₅

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 = (x₀, x₁, x₂, ..., x₁₅)
to funkcja rundy kolumn może być zdefiniowana następująco:
    columnround(x) = (y₀, y₁, y₂, ..., y₁₅)
gdzie:
    (y₀, y₄, y₈, y₁₂) = quarterround(x₀, x₄, x₈, x₁₂)
    (y₅, y₉, y₁₃, y₁) = quarterround(x₅, x₉, x₁₃, x₁)
    (y₁₀, y₁₄, y₂, y₆) = quarterround(x₁₀, x₁₄, x₂, x₆)
    (y₁₅, y₃, y₇, y₁₁) = quarterround(x₁₅, x₃, x₇, x₁₁)

Dane wejściowe składające się z 16 słów mogą być przedstawione za pomocą macierzy:

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:

1. x₄
2. x₈
3. x₁₂
4. x₀

W drugiej kolumnie, słowa są zmieniane w kolejności:

1. x₉
2. x₁₃
3. x₁
4. x₅

W trzeciej kolumnie, słowa są zmieniane w następującej kolejności:

1. x₁₄
2. x₂
3. x₆
4. x₁₀

W ostatniej, czwartej kolumnie, słowa są zmieniane w kolejności:

1. x₃
2. x₇
3. x₁₁
4. x₁₅

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))

Otrzymane 4 bajty są zwracane w odwrotnej kolejności.

Jeśli b jest ciągiem 4 bajtów:
    b = (b₀, b₁, b₂, b₃)
to przekształcenie może być zdefiniowane następująco:
    littleendian(b) = b₀ + 2⁸b₁ + 2¹⁶b₂ + 2²⁴b₃

Zamiana ta jest odwracalna. Powtórne użycie tej funkcji na otrzymanych danych powoduje powrót do stanu pierwotnego.

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. Jażeli input jest ciągiem 64 bajtów:
    input =(b₀, b₁, b₂, ..., b₆₃)
to 16 słów jest tworzonych następująco:
    w₀ = littleendian(b₀, b₁, b₂, b₃)
    w₁ = littleendian(b₄, b₅, b₆, b₇)
    [...]
    w₁₅ = littleendian(b₆₀, b₆₁, b₆₂, b₆₃)

Następnie, wszystkie 16 słów jest modyfikowanych w trakcie 10 iteracji Funkcji Podwójnej Rundy:
    (x₀, x₁, ..., x₁₅) = doubleround¹⁰(w₀, w₁, ..., w₁₅)

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(x₀+w₀) + littleendian^-1(x₁+w₁) + ... + littleendian^-1(x₁₅+w₁₅)

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 (k₀ i k₁). Funkcja Rozszerzająca Salsa20 jest wtedy definiowana za pomocą Funkcji Haszującej Salsa20 w następujący sposób:
    Salsa20Expansion_{k0, k1}(n) = Salsa20Hash(a₀, k₀, a₁, n, a₂, k₁, a₃)
gdzie:
    a₀ = (101, 120, 112, 97)
    a₁ = (110, 100, 32, 51)
    a₂ = (50, 45, 98, 121)
    a₃ = (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:
    Salsa20Expansion_k(n) = Salsa20Hash(b₀, k, b₁, n, b₂, k, b₃)
gdzie:
    b₀ = (101, 120, 112, 97)
    b₁ = (110, 100, 32, 49)
    b₂ = (54, 45, 98, 121)
    b₃ = (116, 101, 32, 107)

Wartości wektora (a₀, a₁, a₂, a₃) oznaczają "expand 32-byte k", zapisane w kodzie ASCII. Wartości wektora (b₀, b₁, b₂, b₃) oznacza "expand 16-byte k" w kodzie ASCII.