CubeHash

CubeHash [1]  är en parametrerbar familj av CubeHash r/b kryptografiska hashfunktioner . CubeHash8/1 föreslogs av Daniel Bernstein som en ny standard för SHA-3 i hashtävlingen National Institute of Standards and Technology (NIST ) . Inledningsvis krävde NIST cirka 200 cykler per byte [2] . Efter några förtydliganden från NIST ändrade författaren parametrarna till CubeHash16/32, vilket är cirka 16 gånger snabbare än CubeHash8/1 och kommer lätt ikapp SHA-256 och SHA-512 på olika plattformar [3] [4] [5] [6] .

CubeHash tog sig till den andra omgången av tävlingen, men tog sig inte till de fem bästa finalisterna [7] [8] .

Beskrivning av algoritmen

Arbetet med CubeHash r/bh bygger på tre parametrar: r , b och h .

Algoritmen har 5 huvudsteg:

Initialisering. 128-byte-tillståndet ses som en sekvens av 32 fyra-byte-ord x 00000 , x 00001 , x 00010 ,…, x 11111 , vart och ett representerat i little-endian form som 32-bitars heltal. De tre första orden x 00000 , x 00001 , x 00010 är inställda på h /8, b , r respektive. De återstående orden är noll. Sedan omvandlas tillståndet genom 10 r identiska omgångar.

Fyllning. 1 bit läggs till det inkommande meddelandet, sedan fylls det med minsta möjliga antal nollbitar så att antalet bitar är en multipel av 8 b .

Utfyllnad kräver inte att lagringen av meddelandelängden, bearbetningsblocket och resten separeras. En implementering kan lagra ett enda nummer mellan 0 och 8 b för att registrera antalet bitar som hittills bearbetats i det aktuella blocket.

Komplettering. 1 adderas modulo två till det sista tillståndet av ordet x 11111. Vidare transformeras tillståndet genom att hålla 10 r identiska omgångar.

Varje omgång innehåller 10 steg:

Funktioner i algoritmen

CubeHash-algoritmen inkluderar inte räknarblock, block som använder slumptal och liknande block. Utan dessa block är det lättare att hitta tillståndet där kollisionen inträffar , men det här argumentet fungerar inte när tillståndets storlek är ganska stor. En typisk attack på CubeHash skulle ta 2^400 försök att hitta en 1024-bitars tillståndskollision för CubeHash. Det finns heller ingen anledning att bryta någon symmetri som används i omgångar .

Initieringstillståndet för CubeHash är inte symmetriskt, om parametern b inte är särskilt stor, har angriparen inte tillräckligt med datorkraft för att beräkna ett symmetriskt tillstånd eller ett par tillstånd.

De huvudsakliga operationerna som används i CubeHash är:

Dessa operationer tar konstant tid på typiska processorer. De flesta implementeringar kommer att undvika läckor från olika mjukvarulager. Till exempel är det möjligt för de flesta programvaruimplementeringar som använder AES att läcka nycklar genom cachen . Detta faktum tvingade Intel att lägga till en tidskonstant relaterad till AES.

Arbetshastighet

På SHA - 3 -tävlingen testade NIST de föreslagna funktionerna, en av dem var CubeHash med parametrarna 16/32. Testning utfördes på två Intel Core 2 Duo 6f6 (katana) och Intel Core 2 Duo E8400 1067a (brick)-processorer:

• 11,47 cykler/byte: CubeHash16/32, brick, AMD64-arkitektur.

• 12,60 cykler/byte: SHA-512, brick, AMD64-arkitektur.

• 12,60 cykler/byte: SHA-512, katana, AMD64-arkitektur.

• 12,66 cykler/byte: CubeHash16/32, katana, AMD64-arkitektur.

• 12,74 cykler/byte: CubeHash16/32, brick, x86-arkitektur.

• 14,07 cykler/byte: CubeHash16/32, katana, x86-arkitektur.

• 15,43 cykler/byte: SHA-256, brick, x86-arkitektur.

