Svamp funktion - Sponge function

Svampekonstruktionen til hashfunktioner. P _jeg er blokke af inputstrengen, Z _jeg er punkterede udgangsblokke.

I kryptografi , en svamp funktion eller svamp konstruktion er helst af en klasse af algoritmer med definerbar indre tilstand , der tager et input bitstrøm af enhver længde og producere et output bitstrøm af enhver ønsket længde. Svampfunktioner har både teoretisk og praktisk anvendelse. De kan bruges til at modellere eller implementere mange kryptografiske primitiver , inklusive kryptografiske hashser , meddelelsesgodkendelseskoder , maskegenereringsfunktioner , streamciffer , pseudo-tilfældige talgeneratorer og godkendt kryptering .

Konstruktion

En svampfunktion er bygget af tre komponenter:

• en tilstand hukommelse, S , indeholdende b bits,
• en funktion, der transformerer tilstandshukommelsen (ofte er det en pseudorandom- permutation af tilstandsværdierne)${\ displaystyle f: \ {0,1 \} ^ {b} \ højre højre \ {0,1 \} ^ {b}}$${\ displaystyle 2 ^ {b}}$
• en polstring funktion P

Tilstandshukommelsen er opdelt i to sektioner: en af ​​størrelse r (bitrate) og den resterende del af størrelse c (kapaciteten). Disse afsnit er betegnet R og C hhv.

Polstringsfunktionen tilføjer nok bit til inputstrengen, så længden af ​​den polstrede input er en hel multipel af bitrate, r . Det polstrede input kan således opdeles i r- bit-blokke.

Operation

Svampfunktionen fungerer som følger:

• Tilstanden S initialiseres til nul
• Inputstrengen er polstret. Dette betyder input transformeres i blokke af r bit under anvendelse polstring funktionen P .
• for hver r- bit-blok B i det polstrede input:
  • R erstattes med R XOR B (ved hjælp af bitvis XOR )
  • S erstattes af f ( S )

Denne proces "absorberer" (i svamp metafor) alle blokke af polstrede streng input.

Svampefunktionsudgangen er nu klar til at blive produceret ("presset ud") som følger:

• den R del af staten hukommelse udlæses
• gentag, indtil der udsendes nok bits:
  • S erstattes af f ( S )
  • den R del af staten hukommelse udlæses

Hvis der ikke skal udskrives mindre end r bit, udskæres R (kun en del af R udsendes).

En anden metafor beskriver tilstandshukommelsen som en " entropipool ", med input "hældt i" puljen, og transformationsfunktionen benævnt "omrøring af entropipuljen".

Bemærk, at indgangsbits aldrig XOR-ledes i C- delen af ​​tilstandshukommelsen, og at der aldrig udsendes nogen bits af C direkte. I hvilket omfang C ændres af input afhænger helt af transformationsfunktionen f. I hash-applikationer afhænger modstand mod kollision eller præimage-angreb af C , og dens størrelse ("kapaciteten" c ) er typisk det dobbelte af det ønskede modstandsniveau.

Duplex konstruktion

Det er også muligt at absorbere og klemme skiftevis. Denne operation kaldes duplekskonstruktion eller dupleksudvikling. Det kan være grundlaget for et enkelt pass-godkendt krypteringssystem.

• Tilstanden S initialiseres til nul
• R er XORed med den første r- bit-blok af input
• S erstattes af f ( S )
• R er nu de første r bit af output.
• R er XORed med den næste r- bit blok af input
• S erstattes af f ( S )
• R er nu de næste r bit af output.
• ...

Overskrivningstilstand

Det er muligt at udelade XOR-operationer under absorption, mens du stadig opretholder det valgte sikkerhedsniveau . I denne tilstand i den absorberende fase overskriver den næste blok af input R- delen af ​​staten. Dette gør det muligt at holde en mindre tilstand mellem trinnene. Da R- delen alligevel vil blive overskrevet, kan den kasseres på forhånd, kun C- delen skal holdes.

Applikationer

Svampfunktioner har både teoretisk og praktisk anvendelse. I teoretisk kryptanalyse er en tilfældig svampfunktion en svampekonstruktion, hvor f er en tilfældig permutation eller transformation efter behov. Tilfældige svampfunktioner fanger flere af de praktiske begrænsninger af kryptografiske primitiver end den vidt anvendte tilfældige orakelmodel , især den endelige indre tilstand.

Svampekonstruktionen kan også bruges til at opbygge praktiske kryptografiske primitiver. For eksempel er Keccak kryptografisk svamp med en 1600-bit tilstand valgt af NIST som vinderen i SHA-3-konkurrencen . Styrken ved Keccak stammer fra den komplicerede, multi-round permutation f, som dens forfattere udviklede. Den RC4 -redesign kaldet Spritz refererer til det svampelignende konstruktionen at definere algoritmen.

For et andet eksempel kan en svampfunktion bruges til at opbygge godkendt kryptering med tilhørende data (AEAD).

Referencer