Blowfish

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání

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[editovat | editovat zdroj]

Blowfish používá bloky dlouhé 64 bitů a proměnlivou délku klíče od 32 až po 448 bitů.[1] 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
BlowfishFFunction.svg

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 232 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 , 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í P1 a P2. Stejný šifrovaný text je poté znovu šifrován s novými podklíči, nový výsledný šifrovaný text nahradí P3 a P4. 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,[1] 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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Blowfish je znám náchylností k útokům na jistou skupinu slabých klíčů.[2] [3] 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.“[4] 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.[5]

Reference[editovat | editovat zdroj]

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

  1. a b Bruce Schneier. "Description of a New Variable-Length Key, 64-Bit Block Cipher (Blowfish)". 191–204 Springer-Verlag.
  2. Tom Gonzalez. A Reflection Attack on Blowfish [online]. JOURNAL OF LATEX CLASS FILES, January 2007. Dostupné online. (anglicky) 
  3. Orhun Kara and Cevat Manap. A New Class of Weak Keys for Blowfish [online]. FSE 2007, March 2007. Dostupné online. (anglicky) 
  4. DAHNA, McConnachie. Bruce Almighty: Schneier preaches security to Linux faithful [online]. 2007-12-27 [cit. 2015-01-29]. S. 3. At this point, though, I'm amazed it's still being used. If people ask, I recommend Twofish instead.. Dostupné v archivu pořízeném dne 2012-06-03. (anglicky) 
  5. http://www.gnupg.org/faq/gnupg-faq.html#define_fish

Související stránky[editovat | editovat zdroj]

Externí odkazy[editovat | editovat zdroj]

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