# 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 ; : tutto questo avvenne contro i voleri di Merkle . 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 è 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$^{43}$ testi in chiaro scelti e richiede un tempo di 2$^{43}$ (Gilbert e Chauvaud, 1994). Invece, per distinguere il cifrario da un flusso casuale di bit sono richiesti 2$^{32}$ testi in chiaro ed una complessità di 2$^{32}$. 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$^{18}$ 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 è 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$^{38}$ testi in chiaro noti. Similmente, 24 passaggi possono essere attaccati utilizzando 2$^{53}$ testi in chiaro scelti oppure 2$^{59}$ testi in chiaro noti.