Domácí úkoly z předmětu Kryptoanalytické útoky

Algebraické útoky

Máme filtrový generátor, který se skládá z jednoho LFSR délky 56 a nelineární booleovské funkce f, která v každém kroku kombinuje čtyři bity posuvného registru do jednoho bitu keystreamu. Funkci f máme předepsanou v algebraické normální formě, kde x₀ značí nejnižší bit registru. Ve vzorové implementaci máme funkci f navíc předepsanou jako pole délky 16. Bit keystreamu se zjistí tak, že ze 4 bitů na daných pozicích v registru poskládáme celé číslo v intervalu {0, … , 15} a podíváme se na příslušnou pozici v poli.

Vzorová implementace zde.

Příklad zpětné vazby:


feedback = 0xccfe77fa1013cb

Příklad funkce f v algebraické normální formě:


f(u_0, ..., u_55) = u_1 + u_9 u_22 + u_1 u_9 u_22 + u_33 + u_9 u_33

Příklad téže funkce zadané pomocí pole:


bits = [1, 9, 22, 33]

f = [0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1]

Prvních 10 kroků registru na náhodně zvoleném počátečním stavu:


0b00101001000010001010001110000011101000010010100011100000

0b01010010000100010100011100000111010000100101000111000001

0b10100100001000101000111000001110100001001010001110000010

0b01001000010001010001110000011101000010010100011100000100

0b10010000100010100011100000111010000100101000111000001000

0b00100001000101000111000001110100001001010001110000010001

0b01000010001010001110000011101000010010100011100000100010

0b10000100010100011100000111010000100101000111000001000101

0b00001000101000111000001110100001001010001110000010001011

0b00010001010001110000011101000010010100011100000100010110

keystream = [1, 1, 1, 0, 0, 0, 1, 0, 0, 0, … ]

Domácí úkol č. 10

E-mailem dostanete funkci f, zpětnou vazbu registru a 1600 bitů keystreamu. Cílem je odhalit počáteční stav registru. Stav zapište v binárním rozvoji.

Začněte tím, že z algebraické normální formy funkce f sestrojíte booleovskou rovnici stupně 2 podobně, jako v útoku na Toyocrypt. Potom sestrojte soustavu rovnic pro bity počátečního stavu registru. Termy stupně 2 přepište na nové proměnné, abyste získali soustavu lineárních rovnic. K řešení soustavy můžete použít jeden z postupů zde, anebo postup uvedený níže.

Vhodné nástroje v Mathematice

Vytvoření seznamu z řádků souboru:

ReadList["nazev_souboru"]

Roznásobení polynomů:

Expand[seznam_polynomu]

Přepsání druhých mocnin proměnných na první mocniny:

seznam_polynomu /. a_^2 -> a

Redukce koeficientů polynomů modulo 2:

PolynomialMod[seznam_polynomu, 2]

Přepsání termů stupně 2 na nové proměnné, např. součin x1 * x2 se přepíše na proměnnou x1x2:

seznam_polynomu /. Times[a_, b_] :> Symbol[SymbolName[a] <> SymbolName[b]]

Vyřešení seznamu rovnic modulo 2 (seznam polynomů pokládáme roven seznamu nul):

solution = Solve[seznam_polynomu == Table[0, {Length[seznam_polynomu]}], Modulus -> 2]

Funkce Solve vrací seznam přepisovacích pravidel. Pro čitelnější výstup si můžete vytvořit seznam jednoduchých proměnných {x55, x54, …, x0} a nechat ho přepsat:

Table[Symbol["x" <> ToString[i]], {i, 55, 0, -1}] /. solution

Jednoduchý příklad s čtyřbitovým registrem

Zadání:


feedback = 0x9

f(u_0, ..., u_3) = u_1 + u_0 u_1 + u_0 u_2 + u_3 + u_0 u_2 u_3

bits = [0, 1, 2, 3]

f = [0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1] 

keystream = [1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0]

Z f sestrojíme booleovskou rovnici stupně 2:

(keystream[i] + u1 + u3) (1 + u0) == 0

Bity vystupující z registru popíšeme jako kombinace bitů počátečního stavu registru:

x3
x2
x1
x0
x0 + x3
x0 + x2 + x3
x0 + x1 + x2 + x3
x1 + x2 + x3
x0 + x1 + x2
x1 + x3
x0 + x2
x0 + x1 + x3
x2 + x3
x1 + x2
x0 + x1
…

Dosazením sestrojíme soustavu rovnic pro bity počátečního stavu registru:


(1 + x1 + x3) (1 + x0) == 0

(x0 + x2) (1 + x0 + x3) == 0

(1 + x0 + x1 + x3) (1 + x0 + x2 + x3) == 0

(1 + x2 + x3) (1 + x0 + x1 + x2 + x3) == 0

(1 + x1 + x2) (1 + x1 + x2 + x3) == 0

(1 + x0 + x1) (1 + x0 + x1 + x2) == 0

(1 + x3) (1 + x1 + x3) == 0

(1 + x2) (1 + x0 + x2) == 0

x1 (1 + x0 + x1 + x3) == 0

(1 + x0) (1 + x2 + x3) == 0

(x0 + x3) (1 + x1 + x2) == 0

(x0 + x2 + x3) (1 + x0 + x1) == 0

Roznásobíme a termy stupně 2 přepíšeme na nové proměnné:


1 + x0 + x0x1 + x0x3 + x1 + x3 == 0

x0x2 + x0x3 + x2 + x2x3 == 0

1 + x0 + x0x1 + x0x2 + x1 + x1x2 + x1x3 + x2 + x2x3 + x3 == 0

1 + x0 + x0x2 + x0x3 + x1 + x1x2 + x1x3 + x2 + x3 == 0

1 + x1 + x1x3 + x2 + x2x3 + x3 == 0

1 + x0 + x0x2 + x1 + x1x2 + x2 == 0

1 + x1 + x1x3 + x3 == 0

1 + x0 + x0x2 + x2 == 0

x0x1 + x1x3 == 0

1 + x0 + x0x2 + x0x3 + x2 + x3 == 0

x0 + x0x1 + x0x2 + x1x3 + x2x3 + x3 == 0

x0x1 + x0x2 + x0x3 + x1x2 + x1x3 + x2 + x3 == 0

Soustava má jediné řešení:

x0 = 1, x0x1 = 0, x0x2 = 1, x0x3 = 1, x1 = 0, x1x2 = 0, x1x3 = 0, x2 = 1, x2x3 = 1, x3 = 1.

Tedy počáteční stav byl 0b1101.