Khufu e Khafre

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) US5003597, United States Patent and Trademark Office, Stati Uniti d'America., depositato il 26 marzo 1991).

Khufu

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 2⁴³ testi in chiaro scelti e richiede un tempo di 2⁴³ (Gilbert e Chauvaud, 1994). Invece, per distinguere il cifrario da un flusso casuale di bit sono richiesti 2³² testi in chiaro ed una complessità di 2³². Un attacco a boomerang (Wagner, 1999) può essere utilizzato in una situazione di attacco adattivo con testo in chiaro scelto/testo cifrato scelto con 2¹⁸ 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 reti di Feistel incomplete, non bilanciate, pesantemente mirate all'eterogenità.

Khafre

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, che non calcola dalla chiave ma genera 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 utilizzate 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 in maniera molto rapida piccoli quantitativi di dati. 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 modificate 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 2³⁸ testi in chiaro noti. Similmente, 24 passaggi possono essere attaccati utilizzando 2⁵³ testi in chiaro scelti oppure 2⁵⁹ testi in chiaro noti.

Bibliografia

• R.C. Merkle: Fast Software Encryption Functions - CRYPTO 1990
• Eli Biham, Adi Shamir: Differential Cryptanalysis of Snefru, Khafre, REDOC-II, LOKI and Lucifer - CRYPTO 1991
• Henri Gilbert, Pascal Chauvaud: A Chosen Plaintext Attack of the 16-round Khufu Cryptosystem - CRYPTO 1994
• Bruce Schneier, John Kelsey: Unbalanced Feistel Networks and Block Cipher Design - Fast Software Encryption 1996
• Eli Biham, Alex Biryukov, Adi Shamir: Miss in the Middle Attacks on IDEA, Khufu and Khafre - Fast Software Encryption 1999
• David Wagner: The Boomerang Attack - Fast Software Encryption 1999