DES Data Encryption Standard-ren siglak dira (euskaraz Datu Kodeketa Estandarra). DES zifratze algoritmo bat da, hau da, informazioa kodetzeko metodoa.

DES IBMk garatuko kriptosistema da. Lucifer kriptosisteman hainbait aldaketa eginda eta NSAren (National Security Agency, edo euskaraz Segurtasunerako Nazio-agentzia) begiradarekin DES sistema jaio zen. Ameriketako Estatu Batuetan FIPS (Federal Information Processing Standards, edo euskaraz Informazio Prozesamendurako Estandar Federala) bezala aukeratua izan zen 1976. urtean. DES erabiltzea, 1977tik aurrera derrigorrezkoa bihurtu zen, AEB gobernuko informazioaren zifraketetan. Honen erabilpena mundu osoan zehar zabaldu zen. DES software naiz txip bezala inplementatu daieteke, VLSI teknologiari esker. Hardware adibide bezala PC-Encryptor daukagu eta softwarearena Oceanics enperesako DES-LOCK.

Gako pribatuko teknika da, bai zifratzean nola deszifratzean, hau 56 bitekoa delarik. Hasiera batetik algoritmo hau eztabaidagarria izan zen, diseinuaren elementu batzuk sailkatuak baitziren. Gainera, gako luzera motz samar bat erabiltzen zuen eta NSA erakundearentzat atzeko ate bat edukitzearen susmoak zeuden. Gerora DES algoritmoak azterketa akademiko gogor bat jasan zuen, blokekako zifraketaren kontzeptua ekarri zuen eta algoritmoaren kriptoanalisia bultzatu zen.

Gaur egun mundu mailan kriptosistema erabilgarrien artean dago, hala ere, DES aplikazio askotarako ez da segurutzat jotzen. Hau, batez ere, 56 biteko gako luzera motzegia delako da; ordenagailu berrien kalkulu potentzia dela-eta, erabiltzen dituen 56 bitak gutxiegi dira fidagarritasuna bermatzeko (DES gakoak 24 ordu baino gutxiagoan apurtu dira). Gainera, analisien emaitzek kodeketaren ahultasun teorikoak frogatu dituzte, hala ere praktikan bideraezinak dira. Algoritmo hau segurutzat jotzen da DES Hirukoitza moldaketan (3DES), nahiz eta eraso teorikoak egon.

Duela urte batzuk algoritmoa AESarengatik (Advanced Encryption Standard, edo euskaraz, Kodeketa Estandar Aurreratua) ordezkatua izan da.

Kasu batzuetan, DESk DEA (Data Encryption Algorithm, edo euskaraz Datu Kodeketa Algoritmoa) izena jaso du.

DESren historia

aldatu

DESren jatorria 70eko hamarkada hasieran kokatzen da. 1972. urtean, gobernuak segurtasun informatikoari buruz zituen beharren azterketa bukatu ondoren, AEBtako estandarren agintaritzak, NBSk (National Bureau of Standards) – orain NIST (National Institute of Standards and Technology, edo euskaraz Estandarren eta Teknologiaren Nazio-institutua) –, informazio konfidentziala zifratzeko gobernu mailako estandar baten beharra zegoela erabaki zuen. Honen ondorioz, 1973ko maiatzaren 15ean, NSArekin kontsultatu ondoren, NBSk diseinu irizpide zorrotz batzuk beteko zituen algoritmo batentzat proposamenak eskatu zituen. Hala ere, aurkeztutakoetatik bat ere ez zen egokia izan. 1974ko abuztuaren 27an bigarren eskaera bat egin zen. Kasu hartan IBMk onargarritzat hartu zen hautagai bat aurkeztu zuen, 1973 eta 1974 urteen artean garatutako algorimo bat. Hau Horst Feistel-en Lucifer algorimoan oinarritu zen. Algoritmoaren diseinuaz eta analisiaz arduratzen zen IBMko taldea ondorengo hauekin osatuta zegoen: Feistel, Walter Tuchman, Don Coppersmith, Alan Conheim, Carl Meyer, Mike Matyas, Roy Adler, Edna Grossman, Bill Notz, Lynn Smith, eta Bryant Tuckerman.

NSAren papera diseinuan

aldatu

