Panama (funcție hash)

Panama [1] este o primitivă criptografică care poate fi folosită fie ca funcție hash criptografică, fie ca cifră de flux. A fost dezvoltat în 1998 de Joan Dymen și Craig Klep pentru a îmbunătăți eficiența software-ului pentru arhitecturi pe 32 de biți. Este unul dintre progenitorii algoritmului de hashing Keccak , care a devenit câștigătorul competiției de primitive criptografice de la Institutul Național de Standarde și Tehnologie din SUA [2] . Se bazează în mare măsură pe modulul hash de streaming StepRightUp. [3]

Caracteristici

Potrivit dezvoltatorilor, „Panama” la momentul dezvoltării avea un nivel ridicat de securitate, dar acest lucru a fost realizat cu prețul unei sarcini de calcul uriașe. Prin urmare, după cum s-a dovedit, „Panama” ca funcție hash s-a dovedit a fi mai puțin potrivită pentru hashing mesaje decât rivalii săi. Dacă vorbim despre „Panama” ca un cifru de flux, atunci o procedură lungă de inițializare s-a dovedit a fi o trăsătură distinctivă a utilizării sale. Prin urmare, atunci când îl utilizați în sarcini care necesită viteze mari, este necesar să se asigure toate condițiile care vor avea drept scop reducerea numărului de desincronizări. [patru]

S-a presupus că „Panama” va fi folosit în criptarea sau decriptarea videoclipurilor pentru a accesa unele aplicații, în special „TV-ul cu plată”. [5] Logica dezvoltatorilor a fost că set-top box-urile și televizoarele digitale vor folosi procesoare de mare viteză, iar Panama nu ar încărca prea mult aceste procesoare în timpul decriptării.

Structura

„Panama” se bazează pe o mașină cu stări finite, constând din două blocuri mari: 544 de biți de stare și un buffer de 8192 de biți, funcționând pe principiul unui registru cu deplasare cu feedback . Feedback-ul asigură că biții de intrare trec prin mai multe iterații după intrare, ceea ce la rândul său asigură difuzia pe biți. Trebuie să spun că un buffer similar este folosit în funcția de compresie SHA. [6] Obiectul de lucru Panama este un cuvânt de 32 de biți și starea constă din 17 astfel de cuvinte, în timp ce bufferul are 32 de celule, fiecare dintre ele conține 8 astfel de cuvinte. [7]

Operațiuni

Panama poate actualiza tamponul și statele prin iterare. Iar pentru funcția iterativă sunt implementate trei moduri: „Reset”, „Push” și „Pull”. În modul „Push”, aparatul primește o anumită intrare, dar nu scoate nimic. În modul „Pull”, dimpotrivă, se formează datele de ieșire, dar nimic nu este luat ca intrare. De asemenea, o „iterație Pull goală” înseamnă că rezultatul din acea iterație este aruncat. În modul „Resetare”, starea și tamponul sunt resetate la zero. [opt]

Schimbarea stării este caracterizată de difuzie ridicată și neliniaritate distribuită. [9] Aceasta înseamnă că un număr mic de iterații este suficient pentru a obține o dispersie bună. Acest lucru se face folosind 4 blocuri, fiecare își rezolvă propria sarcină.

Primul rezolvă problema neliniarității.
Al doilea oferă dispersie pe biți.
Al treilea creează difuzie pe biți.
Al patrulea introduce un buffer și date de intrare. [zece]

Dacă considerăm „Panama” ca o funcție hash, atunci algoritmul pentru funcționarea sa este următorul. Inițial, funcția hash acceptă toate blocurile de mesaje. După aceea, sunt efectuate mai multe iterații „Push”, ceea ce permite ca ultimele blocuri de mesaje primite să fie împrăștiate în interiorul tamponului și al stării. După aceea, se efectuează ultima iterație „Pull”, care vă permite să obțineți rezultatul hash. Schema de criptare în flux este inițializată după cum urmează: în primul rând, trec două iterații „Push” pentru a obține cheia și parametrul de diversificare. După aceea, apar o serie de iterații „Pull” pentru a dispersa cheia și parametrul în interiorul bufferului și stărilor. Aceasta finalizează inițializarea și Panama este gata să creeze biți din secvența de ieșire prin efectuarea iterațiilor „Pull”. [3]

Cum funcționează

