Blowfish

Feistelkrypto
Utgivningsdatum	1993
Designer	Bruce Schneier
Blockstorlek	64±0 bit
Officiell webbplats	länk

Blowfish är en krypteringsteknik, mer precist ett blockchiffer med hemlig nyckel. Det föreslogs 1994 av Bruce Schneier. Det var tänkt som en konkurrent till IDEA, International Data Encryption Algorithm, som var patentskyddat och DES, Data Encryption Standard, som var för komplicerad att implementera i program samt hade svagheter. Blowfish är därför opatenterat och vem som helst får använda det. Schneier skrev 1994 att Blowfish är opatenterat och för alltid kommer förbli det, i alla länder, samt att algoritmen får användes av vem som helst. Kryptot är ett Feistelkrypto som itererar en enkel krypteringsfunktion 16 gånger. Storleken på blocken är 64 bitar och nyckeln kan ha en storlek på 32-bitar till så mycket som 448 bitar. Det går väldigt snabbt att kryptera data, men det krävs först en tidskrävande initialiseringsfas. ^[1]

Designmål

När Schneier skapade Blowfish hade han ett flertal mål. Han ville ha en ny krypteringsstandard. DES som använts tidigare blev allteftersom datorerna blev starkare, sårbar mot Brute_force-attacker. Dessutom var DES komplicerad att implementera i datorprogram, vilket ofta resulterade i fel. IDEA låg bakom patentskydd. Blowfish är då ett förslag till en ny krypteringsstandard. Målet var att krypteringsalgoritmen skulle vara anpassad för:

"Bulk-kryptering", alltså där filer eller dataströmmar skulle krypteras.
"Slumpbitsgenerering"
Paketkryptering, alltså kunna kryptera data som skickas som paket
"Hashing", alltså fungera som en Kryptografisk hasfunktion.

Krypteringsalgoritmen skulle även gå att implementeras på en rad olika system:

VLSIhårdvara, Very-Large-Scale-Integration, alltså implementeras i hårdvaran på integrerade kretsar och chip.
Stora processorer, algoritmen skulle kunna implementeras som mjukvara på en 32-bitars Mikroprocessor med 4kiloByte minne.
Mellanstora processorer, exempelvis 68HC11 som är en 8-bitars Mikrokontroller.
Små processorer såsom på Smartkort.

Förutom detta ska algoritmen vara enkel för en programmerare att implementera. Den ska vara utan eller ha väldigt få svaga nycklar, så kallad "flat keyspace". ^[1]

Blowfish använder väldigt enkla operationer och kan onekligen implementeras på många olika platformar. Det har dock på senare år bevisats att Blowfish har svaga nyklar, om än ganska få. Blowfish uppfyller bland annat av den anledningen inte alla dessa krav.

Hur det fungerar

Subnycklar

Blowfish använder sig av subnycklar. Dessa måste beräknas innan kryptering eller dekryptering. Man använder sig av:

"P-array", som består av 18 32-bitars subnycklar P1, P2, ..., P18
Fyra 32-bitars "S-boxes" (Substitutionsbox) med 256 element styck. (bild behövs)

 S1,0, S1,1, ..., S1,255;
 S2,0, S2,1, ..., S2,255;
 S3,0, S3,1, ..., S3,255;
 S4,0, S4,1, ..., S4,255.

Subnycklarna beräknas med Blowfishalgoritmen.

 1. Fyll P-array och alla S-boxes i ordning, med en sträng i hexadecimal form. 
 2. Sätt P1 till P1 XOR de första 32 bitarna i nyckeln. Sätt P2 till P2 XOR de nästkommande 32 bitarna i nyckeln, och så vidare till och med P14.
 3. Kryptera en tom sträng (nollfylld) med Blowfish-algoritmen med hjälp av subnycklarna ovan.
 4. Byt ut P1 och P2 med utdata från steg 3.
 5. Kryptera utdatan från steg 3 med Blowfish-algoritmen och de nu modifierade subnycklarna.
 6. Byt ut P3 och P4 med utdata från steg 5.
 7. Fortsätt tills alla element i "P-array" är utbytta, och därefter med de fyra Substitutionsboxarna i ordning.

Denna process kräver 521 iterationer, men det går att lagra dem istället för att upprepa beräkningen varje gång något ska krypteras eller dekrypteras. ^[1]

Kryptering

Funktionen F använder sig endast av två additioner och en XOR-operation