1975eko martxoaren 17an DESren proposamena Erregistro Federalean argitaratu zen. Publikoren iruzkinak eskatu ziren, eta hurrengo urtean bi mintegi libre sortu ziren proposatutako estandarraren inguruan eztabaidatzeko. Alderdi batzuen kritikak egon ziren, Martin Hellman eta Whitfield Diffie barne (kriptografia simetrikoaren aitzindariak). Gako luzera motza eta S-kutxa misteriotsuak aipatu ziren NSAren interferentzia desegokiaren froga bezala. Agentziak ezkutuan agoritmoa ahuldu zuenaren susmoa zegoen, era honetan NSAk – eta ez beste inork – mezu zifratuak erraz irakur zitzakeen. Behin Alan Konheim-ek (DESren diseinatzaileetako bat) hurrengo hau aipatu zuen: "S-kutxak Washington-era bidali zituzten. Itzuli zirenean guztiz ezberdinak ziren". USSSCIk (United States Senate Select Committee on Intelligence, edo euskaraz Estatu Batuetako Senatuko Inteligentziarako Aparteko Batzordea) NSAren ekintzak berrikusi zituen jokabide desegokia egon zen erabakitzeko. Ondorioen sailkatu gabeko laburpenean, 1978an argitaratua, batzordeak hurrengoa zioen: "DESren garapenean, NSAk gako luzera motz bat nahikoa zela sinestarazi zion IBMri; S-kutxen egituraren garapenean zeharkako parte hartzea izan zuen; eta, zuten ezagutzekin, ahultasun matematiko edo estadistikorik ez zuela ziurtatu zuen". Dena den, hurrengo ondorioa ere atera zuen: "NSAk ez zuen inongo presiorik eragin algoritmoaren diseinuan. IBMk algoritmoa asmatu eta diseinatu zuen, honi buruzko erabaki guztiak hartu zituen eta DESrentzat pentsatuta zeuden aplikazio komertzial guztietarako gako luzera egokia zela bat egin zuen". DESren taldeko beste partaide batek, Walter Tuchman, hau esan zuen: "DES algoritmoa IBMn garatu genuen eta IBMko jendearekin. NSAk ez zuen pauso bat bera ere agindu!".

S-kutxek ahultasunak zuezkaten susmo batzuk alde batera utzi ziren 1990ean, Eli Biham-ek eta Adi Shamir-ek beraien kabuz aurkitutako eta libreki argitaratutako kriptoanalisi diferentziala dela eta. Hau blokekako zifratzeak apurtzeko metodo orokor bat da. DESren S-kutxak oso sendoak ziren, zoriz aukeratuak izan balira baino askoz gehiago. Honek IBMk 70eko hamarkadan teknika hau ezagutzen zuela iradokitzen zuen. 1994ean, Coppersmith jaunak S-kutxen jatorrizko diseinu irizpideak argaitaratu zituen. IBMk kriptoanalisi diferentziala aurkitu zuen 70eko hamarkadan eta, DES gogortu ondoren, NSAk teknika hau isilpean gordetzeko agindu zien. Coppersmith hau azaldu zuen: "Hau horrela izan zen kriptoanalisi diferentziala tresna oso ahaltsua izan daitekeelako, eskema ezberdin askoren aurka, eta informazio hau publikoaren eskutan egon ezkero segurtasun nazioanla kaltetu zezakeelako." Shamir-ek hau ere esan zuen: "Esango nuke, batzuek uste duten ez bezala, begi-bistan ez dagoela ezer DESren oinarrizko egituraren diseinua ahulduta dagoela pentsarazi dezakeenik."

Beste kritikak (gako luzera motzegiari buruzkoak) NSAk gako luzera mozteko emandako arrazoia susmagarria zirudien: gakoa 64 bitetik 56era igarotzean beste 8 bitak paritatea kalkulatzeko kontrol bit bezala erabil zitezkeen. Gehienek onartzen dute NSAren erabakiaren benetako arrazoia beste bat zela, agentziak 56 biteko gako baten aurkako eraso bat egiteko aukera indar gorria erabiliz beste edozein baino urte asko lehenago lor zezakeen.

Algoritmoa estandar bezala

aldatu

