V databázi přístupových údajů jsou uloženy otisky hesel ve tvaru SHA-256(heslo ∥ sůl), kde ∥ značí operátor zřetězení a sůl = 'zaqx4jcWnzMNb6KdN2vX' je stejná pro všechna hesla. Všechna hesla jsou délky 10 a skládají se ze znaků 'A',…, 'Z', 'a',…, 'z', '0',…,'9', '+', '/'.
K dispozici máme duhovou tabulku pro tuto solenou hashovací funkci. Tabulka využívá tři podobné redukční funkce. První redukční funkce převede otisk do kódování Base64 a vrátí prvních 10 znaků v tomto kódování. Druhá redukční funkce dělá totéž, ale vrací znaky na 11. až 20. pozici. Třetí redukční funkce vrací znaky na 21. až 30. pozici. Všechny řetězy zaznamenané v tabulce mají délku 300001 hesel.
Ukázka výpočtu prvního řetězu tabulky v jazyce Python zde. Duhová tabulka jako Pythonovský slovník zde.
Konec řetězu | Začátek řetězu |
---|---|
ic0CVeOSPb | demografie |
YBk/QG9ZuP | intrikarka |
SmCMFKS8Y0 | mikrofiltr |
v4otw9F01l | carodejnik |
CV9nW38uKF | podporucik |
ubvI/k2Pss | ctvernozec |
5lk5//gykJ | haplologie |
K0QeX+TkhD | hedonismus |
Le+OOdaCja | segmentace |
fsLnAGUser | isochronie |
nOOsXcwo4T | prolaklina |
kVDzF64pZo | koralnatec |
v1FfG6oH0f | maloobchod |
0zeXiuKUP+ | bikarbonat |
APPOLSUjFO | archaismus |
PiY+2iWyyT | pozitivita |
xzEak+2Irc | alchymista |
asL2okN1l2 | fosilisace |
DdG9Kl4xfh | plosinovka |
05iISBWZO7 | trampolina |
E-mailem dostanete otisk spočítaný shora uvedenou solenou hashovací funkcí. Otisk je zadaný jako posloupnost 32 bajtů v hexadecimálním zápisu. Cílem je najít heslo, které má tento otisk. (Naše duhová tabulka je sice mnohonásobně menší, než by ve skutečnosti bylo potřeba, ale dají se pomocí ní vyřešit všechny úlohy, které dostanete.)
Vzhledem k tomu, že meet-in-the-middle útok na Double DES má pro běžný domácí počítač relativně velkou časovou a paměťovou složitost, budeme pracovat s oslabenou verzí DESu, kterou nazveme DES-21. Tato verze se od DESu liší pouze omezenější množinou klíčů. Každý z posledních pěti bajtů klíče šifry DES-21 je nastavený na hodnotu 1. Klíč má tedy entropii 21 bitů. K provedení meet-in-the-middle útok na Double DES-21 stačí na domácím počítači jedna minuta výpočtů.
Ukázka šifrovacího skriptu zde.
E-mailem dostanete šifrový text c, který vznikl opakovaným zašifrováním slova "brusinka" šifrou DES-21 s dvěma nezávislými 21bitovými klíči k1 a k2. Cílem je odhalit tyto klíče.
c = DES-21(DES-21("brusinka", k1), k2)
Šifrový text dostanete zadaný jako posloupnost osmi bajtů v hexadecimálním zápisu. Odhalené klíče k1 a k2 odevzdejte také v hexadecimálním zápisu.
Úlohu doporučuji řešit v jazyce Python.
Python má zabudované dynamické pole zvané list ("seznam") a asociativní pole zvané dictionary ("slovník"). Seznam se vytvoří hranatými závorkami, mezi něž můžeme vložit inicializační data:
names = ['Homer', 'Marge', 'Bart', 'Lisa', 'Maggie']
Položky jsou indexované od nuly a přistupuje se k nim operátorem [].
Slovník se vytvoří složenými závorkami, mezi něž můžeme vložit inicializační data:
ages = {'Homer' : 36, 'Marge' : 34, 'Bart' : 10, 'Lisa' : 8, 'Maggie' : 1}
K záznamům přistupujeme také operátorem []:
print 'Bart is', ages['Bart'], 'years old.'
Podobně můžeme přidat nový záznam:
ages['Abe'] = 83
Operátorem in
lze zjistit, zda slovník obsahuje určitý záznam:
name = 'Joe'
if name in ages:
print name, 'is', ages[name], 'years old.'
else:
print name + "'s", 'age is unknown.'
Řetězce v Pythonu se vytvářejí dvojitými uvozovkami "text" anebo jednoduchými uvozovkami 'text'. Řetězce jsou objekty a mají užitečné členské funkce. Text, který dostanete zadaný v hexadecimálním zápisu, můžete převést na řetězec bajtů například takto:
ciphertext = "e5dbd0e12d279d96".decode('hex')
V situacích, kdy chcete pohodlně manipulovat s bajty, se vám bude hodit následující způsob převodu na řetězec:
str(bytearray([0xe5, 0xdb, 0xd0, 0xe1, 0x2d, 0x27, 0x9d, 0x96]))
Obě metody dávají stejný výsledek.
Pro práci s DESem musíme importovat příslušný modul:
from Crypto.Cipher import DES
Nejdříve vytvoříme objekt, kterému zadáme klíč:
objDES = DES.new(key, DES.MODE_ECB)
Ten pak můžeme použít k šifrování
ciphertext = objDES.encrypt(message)
anebo k dešifrování
message = objDES.decrypt(ciphertext)
Podrobnější dokumentace zde.