• 15,53 cykler/byte: SHA-256, brick, amd64-arkitektur.

• 15,56 cykler/byte: SHA-256, katana, AMD64-arkitektur.

• 17,76 cykler/byte: SHA-512, brick, x86-arkitektur.

• 20.00 cykler/byte: SHA-512, katana, x86-arkitektur.

• 22,76 cykler/byte: SHA-256, katana, x86-arkitektur.

CubeHash är inte sämre i hastighet än sina motståndare.

Exempel på hash

Det här exemplet använder CubeHash 8/1-512.

Initieringsvektorn är densamma för alla 8/1-512-hashar och ser ut så här:

6998f35dfb0930c760948910e626160f36077cf3b58b0d0c57cf193d3341e7b8\ a334805b2089f9ef31ffc4142aef3850fe121839e940a4527d5293a27045ca12\ 9358096e81bf70349a90a44a93c33edb14c3e9844a87dbd0bc451df25212b3ac\ 6aabe51c5df0f63bddbb8ae8fad3cf0fd52582fbad2e2446094025a521a23d5c

Att hasha ASCII- meddelandet "Hej" (hex: 0x48, 0x65, 0x6c, 0x6c, 0x6f) använder 6 block. De första 5 blocken kommer (eftersom i detta fall varje bokstav är en byte) från meddelandet och ytterligare ett block att fylla.

Värdet på 512-bitars hash är:

7ce309a25e2e1603ca0fc369267b4d43f0b1b744ac45d6213ca08e7567566444\ 8e2f62fdbf7bbd637ce40fc293286d75b9d09e8dda31bd029113e02eccfd39b

En liten förändring i meddelandet (till exempel en förändring på en bit) leder till en betydande förändring av hashen (den så kallade lavineffekten ).

Låt oss till exempel ta meddelandet "hej", som skiljer sig från "Hej" med bara en bit. Hashen i detta meddelande är:

01ee7f4eb0e0ebfdb8bf77460f64993faf13afce01b55b0d3d2a63690d25010f\ 7127109455a7c143ef12254183e762b15575e0fcc49c79a0471a970ba8a66638

Ändra inställningar

CubeHash r/bh accepterar många olika parametrar som används för att bestämma hashen. Detta ger flexibilitet till algoritmen i förhållande till slutanvändaren, som själv bestämmer de bästa parametrarna för användning. Nedan finns några exempel på hash för olika meddelanden som använder olika algoritmparametrar. Alla meddelanden är skrivna i ASCII. De tre parametrarna som används i hashgenerering är i r/bh- format.

Meddelande: "" (tom sträng, noll-längd sträng) CubeHash 16/32-512: 4a1d00bbcfcb5a9562fb981e7f7db3350fe2658639d948b9d57452c22328bb32\ f468b072208450bad5ee178271408be0b16e5633ac8a1e3cf9864cfbfc8e043a CubeHash 8/1-512: 90bc3f2948f7374065a811f1e47a208a53b1a2f3be1c0072759ed49c9c6c7f28\ f26eb30d5b0658c563077d599da23f97df0c2c0ac6cce734ffe87b2e76ff7294 CubeHash 1/1-512: 3f917707df9acd9b94244681b3812880e267d204f1fdf795d398799b584fa8f1\ f4a0b2dbd52fd1c4b6c5e020dc7a96192397dd1bce9b6d16484049f85bb71f2f CubeHash 16/32-256: 44c6de3ac6c73c391bf0906cb7482600ec06b216c7c54a2a8688a6a42676577d CubeHash 8/1-256: 38d1e8a22d7baac6fd5262d83de89cacf784a02caa866335299987722aeabc59 CubeHash 1/1-256: 80f72e07d04ddadb44a78823e0af2ea9f72ef3bf366fd773aa1fa33fc030e5cb Meddelande: "Hej" CubeHash 16/32-512: dcc0503aae279a3c8c95fa1181d37c418783204e2e3048a081392fd61bace883\ a1f7c4c96b16b4060c42104f1ce45a622f1a9abaeb994beb107fed53a78f588c CubeHash 8/1-512: 7ce309a25e2e1603ca0fc369267b4d43f0b1b744ac45d6213ca08e7567566444\ 8e2f62fdbf7bbd637ce40fc293286d75b9d09e8dda31bd029113e02eccfd39b CubeHash 1/1-512: 13cf99c1a71e40b135f5535bee02e151eb4897e4de410b9cb6d7179c677074eb\ 6ef1ae9a9e685ef2d2807509541f484d39559525179d53838eda95eb3f6a401d CubeHash 16/32-256: e712139e3b892f2f5fe52d0f30d78a0cb16b51b217da0e4acb103dd0856f2db0 CubeHash 8/1-256: 692638db57760867326f851bd2376533f37b640bd47a0ddc607a9456b692f70f CubeHash 1/1-256: f63041a946aa98bd47f3175e6009dcb2ccf597b2718617ba46d56f27ffe35d49

