Blowfish

De Viquipèdia
Dreceres ràpides: navegació, cerca
Blowfish
La funció rodona (Funció Feistel) de Blowfish

La funció rodona (Funció Feistel) de Blowfish
General
Dissenyadors Bruce Schneier
Data primera publicació 1993
Successors Twofish
Detall de xifratge
Mida de la clau 32-448 bits en passos de 8 bits; per omissió 128 bits
Mida del bloc 64
Estructura Xarxa Feistel
Rondes 16
Millor criptoanàlisi pública
Quatre rondes de Blowfish són susceptibles d'un atac diferencial de segon ordre (Rijmen, 1997); per a una classe de claus fbles, 14 rondes de Blowfish es poden distingir amb una permutació pseudoaleatòria (Vaudenay, 1996).


Blowfish és un sistema de xifratge per blocs de clau, simètrica, dissenyat el 1993 per Bruce Schneier i s'inclou en un gran nombre de paquets de xifratge i productes d'encriptació. Blowfish proporciona un bon ritme d'encriptació en el programari i no s'ha trobat cap criptoanàlisi eficient fins a la data (2010). Tanmateix, en l'actualitat es presta més atenció al sistema AES.

Schneier va dissenyar Blowfish com un algorisme d'ús general, amb la intenció de ser un substitut per al DES i lliure dels problemes i restriccions associades a altres algorismes. A l'època en que va sortir Blowfish, molts altres dissenys estaven patentats, eren sistemes propietaris o eren els secrets de comercials o governamentals. Schneier ha manifestat que, "Blowfish està sense patentar, i romandrà així a tots els països. L'algorisme es posa d'ara endavant en domini públic, i el pot fer servir lliurement tothom."

Els trets notables del disseny inclouen Caixes-S dependents de la clau i una programació de claus altament complexa.

L'algorisme[modifica | modifica el codi]

Blowfish té una longitud de bloc de 64 bits i una mida de clau variable des de 32 fins a 448 bits.[1] És un xifratge per xarxa de Feistel de 16 rondes i fa servir claus dependents de les Caixes-S. És similar en estructura a CAST5, que fa servir caixes-S fixes.

L'estructura Feistel de Blowfish

El diagrama de l'esquerra mostra l'actiació de Blowfish. Cada línia representa 32 bits. L'algorisme conserva dues taules de subclaus: la taula-P de 18 entres i quatre caixes-S de 256 entrades. Les caixes-S accepten entrades de 8 bits o donen 32 bits a la sortida. A cada ronda es fa servir una entrada de la taula-P, i un altre després de la ronda final, cada meitat del bloc de dades es combina amb una operació XOR amb una de les dues entrades-P restants encara no fetes servir.

El diagrama de dalt a la dreta presenta le funció F de Blowfish. La funció parteix l'entrada de 32 bits en quatre quartes parts de vuit bits cada una, i fa servir les parts com entrada a les caixes-S. Les sortides se sumen mòdul 232 i es combinen amb una operació XOR per obtenir la sortida final de 32 bits.

El desxifratge és exactament igual com el xifratge, excepte que P1, P2..., P18 es fan servir en l'ordre invers. Això no és tan obvi perquè l'operació XOR és commutativa i associativa. Un error habitual és fer servir l'ordre invers del xifratge com algorisme de desxifratge (i.e. primer combinant amb l'operació XOR P17 i P18 amb el bloc de text xifrat, llavors fent servir les entrades P en ordre invers).

La programació de claus de Blowfish comença inicialitzant la taula P i les caixes S amb valors obtinguts a partir dels dígits hexadecimals de pi, que no conté cap patró obvi. La clau secreta llavors es combina amb una operació XOR amb les entrades P en ordre (reciclant la clau si és necessari). Per tant un bloc amb tots els 64 bits a zero és encriptat amb l'algorisme tal qual. El text xifrat resultant substitueix P1 i P2. El text xifrat s'encripta llavors una altra vegada amb les subclaus noves, i P3 i P4 es canvien pel text xifrat nou. Això continua, substituint la taula P sencera i totes les entrades de les caixes S. En total, l'algorisme d'encriptació Blowfish s'executarà 521 vegades per generar totes les subclaus - es processen al voltant de 4 Kb de dades.

Criptoanàlisis de Blowfish[modifica | modifica el codi]

No hi ha cap cryptoanàlisis eficaç conegut públicament contra la versió de ronda completa de Blowfish. S'ha identificat un error d'extensió de senyal en una publicació de codi C.[2]

