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

Lineární kryptoanalýza 2

V následujících úkolech budeme využívat text od Howarda Heyse, A Tutorial on Linear and Differential Cryptanalysis. Používáme stejnou notaci a všechny zde uvedené odkazy se vztahují k tomuto článku. Našim cílem bude provést lineární kryptoanalýzu substituční-permutační šifry popsané v oddílu 2 článku, ovšem s jiným S-boxem.

Značení

Šifra pracuje s 16-bitovými bloky a s pěti 16-bitovými rundovními klíči. Všechny tyto 16-bitové hodnoty budeme reprezentovat jako celá čísla a budeme je zapisovat v hexadecimálním zápisu. Například číslo reprezentující otevřený text (P₁,…,P₁₆) je definováno vzorcem

P₁ 2¹⁵ + P₂ 2¹⁴ + … + P₁₅ 2¹ + P₁₆ 2⁰.

Takže například 5c7e reprezentuje otevřený text (P₁,…,P₁₆) = (0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0).

Domácí úkol č. 5

E-mailem dostanete S-box zadaný jako vyhledávací tabulku, tj. stejně jako druhý řádek tabulky 1 v článku. Vašim prvním úkolem je sestavit pro tento S-box lineární aproximační tabulku (podobně jako tabulka 4 v článku).

Definujme novou šifru, která vznikne nahrazením S-boxů v šifře z článku zadaným S-boxem. Vašim druhým úkolem je najít lineární aproximace prvních tří rund této šifry s následujícími vlastnostmi:

Každá aproximace musí mít bias alespoň 0,03.
Alespoň jedna aproximace musí obsahovat vstupy do nejvýše dvou S-boxů čtvrté rundy.
Aproximace musejí dohromady obsahovat alespoň jeden vstupní bit každého ze čtyř S-boxů čtvrté rundy.

Smyslem těchto podmínek je, aby se aproximace daly pohodlně použít k útoku v dalším domácím úkolu.

Každou nalezenou aproximaci popište tak, že uvedete, jak jste aproximovali S-boxy. Například aproximaci na obrázku 3 v článku byste zapsali:

S12:B/4, S22:4/5, S32:4/5, S34:4/5.

Toto odpovídá značení v lineární aproximační tabulce 4. První položka S12:B/4 říká, že v první rundě aproximujeme druhý S-box aproximací odpovídající položce na řádku B ve sloupci 4, tj. rovnicí X₁ ⊕ X₃ ⊕ X₄ = Y₂.

V případě S-boxu použitého v článku by správným řešením úkolu byla lineární aproximační tabulka společně s například následující dvojicí aproximací:

S12:B/4, S22:4/5, S32:4/5, S34:4/5.
S12:C/2, S23:4/5, S32:2/E, S34:2/E.

První aproximace má bias 0,0312 a druhá 0,0703. První obsahuje vstupy do druhého a čtvrtého S-boxu čtvrté rundy a splňuje tedy podmínku 2. Třetí obsahuje vstupy do prvních tří S-boxů čtvrté rundy. Aproximace tedy dohromady pokrývají všechny S-boxy poslední rundy.

Doporučuji najít co nejvíc lineárních aproximací, abyste v příštím úkolu měli co největší jistotu, že jste nalezli správný rundovní klíč. Odevzdejte však jen minimální množinu aproximací splňující uvedené podmínky.

Domácí úkol č. 6

E-mailem dostanete soubor, který na každém řádku obsahuje otevřený text a příslušný šifrový text, který vznikl zašifrováním otevřeného textu šifrou z předchozího domácího úkolu. Všechny otevřené texty jsou zašifrovány stejnou pěticí rundovních klíčů. Cílem je odhalit pátý rundovní klíč, tj. závěrečný bělící klíč. Na odevzdání správného rundovního klíče máte jen jeden pokus.

Soubor obsahuje 10000 párů otevřených a šifrových textů. Na odhalení správného rundovního klíče s dostatečnou jistotou by stačilo i 500 párů, při použití více lineárních aproximací.

Poznámka. Pokud nechcete řešit předchozí úkol, ale rádi byste řešili tento úkol, napište mi e-mail a obdržíte sadu lineárních aproximací prvních tří rund šifry.

Bonus. Kdo odhalí všech pět rundovních klíčů, dostane bonbón!

Při vaší práci vám může přijít vhod tato implementace šiforvacího a dešifrovacího algoritmu.

Pro načtení dvojic otevřeného a šifrového textu ze souboru do seznamu vám poslouží následující kód:


  pclist = []

  with open("pclist.txt", "r") as f:

      for line in f:

          pclist.append([int(n, base=16) for n in line.strip().split(' ')])

Dvojice pak lze pohodlně procházet například takto:


  for plaintext, ciphertext in pclist:

      print "Otevreny text {:04x} se zasifruje na {:04x}.".format(plaintext, ciphertext)

Ukázka statistik

V první fázi jsem použil lineární aproximace prvních tří rund šifry s biasem 0,0312, abych odhalil prostředních 8 bitů pátého rundovního klíče. Výsledky jsou setříděny podle naměřeného biasu testovaných klíčů.

Rundovní klíč	Bias
?1b?	0,0314
?13?	0,0204
?19?	0,0192
?1d?	0,0184
?9b?	0,0180
?1a?	0,0174
?1f?	0,0173
…	…
?6f?	0,0069
?d2?	0,0066
?d8?	0,0066

Ve druhé fázi jsem použil lineární aproximace s biasem 0,0703, abych odhalil první 4 bity pátého rundovního klíče.

Rundovní klíč	Bias
f1b?	0,0684
b1b?	0,0508
e1b?	0,0469
21b?	0,0358
11b?	0,0358
01b?	0,0356
31b?	0,0356
51b?	0,0354
61b?	0,0352
41b?	0,0352
71b?	0,0350
d1b?	0,0341
91b?	0,0339
c1b?	0,0327
81b?	0,0325
a1b?	0,0293

V poslední fázi jsem použil lineární aproximace s biasem 0,0703, abych odhalil poslední 4 bity pátého rundovního klíče.

Rundovní klíč	Bias
f1b6	0,0809
f1b2	0,0614
f1b7	0,0597
f1bc	0,0486
f1b1	0,0481
f1bd	0,0474
f1b5	0,0446
f1b8	0,0445
f1bb	0,0444
f1b9	0,0433
f1b0	0,0421
f1bf	0,0420
f1ba	0,0413
f1b3	0,0402
f1be	0,0389
f1b4	0,0386