Testen ist ein integraler Bestandteil bei der Entwicklung von Software aller Art, und dies gilt insbesondere für kryptografische Software, wie die im Rahmen des QUASIKOM-Projekts erstellte Implementierung von NTRU. Moderne asymmetrische kryptografische Algorithmen, wie z.B. RSA, Elliptische-Kurven-Kryptografie oder eben auch NTRU, basieren auf soliden mathematischen Grundlagen und können somit (zumindest theoretisch) extrem hohe Sicherheitsanforderungen erfüllen. Das "Brechen" solcher kryptografischen Algorithmen erfordert nämlich das Lösen von gewissen mathematischen Problemen, die so schwierig sind, dass dazu extremer Rechenaufwand notwendig wäre. Neben dem Algorithmus selbst bestimmen auch die verwendeten Parameter (z.B. die Schlüssellänge) die tatsächliche Sicherheit. Diese Parameter werden üblicherweise so gewählt, dass sie eine Sicherheit von 128 Bit garantieren, wodurch zum "Knacken" der Verschlüsselung ein Rechenaufwand von 2^128 bzw. 3.4*10^38 Operationen erforderlich wird, was praktisch nicht realisierbar ist. Die zurzeit besten Supercomputer der Exascale-Klasse, wie z.B. der chinesische Tianhe-3, erreichen eine Leistung von einer Trillion (d.h. 10^18) Operationen pro Sekunde. Selbst wenn ein Angreifer eine Million solcher Exascale-Supercomputer zur Verfügung hätte, und somit eine Quadrillion (d.h. 10^24) Rechenoperationen pro Sekunde ausführen könnte, würde es immer noch über 10 Millionen Jahre dauern, einen geheimen Schlüssel zu berechnen. Bei gewissen kryptografischen Algorithmen wie z.B. NTRU erbringt selbst der Einsatz von Quantencomputern keine Verkürzung der Rechenzeit.

Aufgrund ihrer hohen mathematischen Garantien bilden asymmetrische kryptografische Algorithmen das Fundament von so gut wie allen sicherheitskritischen Programmen und Systemen, und werden oft als unfehlbar angesehen. Der Weg von mathematischen Gleichungen zu korrekt implementierter Software ist jedoch äußerst mühsam und es gibt viele Hindernisse und Stolpersteine zu überwinden, was selbst für Profis mit jahrzehntelanger Erfahrung alles andere als einfach ist. Programmierfehler betreffen jegliche Art von Software und können zur Folge haben, dass ein Programm nicht die korrekten Ergebnisse liefert oder sogar abstürzt. Bei kryptografischer Software kann ein Bug noch weit schwerwiegendere Probleme mit sich bringen und es im schlimmsten Fall einem Angreifer sogar ermöglichen, mit relativ geringem Aufwand den verwendeten geheimen Schlüssel ausfindig zu machen. Nachdem kryptografische Algorithmen das Fundament der Sicherheit darstellen, haben Konstruktions- oder Implementationsfehler bei kryptografischer Software oft katastrophale Auswirkungen und können die Sicherheit einer Applikation bzw. Systems wie ein Kartenhaus zusammenbrechen lassen. Tatsächlich gab es in den letzten Jahren einige spektakuläre Fälle, in denen fehlerhafte Implementierungen von kryptografischen Algorithmen für weltweite Schlagzeilen sorgten. Ein schon etwas länger zurückliegendes Beispiel ist ein Fehler in Signatur-Software für die Sony PlayStation 3 (PS3), der dazu führte, dass das Sicherheitssystem der PS3 (inklusive Kopierschutz von PS3-Spielen) komplett ausgehebelt werden konnte, was für Sony neben riesigen finanziellen Schäden auch noch einen erheblichen Imageverlust zur Folge hatte. Im April 2014 wurde eine kritischer Schwachstelle namens "Heartbleed" in der TLS-Software OpenSSL bekannt, die es einem Angreifer ermöglicht, auf den Hauptspeicher des jeweiligen Systems zuzugreifen und so im schlimmsten Fall heikle Userdaten wie etwa Passwörter oder geheime Schlüssel auszuspähen. Aufgrund der großen Verbreitung von OpenSSL in Webservern wie z.B. Apache waren weltweit ungefähr eine halbe Million Websites betroffen, darunter einige zig-tausend in Österreich. Ebenfalls im Jahr 2014 veröffentliche Apple die ersten Details über einen als "Gotofail" bezeichneten Programmierfehler in der TLS-Software des Betriebssystems iOS7, dass auf Millionen von Apple Computern, Notebooks, Tablets und Smartphones installiert war. Dieser Programmierfehler besteht aus einer überflüssigen Goto-Anweisung und bewirkt, dass die Zertifikatsüberprüfung für TLS-Verbindungen umgangen werden kann. Dadurch werden auch ungültige Zertifikate akzeptiert, was eine sicher geglaubte Verbindung anfällig für sogenannte Man-in-the-Middle-Angriffe macht und somit abgehört werden kann.