El 1996, Serge vaudenay va trobar un atac de texts clars coneguts que requereix 28r+ 1 texts clars coneguts per trencar-lo, on r és el nombre de rondes. A més, també trobava una classe de claus febles que es poden detectar i ser trencades pel mateix atac amb només 24r + 1 texts clars coneguts. Aquest atac no es pot fer servir contra el Blowfish normal; assumeix el coneixement de les caixes S dependents de la clau. Vincent Rijmen, a la seva tesi doctoral introduïa un atac diferencial de segon ordre que pot trencar quatre rondes però no més. Roman desconeguda la manera de trencar les 16 rondes completes, a part d'un atac per la força bruta.[3]

Bruce Schneier observa que mentre Blowfish és encara en ús, recomana fer servir en canvi l'algorisme Twofish més recent.[4]

Blowfish en la pràctica[modifica | modifica el codi]

Blowfish és un sistema de xifratge per blocs ràpid, excepte quan es canvien les claus. Cada clau nova exigeix un preprocessament equivalent a encriptar aproximadament 4 kilobytes de text, que és molt lent comparat amb altres xifratges de bloc. Això evita el seu ús en certes aplicacions, però no és un problema en altres. En una aplicació, és de fet un benefici: el mètode de hashing de contrasenya que fa servir OpenBSD fa servir un algorisme obtingut de Blowfish que fa ús de la lentitud de la programació de claus; la idea és que l'esforç computacional extraordinari que exigeix dóna protecció contra atacs de diccionari.

En aplicacions actuals de biblioteques criptogràfiques (específicament OpenSSL), Aes-128 és una mica (< 50%) més ràpid que Blowfish en molts maquinaris.[5] És probable que els avenços en l'arquitectura CPU (d'execució fora d'ordre) accelerin AES més que Blowfish. Per exemple, la CPU Àtom de Intel corre Blowfish dues vegades més ràpid que AES-128.[6] Hi pot haver espai per a més optimització de Blowfish, però el Rijndael ha rebut més atenció des que es triava per a AES.

Està estesa la creença que Blowfish sigui l'algorisme més ràpid, encara que actualment no és veritat en maquinari de Pc. Roman el cas en algunes Cpus incrustades (p. ex. Àtom, ARM[7] La velocitat d'encriptació es té amb possibilitats de ser un coll d'ampolla en aquests sistemes més lents, així Blowfish és naturalment útil ells. Tanmateix, algunes plataformes aquestes CPUs lentes proporcionen maquinari de criptografia dedicat, alguns dels quals només suporten els algorismes més populars (i.e. AES).

Blowfish té una petjada de memòria just per damunt de 4 kilobytes de RAM. Aquesta restricció no és un problema ni tan sols per als ordinadors personals més vells i els ordinadors portàtils, encara que evita que es pugui fer servir en els sistemes incrustats més petits com les primeres targetes intel·ligents.

Blowfish va ser un dels primers sistemes de xifratge per bloc segurs no subjecte a cap patent i per això lliurement disponible perquè qualsevol el faci servir. Aquest benefici ha contribuït a la seva popularitat en el programari criptogràfic.

Vegeu també[modifica | modifica el codi]

Notes i referències[modifica | modifica el codi]

  1. [enllaç sense format] http://www.schneier.com/article-blowfish-fse.html
  2. [enllaç sense format] http://www.schneier.com/blowfish-bug.txt
  3. Serge Vaudenay. On the Weak Keys of Blowfish (PostScript), 1996 [Consulta: 23 agost 2006]. 
  4. Dahna, McConnachie. «Bruce Almighty: Schneier preaches security to Linux faithful». Computerworld p. 3, 2007-12-27. [Consulta: 2007-12-31]. «At this point, though, I'm amazed it's still being used. If people ask, I recommend Twofish instead.»
  5. Els jocs de proves enviats a lwn.net inclouen proves sobre arquitectures no-x86.
  6. [enllaç sense format] http://www.mail-archive.com/support@pfsense.com/msg15423.html
  7. [enllaç sense format] http://www.debian-administration.org/articles/217#comment_15
  • Vincent Rijmen, "Cryptanalysis and design of iterated block ciphers", dissertació doctoral, octubre de 1997.
  • Bruce Schneier, Description of a New Variable-Length Key, 64-bit Block Cipher (Blowfish). Fast Software Encryption 1993: 191–204 «Enllaç»..
  • Bruce Schneier, The Blowfish Encryption Algorithm -- One Year Later, Dr. Dobb's Journal, 20(9), p. 137, September 1995 «Enllaç»..
  • Serge Vaudenay, "On the weak keys of Blowfish," Fast Software Encryption (FSE'96), LNCS 1039, D. Gollmann, Ed., Springer-Verlag, 1996, pp. 27–32.

Enllaços Externs[modifica | modifica el codi]

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Blowfish Modifica l'enllaç a Wikidata