Looking for Weak States of RC4 by Means of Waiting Tables
| Thesis title in Czech: | Hledání slabých stavů RC4 pomocí čekacích tabulek |
|---|---|
| Thesis title in English: | Looking for Weak States of RC4 by Means of Waiting Tables |
| Key words: | RC4; slabý stav; čekací tabulka; čekací cesta; čekací matice |
| English key words: | RC4; weak state; waiting table; waiting path; waiting matrix |
| Academic year of topic announcement: | 2016/2017 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | angličtina |
| Department: | Department of Algebra (32-KA) |
| Supervisor: | prof. RNDr. Aleš Drápal, CSc., DSc. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 16.05.2017 |
| Date of assignment: | 16.05.2017 |
| Confirmed by Study dept. on: | 25.05.2017 |
| Date and time of defence: | 12.09.2018 10:00 |
| Date of electronic submission: | 23.07.2018 |
| Date of submission of printed version: | 20.07.2018 |
| Date of proceeded defence: | 12.09.2018 |
| Opponents: | Mgr. Milan Boháček |
| Guidelines |
| Ú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. |
| References |
| 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. |
| Preliminary scope of work |
| Předběžně domluveno s panem Čížkem. |