Nahiz eta eztabaidatsua izan, DES estandar federal bezala onartu zen 1976an, eta FIPS PUB 46 bezala argitaratua izan zen 1977ko urtarrilaren 15ean, sailkatu gabeko datuekin erabiltzeko baimendua. Geroago estandar bezala berretsi zen 1983an, 1988an (FIPS-46-1 bezala berrikusia), 1993an (FIPS-46-2), eta berriz ere 1998an (FIPS-46-3), azken honetan "DES Hirukoitza" definitu zen (ikus beherago). Azkenean 2002ko maiatzaren 26an, DES AESgatik ordezkatua izan zen txapelketa publiko baten ondoren. Gaur egun (2006) DES asko erabiltzen jarraitzen da.

1994ean eraso teoriko bat argitaratu zen: kriptoanalisi lineala. Baina indar gorria erabiliz 1998an egindako eraso bat izan zen DES praktikan eraso zitekeela frogatu zuena, eta ordezkapen algoritmo baten beharra nabarmendu zuen. Kriptoanalisi metodo hauek eta beste batzuk zehatzago azaltzen dira aurrerago artiku honetan bertan.

DESren sarrerak kriptografiaren azterketa akademikoa ekarri zuen, zehazki blokekako zifratzea apurtzeko metodoena. Bruce Schneier-ek idazten du:

"NSAk DES bere akats handietako bat bezala ikusi du. Jendeak softwarea idatz zezan honen zehaztasunak argitaratu egingo zirela jakin izan balu, ez litzateke inoiz ados egongo. DESk kriptografiaren eremua bultzatu zuen aurreko beste ezerk baino gehiago. Orain ikertzeko algoritmoa zegoen: NSAk segurua zela zioen bat."

Kronologia

aldatu
Data Urtea Gertakaria
Maiatzaren 15a 1973 NBSak zifratze algoritmo estandar baten lehen eskakizuna argitaratzen du.
Abuztuaren 27a 1974 NBSak zifratze algoritmo estandar baten bigarren eskakizuna argitaratzen du.
Martxoaren 17a 1975 DES Erregistro Federalean argitaratu zen iruzkinak egiteko.
Abuztua 1976 DESren lehen mintegia.
Iraila 1976 Bigarren mintegia, DESren oinarri matematikoen ingurukoa.
Azaroa 1976 DES estandar bezala onartzen da.
Urtarrilaren 15a 1977 DES FIPS bezala argitaratzen da, FIPS PUB 46 estandarra.
1983 DES lehen aldiz berresten da.
Urtarrilaren 22a 1988 DES bigarren aldiz berresten da FIPS 46-1 bezala, FIPS PUB 46 ordezkatuz.
1992 Biham-ek eta Shamir-ek indar gorria baino konplexutasun gutxiago duen lehen eraso teorikoa argitaratzen dute: kriptoanalisi diferentziala. Edozein kasutan, hautatutako 247 testu garbi behar dira (Biham ans Shamir, 1992).
Abenduaren 30a 1993 DES hirugarren aldiz berresten da FIPS 46-2 bezala.
1994 DESren lehen kriptoanalisi esperimentala burutzen da kriptoanalisi lineala erabiliz.
Uztaila 1998 EFFren (Electronic Frontier Foundation, edo euskaraz Muga Elektronikoen Fundazioa) DES cracker-ak, Deep Crack bezala ezaguna, DES gako bat 56 ordutan apurtzen du.
Urtarrila 1999 Deep Crack eta distributed.net elkartzen dira eta DES gako bat 22 ordu eta 15 minututan apurtzen dute.
Urriaren 25a 1999 DES laugarren aldiz berresten da FIPS 46-3 bezala, DES Hirukoitzaren erabilera hobetsiz , DES simplea sistema heredatuetan bakarrik baimentzen da.
Azaroaren 26a 2001 AES algoritmoa FIPS 197 bezala argitaratzen da.
Maiatzaren 26a 2002 AES estandarra egiazko bihurtzen da.
Uztailaren 26a 2004 Erregistro Federalean FIPS 46-3a (eta erlazionatutako beste bi estandar) baztertzea proposatzen da.
Maiatzaren 19a 2005 NISTk FIPS 46-3a baztertu egin zuen.
Martxoaren 15a 2007 FPGAn oinarritutako COPACABANA makina paraleloak DES apurtzen du 6,4 egunetan. Makina hau Bochum eta Kiel-eko unibertsitateetan egin zen, Alemanian, 10.000 dolarreko kostua izan zuelarik.

Funtzionamendua

aldatu

