Funkce houba - Sponge function
V kryptografii je funkce houba nebo konstrukce houby libovolnou třídou algoritmů s konečným vnitřním stavem, které přijímají vstupní bitový proud libovolné délky a vytvářejí výstupní bitový proud libovolné délky. Funkce houby mají teoretické i praktické využití. Lze je použít k modelování nebo implementaci mnoha kryptografických primitiv , včetně kryptografických hashů , ověřovacích kódů zpráv , funkcí generování masek , šifrovacích proudů , generátorů pseudonáhodných čísel a ověřeného šifrování .
Konstrukce
Funkce houba se skládá ze tří složek:
- paměť stavu, S , obsahující b bitů,
- funkce, která transformuje stavovou paměť (často se jedná o pseudonáhodnou permutaci stavových hodnot)
- funkce polstrování P
Stavová paměť je rozdělena do dvou částí: jedna o velikosti r (bitrate) a zbývající část o velikosti c (kapacita). Tyto sekce jsou označeny R a C, v tomto pořadí.
Funkce padding připojí k vstupnímu řetězci dostatek bitů, takže délka polstrovaného vstupu je celý násobek bitrate r . Polstrovaný vstup lze tedy rozdělit na bloky r- bit.
Úkon
Funkce houba funguje následovně:
- Stav S je inicializován na nulu
- Vstupní řetězec je polstrovaný. To znamená, že vstup je transformován do bloků r bitů pomocí funkce polstrování P .
- pro každý r -bitový blok B polstrovaného vstupu:
- R je nahrazeno R XOR B (pomocí bitového XOR )
- S je nahrazeno f ( S )
Tento proces „pohltí“ (v metaforě houby ) všechny bloky polstrovaného vstupního řetězce.
Výstup funkce houba je nyní připraven k výrobě („vytlačen“) následujícím způsobem:
- na výstupu je část R státní paměti
- opakujte, dokud nebude vydáno dostatek bitů:
- S je nahrazeno f ( S )
- na výstupu je část R státní paměti
Pokud zbývá na výstupu méně než r bitů, bude R zkráceno ( na výstup bude pouze část R ).
Další metafora popisuje stavovou paměť jako „ entropický fond “, se vstupem „nalil do“ fondu a transformační funkce označovaná jako „míchání entropického fondu“.
Všimněte si, že vstupní bity nikdy nejsou XORy do C části stavové paměti, ani nejsou přímo vyvedeny žádné bity C. Rozsah, ve kterém je C změněn vstupem, zcela závisí na transformační funkci f. V hašovacích aplikacích odolnost proti kolizi nebo útokům předběžného obrazu závisí na C a jeho velikost („kapacita“ c ) je obvykle dvojnásobná než požadovaná úroveň odporu.
Duplexní konstrukce
Je také možné vstřebávat a mačkat střídavě. Tato operace se nazývá duplexní konstrukce nebo duplexování. Může to být základem ověřovacího šifrovacího systému s jedním průchodem.
- Stav S je inicializován na nulu
- R je XORed s prvním r -bitovým blokem vstupu
- S je nahrazeno f ( S )
- R je nyní prvních r bitů výstupu.
- R je XORed s dalším r -bitovým blokem vstupu
- S je nahrazeno f ( S )
- R je nyní dalších r bitů výstupu.
- …
Přepsat režim
Během absorpce je možné vynechat operace XOR při zachování zvolené úrovně zabezpečení . V tomto režimu v absorpční fázi další blok vstupu přepíše R část stavu. To umožňuje udržovat mezi kroky menší stav. Vzhledem k tomu, že část R bude stejně přepsána, lze ji předem zahodit, je nutné ponechat pouze část C.
Aplikace
Funkce houby mají teoretické i praktické využití. V teoretické dešifrování je náhodná funkce houba konstrukcí houby, kde f je náhodná permutace nebo transformace, jak je to vhodné. Funkce náhodné houby zachycují více praktických omezení kryptografických primitiv než široce používaný model náhodných věštců , zejména konečný vnitřní stav.
Konstrukci houby lze také použít k vytvoření praktických kryptografických primitiv. Například kryptografická houba Keccak se 1600bitovým stavem byla vybrána NIST jako vítěz v soutěži SHA-3 . Síla Keccak pochází ze složitého, vícekolového permutace f , že její autoři vyvinuli. Návrh RC4 zvaný Spritz odkazuje na konstrukci houby k definování algoritmu.
Pro další příklad lze použít funkci houba k vytvoření ověřeného šifrování s přidruženými daty (AEAD).
