Panama (hashfunktion)

Panama [1] är en kryptografisk primitiv som kan användas antingen som en kryptografisk hashfunktion eller som ett strömchiffer. Den utvecklades 1998 av Joan Dymen och Craig Klep för att förbättra effektiviteten i programvara för 32-bitars arkitekturer. Det är en av förfäderna till Keccak- hash-algoritmen , som blev vinnaren i tävlingen om kryptografiska primitiver från US National Institute of Standards and Technology [2] . Förlitar sig mycket på StepRightUp-strömningshashmodulen. [3]

Funktioner

Enligt utvecklarna hade "Panama" vid utvecklingstillfället en hög säkerhetsnivå, men detta uppnåddes till priset av en enorm beräkningsbelastning. Därför, som det visade sig, visade sig "Panama" som hashfunktion vara mindre lämplig för att hasha meddelanden än sina konkurrenter. Om vi talar om "Panama" som ett strömchiffer, visade sig en lång initialiseringsprocedur vara ett utmärkande drag för dess användning. Därför, när du använder det i uppgifter som kräver höga hastigheter, är det nödvändigt att tillhandahålla alla villkor som kommer att syfta till att minska antalet avsynkroniseringar. [fyra]

Det antogs att "Panama" skulle användas för att kryptera eller dekryptera video för att komma åt vissa applikationer, i synnerhet "betal-TV". [5] Utvecklarnas logik var att set-top-boxar och digitala TV-apparater skulle använda höghastighetsprocessorer, och Panama skulle inte ladda dessa processorer för mycket under dekryptering.

Struktur

"Panama" är baserad på en finita tillståndsmaskin, bestående av två stora block: 544 tillståndsbitar och en 8192-bitars buffert, som arbetar enligt principen om ett återkopplingsskiftregister . Återkopplingen säkerställer att ingångsbitarna går igenom flera iterationer efter inmatningen, vilket i sin tur säkerställer bitvis diffusion. Jag måste säga att en liknande buffert används i SHA-komprimeringsfunktionen. [6] Panama arbetsobjekt är ett 32-bitars ord och tillståndet består av 17 sådana ord, medan bufferten har 32 celler, som var och en innehåller 8 sådana ord. [7]

Operationer

Panama kan uppdatera bufferten och tillstånden genom att iterera. Och för den iterativa funktionen är tre lägen implementerade: "Återställ", "Push" och "Pull". I "Push"-läge tar maskinen emot viss input men matar inte ut någonting. I "Pull"-läget, tvärtom, bildas utdata, men ingenting tas som indata. En "tom pull-iteration" betyder också att utdata från den iterationen kasseras. I "Reset"-läget återställs tillståndet och bufferten till noll. [åtta]

Tillståndsförändringen kännetecknas av hög diffusion och distribuerad icke-linjäritet. [9] Detta betyder att ett litet antal iterationer är tillräckligt för att uppnå god spridning. Detta görs med hjälp av 4 block, som var och en löser sin egen uppgift.

Den första löser problemet med olinjäritet.
Den andra ger bitvis dispersion.
Den tredje skapar bitvis diffusion.
Den fjärde introducerar en buffert och indata. [tio]

Om vi betraktar "Panama" som en hashfunktion, är algoritmen för dess funktion som följer. Inledningsvis accepterar hashfunktionen alla block av meddelanden. Därefter utförs flera fler "Push" iterationer, vilket gör att de senast mottagna blocken av meddelanden kan spridas inuti bufferten och tillståndet. Därefter utförs den sista "Pull" iterationen, vilket gör att du kan få hashresultatet. Strömmande krypteringsschemat initieras enligt följande: först går två "Push" iterationer igenom för att erhålla nyckeln och diversifieringsparametern. Därefter sker ett antal "Pull"-iterationer för att sprida nyckeln och parametern inuti bufferten och tillstånden. Detta slutför initieringen och Panama är redo att skapa bitar av utdatasekvensen genom att utföra "Pull" iterationer. [3]