64 biteko testu bloke argitan lan egiten duen zifratze algoritmo bat da; hauei 56 bitetako gako bat aplikatzen zaie, azkenean 64 biteko bloketan banatutako testu zifratu bat lortzen delarik. Permutazio, ordezkapen eta OR esklusiboan oinarritzen da eta gako bera erabiliz atzera jo daitekeela du propietate gisa. Deszifratzeko egin behar den gauza bakarra, gakoa erabiltzea da, zifratzeko egin diren pausoak alderantzizko ordenan eginaz.

DESren aurka egin daitekeen eraso mekanismorik onena, indar gorria erabiltzean datza. Hau da, kodetutako testua deszifratzen saiatu gako posible guztiak probatuz (256 = 7.206 x 106 aukera) eta, emaitza logikoak lortu, edo testu argi zati bat izanez gero, lortutako emaitzarekin parekatu.

Algoritmoa teorikoki sendoa da eta ez du ahulune garrantzitsurik (erabili behar ez diren gako ezagun gutxi batzuk daude). IBMk egin zuen lehen bertsioa 128 bitekoa izanik, oraindik indar gorri motako erasoak gainditzeko gai da. Hala ere, gaur egungo bilakaera teknologikoa ikusirik, DES estandarrak ematen duen segurtasuna (soilik 56 biteko gakoekin) nahiko mugatua da, are gehiago, jada inoiz bortxatua izan da. (Batzuk diote NSAk hasierako 128 bitak 56ra murriztu zituela DESrekin kodetutako mezuak deszifratu ahal izateko). Honek guztiak, beste sistema simetriko batzuen bilaketa hasi du (3DES, IDEA,...).

Deskribapena

aldatu
 
1 irudia — Feistel-en egitura orokorra DESn
Laburtzeko asmoz, jarraian datorren deskribapenak algoritmoaren aldaketa eta permutazio zehatzak baztertu egin dira; informazio gehiagorako ikus DES eduki gehiagarria.

DES blokekako zifraketaren prototipo algoritmoa da — bit luzera jakin bateko testu garbi bat hartzen du algoritmo honek, eta eragiketa konplexu batzuen bidez luzera berdineko testu zifratuan eraldatzen du. DESren kasuan blokearen tamaina 64 bitekoa da. DESk gako kriptografiko bat ere erabiltzen du eraldaketa aldatzeko, modu honetan kodeketan erabilitako gakoa ezagutzen dutenek bakarrik egin dezakete deszifraketa. Gakoak 64 biteko luzera du, baina hauetatik bakarrik 56 erabiltzen dira algoritmoan. Gainontzeko 8 bitak paritatea egiaztatzeko bakarrik erabiltzen dira, eta gero baztertu egiten dira. Beraz, DESren gako luzera eraginkorra 56 bitekoa da, eta horrela zehazten da.

Beste blokekako zifratzetan bezala, DES blokekako zifratze eragiketa moduan erabili behar da 64 bit baino luzeagoko mezuetan (mezua 64 bit baino luzeagoa bada, mezua 64 biteko bloketan banatzen da, gero blokeak banan-banan kodetzen dira). FIPS-81ek DES erabiltzeko hainbat modu zehazten ditu, egiaztapenerako modu bat barne. FIPS-74ean DESren erabilpenerako beste dokumentu batzuk kontsulta daitezke.

Oinarrizko egitura

aldatu

Algoritmoaren oinarrizko egitura 1 irudian irudikatzen da: prozesuak 16 fase berdin ditu, txandak deiturikoak (rounds). Hasierako eta bukaerako permutazioak ere ditu, IP eta FP, elkarren artean alderantzizkoak direnak (IPk FPren eragina "desegiten" du, eta alderantziz). IP eta FP kriptografikoki ez dira esanguratsuak, baina ustez 70eko hamarkada erdialdeko hardware-an blokeen karga eta deskarga errazteko sartu ziren. Txanden aurretik, blokea 32 biteko bi zatitan banatzen da eta txandaka prozesatzen dira. Gurutzaketa hau Feistel eskema bezala ezagutzen da.

Feistel eskemak zifraketa eta deszifraketa prozesuak oso antzekoak izan daitezen bermatzen du — ezberdintasun bakarra deszifraketan azpi-gakoak aurkako ordenean erabiltzen direla da. Algoritmoaren gainontzekoa berdin-berdina da. Honek inplementazioa izugarri errazten du, hardware-an bereziki, ez baitago zifraketarako eta deszifraketarako algoritmo ezberdinak erabiltzeko beharrik.

