Details

Abstrakt in Englisch

The Tactile Internet will enable interactive real-time applications in industry and society. Proposed applications require, first, an end-to-end latency of about one millisecond, and second, stringent security. Data authentication is an important pillar for this security objective. Digital signatures provide data authentication, but with quantum computers looming at the horizon, most currently employed signature schemes will become unsecure. Hash-based digital signatures have been proposed as post-quantum secure alternative. These schemes are computationally expensive, leading to processing times that contradict the low-latency requirements of the Tactile Internet. This thesis develops a framework to understand, assess, and minimize the end-to-end latency of selected hash-based signatures. We argue for the use of the eXtended Merkle Signature Scheme (XMSS), a postquantum secure algorithm with well-established security margins. For different architectural classes, we establish a performance baseline and assess the gap between our targeted latency budget of 100μs for data authentication and state-of-the-art XMSS implementations. High-end desktop processors utilizing vector extensions are above the target by a factor of 33. A hardware accelerator for embedded applications employing a hardware/software co-design is above target by a factor of 270. Pure software implementations on embedded processors miss by three orders of magnitude. A thorough bottleneck analysis using our enhanced call graph method identifies computational intensive parts of the algorithm, and allows us to focus our later optimizations on the critical processing steps: the authentication path computation, the production of hashes and hash chain nodes, and the processing of hash chains. A comprehensive data dependency analysis studies which XMSS operations can be processed independently. We find that the authentication path computation can be taken out of the critical latency path altogether. By exploiting this, our developed EarlyAuth scheme improves the latency significantly and achieves a speedup of about 4.23 as compared to the XMSS reference implementation. As software optimizations are insufficient to achieve the required performance, we design an application-specific integrated processor based on the Tensilica LX6 architecture. Using a hardware/software-codesign approach, we develop a generic accelerator for the underlying hash function which constitutes the main bottleneck of the XMSS signing and verification procedures. Although a speedup of 183 over the reference implementation could be achieved, with 440μs for signing alone, this generic architecture fails to meet our latency objective. Our instruction histogram analysis reveals that memory accesses require 51 percent of all cycles of the hash chain node computation. To mitigate these memory loads, we refine the architecture to take the specifics of XMSS into account. This improved design employs a result shift mechanism, a hardware padding generator, and tailored buffers designed to minimize memory operations. Although the cycles for memory loads are reduced to 7 percent, the performance is still insufficient. Further analysis reveals that the hash permutation function emerges as the new bottleneck and requires over 79 percent of the chain node computation cycles. We alleviate this by introducing a hardware unrolling scheme and optimize the trade-offs with respect to area-time and area-time-energy products. Our fastest architecture achieves a minimal total processing time for signing and verification of 265μs. Together with the EarlyAuth scheme, latencies below 100μs become viable. Finally, we develop an end-to-and latency model that not only takes the signing and verification times into account, but also the data transmission times of message and signature. With this model, we analyze achievable end-to-end latencies and perform XMSS parameter optimizations. In addition, we derive a lower bound for the achievable XMSS end-to-end latency as a tool for design space exploration. Our derived latency efficiency metric relates the latency achieved by an actual design to the lower bound. This allows for comparison of different XMSS implementations. We present a comprehensive set of analysis tools, implementation methods, and models, that aim to optimize the end-to-end latency of data authentication from an application perspective. Only the combination of all developed software and hardware optimizations makes it possible to achieve our latency objective. We improve the state of the art by up to two orders of magnitude and widen the envelope of viable secure applications for the Tactile Internet.

Abstrakt in Deutsch

