Looking for Weak States of RC4 by Means of Waiting Tables

• Název práce v češtině: Hledání slabých stavů RC4 pomocí čekacích tabulek
• Název v anglickém jazyce: Looking for Weak States of RC4 by Means of Waiting Tables
• Klíčová slova: RC4; slabý stav; čekací tabulka; čekací cesta; čekací matice
• Klíčová slova anglicky: RC4; weak state; waiting table; waiting path; waiting matrix
• Akademický rok vypsání: 2016/2017
• Typ práce: bakalářská práce
• Jazyk práce: angličtina
• Ústav: Katedra algebry (32-KA)
• Vedoucí / školitel: prof. RNDr. Aleš Drápal, CSc., DSc.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 16.05.2017
• Datum zadání: 16.05.2017
• Datum potvrzení stud. oddělením: 25.05.2017
• Datum a čas obhajoby: 12.09.2018 10:00
• Datum odevzdání elektronické podoby: 23.07.2018
• Datum odevzdání tištěné podoby: 20.07.2018
• Datum proběhlé obhajoby: 12.09.2018
• Oponenti: Mgr. Milan Boháček

Zásady pro vypracování

Útoků na RC4 je publikováno značné množství, jde však většinou o využití různých statistických slabin (z nichž mnohé lze odstranit, protože jsou spjaty s počátečními fázemi algoritmu). Tyto útoky v práci pojednány nebudou. Práce se bude soustředit na otázku existence slabých stavů, které vytvářejí potenciálně nekonečnou posloupnost reprodukujících se stavů částečných. Tyto částečné stavy se nazývají persistentní. O jejich existenci či neexistenci se stále nic definitivního neví. Téma je obtížné a v poslední době se jím nikdo - zdá se - nezabývá. V diplomové práci Michala Hojsíka byl navržen jejich model pomocí tzv. čekacích tabulek. Periodické čekací tabulky existují, nejsou však známy žádné netriviální injektivní, přičemž právě periodické injektivní odpovídají hledaným slabým stavům. Jednou z možností, jak takové čekací tabulky hledat, je soustředit se na jejich speciální třídu tzv. sloupcově-periodických čekacích tabulek. Student popíše vazbu čekacích tabulek a šifry RC4. Dále se bude zabývat podmínkami, které musí sloupcově-periodické čekací tabulky splňovat, mají-li být injektivní. Zde se objevují zajímavé způsoby vyjádření v řeči teorie grafů. Student je popíše a bude se věnovat hledání vhodných grafů, které by mohly vést k nalezení injektivní tabulky, a to dílem obecnými nástroji, dílem počítačovými algoritmy.

Seznam odborné literatury

Itsik Mantin: Analysis of the Stream Cipher RC4, Master Thesis, The Weizmann Institute of Science, Israel, 2001.

Paul Souradyuti, Bart Preneel: Analysis of Non-fortuitous Predictive States of the RC4 Keystream Generator, Progress in Cryptology —
INDOCRYPT 2003: 4th International Conference on Cryptology in India, 2003.

Michal Hojsík: Proudová šifra RC4, diplomová práce, MFF UK 2006.

Aleš Drápal, Michal Hojsík: A riddle induced by persistent state of RC4, preprint.

Předběžná náplň práce

Předběžně domluveno s panem Čížkem.