Fast Syndrome Based Hash

FSB (Fast Syndrome-Based Hash Function) är en uppsättning kryptografiska hashfunktioner skapade 2003 och lämnade in 2008 som kandidater till SHA-3-tävlingen [1] . Till skillnad från många hashfunktioner som för närvarande används, kan FSB:s kryptografiska styrka bevisas i viss utsträckning. Att bevisa styrkan hos FSB är att det är lika svårt att knäcka FSB som att lösa något NP-komplett problem känt som vanlig syndromavkodning. Även om det fortfarande inte är känt om NP-fullständiga problem är lösbara i polynomtid , antas det allmänt att de inte är det.

Under utvecklingsprocessen föreslogs flera versioner av FSB, varav den sista skickades in vid SHA-3-tävlingen, men avslogs i första omgången. Medan alla versioner av FSB hävdar att de är säkra , knäcktes vissa pre-releaseversioner så småningom [2] . Vid utvecklingen av den senaste versionen av FSB togs hänsyn till alla sårbarheter, och för tillfället förblir algoritmen kryptografiskt resistent mot alla för närvarande kända attacker.

Å andra sidan kommer motståndskraft med en kostnad. FSB är långsammare än traditionella hashfunktioner, och den använder ganska mycket RAM, vilket gör det opraktiskt i miljöer där det är begränsat. Dessutom kräver komprimeringsfunktionen som används i FSB en stor utdatameddelandestorlek för att garantera kryptografisk styrka. Det här problemet har lösts i de senaste versionerna där utdata komprimeras av Whirlpool- funktionen . Men även om författarna hävdar att tillägg av denna sista sammandragning inte minskar stabiliteten, gör det det omöjligt att formellt bevisa det [3] .

Beskrivning av hashfunktionen

Komprimeringsfunktionen har parametrar som och . Den här funktionen fungerar endast med meddelanden med längden .  - Utdatastorlek. Dessutom, och måste vara naturliga tal  - den binära logaritmen). Anledningen är att vi vill att det ska vara en komprimeringsfunktion, så ingången måste vara större än utgången. Senare använder vi Merkle-Damgard-konstruktionen för att utöka ingångsdomänen för meddelanden av godtycklig längd.

Grunden för denna funktion består av en (slumpmässigt vald) binär matris som interagerar med ett meddelande av bitar genom matrismultiplikation . Här kodar vi ett -bitmeddelande som en vektor i ett -dimensionellt vektorutrymme över ett fält av två element, så att utdata blir ett meddelande av bitar.

Av säkerhetsskäl, och även för att ha en snabb hashhastighet, används endast "vikt vanliga ord " som input till vår matris.

Definitioner

Ett meddelande kallas ett ord med vikt och längd om det består av bitar och det är från dessa bitar som inte är noll.

Ett ord med vikt och längd kallas regelbundet om varje intervall innehåller exakt ett element som inte är noll för alla . Det betyder att om vi delar upp meddelandet i w lika delar, så innehåller varje del exakt ett element som inte är noll.

Kompressionsfunktion

Det finns exakt olika vanliga ord i vikt och längd , så vi behöver exakt de bitar av data för att koda dessa vanliga ord. Fixa en en-till-en-överensstämmelse mellan uppsättningen av längdbitsträngar och uppsättningen av vanliga ord med vikt och längd , och definiera sedan FSB-komprimeringsfunktionen enligt följande:

1. Ingången är ett meddelande om storlek
2. Konvertera det till ett vanligt ord av vikt och längd
3. Matrismultiplikation
4. Vid utgången får vi en hash av storleken

Denna version kallas allmänt för syndromisk kompression. Detta går ganska långsamt och görs i praktiken på ett annat och snabbare sätt som kallas snabb syndromkompression. Vi delar upp i storlekssubmatriser och fixar en en-till-en-överensstämmelse mellan bitsträngar av längd och en uppsättning talsekvenser från 1 till . Detta motsvarar en en-till-en-överensstämmelse med en uppsättning vanliga ord av längd och vikt , eftersom man kan se det ordet som en sekvens av siffror från 1 till . Kompressionsfunktionen ser ut så här:

1. Ingången är ett meddelande om storlek
2. Konvertera det till en talföljd från 1 till
3. Lägga till lämpliga kolumner med matriser för att få en binär längdsträng
4. Vid utgången får vi en hash av storleken

Vi kan nu använda Merkle-Damgard-strukturen för att generalisera komprimeringsfunktionen så att indata kan vara av godtycklig längd.

Kompressionsexempel

Inledande villkor :

Vi hash meddelandet med hjälp av en matris som är indelad i submatriser , , .

Algoritm :

