ChaCha20
ChaCha/20
Schemat funkcji ćwierćrundy szyfru ChaCha20 |
| Rodzaj algorytmu |
Szyfr strumieniowy |
| Data stworzenia |
2008 |
| Autorzy |
Daniel J. Bernstein |
| Wielkość bloku wyjściowego |
512 bitów |
| Długość klucza |
128, 256 [bit] |
| Liczba rund |
20 |
ChaCha20 – szyfr strumieniowy opracowany w 2008 roku przez amerykańskiego kryptografa Daniela J. Bernsteina jako rozwinięcie algorytmu Salsa20. Należy do rodziny szyfrów wykorzystujących dodawanie, rotacje bitów i operację XOR, określanej skrótem ARX (add–rotate–XOR). W porównaniu z Salsa20 wykorzystuje zmodyfikowaną funkcję rundy i inny sposób przekształcania elementów stanu wewnętrznego. Zmiany te miały zwiększyć szybkość rozprzestrzeniania się zmian w danych podczas kolejnych rund, przy zachowaniu porównywalnej lub większej wydajności obliczeniowej.
Podstawowy wariant ChaCha20 wykonuje 20 rund przekształceń. Algorytm wykorzystuje 256-bitowy klucz w wersji opisanej przez IETF, chociaż pierwotna rodzina ChaCha dopuszczała również klucze 128-bitowe. Specyfikację ChaCha20 dla protokołów internetowych przedstawiono w RFC 7539 z 2015 roku, zastąpionym w 2018 roku przez RFC 8439.
Zasada działania
ChaCha20 generuje pseudolosowy strumień bajtów na podstawie tajnego klucza, jednorazowej wartości nonce oraz licznika bloków. Szyfrowanie polega na wykonaniu operacji XOR między tekstem jawnym a strumieniem klucza. Odszyfrowanie wykorzystuje tę samą operację, wykonywaną na szyfrogramie i identycznie wygenerowanym strumieniu klucza.
Każde wywołanie funkcji blokowej ChaCha20 wytwarza 64 bajty (512 bitów) strumienia klucza. Poszczególne bloki można obliczać niezależnie, korzystając z odpowiadających im wartości licznika. Pozwala to na równoległe przetwarzanie danych i bezpośredni dostęp do wybranego fragmentu strumienia bez konieczności obliczania wszystkich poprzednich bloków.
Stan wewnętrzny
Algorytm operuje na stanie o długości 512 bitów, przedstawianym jako macierz 4 × 4 zawierająca szesnaście 32-bitowych słów. W wariancie IETF stan początkowy składa się z:
- czterech 32-bitowych słów będących stałymi algorytmu;
- ośmiu słów zawierających 256-bitowy klucz;
- jednego słowa zawierającego 32-bitowy licznik bloków;
- trzech słów zawierających 96-bitową wartość nonce.
Układ stanu początkowego jest następujący:
stała stała stała stała
klucz0 klucz1 klucz2 klucz3
klucz4 klucz5 klucz6 klucz7
licznik nonce0 nonce1 nonce2
Cztery stałe odpowiadają zapisowi ASCII ciągu expand 32-byte k, podzielonemu na cztery 32-bitowe słowa. Wielobajtowe wartości są interpretowane w porządku little-endian.
Pierwotna wersja ChaCha20 wykorzystywała 64-bitowy licznik i 64-bitową wartość nonce. Wariant IETF zmienił ich podział na 32-bitowy licznik i 96-bitową wartość nonce, zachowując łączną długość 128 bitów. Zwiększenie długości nonce ułatwia przypisywanie odrębnych wartości kolejnym wiadomościom, lecz skrócenie licznika ogranicza liczbę bloków możliwych do wygenerowania dla jednej pary klucza i wartości nonce do 232. Odpowiada to 256 GiB strumienia klucza.
Funkcja rundy
ChaCha20 wykorzystuje trzy podstawowe operacje na 32-bitowych słowach:
- dodawanie modulo 232;
- bitową alternatywę rozłączną (XOR);
- cykliczną rotację bitów w lewo.
Podstawowym przekształceniem jest funkcja quarterround (ćwierćrunda), działająca na czterech słowach oznaczonych jako a, b, c i d. Wykonuje ona następującą sekwencję operacji:
a = a + b
d = ROTL(d XOR a, 16)
c = c + d
b = ROTL(b XOR c, 12)
a = a + b
d = ROTL(d XOR a, 8)
c = c + d
b = ROTL(b XOR c, 7)
W powyższym zapisie dodawanie odbywa się modulo 232, a ROTL(x, n) oznacza cykliczną rotację 32-bitowego słowa x w lewo o n bitów. W porównaniu z Salsa20 zmieniono kolejność operacji i odległości rotacji, które w ChaCha20 wynoszą 16, 12, 8 i 7 bitów. Każde z czterech słów jest modyfikowane dwukrotnie w jednej ćwierćrundzie.
Cztery ćwierćrundy tworzą jedną rundę algorytmu. ChaCha20 naprzemiennie wykonuje rundy kolumnowe i diagonalne. W rundzie kolumnowej przekształcane są słowa znajdujące się w tych samych kolumnach macierzy, na przykład na pozycjach (0, 4, 8, 12). W rundzie diagonalnej przekształcenia obejmują odpowiednio dobrane grupy słów, na przykład pozycje (0, 5, 10, 15).
Pełny ChaCha20 wykonuje 20 rund, czyli łącznie 80 ćwierćrund. Po zakończeniu przekształceń każde słowo wynikowego stanu jest dodawane modulo 232 do odpowiadającego mu słowa stanu początkowego. Następnie słowa są zapisywane w porządku little-endian, tworząc 64-bajtowy blok strumienia klucza.
Różnice względem Salsa20
ChaCha20 zachowuje ogólną konstrukcję Salsa20, w tym 512-bitowy stan wewnętrzny, przetwarzanie 32-bitowych słów i generowanie 64-bajtowych bloków strumienia klucza. Różnice dotyczą przede wszystkim funkcji ćwierćrundy, rozmieszczenia słów w stanie początkowym i sposobu wykonywania rund.
| Cecha |
Salsa20 |
ChaCha20 |
|---|
| Rok opracowania |
2005 |
2008 |
| Liczba rund w pełnym wariancie |
20 |
20 |
| Rotacje w ćwierćrundzie |
7, 9, 13, 18 bitów |
16, 12, 8, 7 bitów |
| Przekształcenia stanu |
Rundy kolumnowe i wierszowe |
Rundy kolumnowe i diagonalne |
| Modyfikacje pojedynczego słowa w ćwierćrundzie |
Jedna |
Dwie |
| Długość nonce w pierwotnej wersji |
64 bity |
64 bity |
Zmodyfikowana funkcja ćwierćrundy ChaCha zapewnia szybsze rozprzestrzenianie zmian między słowami stanu. Według analizy Bernsteina, przy założeniu braku przeniesień w operacjach dodawania, zmiana jednego bitu wejściowego powoduje zmianę średnio 12,5 bitu wyjściowego ćwierćrundy ChaCha, w porównaniu z 8 bitami w Salsa20.
Bezpieczeństwo
Bezpieczeństwo ChaCha20 było przedmiotem licznych badań kryptograficznych. Analizy koncentrowały się przede wszystkim na wariantach o zmniejszonej liczbie rund, wykorzystując między innymi kryptoanalizę różnicową i techniki różnicowo-liniowe.
W 2008 roku Jean-Philippe Aumasson i współautorzy opisali ataki na sześciorundowy i siedmiorundowy wariant ChaCha z kluczem 256-bitowym. Ich szacowane złożoności wynosiły odpowiednio 2139 i 2248 operacji.
W badaniu opublikowanym 9 października 2026 roku Guoqiang Liu i współautorzy przedstawili udoskonalone oszacowania ataków różnicowo-liniowych na warianty ChaCha obejmujące 7 i 7,5 rundy. Dla ataków polegających na odzyskiwaniu klucza oszacowano złożoność czasową odpowiednio na 2140 i 2241,31 operacji. Wyniki te dotyczą wersji o znacznie zmniejszonej liczbie rund i nie oznaczają złamania pełnego ChaCha20.
Pełny, dwudziestorundowy ChaCha20 pozostaje odporny na znane praktyczne metody kryptoanalizy. Badania wariantów o mniejszej liczbie rund służą przede wszystkim ocenie marginesu bezpieczeństwa całej konstrukcji.
Istotnym warunkiem bezpiecznego stosowania ChaCha20 jest niepowtarzanie tej samej wartości nonce przy szyfrowaniu różnych wiadomości tym samym kluczem i przy identycznym początkowym liczniku bloków. Ponowne użycie takiej kombinacji powoduje wygenerowanie tego samego strumienia klucza, co może ujawnić zależności między tekstami jawnymi.
Konstrukcja oparta wyłącznie na operacjach ARX nie wymaga tablic podstawień ani zależnych od danych odczytów takich tablic. Ułatwia to tworzenie implementacji odpornych na ataki czasowe związane z dostępem do pamięci. Nie oznacza to jednak odporności każdej implementacji na wszystkie rodzaje ataków bocznokanałowych.
Sam ChaCha20 zapewnia poufność danych, lecz nie gwarantuje ich integralności ani autentyczności. Modyfikacja szyfrogramu może spowodować przewidywalną zmianę odszyfrowanego tekstu bez wykrycia ingerencji. Z tego powodu w zastosowaniach wymagających uwierzytelniania wiadomości wykorzystuje się konstrukcje łączące szyfrowanie z odpowiednim mechanizmem uwierzytelniania.
Zastosowania
ChaCha20 jest wykorzystywany w bibliotekach kryptograficznych oraz jako element konstrukcji zapewniających uwierzytelnione szyfrowanie. Najbardziej rozpowszechnioną z nich jest ChaCha20-Poly1305, łącząca szyfr strumieniowy ChaCha20 z algorytmem uwierzytelniania wiadomości Poly1305. Konstrukcja ta zapewnia zarówno poufność, jak i ochronę integralności oraz autentyczności danych.
ChaCha20-Poly1305 znajduje zastosowanie między innymi w:
- TLS, w tym TLS 1.3, jako jeden z dostępnych algorytmów szyfrowania uwierzytelnionego;
- IPsec, gdzie jego użycie opisano w RFC 7634;
- SSH, między innymi w wariancie
chacha20-poly1305@openssh.com stosowanym przez OpenSSH;
- WireGuard, gdzie stanowi podstawę szyfrowania uwierzytelnionego przesyłanych danych.
Wersja ChaCha20 z 96-bitową wartością nonce oraz konstrukcja ChaCha20-Poly1305 zostały opisane w RFC 7539 z maja 2015 roku. W czerwcu 2018 roku dokument ten zastąpiono RFC 8439, który uwzględnił poprawki i rozszerzył omówienie zagadnień bezpieczeństwa. RFC 8439 ma status dokumentu informacyjnego (Informational), a nie standardu internetowego z kategorii Standards Track.
