Datakrypteringsstandard

DES ( datakrypteringsstandard )

DES-F-funksjon. sammendrag

Designer (r)	IBM
Første publikasjon	1975 ( 1977 for standarden)
Avledet fra	Lucifer
Kryptering (er) basert på denne algoritmen	Triple DES , G-DES , DES-X , LOKI89 , ICE

Kjennetegn

Blokkstørrelse (r)	64 bits
Nøkkel lengde (r)	56 biter
Struktur	Feistel-ordningen
Antall svinger	16 runder med DES

Bedre kryptanalyse

lineær kryptanalyse , differensiell kryptanalyse , brute force-angrep nå mulig

Den Data Encryption Standard ( DES , uttales / d ɛ s /) er en algoritme symmetrisk krypterings ( blokkode ) ved anvendelse av 56 nøkkelbiter . Bruken av den anbefales ikke lenger i dag på grunn av dens treghet i utførelsen og for liten nøkkelplass som tillater et systematisk angrep på rimelig tid. Når den fortsatt brukes, er den vanligvis i Triple DES , som ikke gjør noe for å forbedre ytelsen. DES har blitt brukt spesielt i UNIX- passordsystemet .

Den første DES-standarden er utgitt av FIPS den15. januar 1977 under navnet FIPS PUB 46. Den siste versjonen før foreldelse stammer fra 25. oktober 1999.

Historie

I Mai 1973American National Bureau of Standards krever at det opprettes en krypteringsalgoritme som kan brukes av selskaper. På den tiden hadde IBM allerede en algoritme kalt Lucifer , designet i 1971 av Horst Feistel .

Logisk sett burde denne algoritmen ha blitt valgt av NBS. I praksis var dette nesten tilfelle: NSA krevde at Lucifer ble endret, av ham. Dermed ble DES opprettet, som ble vedtatt som standard i november 1976 . Dette vekket mistanker om at NSA med vilje svekket algoritmen, i et forsøk på å kunne bryte den. Merkelig, DES har vist seg å være motstandsdyktig mot flere angrep som ikke var forventet å dukke opp i det akademiske samfunnet før mye senere. Enda mer forbløffende motsto Lucifer , ham, mindre godt. Dette antyder at NSA på den tiden var klar over disse kryptanalyseteknikkene , og at den derfor i realiteten ville gjøre DES mer motstandsdyktig.

Operasjon

DES-algoritmen forvandler en 64-biters blokk til en annen 64-biters blokk. Den manipulerer individuelle 56-bits nøkler, representert med 64 bits (med en bit i hver byte som brukes til paritetskontroll ). Dette symmetriske krypteringssystemet er en del av den iterative blokkeringsfamilien, mer spesifikt er det et Feistel-oppsett (oppkalt etter Horst Feistel ved opprinnelsen til Lucifer- krypteringen ).

Generelt kan vi si at DES fungerer i tre trinn:

innledende og fast permutasjon av en blokk (uten noen innvirkning på sikkerhetsnivået);
resultatet blir utsatt for 16 iterasjoner av en transformasjon, disse iterasjonene avhenger ved hver sving av en annen delnøkkel på 48 bits. Denne mellomtasten blir beregnet fra brukerens opprinnelige nøkkel (takket være et nettverk av erstatningstabeller og XOR- operatører ). Under hver sving er 64-biters blokken delt i to 32-biters blokker, og disse blokkene byttes ut med hverandre i henhold til et Feistel-skjema. Den viktigste 32-biters blokken (den som strekker seg fra 32 bit til 64 bit) vil gjennomgå en transformasjon;
resultatet av den siste svingen blir transformert av den inverse funksjonen til den første permutasjonen.

DES bruker åtte erstatningstabeller ( S-Boxes ) som var gjenstand for mye kontrovers med hensyn til innholdet. Vi mistenkte en svakhet som bevisst ble satt inn av designerne. Disse ryktene ble fjernet på begynnelsen av 1990-tallet ved oppdagelsen av differensiell kryptanalyse som viste at bordene var godt utformet.

Angrep

Flere angrep har blitt oppdaget på DES. De gjør det mulig å redusere kostnadene ved et uttømmende søk etter nøkler som i gjennomsnitt utgjør operasjoner. Noen av disse metodene er ikke lenger effektive med nyere krypteringsalgoritmer på grunn av innføringen av en skredeffekt . $2 ^ {{55}}$