Das Taktile Internet wird interaktive Echtzeitanwendungen in Industrie und Gesellschaft ermöglichen. Vorgeschlagene Anwendungen erfordern erstens, eine Ende-zu-Ende-Latenz von etwa einer Millisekunde und zweitens, eine sehr hohe Sicherheit. Die Datenauthentifizierung ist ein wichtiger Grundpfeiler für dieses Sicherheitsziel. Datenauthentifizierung wird mittels digitaler Signaturen sichergestellt, jedoch wird ein Großteil der derzeit verwendeten Signaturverfahren durch die sich abzeichnenden zukünftigen Quantencomputer gebrochen werden. Hash-basierte digitale Signaturen gelten als post-quanten-sichere Alternative, da Quantencomputer hier ihre Vorteile nicht ausspielen können. Diese Verfahren sind rechenintensiv, was zu Verarbeitungszeiten führt, die im Widerspruch zu den Latenzanforderungen des taktilen Internets stehen. Die vorliegende Arbeit entwickelt ein Framework, um die Ende-zu-Ende-Latenz zu verstehen, zu bewerten und sie für ausgewählte Hash-basierte Signaturen zu minimieren. Wir plädieren für die Verwendung des eXtended Merkle Signature Scheme (XMSS), einem post-quanten-sicheren Algorithmus mit gut erforschten Sicherheitsmargen. Für verschiedene Architekturklassen ermitteln wir einen Performanz-Referenzwert und bewerten die Lücke zwischen unserem angestrebten Latenzbudget von 100 μs für die Datenauthentifizierung und dem Stand dem Stand der Technik von XMSS-Implementierungen. High-End-Desktopprozessoren, die Vektorerweiterungen nutzen, liegen um den Faktor 33 über dem Zielwert. Ein Hardwarebeschleuniger für eingebettete Anwendungen, der ein Hardware/Software-Co-Design verwendet, liegt um den Faktor 270 über der Ziellatenz. Reine Softwareimplementierungen für eingebetteten Prozessoren verfehlen das Ziel um drei Größenordnungen. Eine ausführliche Engpassanalyse identifiziert mithilfe unserer erweiterten Call-Graph-Methode rechenintensive Teile des Algorithmus und ermöglicht es uns, unsere späteren Optimierungen auf die kritischen Verarbeitungsschritte zu konzentrieren: die Berechnung des Authentifizierungspfads, die Erzeugung von Hashes und Hashkettenknoten und die Verarbeitung von Hashketten. Eine umfassende Datenabhängigkeitsanalyse untersucht, welche XMSS-Operationen unabhängig voneinander verarbeitet werden können. Wir stellen fest, dass die Berechnung des Authentifizierungspfads aus dem kritischen Latenzpfad herausgenommen werden kann. Indem wir dies ausnutzen, verbessert unser entwickeltes EarlyAuth-Schema die Latenzzeit signifikant und erreicht einen Speedup von etwa 4,23 im Vergleich zur XMSS-Referenzimplementierung. Da Softwareoptimierungen allein nicht ausreichen, um die geforderte Leistung zu erreichen, entwerfen wir auf Basis der Cadence Tensilica LX6 Architektur einen anwendungsspezifischen integrierten Prozessor. Mithilfe eines Hardware/Software-Codesign-Ansatzes entwickeln wir einen generischen Beschleuniger für die zugrundeliegende Hashfunktion, die den Engpass der XMSS-Signier- und Verifikationsoperationen darstellt. Obwohl ein Speedup von 183 gegenüber der Referenzimplementierung erreicht werden konnte, erfüllt diese generische Architektur, mit 440 μs für das Signieren allein, nicht unser Latenzziel. Unsere Instruktionshistogrammanalyse zeigt, dass Speicherzugriffe 51 Prozent aller Taktzyklen der Hashkettenknotenberechnung benötigen. Um diese Speicherbelastung zu verringern, verfeinern wir die Architektur unter Ausnutzung spezifischer Eigenheiten von XMSS. Dieses verbesserte Design verwendet einen Result-Shift-Mechanismus, einen Hardware-Padding-Generator und maßgeschneiderte Datenpuffer, um die Speicheroperationen zu minimieren. Obwohl die Zyklen für Speicherzugriffe auf 7 Prozent reduziert werden, ist die Leistung immer noch unzureichend. Eine weitere Analyse zeigt, dass sich die Hash-Permutationsfunktion als neuer Engpass herausstellt und über 79 Prozent aller Taktzyklen für die Berechnung der Kettenknoten benötigt. Dies können wir durch Einführung eines Hardware-Unrolling-Schemas abmildern und optimieren sich ergebende Parameter durch Abwägungen der Fläche×Zeit und Fläche×Zeit×Energie-Produkte. Unsere schnellste Architektur erreicht eine minimale Gesamtverarbeitungszeit für Signierung und Verifizierung von 265 μs. Zusammen mit dem EarlyAuth-Schema werden Latenzen unter 100 μs realisierbar. Zudem entwickeln wir ein Ende-zu-Ende-Latenz-Modell, das nicht nur die Signier- und Verifikationszeiten berücksichtigt, sondern auch die Datenübertragungszeiten von Nachricht und Signatur mit einbezieht. Mit diesem Modell analysieren wir die erreichbaren Ende-zu-Ende-Latenzen und führen Optimierungen der XMSS-Parameter durch. Darüber hinaus leiten wir eine untere Schranke für die erreichbare Ende-zu-Ende-Latenz von XMSS ab, die als Werkzeug für die Entwurfsraumexploration dient. Unsere abgeleitete Latenz-Effizienz-Metrik setzt die durch ein tatsächliches Design erreichte Latenz zur unserer hergeleiteten theoretischen unteren Schranke in Beziehung. Dies ermöglicht den Vergleich verschiedener XMSS-Implementierungen. Wir präsentieren einen umfassenden Satz von Analysewerkzeugen, Implementierungsmethoden und Modellen, die darauf abzielen, die Ende-zu-Ende-Latenz der Datenauthentifizierung aus Anwendungsperspektive zu optimieren. Erst durch Kombination aller entwickelten Software- und Hardwareoptimierungen ist es möglich, unser Latenzziel zu erreichen. Wir verbessern den Stand der Technik um bis zu zwei Größenordnungen und erweitern so den Bereich der realisierbaren sicheren Anwendungen für das Taktile Internet.