Kryptographische Systeme auf der Grundalge von fehlerkorrigierenden Codes
Final Report Abstract
Asymmetrische Verschlüsselung (PKC) ist zu einer Schlüsseltechnologie unserer Gesellschaft geworden (Gesundheitskarte, E-Reisepass, Onlinebanking, etc.). Man ist bestrebt, die Sicherheit von Kryptoverfahren auf schwierigen mathematischen Problemen aufzubauen, so daß deren Unsicherheit grundlegende mathematische Annahmen widerlegen würde. Shor's Arbeit zeigt, daß die verbreiteten zahlentheoretischen Verfahren mit Quantencomputern zu brechen wären und hat die Suche nach Alternativen reinitialisiert. Das Forschungsprojekt befasste sich mit PKCs, die auf Codierungstheorie bzw. Gittertheorie aufbauen und als resistent gegen Quantencomputer gelten. In dem geförderten Forschungsprojekt wurden insbesondere Ergebnisse in der Kryptanalyse von quantencomputerresistenten Kryptosystemen erzielt. Die erzielten Ergebnisse sind nicht nur von theoretischer Bedeutung, sondern haben direkte Auswirkungen auf die Praxis. Die zuerst veröffentlichte Arbeit beschäftigt sich mit der Einschätzung der Sicherheit des NTRU PKC. Ziel der Arbeit war es, herauszufinden in wie weit sich die Verallgemeinerung des Geburtstagsparadox auf die kombinatorischen Angriffe auf das NTRU PKC auswirkt. Überraschenderweise ermöglicht diese Verallgemeinerung einen Angriff, der zwar nicht der schnellste bekannte, aber dafür im Maß "Zeit x Speicherplatz" der effizienteste ist. Letzteres Maß wird oft zur Einschätzung der Gesamtkosten (Hardwarekosten) eines verteilten Angriffs herangezogen. Ferner wurden Sicherheitslücken im McEliece PKC betrachtet, die durch eine unbedachte Umsetzung des theoretisch sicheren Systems in die Praxis entstehen können. Es wurden Seitenkanäle in naiven Implementationen identifiziert, über die ein Angreifer Informationen erhalten und ausnutzen kann, die er nach dem theoretischen Modell nicht erhalten darf. Daraufhin wurden konkrete Abwehrmaßnahmen vorgeschlagen. Desweiteren wurde das RFID-Authentikationsverfahren HB# gebrochen, welches auf dem Problem basiert, einen unbekannten Code zu identifizieren bzw. zu korrigieren. Das Protokoll wurde durch einen Man-in-the-Middle-Angriff gebrochen, gegen welche es fälschlicherweise als sicher angenommen wurde; obwohl dies nur zum Teil bewiesen war. Ferner wurden Resultate zur Realisierung von "Oblivious Transfer" und ''blinden Signaturen" erzielt. Außerdem wurden die Arbeiten mit N. Sendrier an dem Kapitel über Codierungstherorie in dem in 2009 erscheinenden Buch über "Post-Quantum-Kryptographie" abgeschlossen.
Publications
- A multiple birthday attack on ntru. In Proc. of SECRYPT 2008, Porto, Portugal, pages 237-244, 2008
R. Overbeck
- Coding-based oblivious transfer. In Proc. of MMICS 2008, Karlsruhe, 2008
K. Kobara, K. Morozov, and R. Overbeck
- On the security of HB# against a man-in-the-middle attack. In Proc. of Asiacrypt 2008
K. Ouafi, R. Overbeck, and S. Vaudenay
- Side channels in the McEliece PKC. In PQCrypto 2008, LNCS. Springer Verlag
H.G. Molter, R. Overbeck, A. Shoufan, F. Strenzke, and E. Tews
- Chapter: Code-based cryptography. In D.J. Bernstein, J. Buchmann, and E. Dahmen, editors, Post-Quantum, Cryptography, pages 95-146, Heidelberg, Berlin, 2009. Springer Verlag
R. Overbeck and N. Sendrier