Det som ska krypteras delas upp i block av 64 bitars storlek. Kryptering av varje block sker genom iteration av en enkel algoritm. Det är ett Feistelkrypto med 16 krypteringsomgångar.

 1. Kalla blocket för x, och dela upp det i två lika stora delar, xV och xH 
 2. Pi är elementen på rad i, i P-arrayen. 
 3. Sätt i till 1
 4. Sätt xV till xV XOR Pi
 5. Sätt xH till F(xV) XOR xH
 6. Byt plats på xV och xH
 7. Repetera 3, 4, 5, 6 med nästkommande i till och med att i är 16
 8. Byt plats på xV och xH en sista gång
 9. Sätt xH till xH XOR P17
 10. Sätt xV till xV XOR P18

Funktionen F delar xV i fyra 8-bitars fjärdedelar, a, b, c och d.
$F(xV)=((((S1,a+S2,b)\ mod\ 2^{32})\oplus S3,c)+S4,d)\ mod\ 2^{32}).$ ^[1]

Dekryptering

Dekryptering sker på exakt samma sätt som kryptering, förutom att P-arrayen används baklänges, alltså att P1 blir P18, P2 blir P17 osv. ^[1]

Praktisk användning

Blowfish används inom många olika applikationer. Bruce Schneiers grundtanke var att algoritmen effektivt skulle kunna kryptera data-filer och data som skickas som paket, samt vara bra på hashning^[1]. Följande är en lista över där Blowfish används:
• Hårddisksprogrammeringsprogram såsom "Advanced Encryption Package Professional" och "CryptoDisk"
• Lösenordshanteringsprogram såsom "Java PasswordSafe" och "Password Plus"
• Datakomprineringsprogram såsom "FreeArc" och "Peazip"
• Säkerhet för databaser, exempelvis "IDS Server" och "Encryptionizer"
• I vissa program för E-handel, till exempel "X-Cart"
• För kryptering av E-mail, bland annat "Z1 SecureMail Gateway"
• För säker filöverföring i exempelvis "SSH Tectia"
• SSH i både "PuTTY" och "OpenSSH"
• Operativsystem, exempelvis kärnan (i) [Linux] samt [OpenBSD]
• Steganografiprogram såsom "Data Stash" ^[2]

Kryptoanalys och svagheter

Algoritmen används flitigt men Blowfish har svagheter. Ingen omfattande kryptoanalys har kunnat göras på Blowfish. Dock finns det en kategori svaga nycklar. Dessa nycklar kallas då för "Reflectively weak keys" och ett krypto med dessa nycklar kan då relativt enkelt knäckas^[3]. Sannolikheten att en slumpmässigt vald nyckel är en så kallad svag nyckel, är $2^{32-16r}$ där $(r-2)$ är antalet omgångar Blowfish-funktionen appliceras^[3]. Risken att en nyckel är svag är ganska liten, men eftersom ett knäckt krypto kan få katastrofala följder bör Blowfish-användare betänka sina nycklar alternativt byta kryptoteknik. Exempelvis till det nyare Twofish. Bruce Schneier uttalade sig om Blowfish svagheter 2007. Han var förvånad över att Blowfish fortfarande användes och han rekommenderade istället Twofish.^[4]

Referenser

^ [a b c d e f] Bruce Schneier. "Description of a New Variable-Length Key, 64-Bit Block Cipher (Blowfish)". Springer-Verlag.
^ Bruce Schneier. "Products that Use Blowfish".
^ [a b] Orhun Kara and Cevat Manap (1 mars 2007). ”A New Class of Weak Keys for Blowfish”. FSE 2007. http://www.iacr.org/archive/fse2007/45930168/45930168.pdf.
^ (2007-12-27). "Bruce Almighty: Schneier preaches security to Linux faithful".

[blowfish-paper-1] [a b c d e f] Bruce Schneier. "Description of a New Variable-Length Key, 64-Bit Block Cipher (Blowfish)". Springer-Verlag.

[blowfish-applications-2] Bruce Schneier. "Products that Use Blowfish".

[weak-keys-3] [a b] Orhun Kara and Cevat Manap (1 mars 2007). ”A New Class of Weak Keys for Blowfish”. FSE 2007. http://www.iacr.org/archive/fse2007/45930168/45930168.pdf.

[Schneier-recommendation-4] (2007-12-27). "Bruce Almighty: Schneier preaches security to Linux faithful".

[1]

[2]

[3]

[4]