Crypto-IT

• Długość klucza: maksymalnie 2048 bitów

RC4 to symetryczny szyfr strumieniowy, szczególnie znany i ceniony za prostotę implementacji i szybkość działania.

Autorem szyfru RC4 jest amerykański profesor Ron Rivest, który zaprojektował go w 1987 roku. Jest on założycielem firmy RSA Security. Szczegóły implementacji szyfru RC4 nie były znane aż do roku 1994, kiedy to zostały anonimowo wysłane na listę mailingową Cypherpunks. Szyfr RC4 jest często określany jako ARCFOUR lub ARC4 dla uniknięcia problemów prawnych z zastrzeżoną nazwą RC4. Skrót RC4 pochodzi oficjalnie od "Rivest Cipher 4", ale akronim RC jest też alternatywnie rozumiany jako "Ron's Code" (ang. kod Rona).

RC4 jest jednym z najbardziej popularnych szyfrów symetrycznych. Jest wykorzystywany w wielu protokołach, na przykład do ochrony komunikacji w Internecie - TLS (ang. Transport Layer Security) lub w zabezpieczeniach sieci bezprzewodowych - WEP (ang. Wired Equivalent Privacy).

RC4 jest szyfrem strumieniowym. Jego działanie polega na tworzeniu długich sekwencji bajtów klucza, które są następnie dodawane do bajtów danych.

Szyfrowanie za pomocą RC4 polega na sumowaniu XOR kolejnych bajtów wiadomości z kolejnymi bajtami strumienia klucza. Cały algorytm RC4 koncentruje się na tworzeniu kolejnych bajtów strumienia. Strumień bajtów klucza otrzymywany jest z jednowymiarowej tablicy, nazywanej tabelą T.

Tabela T ma długość 256 bajtów. Jest wypełniana bajtami na podstawie wartości sekretnego klucza, przed rozpoczęciem operacji szyfrowania lub deszyfrowania. Następujące operacje powinny zostać wykonane, aby utworzyć tabelę:

1. W każdą komórkę tablicy wpisywana jest liczba odpowiadająca numerowi jej pozycji (licząc od zera).
2. Tworzona jest zmienna pomocnicza i inicjowana na 0.
3. Dla każdej liczby w tablicy (numery przyjmują wartości kolejno od 0 do 255) wykonywane są dwie operacje:
   1. Wartość zmiennej pomocniczej jest modyfikowana (patrz: Funkcje Matematyczne).
   2. Liczba w tablicy w aktualnej pozycji jest zamieniana miejscem z liczbą w tabeli w pozycji określonej przez zmienną pomocniczą.

W trakcie szyfrowania i deszyfrowania generowane są bajty strumienia klucza, które następnie sumuje się XOR z bajtami wiadomości Bajty strumienia klucza produkowane są na podstawie tablicy T. Następujące kroki są wykonywane:

1. Tworzone są dwie zmienne pomocnicze p₁ i p₂, obie inicjowane są na 0.
2. Do zmiennej p₁ dodaje się 1, a wynik dzieli modulo przez 256.
3. Do zmiennej p₂ dodaje się wartość tablicy na pozycji p₁ (czyli T[p₁]), a wynik dzieli modulo przez 256.
4. Zamienia się miejscami wartości tablicy na pozycjach p₁ i p₂.
5. Sumuje się dwie wartości tablicy na pozycjach p₁ i p₂, a wynik dzieli modulo przez 256. Następnie wynik przypisuje się do nowej zmiennej pomocniczej p₃.
6. Wartość tablicy na pozycji p₃ jest kolejnym bajtem strumienia klucza.
7. Jeśli potrzebne są kolejne bajty strumienia klucza, to należy wrócić do punktu II i powtórzyć powyższe kroki.

Algorytm RC4 jest zaprojektowany specjalnie do stosowania w programach komputerowych, ponieważ jedynymi wykonywanymi operacjami są działania na pojedynczych bajtach. W przeciwieństwie do wielu szyfrów strumieniowych nie wykorzystuje się rejestrów LFSR, które dobrze sprawdzają się w rozwiązaniach sprzętowych, ale znacznie gorzej w implementacjach programistycznych.

