Differentiaalinen kryptoanalyysi

Differentiaalinen kryptoanalyysi on moderni menetelmä lähinnä lohkosalaajien analysoimiseen ja murtamiseen. Menetelmä on hyvin tehokas ja sen avulla on murrettu suuri määrä algoritmeja. Se on yksi käytetyimmistä moderneista kryptoanalyyttisistä tekniikoista.

Analyysi
Etsitään erotuksia dn, 0 kryptografisen algoritmin kierrosfunktiolle f siten että kohtuullisella todennäköisyydellä f(x+dn, 0, k)-f(x, k) antaa tulokseksi saman luvun dn, 1. Etsitään monia tällaisia pareja. Pyritään rakentamaan erotuksista ketju D siten että D0=dm0, 0, D1=dm0, 1=dm1, 0, D2=dm1, 1=dm2, 0 jne. niin että kohtuullisella todennäköisyydellä voidaan tietää kahden salattavan lohkon erotus mahdollisimman monen salauskierroksen läpi.

Hyökkäys
Pyydetään salaukset (c0, c1) lohkoille (b0, b1) siten että b1=b0+D0. Oletetaan että differentiaali D pätee tälle lohkoparille vähintään r-1 kierrosta jossa r on kierrosten kokonaislukumäärä. Dekryptataan (c0, c1) jokaisella mahdollisella kierrosavaimella k. Jos f-1(c1, k)-f-1(c0, k)=Dr-1, k on potentiaalisesti oikea avain kyseiselle kierrokselle. Pyydetään salauksia lohkopareille ja toistetaan tätä operaatiota kunnes yksi avain on valittu potentiaaliseksi avaimeksi huomattavasti useammin kuin mikään muu avain. Tämä on nyt oletettavasti avain kierrokselle r. Nyt voidaan jatkaa hyökkäystä siten että lohkopareille pyydettyjä salauksia dekryptataan aluksi yksi kierros tunnetulla avaimella. Nyt oletetaan että D pätee osittain dekryptatuille lohkopareille vähintään r-2 kierrosta ja voidaan etsiä samalla prosessilla avain kierrokselle r-1. Jatketaan kunnes kaikki kierrosavaimet on selvitetty tai niitä on tarpeeksi jäljellä olevien päättelemiseen.

Tekniikasta on monia erilaisia variaatioita ja siihen on kehitetty erilaisia parannuksia. Normaalisti hyökkääjä pyrkii käyttämään algoritmin kierrosfunktion perusteella kehitettyä menetelmää joka pystyy havaitsemaan lohkoparit (c0, c1) joille D ei taatusti ole pätenyt edelliskierrokselle asti. Tämä nopeuttaa hyökkäystä huomattavasti, sillä D yleensä pätee r-1 kierrosta vain harvoille lohkopareille. Kierrosavaimen koosta riippuen voi olla myös hyvin hyödyllistä kehittää nopea tekniikka potentiaalisten kierrosavainten löytämiseksi kaikkien avainten läpikäymisen sijaan. Tämä on verrattavissa saman salausalgoritmin murtamiseen kun r=1.

Salakirjoitustekniikka