1. Vi delar upp det inkommande meddelandet i delar av längden och får , , .
2. Låt oss konvertera varje sträng till ett tal och få , , .
3. Från den första submatrisen tar vi den andra kolumnen, från den andra tar vi den första, från den tredje  - den fjärde.
4. Lägg till de valda kolumnerna och få resultatet: .

FSB säkerhetsbevis

Merkle-Damgard-strukturen baserar sin säkerhet endast på säkerheten för den använda komprimeringsfunktionen. Därför behöver vi bara visa att komprimeringsfunktionen är resistent mot kryptoanalys .

En kryptografisk hashfunktion måste vara säker på tre olika sätt:

1. Första förbildsresistans: Givet en hash h , borde det vara svårt att hitta ett meddelande m så att Hash( m )= h .
2. Det andra förbildsmotståndet är: givet ett meddelande m 1 borde det vara svårt att hitta ett meddelande m 2 så att Hash( m 1 ) = Hash( m 2 ).
3. Kollisionsbeständig: Det borde vara svårt att hitta två distinkta meddelanden m 1 och m 2 så att Hash( m 1 )=Hash( m 2 ).

Det är värt att notera att om du kan hitta den andra förbilden så kan du naturligtvis hitta en kollision . Det betyder att om vi kan bevisa att vårt system är kollisionsbeständigt kommer det säkert att vara säkert mot att hitta en andra förbild.

Vanligtvis i kryptografi betyder svårt något i stil med "nästan säkert utom räckhåll för alla motståndare vars systembrott måste förhindras", men låt oss definiera detta begrepp mer exakt. Vi kommer att anta: "exekveringstiden för varje algoritm som hittar en kollision eller förbild beror exponentiellt på storleken på hashvärdet." Detta gör att vi med relativt små tillägg till hashstorleken snabbt kan komma till en hög nivå av kryptografisk styrka.

Preimage motstånd

Som nämnts tidigare beror den kryptografiska styrkan hos FSB på en uppgift som kallas vanlig syndromavkodning. Ursprungligen ett problem inom kodningsteori , men dess NP-fullständighet har gjort det till en praktisk applikation för kryptografi. Det är ett specialfall av syndromavkodning och definieras enligt följande:

Givet matriser av dimension och en bit längdsträng så att det finns en uppsättning kolumner, en för varje , som utgör . Vi måste hitta en sådan uppsättning kolumner.

Detta problem har visat sig vara NP-komplett genom att undvika 3D-matchning. Återigen, även om det inte är känt om det finns polynomalgoritmer för att lösa tids-NP-fullständiga problem, är ingen av dem kända och att hitta en skulle vara en enorm upptäckt.

Det är lätt att se att att hitta förbilden för en given hash exakt motsvarar detta problem, så FSB-förbildsproblemet måste också vara NP-komplett.

Vi behöver fortfarande bevisa kollisionsmotstånd. För att göra detta behöver vi en annan NP-komplett variant av vanlig syndromkodning, kallad "biregular zero syndromic decoding".

Kollisionsmotstånd

Dimensionsmatriser och en bitsträng av längd anges . Sedan finns det en uppsättning kolumner, antingen två eller ingen i varje , som utgör 0, där . Vi måste hitta en sådan uppsättning kolumner. Denna metod har visat sig vara NP-komplett genom att undvika 3D-matchning.

Precis som vanlig syndromavkodning i huvudsak är likvärdig med att hitta ett vanligt ord så att , är biregular noll syndromisk avkodning likvärdigt med att hitta ett biregulärt ord så att . Ett tvåregelbundet ord av längd och vikt är en bitsträng av längd så att i varje intervall antingen exakt två poster är 1 eller ingen. Observera att ett 2-regelbundet ord helt enkelt är summan av två vanliga ord.

Antag att vi har hittat en kollision: Hash( m 1 ) = Hash( m 2 ) för . Då kan vi hitta två vanliga ord och så där . Vi får då , där är summan av två olika reguljära ord och det måste vara ett bireguljärt ord vars hash är noll, så vi har löst problemet med bi-reguljärt nollsyndrom. Vi drog slutsatsen att det är minst lika svårt att hitta kollisioner i FSB som att lösa avkodningsproblemet med biregulärt nollsyndrom, och därför är algoritmen NP-komplett.

De senaste versionerna av FSB har använt Whirlpool-komprimeringsfunktionen för att ytterligare komprimera utmatningen av hashfunktionen. Även om den kryptografiska styrkan i detta fall inte kan bevisas, hävdar författarna att denna sista komprimering inte minskar den. Observera att även om det skulle vara möjligt att hitta kollisioner i Whirpool, skulle det fortfarande vara nödvändigt att hitta förbildskollisioner i den ursprungliga FSB-komprimeringsfunktionen för att hitta kollisioner i FSB.