Puteți desemna starea ca , iar cele 17 cuvinte care definesc stările pot fi desemnate ca . Buffer-ul este notat ca , celula sa - ca și unul dintre cuvintele care se află în interiorul acestei celule - ca . Inițial, atât starea, cât și memoria tampon sunt umplute doar cu zerouri. În modul „Push”, „Panama” primește un cuvânt de 8 biți ca intrare, în modul „Pull”, un cuvânt de 8 biți este format ca ieșire. [7] $A$ $a0...a16$ $B$ $j$ $b^{j}$ $b_{i}^{j)$

Dacă desemnăm funcția care actualizează tamponul ca , atunci, dacă acceptăm că , putem obține următoarele reguli pentru actualizarea tamponului: $\lambda$ $d=\lambda (b)$

d^{j}=b^{j-1)

la ,

j\notin {0...25}

d^{0}=b^{31}\oplus q

d_{i}^{25}=b_{i}^{24}\oplus b_{i+2mod8}^{31)

pentru

0<i<8

unde în modul „Push” există un bloc de intrare , iar în modul „Pull” este o parte a stării , adică 8 dintre componentele sale, definite ca $q$ $p$ $A$

q_{i}=a_{i+1}

pentru

0<i<8

Starea este actualizată conform următoarei reguli , care este o suprapunere a 4 transformări diferite: $\rho$

\rho ={\sigma }+\theta +\pi +\gamma

unde este o transformare liniară inversă, este, din nou, o transformare liniară inversă, este o combinație de rotație a biților de cuvânt și amestecare a poziției cuvântului, iar transformarea este o adăugare pe biți a memoriei tampon și a cuvântului de intrare. $\theta$ $\gamma$ $\pi$ $\sigma$

În acest caz, se va determina suma operațiilor, unde se efectuează prima cea din dreapta. $+$

Acum putem lua în considerare fiecare dintre aceste operațiuni. este definită după cum urmează: $\theta$

c=\theta (a)\Leftrightarrow c_{i}=a_{i}\oplus a_{i+1}\oplus a_{i+4)

pentru ,

i\in {0...17}

unde toți indicii sunt luați modulo . Rețineți că reversibilitatea acestei transformări rezultă din faptul că este coprim cu . $17$ $1\oplus x\oplus x^{4)$ $1\oplus x^{17}$

$\gamma$ poate fi definit ca:

c=\gamma (a)\Leftrightarrow c_{i}=a_{i}\oplus (a_{i+1}SAU\neg a_{i+2})

pentru ,

i\in {0...17}

unde toți indicii sunt luați modulo . $17$

Dacă pentru conversie se determină că există un offset în poziții de la bitul cel mai puțin semnificativ la cel mai semnificativ, atunci: $\pi$ $t_k$ $k$

c=\pi (a)\Leftrightarrow c_{i}=t_{k}(a_{j})

și , și $j=7i{}{\pmod {17}}$ $k=i(i+1)/2{\pmod {32)}$

Dacă pentru transformare se va efectua aceea , atunci $\sigma$ $c=\sigma (a)$

c_{0}=a_{0}\oplus 00000001_{hex)

c_{i+1}=a_{i+1}\oplus l_{i)

pentru ,

0\leqslant i<8

c_{i+9}=a_{i+9}\oplus b_{i}^{16)

pentru

0\leqslant i<8

În modul „Push” este mesajul de intrare , iar în modul „Pull” - . $l$ $p$ $l=b^{4}$

Cuvântul de ieșire în modul „Pull” este definit după cum urmează: $z$

z_{i}=a_{i+9}

0\leqslant i<8

. [unsprezece]

„Panama” ca funcție hash

„Panama” ca funcție hash mapează un rezultat hash de 256 de biți la un mesaj de lungime arbitrară. [11] În acest caz, hashingul are loc în 2 etape $M$

$M$ este convertit într-un șir cu o lungime care este un multiplu de 256 prin adăugarea celor. $M'$
Șirul corespunzător este încărcat în „Panama”. $M'$

Poate fi notat ca o succesiune de blocuri de intrare . Apoi, în momentul zero de timp, se generează modul Reset, apoi, în timpul ciclurilor, blocurile de intrare sunt încărcate. După aceea, sunt efectuate 32 de iterații „Pull” goale. Și apoi, la a 33-a iterație „Pull”, rezultatul hash este returnat . $M'$ $V$ $p$ $V$ $h$

Sarcina principală a dezvoltării funcției hash Panama a fost de a găsi o funcție hash „ermetică” [11] , adică o funcție pentru care (dacă rezultatul hash este format din biți): $n$