Gorriz dagoen   ikurra OR esklusiboaren (XOR) eragitketa adierazten du. F-funtzioak blokearen erdia gakoaren zati batekin nahasten du, eta gero bi azpi-blokeak trukatu egiten dira hurrengo txanda baino lehen. Azken txandaren ondoren, bi azpi-blokeak ez dira trukatzen; hau Feistel-en egituraren ezaugarri bat da zeinak zifraketa eta deszifraketa antzeko prozesuak izan daitezen egiten duen.

Feistel-en funtzioa (F)

aldatu
 
2 irudia — DESren Feistel funtzioa (F-funtzioa)

F-funtzioak, 2 irudian irudikatzen da, 32 biteko bloke erdi baten gainean egiten du lan eta lau pausoz osatzen da.

  1. Hedapena — 32 biteko blokearen erdia 48 bitetara luzatzen da hedapen permutazioaren bidez, diagraman E deitua, bit batzuk errepikatu egiten dira.
  2. Nahasketa — emaitza azpi-gakoarekin batzen da XOR eragiketaren bidez. Hasierako gakotik 16 azpi-gako (txanda bakoitzerako bat) eratortzen dira, hauek beherago azaltzen den azpi-gakoen sorkuntzaren bidez lortzen dira.
  3. Ordezkapena — azpi-gakoarekin nahastu ondoren, blokea 6 biteko zortzi zatitan banatzen da, eta zati bakoitza S-kutxetan, edo aldaketa kutxetan, prozesatzen dira. S-kutxetako bakoitzak sarrerako 6 bit irteerako 4 bitengatik aldatzen ditu. Aldaketa hau transformazio ez lineal baten bidez egiten da, bilaketa taulak zehazten duen bezala. S-kutxek DESren segurtasunaren muina osatzen dute — hauek gabe, zifraketa lineala izango litzateke, eta apurtzeko erraza.
  4. Permutazioa — azkenik, S-kutxen 32 irteerak permutazio finko batekin berrantolatzen dira; P-kutxa.

S-kutxen ordezkapenen txandakatzeak, eta P-kutxaren permutazioaren eta E-hedapenaren txandakatzeak "nahasmena eta zabalkundea" dakartzate. Kontzeptu hau zifratze bat segurua eta praktikoa izateko derrigorrezko baldintza bezala identifikatu zuen Claude Shannon-ek 40ko hamarkadan.

 
3 irudia — DESren gakoen sorkuntza.

Gako sorkuntza

aldatu

3 irudiak zifraketarako gako sorkuntza irudikatzen du — azpi-gakoak emateaz arduratzen den algoritmoa. Lehenengo, hasierako gakoaren 64 bitetatik 56 hartzen dira Aukeraketa Permutazioa 1en bidez (PC-1) — beste zortzi bitak alde batera utz daitezke edo bestela paritatea egiaztatzeko erabili. 56 bitak 28 biteko bi zatitan banatzen dira; ondoren zati bakoitza bere aldetik maneiatzen da. Txanda bakoitzean, bi zatiak ezkerrera lekualdatzen dira bit bat edo bi bit (txandaren arabera), eta 48 biteko azpi-gakoa sortzen da Aukeraketa Permutazioa 2aren bidez (PC-2) — 24 bit ezkerreko zatikoa eta 24 bit eskuinekoa. Lekualdaketek (diagraman "<<<" ikurrarekin azaltzen da) azpi-gako bakoitzerako bit multzo ezberdina erabiltzen dela ziurtatzen dute; gutxi gorabehera bit bakoitza 14 aldiz erabiltzen da 16 azpi-gakoetan.

Deszifraketa prozesuan gako sorkuntza antzeko moduan egiten da — gakoak alderantzizko ordenean sortu behar dira. Beraz, desplazamenduak eskuinerantz egin behar dira ezkerrerantz beharrean.

Ordezkapen algoritmoak

aldatu

