Szyfr strumieniowy
W kryptografii szyfr strumieniowy jest szyfrem symetrycznym, w którym bity zwykłego tekstu łączą się z pseudolosowym strumieniem bitów szyfru (keystream) za pomocą operacji exclusive-or (xor). W szyfrze strumieniowym cyfry zwykłego tekstu są szyfrowane pojedynczo, a transformacja kolejnych cyfr zmienia się w trakcie stanu szyfrowania. Alternatywną nazwą jest szyfr stanowy, ponieważ szyfrowanie każdej cyfry jest zależne od bieżącego stanu. W praktyce, cyfry są zazwyczaj pojedynczymi bitami lub bajtami.
Szyfr strumieniowy reprezentuje inne podejście do szyfrowania symetrycznego niż szyfrowanie blokowe. Szyfrów blokowych używa się na dużych blokach o stałej długości. Szyfr strumieniowy wykonuje się zazwyczaj z większą prędkością niż szyfr blokowy i ma mniejsze wymagania sprzętowe. Szyfr strumieniowy może być jednak podatny na poważne problemy z bezpieczeństwem, jeśli zostanie użyty nieprawidłowo; na przykład, ten sam stan początkowy nie może być nigdy użyty dwukrotnie.
Szyfr strumieniowy wykorzystuje znacznie mniejszy i wygodniejszy klucz kryptograficzny, na przykład 128-bitowe klucze. Na podstawie tego klucza generuje on pseudolosowy strumień kluczy, który może być łączony z cyframi zwykłego tekstu w sposób podobny do algorytmu szyfrowania typu "one time pad". Ponieważ jednak strumień kluczy jest pseudolosowy, a nie prawdziwie przypadkowy, zabezpieczenie związane z jednorazowym padem nie może być zastosowane i jest całkiem możliwe, że szyfr strumieniowy jest całkowicie niepewny.
Działanie generatora strumienia kluczy w A5/1, szyfru strumieniowego opartego na LFSR, używanego do szyfrowania rozmów w telefonach komórkowych.
Rodzaje szyfrów strumieniowych
Szyfr strumieniowy generuje kolejne elementy strumienia klucza w oparciu o stan wewnętrzny. Stan ten jest aktualizowany na dwa sposoby:
- Jeśli stan zmienia się niezależnie od komunikatów tekstowych lub szyfrujących, szyfr jest klasyfikowany jako szyfr strumieniowy synchroniczny.
- Jeżeli stan jest aktualizowany na podstawie wcześniejszych zmian cyfr szyfru, to jest on klasyfikowany jako samosynchronizujący się szyfr strumieniowy.
Synchroniczne szyfratory strumieniowe
W synchronicznym strumieniu szyfrującym generowany jest strumień pseudolosowych cyfr niezależnie od tekstu zwykłego i wiadomości szyfrujących, a następnie łączony z tekstem zwykłym (w celu zaszyfrowania) lub z szyfrem (w celu odszyfrowania). W najczęstszej formie używane są cyfry binarne (bity), a strumień klucza jest łączony z tekstem zwykłym za pomocą wyłączności lub operacji (XOR). Jest to określane jako binarny szyfr strumienia dodatków uszlachetniających.
W szyfrze strumienia synchronicznego nadawca i odbiornik muszą być w synchronizacji, aby odszyfrowanie zakończyło się sukcesem. W przypadku dodania lub usunięcia cyfr z wiadomości w trakcie transmisji, synchronizacja zostaje utracona. Aby przywrócić synchronizację, można systematycznie próbować różnych odsunięć w celu uzyskania prawidłowego deszyfrowania. Innym podejściem jest oznaczenie szyfru znacznikami w regularnych punktach na wyjściu.
Jeśli jednak jakaś cyfra zostanie uszkodzona podczas transmisji, a nie dodana lub zagubiona, będzie to dotyczyło tylko pojedynczej cyfry w prostym tekście, a błąd nie rozprzestrzeni się na inne części komunikatu. Właściwość ta jest przydatna, gdy poziom błędów w transmisji jest wysoki; sprawia ona jednak, że jest mniej prawdopodobne, że błąd zostanie wykryty bez dalszych mechanizmów. Co więcej, dzięki tej właściwości szyfry strumieniowe synchroniczne są bardzo podatne na aktywneataki - jeśli napastnik może zmienić cyfrę w szyfrze, może być w stanie dokonać przewidywalnych zmian w odpowiadającym jej bitu w tekście zwykłym; na przykład obrócenie bitu w szyfrze powoduje obrócenie tego samego bitu (Toggled) w tekście zwykłym.
Samosynchronizujące się szyfry strumieniowe
Samosynchronizujące się szyfry strumieniowe to kolejna technika, która wykorzystuje część poprzednich cyfr szyfru N do obliczania strumienia kluczy. Takie schematy znane są również jako asynchroniczne szyfry strumieniowe lub autokey szyfrujący (CTAK). Pomysł samosynchronizacji został opatentowany w 1946 roku i ma tę zaletę, że odbiornik będzie automatycznie synchronizował się z generatorem strumienia kluczy po otrzymaniu N cyfr szyfrujących, co ułatwi jego odzyskanie w przypadku upuszczenia lub dodania cyfr do strumienia wiadomości. Błędy jednocyfrowe są ograniczone w swoim działaniu i dotyczą tylko do N-cyfrowego szyfru. Nieco trudniej jest przeprowadzać aktywne ataki na samosynchronizujące się szyfry strumieniowe niż na ich synchroniczne odpowiedniki.
Przykładem samosynchronizującego się szyfru strumieniowego jest szyfr blokowy w trybie cipher-feedback (CFB).
Liniowe sprzężenia zwrotne przesunięcia rejestrów oparte na szyfrach strumieniowych
Binarne szyfry strumieniowe są często konstruowane z wykorzystaniem liniowych rejestrów sprzężenia zwrotnego (LFSR), ponieważ można je łatwo zaimplementować w sprzęcie i szybko przeanalizować matematycznie. Jednak wykorzystanie tylko LFSR jest niewystarczające do zapewnienia dobrego bezpieczeństwa. W celu zwiększenia bezpieczeństwa LFSR opracowano różne programy.
Nieliniowe funkcje łączenia
Ponieważ LFSR są z natury liniowe, jedną z technik usuwania liniowości jest zasilanie wyjść grupy równoległych LFSR w nieliniową funkcję boole'ową, aby stworzyć generator kombinacji. Różne właściwości takiej funkcji łączenia są ważne dla zapewnienia bezpieczeństwa wynikowego schematu, na przykład w celu uniknięcia ataków korelacyjnych.
Generatory sterowane zegarem
Normalnie LFSR są regularnie sterowane. Jedną z technik wprowadzania nieliniowości jest to, że LFSR jest taktowany nieregularnie, kontrolowany przez wyjście drugiego LFSR. W skład takich generatorów wchodzi generator stop-and-go, generator zmiennostopniowy i generator obkurczający.
Generator stop and go (Beth i Piper, 1984) składa się z dwóch LFSR. Jeden LFSR jest taktowany, jeśli wyjście drugiego jest "1", w przeciwnym razie powtarza poprzednie wyjście. Wyjście to jest następnie (w niektórych wersjach) łączone z wyjściem trzeciego LFSR'a taktowanego z regularną częstotliwością.
Generator obkurczający wykorzystuje inną technikę. Stosowane są dwa LFSR-y, oba regularnie taktowane w następujący sposób:
- Jeśli moc pierwszego LFSR wynosi "1", to moc drugiego LFSR staje się mocą generatora.
- Jeśli wyjście pierwszego LFSR "0", to wyjście drugiego jest odrzucane i żaden bit nie jest wyprowadzany przez generator.
Technika ta cierpi na ataki czasowe na drugi generator, ponieważ prędkość obrotowa wyjścia jest zmienna w sposób zależny od stanu drugiego generatora. Można to poprawić poprzez buforowanie wyjścia.
Generator filtrów
Innym podejściem do poprawy bezpieczeństwa LFSR jest przekazanie całego stanu pojedynczego LFSR do nieliniowej funkcji filtrowania.
Inne projekty
Zamiast liniowego urządzenia napędowego można użyć nieliniowej funkcji aktualizacji. Na przykład Klimov i Shamir zaproponowali funkcje trójkątne (funkcje T) z jednym cyklem na n-bitowych słowach.
Bezpieczeństwo
Aby zapewnić bezpieczeństwo, okres strumienia kluczy (liczba cyfr na wyjściu przed powtórzeniem się strumienia) musi być wystarczająco duży. Jeśli sekwencja się powtarza, wówczas nakładające się na siebie szyfry mogą być wyrównane "na głębokość", a istnieją techniki, które pozwalają na ekstrakcję wygenerowanych za pomocą tych metod szyfrogramów w formie prostego tekstu.
Zastosowanie
Szyfrów strumieniowych używa się często w aplikacjach, w których zwykły tekst ma nieznaną długość, jak w przypadku bezpiecznych połączeń bezprzewodowych. Jeśli szyfr blokowy miałby być użyty w tego typu aplikacji, projektant musiałby wybrać albo wydajność transmisji, albo złożoność implementacji, ponieważ szyfr blokowy nie może pracować bezpośrednio na blokach krótszych niż ich wielkość. Na przykład, jeśli 128-bitowy szyfr blokowy odbierałby oddzielne 32-bitowe impulsy prostego tekstu, trzy czwarte przesyłanych danych wymagałoby wypełnienia. Szyfrów blokowych należy używać w trybie kradzieży lub szczątkowego zakończenia bloku, aby uniknąć wypełniania, natomiast szyfrów strumieniowych eliminuje ten problem poprzez działanie na najmniejszej przesyłanej jednostce (zazwyczaj bajtowej).
Kolejną zaletą szyfru strumieniowego w kryptografii wojskowej jest to, że strumień szyfru może być generowany przez urządzenie szyfrujące, które podlega ścisłym środkom bezpieczeństwa, a następnie jest przekazywane do innych urządzeń, np. radioodbiornika, który w ramach swojej funkcji wykona operację xor. Drugie urządzenie może być przeznaczone do użycia w mniej bezpiecznych środowiskach.
RC4 jest najczęściej stosowanym szyfrem strumieniowym w oprogramowaniu; inne obejmują: A5/1, A5/2, Chameleon, FISH, Helix, ISAAC, MUGI, Panama, Phelix, Pike, SEAL, SOBER, SOBER-128 i WAKE.
RC4 jest jednym z najczęściej używanych projektów szyfru strumieniowego.
Porównanie szyfrów strumieniowych
| Szyfr StreamCipher | CreationDate | Prędkość | (bity) | Atak | |||
| Skuteczne | Wektor inicjalizacji | Państwo Wewnętrzne | Najlepiej znany | ComputationalComplexity | |||
| A5/1 | 1989 | Głos (Wphone) | 54 | 114 | 64 | Aktywny KPA LUB | ~2 sekundy OR239.91 |
| A5/2 | 1989 | Głos (Wphone) | 54 | 114 | 64? | Aktywny | 4,6 milisekundy |
| FISH | 1993 | Całkiem szybko (Wsoft) | Ogromny | ? | ? | Znany atak kontekstowy | 211 |
| Ziarno | Przed 2004 r. | Szybko | 80 | 64 | 160 | Klucz-Derywatyzacja | 243 |
| HC-256 | Przed 2004 r. | 4 (WP4) | 256 | 256 | 65536 | ? | ? |
| ISAAC | 1996 | 2,375 (bit W64) -4 | 8-8288 Zwyczajowo | NIE DOTYCZY | 8288 | (2006) First-roundWeak-Internal-StateDerivation (Pierwsza runda) | 4.67×101240 (2001) |
| MUGI | 1998-2002 | ? | 128 | 128 | 1216 | NIE DOTYCZY (2002) | ~282 |
| PANAMA | 1998 | 2 | 256 | 128? | 1216? | Zderzenia haszowe (2001) | 282 |
| Phelix | Przed 2004 r. | do 8 (Wx86) | 256 + a 128-bitowy Nonce | 128? | ? | Różnicowy (2006) | 237 |
| Pike | 1994 | 0,9 x FISH (Wsoft) | Ogromny | ? | ? | NIE DOTYCZY (2004) | NIE DOTYCZY (2004) |
| Py | Przed 2004 r. | 2.6 | 8-2048? | 64 | 8320 | Teoria kryptoanalityczna (2006) | 275 |
| Królik | 2003-luty | 3.7(WP3)-9.7(CIEPŁY7) | 128 | 64 | 512 | NIE DOTYCZY (2006 R.) | NIE DOTYCZY (2006 R.) |
| 1987 | Imponujące | 8-2048 Zwyczajowo | 8 | 2064 | Shamir Initial-Bytes Key-Derivation OR KPA | 213 LUB 233 | |
| Salsa20 | Przed 2004 r. | 4.24 (WG4) -11 | 128 + 64-bitowy Nonce | 512 | 512 + 384 (klucz+IV+indeks) | Różnicowy (2005) | NIE DOTYCZY (2005 R.) |
| Krzyk | 2002 | 4 - 5 (Wsoft) | 128 + a 128-bit Nonce | 32? | 64-bitowa funkcja rundy | ? | ? |
| SEAL | 1997 | Bardzo szybki (W32-bit) | ? | 32? | ? | ? | ? |
| SNOW | Przed 2003 r. | Bardzo dobry (W32-bit) | 128 LUB 256 | 32 | ? | ? | ? |
| SOBER-128 | 2003 | ? | do 128 | ? | ? | Fałszerka wiadomości | 2−6 |
| SOSEMANUK | Przed 2004 r. | Bardzo dobry (W32-bit) | 128 | 128 | ? | ? | ? |
| Trivium | Przed 2004 r. | 4 (Wx86) - 8 (WLG) | 80 | 80 | 288 | Brutalny atak siłowy (2006) | 2135 |
| Turing | 2000-2003 | 5.5 (Wx86) | ? | 160 | ? | ? | ? |
| VEST | 2005 | 42 (WASIC) -64 (WFPGA) | Zmienna | Zmienna | 256 - 800 | NIE DOTYCZY (2006 R.) | NIE DOTYCZY (2006 R.) |
| WAKE | 1993 | Szybko | ? | ? | 8192 | CPA I CCA | Wrażliwe |
| Szyfr StreamCipher | CreationDate | Prędkość | (bity) | Atak | |||
| Skuteczne | Wektor inicjalizacji | Państwo Wewnętrzne | Najlepiej znany | ComputationalComplexity | |||
Powiązane strony
- eSTREAM
Pytania i odpowiedzi
P: Co to jest szyfr strumieniowy?
A: Szyfr strumieniowy to szyfr z kluczem symetrycznym, w którym bity tekstu jawnego są łączone z pseudolosowym strumieniem bitów szyfru (strumieniem klucza) za pomocą operacji wyłączenia-lub (xor).
P: Czym różni się od szyfrów blokowych?
O: Szyfry strumieniowe pracują zazwyczaj z większą prędkością niż szyfry blokowe i mają mniejsze wymagania sprzętowe. Szyfry blokowe operują na dużych blokach o stałej długości, natomiast szyfry strumieniowe szyfrują cyfry po kolei, a transformacja kolejnych cyfr zmienia się w trakcie stanu szyfrowania.
P: Jakiego rodzaju klucze są wykorzystywane?
O: Szyfry strumieniowe wykorzystują znacznie mniejsze i wygodniejsze klucze kryptograficzne, na przykład klucze 128-bitowe.
P: Jak generowany jest strumień klucza?
O: Strumień klucza jest generowany na podstawie użytego klucza kryptograficznego, w podobny sposób jak w przypadku algorytmu szyfrowania one-time pad. Ponieważ jednak strumień klucza jest pseudolosowy, a nie prawdziwie losowy, nie można zastosować zabezpieczenia związanego z one-time pad.
P: Dlaczego nie wolno używać dwa razy tego samego stanu początkowego?
O: Dwukrotne użycie tego samego stanu początkowego może prowadzić do poważnych problemów z bezpieczeństwem, ponieważ ułatwia napastnikom odszyfrowanie danych bez znajomości lub dostępu do Państwa klucza kryptograficznego.
P: Czy istnieje ryzyko związane z używaniem szyfrów strumieniowych?
O: Tak, jeżeli używa się ich nieprawidłowo lub bez zachowania odpowiednich środków ostrożności, istnieje ryzyko związane z używaniem szyfrów strumieniowych, ponieważ mogą one być całkowicie niebezpieczne, jeżeli nie są prawidłowo obsługiwane.
