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 Abstract | Language |
---|
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 |
|