DESren erabiltzaile zaharretako askok DES Hirukoitza (3DES) erabiltzen dute orain. Hau DESren patenteetako batean deskribatu eta aztertu zen (ikus FIPS PUB 46-3); DES hiru aldiz jarraian erabiltzean datza, aldi bakoitzean gako ezberdin bat erabiliz. Momentuz, orokorrean 3DES segurutzat hartzen da, nahiz eta nahiko geldoa izan. Konputagailu eragiketa aldetik alternatiba merkeago bat DES-X da, gako luzera handitzen duena XOR logiko bat eginez gakoaren aparteko elementuen gainean DES baino lehen eta gero. GDES kodetze prozesua azkartzen duen DESren aldaera bat da, baina kriptoanalisi diferentzialaren bidez apurtzeko aukera zegoela frogatu zen.

2001ean, nazioarteko txapelketa baten ondoren, NISTk DES ordezkatzeko algoritmo berri bat aukeratu zuen: AES (Advanced Encrytion Standard). AES izateko aukeratutako algoritmoa bere diseinatzaileek aurkeztu zuten Rijndael izenarekin. NISTk antolatutako AES txapelketako beste finalista batzuk RC6, Serpent, MARS eta Twofish izan ziren.

Orokorrean, ez dago erabilera guztietarako ezin hobeki moldatzen den algoritmorik. Erabilera orokorretarako makina batean erabiltzeko algoritmo bat (adibidez, SSH, edo posta elektronikorako zifratze mota batzuk), beti ez dabil ondo sistema txertatuetan edo txartel adimenduetan, eta alderantziz.

Segurtasuna eta kriptoanalisia

aldatu

Blokekako beste edozein zifratzerekin konparatuz, DESren kriptoanalisiari buruzko informazio askoz gehiago argitaratu da. Nahiz eta hau horrela izan, gaur egungo erasorik praktikoena indar gorriaren bidez izaten jarraitzen du. Garrantzi txikiko propietate kriptoanalitiko asko ezagutzen dira, eta hiru eraso mota teoriko posible daude zeintzuak indar gorri bidezko eraso bat baino konplexutasun teoriko txikiagoa behar duten. Hala ere eraso mota hauek burutu ahal izateko testu garbi ezagun eta hautatu kopuru ezinezkoa behar dute. Arrazoi honengatik ez dira praktikan kontutan hartzen.

Indar gorri bidezko erasoa

aldatu
 
Electronic Frontier Foundation-en DES crackeatzeko makina. 1536 txip zituen eta DES gako bat egunetan apurtu zezakeen indar gorria erabiliz – Irudian Deep Crack txip ugari dituen zirkuitu bat ikus daiteke.

Edozein zifratze motarako, eraso motarik sinpleena indar gorri bidezko erasoa da. Indar gorriak gako posible guztiak banan-banan egiaztatzen ditu. Gako luzerak gako posible kopurua zehazten du, eta beraz erasoaren bideragarritasuna ere. DESren kasuan, bere hastapenetan zuen gako luzera eztabaidatu egin zen, estandar moduan onartua izan baino lehen ere. Kriptoanalisi teorikoa baino gehiago, bere gako luzera motza izan zen algoritmoaren ordezkapena eragin zuena. Gauza jakina da NSA izan zela IBM bultzatu zuena, edo agian behartu zuena, gako luzera 128 bitetik 64ra murriztera, eta hortik 56 bitera moztera. Hau askotan froga moduan hartu izan da, 70eko hamarkada erdialdean NSAk tamaina honetako gakoak apurtzeko ahalmen konputazional nahikoa zuela esateko.

Akademikoki, DES apurtzeko makinen proposamen ugari aurreratu ziren. 1977an, Diffie-k eta Hellman-ek 20 milioi dolarretan balioztatutako kostua zuen makina bat proposatu zuten, honek DES gako bat egun bakar batean aurkitzeko gaitasuna izango zuen. 1993. urte inguruan. Wiener-ek gako bilaketarako makina bat proposatu zuen, honen kostua milioi bat dolarretan balioztatu zen eta gakoa 7 ordutan aurkitzeko gai izango zen. DESren ahultasuna praktikan 1998an frogatua gelditu zen Electronic Frontier Foundation (EFF) fundazioak, ziberespazioaren zuzenbide zibilari buruz arduratzen den talde bat, DES apurtzeko zuzenduta zegoen makina bat eraiki zuenean, 250.000 dolarreko gutxi gorabeharako kostuarekin (ikus EFF DES craker). DES apurtzea, bai teorian bai praktikan, posible zela frogatzea zuen helburu: "Jende asko dago ez duela egia sinetsiko bere begiekin ikusteko aukera izan arte. DES egun gutxi batzuetan apurtzeko gai den egiazko makina bat erakustea da jendea konbentzitzeko modu bakarra, ikus dezaten benetan ezin dutela beraien segurtasuna DESren eskuetan utzi.". Makina honek gako bat apurtu zuen indar gorria erabiliz, bilaketak 2 egun baino apur bat gehiago iraun zuen. Gutxi gorabehera aldi berean, AEBtako Segurtasun Saileko abokatu batek DES hauskaitza zela ziurtatzen zuen.

