Сунђер конструкција

У криптографији, сунђер функција или сунђер конструкција је класа алгоритама са коначним унутрашњим стањем, чији је улаз бинарни низ произвољне дужине и који враћају бинарни низ произвољне дужине. Сунђер функције имају теоријску и практичну примену. Могу се користити за имплементацију хеш функције, аутентикационог кода поруке, проточне шифре, генераторa псеудослучајних бројева, аутентификованог шифровања и MGF (енгл. mask generation function).

Конструкција

Сунђер функција састоји се из три компоненте^[1]:

S меморије, која садржи b битова
функцијe $f:\{0,1\}^{|bits|}\rightarrow \{0,1\}^{|bits|}$ која трансформише меморију стања (често је псеудослучајна пермутација $2^{|bits|}$ вредности стања)
функцијe допуњавања P

Стање меморије S подељенo je на два дела: први део је R, величине r (брзина, rate), a преостали део је C, величинe c (капацитет, capacity). Функција допуњавања додаје потребан број битова на крај улазне ниске тако да дужина допуњене ниске буде дељива са r. На тај начин се допуњена порука може поделити на r-битне блокове.

Опис рада

Сунђер функција делује на следећи начин:

Стање S се иницијализује нулама
Улазна ниска се допуњује и дели на блокове, величине r битова
Фаза упијања података: За сваки блок B, величине r битова
- R се замењује са R XOR B (битска операција XOR)
- S се замењује са f(S)

Фаза истискивања резултата: Укључити део R стања S у излаз
Понављати све док није обезбеђен довољан број излазних бита
- заменити S са f(S)
- Укључити део R стања S у излаз; ако у излазу недостаје мање од r битова, у излаз се укључује само део R

Битови из дела C не учествују у операцији XOR, нити се директно укључују у излаз, већ се мењају у зависности од функције трансформације f. У хеш апликацијама, отпорност на колизије или одређивање инверзне слике зависе од C. Величина c дела C обично се бира тако да буде једнака двострукој вредности нивоа сигурности.

Дуплексна конструкција

Фазе упијања и истискивања могу се наизменично смењивати^[2]. Овакав начин рада назива се дуплексна конструкција или дуплексирање. Mоже се искористити за једнопролазни систем аутентификованог шифровања.

Стање S се иницијализује нулама
R се XOR-ује са првим улазним r-битним блоком
S се замењује са f(S)
R je сада првих r битова излаза
R се XOR-ује са наредним улазним блоком
S се замењује са f(S)
R даје наредних r битова излаза

Режим са преписивањем

Toком упијања могуће је изоставити операцију XOR, уз задржавање одабраног нивоа сигурности ^[2]. У фази упијања замењује се претходни део стања R. Oво омогућава задржавање мањег стања између корака: пошто се део R ионако брише, може се чувати само део C.

Примене

Сунђер функције имају теоријске и практичне примене. У теоријској криптоанализи случајна сунђер функција је сунђер конструкција у оквиру које је f случајна пермутација или трансформација, према потреби. На пример, криптографски сунђер Кечак са 1600-битним стањем NIST је изабрао за победника конкурса за хеш алгоритам SHA-3^[3]. Модификована верзија алгоритма RC-4 која се зове Spirtz такође користи сунђер конструкцију. Такође, користи се за изградњу аутентификованог шифровања са придруженим подацима (АЕАD)^[4], у оквиру схема за хеширање лозинке ^[5].

Референце

^ Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche. „Sponge Functions”. Ecrypt Hash Workshop 2007.
^ ^а ^б 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. Приступљено 4. 10. 2012.
^ Rivest, Ron; Schuldt, Jacob (27. 10. 2014). „Spritz – a spongy RC4-like stream cipher and hash function” (PDF). Приступљено 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. стр. 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. Приступљено 4. 10. 2012.

[Rivest2014-4] Rivest, Ron; Schuldt, Jacob (27. 10. 2014). „Spritz – a spongy RC4-like stream cipher and hash function” (PDF). Приступљено 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. стр. 1—5. arXiv:1807.05764 . doi:10.1109/ISCAS.2019.8702498.

[1]

[2]

[3]

[4]

[5]