Blokkchiffer

Innen kryptografi er et blokkchiffer (blokkryptogram) et symmetrisk nøkkelchiffer som utfører en fastsatt omforming av grupper av bits med fastsatt lengde, som kalles blokker. Når det krypteres så kan et blokkchiffer eksempelvis ta en 128-bit blokk av klartekst som inndata, og produsere en tilsvarende 128-bit blokk med chiffertekst. Nøyaktig hvilken omforming som benyttes er kontrollert av en tilleggsinformasjon — den hemmelige krypteringsnøkkelen.

Kryptering

Dekryptering

Dekryptering er tilsvarende: dekrypteringsalgoritmen tas som inndata chifferteksten og krypteringsnøkkelen, og i eksempeltilfellet produserer den opprinnelige 128-bit klarteksten.

For å kryptere meldinger lenger enn blokkstørrelsen (128 bit i eksempelet over), så brukes et blokkoperasjonsmodus.

Blokkchiffer kan skilles fra flytchiffer (flytkryptogram) ved at et flytchiffer opererer på individuelle tegn – en av gangen, og transformeringen varierer under den pågående krypteringen. Skillet mellom disse to typene chiffer er ikke alltid helt klart, for når et blokkchiffer brukes i enkelte blokkoperasjonsmodus, så er virker det i realiteten som et flytchiffer.

En tidlig og meget viktig implementasjon av et blokkchiffer er Data Encryption Standard (DES), utviklet hos IBM og publisert som en standard i 1977. En etterfølger til DES, Advanced Encryption Standard (AES), ble innført i 2001.

Generelt

Et blokkchiffer består av to algoritmer som er satt sammen i som et par. En for kryptering E og en for dekryptering E^-1. Begge algoritmene aksepterer to inndata: inngående blokkstørrelse på n bit, og en krypteringsnøkkel på k bits, som gir en n-bit blokk med utdata. For enhver fast nøkkel, så er dekryptering den inverse funksjonen av kryptering, slik at

$E_{K}^{-1}(E_{K}(M))=M$

for enhver blokk M og krypteringsnøkkel K.

For hver nøkkel K, så er E_K en permutasjon over settet av inndata blokker. Hver nøkkel velger en permutasjon fra den mulige listen av $2^{n}!$.

Blokkstørrelsen n er typisk 64 eller 128 bit, selv om noen chiffer har variabel blokkstørrelse. 64 bit var den vanligste størrelsen inntil midt på 90-tallet, når ny design begynte å bruke den lengre 128-bit størrelsen. En av flere blokkoperasjonsmodi brukes gjerne med en utfylling for å tillate at klartekster med uodd størrelse kan krypteres. Hver modus har forskjellige karakteristikker i forhold til feilhåndtering, tilgjengelighet og svakheter overfor spesifikke angrep. Typiske nøkkelstørrelser (k) inkluderer 40, 56, 64, 80, 128, 192 og 256 bit. I 2006 så regnes 80 bit som minste nøkkelstørrelse som er påkrevet for å unngå bruteforce angrep.

Itererte blokkchiffer

De fleste blokkchiffer er laget ved å gjenta en enklere funksjon. Denne fremgangsmåten er kjent som itererte blokkchiffer (se også produktchiffer). Hver iterasjon er betegnet som en runde, og den repeterte funksjonen er betegnet rundefunksjon. Alt mellom 4 og 32 runder er typisk.

Mange blokkchiffer kan kategoriseres som Feistel-chiffer, eller mer generelt substitusjon/permutasjon-chiffer. Aritmetiske operasjoner, logiske operasjoner (særlig XOR), S-bokser og forskjellige permutasjoner blir ofte brukt som komponenter.

Historie

Lucifer regnes som det første sivile blokkchiffer, utviklet hos IBM på 70-tallet, basert på arbeidet til Horst Feistel. En oppdatert versjon av algoritmen ble antatt som en FIPS standard hos regjeringen i USA, som i dag er kjent som Data Encryption Standard (DES). Den ble valgt av US National Bureau of Standards (NBS) etter en offentlig utlyst invitasjon for bidrag, og noen interne endringer utført av NBS (og, muligens NSA). DES ble offentlig publisert i 1976, og har blitt meget utbredt.

DES ble utviklet for blant annet å motstå et spesifikt kryptoanalytisk angrep som var kjent av NSA, og som ble gjenoppdaget av IBM. Selv med denne historien har angrepet ikke vært alment kjent, inntil det ble gjenoppdaget ennå en gang, og publisert av Eli Biham og Adi Shamir på slutten av 80-tallet. Teknikken kalles differensiell kryptoanalyse og er en av få generelle angrep mot blokkchiffer. Lineær kryptoanalyse er en annen teknikk som faktisk kan ha vært ukjent for NSA inntil den ble publisert av Mitsuru Matsui. DES var årsaken til mye utført arbeide og publiseringer innenfor kryptografi og kryptoanalyse i samfunnet for åpen kildekode, og DES var inspirasjonskilde til utvikling av mange nye chiffermetoder.

DES har en blokkstørrelse på 64 bits og en nøkkelstørrelse på 56 bits. 64-bit blokker ble vanlige i blokkchiffer design etter DES. Nøkkellengder var avhengige av flere faktorer, blant dem offisielle retningslinjer. Mange observatører på 70-tallet kommenterte at 56-bit blokkstørrelsen som ble brukt i DES ble for kort. Etterhvert som tiden gikk ble utilstrekkeligheten klarere, og påpekt særlig gjennom en spesiallaget maskin som hadde som fokus på å knekke DES. Denne ble demonstrert i 1988 av Electronic Frontier Foundataion. En variant av DES, Trippel DES, utfører en trippel-kryptering (chifrering) på blokker med (vanligvis) to forskjellige nøkler (2TDES), som resulterer i en 112-bit nøkkel og 80-bit sikkerhet. Dette ble jevnt over akseptert som en erstatter, og er fremdeles (2004) ansett som sikkert.

DES har blitt erstattet av Advanced Encryption Standard (AES). Chifferet ble utviklet av to belgiske kryptografer, Joan Daemen og Vincent Rijmen, og ble innsendt som Rijndael. AES har en blokkstørrelse på 128 bits og tre mulige nøkkelstørrelse, 128, 192 og 256 bits.

Kilder

• M. Liskov, R. Rivest, and D. Wagner, "Tweakable Block Ciphers", Crypto 2002 PDF.

Eksterne lenker

• A list of many symmetric algorithms, the majority of which are block ciphers.
• The block cipher lounge
• What is a block cipher? fra RSA FAQ
• Block Ciphers and Cryptanalysis (PDF). Technical Report: an introduction to mathematics of block ciphers and methods for cryptanalysis.