DES-design och Lucifer-chiffret

År 1971 utvecklade Horst Feistel vid IBM Research ett chiffer kallat Lucifer som en del av ett projekt för banksäkerhet hos Lloyd's of London. Lucifer var ett av de första moderna blockchiffrerna och använde en 128-bitars nyckel och 128-bitars block.

Lucifer visade att ett starkt blockchiffer kunde byggas med Feistelstrukturen: växlande omgångar av substitution och permutation som tillämpas på halvblock. Det var den direkta föregångaren till DES.

DES tillämpar Feistelstrukturen i 16 omgångar på 64-bitarsblock. I varje omgång delas 64-bitarsblocket upp i två halvor på 32 bitar. Den högra halvan expanderas till 48 bitar, XOR:as med en 48-bitars delnyckel, skickas genom S-boxar, permuteras och XOR:as med den vänstra halvan.

Halvorna byter sedan plats och processen upprepas. Efter 16 omgångar producerar en slutlig permutation chiffertexten på 64 bitar. Dekryptering använder samma struktur med delnycklarna i omvänd ordning.

DES krypterar data i block om 64 bitar (8 byte). Den fasta blockstorleken var lämplig för maskinvara från 1977 men har blivit ett säkerhetsproblem. När tillräckligt mycket data används blir kollisioner enligt födelsedagsparadoxen sannolika.

Vid block på 64 bitar börjar statistiska mönster uppträda efter ungefär 2^32 block (~32 GB data som krypterats med samma nyckel). Denna Sweet32-attack gjorde 3DES osäkert för trafikvolymer som vid HTTPS.

DES använder en nyckel på 64 bitar, men 8 av bitarna är paritetsbitar som används för feldetektering och inte för kryptering. Den effektiva nyckellängden är därför bara 56 bitar.

Det innebär att det bara finns 2^56 (cirka 72 biljarder) möjliga DES-nycklar. Enligt 1977 års standard ansågs detta vara tillräckligt. År 1997 kunde en målmedveten angripare bevisligen knäcka det.

DES börjar med en initial permutation (IP) som omarrangerar de 64 bitarna i klartextblocket och avslutas med en slutlig permutation (IP^-1) som är den exakta inversen. Dessa permutationer tillför ingen kryptografisk styrka.

De utformades för effektiv maskinvarubearbetning på specifika chiparkitekturer från 1970-talet, vilket möjliggjorde snabbare inläsning av bitar i register. Modern analys bekräftar att de inte bidrar till säkerheten.

De åtta S-boxarna (substitutionsboxarna) utgör kärnan i DES:s ickelinjäritet. Varje S-box tar emot 6 bitars indata och producerar 4 bitars utdata med hjälp av en fast uppslagstabell. De yttersta 2 bitarna väljer raden och de inre 4 bitarna väljer kolumnen.

Utan den ickelinjäritet som S-boxarna ger skulle DES vara ett rent linjärt chiffer som linjär algebra enkelt kunde knäcka. Den specifika utformningen av DES:s S-boxar står emot differentialkryptanalys.

Efter S-boxarna tillämpar DES en P-box-permutation som omarrangerar de 32 utbitarna från S-boxarna. Detta ger diffusion genom att sprida utsignalen från varje S-box så att flera S-boxar påverkas i nästa omgång.

P-boxen utformades noggrant för att maximera diffusionen: varje utbit från en S-box påverkar minst två olika S-boxar i nästa omgång, vilket säkerställer en snabb lavineffekt.

DES härleder 16 olika delnycklar på 48 bitar från huvudnyckeln på 56 bitar, en för varje runda. Nyckelschemat börjar med att tillämpa en permuted choice (PC-1) för att ta bort paritetsbitar och ordna om nyckelns bitar.

De 56 bitarna delas upp i två halvor på 28 bitar, som roteras åt vänster med 1 eller 2 positioner i varje runda. Därefter väljer en permuted choice (PC-2) ut 48 av de 56 bitarna för att bilda delnyckeln för varje runda.

NSA samarbetade med IBM under utvecklingen av DES och minskade nyckellängden från Lucifers 128 bitar till 56 bitar samt ändrade S-boxarnas utformning. Detta utlöste årtionden av kontroverser kring huruvida bakdörrar hade införts.

På 1990-talet bekräftade NSA-tjänstemän att de hade förstärkt S-boxarna mot differentiell kryptoanalys, en teknik som IBM upptäckte 1974. NSA hade känt till differentiell kryptoanalys i flera år innan den blev känd inom akademin, vilket tyder på att myndigheten gjorde DES mer motståndskraftigt, inte svagare.

DES antogs som Federal Information Processing Standard 46 i januari 1977 efter en konkurrensutsatt utvärderingsprocess. Det blev standardchiffret för icke-sekretessbelagda myndighetsdata och antogs i stor utsträckning av banker och industrin.

Standardiseringen av DES var historiskt betydelsefull: det var den första offentligt tillgängliga, myndighetsstödda kryptografiska algoritmen. Den drev utvecklingen av hårdvaruimplementationer och etablerade en förebild för framtida standardiseringsprocesser för chiffer.

DES är i sig ett blockchiffer som krypterar exakt 64 bitar åt gången. Verkliga meddelanden är längre, så driftlägen definierar hur chiffret ska tillämpas på flera block. Vanliga lägen är ECB (kryptera varje block separat), CBC (XOR:a varje block med föregående chiffertext före krypteringen), CFB, OFB och CTR.

ECB är det svagaste läget: identiska klartextblock ger identiska chiffertextblock, vilket skapar synliga mönster. CBC- och CTR-lägena eliminerar denna svaghet och föredras vid praktisk användning av DES och 3DES.

DES utvecklades från IBMs Lucifer-chiffer till ett Feistel-chiffer med 16 rundor, block på 64 bitar och en effektiv nyckellängd på 56 bitar. Säkerheten bygger på 8 icke-linjära S-boxar som ger konfusion, P-boxen som ger diffusion samt 16 rundor som förstärker lavineffekten.

NSA:s medverkan i utformningen av S-boxarna var kontroversiell men förbättrade i slutändan motståndskraften mot differentiell kryptoanalys. DES-nyckeln på 56 bitar, som utformats för 1977 års hårdvara, visade sig vara otillräcklig i slutet av 1990-talet.