4. sada úloh (celkem 22b, max 16b za tuto sadu)

Úloha 1 (6 bodů)

Předpokládejme, že máme šifru lDES, která se od šifry DES liší pouze v tom, že používá jiné S-boxy. A to takové, že každý S-box $S:\mathbb{Z}^6_2 \rightarrow \mathbb{Z}^4_2$ šifry lDES je lineární. Dokažte, že šifra lDES je afinní v klíči i plaintextu, neboli \[ \forall k_1,\,k_2,\,p \in \mathbb{Z}^{64}_2: lDES_{k_1+k_2}(0) = lDES_{k_1}(p) + lDES_{k_2}(p) \] \[ \forall p_1,\,p_2,\,k \in \mathbb{Z}^{64}_2: lDES_{0}(p_1+p_2) = lDES_{k}(p_1) + lDES_{k}(p_2) \] Zkuste to třeba tak, že afinitu dokážete pro základní funkce (bitová rotace, bitový výběr, přičtení klíče), potom pro části šifry (odvození klíče, Feistelova funkce, runda) a nakonec pro celou šifru. Využijte toho, že funkce je lineární nad $\mathbb{Z}_2$, pokud každý výstupní bit funkce je lineární kombinací vstupních bitů.

Úloha 2 (2 + 2 body)

Napište funkci invert, která najde v tělese $\mathbb{Z}_2[x]/(x^8+x^7+x^2+x+1)$ pro prvek, který dostane jako parametr, jeho inverz. Pokud inverz pro tento prvek neexistuje, pak vyhodí chybu. Prvky tohoto tělesa na vstupu/výstupu budou reprezentovány jako 8-bitové číslo (podobný trik jako u Rijndael S-boxu šifry AES).
Uvažme Rijndael S-box šifry AES nad tímto tělesem (tj. matice zůstává, jen výpočet inverzu bude jiný). Zjistěte, jakou hodnotu dostaneme z tohoto S-boxu, když na jeho vstupu bude číslo 0xf3. Na tuto část můžete (ale nemusíte) využít funkci invert z předchozího odstavce.

Pozn.: Hlavička funkce by měla býti následující (opět C# notace, jiné jazyky analogicky):
byte invert(byte element)

Úloha 3 (0 + 6 bodů)

export2DES Klíčem této šifry je blok o šesti bajtech \[ k_1:k_2:k_3:k_4:k_5:k_6 \] takový, že jednotlivé bajty $k_i$ mají lichou paritu (tedy lichý počet bitů s hodnotou jedna). Šifrování probíhá následovně: Nejprve jsou odvozeny klíče \[ a=k_1:k_2:k_3:01:01:01:01:01 \] \[ b=k_4:k_5:k_6:01:01:01:01:01 \] Ciphertextem plaintextu $p$ je potom $DES^{-1}_b(DES_a(p))$.

Plaintext (hexadecimálně) 00:01:02:03:04:05:06:07 byl šifrou export2DES zašifrován na B0:20:23:51:D7:0E:AF:D7. Najděte odpovídající klíč.
Na této stránce najdete návod, jak implementovat DES v různých programovacích jazycích. Upozorňuji, že útok může, v závislosti na jeho implementaci a zvoleném programovacím jazyce, trvat i několik minut.

PKCS #7 padding Standard RFC 2315 PKCS#7 definuje padding takto:

Some content-encryption algorithms assume the input length is a multiple of k octets1, where $k>1$, and let the application define a method for handling inputs whose lengths are not multiple of k octets. For such algorithms, the method shall be to pad the input at the trailing end with $k-(l\ mod\ k)$ octets all having value $k - (l\ mod\ k)$, where l is the length of the input.

Mějme blokovou šifru s blokem délky 8 bajtů, tedy $k=8$. Přidání paddingu vypadá takto: \[ AA:BB:CC:DD:EE:FF \mapsto AA:BB:CC:DD:EE:FF:02:02. \] Všimněte si, že padding je do zprávy přidán i v případě, že délka zprávy je násobkem délky bloku. V tomto případě je za poslední blok zprávy vložen padding \[ 08:08:08:08:08:08:08:08 \]

Úloha 4 (1 bod)

Ze standardu jsem vypustil jedno omezení pro k. Dokážete přijít na to jaké?

Úloha 5 (2 body)

Ukažte, že neexistují dvě různé zprávy, které by se shodovaly po přidání paddingu.

Úloha 6 (3 body)

Předpokládejme, že blok má délku 8 bajtů. Jaká je pravděpodobnost, že uniformně náhodně zvolená zpráva o dvou blocích bude mít korektní padding? Kolik bajtů bude padding nejpravděpodobněji mít?

1. Osmice bitů, tedy jeden bajt.