SHA-3

SHA-3

Architektura „gąbki” w algorytmie Keccak
Rodzaj algorytmu

kryptograficzna funkcja skrótu

Data stworzenia

2012

Autorzy

Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche

SHA-3 (Secure Hash Algorithm 3) – kryptograficzna funkcja skrótu wyłoniona w 2012 roku w ramach konkursu ogłoszonego przez amerykański NIST[1].

Historia

Konkurs na SHA-3 rozpoczął się w 2009 roku. Zgłoszono do niego 30 kandydatów[2]. W 2012 roku NIST wyłonił jako zwycięzcę algorytm Keccak[3].

Charakterystyka

Algorytm Keccak charakteryzuje się wyższą wydajnością niż SHA-2 zarówno w implementacjach sprzętowych jak i programowych (różnica sięga 25-80% w zależności od procesora i implementacji)[4]. Keccak ma architekturę „gąbki” (ang. sponge construction) — bloki wejściowe są stopniowo „wchłaniane” w kolejnych etapach i mieszane z dużym rejestrem stanu. Blok wyjściowy jest konstruowany w podobny sposób, przez „wyciskanie” kolejnych fragmentów danych wyjściowych z rejestru stanu, wielokrotnie go mieszając pomiędzy wyciskanymi blokami. Wchłanianie i wyciskanie odbywa się na małej części rejestru stanu poprzez wykonanie funkcji binarnej alternatywy wykluczającej (xor) z danymi wejściowymi lub odczyt tej samej małej części przy odczycie danych wyjściowych. Pozostała część stanu nigdy nie jest bezpośrednio używana do konstrukcji danych wyjściowych ani nie oddziałuje bezpośrednio z danymi wejściowymi.

Funkcja mieszająca stanu (funkcja f na rysunku), składa się z wielokrotnej aplikacji funkcji rundy (do 24 razy w przypadku największej wersji algorytmu). Każda runda z kolei składa się z kompozycji 5 prostych i wydajnych w implementacji funkcji, które dokonują odwracalnych permutacji, rotacji, mieszań albo dyfuzji. Ostatnia z tych funkcji w rundzie dodatkowo jest parametryzowana stałą wartością zależną od numeru rundy (i wersji algorytmu) w celu usunięcia symetrii z funkcji rundy.

Dane wejściowe są dopełniane do całkowitej wielokrotności liczby bitów w pojedynczym bloku przy pomocy prostego schematu dopełniania zwanego „101”: do ciągu danych wejściowych w postaci ciągu binarnego dopisz bit o wartości 1, następnie bity o wartości 0, aż do przedostatniego bitu w pełnym bloku, następnie dopisz bit o wartości 1 dopełniając blok całkowicie.

Implementacje

Dostępne są implementacje w językach: C/C++, Java, VHDL, Python[5], Rust[6], Cryptol[7], .NET C#.

Przypisy

  1. ↑ NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition. National Institute of Standards and Technology, 2012.
  2. ↑ Trzydziestu kandydatów do SHA-3. IPSec.pl, 4 listopada 2009. [dostęp 2012-10-09]. [zarchiwizowane z tego adresu (11 lutego 2011)].
  3. ↑ Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche: The Keccak sponge function family.
  4. ↑ Thomas Pornin: Comparative Performance Review of the SHA-3 Second-Round Candidates. 2010.
  5. ↑ Software and other files. The Keccak sponge function family.
  6. ↑ libOctavo/octavo.
  7. ↑ Alfonso De Gregorio: Untwisted: A Cryptol Implementation of Keccak – Part 1. 2011. [dostęp 2012-10-09]. [zarchiwizowane z tego adresu (2013-04-07)].

Media użyte na tej stronie

SpongeConstruction.svg
(c) http://sponge.noekeon.org/, CC BY 3.0
A diagram showing the sponge construction for cryptographic hash functions.