Blowfish: avoin symmetrinen lohkosalausalgoritmi (Bruce Schneier)

Blowfish — Bruce Schneierin avoin symmetrinen lohkosalausalgoritmi: patentoimaton, nopea ohjelmistossa, 64‑bittinen lohko, 0–448 b avain, hidas avainvaihto; käytössä mm. OpenBSD.

Salakirjoituksessa Blowfish on Bruce Schneierin vuonna 1993 kehittämä symmetrinen lohkosalakirjoitus, joka on vuodesta 1993 lähtien sisältynyt lukuisiin salaustuotteisiin. Blowfishin salausnopeus ohjelmistoissa on hyvä, eikä sille ole löydetty kryptoanalyyttistä hyökkäysmallia vuoteen 2008 asti. AES-lohkosalausalgoritmi on kuitenkin saanut nyt enemmän huomiota.

Schneier kehitti Blowfishin yleiskäyttöiseksi algoritmiksi, jolla korvattaisiin vanha DES-algoritmi ja poistettaisiin muiden salausalgoritmien ongelmat ja vaikeudet. Blowfishin julkaisun aikaan monet muut algoritmit olivat patentoituja tai salaisia. Schneier on sanonut, että "Blowfish on patentoimaton ja pysyy sellaisena kaikissa maissa. Algoritmi asetetaan täten julkiseen käyttöön, ja kuka tahansa voi käyttää sitä vapaasti."

Suunnitelman pääpiirteisiin kuuluvat avaimesta riippuvaiset S-laatikot ja erittäin monimutkainen avaimen aikataulu. Blowfish on yksi nopeimmista monien käyttämistä lohkosalaimista, paitsi avainta vaihdettaessa. Jokainen uusi avain on esikäsiteltävä, mikä vie saman ajan kuin noin 4 kilotavun tekstin salaus, mikä on hyvin hidasta verrattuna muihin lohkosalaimiin. Tämä estää sen käytön tietyissä sovelluksissa (kuten pienimmissä sulautetuissa järjestelmissä, kuten varhaisissa älykorteissa), mutta se ei ole ongelma muissa sovelluksissa. Eräässä sovelluksessa se on itse asiassa hyvä: OpenBSD:ssä käytetty salasanojen salausmenetelmä käyttää Blowfishista peräisin olevaa algoritmia, joka hyödyntää hidasta avaimen aikataulua; ideana on, että tarvittava ylimääräinen laskentatyö antaa suojaa sanakirjahyökkäyksiä vastaan. Katso avainten vahvistaminen.

Blowfishin lohkokoko on 64 bittiä ja avaimen pituus vaihtelee 0:sta 448 bittiin. Se on 16-kierroksinen Feistel-salaus ja käyttää suuria avaimesta riippuvaisia S-boxeja. Se on rakenteeltaan samanlainen kuin CAST-128, joka käyttää kiinteitä S-boxeja.

Vuonna 1996 Serge Vaudenay löysi hyökkäyksen, joka tarvitsi ^28r+1 tunnettua tekstitiedostoa murtautuakseen, missä r on kierrosten lukumäärä. Lisäksi hän löysi myös luokan heikkoja avaimia, jotka voidaan havaita ja murtaa samalla hyökkäyksellä vain ^{24r + 1} tunnetulla salatekstillä. Tätä hyökkäystä ei voida käyttää tavallista Blowfishia vastaan, sillä se edellyttää avaimesta riippuvien S-boxien tuntemista. Vincent Rijmen esitteli väitöskirjassaan toisen asteen differentiaalihyökkäyksen, jolla voidaan murtaa neljä kierrosta, mutta ei enempää. Edelleenkään ei tiedetä mitään keinoa murtaa kaikkia 16 kierrosta, lukuun ottamatta raa'an voiman hakua. Eräässä julkaistussa C-koodissa havaittiin vuonna 1996 merkinlaajennusvirhe.

Blowfishin täyskierroksisesta versiosta ei ole tehty hyvää kryptoanalyysiä, joka olisi ollut julkisesti tiedossa ennen vuotta 2008. Vuonna 2007 Bruce Schneier totesi kuitenkin, että vaikka Blowfish on edelleen käytössä, hän suositteli uuden Twofish-algoritmin käyttöä sen sijaan.

Suunnittelu ja tekniset yksityiskohdat

Blowfish on suunniteltu käytännölliseksi ja nopeaksi ohjelmistossa toteutettavaksi lohkosalaimeksi. Sen pääominaisuuksia:

• Lohkokoko: 64 bittiä.
• Kierrokset: 16 Feistel-kierrosta.
• Avaimen pituus: muuttuva, 0–448 bittiä (tyypillisesti 128/192/256 bittiä käytetään käytännössä).
• Alkeisosat: P-taulukko (18 32-bittistä sanaa) ja neljä S-laatikkoa (jokaisessa 256 32-bittistä alkioita), jotka tehdään avaimesta riippuviksi avainlaajennusvaiheessa.

Algoritmin alkuperäiset P-taulukon ja S-laatikoiden lähtöarvot asetetaan tunnetuilla vakioilla (alkuperäisessä määrittelyssä käytettiin pi-lukusarjan heksadesimaaliarvoja), ja nämä arvot sekoitetaan avaimen sisällöllä avaimesikseen. Tuloksena syntyvät avaimesta riippuvat S-laatikot ovat keskeinen osa Blowfishin turvaa.

Avaimen alustus ja vaikutus suorituskykyyn

