FEAL

FEAL
La funzione Feistel del FEAL
Generale
Progettisti	Akihiro Shimizu e Shoji Miyaguchi (NTT)
Prima pubblicazione	FEAL-4 nel 1987, FEAL-N/NX nel 1990
Dettagli
Dimensione chiave	64 (FEAL) e 128 bit (FEAL-NX)
Dimensione blocco	64 bit
Struttura	rete di Feistel
Numero di passaggi	4, poi 8, poi variabili (raccomandati 32)
Migliore crittanalisi
È possibile violare il FEAL-4 con la crittanalisi lineare avendo a disposizione 5 testi in chiaro noti (Matsui e Yamagishi, 1992). Il FEAL-N/NX con meno di 31 passaggi può essere violato con la crittanalisi differenziale (Biham e Shamir, 1991).

In crittografia il FEAL (Fast data Encipherment ALgorithm) è un cifrario a blocchi proposto come sostituto del Data Encryption Standard (DES) e progettato per essere molto più veloce di questo nelle implementazioni software. Il cifrario, che si basa anch'esso su una rete di Feistel, fu pubblicato per la prima volta nel 1987 da Akihiro Shimizu e Shoji Miyaguchi della società di telecomunicazioni giapponese NTT. È sensibile a varie forme di crittanalisi ed ha svolto un ruolo fondamentale come banco di prova per la scoperta della crittanalisi differenziale e di quella lineare.

Versioni e vulnerabilità

Ci sono state diverse versioni del FEAL, ma tutte sono basate sulla rete di Feistel, fanno uso della stessa funzione interna ed operano su blocchi di dimensione di 64 bit. Una delle prime versioni del cifrario, nota oggi come FEAL-4, è basata su 4 passaggi della funzione interna ed opera con una lunghezza della chiave di 64 bit.

Sfortunatamente il FEAL-4 manifestò subito evidenti debolezze strutturali: Bert den Boer descrisse una vulnerabilità in un'inedita analisi alla stessa conferenza dove fu presentato il cifrario. In un documento del 1988 sempre den Boer descrive un attacco che richiede 100–10.000 testi in chiaro scelti mentre Sean Murphy, nel 1990, ne illustra una versione migliorata che richiede solo 20 testi in chiaro scelti. I metodi di attacco di den Boer e Murphy mostrano elementi simili a quelli usati dalla crittanalisi differenziale.

Gli sviluppatori corsero ai ripari pubblicando nel 1988 il FEAL-8, che presentava 8 passaggi della funzione interna. Ma anche il raddoppio dei passaggi si dimostrò insufficiente per rendere sicuro l'algoritmo: infatti, nel 1989, alla conferenza Securicom, Eli Biham e Adi Shamir descrissero un attacco differenziale contro il cifrario, menzionato da Miyaguchi nel 1989. Gilbert e Chassé, nel 1990, pubblicarono un attacco statistico subsequenziale simile alla crittanalisi differenziale che richiedeva 10.000 coppie di testo in chiaro scelto e testo cifrato.

In risposta a questi nuovi attacchi gli sviluppatori introdussero nel 1990 il FEAL-N, una versione del cifrario capace di operare con un numero variabile di passaggi dove "N" (indicante questo numero) era scelto dall'utente, ed il FEAL-NX, capace di gestire chiavi lunghe 128 bit. Ma la crittanalisi differenziale, ideata da Biham e Shamir, dimostrò nel 1991 che sia il FEAL-N che il FEAL-NX potevano essere violati molto più velocemente di una ricerca esaustiva della chiave comportasse per N ≤ 31. Tardy-Corfdir e Gilbert nel 1991 e poi Matsui e Yamagishi nel 1992 dimostrarono, con una serie di attacchi, precursori della crittanalisi lineare, che si potevano violare i cifrari utilizzando metodologie basate sull'uso di testi in chiaro noti: gli attacchi di Matsui e Yamagishi violavano il FEAL-4 utilizzando solo 4 testi in chiaro noti, il FEAL-6 con 100 di questi testi ed il FEAL-8 con 2¹⁵ testi.

Voci correlate

• N-Hash
• Rete di Feistel
• Data Encryption Standard
• Crittanalisi lineare
• Crittanalisi differenziale

Bibliografia

• Eli Biham, Adi Shamir: Differential Cryptanalysis of Feal and N-Hash - EUROCRYPT 1991, pagg. 1–16
• Bert den Boer: Cryptanalysis of F.E.A.L. - EUROCRYPT 1988, pagg. 293–299
• Henri Gilbert, Guy Chassé: A Statistical Attack of the FEAL-8 Cryptosystem - CRYPTO 1990, pagg. 22–33.
• Shoji Miyaguchi: The FEAL Cipher Family - CRYPTO 1990, pagg. 627–638
• Shoji Miyaguchi: The FEAL-8 Cryptosystem and a Call for Attack - CRYPTO 1989, pagg. 624–627
• Mitsuru Matsui, Atsuhiro Yamagishi: A New Method for Known Plaintext Attack of FEAL Cipher - EUROCRYPT 1992, pagg. 81–91
• Sean Murphy: The Cryptanalysis of FEAL-4 with 20 Chosen Plaintexts - J. Cryptology 2(3), pagg. 145–154 (1990)
• A. Shimizu, S. Miyaguchi: Fast data encipherment algorithm FEAL - Advances in Cryptology — Eurocrypt '87, Springer-Verlag (1988), pagg. 267–280.
• Anne Tardy-Corfdir, Henri Gilbert: A Known Plaintext Attack of FEAL-4 and FEAL-6 - CRYPTO 1991, pagg. 172–181

Collegamenti esterni

• Homepage del FEAL, su info.isl.ntt.co.jp.
• Articolo su sci.crypt di Peter Gutmann che descrive il FEAL, su groups.google.com.
• Brevetto USA 4850019, su patft.uspto.gov. URL consultato il 5 giugno 2009 (archiviato dall'url originale il 9 aprile 2016).