Säkerhet

Styrkan hos denna algoritm ökar både när b minskar till 1 och när r ökar .
Därför är CubeHash 8/1-512 mer stabil (säkrare) än CubeHash 1/1-512, och CubeHash 1/1-512 är mer stabil än CubeHash 1/2-512. Den svagaste möjliga versionen av denna algoritm är CubeHash 1/128- h . Säkerheten är dock tidsberoende. Det säkrare alternativet tar längre tid att beräkna hashvärdet.

Möjliga attacker

Attacker som använder strukturen för en hashfunktion är vanligtvis de mest framgångsrika av alla möjliga typer av attacker. Sådana attacker kan hitta kollisioner, förbilder och andra förbilder. Det utmärkande för sådana attacker är dock att de nästan alltid är designade för en specifik hashfunktion, eftersom sådana attacker använder en specifik implementering av tillståndsberäkningen [9] .

Single Block Attack

Eftersom beräkningsomgången i CubeHash är reversibel, kan initialtillståndet beräknas genom att utföra de omvända operationerna på sluttillståndet. Single block attack baseras på denna omständighet.

Låt oss överväga algoritmen för denna attack.

Givet en hash H för något meddelande, beräknas b - byten för den andra förbilden av meddelandet med hjälp av CubeHashr/bh .

  1. Ställ in de första h/8 byten av det slutliga tillståndet med hjälp av hash H , och de återstående 128-h/8 byten med hjälp av försöksvärdet T , vi får tillstånd 6. Metoden för val av försöksvärde kommer att beskrivas senare.
  2. Genom att applicera 10r omvända rundor på tillstånd 6 får vi tillstånd 5. Funktionens omvända omgångar kan erhållas genom att göra stegen i algoritmen i omvänd ordning, det vill säga att ersätta cirkulära förskjutningar till vänster med cirkulära förskjutningar till höger och ersätter addition med subtraktion modulo 2 32 .
  3. Tillämpa den exklusiva eller operationen på 1 och det sista ordet i tillstånd 5, och erhåll på så sätt tillstånd 4
  4. Efter att ha gjort omvända omgångar med tillstånd 4, får vi tillstånd 3.
  5. Vi tillämpar den exklusiva eller operationen på meddelandet 0x80 och den första statusbyte 4, vilket resulterar i status 3.
  6. Efter att ha gjort omvända omgångar med tillstånd 2 får vi tillstånd 1.
  7. Om de sista 128-b- bytena av tillstånd 1 inte matchar 128-b- bytena för initieringsvektorn (tillstånd 0), valdes sondmeddelandet misslyckat.
  8. Annars har testmeddelandet valts. Den andra förbilden beräknas med användning av exklusiva eller över de första b byten av tillstånd 1 och de första b byten av tillståndet för initialiseringsvektorn.

Genom att upprepa proceduren ovan med olika värden på T kommer en andra förbild så småningom att genereras. Metoden för att välja värdet på T är inte kritisk. Till exempel kan en sekvens av på varandra följande nummer användas.