Indar gorria baino eraso azkarragoak

aldatu

DESren 16 txandak indar gorri bidezko eraso bat baino konplexutasun txikiagoarekin apur dezaketen hiru eraso ezagutzen dira: kriptoanalisi diferentziala (KD), kriptoanalisi lineala (KL) eta Davies-en erasoa. Dena den, eraso guzti hauek teorikoak baino ez dira eta ezin dira praktikan aurrera eraman; eraso mota hauek batzuetan "egiaztapeneko ahultasunak" deitzen dira.

  • Kriptoanalisi diferentziala Eli Biham-ek eta Adi Shamir-ek aurkitu zuten 80ko hamarkadaren amaiera aldean, hala ere, NSAk eta IBMk lehenagotik ezagutzen zuten, baina hauek isilpean gorde zuten. 16 txandak apurtzeko, kriptoanalisi diferentzialak 247 testu garbi hautatu behar ditu. DES KD jasateko diseinatua izan zen.
  • Kriptoanalisi lineala Mitsuru Matsui-k aurkitu zuen, eta 243 testu garbi hautatu behar ditu (Matsui, 1993); metodo hau inplementatua izan zen (Matsui, 1994), eta ezagutzera eman zen DESren lehen kriptoanalisi esperimentala izan zen. DES eraso mota hau jasateko moldatua izan zela frogatzen duen aztarnarik ez dago. KLaren orokortze bat, kriptoanalisi lineal anizkuna, 1994. urtean proposatu zen (Kaliski eta Robshaw), eta gero Biryukov-ek eta beste batzuek hobetu egin zuten (2004). Bere analisiak hurbilketa lineal anizkunak erabil daitezkeela aditzera ematen du, horrela erasorako behar den datu kopurua gutxitu daiteke gutxienez 4ko faktore batean (hau da, 241 testu beharko lirateke 243 beharrean). Aurrekoaren antzera, datuen konplexutasuna murrizteko testu garbi hautatuen kriptoanalisi linealaren moldaketa bat erabil daiteke (Knudsen eta Mathiassen, 2000). Junod-ek (2001) hainbat saiakuntza egin zituen kriptoanalisi linealaren konplexutasuna zehazteko, eta aurresan zena baino zerbait azkarragoa zela ikusi zuen, DESren 239 – 241 egiaztapen egiteko behar den denbora hain zuzen ere.
  • Davies-en eraso hobetua: analisi lineal eta diferentzialak teknika orokorrak dira eta eskema ezberdin ugaritan aplikatu daitezkeen bitartean, Davies-en erasoa zehazki DESrentzat sortutako teknika bat da. Lehen aldiz Davies-ek proposatu zuen 80ko hamarkadan eta Biham-ek eta Biryukov-ek hobetu egin zuten (1997). Erasoaren modu ahaltsuenak 250 testu garbi hautatu behar ditu, 250eko konplexutasun konputazionala dauka, eta arrakasta izateko probabilitatea %51koa da.

Txanda gutxiago erabiltzen duten algoritmo honen bertsioak existitzen dira, eta hauentzat pentsatuta dauden erasoak ere badaude, hau da, 16 txanda baino gutxiago duten DESren bertsioetarako. Analisi hauek segurtasuna lortzeko behar diren txanda kopuruaren ikuspegi bat ematen dute, eta bertsio osoak zein segurtasun-marjin ematen duen jakiteko ere balio dute. Langford-ek eta Hellman-ek kriptoanalisi diferentzial-lineala proposatu zuten 1994. urtean, eta kriptoanalisi diferentziala eta lineala eraso bakar batean batzen ditu. Eraso honen bertsio hobetu batekin 9 txandako DES bat apurtu dezake 215,8 testu garbi ezagun erabiliz eta 229,2ko denbora konplexutasuna dauka (Biham eta beste batzuk, 2002).

Ikus, gainera

aldatu

Kanpo estekak

aldatu