Funkcja gąbki

Konstrukcja gąbki dla funkcji mieszających. P _i to bloki łańcucha wejściowego, Z _i to zahaszowane bloki wyjściowe.

W kryptografii funkcja gąbki lub konstrukcja gąbki to dowolna klasa algorytmów o skończonym stanie wewnętrznym , które pobierają wejściowy strumień bitów o dowolnej długości i wytwarzają wyjściowy strumień bitów o dowolnej pożądanej długości. Funkcje gąbczaste mają zastosowanie zarówno teoretyczne, jak i praktyczne. Można je wykorzystać do modelowania lub implementacji wielu prymitywów kryptograficznych , w tym skrótów kryptograficznych , kodów uwierzytelniających wiadomości , funkcji generowania masek , szyfry strumieniowe , generatory liczb pseudolosowych i uwierzytelnione szyfrowanie .

Budowa

Funkcja gąbki jest zbudowana z trzech elementów:

• pamięć stanu S zawierająca b bitów,
• funkcja ${\ Displaystyle f: \ {0,1 \} ^ {b} \ strzałka w prawo \ {0,1 \} ^ {b}}$
• funkcja wypełniająca P

S jest podzielony na dwie sekcje: jedną o rozmiarze r (szybkość transmisji) i pozostałą część o rozmiarze c (pojemność). Sekcje te są oznaczone odpowiednio jako R i C.

f tworzy pseudolosową permutację stanów $_$ S . _

P dodaje wystarczającą liczbę bitów do ciągu wejściowego, aby długość uzupełnionego wejścia była całkowitą wielokrotnością szybkości transmisji bitów, r . Oznacza to, że dane wejściowe są podzielone na bloki r bitów.

Operacja

Funkcja gąbki „pochłania” (w metaforze gąbki ) wszystkie bloki wypełnionego ciągu wejściowego w następujący sposób:

• S jest inicjalizowany na zero
• dla każdego r -bitowego bloku B z P (string)
  • R jest zastępowane przez R XOR B (przy użyciu bitowego XOR )
  • S zostaje zastąpione przez f ( S )

Wyjście funkcji gąbki jest teraz gotowe do wytworzenia („wyciśnięte”) w następujący sposób:

• powtarzać
  • wyprowadź część R z S
  • S jest zastępowane przez f ( S ), chyba że wyjście jest pełne

Jeśli do wysłania pozostało mniej niż r bitów, wówczas R zostanie obcięte ( wyprowadzona zostanie tylko część R ).

Inna metafora opisuje pamięć stanu jako „ pulę entropii ”, z danymi wejściowymi „wlewanymi” do puli, a funkcją transformacji określaną jako „mieszanie puli entropii”.

Należy zauważyć, że bity wejściowe nigdy nie są poddawane operacji XOR w części C pamięci stanu, ani żadne bity C nie są wyprowadzane bezpośrednio. Zakres, w jakim C jest zmieniany przez dane wejściowe, zależy całkowicie od funkcji transformacji f . W zastosowaniach mieszających odporność na kolizje lub ataki przedobrazowe zależy od C , a jego rozmiar („pojemność” c ) jest zwykle dwukrotnie większy od pożądanego poziomu oporu.

Konstrukcja dwustronna

Możliwe jest również wchłanianie i wyciskanie naprzemiennie. Ta operacja nazywana jest konstrukcją dupleksową lub dupleksowaniem. Może stanowić podstawę systemu szyfrowania uwierzytelnionego jednym przebiegiem.

• Stan S jest inicjalizowany na zero
• R jest XORowane z pierwszym r -bitowym blokiem wejścia
• S zostaje zastąpione przez f ( S )
• R to teraz pierwsze r bitów danych wyjściowych.
• R jest XORowany z następnym r -bitowym blokiem wejścia
• S zostaje zastąpione przez f ( S )
• R to teraz kolejne r bitów danych wyjściowych.
• …

Tryb nadpisywania

Możliwe jest pominięcie operacji XOR podczas absorpcji, przy zachowaniu wybranego poziomu bezpieczeństwa . W tym trybie, w fazie pochłaniania, kolejny blok wejścia nadpisuje R stanu. Pozwala to na utrzymanie mniejszego stanu między krokami. Ponieważ R i tak zostanie nadpisana, można ją z góry wyrzucić, należy zachować tylko część C.

Aplikacje

Funkcje gąbczaste mają zastosowanie zarówno teoretyczne, jak i praktyczne. W kryptoanalizie teoretycznej losowa funkcja gąbki jest konstrukcją gąbki, gdzie f jest odpowiednio losową permutacją lub transformacją. Losowe funkcje gąbki wychwytują więcej praktycznych ograniczeń prymitywów kryptograficznych niż szeroko stosowany losowej wyroczni , w szczególności skończony stan wewnętrzny.

Konstrukcję gąbki można również wykorzystać do budowy praktycznych prymitywów kryptograficznych. Na przykład Keccak o stanie 1600-bitowym została wybrana przez NIST jako zwycięzca w konkursie SHA-3 . Siła Keccak wywodzi się z zawiłej, wielookrągłej permutacji f , którą opracowali jej autorzy. Przeprojektowanie RC4 o nazwie Spritz odnosi się do konstrukcji gąbki w celu zdefiniowania algorytmu.

W innych przykładach funkcja gąbki może służyć do budowania uwierzytelnionego szyfrowania z powiązanymi danymi (AEAD), a także schematów mieszania haseł .