Om vi ​​antar att CubeHash (framåt eller bakåt) beter sig som en slumpmässig mappning för ett godtyckligt testvärde T, så är sannolikheten att de sista 128-b byten av tillstånd 1 kommer att vara lika med motsvarande byte för initialiseringsvektorn 2 −8( 128-b) . Antalet probmeddelanden före framgång är således 28 (128-b) . Om 2 8(128-b) < 2 timmar så kommer en enda blockattack att hitta den andra förbilden på färre försök än brute force. Med andra ord, en enstaka blockattack är mer effektiv än brute force för följande värden h = 224 och b > 100 , för h = 256 och b > 96 , för h=384 och b> 80 , för h=512 och b > 64 .

Det förväntade antalet försök som krävs för att lyckas beror dock inte på antalet omgångar r. Tiden som behövs för att utföra en attack ökar linjärt med r, och inte som en exponentiell funktion. För b = 128 kommer vilket värde som helst på T omedelbart att vara den andra förbilden.

Överväg en algoritm för att förbättra attacken för att hitta den första förbilden.

  1. Baserat på värdena ( h , b , r ) beräknar vi initialiseringsvektorn (tillstånd 0).
  2. För h bitar och 1024-h , utför 10r omvända rundor och XOR för att få tillståndet f .
  3. Hitta två n blocksekvenser som mappar tillstånd 0 och tillstånd f till två tillstånd som har samma senaste 1024-h bitar.

Det finns 2 nb möjliga ingång n block och ett av dem kommer att kollidera. Antalet försök som krävs för att hitta en kollision uppskattas till

2 * (521 / b - 4) * 2 512 - 4b = 2 * 522 - 4b - logb

Dessutom tar vi hänsyn till att varje omgång kräver 2 11 -bitarsoperationer, då ändras formeln till 2 533-4b-logb+logr- bitarsoperationer. Accelerationen av denna attack kan uppnås på grund av det faktum att vi kommer att söka efter en kollision inte bara efter beräkningen av det n:e blocket, utan också i varje annat tillstånd som vi har nått (vi kommer också att använda mellantillstånd). Därmed kommer vi att bli av med faktorn (512/b-4) . Sedan kommer antalet försök som krävs för att hitta en kollision att uppskattas till 2513-4b bitars operationer. Betrakta CubeHash-512 med parametrarna h, b, r lika med 512, 1, 8 respektive. För den förbättrade algoritmen är antalet försök som krävs för att hitta en kollision 2523 jämfört med standardattackalgoritmen med 2532 försök att hitta en kollision . Om r = 8 behöver den förbättrade algoritmen b > 3 för att antalet försök ska vara mindre än 2512 måste den normala algoritmen uppfylla b > 5 .

Symmetriattack

Som nämnts ovan är CubeHash-algoritmen mycket symmetrisk och använder inga konstanter. Därför finns det många symmetriklasser med avseende på permutationer. Den mest effektiva attacken är att använda en symmetriklass för vilken ett meddelandetillägg kan generera symmetriska meddelanden. Vi kan till exempel använda en symmetriklass som heter C2. För denna klass kallas ett tillstånd symmetriskt om x ijkl0 =x ijkl1 för valfri i, j, k, l.

När parameter b är 32, dvs. CubeHash är normal, ger meddelandeinjektion kontroll över x 00klm för valfri k, l, m.

Därför, för att uppnå ett symmetriskt tillstånd, behöver man helt enkelt nå ett tillstånd som uppfyller följande 384-bitars ekvation

x 01kl0 = x 01kl1

x 10kl0 = x 10kl1

x 11kl0 = x 11kl1

för varje k, l.

Och då kan meddelandeinjektion användas för att uppnå ett helt symmetriskt tillstånd. Den förväntade komplexiteten är 2 384 .

Detta kan användas för en preimage-attack. Algoritmen kan skrivas enligt följande

  1. Hitta ett meddelande A som är symmetriskt med initialiseringsvektorn
  2. Hitta ett meddelande D som är omvänt symmetriskt med det givna.
  3. Generera 2 192 symmetriska meddelanden B j . Beräkna sedan tillståndet som erhålls efter att ha utfört operationen eller på A och B j
  4. Generera 2 192 symmetriska meddelanden С j . Beräkna sedan tillståndet som är resultatet av utförandet av operationen eller över utförandet av Cj och D.
  5. Med hög sannolikhet finns det ett par värden som uppfyller

