Sunđer konstrukcija

U kriptografiji, sunđer funkcija ili sunđer konstrukcija je klasa algoritama sa konačnim unutrašnjim stanjem, čiji je ulaz binarni niz proizvoljne dužine i koji vraćaju binarni niz proizvoljne dužine. Sunđer funkcije imaju teorijsku i praktičnu primenu. Mogu se koristiti za implementaciju heš funkcije, autentikacionog koda poruke, protočne šifre, generatora pseudoslučajnih brojeva, autentifikovanog šifrovanja i MGF (engl. mask generation function).

Konstrukcija[uredi | uredi izvor]

Sunđer funkcija sastoji se iz tri komponente^[1]:

S memorije, koja sadrži b bitova
funkcije $f:\{0,1\}^{|bits|}\rightarrow \{0,1\}^{|bits|}$ koja transformiše memoriju stanja (često je pseudoslučajna permutacija $2^{|bits|}$ vrednosti stanja)
funkcije dopunjavanja P

Stanje memorije S podeljeno je na dva dela: prvi deo je R, veličine r (brzina, rate), a preostali deo je C, veličine c (kapacitet, capacity). Funkcija dopunjavanja dodaje potreban broj bitova na kraj ulazne niske tako da dužina dopunjene niske bude deljiva sa r. Na taj način se dopunjena poruka može podeliti na r-bitne blokove.

Opis rada[uredi | uredi izvor]

Sunđer funkcija deluje na sledeći način:

Stanje S se inicijalizuje nulama
Ulazna niska se dopunjuje i deli na blokove, veličine r bitova
Faza upijanja podataka: Za svaki blok B, veličine r bitova
- R se zamenjuje sa R XOR B (bitska operacija XOR)
- S se zamenjuje sa f(S)

Faza istiskivanja rezultata: Uključiti deo R stanja S u izlaz
Ponavljati sve dok nije obezbeđen dovoljan broj izlaznih bita
- zameniti S sa f(S)
- Uključiti deo R stanja S u izlaz; ako u izlazu nedostaje manje od r bitova, u izlaz se uključuje samo deo R

Bitovi iz dela C ne učestvuju u operaciji XOR, niti se direktno uključuju u izlaz, već se menjaju u zavisnosti od funkcije transformacije f. U heš aplikacijama, otpornost na kolizije ili određivanje inverzne slike zavise od C. Veličina c dela C obično se bira tako da bude jednaka dvostrukoj vrednosti nivoa sigurnosti.

Dupleksna konstrukcija[uredi | uredi izvor]

Faze upijanja i istiskivanja mogu se naizmenično smenjivati^[2]. Ovakav način rada naziva se dupleksna konstrukcija ili dupleksiranje. Može se iskoristiti za jednoprolazni sistem autentifikovanog šifrovanja.

Stanje S se inicijalizuje nulama
R se XOR-uje sa prvim ulaznim r-bitnim blokom
S se zamenjuje sa f(S)
R je sada prvih r bitova izlaza
R se XOR-uje sa narednim ulaznim blokom
S se zamenjuje sa f(S)
R daje narednih r bitova izlaza

Režim sa prepisivanjem[uredi | uredi izvor]

Tokom upijanja moguće je izostaviti operaciju XOR, uz zadržavanje odabranog nivoa sigurnosti ^[2]. U fazi upijanja zamenjuje se prethodni deo stanja R. Ovo omogućava zadržavanje manjeg stanja između koraka: pošto se deo R ionako briše, može se čuvati samo deo C.

Primene[uredi | uredi izvor]

Sunđer funkcije imaju teorijske i praktične primene. U teorijskoj kriptoanalizi slučajna sunđer funkcija je sunđer konstrukcija u okviru koje je f slučajna permutacija ili transformacija, prema potrebi. Na primer, kriptografski sunđer Kečak sa 1600-bitnim stanjem NIST je izabrao za pobednika konkursa za heš algoritam SHA-3^[3]. Modifikovana verzija algoritma RC-4 koja se zove Spirtz takođe koristi sunđer konstrukciju. Takođe, koristi se za izgradnju autentifikovanog šifrovanja sa pridruženim podacima (AEAD)^[4], u okviru shema za heširanje lozinke ^[5].

Reference[uredi | uredi izvor]

^ Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche. „Sponge Functions”. Ecrypt Hash Workshop 2007.
^ ^a ^b Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche. „Duplexing the sponge: single-pass authenticated encryption and other applications” (PDF).
^ Boutin, Chad (2. 10. 2012). „NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition”. NIST. Pristupljeno 4. 10. 2012.
^ Rivest, Ron; Schuldt, Jacob (27. 10. 2014). „Spritz – a spongy RC4-like stream cipher and hash function” (PDF). Pristupljeno 29. 12. 2014.
^ van Beirendonck, M.; Trudeau, L.; Giard, P.; Balatsoukas-Stimming, A. (29. 5. 2019). A Lyra2 FPGA Core for Lyra2REv2-Based Cryptocurrencies. IEEE International Symposium on Circuits and Systems (ISCAS). Sapporo, Japan: IEEE. str. 1—5. arXiv:1807.05764 . doi:10.1109/ISCAS.2019.8702498.

[1] Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche. „Sponge Functions”. Ecrypt Hash Workshop 2007.

[duplex-2] Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche. „Duplexing the sponge: single-pass authenticated encryption and other applications” (PDF).

[3] Boutin, Chad (2. 10. 2012). „NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition”. NIST. Pristupljeno 4. 10. 2012.

[Rivest2014-4] Rivest, Ron; Schuldt, Jacob (27. 10. 2014). „Spritz – a spongy RC4-like stream cipher and hash function” (PDF). Pristupljeno 29. 12. 2014.

[lyra2ToC-5] van Beirendonck, M.; Trudeau, L.; Giard, P.; Balatsoukas-Stimming, A. (29. 5. 2019). A Lyra2 FPGA Core for Lyra2REv2-Based Cryptocurrencies. IEEE International Symposium on Circuits and Systems (ISCAS). Sapporo, Japan: IEEE. str. 1—5. arXiv:1807.05764 . doi:10.1109/ISCAS.2019.8702498.

[1]

[2]

[3]

[4]

[5]