Hur det fungerar

Du kan beteckna tillståndet som , och de 17 orden som definierar tillstånd kan betecknas som . Bufferten betecknas som , den -th av dess cell - as , och ett av orden som ligger inuti denna cell - as . Inledningsvis är både tillståndet och bufferten fyllda med endast nollor. I "Push"-läget tar "Panama" emot ett 8-bitars ord som inmatning, i "Pull"-läget bildas ett 8-bitars ord som en utgång. [7] $A$ $a0...a16$ $B$ $j$ $b^{j}$ ${\displaystyle b_{i}^{j))$

Om vi anger funktionen som uppdaterar bufferten som , då, om vi accepterar det , kan vi få följande regler för uppdatering av bufferten: $\lambda$ $d=\lambda (b)$

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

vid ,

j\notin {0...25}

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

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

för

0<i<8

där det i "Push"-läget finns ett ingångsblock och i "Pull"-läget är det en del av tillståndet , dvs 8 av dess komponenter, definierade som $q$ $sid$ $A$

q_{i}=a_{i+1}

för

0<i<8

Tillståndet uppdateras enligt följande regel , som är en överlagring av 4 olika transformationer: $\rho$

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

där är en invers linjär transformation, är återigen en invers linjär transformation, är en kombination av ordbitrotation och ordpositionsblandning, och transformationen är en bitvis addition av bufferten och inmatningsordet. $\theta$ $\gamma$ $\pi$ $\sigma$

I det här fallet kommer det att bestämma summan av operationer, där den till höger utförs först. $+$

Nu kan vi överväga var och en av dessa operationer. definieras enligt följande: $\theta$

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

för ,

i\in {0...17}

där alla index tas modulo . Observera att reversibiliteten för denna transformation följer av det faktum att den är coprime med . $17$ ${\displaystyle 1\oplus x\oplus x^{4))$ $1\oplus x^{17}$

$\gamma$ kan definieras som:

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

för ,

i\in {0...17}

där alla index tas modulo . $17$

Om det för konverteringen fastställs att det finns en offset i positioner från den minst signifikanta biten till den mest signifikanta, då: $\pi$ $t_k$ $k$

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

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

Om för omvandlingen kommer att utföras som , då $\sigma$ $c=\sigma (a)$

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

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

för ,

0\leqslant i<8

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

för

0\leqslant i<8

I "Push"-läge är inmatningsmeddelandet och i "Pull"-läge - . $l$ $sid$ $l=b^{4}$

Utgångsordet i "Pull"-läge definieras enligt följande: $z$

z_{i}=a_{i+9}

0\leqslant i<8

. [elva]

"Panama" som en hashfunktion

"Panama" som en hashfunktion mappar ett hashresultat på 256 bitar till ett meddelande av godtycklig längd. [11] I det här fallet sker hashing i två steg $M$

$M$ konverteras till en sträng med en längd som är en multipel av 256 genom att lägga till ettor. $M'$
Motsvarande sträng laddas i "Panama". $M'$

Kan betecknas som en sekvens av ingångsblock . Sedan, vid tidpunkten noll, genereras återställningsläget, sedan, under cyklerna, laddas ingångsblocken. Därefter utförs 32 tomma "Pull" iterationer. Och sedan på den 33:e "Pull"-iterationen returneras hashresultatet . $M'$ $V$ $sid$ $V$ $h$

Huvuduppgiften med att utveckla Panama-hashfunktionen var att hitta en "hermetisk" hashfunktion [11] , det vill säga en funktion för vilken (om hashresultatet består av bitar): $n$

för kollisionssökningsproblemet är den förväntade komplexiteten $2^{{n/2}}$
för bildberäkningsproblemet är den förväntade komplexiteten $2^{n}$
för uppgiften att beräkna den andra bilden är den förväntade komplexiteten lika med $2^{n}$

