SipHash - SipHash

SipHash er en add-rotate-xor (ARX) basert familie av pseudorandom-funksjoner opprettet av Jean-Philippe Aumasson og Daniel J. Bernstein i 2012, som svar på en strøm av "hash-flom" denial-of-service-angrep i slutten av 2011.

Selv om den er designet for bruk som en hashfunksjon for å sikre sikkerhet, er SipHash vesentlig forskjellig fra kryptografiske hashfunksjoner som SHA ved at den bare er egnet som en meldingstegn -kode : en nøkkelbasert hash -funksjon som HMAC . Det vil si at SHA er designet slik at det er vanskelig for en angriper å finne to meldinger X og Y slik at SHA ( X ) = SHA ( Y ), selv om hvem som helst kan beregne SHA ( X ). SipHash garanterer i stedet at etter å ha sett X i og SipHash ( X i , k ), kan en angriper som ikke kjenner nøkkelen k ikke finne (informasjon om) k eller SipHash ( Y , k ) for noen melding Y ∉ { X i } som de ikke har sett før.

Oversikt

SipHash beregner en 64-biters meldingsautentiseringskode fra en melding med variabel lengde og 128-biters hemmelig nøkkel. Den ble designet for å være effektiv selv for korte innganger, med ytelse som kan sammenlignes med ikke-kryptografiske hashfunksjoner, for eksempel CityHash , dette kan brukes til å forhindre denial-of-service-angrep mot hashtabeller ("hashflom"), eller for å autentisere nettverkspakker . En variant ble senere lagt til som gir et 128-bits resultat.

En hash-funksjon uten nøkkel som SHA er kun kollisjonsbestandig hvis hele utgangen brukes. Hvis den brukes til å generere en liten utgang, for eksempel en indeks i en hash -tabell av praktisk størrelse, kan ingen algoritme forhindre kollisjoner; en angriper trenger bare gjøre så mange forsøk som det er mulige utdata.

Anta for eksempel at en nettverksserver er designet for å kunne håndtere opptil en million forespørsler samtidig. Den holder styr på innkommende forespørsler i en hashtabell med to millioner oppføringer, ved hjelp av en hashfunksjon for å kartlegge identifiserende informasjon fra hver forespørsel til en av de to millioner mulige tabelloppføringene. En angriper som kjenner hashfunksjonen trenger bare mate den vilkårlige innganger; en av to millioner vil ha en bestemt hash -verdi. Hvis angriperen nå sender noen hundre forespørsler som alle er valgt om å ha samme hash -verdi til serveren, vil det gi et stort antall hashkollisjoner, noe som reduserer (eller muligens stopper) serveren med en effekt som ligner på en pakkeflom på mange millioner forespørsler.

Ved å bruke en nøkkel som er ukjent for angriperen, forhindrer en nøkkelbasert hashfunksjon som SipHash denne typen angrep. Selv om det er mulig å legge til en nøkkel til en hash -funksjon uten nøkkel ( HMAC er en populær teknikk), er SipHash mye mer effektiv.

Funksjoner i SipHash -familien er spesifisert som SipHash- c - d , hvor c er antall runder per meldingsblokk og d er antall avsluttende runder. De anbefalte parameterne er SipHash-2-4 for best ytelse, og SipHash-4-8 for konservativ sikkerhet. Noen få språk bruker Siphash-1-3 for ytelse med fare for ennå ukjente DoS-angrep.

Den referansen implementeringen ble utgitt som public domain programvare under CC0 .

Bruk

SipHash brukes i hash table implementeringer av diverse programvare:

Følgende programmer bruker SipHash på andre måter:

  • Bitcoin for korte transaksjons -ID -er
  • Bloomberg BDE som en C ++ - objektherrer
  • IPFS for sine syv Bloom filter hashes

Implementeringer

Se også

Referanser

Eksterne linker