Blowfish

Blowfish je symetrická bloková šifra, navržena roku 1993 Brucem Schneierem a používána ve značném množství šifrovacích balíků a systémů. Blowfish poskytuje dobrou rychlost šifrování a dodnes není známa efektivní metoda jejího prolomení. Dnes se ale pozornost přesunuje spíše k Advanced Encryption Standard (AES).

Schneier navrhl Blowfish jako obecný algoritmus, zamýšlený jako alternativa k zastarávajícímu DES, bez problémů a omezení vyskytujících se u jiných algoritmů. V době vydání Blowfish, mnoho dalších návrhů bylo uzavřeným softwarem, zatíženým patenty nebo obchodním či vládním tajemstvím. Schneier prohlásil: „Blowfish je nepatentovaný a také tak ve všech zemích zůstane. Algoritmus je tedy volným dílem a může být volně kýmkoli použit.“

Zvláštním rysem návrhu jsou S-boxy závislé na klíči a vysoce komplexní rozvrh užití klíčů.

Algoritmus

Blowfish používá bloky dlouhé 64 bitů a proměnlivou délku klíče od 32 až po 448 bitů. Je 16kolová feistelova šifra užívající velké na klíči závislé S-boxy. Strukturou podobné CAST-128, která používá fixní S-boxy.

The Feistelovo schéma Blowfish

Schéma vlevo ukazuje fungování Blowfish. Každá řádka představuje 32 bitů. Algoritmus uchovává dvě pole podklíčů: 18hodnotové P-pole a čtyři 256hodnotové S-boxy. S-boxy přijímají 8bitový vstup a poskytují 32bitový výstup. Každé kolo je použita jedna hodnota P-pole, po posledním kole, každá polovina data bloku je sloučena funkcí XOR s jednou ze dvou zbývajících nepoužitých P-hodnot.

Diagram napravo zobrazuje Blowfish F-funkci. Funkce rozděluje 32bitový vstup na čtyři osmibitové části, tyto části poté používá jako vstup pro S-boxy. Výstup je upraven modulem 2³² a použita funkce XOR k vytvoření konečného 32bitového výstupu.

Dešifrování je přesně stejné jako šifrování, kromě toho že P1, P2,…, P18 jsou použity v opačném pořadí. To není tak zřejmé protože xor je komutativní a asociativní funkcí. Běžným omylem je použití opačného pořadí šifrování jako dešifrovací algoritmus (tedy prvně užít xor k P17 a P18 na blok šifrovaného textu, poté užít P-vstupy v opačném pořadí).

Rozvrh užití klíčů začíná inicializací P-pole a S-boxů hodnotami odvozenými z šestnáctkového zápisu čísla pí, které neobsahuje žádný zřejmý vzor. Tajný klíč je poté, bajt po bajtu, v případě potřeby opakován, použit ve funkci XOR se všemi P-hodnotami v daném pořadí. 64bitový blok nul je poté zašifrován algoritmem. Nový výsledný šifrovaný text nahradí P₁ a P₂. Stejný šifrovaný text je poté znovu šifrován s novými podklíči, nový výsledný šifrovaný text nahradí P₃ a P₄. Toto pokračuje, nahrazením všech hodnot P-pole a všech hodnot S-boxů. Celkem Blowfish šifrovací algoritmus proběhne 521krát k vygenerování všech podklíčů, je zpracováno zhruba 4KB dat.