Exempel

När vi löser problemet med vanlig syndromavkodning är vi så att säga i motsatt riktning, med avseende på hash. Med samma värden som i föregående exempel får vi ett underblock och en sträng . Vi måste hitta en kolumn i varje underblock, så de blir . Så det förväntade svaret skulle vara , . Detta är notoriskt svårt att beräkna för stora matriser. Vid biregular zero syndrome-avkodning vill vi i varje subblock inte hitta en kolumn, utan antingen två eller ingen så att de leder till (och inte till ). I exemplet skulle vi kunna använda den andra och tredje kolumnen (räknat från 0) av , ingen av kolumnerna av , noll och den andra av . Fler lösningar är möjliga, till exempel utan att använda någon av kolumnerna från .

Linjär kryptoanalys

FSB:s bevisbara säkerhet gör att hitta kollisioner är NP-komplett. Men beviset är en reducering till ett mer komplext problem. Men detta ger bara begränsade säkerhetsgarantier, eftersom det fortfarande kan finnas en algoritm som enkelt löser problemet för en delmängd av det givna utrymmet. Till exempel finns det en linjäriseringsmetod som kan användas för att få kollisioner på några sekunder på en stationär PC för tidiga versioner av FSB med en påstådd säkerhetsklassning på 2128 . Det visas att när meddelandeutrymmet väljs på ett visst sätt ger hash-funktionen minimalt med förbild eller kollisionsmotstånd.

Säkerhetsresultat i praktiken

Tabellen visar komplexiteten i de mest kända attackerna mot FSB:

Andra egenskaper

• Ingångs- och utmatningsblockstorleken för hashfunktionen är fullt skalbar.
• Hastigheten kan justeras genom att ändra antalet bitoperationer som används av FSB per ingångsbit.
• Säkerheten kan justeras genom att justera utmatningsstorleken.
• Dåliga fall finns, och försiktighet måste iakttas när du väljer matris .
• Matrisen som används i krympfunktionen kan bli enorm i vissa fall.

Alternativ

Det senare kan vara problematiskt när man använder FSB på enheter med relativt litet minne.

Detta problem löstes 2007, i en relaterad hashfunktion som kallas IFSB (Improved Fast Syndrome Based Hash) [4] , som fortfarande bevisligen är säker, men förlitar sig på något starkare antaganden.

2010 introducerades S-FSB som har en hastighet 30 % snabbare än FSB [5] .

2011 introducerade Daniel Julius Bernstein och Tanya Lange RFSB, som var 10 gånger snabbare än FSB-256 [6] . RFSB, när den kördes på en Spartan 6 FPGA-maskin, uppnådde en genomströmning på upp till 5 Gbps [7] .

Anteckningar

1. ↑ Augot, D.; Finiasz, M.; Sendrier, N. En snabb bevisbart säker kryptografisk hashfunktion (2003). Tillträdesdatum: 10 december 2015. Arkiverad från originalet 3 mars 2016. (obestämd)
2. ↑ Saarinen, Markku-Juhani O. Lineariseringsattacker mot syndrombaserade hash (2007). Hämtad 10 december 2015. Arkiverad från originalet 4 mars 2016. (obestämd)
3. ↑ Finiasz, M.; Gaborit, P.; Sendrier, N. Improved Fast Syndrome Based Cryptographic Hash Functions (otillgänglig länk) (2007). Tillträdesdatum: 10 december 2015. Arkiverad från originalet 3 mars 2016. (obestämd) 
4. ↑ Finiasz, M.; Gaborit, P.; Sendrier, N. Improved Fast Syndrome Based Cryptographic Hash Functions (2007). Tillträdesdatum: 12 december 2015. Arkiverad från originalet 22 december 2015. (obestämd)
5. ↑ Meziani M.; Dagdelen O.; CayrelPL; El Yousfi Alaoui SM S-FSB: En förbättrad variant av FSB Hash Family (inte tillgänglig länk) (2010). Tillträdesdatum: 12 december 2015. Arkiverad från originalet 22 december 2015. (obestämd) 
6. ↑ Bernstein, DJ, Lange, T.; Peters C.; Schwabe P.;. Riktigt snabb syndrombaserad hashing (2011). Hämtad 12 december 2015. Arkiverad från originalet 14 december 2014. (obestämd)
7. ↑ Von Maurich, I.; Guneysu, T.;. Inbäddad syndrombaserad hashing (inte tillgänglig länk) (2011). Tillträdesdatum: 12 december 2015. Arkiverad från originalet 2 maj 2015. (obestämd)