Kansainvälinen salausalgoritmi IDEA – lohkosalaus, 128-bittinen avain
IDEA: tehokas lohkosalaus 64-bittisille lohkoille ja 128-bittisellä avaimella — historia, rakenne, turvallisuus ja käyttö PGP:ssä. Lue kattava analyysi.
Kansainvälinen salausalgoritmi (International Data Encryption Algorithm, IDEA) on lohkosalaus, jonka Xuejia Lai ja James Massey ETH Zürichistä suunnittelivat vuonna 1991. Algorithmin tarkoituksena oli alun perin korvata Data Encryption Standard ja se perustuu osin aikaisempaan salausalgoritmiin nimeltä Proposed Encryption Standard (PES), jota on paranneltu joillakin ratkaisuilla; tämän vuoksi IDEA tunnettiin aluksi myös nimellä IPES (Improved PES).
Perusperiaatteet
IDEA käsittelee tietoa 64-bittisinä lohkoina ja käyttää 128-bittistä avainta. Salauksen runko koostuu kahdeksasta identtisestä kierroksesta (kierros) sekä yhdestä niin sanotusta puolikkaasta kierroksesta (puolikierros), yhteensä siis 8,5 kierrosta. Salauksen ja salauksen purkamisen periaatteet ovat samankaltaiset, mutta purkamisessa käytetään avaimista johdettuja inversioita ja aliavainten eri järjestystä.
Operaatiot ja miksi ne valittiin
IDEA:n tietoturva perustuu eri algebrallisten operaatioiden yhdistelmään: 16-bittinen modulaarinen yhteenlasku (mod 2^16), 16-bittinen modulaarinen kertolasku modulo 2^16+1 (eli modulo 65537) ja bittitasoinen eXclusive OR (XOR). Näitä operaatioita on valittu siten, että ne ovat "algebrallisesti yhteensopimattomia", mikä vaikeuttaa yksinkertaisten yhtälöiden muodostamista ja hyökkäysten rakentamista.
Erityisesti kertolasku modulo 65537 käsitellään siten, että arvo 0 tulkitaan luvuksi 65536, jotta jokaisella 16-bittisellä sanalla on käänteinen alkio tässä ryhmässä. Tämä helpottaa käänteisten aliavainten laskemista purkamisvaiheessa.
Avainten luonti (avainsuuntaus)
IDEA käyttää 52 kappaletta 16-bittisiä aliavaimia: kutakin kahdeksaa täyttä kierrosta varten tarvitaan kuusi aliavainta ja puolikkaalle kierrokselle neljä, yhteensä 8·6 + 4 = 52 aliavainta. Kahdeksan ensimmäistä aliavainta otetaan suoraan 128-bittisestä pääavaimesta, siten että K1 vastaa 16 alinta bittiä ja K8 16 ylimpiä bittejä. Seuraavat aliavainten ryhmät tuotetaan kiertämällä pääavainta vasemmalle 25 bittiä edellisen ryhmän luomisen jälkeen; tällä tavoin saadaan tarvittavat 52 16-bittistä sanaa kuudella 128-bittisen pääavaimen kierrätyksellä.
Salauksessa aliavaimia käytetään suoraan; purkamisessa aliavaimet muunnetaan siten, että kertolaskujen aliavaimet korvataan niiden multiplicatiivisilla inverseilla modulo 65537 ja yhteenlaskujen aliavaimet saavat negatiivisen (mod 2^16) arvon, ja aliavainten järjestys käännetään oikeaan purkausjärjestykseen.
Turvallisuus ja kryptoanalyysi
Suunnittelijat analysoivat IDEA:a erityisesti differentiaalista kryptoanalyysia vastaan ja totesivat sen olevan vahva tietyissä analyysimalleissa. IDEA:n yhdistelmä eri operaatioita tekee siitä hankalan analysoida algebrallisesti. Joitakin heikkojen avainten luokkia on löydetty (esim. Daemen et al., 1994), mutta nämä avaimet ovat niin harvinaisia, että niillä ei ole käytännöllistä merkitystä, kun avaimet valitaan satunnaisesti ja vältetään tunnettuja erikoistapauksia.
Onnistuneita laajalle yleisesti sovellettavia lineaarisia tai differentiaalisia hyökkäyksiä IDEA:ta vastaan ei ole raportoitu. Vuodesta 2007 lähtien tunnetuin hyökkäys koskee lyhennettyä versiota: paras tunnettu hyökkäys voi murtaa IDEA:n, jos se supistetaan kuuteen kierrokseen (täydellinen IDEA käyttää 8,5 kierrosta) . Kokonaisen 8,5-kierroksisen IDEA:n murtaminen kaikkia avaimia vastaan ei ollut julkisesti raportoidusti mahdollista tähän mennessä.
Lisäksi kannattaa huomata käytännön rajoitus: IDEA käyttää 64-bittistä lohkokokoa, mikä periaatteessa tekee siitä alttiimman ns. syntymäpäivähyökkäyksille (birthday attacks) tai lohkon uudelleenkäytön ongelmille, jos samaa avainta käytetään hyvin suurille tietomäärille ilman turvallisia toimintatiloja (esim. uudelleenkäytön estävää IV:tä). Nykyiset käytännöt suosivat yleensä 128-bittisiä lohkokokoja (kuten AES) suurten datamäärien salaamiseen.
Käyttö, lisenssi ja historia
IDEA oli merkittävä 1990-luvulla ja sitä käytettiin esimerkiksi Pretty Good Privacy (PGP) v2.0:ssa sen jälkeen, kun v1.0:ssa käytetty salaus, BassOmatic, todettiin murrettavaksi. IDEA:ta voidaan käyttää OpenPGP-standardin kanssa. Algoritmi on kuitenkin patentoitu useissa maissa, ja sen käyttö kaupallisiin tarkoituksiin edellytti lisenssiä; toisaalta kuka tahansa saattoi käyttää sitä ei-kaupalliseen käyttöön. Nimi "IDEA" on myös tavaramerkki. Patentit päättyivät vuosina 2010–2011, ja nykyisin IDEA:n lisensiointi on ollut maailmanlaajuisesti MediaCrypt-nimisen yrityksen hallinnassa.
IDEA:n suunnittelun jälkeen salaukseen liittyvässä kentässä on kehittynyt runsaasti uusia vaihtoehtoja. Esimerkiksi vuonna 1996 Bruce Schneier totesi IDEA:sta: "Mielestäni se on paras ja turvallisin tällä hetkellä yleisön saatavilla oleva lohkoalgoritmi." (Applied Cryptography, 2. painos.) Myöhemmin, noin vuoteen 1999 mennessä, hän ei enää suositellut IDEA:ta samalla tavalla johtuen uusien algoritmien nopeudesta, salausanalyysin kehityksestä ja patenttikysymyksistä .
Toteutukset ja suorituskyky
IDEA on suunniteltu toimimaan tehokkaasti sekä ohjelmisto- että laitteistoympäristöissä. Sen operaatiot on helppo toteuttaa 16-bittisillä sanoilla toimivissa arkkitehtuureissa. Kuitenkin nykyaikaisilla 32- ja 64-bittisillä prosessoreilla uudemmat algoritmit (kuten AES) voivat olla nopeampia ja hyödyntävät laitteistotukea (esim. AES-NI).
Yhteenveto
- IDEA on 1991 suunniteltu 64-bittinen lohkosalaus, joka käyttää 128-bittistä avainta.
- Se yhdistää modulo-2^16 yhteenlaskun, modulo-65537 kertolaskun ja XOR-operaation luodakseen vahvan sekoituksen.
- Avainten generointi perustuu 128-bittisen pääavaimen kiertämiseen ja tuottaa 52 kpl 16-bittisiä aliavaimia.
- Algoritmi on osoittautunut kestäväksi monia perinteisiä hyökkäysmenetelmiä vastaan, vaikkakin lyhennetyt versiot voidaan murtaa tehokkaammin.
- Patentit ja pienempi lohkokoko vaikuttivat IDEA:n laajempaan käytettävyyteen verrattuna myöhempiin standardeihin, kuten AES:ään.
IDEA on historiallisesti merkittävä ja käytännössä turvallinen lohkoalgoritmi useisiin tarkoituksiin, mutta nykykäytössä sen roolia ovat vähentäneet patentit, pienempi lohkokoko ja suorituskykynäkökohdat verrattuna nykyaikaisiin vaihtoehtoihin.
IDEA:n salauskierros, jossa käytetään kuutta aliavainta.
Kysymyksiä ja vastauksia
K: Mikä on kansainvälinen tietojen salausalgoritmi (IDEA)?
V: IDEA on lohkosalaus, jonka Xuejia Lai ja James Massey ETH Zürichistä suunnittelivat vuonna 1991. Sen oli tarkoitus korvata Data Encryption Standard, ja se sisältää kahdeksan identtistä muunnosta (kierrosta) ja yhden tulomuunnoksen (puolikierros).
K: Miten IDEA toimii?
V: IDEA toimii 64-bittisillä lohkoilla käyttäen 128-bittistä avainta. Se tekee näin yhteensä 8,5 kierrosta. Salaus- ja purkuprosessit ovat samanlaisia. IDEA saa suuren osan turvallisuudestaan yhdistämällä eri ryhmien operaatioita - modulaarinen yhteen- ja kertolasku sekä bittimainen eXclusive OR (XOR) - jotka on valittu niin, että ne ovat "algebrallisesti yhteensopimattomia". Kullakin kahdeksalla kierroksella käytetään kuutta ja puolikkaalla kierroksella neljää aliavainta, eli yhteensä 52 aliavainta. Kukin aliavain on 16-bittinen.
K: Onko IDEA patentoitu?
V: Kyllä, se on patentoitu useissa maissa, mutta kuka tahansa voi käyttää sitä ei-kaupalliseen käyttöön. IDEA-nimi on myös suojattu tavaramerkillä, jonka patentit päättyvät vuosina 2010-2011. Nykyään MediaCrypt lisensoi sen maailmanlaajuisesti.
K: Käytettiinkö IDEAa PGP:ssä (Pretty Good Privacy)?
V: Kyllä, sitä käytettiin PGP v2:ssa sen jälkeen, kun v1:ssä käytetyn BassOmatic-salakirjoituksen todettiin olevan murrettavissa. Sitä voidaan käyttää myös OpenPGP-standardin kanssa nykyään.
K: Onko IDEAa vastaan raportoitu onnistuneita hyökkäyksiä?
V: IDEAa vastaan ei ole vielä raportoitu onnistuneita lineaarisia tai differentiaalisia hyökkäyksiä; joitakin heikkojen avainten luokkia on kuitenkin löydetty, mutta ne ovat niin harvinaisia, että ne voidaan helposti välttää, kun algoritmia käytetään turvallisesti. Vuodesta 2007 lähtien paras hyökkäys, joka koskee kaikkia avaimia, voi murtaa IDEA:n, jos se supistetaan kuuteen kierrokseen (täysversio käyttää kahdeksaa kierrosta).
K: Mitä Bruce Schneier sanoi IDEAsta?
V: Vuonna 1996 hän kirjoitti, että se oli "paras ja turvallisin lohkoalgoritmi, joka oli tuolloin saatavilla"; vuonna 1999 hän ei kuitenkaan enää suositellut sitä, koska saatavilla oli nopeampia algoritmeja ja koska sen salausanalyysissä oli tapahtunut jonkin verran edistystä ja koska sen käyttöön liittyi patenttikysymyksiä.
Etsiä