Autor: Thomas P\u00f6ppelmann, Infineon Technologies AG Quantencomputer besitzen aufgrund ihrer Rechenleistung das Potenzial, verschiedene aktuell verwendete Verschl\u00fcsselungsalgorithmen zu brechen oder zu schw\u00e4chen. Betroffen sind insbesondere asymmetrische Kryptoverfahren wie RSA und Elliptic Curve Cryptography (ECC), welche von zahlreichen Internetstandards wie Transport Layer Security (TLS), S\/MIME, PGP und GPG genutzt werden. Abhilfe verspricht hier die Post-Quantum-Kryptographie (Post-Quantum Cryptography, PQC), bei der es sich um Verfahren handelt, die auf klassischen Computern ausgef\u00fchrt werden k\u00f6nnen, aber der Leistung von Quantencomputern standhalten. Aktuell existiert eine gro\u00dfe Zahl solcher PQC-Verfahren, welche sich bzgl. ihrer Implementierungseigenschaften stark von RSA und ECC unterscheiden.<\/strong><\/p>\n Asymmetrische kryptographische Verfahren wie RSA oder ECC sind heutzutage die Basis vieler kryptographischer Sicherheitsprotokolle. Ein bedeutendes Beispiel ist das Transport Layer Security (TLS) Protokoll, welches die Kommunikation zwischen Web-Browsern und Servern absichert, aber auch immer mehr Verbreitung im Internet der Dinge oder anderen eingebetteten Systemen findet. Aufgrund der gegen\u00fcber RSA effizienteren Arithmetik ist auf eingebetteten Systemen besonders ECC attraktiv. So ist es selbst auf einigen Mikrocontrollern grunds\u00e4tzlich m\u00f6glich, ECC ohne dedizierten Hardwarebeschleuniger auszuf\u00fchren.<\/p>\n RSA und ECC gelten dazu heute als sehr sicher, da die zugrundeliegenden mathematischen Probleme wie effizientes Faktorisieren oder das Berechnen des diskreten Logarithmus \u00fcber elliptischen Kurven auch nach Jahren der Untersuchung als schwer gelten. Allerdings hat Peter Shor bereits im Jahr 1994 einen Algorithmus vorgestellt, der RSA und ECC auf einer theoretischen Maschine – dem Quantencomputer – zu brechen vermag. Da ein leistungsf\u00e4higer Quantencomputer mittels Shors Algorithmus den privaten Schl\u00fcssel aus dem \u00f6ffentlichen Schl\u00fcssel des RSA oder ECC-Kryptosystems in Polynomialzeit extrahiert, k\u00f6nnen selbst massiv vergr\u00f6\u00dferte Parameter diesen Angriff nicht verhindern. Neben asymmetrischen Verfahren wie RSA oder ECC ist auch die symmetrische Kryptographie, wie AES oder Triple-DES, von Quantenalgorithmen betroffen. Allerdings ist ein praktischer Angriff durch den sogenannten Grover-Algorithmus weit weniger fatal, da aktuell angenommen wird, dass dieser durch das Verdoppeln der Schl\u00fcssell\u00e4nge von symmetrischen Verfahren kompensiert werden kann (z.B. Einsatz von AES-256 anstelle von AES-128).<\/p>\n Seit Jahren wird schon an der Entwicklung eines ausreichend leistungsstarken Quantencomputers gearbeitet, der neben Fortschritten bei der Kryptoanalyse auch Einsatz in der Materialentwicklung oder chemischen Simulation finden k\u00f6nnte. Um den negativen Konsequenzen f\u00fcr die Kryptographie entgegenzuwirken, arbeiten Forscher schon seit Jahren an der so genannten Post-Quantum-Kryptographie (PQC). Dabei handelt es sich um kryptographische Algorithmen, die auf klassischen Computern ausgef\u00fchrt werden, aber dabei auf mathematischen Problemen und Strukturen basieren, die selbst f\u00fcr Quantencomputer als extrem schwer l\u00f6sbar angenommen werden.<\/p>\n Trotzdem ist es eine berechtigte Fragestellung, warum man sich als praktischer Anwender oder Implementierer von Kryptographie und IT-Sicherheitsl\u00f6sungen nun Gedanken \u00fcber eine theoretische Maschine machen soll. Und weiterhin ist es richtig, dass PQC au\u00dferhalb der akademischen Welt lange Zeit ein Nischendasein f\u00fchrte und kaum beachtet wurde. Allerdings hat sich diese Situation sp\u00e4testens August 2015 durch eine Ank\u00fcndigung der National Security Agency (NSA) der Vereinigten Statten grundlegend ge\u00e4ndert. In einer Ver\u00f6ffentlichung auf ihrer Webseite k\u00fcndigte die NSA f\u00fcr die „Commercial National Security Algorithm Suite“ (CNSA Suite) an, „in the not too distant future“ auf Quantencomputer-resistente Algorithmen zu wechseln. Gleichzeitig wurden die Anforderungen bzgl. der Schl\u00fcssell\u00e4nge f\u00fcr neue geheimnisverarbeitende Computersysteme zus\u00e4tzlich versch\u00e4rft, zum Beispiel muss nun AES-256 eingesetzt werden. Auch Mitarbeiter des BSI kommen zu dem \u00e4hnlichen Schluss, dass es heute Zeit ist zu handeln [1]. Ein weiterer Vorsto\u00df kommt vom US National Institute for Standards and Technology (NIST), welches k\u00fcrzlich ein Post-Quantum-Krypto-Projekt gestartet hat. Das langfristige Ziel ist, in einem wettbewerbs\u00e4hnlichen Prozess neue Schl\u00fcsselaustausch-, Public-Key-Verschl\u00fcsselungs- und Signaturverfahren zu standardisieren. Aufgrund dieser Initiativen und der damit verbunden Disruption erscheint es au\u00dferordentlich wichtig, das Thema PQC nicht zu ignorieren, sondern aktiv zu gestalten.<\/p>\n Aktuell existieren f\u00fcnf fundamentale mathematische Probleme bzw. Klassen von Algorithmen, mit denen Post-Quantum-Kryptographie\u00a0 realisiert werden kann. Dies sind Signaturverfahren basierend auf Hashfunktionen oder dem schweren Problem multivariate quadratische Polynomgleichungen zu l\u00f6sen. Zus\u00e4tzlich existieren Public-Key Verschl\u00fcsselungs- und Schl\u00fcsselaustauschverfahren basierend auf codierungstheoretischen Problemen oder Problemen auf supersingul\u00e4ren elliptischen Kurven. Eine weitere vielversprechende Kategorie ist die sogenannte gitterbasierte Kryptographie. Mir ihr lassen sich asymmetrische Public-Key Verschl\u00fcsselungs- und Signaturverfahren realisieren, die ein hohes Sicherheitsniveaus bei moderat gro\u00dfen Schl\u00fcsseln und Chiffretexten bieten.<\/p>\n Die praktische Implementierung von PQC-Verfahren auf eingebetteten Systemen ist seit einigen Jahren Gegenstand der Forschung. Es m\u00fcssen dazu neue Wege zur effizienten Berechnung auf 8-, 16-, oder 32-Bit Prozessoren gefunden werden, da die bisherigen RSA- oder ECC-orientierten Konzepte\u00a0 nicht mehr angewandt werden k\u00f6nnen. Ein Beispiel f\u00fcr ein post-quantum Schl\u00fcsselaustauschverfahren ist das sogenannte gitterbasierte NewHope-Verfahren [2], welches von Alkim, Ducas, P\u00f6ppelmann und Schwabe entwickelt wurde. NewHope \u00a0kann aktuell verf\u00fcgbare Diffie-Hellman- oder Elliptic Curve Diffie-Hellman-basierte Schl\u00fcsselaustauschmechanismen ersetzen oder komplementieren. F\u00fcr langfristige Sicherheit erreicht NewHope nach aktuellem Stand der Forschung etwa 256 Bits an Sicherheit gegen Angriffe durch Quantencomputer. Beide Seiten m\u00fcssen f\u00fcr einen Schl\u00fcsselaustauch etwa jeweils 2048 Bytes \u00fcbertragen. Im Jahr 2016 wurde der NewHope-Algorithmus von Google in einer \u00f6ffentlichen Betaversion des Chrome-Browsers in das TLS-Protokoll integriert und erfolgreich getestet.<\/p>\n Die Ausf\u00fchrung des NewHope-Algorithmus erfordert drei Schritte. Als ersten Schritt\u00a0 generiert der Server einen \u00f6ffentlichen Schl\u00fcssel (key generation) aus einem Geheimnis, welches nur der Server kennt. Im zweiten Schritt erzeugt der Client einen \u00f6ffentlichen Schl\u00fcssel aus einem nur dem Client zug\u00e4nglichen Geheimnis. Der Client verkn\u00fcpft dann sein Geheimnis mit dem \u00f6ffentlichen Schl\u00fcssel des Servers und erzeugt den symmetrischen Sitzungsschl\u00fcssel (keygen + shared key). Im dritten Schritt erzeugt der Server mit seinem Geheimnis und dem \u00f6ffentlichen Schl\u00fcssel des Clients denselben Sitzungsschl\u00fcssel (shared key). Ein passiver Angreifer, welcher nur die Daten\u00fcbertragung verfolgt, wird durch die mathematische Komplexit\u00e4t der Schl\u00fcsselgenerierung daran gehindert, R\u00fcckschl\u00fcsse auf die individuellen Geheimnisse oder den erzeugten symmetrischen Sitzungsschl\u00fcssel zu ziehen.<\/p>\n Auf einer Intel-CPU k\u00f6nnen mittels der h\u00e4ufig verf\u00fcgbaren Vektorregister (Advanced Vector Extensions; AVX) mehrere tausend Schl\u00fcsselaustauschvorg\u00e4nge pro Sekunde berechnet werden. Eine \u00f6ffentlich verf\u00fcgbare Implementierung des NewHope-Verfahrens f\u00fcr eingebettete Systeme wurde bereits von Alkim, Jakubeit und Schwabe vorgestellt [3]. Auf einem Cortex-M0 kann dabei der „Key generation“ Schritt in 1,2 Millionen Zyklen, der „Keygen + shared key“ Schritt in 1,7 Millionen Zyklen und der „Shared key“ Schritt in 0,3 Millionen Zyklen ausgef\u00fchrt werden. Die Implementierung ist mittels Assembler-Befehlen optimiert und nutzt f\u00fcr die notwendige Polynommultiplikation einen Fast Fourier Transform (FFT)\u00a0 basierten Algorithmus. Ein weiterer wichtiger Schritt in Richtung ausreichend sicherer Implementierungen ist der Schutz gegen physikalische Angriffe. In [4] pr\u00e4sentieren Oder, Schneider und P\u00f6ppelmann eine Implementierung eines Public-Key-Verschl\u00fcsselungsverfahrens, welches NewHope \u00e4hnelt und nach aktuellem Stand 233-Bit Sicherheit bieten soll. Dabei wird durch Randomisierung der internen Daten ein gewisser Schutzlevel gegen eine Stromprofilanalyse erreicht. Auf einem Cortex-M4F ben\u00f6tigt die Verschl\u00fcsselung einer Nachricht dann 4,1 Millionen Zyklen, w\u00e4hrend die seitenkanalgesch\u00fctzte Entschl\u00fcsselung 25,6 Millionen Zyklen ben\u00f6tigt.<\/p>\n Infineon hat den NewHope-Ansatz erstmals auf einem kommerziell verf\u00fcgbaren kontaktlosen Sicherheitschip implementiert. Das belegt, dass PQC auch auf Smart-Card-Systemen mit wenig Speicher und kontaktloser Stromversorgung implementiert werden kann und somit praktikabel ist.<\/p>\n Weitere Forschungsarbeiten sind erforderlich, um vorhandene Systeme im Hinblick auf einen niedrigen Stromverbrauch, einen geringen Speicherbedarf und hohe Sicherheit zu optimieren. Infineon als f\u00fchrender Hersteller von Security ICs und Chips f\u00fcr das Internet der Dinge und die Automobilindustrie ist dabei auf mehreren Ebenen aktiv, um zuk\u00fcnftige L\u00f6sungen f\u00fcr Kunden und Anwender bereitzustellen. Die Aktivit\u00e4ten umfassen wissenschaftliche Beitr\u00e4ge, Teilnahme an der PQC-Standardisierung und prototypische Entwicklung und Forschung.<\/p>\n [1] Heike Hagemeier, Manfred Lochter:\u00a0Informationssicherheit im Quantenzeitalter<\/a>. Mit Sicherheit – BSI-Magazin 2017\/01,<\/p>\n [2] Erdem Alkim, L\u00e9o Ducas, Thomas P\u00f6ppelmann, Peter Schwabe:\u00a0Post-quantum Key Exchange – A New Hope<\/a>. USENIX Security Symposium 2016: 327-343,<\/p>\n [3] Erdem Alkim, Philipp Jakubeit, Peter Schwabe:\u00a0NewHope on ARM Cortex-M<\/a>. SPACE 2016: 332-349<\/p>\n [4] Tobias Oder, Tobias Schneider, Thomas P\u00f6ppelmann, Tim G\u00fcneysu:\u00a0Practical CCA2-Secure and Masked Ring-LWE Implementation<\/a>. IACR Cryptology ePrint Archive 2016: 1109 (2016)<\/p>\n Beitrag als PDF downloaden<\/strong><\/a><\/p>\n Wollen Sie sich auf den aktuellen Stand der Technik bringen?<\/strong><\/p>\n Dann informieren Sie sich\u00a0hier<\/strong>\u00a0<\/a>zu Schulungen\/ Seminaren\/ Trainings\/ Workshops und individuellen Coachings von MircoConsult zum Thema\u00a0Qualit\u00e4t, Safety & Security<\/strong>.<\/p>\n Training & Coaching zu den weiteren Themen unseren Portfolios finden Sie hier<\/a>.<\/strong><\/p>\n Wertvolles Fachwissen zum Thema Qualit\u00e4t, Safety & Security steht\u00a0hier\u00a0<\/a>f\u00fcr Sie zum kostenfreien Download bereit.<\/p>\n
\n<\/strong><\/p>\nBeitrag – Embedded Software Engineering Kongress 2017<\/h3>\n
Post-Quantum-Kryptographie, die NSA und NIST<\/h2>\n
Implementierung von Post-Quantum-Kryptographie<\/h2>\n
Literatur- und Quellenverzeichnis<\/h2>\n
\nUnsere Trainings & Coachings<\/h2>\n
\nQualit\u00e4t, Safety & Security – Fachwissen<\/h2>\n