Vés al contingut

Blowfish

De la Viquipèdia, l'enciclopèdia lliure
Blowfish
La funció rodona (Funció Feistel) de Blowfish
La funció rodona (Funció Feistel) de Blowfish
La funció rodona (Funció Feistel) de Blowfish
General
DissenyadorsBruce Schneier
Data primera publicació1993
SuccessorsTwofish
Detall de xifratge
Mida de la clau32-448 bits en passos de 8 bits; per omissió 128 bits
Mida del bloc64
EstructuraXarxa Feistel
Rondes16
Millor criptoanàlisi pública
Quatre rondes de Blowfish són susceptibles d'un atac diferencial de segon ordre (Rijmen, 1997);[1] per a una classe de claus febles, 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.[2]

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 què 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."[3]

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

L'algorisme

[modifica]
L'estructura Feistel de Blowfish.

Blowfish té una longitud de bloc de 64 bits i una mida de la clau variable des de 32 fins a 448 bits. É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.[4]

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 2³² i es combinen amb una operació XOR per obtenir la sortida final de 32 bits.[5]

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 P₂. El text xifrat s'encripta llavors una altra vegada amb les subclaus noves, i P₃ i P₄ 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àlisi de Blowfish

[modifica]

No hi ha cap criptoanàlisi 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.[6]

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.[7]

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

Blowfish en la pràctica

[modifica]

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 dona 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.[a] É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.[8] 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).[9] 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 (p. ex. 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.

Punts febles i successors

[modifica]

L'ús que fa Blowfish d'una mida de bloc de 64 bits (a diferència de la mida de bloc de 128 bits d'AES) fa que sigui vulnerable als atacs d'aniversari, especialment en contextos com HTTPS. El 2016, l'atac SWEET32 va demostrar com aprofitar els atacs d'aniversari per dur a terme la recuperació de text complet (és a dir, desxifrar text xifrat) contra xifrats amb una mida de bloc de 64 bits.[10]

El projecte GnuPG recomana que Blowfish no s'utilitzi per xifrar fitxers de més de 4 GB a causa de la seva petita mida de bloc. Per a un xifrat amb una mida de bloc de vuit bytes, és probable repetir un bloc després d'uns 32 gigabytes de dades. Això significa que si es xifra un missatge més gran de 32 gigabytes, és gairebé una garantia estadística que hi haurà un bloc repetit.[11] En canvi, Twofish no té aquesta restricció.[12]

Les implementacions de Blowfish utilitzen 16 rondes d'encriptació, i no són susceptibles a atacs de text pla conegut (KPA) en claus reflexivament febles.[13][14] Tot i això, Bruce Schneier ha recomanat migrar al seu successor, Twofish.[2]

Notes

[modifica]
  1. ↑ Els jocs de proves enviats a lwn.net inclouen proves sobre arquitectures no-x86.

Referències

[modifica]
  1. ↑ Vincent Rijmen «Cryptanalysis and Design of Iterated Block Ciphers» (PostScript). Ph.D Thesis, 1997. Arxivat de l'original el 2013-05-08.
  2. ↑ 2,0 2,1 2,2 Dahna, McConnachie. «Bruce Almighty: Schneier preaches security to Linux faithful». Computerworld p. 3, 27-12-2007. [Consulta: 31 desembre 2007]. «At this point, though, I'm amazed it's still being used. If people ask, I recommend Twofish instead.»
  3. ↑ Bruce Schneier «Description of a New Variable-Length Key, 64-Bit Block Cipher (Blowfish)». Fast Software Encryption, Cambridge Security Workshop Proceedings. Springer-Verlag, 1993, pàg. 191–204. Arxivat de l'original el 2014-01-26.
  4. ↑ Bruce Schneier, «The Blowfish Encryption Algorithm - One Year Later»., Dr. Dobb's Journal, 20(9), p. 137, September 1995.
  5. ↑ «Cryptography: Description of a New Variable-Length Key, 64-Bit Block Cipher (Blowfish) - Schneier on Security». Arxivat de l'original el 2016-03-04. [Consulta: 31 desembre 2015].
  6. ↑ «Blowfish Bug» (en anglès). Schneier, 2015. [Consulta: 25 desembre 2017].
  7. ↑ Serge Vaudenay. On the Weak Keys of Blowfish (PostScript), 1996 [Consulta: 23 agost 2006].  Arxivat 2007-11-04 a Wayback Machine.
  8. ↑ «Re: [pfSense Support Intel Atom Motherboards or Similar Systems]» (en anglès). [Consulta: 25 desembre 2017].
  9. ↑ Administration, Debian. «Simple rotated backups with rsnapshot» (en anglès). [Consulta: 25 desembre 2017].
  10. ↑ Karthikeyan Bhargavan; Gaëtan Leurent. «On the Practical (In-)Security of 64-bit Block Ciphers — Collision Attacks on HTTP over TLS and OpenVPN». ACM CCS 2016, 01-08-2016. Arxivat de l'original el 2016-10-09.
  11. ↑ «GnuPG Frequently Asked Questions». Arxivat de l'original el 2017-12-21. [Consulta: 27 gener 2018].
  12. ↑ «GnuPG Frequently Asked Questions». Arxivat de l'original el 2017-12-21. [Consulta: 26 gener 2018]. «Blowfish should not be used to encrypt files larger than 4Gb in size, but Twofish has no such restrictions.»
  13. ↑ Tom Gonzalez. «A Reflection Attack on Blowfish». Journal of LATEX Class Files, 01-01-2007. Arxivat de l'original el 2015-11-18. [Consulta: 17 novembre 2015].
  14. ↑ Orhun Kara; Cevat Manap. «A New Class of Weak Keys for Blowfish». FSE 2007, 01-03-2007. Arxivat de l'original el 2016-10-05.

Vegeu també

[modifica]

Enllaços externs

[modifica]
A Wikimedia Commons hi ha contingut multimèdia relatiu a: Blowfish
Obtingut de «https://ca.wikipedia.org/w/index.php?title=Blowfish&oldid=33347036»