IDEA - bloková šifra (1991): 64-bitové bloky, 128-bitový kľúč

IDEA (1991) — robustná bloková šifra so 64-bitovými blokmi a 128-bitovým kľúčom, bezpečná voči kryptoanalýze, používaná v PGP pre spoľahlivé šifrovanie dát.

Medzinárodný algoritmus šifrovania údajov (IDEA) je bloková šifra, ktorú v roku 1991 navrhli Xuejia Lai a James Massey z ETH Zürich. IDEA bola navrhnutá ako náhrada za Data Encryption Standard (DES) a vychádza zo skôr navrhnutej šifry Proposed Encryption Standard (PES) s niekoľkými vylepšeniami; pôvodné meno návrhu bolo IPES (Improved PES).

Základné vlastnosti

IDEA pracuje so 64-bitovými blokmi a používa 128-bitový kľúč. Šifra pozostáva z ôsmich identických kôl a jednej výstupnej transformácie (tzv. polkolo), čo predstavuje spolu 8,5 kôl. Procesy šifrovania a dešifrovania sú si veľmi podobné — dešifrovanie sa vykonáva použitím inverzných podkľúčov v opačnom poradí.

Interná štruktúra a operácie

64-bitový blok sa počas každej iterácie rozdelí na štyri 16-bitové slová. IDEA kombinujebiežné aritmetické a bitové operácie, konkrétne:

• násobenie modulo 2¹⁶ + 1 (tj. modulo 65537), pričom hodnota 0 je v tejto operácii považovaná za 2¹⁶ (to zabezpečuje prítomnosť multiplikatívnych inverzií pre väčšinu hodnôt),
• modulárne sčítanie modulo 2¹⁶,
• bitové exkluzívne OR (XOR).

Tieto tri typy operácií pochádzajú z rôznych algebraických štruktúr a ich kombinácia (tzv. prelínanie) zvyšuje odolnosť proti algebraickým útokom, pretože sú „algebraicky nekompatibilné“.

Podkľúče a rozšírenie kľúča

IDEA vyžaduje celkom 52 podkľúčov po 16 bitoch: každé z ôsmich plných kôl používa šesť podkľúčov a polkolo používa štyri. Počiatočných osem 16-bitových podkľúčov sa získava priamo z 128-bitového hlavného kľúča (K1 sú najnižšie 16 bitov, K8 najvyššie 16 bitov). Ďalšie skupiny po ôsmich podkľúčoch sa vytvárajú rotáciou hlavného kľúča doľava o 25 bitov po vytvorení predchádzajúcej skupiny; postupom viacerých takýchto rotácií (šesť rotácií plus doplnenie poslednými 4 podkľúčmi) sa vygeneruje všetkých 52 podkľúčov.

Pri dešifrovaní sa potrebné podkľúče transformujú na ich inverzné hodnoty: pre násobenie sa používajú multiplikatívne inverzy modulo 65537, pre sčítanie zase aditívne inverzy modulo 2¹⁶, a následne sa poradie podkľúčov obráti.

Použitie v praxi

IDEA sa preslávila najmä vďaka použitiu v programe Pretty Good Privacy (PGP) vo verzii 2.0, keď sa zistilo, že pôvodná šifra BassOmatic použitá vo verzii 1.0 nie je bezpečná. IDEA sa takisto môže používať so štandardom OpenPGP. Autorské práva a patenty však ovplyvnili jej rozšírenie v komerčnej oblasti.

Patenty, licencie a právny stav

Šifra IDEA bola patentovaná vo viacerých krajinách a jej používanie pre komerčné účely bolo viazané licenciou; meno "IDEA" je tiež ochrannou známkou. Podľa pôvodných informácií platnosť patentov vypršala v rokoch 2010–2011. V čase, keď boli patenty platné, bola IDEA celosvetovo licencovaná spoločnosťou MediaCrypt.

Bezpečnosť a kryptoanalýza

Konštruktéri IDEA analyzovali odolnosť šifry proti diferenciálnej kryptoanalýze a ďalším známym metódam a konštatovali, že pri bežných podmienkach nie je ľahko napadnuteľná. Doteraz neboli zaznamenané žiadne prakticky použiteľné lineárne ani diferenciálne útoky na plnú verziu (8,5 kôl). Boli nájdené určité triedy slabých kľúčov (napr. Daemen et al., 1994), avšak tieto triedy sú také zriedkavé, že pre bežné použitie majú malý praktický význam.

V rokoch nasledujúcich po návrhu šifry sa výskumníci postupne zamerali na redukované verzie IDEA: od roku 2007 sú známe najlepšie útoky, ktoré dokážu prelomiť IDEA zredukovanú na 6 kôl; na plnú 8,5-kolovú verziu však neexistuje úspešný útok nad rámec „teoretických“ znížených variantov.

Názory a súčasné postavenie

Bruce Schneier o IDEA v roku 1996 napísal: „Podľa môjho názoru je to najlepší a najbezpečnejší blokový algoritmus, ktorý je v súčasnosti k dispozícii verejnosti.“ (Applied Cryptography, 2nd ed.). V roku 1999 však Schneier odporučil iné riešenia, keďže medzičasom sa objavili rýchlejšie algoritmy, zaznamenal sa určitý pokrok v kryptoanalýze IDEA a existovala problematika patentov. Dnes (po zavedení a štandardizácii AES a ďalších moderných šifier) sa IDEA používa menej často, no z pohľadu konštrukcie a doterajšej kryptoanalýzy zostáva považovaná za silný a dobre preskúmaný algoritmus.

Implementačné poznámky

• Pri implementácii je potrebné správne zaobchádzať s násobením modulo 65537 a s interpretáciou hodnoty 0 (mapovanie na 2¹⁶), aby výsledky zodpovedali špecifikácii.
• Vzhľadom na kombináciu rôznych aritmetík (modulárne sčítanie, násobenie a XOR) vyžaduje IDEA starostlivé vyhotovenie pre efektívnosť, najmä na platformách bez hardvérovej podpory pre 16-bitové operácie.
• Pre nové projekty sa často uprednostňuje AES, ktorý je rýchlejší na modernejších procesoroch a voľne použiteľný bez problémov s licenciami; IDEA môže byť však stále vhodná tam, kde sú požiadavky späté s kompatibilitou so staršími systémami alebo kde je jej použitie explicitne povolené.

IDEA zostáva dôležitou súčasťou histórie blokových šifier — predstavuje zaujímavý prípad konštrukcie založenej na prelínaní algebraicky odlišných operácií a dodnes slúži ako referenčný príklad pri štúdiu symetrických algoritmov.

Otázky a odpovede

Otázka: Čo je to medzinárodný algoritmus šifrovania údajov (IDEA)?

Otázka: Ako funguje IDEA?

Otázka: Je IDEA patentovaná?

Otázka: Bola IDEA použitá v programe Pretty Good Privacy (PGP)?

Otázka: Bol zaznamenaný nejaký úspešný útok proti IDEA?

Otázka: Čo povedal Bruce Schneier o IDEA?

Hľadajte podľa písmena