Differentiaalisen kryptanalyysin perusteet

Differentiaalinen kryptanalyysi (Biham & Shamir, 1990) on valitun selvätekstin hyökkäys, jossa analysoidaan, miten selvätekstiparien erot etenevät salaimen läpi. Etsimällä syöte-eroja, jotka tuottavat suurella todennäköisyydellä ennustettavia tuloste-eroja, hyökkääjä palauttaa avaimen bittejä tilastollisesti.

XOR-pohjaisille salaimille: ero ΔX = X XOR X'. Yhteenlaskuun perustuville salaimille: ero ΔX = X - X' mod 2^n. XOR-erot ovat yleisimpiä, koska XOR kommutoi XOR-avaamisen kanssa (avaintaulun vaikutukset kumoutuvat differentiaalipareissa).

Differentiaaliparilla (P, P') on syöte-ero ΔP = P XOR P'. Salaamisen jälkeen saadaan pari (C, C'), jonka tuloste-ero on ΔC = C XOR C'. Hyödyllinen differentiaali on ΔP → ΔC, jolla on suuri todennäköisyys p — tämä tarkoittaa, että monet eron ΔP omaavat (P, P')-parit tuottavat tuloste-eron ΔC.

DDT (Differential Distribution Table) laskee, kuinka monelle syötteelle x pätee kunkin syöte-eron Δx ja tuloste-eron Δy kohdalla S(x) XOR S(x XOR Δx) = Δy. Jakamalla luvulla 2^n saadaan todennäköisyys. Hyvän S-boxin DDT:n enimmäisarvo on 2 (todennäköisyys 1/2^{n-1}) — vahvoja differentiaaleja ei ole.

Kun lohkosalaimessa on r kierrosta, etsi jono ΔP → ΔU1 → ΔU2 → ... → ΔU_{r-1}, jossa jokaisella kierroksen siirtymällä on tunnettu todennäköisyys. Kerro kierrosten todennäköisyydet keskenään: kokonaistodennäköisyys p = p1 * p2 * ... * p_{r-1}. Hyökkäys käyttää 2/p paria viimeisen kierroksen avaimen palauttamiseen.

Kun käytettävissä on suuren todennäköisyyden r-1 kierroksen differentiaali: kerää N = 2/p selvätekstiparia. Pura jokaisen viimeisen kierroksen avainehdokkaan K' kohdalla molemmat salatekstit yhden kierroksen verran, XOR:aa tulokset ja tarkista, vastaako ero arvoa ΔU_{r-1}. Oikea K' täsmää noin N/2 kertaa; väärät avaimet täsmäävät noin N/2^{bit_size} kertaa.

AES:n S-box muodostuu GF(2^8):n multiplikatiivisesta käänteisalkiosta ja sitä seuraavasta affiinista muunnoksesta. Sen DDT:n enimmäisarvo on 4 (256:sta), joten differentiaalinen todennäköisyys on S-boxia kohden ≤ 4/256 = 1/64. AES:ssä on 4 S-boxia kierrosta kohden, mutta Wide Trail -suunnittelu varmistaa, että täydellisten differentiaalipolkujen todennäköisyys on alle 2^{-100}.

Joan Daemenin Wide Trail -suunnittelu (käytössä AES:ssä/Rijndaelissa): määritä MixColumnsin haaraluku B. Jokainen epätriviaali differentiaalipolku yhden kierroksen läpi aktivoi vähintään B aktiivista S-boxia. 4 kierrosta × 4 S-boxia kierrosta kohden takaa vähintään 25 aktiivista S-boxia → todennäköisyys < 2^{-100}.

Typistetyt differentiaalit määrittävät vain osan erosta (esimerkiksi vain sen, mitkä sarakkeet ovat aktiivisia, eivät tarkkoja eroarvoja). Tämä mahdollistaa hyökkäykset useampia kierroksia vastaan silloin, kun täydelliset differentiaalit ovat liian heikkoja. Menetelmää käytetään supistettujen kierrosmäärien AES:ää, SERPENTiä ja muita SPN-salaimia vastaan.

Mahdoton differentiaali on pari (ΔP, ΔC), joka ei voi esiintyä millään avaimella. Jokainen avain, joka yhdistää havaitun parin (P, P') tähän eroon, hylätään. Keräämällä riittävästi pareja kaikki väärät avaimet voidaan karsia, jolloin jäljelle jää oikea avain.

Bumerangihyökkäys (Wagner, 1999) yhdistää kaksi lyhyttä differentiaalia mukautuvaksi valitun selvätekstin/salatekstin hyökkäykseksi. Se jakaa salaimen kahteen puoliskoon, joista kummallakin on lyhyt ja suuren todennäköisyyden differentiaali, ja mahdollistaa hyökkäyksen useampaa kierrosta vastaan kuin yksittäinen differentiaali sallisi.

Differentiaalinen kryptanalyysi hyödyntää syöte-erojen suuren todennäköisyyden mukaista etenemistä tuloste-eroiksi. AES kestää sitä DDT:n suhteen optimaalisen S-boxinsa ja Wide Trail -suunnittelunsa ansiosta. Seuraavaksi: lineaarinen kryptanalyysi ja approksimaatiotaulukot.