DES, acronimo di Data Encryption Standard, è l’algoritmo di cifratura scelto come standard dal Governo statunitense nel 1976 e poi adottato da molti altri governi del mondo. DES è stato utilizzato come standard crittografico per i documenti non segreti fino al 1998 quando fu rimpiazzato dall’algoritmo AES (Advanced Encryption Standard), considerato più sicuro.

Storia di DES

Agli inizi degli anni ’70, l’allora NBS ora noto come NIST (l’ente americano incaricato della gestione degli standard tecnologici) decise che era arrivato il momento di definire uno standard per la protezione dei documenti non classificati, in modo da garantire un livello minimo di sicurezza nella comunicazione tra i vari dipartimenti. Nel 1974 fu creato un bando pubblico, alla quale tutti gli sviluppatori poterono presentare i propri algoritmi crittografici. Gli algoritmi furono testati da un comitato e in parallelo dal NSA (National Security Agency), l’agenzia per la sicurezza nazionale degli Stati Uniti.

In seguito alla conclusione della gara e trascorso il periodo di test da parte delle varie organizzazioni, l’IBM si aggiudicò il bando grazie al suo algoritmo crittografico DEA, poi rinominato DES. Nonostante la vittoria ottenuta la National Security Agency consigliò ad IBM di modificare le S-BOX usate in DES (le funzioni non lineari che rendono l’algoritmo non invertibile) prima di consegnare il critto-sistema al governo americano e agli altri utenti. Le nuove S-BOX non furono però scelte da IBM bensì dall’NSA stessa.

<< …noi inviammo le S-BOX a Washington. Tornarono indietro completamente differenti >>
Progettisti di DES

In seguito, DES divenne prima lo standard del Governo americano (nel 1976) e in seguito standard globale. A causa dell’intervento dell’NSA numerose persone iniziarono a sostenere che l’agenzia avesse volontariamente creato delle S-BOX deboli, così da poter essere la sola in grado di decodificare (forzatamente) i messaggi cifrati. Le S-BOX di DES furono definite “oscurate”, malgrado esse fossero visibili non ne erano note le funzioni generatrici. Dopo che queste funzioni furono finalmente rese pubbliche (negli anni ’90) si scoprì che DES era effettivamente sensibile ad un attacco basato sulla crittoanalisi differenziale. Si fece così strada l’ipotesi che l’agenzia avesse effettivamente inserito una backdoor in DES. Per questo motivo al bando successivo, tenutosi nella metà degli anni ’90 e voluto proprio dal NIST per rimpiazzare l’algoritmo DES, i singoli sviluppatori resero da subito pubbliche le funzioni delle varie S-BOX.

Pro e contro

Analizziamo i principali punti di forza e le debolezze dell’algoritmo crittografico DES.
Vantaggi:

  • DES è un algoritmo veloce e in grado di funzionare efficacemente anche su hardware datato;
  • È in grado di operare su sistemi a 6 bit;
  • Era considerato sufficientemente sicuro.

Svantaggi:

  • Aveva una chiave molto corta, composta da soli 56 bit;
  • Fu (probabilmente) manomesso dall’NSA.

Funzionamento

DES utilizza una chiave di cifratura a 64 bit, 8 di questi bit sono però usati per i controlli di parità e non influenzano la cifratura del messaggio. La chiave è quindi di fatto lunga solamente 56 bit, troppo pochi per un odierno sistema di cifratura. Il sistema è basato su cicli di 16 round, ma siccome ad ogni round viene cifrato solo metà del testo, il testo viene realmente cifrato solo 8 volte.

Di seguito analizziamo il funzionamento di DES attraverso alcuni schemi, il primo mostra il funzionamento generale dell’algoritmo:

  1. Il plaintext di 64 bit viene suddiviso in due blocchi.
  2. La permutazione iniziale si basa su una tabella di sostituzione dei bit. Ad esempio, il bit 1 viene sostituito dal bit 58. Questo garantiva il caricamento veloce dei cip e proteggeva da alcuni attacchi minori;
  3. I due blocchi risultati dalla permutazione iniziale (32 bit) vengono codificati indipendentemente ad ogni round mediante la funzione Feistel. La funzione Feistel mescola una metà del blocco r_n con una parte della chiave k_n . I due blocchi sono poi uniti tramite un OR esclusivo (XOR) per formare una rete di Feistel. La chiave k_0 viene generata dalla chiave iniziale (da cui vengono esclusi i bit di parità). Le chiavi successive dipendono tutte dalla prima;
  4. L’operazione viene ripetuta per 16 round. In questo modo ogni blocco del plaintext viene codificato 8 volte;
  5. La permutazione finale serve per annullare il lavoro svolto dalla permutazione iniziale.
critto4

Il secondo schema descrive il funzionamento della funzione Feistel:

  1. Alla funzione Feistel vengono inviati i 32 bit proveniente dal blocco destro;
  2. Il blocco viene espanso fino a 48 bit. Questo risultato viene ottenuto duplicando alcuni bit in posizioni note. Esempio: Il 4° bit viene duplicato in posizione 5 e 7.
  3. Il risultato dell’espansione viene combinato tramite OR esclusivo (XOR) con una delle sottochiave k_n ottenute dal Gestore delle Chiavi. Successivamente il blocco viene diviso in otto parti da 6 bit e ogni parte viene inviata ad una S-BOX differente. Ogni S-BOX accetta in input 6 bit e restituisce in output 4 bit generati mediante una funzione non lineare ottenuta da una matrice 6×4;
  4. Infine i 32 bit (4 bit da 8 S-BOX) vengono riordinati e permutati.
critto4

Vediamo infine il funzionamento del gestore delle chiavi:

  1. Dalla chiave di 64 bit vengono sottratti 8 bit (1 bit ogni 8) e vengono svolti i controlli di parità;
  2. Successivamente i bit vengono permutati tramite una funzione simile alla permutazione iniziale (si faccia riferimento al primo schema). I 56 bit vengono poi divisi in due blocchi da 28 bit;
  3. I due blocchi da 28 bit vengono poi shiftati di una lunghezza variabile: 1 bit per i round 1, 2, 9, 16 e due bit per gli altri round. Vengono poi scelti 24 bit da ogni blocco (48 bit in totale), questi bit verranno permutati e usati per generale la chiave k_n . Contemporaneamente i due blocchi da 28 bit sono portati avanti e usati per la generazione della chiave successiva k_{n+1} ;
  4. Nei passaggi successivi non saranno più necessari controlli di parità.
critto4