pentru problema de căutare a coliziunii, complexitatea așteptată este $2^{{n/2}}$
pentru problema calculului imaginii, complexitatea așteptată este $2^{n}$
pentru sarcina de a calcula a doua imagine, complexitatea așteptată este egală cu $2^{n}$

În plus, nu este posibil să se detecteze corelații sistematice între orice combinație liniară de biți de intrare și orice combinație liniară de biți de rezultat hash. [unsprezece]

Găsirea coliziunilor

Această funcție hash a fost atacată cu succes de două ori. Deja în 2001, s-a demonstrat că această funcție hash nu este sigură criptografic, deoarece au fost găsite coliziuni pentru operațiuni. Mai mult, Joan Dymen a arătat că este posibil să se găsească coliziuni deja pentru operații, iar pentru a satisface parametrii de fiabilitate, este necesar ca coliziunile să fie localizate cel puțin pentru operații. [12] $2^{82}$ $2^6$ $2^{128}$

Note

↑ Fast Hashing și Stream Encryption cu Panama de Joan Daemen, Craig Clapp
↑ NIST selectează câștigătorul competiției Secure Hash Algorithm (SHA-3) . Data accesului: 5 noiembrie 2016. Arhivat din original pe 5 octombrie 2012. (nedefinit)
↑ 1 2 J. Daemen, „Cipher and hash function design strategies based on linear and differental cryptanalysis”
↑ Hashing rapid și criptare în flux cu Panama” Joan Daemen, Craig Clapp
↑ Copie arhivată (link nu este disponibil) . Consultat la 16 decembrie 2016. Arhivat din original la 15 august 2011. (nedefinit)
↑ SHA1 versiunea 1.0 . Consultat la 16 decembrie 2016. Arhivat din original la 14 mai 2017. (nedefinit)
↑ 12 Panama . _ Consultat la 4 noiembrie 2016. Arhivat din original la 26 decembrie 2016. (nedefinit)
↑ Funcția criptografică Panama | Dr Dobb (link indisponibil) . Data accesului: 4 noiembrie 2016. Arhivat din original pe 23 februarie 2016. (nedefinit)
↑ * „Fast Hashing and Stream Encryption with Panama” de Joan Daemen, Craig Clapp
↑ Cod PANAMA | Blog de criptare . Consultat la 5 noiembrie 2016. Arhivat din original pe 5 noiembrie 2016. (nedefinit)
↑ 1 2 3 4 „Hashing rapid și criptare în flux cu Panama” Joan Daemen, Craig Clapp
↑ Producerea coliziunilor pentru Panama, instantaneu . Consultat la 13 noiembrie 2016. Arhivat din original la 10 octombrie 2019. (nedefinit)

Literatură

„Hashing rapid și criptare în flux cu Panama” Joan Daemen, Craig Clapp
A. Bosselaers, R. Govaerts, J. Vandewalle, „Fast Hashing on the Pentium”
J. Daemen, „Strategii de proiectare a funcției de criptare și hash bazate pe criptoanaliza liniară și diferențială”
CSK Clapp „Optimizarea unui cifru cu flux rapid pentru procesoarele VLIW, SIMD și superscalare”
Asoskov A. V., Ivanov M. A., Mirsky A. A., Ruzin A. V., Slanin A. V., Tyutvin A. N. „Cifuri de flux”.

Link -uri

Funcții hash
scop general	Adler-32 CRC Suma de control Fletcher FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash suma hash
Criptografic	Stribog GOST R 34.11-94 centura BLAKE BMW CubeHash ECOU edonkey2k FSB Fugă Grostl HAVAL Hamsi JH Kupyna LM hash Luffa MD2 MD4 MD5 MD6 N-hash RIPEMD-128 RIPEMD-160 RIPEMD-256 RIPEMD-320 SHA-1 SHA-2 Keccak (SHA-3) SHABAL SHAvite-3 SIMD SWIFFT Piele Snefru Tigru Vârtej
Funcții de generare a cheilor	bcrypt PBKDF2 cripta Argon2 Lyra2
Numărul de verificare ( comparație )	Verificați suma Algoritmul lui Verhouff Algoritmul lunii Algoritmul Damm Cod de bare conturi bancare carduri bancare ESTE IN SNILS OKPO STANIU OKATO ISBN OGRN și OGRNIP VIN
Hashes	Comparația numerelor de cec Protocoale de autentificare Comparația codurilor de bare Criptografie Legătură magnetică Semnătura Merkle ed2k URNĂ