Den differensial kryptoanalyse oppdaget av Eli Biham og Adi Shamir i 1991 gjør det mulig å finne nøkkelen ved hjelp av ren tekst. Prinsippet er å ha en DES implementert i en hermetisk svart boks med en hemmelig nøkkel inni. Ved å gi nok tekst som inndata, kan vi statistisk analysere oppførselen til utgangene i henhold til inngangene og finne nøkkelen. Inngangene som brukes til dette angrepet må ha en liten forskjell i forhold til hverandre (f.eks. En skiftende bit). Ved å se på hvordan forskjellen påvirker produksjonen, kan du etablere statistikk og ved å øke antall innganger forbedrer du påliteligheten av angrepet. $2 ^ {{47}}$
T-angrepet ( Tickling attack ) er en variant av differensiell kryptanalyse oppdaget i 1974 under design av DES av IBM-forskere. I tjue år var det fullstendig stillhet om denne oppdagelsen. Det var Don Coppersmith som avslørte hemmeligheten i 1994. På det tidspunktet hadde hun oppfordret DES-designerne til å styrke innholdet i erstatningstabellene (i stedet for å svekke det slik ryktene antydet).
Den lineære kryptanalysen , oppfunnet av Henry Gilbert og uavhengig av Mitsuru Matsui i 1993, er mer effektiv, men mindre praktisk av den enkle grunn at angriperen ikke har den svarte boksen, og han kan ikke sende inn sine egne tekster. Dette angrepet krever par (alle kryptert med samme nøkkel) som angriperen har klart å gjenopprette på en eller annen måte. Den består i å lage en lineær tilnærming av DES ved å forenkle den. Ved å øke antallet tilgjengelige par forbedres presisjonen til tilnærmingen, og nøkkelen kan trekkes ut. $2 ^ {{43}}$
Den tids minne kompromiss er et konsept utviklet av Martin Hellman i 1980. Forutsatt at den samme meldingen vil bli kryptert flere ganger med forskjellige nøkler, kan vi beregne et stort bord som inneholder alle de krypterte versjoner av. Melding dette. Når vi fanger opp en kryptert melding, kan vi finne den i tabellen og få tak i nøkkelen som ble brukt til å kode den. Dette angrepet er selvfølgelig ikke gjennomførbart fordi vi trenger en tabell i størrelsesorden en milliard GB. Hellmans geni var å finne en måte å redusere denne tabellen til omtrent 1 terabyte (eller 1 million ganger mindre enn hele bordet), som er gjennomførbart i dag.
På de andre angrepene er spesifikke implementeringer og er ikke nødvendigvis spesifikke for DES. I tilfelle av en DES implementert i maskinvare, kan man analysere strømforbruket og utlede litt informasjon om nøkkelen (økt forbruk indikerer aktive biter ). Den samme angrepsstilen kan også brukes på en datamaskin ved å beregne tiden det tar å kryptere med forskjellige tekster eller ved å analysere minnet som brukes.
Alle andre DES-angrep tar sikte på å redusere beregningstiden for et uttømmende søk ved å bruke maskiner spesielt designet for oppgaven (takket være FPGA-er parallelt, for eksempel). En slik maskin ble bygget i 1998 . Deep Crack kostet rundt $ 200 000 og kan bryte nøkkelen på mindre enn en uke. Den distribuert databehandling ved hjelp av datamaskinene til individer ( distributed.net ) har vist seg effektive i å bryte en nøkkel på mindre enn 24 timer .

Status

Algoritmen opprinnelig designet av IBM brukte en 112-bit nøkkel. NSA- intervensjon reduserte nøkkelstørrelsen til 56 bits. I dag er Triple DES fortsatt veldig populær, og "enkel" DES eksisterer bare i eldre applikasjoner. DES-standarden ble erstattet i 2001 av AES (Advanced Encryption Standard).

Merknader og referanser

Merknader

Referanser

(in) " Data Encryption Standard (DES) " [PDF] ,25. oktober 1999(åpnet 20. oktober 2015 ) .
Involvering av NSA i utviklingen av standard for datakryptering
(i) Don Coppersmith , " The Data Encryption Standard (DES) and Its strength contre attack " , IBM Journal of Research and Development , Vol. 38, n o 3, Mai 1994, s. 243 ( les online [PDF] )

Vedlegg

Relaterte artikler

Eksterne linker

(no) En veiledning om lineær og differensiell kryptanalyse av Howard M. Heys: Dokument som oppsummerer lineær og differensiell analyse