Lucifer (xifratge)
Lucifer és una família d'algorismes de xifratge per blocs desenvolupats per Horst Feistel i els seus col·legues d'IBM. Es tracta d'un dels primers mètodes de xifratge modern destinat a un ús civil. Lucifer va ser el precursor directe de DES. Una de les versions DTD-1, es va fer servir per a banca electrònica durant els anys 70.
| Lucifer | |
|---|---|
| General | |
| Dissenyadors | Horst Feistel, IBM |
| Data primera publicació | 1971 |
| Desenvolupat a partir de | Cap |
| Successors | DES |
| Detall de xifratge | |
| Mida de la clau | 48, 64, 128 bits |
| Mida del bloc | 32, 48, 128 bits |
| Estructura | fa servir caixes S i una xarxa de Feistel |
| Rondes | 16 (per a la versió a 128 bits) |
| Millor criptoanàlisi pública | |
Una altra variant, descrita a la patent (US Patent 3,798,359; Juny 1971), fa servir un bloc de 48 bits. El xifratge es fa via una xarxa de permutacions i de substitucions. Es fan servir dues taules de substitucions, de les caixes S de 4 bits. La clau determina la taula que es fa servir per a la substitució i la patent descriu l'execució del xifratge sobre 24 bits a la vegada, així com una versió seqüencial que treballa per llesques de 8 bits.
En una altra patent (US Patent 3,796,830; Novembre 1971), Lucifer es presenta sota la forma d'un bloc de 32 bits xiftat amb una clau de 64 bits. L'arquitectura del xifratge es basa en una addició mòdul 4 i una sola taula de substitució de 4 bits. L'algorisme està dissenyat per operar sobre 4 bits per cada tic de rellotge. Es tracta probablement del xifratge per bloc més senzill i més reduït mai dissenyat.
Una variant més robusta, descrita per Feistel el 1973, fa servir una clau de 128 bits i treballa sobre un bloc de la mateixa mida. Es tracta aquí d'una sèrie de permutacions i de substitucions amb dos caixes S de 4 bits lús de les quals depèn de la clau. Més tard, el 1984 Sorkin va aoportar una modificació que va publicar. Aquest Lucifer estava construït al voltant d'una xarxa de Feistel de 16 torres amb un bloc de 128 bits. La clau era sempre de 128 bits però malgrat aquesta mida d'un conservadorisme destacable per a l'època, aquesta versió va ser trencada des de l'aparició del criptoanàlisi diferencial. Per a aproximadament la meitat de les claus, és possible forjar tal atac amb aproximadament 236 texts clars escollits pel criptoanalista. La complexitat en temps és de 236 (resultats de Ben-Aroya i Eli Biham el 1996).
AES). Després de diverses modificacions entre les quals una reducció de la mida de la clau en 56 bits i un bloc més curt (64 bits), aquest Lucifer refett va esdevenir el nou estàndard de xifratge el 1977. Llavors es va demostrar que l'algorisme havia estat millorat des del punt de vista criptogràfic limitant-se les possibilitats d'atacs diferencials. L'equip d'IBM havia descobert en efecte el precursor de l'atac diferencial (l'atac-T) i havia reforçat DES.
Descripció de la variant de Sorkin
modificaEl 1984, Arthur Sorkin descriu una versió basada en una xarxa de Feistel amb 16 rondes, com DES, però sense les permutacions inicials i finals. La clau i el bloc són de 128 bits. La funció de Feistel treballa sobre trossos de 64 bits (el bloc s'escindeix en dues parts) amb una clau de cada ronda de 64 bits i 8 bits anomenats ICB (interchange control bits). Aquests bits controlen de fet de les operacions de permutació.
El bloc de 64 bits es considera com una sèrie de 8 octets i si els ICB que corresponen a un octet particular són nuls, llavors l'octet es talla en dos i els 4 bits s'intercanvien. Altrament, l'octet continua intacte. Llavors cada octet s'introdueix en dos caixes S que treballa cadascuna sobre una meitat de l'octet. Les sortides de les taules es concatenen i es combinen amb una clau intermediària fent servir un XOR (key interruption). Segueix una permutació en dues etapes, la primera fa una permutació constant de l'octet mentre que la segona barreja els bits entre diversos octets.
La creació de les claus intermediàries és relativament senzilla. La clau de 128 bits es carrega en un registre a decalatge. A cada volta, els 64 primers bits del registre formen la clau intermediària i els 8 últims bits formen els ICB. Després de cada volta, el registre experimenta una rotació de 56 bits cap a l'esquerra.
Anècdota
modificaEl nom de «Lucifer» provindria de « Demon » que s'obté truncant « Demonstration » el nom del sistema sobre el qual treballava Feistel. El sistema operatiu no podia manejar noms tan llargs, d'aquí «Demon» que va ser transformat en « Lucifer ».
Referències
modifica- Horst Feistel. Block Cipher Cryptographic System, US Patent 3,798,359. Filed June 30, 1971. (IBM)
- John Lynn Smith. Recirculating Block Cipher Cryptographic System, US Patent 3,796,830. Filed Nov 2, 1971. (IBM)
- Horst Feistel, (1973). Cryptography and Computer Privacy". Scientific American, 228(5), May 1973, pàg. 15-23.
- A. Sorkin, (1984). LUCIFER: a cryptographic algorithm. Cryptologia, 8(1), 22--35, 1984.
- Eli Biham, Adi Shamir (1991). Differential Cryptanalysis of Snefru, Khafre, REDOC-II, LOKI and Lucifer. CRYPTO 1991: pp156–171
- Ishai Ben-Aroya, Eli Biham (1996). Differential Cryptanalysis of Lucifer. Journal of Cryptology 9(1), pp. 21–34, 1996.
- Whitfield Diffie, Susan Landau (1998). Privacy on the Line: The Politics of Wiretapping and Encryption.
- Stephen Levy. (2001). Crypto: Secrecy and Privacy in the New Code War (Penguin Press Science).