b 01kl0 =c 01kl0

b 10kl0 =c 10kl0

b 11kl0 =c 11kl0

sedan följer följande likheter av symmetrin

b 01kl1 =c 01kl1

b 10kl1 =c 10kl1

b 11kl1 =c 11kl1

som håller för något k, l.

Vi använder sedan X-blocket för att matcha de första 256 bitarna. Detta ger en förbild - vi utför en operation eller på A, B i 0 , X, C i 0 , D.

Komplexiteten för steg 1 och 2 är 2384 och komplexiteten för steg 3 och 4 är 2192 . Det kan implementeras utan stora minneskostnader. Denna attack har samma komplexitet som den maktbaserade attacken när B är en potens av två, men den blir mer effektiv när b inte är en potens av två.

Den mest tidskrävande delen av en symmetribaserad attack är den beräkning som krävs för att beräkna symmetritillståndet. Det visar sig dock att detta problem enkelt löses med Grovers algoritm på en kvantdator. Faktum är att att hitta ett tillstånd som uppfyller ekvationen som beskrivs ovan är likvärdigt med att hitta en förbild på noll för en hashfunktion som kommer att iterera över varven för CubeHash-funktionen, och vars utdata kommer att representeras av

x 01000 x 01001

x 01010 x 01011

x 01100 x 01101

x 01110 x 01111

x 10 000 x 10 001

x 10010 x 10011

x 10100 x 10101

x 10110 x 10111

x 11  000 x 11 001

x 11010 x 11011

x 11100 x 11101

x 11110 x 11111

För en 384-bitars funktion har Grovers algoritm en komplexitet på 2 192 operationer. Då skulle en symmetriattack kräva 2 192 operationer, förutsatt att kvantdatorer är tillgängliga.

Anteckningar

  1. ↑ Daniel J. Bernstein. CubeHash-specifikation . Hämtad 25 januari 2013. Arkiverad från originalet 14 augusti 2011.
  2. ↑ Daniel J. Bernstein. CubeHash effektivitetsuppskattningar . Datum för åtkomst: 26 januari 2013. Arkiverad från originalet den 14 augusti 2011.
  3. ↑ Daniel J. Bernstein. CubeHash-parameterjustering: 16 gånger snabbare . Hämtad 25 januari 2013. Arkiverad från originalet 14 augusti 2011.
  4. ↑ Alan Kaminsky, Benjamin Bloom Single block attacker och statistiska tester på CubeHash . Hämtad 30 november 2014. Arkiverad från originalet 5 december 2014.
  5. ↑ Jean-Philippe Aumasson, Eric Brier, Willi Meier, Marıa Naya-Plasencia, Thomas Peyrin Inside the Hypercube Arkiverad 4 december 2014.
  6. ↑ Gaëtan Leurent Quantum Preimage och kollisionsattacker på CubeHash . Hämtad 30 november 2014. Arkiverad från originalet 4 mars 2016.
  7. ↑ Statusrapport om den andra omgången av SHA-3 Cryptographic Hash Algorithm Competition Arkiverad 14 mars 2011 på Wayback Machine (PDF). Hämtad 2 mars 2011
  8. ↑ Omfattande jämförelse av hårdvaruprestanda för fjorton omgång 2 SHA-3-kandidater med 512-bitars utdata (länk ej tillgänglig) . Hämtad 11 maj 2018. Arkiverad från originalet 11 maj 2018. 
  9. ↑ Kryptoanalys av CubeHash . Hämtad 11 maj 2018. Arkiverad från originalet 11 maj 2018.

Litteratur

Länkar

 Hash-funktioner
generell mening
Kryptografisk
Nyckelgenereringsfunktioner
Kontrollnummer ( jämförelse )
Hashes