TU Darmstadt / ULB / TUprints

Efficiency and Implementation Security of Code-based Cryptosystems

Strenzke, Falko (2013)
Efficiency and Implementation Security of Code-based Cryptosystems.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

[img]
Preview
Text
thesis.pdf
Copyright Information: CC BY-NC-ND 2.5 Generic - Creative Commons, Attribution, NonCommercial, NoDerivs .

Download (1MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Efficiency and Implementation Security of Code-based Cryptosystems
Language: English
Referees: Johannes, Prof. Dr. Buchmann ; Christof, Prof. Dr. Paar
Date: 28 August 2013
Place of Publication: Darmstadt
Date of oral examination: 12 November 2013
Abstract:

This thesis studies efficiency and security problems of implementations of code-based cryptosystems. These cryptosystems, though not currently used in the field, are of great scientific interest, since no quantum algorithm is known that breaks them essentially faster than any known classical algorithm. This qualifies them as cryptographic schemes for the quantum-computer era, where the currently used cryptographic schemes are rendered insecure. Concerning the efficiency of these schemes, we propose a solution for the handling of the public keys, which are, compared to the currently used schemes, of an enormous size. Here, the focus lies on resource-constrained devices, which are not capable of storing a code-based public key of communication partner in their volatile memory. Furthermore, we show a solution for the decryption without the parity check matrix with a passable speed penalty. This is also of great importance, since this matrix is of a size that is comparable to that of the public key. Thus, the employment of this matrix on memory-constrained devices is not possible or incurs a large cost. Subsequently, we present an analysis of improvements to the generally most time-consuming part of the decryption operation, which is the determination of the roots of the error locator polynomial. We compare a number of known algorithmic variants and new combinations thereof in terms of running time and memory demands. Though the speed of pure software implementations must be seen as one of the strong sides of code-based schemes, the optimisation of their running time on resource-constrained devices and servers is of great relevance. The second essential part of the thesis studies the side channel security of these schemes. A side channel vulnerability is given when an attacker is able to retrieve information about the secrets involved in a cryptographic operation by measuring physical quantities such as the running time or the power consumption during that operation. Specifically, we consider attacks on the decryption operation, which either target the message or the secret key. In most cases, concrete countermeasures are proposed and evaluated. In this context, we show a number of timing vulnerabilities that are linked to the algorithmic variants for the root-finding of the error locator polynomial mentioned above. Furthermore, we show a timing attack against a vulnerability in the Extended Euclidean Algorithm that is used to solve the so-called key equation during the decryption operation, which aims at the recovery of the message. We also present a related practical power analysis attack. Concluding, we present a practical timing attack that targets the secret key, which is based on the combination of three vulnerabilities, located within the syndrome inversion, a further suboperation of the decryption, and the already mentioned solving of the key equation. We compare the attacks that aim at the recovery of the message with the analogous attacks against the RSA cryptosystem and derive a general methodology for the discovery of the underlying vulnerabilities in cryptosystems with specific properties. Furthermore, we present two implementations of the code-based McEliece cryptosystem: a smart card implementation and flexible implementation, which is based on a previous open-source implementation. The previously existing open-source implementation was extended to be platform independent and optimised for resource-constrained devices. In addition, we added all algorithmic variants presented in this thesis, and we present all relevant performance data such as running time, code size and memory consumption for these variants on an embedded platform. Moreover, we implemented all side channel countermeasures developed in this work. Concluding, we present open research questions, which will become relevant once efficient and secure implementations of code-based cryptosystems are evaluated by the industry for an actual application.

Alternative Abstract:
Alternative AbstractLanguage

Die vorliegende Arbeit befasst sich mit Effizienz- und Sicherheitsproblemen bei der Implementierung von Code-basierten Public-Key Verschlüsselungsverfahren. Diese Verfahren, obwohl derzeit nicht in Verwendung, sind von großem wissenschaftlichen Interesse, da kein Quantenalgorithmus bekannt ist, der diese entscheidend effizienter brechen kann als ein klassischer Algorithmus. Dies macht sie zu Kandidaten für die Quantencomputerära, in der die heute verwendeten Public-Key Verschlüsselungsverfahren unsicher werden.

Bezüglich der Effizienz wird eine Lösung für die Handhabung der bei dieser Art von Verfahren im Vergleich mit den heute im Einsatz befindlichen extrem großen öffentlichen Schlüsseln vorgestellt. Dabei liegt der Fokus auf ressourcenbeschränkten Geräten, die nicht in der Lage sind, den öffentlichen Schlüssel eines Kommunikationspartners im flüchtigen Speicher zu halten. Ferner wird eine Lösung aufgezeigt, mit der die Entschlüsselung auch ohne die Parity Check Matrix mit vertretbaren Geschwindigkeitseinbußen möglich ist. Dies ist ebenso von großer Bedeutung, da diese Matrix von vergleichbarer Größe ist wie der öffentliche Schlüssel, und somit eine Verwendung derselben auf speicherarmen Geräten nicht möglich oder mit hohen Kosten verbunden ist.

Es wird auch eine Untersuchung zur Verbesserung der Laufzeit der im Allgemeinen rechenintensivsten Teiloperation bei der Entschlüsselung, dem Finden der Nullstellen des Fehlerlokatorpolynoms, vorgestellt. Hierbei werden verschiedene bekannte algorithmische Varianten und neue Kombinationen derselben in Bezug auf Laufzeit und Speicheranforderungen verglichen. Obwohl die Geschwindigkeit reiner Softwareimplementierungen gerade als eine der Stärken der Code-basierten Verfahren angesehen werden muss, ist die Optimierung der Laufzeit sowohl auf ressourcenbeschränkten Plattformen als auch auf Servern von großer Relevanz.

Der zweite wesentliche Teil der Arbeit befasst sich mit der Seitenkanalsicherheit dieser Verfahren. Seitenkanalschwachstellen bedeuten, dass ein Angreifer während einer kryptographischen Operation durch die Messung physikalischer Größen wie der Laufzeit der Berechnung oder der Leistungsaufnahme des Geräts während der Operation Informationen über an der Berechnung beteiligte geheime Informationen erhält. Dabei werden Angriffe auf die Entschlüsselungsoperation betrachtet, die entweder auf die Rekonstruktion der Nachricht oder des geheimen Schlüssels abzielen, und in den meisten Fällen konkrete Gegenmaßnahmen vorgeschlagen und evaluiert. In diesem Zusammenhang werden eine Reihe von Laufzeitschwachstellen aufgezeigt, welche mit manchen der bereits oben erwähnten algorithmischen Varianten für das Finden der Nullstellen des Fehlerlokatorpolynoms zusammenhängen. Des Weiteren wird ein Laufzeitangriff gegen eine Schwachstelle des bei der Entschlüsselung verwendeten erweiterten Euklidischen Algorithmus zur Lösung der sogenannten Key Equation vorgestellt, der auf die Rekonstruktion der Nachricht abzielt. Hierzu wird auch eine praktische Leistungsaufnahmeattacke vorgeführt. Schließlich wird eine praktische Laufzeitattacke zur Rekonstruktion des geheimen Schlüssels vorgestellt, die auf der Kombination von drei Schwachstellen innerhalb der Syndrominvertierung, einer weiteren Teiloperation der Entschlüsselung, und der schon erwähnten Lösung der Key Equation beruht.

Die Angriffe, die die Rekonstruktion der Nachricht zum Ziel haben, werden mit ihrem Analogon für das RSA Public Key Verschlüsselungsverfahren verglichen, und es wird eine allgemeine Methodologie für das Auffinden der in solchen Fällen zugrunde liegenden Schwachstellen entwickelt.

Ferner werden zwei Implementierungen des Code-basierten McEliece Verschlüsselungsverfahrens vorgestellt: Eine Smartcard-Implementierung und eine auf einer quelloffenen PC Implementierung basierende flexible Implementierung. Die bestehende quelloffene Implementierung wurde dahingehend erweitert, dass sie plattformunabhänig wurde und für ressourcenbeschränkte Geräte optimiert wurde. Außerdem wurden dort alle in dieser Arbeit vorgestellten algorithmischen Varianten integriert, für die jeweils alle relevanten Performanzdaten wie Laufzeit, Code-Größe und Speicherverbrauch auf einem eingebetteten System vorgestellt werden. Ferner wurden die erarbeiteten Seitenkanalgegenmaßnahmen implementiert.

Zuletzt werden in dieser Arbeit offen bleibende Forschungsfragen vorgestellt, die Relevanz erhalten werden, sobald effiziente und sichere Implementierungen Code-basierter Verfahren von der Industrie für den Einsatz evaluiert werden.

German
Uncontrolled Keywords: Post-Quantum Cryptography, Code-based Cryptography, Side Channel Attacks, Efficient Implementation
Alternative keywords:
Alternative keywordsLanguage
Post-Quantum Kryptographie, Code-basierte Kryptographie, Seitenkanalangriffe, Effiziente ImplementierungGerman
URN: urn:nbn:de:tuda-tuprints-36908
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science
Date Deposited: 06 Dec 2013 11:20
Last Modified: 06 Dec 2013 11:20
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/3690
PPN: 334460174
Export:
Actions (login required)
View Item View Item