Premessa

I concetti di crittografia che sono implementati nel DES hanno radici che affondano indietro nel tempo. È noto da secoli che se si utilizzano algoritmi di sostituzione [1] per nascondere il significato di un testo, un attaccante che riceve un testo cifrato può studiare la frequenza dei simboli in esso presenti.

Infatti ogni linguaggio presenta frequenze statistiche costanti delle proprie lettere, o coppie di lettere, o triple, ... Nelle ipotesi che:

• sia stato cifrato un testo;
• sia conosciuta la lingua originale del testo in chiaro;
• il testo cifrato sia abbastanza lungo affiché i simboli in esso presenti abbiano rilevanza statistica;

un attaccante può fare delle ipotesi molto fondate su quale simbolo sostituisce cosa. Ricostruendo pian piano il testo in chiaro e, ancora peggio, ricostruendo la chiave utilizzata. Cosa che lo mette in grado di decifrare altri eventuali messaggi composti con l'uso della stessa chiave di cifratura.

Chi studia crittografia ha ben chiaro questo problema. Ad esempio L.S.Hill ha utilizzato il calcolo matriciale per disperdere le informazioni statistiche immerse nel testo da cifrare. È il metodo di cifratura di Hill cui ho accennato in quest'altro articolo.

Più in generale nel 1945 C.Shannon [2] pose le basi per un utilizzo di algoritmi di crittografia simmetrici in cui fossero presenti le proprietà di:

• diffusione, ovvero ogni singolo bit del testo cifrato deve dipendere statisticamente da più bit del testo da cifrare; in tal modo si alterano le frequenze di ricorrenza dei simboli tra testo in chiaro e testo cifrato;
• confusione, non deve essere possibile ricostruire la relazione tra il testo cifrato e la chiave di cifratura; ovvero la cifratura non deve avvenire con operazioni che ammettano una relazione inversa [3].

Nel 1973 H.Feistel e colleghi dell'IBM posero in essere le teorie di Shannon progettando Lucifer, un prodotto di crittografia di IBM.

Nel 1977 il lavoro di Feistel, leggermente modificato, fu accettato e pubblicato come standard ufficiale (FIPS) del National Institute of Standards and Technology (NIST) statunitense, con la denominazione Data Encription Standard [4]: la storia di DES era cominciata.

DES è stato superato nel 2005, quando è stato ufficialmente ritirato dal NIST. Fino a questa data, è stato di gran lunga lo standard di crittografia simmetrica più utilizzato. E anche il più attaccato. Già nel 1997 venne dimostrata pubblicamente una decrittazione, senza utilizzo della chiave, di un messaggio DES. Con il proseguire degli anni l'aumento della potenza di elaborazione dei computer e la sempre maggiore sofisticazione dei metodi di analisi, hanno portato al limite le capacità del DES, nonostante gli accorgimenti per renderlo più robusto (Triple DES). Tanto che nel 2001 NIST ha pubblicato il suo erede: lo Advanced Encryption Standard (AES), e, come detto, lo ha ritirato nel 2005.

Comunque va detto che il lavoro di Feistel è rimasto una pietra miliare, ed ha ispirato successivi algoritmi simili, quale ad esempio Blowfish, pubblicato nel 1993.

Osservazioni

L'algoritmo del DES è relativamente complesso.

Il testo Cryptography and Network Security di Behrouz A. Forouzan, al capitolo 6 [5] riporta una chiara descrizione del funzionamento di questo algoritmo.

La struttura generale è illustrata nella figura seguente.

Il testo da cifrare (plaintex 64 bit) subisce una permutazione iniziale e poi viene sottoposto per 16 volte al trattamento (round) descritto nella figura qui sotto.

In pratica la metà destra del testo viene combinato con la sottochiave Ki nella des function, il cui dettaglio è descritto nella figura precedente. Il risultato di questa operazione è messo in or esclusivo (xor) con la metà sinistra del testo entrante, per poi essere messo in uscita come metà destra. Mentre la metà sinistra del testo in uscita è una copia della metà destra del testo entrante.

Solo il round 16 fa eccezione, in quanto non avviene lo scambio finale tra le due metà di testo [6].

La generazione delle sottochiavi K1 ... K16 è un altro punto importante, ed ha la seguente logica.

Dalla chiave di 64 bit vengono eliminati i bit di parità (posizioni 8, 16, 24, ...). I 56 bit rimanenti sono la effettiva chiave da utilizzare per la cifratura. Questa viene divisa in due metà (28 bit ciascuna), e ad ogni fase di generazione di una sottochiave, le due metà vengono ruotate a sinistra di uno o due bit (dipende dal turno) e fatte confluire in un compressore che restituisce 48 bit: la sottochiave voluta.

Implementare questo algoritmo in Python è relativamente complesso. Il punto critico è la decisione di come implementare un array di bit. A prima vista il modo più semplice è l'uso dei bytearray: vettori di byte, ognuno formato da 8 bit. Solo che ci si scontra con le mezze chiavi di 28 bit, ovvero 3.5 byte.

Personalmente, per semplicità di lettura, e a scopo didattico, abbiamo preferito implementare una apposita classe di supporto, la NBitArray, che utilizza un bytearray come contenitore dei bit. Per documentazione, qui di seguito riportiamo le prime linee del modulo, che indica le principali operazioni disponibili:

