Funcția burete
În criptografie , o funcție de burete sau construcție de burete este o clasă de algoritmi cu stări interne finite care, luând o intrare de orice lungime, produc o ieșire de lungimea dorită. Funcțiile burete au atât utilizări teoretice, cât și practice. Ele pot fi utilizate pentru modelarea sau implementarea multor primitive criptografice, cum ar fi algoritmi, hash criptografic , cod de autentificare a mesajelor , cifrări de flux , cifrări bloc , generatoare de numere pseudo-aleatorii și criptare autentificată . [1]
Constructie
O funcție de burete este formată din 3 componente: [2]
- o memorie de stare, S, care conține b biți,
- o funcție, f , de lungime fixă care permite sau transformă memoria de stare,
- o funcție de umplere P
Memoria de stare este împărțită în două secțiuni, R de dimensiunea r bit și C de dimensiunea c = b - r . Parametrul r se numește bitrate , în timp ce parametrul c se numește capacitate .
Funcția de umplere adaugă biți la șirul de intrare, astfel încât lungimea șirului să fie un multiplu întreg al ratei de biți r . Șirul de intrare îmbogățit poate fi apoi împărțit în blocuri de r biți.
Operațiuni
Funcția burete funcționează după cum urmează:
- Starea S este inițializată la zero
- Șirul de intrare este îmbogățit, ceea ce înseamnă că intrarea este transformată în blocuri de r biți utilizând funcția de umplere P.
- Se calculează XOR între R și primul bloc de r biți ai intrării îmbogățite
- S se înlocuiește cu f (S)
- Se calculează XOR între R și următorul bloc de r -bit (dacă există)
- S se înlocuiește cu f (S)
- ...
Procesul se repetă până când toate blocurile șirului de intrare îmbogățit sunt procesate („absorbite” în metafora buretelui ).
Ieșirea funcției burete este apoi gata să fie returnată („stoarsă”) astfel:
- Primii r biți ai ieșirii sunt echivalenți cu porțiunea R a memoriei de stare,
- Dacă doriți să obțineți alți biți în șirul de ieșire, atunci S este înlocuit cu f (S)
- Următorii r biți ai ieșirii sunt echivalenți cu porțiunea R a memoriei de stare
- ...
Procesul se repetă până când sunt produși toți biții de ieșire doriti. Dacă lungimea ieșirii nu este un multiplu al lui r, atunci aceasta va fi trunchiată.
Trebuie remarcat faptul că XOR nu se aplică niciodată între biții de intrare și porțiunea C a memoriei de stare și nici nu se returnează vreodată biții C. C este modificat doar de biții de intrare prin funcția f . În aplicațiile de hashing, rezistența la coliziune și atacurile de pre-imagine depinde de parametrul C. Magnitudinea sa, „capacitatea” c, este , în general, dublă față de nivelul de rezistență dorit.
Aplicații
Funcțiile burete au atât utilizări teoretice, cât și practice. În criptografia teoretică, o funcție de burete aleatoriu este o construcție de burete în care f este o permutare sau transformare aleatorie. Funcțiile de burete aleatorii depășesc limitări mai practice ale primitivelor criptografice decât modelul de oracol aleatoriu utilizat pe scară largă. Acest lucru se întâmplă datorită memoriei interne de stare finită. [3]
Construcțiile de burete pot fi folosite și pentru a crea primitive criptografice. De exemplu, funcția de hash Keccak este implementată ca o funcție burete. O versiune a Keccak, implementată folosind memoria de stare pe 1600 de biți, a fost selectată de NIST ca câștigătoare a competiției SHA-3 . Robustețea lui Keccak derivă din permutația ciclică complicată a funcției f dezvoltată de autorii săi. [4]
Notă
- ^(EN) Echipa Keccak, Duplexing The Sponge (PDF) pe sponge.noekeon.org.
- ^(EN) Guido Bertoni, Joan Daemen, Michaël Peeters și Gilles Van Assche, Sponge Functions pe sponge.noekeon.org, ECRYPT Hash Workshop 2007.
- ^(EN) Guido Bertoni, Joan Daemen, Michaël Peeters și Gilles Van Assche Despre indiferențialitatea construcției de burete pe sponge.noekeon.org, EUROCRYPT 2008.
- ^ ( RO ) 2012-10-02, NIST selectează câștigătorul concursului Secure Hash Algorithm (SHA-3) , la nist.gov , NIST . Accesat la 4 octombrie 2012 .