Blowfishin avainlaajennus on laskennallisesti raskas verrattuna joihinkin muihin lohkosalaimiin. Jokainen uusi avain vaatii koko P-taulukon ja S-laatikoiden uudelleenlaskennan, mikä käytännössä tarkoittaa sarjaa Blowfish-salausoperaatioita (alkuperäisessä kuvauksessa mainittu esikäsittely vastasi merkittävää määrää salauksia, vastaten noin 4 kilotavun tekstin salaamista). Tämä tekee avaimenvaihdosta ja avaimen luomisesta hitaamman operaation.

Tämä ominaisuus on sekä heikkous että vahvuus riippuen käyttötapauksesta: sulautetussa ympäristössä tai tilanteissa, joissa avainta vaihdetaan usein ja resurssit ovat rajalliset, hidas avainalustus voi olla ongelma. Toisaalta salasanojen hajautuksessa (bcrypt) hidastettu avainalustus antaa suojaa brute-force- ja sanakirjahyökkäyksiä vastaan.

Käyttötapaukset ja rajoitukset

• Historiallinen käyttö: Blowfish on ollut laajasti käytössä ohjelmistoissa ja kirjastoissa 1990-luvulta lähtien.
• Salasanojen hajautus: Blowfishin avainlaajennukseen perustuva bcrypt on hyvin tunnettu ja laajalti käytetty salasanojen hajautusmenetelmä, joka hyödyntää hidasta avainlaajennusta ja kustannusparametria tehon säätämiseen.
• Rajoitus — 64-bittinen lohko: Modernissa käytössä 64-bittinen lohkokoko on usein liian pieni suurissa tiedonmääriä käsittelevissä sovelluksissa. "Birthday attack" -periaatteen vuoksi saman avaimen alla salatuissa tiedoissa lohkon toistumiset tulevat merkittäviksi jo suhteellisen pienessä datamäärässä (noin 2^32 lohkoa), mikä voi altistaa esimerkiksi joitain salausmoodit (CBC, CTR) tietylle riskille suurissa volyymeissa.

Turvallisuus ja tunnetut kryptoanalyysitulokset

Blowfishiin kohdistetut kryptoanalyysit ovat keskittyneet pääasiassa lyennettyihin kierrosmääriin tai tiettyihin avainluokkiin:

• Serge Vaudenay esitti 1990-luvulla erilaisia differentiaalisen analyysin työkaluja, jotka kohdistuivat avaimesta riippuviin S-laatikoihin ja löysivät heikkojen avainten luokkia sekä hyökkäysskenaarioita — nämä tutkimukset koskivat käytännössä pienempiä kierrosmääriä tai erityistapauksia.
• Vincent Rijmen ja muut tutkijat ovat osoittaneet hyökkäyksiä, jotka murtautuvat muutamille kierroksille (esim. neljä kierrosta), mutta tehokasta ja käytännöllistä hyökkäystä kaikkia 16 kierrosta vastaan ei ole julkisesti esitetty ennen 2008-lukua.
• Ohjelmointivirheet (esimerkiksi merkinlaajennusvirheet C-koodissa) ovat myös olleet yksittäisiä toteutuksiin liittyviä ongelmia, eivät itse algoritmin matemaattinen heikkous.

Yleisesti ottaen Blowfishin 16-kierroksinen perusversio ei ole murrettu käytännössä yleisesti hyväksytyllä tavalla, mutta sen 64-bittinen lohkokoko ja muut toteutus- ja avainhallintariskit rajoittavat sen käyttöä nykyaikaisissa järjestelmissä.

Nykytila ja suositukset

Vuonna 2007 Bruce Schneier itse suositteli Twofish-algoritmin käyttöä Blowfishin sijasta uusissa toteutuksissa. Nykyiset suositukset käytännössä korostavat seuraavaa:

• Uusissa järjestelmissä ja protokollissa suositellaan 128-bittisiä lohkosalaimia (kuten AES) tai moderneja virtaus- ja kaistamenetelmiä (esim. ChaCha20) 64-bittisten lohkojen sijaan.
• Blowfish voi edelleen olla käyttökelpoinen legacy-yhteensopivuuteen tai pienimuotoisiin sovelluksiin, joissa salatun datan kokonaismäärä on selkeästi rajattu ja avainvaihto harvinaista.
• Salasanojen tallennukseen on suositeltavaa käyttää erityisesti tähän suunniteltuja hajautusfunktioita kuten bcrypt (joka perustuu Blowfishin avainlaajennukseen), Argon2 tai PBKDF2; bcrypt on yhä laajalti käytössä sen kustannussäädön takia.

Yhteenvetona: Blowfish on historiallisesti merkittävä, nopea ohjelmistototeutuksissa ja patenttivapaa vaihtoehto 1990-luvulta alkaen, mutta sen 64-bittinen lohkokoko ja avainalustuksen erityispiirteet tekevät siitä usein huonomman valinnan nykyaikaisiin uusiin salaussovelluksiin verrattuna 128-bittisiin lohkoihin perustuvaan AES:ään tai muihin nykyaikaisiin menetelmiin.

Kysymyksiä ja vastauksia

K: Mikä on Blowfish?

K: Mitä varten Blowfish tehtiin?

K: Kuinka pitkä avaimen pituus voi olla Blowfishissa?

K: Mitä ominaisuuksia Blowfishin suunnittelussa on?

K: Onko Blowfishin täyskierrosversiolle tiedossa kryptoanalyysiä?

K: Millaisen hyökkäyksen Serge Vaudenay löysi Blowfishia vastaan?

Kysymys: Suositteleeko Bruce Schneier nyt Twofishin käyttöä Blowfishin sijasta?

Hae kirjaimella