Szyfr RC4 został zaprojektowany już jakiś czas temu i w związku z tym ma kilka słabości, które zostały poprawione w nowszych algorytmach szyfrów strumieniowych. Można wskazać zauważyć, że niektóre kombinacje bajtów w strumieniu klucza są nieco bardziej prawdopodobne niż inne. Szereg takich kombinacji został znalezionych w ciągu ostatnich 20 lat oraz powstało kilka ataków bazujących na tej podatności.

Prawdopodobnie największą słabością szyfru RC4 jest niewystarczające mieszanie bajtów sekretnego klucza. Sprawia to, że można wydobyć pewne informacje odnośnie bajtów w sekretnym kluczu, analizując początkowe znaki strumienia klucza. Z tego powodu, zalecane jest odrzucanie pewnej liczby początkowych bajtów tworzonego strumienia klucza. Taki ulepszony algorytm jest określany jako RC4-dropN, gdzie N jest zwykle wielokrotnością liczby 256.

Oprócz sekretnego klucza, algorytm RC4 nie pobiera dodatkowego numeru nonce dla każdej operacji szyfrowania. Wobec tego, system kryptograficzny musi samodzielnie zadbać o to, żeby wartości, z których tworzony jest strumień klucza były unikalne, czyli w jaki sposób połączyć oryginalny klucz szyfrujący z unikalnym numerem nonce. Najlepszym sposobem byłoby użycie funkcji haszujących na bajtach połączonych klucza i nonce, a następnie wykorzystać wyjście z tej funkcji do zainicjowania strumienia bajtów klucza dla szyfru RC4. Niestety, wiele aplikacji po prostu łączy bajty klucza i bajty nonce w jeden ciąg, który następnie jest używany do szyfrowania. Takie systemy stają się podatne na ataki opierające się na podobieństwie kluczy szyfrujących. Ta słabość szyfru RC4 była użyta podczas ataku Fluhrer'a, Mantin'a i Shamir'a (FMS) przeciwko zabezpieczeniom WEP, opublikowanym w roku 2001.

Podczas inicjowania tablicy T o długości 256 bajtów służącej do późniejszego generowania bajtów strumienia klucza, dla każdego elementu tablicy modyfikuje się wartość zmiennej pomocniczej. Liczba ta jest następnie wykorzystywana do zamiany wartości elementów tej tablicy.

• x_pom - zmienna pomocnicza,
• w_akt - wartość aktualnej pozycji w tabeli T,
• k_{akt mod dł(K)} - wartość bajtu klucza w aktualnej pozycji podzielonej modulo przez długość klucza (ponieważ sekretny klucz może być krótszy niż 256 bajtów),
• mod 256 - to dzielenie modulo przez 256 (czyli pobranie reszty z dzielenia)

Po wyliczeniu wartości zmiennej pomocniczej w sposób przedstawiony powyżej, algorytm szyfrujący RC4 zamienia miejscami numery w tablicy T na pozycjach aktualnej i określonej przez zmienną pomocniczą. Pozycje w tabeli numeruje się od 0.

Inicjalizacja tablicy T służącej do generowania bajtów strumienia klucza. Zmienna K to wektor bajtów sekretnego klucza o długości k_len.

for i from 0 to 255
    T[i] := i
endfor
x_temp := 0
for i from 0 to 255
    x_temp := (x_temp + T[i] + K[i mod k_len]) mod 256
    swap(T[i], T[x_temp])
endfor

Podczas generowanie bajtów klucza, poniższa pętla wykonuje się tak długo, jak długo nowe bajty są potrzebne.

p1 := 0
p2 := 0
while GeneratingOutput
    p1 := (p1 + 1) mod 256
    p2 := (p2 + T[p1]) mod 256
    swap(T[p1], T[p2])
    send(T[(T[p1] + T[p2]) mod 256])
endwhile