Die oben genannten Beispiele zeigen eindrucksvoll, dass das Testen und Debuggen von kryptografischer Software alles andere als einfach ist, selbst für internationale Großkonzerne wie Sony und Apple. Um solche und ähnliche Fehler zu entdecken und korrigieren, wurde die im Rahmen des QUASIKOM-Projekts entwickeltes Software ausführlichen Tests auf Komponenten-, Modul- und Systemebene unterzogen. Zusätzlich wurde der gesamte Source-Code mit Werkzeugen zur statischen Code-Analyse, insbesondere Splint, untersucht und potentielle Speicherfehler (z.B. ungültige Speicherzugriffe, inkorrekte Freigabe von dynamisch-bereitgestelltem Speicher, Memory Leaks) mit Hilfe von Valgrind aufgespürt. Insgesamt wurde für das Testen ungefähr 30% der gesamten Entwicklungszeit aufgewendet. Bei den zuvor erwähnten Tests auf Komponenten-, Modul- und Systemebene wurden jeweils drei verschiedene Eigenschaften untersucht, nämlich Funktionalität, Performance, und Robustheit. Funktionalitätstests sind der übliche Ansatz zur Überprüfung der Korrektheit von Software, wobei die zu testenden Funktionen und Module nur mit gültigen Eingaben (d.h. Parametern die der Spezifikation entsprechen) "gefüttert" werden. Im Gegensatz dazu kommen bei Robustheitstests (engl. Fuzzing) absichtlich ungültige Eingabewerte bzw. Parameter zum Einsatz, um zu prüfen, ob diese erkannt und abgefangen werden, bevor sie Unheil anrichten können. Bei Performancetests wird die Ausführungszeit von Funktionen in Abhängigkeit der Größe der Parameter (z.B. Ordnung der Polynome bei NTRU) bestimmt. Diese Tests spielen eine wesentliche Rolle bei kryptografischer Software, da mit ihrer Hilfe Schwachstellen aufgespürt werden können, die eine Implementierung anfällig für sogenannte Timing-Attacken machen. Bei einer Timing-Attacke wird die Ausführungszeit eines implementierten kryptografischen Algorithmus für verschiedene (in der Regel vom Angreifer gewählte) Eingaben analysiert. Aufgrund von Performance-Optimierungen hat eine Implementierung üblicherweise leicht voneinander abweichende Laufzeiten wenn unterschiedliche Eingaben verarbeitet werden. Diese Unterschiede in der Ausführungszeit hängen oft nicht nur von den Eingabedaten (z.B. dem zu verschlüsselten Klartext) ab, sondern auch vom geheimen Schlüssel. Durch aufwändige statistische Analysen der Laufzeitunterschiede kann ein Angreifer den geheimen Schlüssel extrahieren oder zumindest den Suchraum für den geheimen Schlüssel reduzieren.

Alle im Rahmen des Projekts entwickelten Low-Level-Funktionen für Polynom-Arithmetik wurden ausführlichen Performancetests unterzogen, um so Laufzeitunterschiede aufzuspüren, die direkt oder indirekt vom geheimen Schlüssel abhängen. Dabei wurde festgestellt, dass eine normale C-Implementierung der Modulo-3-Reduktion anfällig für Timing-Attacken ist. Wie im letzten Blogeintrag erklärt, müssen gewisse Koeffizienten bei der in NTRU verwendeten Polynom-Arithmetik modulo einem sogenannten "kleinen Modul" p reduziert werden, der üblicherweise den Wert p = 3 hat. In der Programmiersprache C lässt sich diese Reduktion einfach mit einem Befehl der Form r = s % 3 realisieren. Wenn nun s eine Variable vom Typ uint16_t ist (d.h. eine vorzeichenlose 16-bit Ganzzahl), dann benötigt der vom verwendeten GCC-Compiler erzeugte Binärcode für einen 8-bit AVR Prozessor zwischen 193 und 207 Taktzyklen. Durch diese variable Laufzeit wird die C-Implementierung anfällig für Timing-Attacken. Um solche Angriffe zu vereiteln, wurde die Modulo-3-Reduktion in Assembler implementiert, und zwar so, dass die Laufzeit immer konstant ist, egal welchen Wert s hat. Der Assembler-Code befindet sich in der Datei mod3.S im Github-Repository des Projekts. Durch die Assembler-Implementierung wurde die Ausführungszeit nicht nur unabhängig vom konkreten Wert von s, sondern hat sich auch wesentlich verringert im Vergleich zu dem von GCC erzeugten Binärcode.