# :filename: nbitarray.py         a naive buffer
#
# main methods:
#
#   import nbitarray as nba
#
#   ba = nba.NBitArray(list_of_hex)    # create instance
#   bb = nba.NBitArray(list_of_bits)   # create instance
#   len(ba)                    # number of bits
#   ba[ndx]                    # bit at index ndx
#   ba[ndx] = bit_as_integer   # set bit at index ndx
#   ba == bb                   # eq operator
#   str(ba)                    # string of bits
#   ba + bb                    # concatenation operator
#   ba ^ bb                    # xor operator (ba and bb of the same length)
#   ba << n                    # left shift, note: ba.__lshift__(n, circular=True) does a circular left shift
#   ba >> n                    # right shift, note: ba.__rshift__(n, circular=True) does a circular right shift
#   ba.get_byte(bit_ndx|byte_ndx=)  # return one byte as integer from indicated position
#   ba.set_byte(x, bit_ndx|byte_ndx=, lenght=)  # set x as one byte at indicated position for the indicated length in bits
#   ba.permutate(permutation_table)  # return a permutated NBitArray obeying to the given permutation table. ...
#                                    #  ... permutation table is a list of integers where index indicate the position of the output bit ...
#                                    #  ... and value at the index is the position of the input bit.
#   ba.bit_list()              # return the bit array content as a list of integers with values 0|1
#   ba.hex()                   # return the bit array content as a string of hex numbers
#   ba.swap_lr()               # return an NBitArray with left and right halves inverted. len(ba) must be even

Con una classe del genere le operazioni richieste sono semplici da effettuare. Ad esempio, questa:

import nbitarray as nba

#...<cut>...

class Key(object):
    #...<cut>...

    def __init__(self, key):
        self._key64  = nba.NBitArray(key)
        self._keys48 = self.calculate_keys()
        self._curr = -1

    def calculate_keys(self):
        '''calculate all 16 keys of 48 bits to use during rounds'''
        try:
            key56 = self.key_core     # drop parity bits and permutate
        except:
            raise ValueError('cannot calculate keys')
        result = []
        left  = key56[:len(key56)//2]
        right = key56[len(key56)//2:]
        for n in range(1, 17):          # rem.round is from 1 to 16 included
            if n in type(self)._one_key_shifting:
                left  = left.__lshift__(1, circular=True)
                right = right.__lshift__(1, circular=True)
            else:
                left  = left.__lshift__(2, circular=True)
                right = right.__lshift__(2, circular=True)
            tmp56 = left + right
            key48 = tmp56.permutate(type(self)._key_compression)
            result.append(key48)
        return result

    #...<cut>...

è la struttura di una classe che implementa il calcolo delle sottochiavi.

Quando si istanzia con una chiave di 64 bit, questa viene memorizzata in _key64, mentre in _keys48 vi è una lista con le 16 sottochiavi.

Le sottochiavi vengono calcolate dal metodo calculate_keys che scarta i bit di parità [7], spezza la cipher key in due parti uguali e poi cicla per 16 volte effettuando gli shift circolari necessari, ricombinando la chiave in tmp56 e comprimendola applicando la tabella di permutazione _key_compression, dando vita alla sottochiave key48 che viene poi aggiunta in lista.

Come si vede con una ventina di righe di codice si ottengono le sottochiavi da utilizzare per la cifratura DES. Va bè. Se vogliamo essere onesti fino in fondo, tutta la classe Key impegna una cinquantina di righe :-) Più di venti, ma comunque non sconvolgenti.

Tutto il modulo des.py, che implementa la cifratura e decifratura di un testo di 64 bit, è lungo circa 400 linee di codice, pesantemente commentato.

Mentre il modulo di supporto nbitarray.py è lungo meno di 300 linee.

Conclusioni e avvertimenti

Implementare il codice per la (de)cifratura DES aiuta grandemente a comprendere il dettaglio di come funziona. Non è impegno da poco, ma la soddisfazione, una volta finito, è proporzionale allo sforzo compiuto.

Qui spendo una parola di avvertimento riguardo i contenuti delle tabelle da utilizzare per effettuare le varie operazioni. Il DES è tutta una serie di permutazioni, eventualmente con espansione o con compressione dei bit in ingresso. Permutazioni che sono documentate tramite vettori numerici che mettono in corrispondenza il bit di uscita con quello di ingresso [8].

Mentre le S-Box, che qui non ho descritto, sono tabelle che mettono in relazione un sestetto di bit in ingresso con un quartetto di bit in uscita.

Bene. Sbagliare un valore in una di queste (tante) tabelle è veramente facile. Ed è decisamente costoso dare poi la caccia a questo tipo di errori, visto che noi programmatori tendiamo ad ipotizzare di avere sbagliato il codice, e non il dato. Non solo. Abbiamo trovato errori anche nelle tabelle del testo su indicato. Quindi, se vi volete cimentare in questa impresa attrezzatevi con un paio di strumenti indispensabili:

• il documento dello standard, in cui le tabelle sono corrette;
• un amico/parente dotato di molta pazienza, che entrerà in azione dopo che avrete scritto le varie tabelle; vi dovrà dettare i valori uno per uno per ricontrollarli.

Enjoy. ldfa