Khufu e Khafre

Da Wikipedia, l'enciclopedia libera.

In crittografia Khufu e Khafre sono due cifrari a blocchi sviluppati da Ralph Merkle nel 1989 durante il periodo in cui lavorava per Xerox al Palo Alto Research Center. Come Snefru, una funzione di hash, i cifrari furono denominati con i nomi (in lingua inglese) dei faraoni egizi Cheope (Khufu), Chefren (Khafre) e Snefru.

Prima della pubblicazione, Xerox propose volontariamente gli algoritmi Khufu e Khafre al vaglio dell'agenzia NSA, che ne bloccò la pubblicazione per motivi di sicurezza nazionale (vedi esportazione di crittografia). Xerox, che aveva diversi appalti governativi, accondiscese alla richiesta. I documenti furono però copiati da un revisore, che li passò all'attivista John Gilmore, che a sua volta li distribuì sul newsgroup sci.crypt [1]; [2]: tutto questo avvenne contro i voleri di Merkle [3]. Gli schemi furono poi resi pubblici alla conferenza CRYPTO del 1990.

Khufu e Khafre sono brevettati da Xerox (brevetto (EN) United States Patent 5003597, United States Patent and Trademark Office., depositato il 26 marzo 1991).

Khufu[modifica | modifica wikitesto]

Khufu
Generale
Progettisti Ralph Merkle
Prima pubblicazione 1989
Dettagli
Dimensione chiave 512 bit
Dimensione blocco 64 bit
Struttura Rete di Feistel
Numero di passaggi da 8 a 64 (normalmente 16)
Migliore crittanalisi
Attacco differenziale di Gilbert e Chauvaud

Khufu è un cifrario a blocchi che opera su blocchi di 64 bit con una chiave insolitamente grande: 512 bit (in genere i cifrari a blocchi utilizzano chiavi più piccole, difficilmente eccedenti i 256 bit). Molto del materiale della chiave è utilizzato per costruire le S-box del cifrario: a causa del fatto che il tempo impiegato per questo processo è abbastanza elevato, l'uso dell'algoritmo non è consigliato nelle situazioni in cui devono essere gestiti molti messaggi di piccole dimensioni ma è più consigliato per la cifratura di grandi quantitativi di dati.

Il Khufu è un cifrario di Feistel che normalmente esegue 16 passaggi (anche se sono permessi tutti i valori compresi fra 8 e 64 con incrementi di 8), divisi in blocchi di 8: ogni gruppo di 8 passaggi è definito ottetto, e per ogni ottetto viene impiegata una S-box differente. In un passaggio, il byte meno significativo di metà di un blocco è inserito in una S-box (di 8x32 bit): l'output dell'S-box è poi combinato con uno XOR con l'altra metà del blocco. La metà di sinistra è poi ruotata per portare un nuovo byte in posizione ed infine le metà sono invertite. All'inizio ed alla fine dell'algoritmo del materiale aggiuntivo della chiave viene combinato mediante XOR con il blocco (key whitening). Il restante materiale della chiave è, come detto, contenuto nelle S-box.

C'è un attacco differenziale su 16 passaggi del Khufu che può recuperare la chiave segreta: necessita di 243 testi in chiaro scelti e richiede un tempo di 243 (Gilbert e Chauvaud, 1994). Invece, per distinguere il cifrario da un flusso casuale di bit sono richiesti 232 testi in chiaro ed una complessità di 232. Un attacco a boomerang ((Wagner, 1999) può essere utilizzato in una situazione di attacco adattivo con testo in chiaro scelto/testo cifrato scelto con 218 cifrature ed una complessità simile. Khufu è anche vulnerabile ad un attacco differenziale impossibile, che può violare fino a 18 passaggi del cifrario (Biham ed altri aa., 1999).

Schneier e Kelsey (1996) hanno definito i due algoritmi come incomplete reti di Feistel non bilanciate pesantemente mirate all'eterogenità.

Khafre[modifica | modifica wikitesto]

Khafre
Generale
Progettisti Ralph Merkle
Prima pubblicazione 1989
Dettagli
Dimensione chiave 512 bit
Dimensione blocco 64 bit
Struttura Rete di Feistel
Numero di passaggi ≥16
Migliore crittanalisi
Fino a 18 passaggi, un attacco differenziale è più veloce di un attacco a forza bruta (Biham e Shamir)

Khafre è simile a Khufu ma usa un insieme regolare di S-box, senza calcolarle dalla chiave ma generandole dalle tabelle RAND pubblicate nel 1955 con il titolo A Million Random Digits with 100,000 Normal Deviates, che raccoglie un milione di cifre casuali e centomila deviazioni, ampiamente utilizzato ai tempi in cui la potenza di calcolo degli elaboratori non era certo quella di oggi. L'avere S-box precalcolate permette, rispetto al Khufu, di cifrare piccoli quantitativi di dati in maniera molto rapida. D'altro canto, il Khafre richiede un più elevato numero di passaggi per ottenere gli stessi livelli di sicurezza del Khufu, rendendolo più lento nella cifratura di grandi quantitativi di dati.

L'algoritmo usa una chiave la cui dimensione è un multiplo di 64. Siccome le S-box non dipendono dalla chiave, il Khafre gestisce delle sotto-chiavi che sono mdoficate mediante operazioni di XOR ogni 8 passaggi.

La crittanalisi differenziale è molto efficiente contro il Khafre: 16 passaggi possono essere violati utilizzando sia 1.500 testi in chiaro scelti che 238 testi in chiaro noti. Similmente, 24 passaggi possono essere attaccati utilizzando 253 testi in chiaro scelti oppure 259 testi in chiaro noti.

Bibliografia[modifica | modifica wikitesto]