Dessutom är det inte möjligt att detektera systematiska korrelationer mellan någon linjär kombination av inmatningsbitar och någon linjär kombination av hashresultatbitar. [elva]

Hitta kollisioner

Denna hash-funktion har framgångsrikt attackerats två gånger. Redan 2001 visades det att denna hashfunktion inte är kryptografiskt säker, eftersom kollisioner för operationer hittades. Dessutom visade Joan Dymen att det är möjligt att hitta kollisioner redan för operationer, och för att uppfylla tillförlitlighetsparametrarna är det nödvändigt att kollisioner lokaliseras åtminstone för operationer. [12] $2^{82}$ $2^6$ $2^{128}$

Anteckningar

↑ Snabb hashing och strömkryptering med Panama av Joan Daemen, Craig Clapp
↑ NIST utser vinnare av tävlingen Secure Hash Algorithm (SHA-3) . Tillträdesdatum: 5 november 2016. Arkiverad från originalet 5 oktober 2012. (obestämd)
↑ 1 2 J. Daemen, "Chiffer- och hashfunktionsdesignstrategier baserade på linjär och differentiell kryptoanalys"
↑ Snabb hashing och strömkryptering med Panama" Joan Daemen, Craig Clapp
↑ Arkiverad kopia (länk ej tillgänglig) . Hämtad 16 december 2016. Arkiverad från originalet 15 augusti 2011. (obestämd)
↑ SHA1 version 1.0 . Hämtad 16 december 2016. Arkiverad från originalet 14 maj 2017. (obestämd)
↑ 12 Panama . _ Hämtad 4 november 2016. Arkiverad från originalet 26 december 2016. (obestämd)
↑ Panamas kryptografiska funktion | Dr Dobbs (inte tillgänglig länk) . Datum för åtkomst: 4 november 2016. Arkiverad från originalet 23 februari 2016. (obestämd)
↑ * "Fast Hashing and Stream Encryption with Panama" av Joan Daemen, Craig Clapp
↑ PANAMA-kod | Krypteringsblogg . Hämtad 5 november 2016. Arkiverad från originalet 5 november 2016. (obestämd)
↑ 1 2 3 4 "Snabb hashing och strömkryptering med Panama" Joan Daemen, Craig Clapp
↑ Producerar kollisioner för Panama, omedelbart . Hämtad 13 november 2016. Arkiverad från originalet 10 oktober 2019. (obestämd)

Litteratur

"Snabb hashning och strömkryptering med Panama" Joan Daemen, Craig Clapp
A. Bosselaers, R. Govaerts, J. Vandewalle, "Fast Hashing on the Pentium"
J. Daemen, "Chiffer- och hashfunktionsdesignstrategier baserade på linjär och differentiell kryptoanalys"
CSK Clapp "Optimera ett snabbt strömningschiffer för VLIW-, SIMD- och superskalära processorer"
Asoskov A. V., Ivanov M. A., Mirsky A. A., Ruzin A. V., Slanin A. V., Tyutvin A. N. "Strömchiffer".

Länkar

Hash-funktioner
generell mening	Adler-32 CRC Fletcher kontrollsumma FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hashträd jenkins hash hash summa
Kryptografisk	Stribog GOST R 34,11-94 Bälte BLAKE bmw CubeHash EKO edonkey2k FSB Fuga Grostl HAVAL Hamsi J H 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 Hud Snefru Tiger Bubbelpool
Nyckelgenereringsfunktioner	bcrypt PBKDF2 kryptera Argon 2 Lyra2
Kontrollnummer ( jämförelse )	Kontrollera summan Verhouffs algoritm Månen algoritm Jävla algoritm Streckkod bankkonton bankkort ÄR I SNILS OKPO TENN OKATO ISBN OGRN och OGRNIP VIN
Hashes	Jämförelse av checknummer Autentiseringsprotokoll Streckkodsjämförelse Kryptografi Magnet länk Merkle signatur ed2k URNA