Protože je P-pole 576 bitů dlouhé a bajty klíče jsou použity funkcí XOR na celých těchto 576 bitech během inicializace, mnoho implementací umožňuje použití klíče do délky 576 bitů. I když je toto technicky možné, 448bitový limit je nastaven aby se zaručilo, že každý bit všech podklíčů bude záviset na každém bitu klíče, jelikož poslední čtyři hodnoty P-pole neovlivňují všechny bity šifrovaného textu. Toto by se mělo brát v úvahu pro implementace s rozdílným počtem kol, ačkoli to zvyšuje odolnost proti vyčerpávajícímu útoku, oslabuje bezpečnost zaručenou přímo algoritmem. A dáno pomalou inicializací šifry s každou změnou klíče, zaručuje přirozenou ochranu proti útokům hrubou silou, což tedy neospravedlňuje použití klíčů delších než 448 bitů.

 uint32_t P[18];    
 uint32_t S[4][256];
 
 uint32_t f (uint32_t x) {
    uint32_t h = S[0][x >> 24]   S[1][x >> 16 & 0xff];
    return ( h ^ S[2][x >> 8 & 0xff] )   S[3][x & 0xff];
 }
 
 void encrypt (uint32_t & L, uint32_t & R) {
    for (int i=0 ; i<16 ; i  = 2) {
       L ^= P[i];
       R ^= f(L);
       R ^= P[i 1];
       L ^= f(R);
    }
    L ^= P[16];
    R ^= P[17];
    swap (L, R);
 }
 
 void decrypt (uint32_t & L, uint32_t & R) {
    for (int i=16 ; i > 0 ; i -= 2) {
       L ^= P[i 1];
       R ^= f(L);
       R ^= P[i];
       L ^= f(R);
    }
    L ^= P[1];
    R ^= P[0];
    swap (L, R);
 }
 
  {
    // ...
    // inicializace P-pole a S-boxů hodnotami odvozenými od pí; v příkladu vynecháno
    // ...
    for (int i=0 ; i<18 ;   i)
       P[i] ^= key[i % keylen];
    uint32_t L = 0, R = 0;
    for (int i=0 ; i<18 ; i =2) {
       encrypt (L, R);
       P[i] = L; P[i 1] = R;
    }
    for (int i=0 ; i<4 ;   i)
       for (int j=0 ; j<256; j =2) {
          encrypt (L, R);
          S[i][j] = L; S[i][j 1] = R;
       }
 }

Blowfish v praxi

Blowfish je rychlou blokovou šifrou, s výjimkou výměny klíčů. Každý nový klíč vyžaduje preprocessing ekvivalentní zašifrování zhruba 4 kilobajtů textu, což je ve srovnání s jinými blokovými šiframi velmi pomalé. Toto brání použití v některých aplikacích, zatímco u jiných to není problém.

V jedné z aplikací je pomalá výměna klíčů fakticky výhodou, metoda hašování hesla v OpenBSD používá algoritmus odvozený od Blowfish, který využívá pomalý rozvrh klíčů. Představa je taková, že nutný dodatečný výpočetní výkon poskytuje ochranu proti slovníkovému útoku.

Blowfish užívá něco málo přes 4 kilobajty paměti. Takové omezení není problémem ani pro starší počítače, avšak brání použití v nejmenších vestavěných systémech jako rané smartcard.

Blowfish byla jednou z prvních bezpečných blokových šifer, které nebyly zatíženy patenty, a tedy byly pro kohokoli volně k užití. Toto přispělo k její popularitě při užití v kryptografickém softwaru.

Slabiny a nástupci

Blowfish je znám náchylností k útokům na jistou skupinu slabých klíčů. Toto znamená, že uživatelé Blowfish si musejí opatrně vybírat klíče, jelikož existuje skupina klíčů o kterých je známo, že jsou slabé, nebo přejít k modernější alternativě jako třeba AES, Salsa20, či moderní nástupci Blowfish: Twofish a Threefish. Bruce Schneier, tvůrce Blowfish, byl v roce 2007 citován: „V tomto bodě, jsem udiven, že se stále užívá. Pokud by se mě někdo zeptal, doporučil bych Twofish.“ FAQ pro GnuPG (které zahrnuje Blowfish jako jeden ze svých algoritmů) doporučuje, že by Blowfish neměl být používán k šifrování souborů větších než 4GB.

Reference

V tomto článku byl použit překlad textu z článku Blowfish (cipher) na anglické Wikipedii.

Související články

• AES
• Twofish

Externí odkazy

• Obrázky, zvuky či videa k tématu Blowfish na Wikimedia Commons
• Bruce Schneier. The Blowfish Encryption Algorithm [online]. Dostupné online. 
• Bruce Schneier. Products that Use Blowfish [online]. Dostupné online. 
• Standard Cryptographic Algorithm Naming: Blowfish [online]. Dostupné online.