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

Korelační útoky

Máme kombinační generátor, který se skládá z pěti LFSR a nelineární funkce f:{0,1}⁵→{0,1}, která kombinuje výstupní bity posuvných registrů do jednoho bitu keystreamu. Výstupním bitem registru je nejvyšší bit registru. Funkce f je předepsaná jako pole délky 32. Bit keystreamu zjistíme tak, že z pěti bitů, které vystupují z registrů poskládáme celé číslo v intervalu {0, … , 31} a podíváme se na příslušnou pozici v poli. Je-li například výstupní bit prvního a třetího registru 1 a ostatní jsou 0, pak bit keystreamu je f[5], protože 5 = (00101)₂.

Vzorová implementace zde.

Příklad zpětných vazeb a funkce f:


feedback = [0x347f, 0x400100000000, 0xdf9b, 0x1eed, 0x73fb]

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

Například u druhého registru se zpětná vazba počítá jako XOR 47. a 33. bitu. Prvních 10 kroků registrů na náhodně zvolených počátečních stavech:


[0b11101010101110, 0b010110110000001 … 111, 0b1111110011001110, 0b0010111000011, 0b100001011000011]

[0b11010101011100, 0b101101100000010 … 111, 0b1111100110011100, 0b0101110000110, 0b000010110000110]

[0b10101010111001, 0b011011000000101 … 111, 0b1111001100111000, 0b1011100001100, 0b000101100001101]

[0b01010101110011, 0b110110000001011 … 111, 0b1110011001110001, 0b0111000011001, 0b001011000011010]

[0b10101011100111, 0b101100000010111 … 110, 0b1100110011100010, 0b1110000110011, 0b010110000110101]

[0b01010111001110, 0b011000000101110 … 100, 0b1001100111000100, 0b1100001100111, 0b101100001101010]

[0b10101110011100, 0b110000001011101 … 000, 0b0011001110001001, 0b1000011001110, 0b011000011010100]

[0b01011100111000, 0b100000010111010 … 000, 0b0110011100010010, 0b0000110011101, 0b110000110101001]

[0b10111001110001, 0b000000101110100 … 001, 0b1100111000100100, 0b0001100111010, 0b100001101010011]

[0b01110011100010, 0b000001011101001 … 010, 0b1001110001001001, 0b0011001110101, 0b000011010100111]

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

Domácí úkol č. 8

E-mailem dostanete funkci f, zpětné vazby registrů a 1000 bitů keystreamu. Cílem je odhalit počáteční stav dvou krátkých registrů. Stav zapište v binárním rozvoji. Na odevzdání máte jeden pokus.

Nejdříve si vyberte krátký registr s velkým biasem a odhalte jeho počáteční stav hrubou silou. Potom si vhodně vyberte druhý krátký registr a využijte výsledek předchozího kroku k odhalení jeho počátečního stavu hrubou silou. (Pokud se pokusíte odhalit hrubou silou počáteční stav dvou registrů najednou, pak pravděpodobnost, že se trefíte správně je velmi nízká, nemluvě o tom, že to bude poměrně časově náročné.)

Domácí úkol č. 9

Zadání je stejné jako v předchozím úkolu, ale cílem je odhalit počáteční stav dlouhého registru. Stav zapište v binárním rozvoji. Na odevzdání máte jeden pokus.

Bity odhadněte metodou lineárních rovnic. Lze očekávat, že se v odhadnutém stavu vyskytne okolo 5 chyb. Řešení bude uznáno v případě, že 75 % bitů bude odhadnuto správně, tj. připouští se zhruba 12 chyb.

Celý počáteční stav registru můžete odhalit bezchybně tak, že nejisté bity doděláte hrubou silou. Kdo odhalí celý stav bezchybně a zároveň při odevzdání prohlásí, že odevzdává bezchybné řešení, dostane bonbón! Prohlásíte-li však, že odevzdáváte bezchybné řešení, a budou v něm chyby, nebude řešení uznáno.

Ukázka statistik

Odhalení počátečního stavu prvního krátkého registru hrubou silou (kladná korelace):

Počet shodných bitů	Počáteční stav
670	00001001111011
561	11111011011110
560	11100001010101
557	00111111100000
556	11010111101010
556	11001111010011
555	00111011110100
554	10111011111000
554	00111011111100
554	00100001111111
…	…

Odhalení počátečního stavu druhého krátkého registru hrubou silou (záporná korelace):

Počet shodných bitů	Počáteční stav
387	0100000010010
438	1110101000100
443	0101010101111
449	0010101110011
449	1010111001100
451	0101110011111
451	1001111100111
451	1010000001100
452	0101111100100
452	1001111101011
…	…

Odhad počátečního stavu dlouhého registru metodou lineárních rovnic (kladná korelace):

Pozice udává umístění v registru. Nejvyšší bit (na pozici 46) je první bit výstupu registru. (Skóre je výsledek "hlasování", každé rovnici jsem dal 2 hlasy, každému bitu keystreamu 3 hlasy.) Nejisté bity jsou značeny červeně.

Pozice	46	45	44	43	42	41	40	39	38	37	36	35	34	33	32	31	30	29	28	27	26	25	24
Skóre	9	-9	-5	9	1	-1	-9	5	5	9	5	-13	-9	13	5	5	9	-9	-5	-5	-5	3	5
Odhad	1	0	0	1	1	0	0	1	1	1	1	0	0	1	1	1	1	0	0	0	0	1	1

Pozice	23	22	21	20	19	18	17	16	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0
Skóre	-5	-3	-13	9	-13	-13	-9	-9	-13	7	-9	9	-13	7	1	9	9	-9	-9	-13	7	-9	-13	9
Odhad	0	0	0	1	0	0	0	0	0	1	0	1	0	1	1	1	1	0	0	0	1	0	0	1

Odhalení počátečního stavu dlouhého registru hrubou silou na nejistých pozicích:

Počet shodných bitů	Počáteční stav
843	10011101111001111000011000100000101011110001001
780	10011001111001111001011000100000101011110001001
772	10011101111001111001011000100000101011110001001
767	10011101110001111000011000100000101011110001001
766	10011101110001111000011010100000101011110001001
765	10011100111001111000001000100000101011110001001
765	10011001111001111000011000100000101011110001001
763	10011101111001111000001000100000101011110001001
759	10011100111001111000011000100000101011110001001
755	10011101111001101000011000100000101011110001001
…	…