Kan DES worden doorbroken door differentiële cryptanalyse?
Differentiële cryptanalyse is een vorm van cryptanalyse die voornamelijk van toepassing is op blokcijfers, waarbij het effect van bepaalde verschillen in invoerparen op de verschillen aan de uitgang wordt geanalyseerd. Deze methode werd eind jaren tachtig geïntroduceerd door Eli Biham en Adi Shamir en is sindsdien een fundamenteel hulpmiddel geworden in de toolkit van de cryptanalist. De Data Encryption Standard (DES), een algoritme met symmetrische sleutels voor de encryptie van digitale gegevens, is een van de belangrijkste onderwerpen van differentiële cryptanalyse.
Het DES-algoritme, begin jaren zeventig door IBM ontworpen en in 1970 als federale standaard aangenomen door het National Institute of Standards and Technology (NIST), werkt op 1977-bits gegevensblokken met behulp van een 64-bits sleutel. DES maakt gebruik van 56 rondes van een Feistel-netwerk, waarbij elke ronde bestaat uit een reeks vervangingen en permutaties, bepaald door het sleutelschema.
Om te begrijpen of DES kan worden doorbroken door differentiële cryptanalyse, is het belangrijk om rekening te houden met de specifieke kenmerken van zowel de DES-structuur als de principes van differentiële cryptanalyse.
DES-structuur en sleutelschema
DES is gebouwd op een combinatie van substitutie- en permutatiebewerkingen. Elke DES-ronde omvat de volgende stappen:
1. Uitbreiding (E-box): Het halve blok van 32 bits wordt uitgebreid tot 48 bits met behulp van een uitbreidingspermutatie.
2. Toetsmix: Het uitgebreide halve blok wordt XORed met een ronde sleutel afgeleid van de hoofdsleutel met behulp van een sleutelschema.
3. Vervanging (S-box): Het 48-bits resultaat wordt verdeeld in acht 6-bits segmenten, die elk door een overeenkomstige S-box worden geleid om een 4-bits uitvoer te produceren. De acht 4-bits uitgangen worden aaneengeschakeld om een 32-bits blok te vormen.
4. Permutatie (P-box): Het 32-bits blok wordt gepermuteerd met behulp van een vaste permutatietabel.
5. XOR en Swap: Het gepermuteerde blok wordt XORed met de andere helft van het datablok, en de helften worden verwisseld.
Het sleutelschema genereert een reeks van 16 ronde sleutels, elk 48 bits lang, op basis van de oorspronkelijke 56-bits sleutel. Dit proces omvat gepermuteerde keuzeoperaties en linkse circulaire verschuivingen.
Principes van differentiële cryptoanalyse
Differentiële cryptanalyse omvat het bestuderen van hoe verschillen in leesbare tekstparen zich door het cijfer voortplanten om verschillen in de cijfertekst te produceren. Het basisidee is om paren leesbare teksten te selecteren die een specifiek verschil hebben, deze te coderen en de resulterende cijfertekstverschillen te analyseren. Door te observeren hoe deze verschillen evolueren tijdens de rondes van het cijfer, kan een aanvaller informatie over de sleutel afleiden.
Sleutelconcepten in differentiële cryptanalyse zijn onder meer:
- Differentieel: Het XOR-verschil tussen twee waarden. Bijvoorbeeld als 
en 
zijn twee leesbare teksten, hun verschil is 
.
- Kenmerk: Een reeks verschillen die beschrijft hoe een invoerverschil zich voortplant door de ronden van het cijfer.
- Waarschijnlijkheid: De waarschijnlijkheid dat een bepaald inputverschil na een bepaald aantal ronden een specifiek outputverschil zal opleveren.
Aanvraag bij DES
DES is specifiek ontworpen om weerstand te bieden aan differentiële cryptanalyse, die ten tijde van het ontwerp niet publiekelijk bekend was, maar wel werd begrepen door IBM en de NSA. De S-boxen in DES zijn zorgvuldig gekozen om de waarschijnlijkheid van verschillende kenmerken te minimaliseren, waardoor differentiële cryptanalyse moeilijker wordt.
Biham en Shamir hebben echter aangetoond dat DES niet immuun is voor differentiële cryptanalyse. Ze toonden aan dat, hoewel de DES met volledige 16 ronden bestand is tegen praktische differentiële aanvallen, versies met kleinere rondes van het cijfer kwetsbaar zijn. Concreet ontwikkelden ze aanvallen op DES met minder dan 16 ronden.
Een aanval op een DES met 8 ronden kan bijvoorbeeld worden uitgevoerd met een complexiteit van ongeveer 
gekozen leesbare teksten, wat aanzienlijk efficiënter is dan een brute-force aanval op de volledige sleutelruimte. Voor de volledige DES van 16 ronden is de complexiteit van differentiële cryptanalyse veel hoger, waardoor het onpraktisch wordt met de computerbronnen die beschikbaar waren op het moment van hun onderzoek.
Voorbeeld van differentiële cryptanalyse op DES
Om te illustreren hoe differentiële cryptanalyse werkt, overweeg een vereenvoudigd voorbeeld met een gereduceerde DES:
1. Kies een differentieel: Selecteer een specifiek ingangsverschil 
. Voor de eenvoud: neem aan heeft slechts invloed op een paar bits.
2. Genereer plattetekstparen: Genereer een groot aantal leesbare tekstparen 
zoals dat 
.
3. Versleutel plattetekstparen: Versleutel elk paar om cijferteksten te verkrijgen 
.
4. Analyseer outputverschillen: Bereken het uitgangsverschil 
voor elk paar.
5. Identificeer kenmerken: Identificeer patronen in de uitvoerverschillen die specifieke kenmerken van de interne structuur van het cijfer suggereren.
6. Belangrijke informatie afleiden: Gebruik de geïdentificeerde kenmerken om informatie af te leiden over de ronde sleutels en uiteindelijk de hoofdsleutel.
Praktische overwegingen
Hoewel differentiële cryptanalyse een krachtig hulpmiddel is, vereist de praktische toepassing ervan op DES aanzienlijke computerbronnen en een groot aantal gekozen leesbare teksten. Moderne cryptografische praktijken zijn geëvolueerd om complexere en veiligere algoritmen te gebruiken, zoals de Advanced Encryption Standard (AES), die zijn ontworpen om niet alleen differentiële cryptanalyse te weerstaan, maar ook een breed scala aan andere cryptanalytische aanvallen.
Differentiële cryptanalyse is een gevestigde techniek op het gebied van cryptografie die kan worden gebruikt voor het analyseren en, in sommige gevallen, breken van blokcijfers zoals DES. Hoewel de DES met volledige 16 ronden bestand is tegen praktische differentiële aanvallen, zijn versies van DES met beperkte rondes kwetsbaar. Het ontwerp van DES, met name de S-boxen, weerspiegelt een bewustzijn van de verschillende principes van cryptanalyse, wat het belang aantoont van een zorgvuldig cryptografisch ontwerp bij het waarborgen van de veiligheid.
Andere recente vragen en antwoorden over Data Encryption Standard (DES) - Sleutelschema en decodering:
- Tussen lineaire en differentiële cryptanalyse die efficiënt is voor het doorbreken van DES?
- Hoe kan lineaire cyrptanalyse een DES-cryptosysteem doorbreken?
- Kunnen twee verschillende inputs x1, x2 dezelfde output y produceren in Data Encryption Standard (DES)?
- Is differentiële cryptanalyse efficiënter dan lineaire cryptanalyse bij het doorbreken van het DES-cryptosysteem?
- Hoe diende DES als basis voor moderne versleutelingsalgoritmen?
- Waarom wordt de sleutellengte in DES volgens de huidige normen als relatief kort beschouwd?
- Wat is de netwerkstructuur van Feistel en hoe verhoudt deze zich tot DES?
- Hoe verschilt het decoderingsproces in DES van het coderingsproces?
- Wat is het doel van het sleutelschema in het DES-algoritme?
- Hoe draagt het begrijpen van het sleutelschema en het decoderingsproces van DES bij aan de studie van klassieke cryptografie en de evolutie van coderingsalgoritmen?
Bekijk meer vragen en antwoorden in Data Encryption Standard (DES) - Sleutelplanning en decodering