Verwirrung wegen Sicherheit des Signaturalgorithmus MQQ

Ein neues Verfahren für die Erstellung von digitalen Signaturen wurde von der Norwegian University of Science and Technology (NTNU) präsentiert, das laut Eigendarstellung 17.000 mal schneller in der Signaturprüfung und 10.000 mal schneller in der Signaturerstellung ist, verglichen mit bekanten Algorithmen wie RSA 1024 oder ECC 160. Der neue Algorithmus hört auf den etwas sperrigen Namen multivariante quadratische Quasigruppen (multivariant quadratic quasigroups), oder kürzer MQQ.

Die Resonanz auf die Veröffentlichung zeigt das hohe Interesse der online Community an Sicherheitsthemen wie Kryptographie. Allerdings mischen sich auch Untertöne in die Diskussion: schon seit einiger Zeit bekannt aber in der Aussendung unerwähnt ist ein Angriff der TU Darmstadt auf den neuen Algorithmus.

Auch Signaturalgorithmen altern

Die digitale Signatur basiert auf der Anwendung von asymetrischer Kryptographie - vereinfacht sind dies Verschlüsselungsfunktionen, die in eine Richtung für Jedermann nachvollziehbar sind, in die andere jedoch nur für den Besitzer eines geheimen Schlüssels. Die zugrunde liegenden kryptographischen Algorithmen müssen dabei dem jeweiligen Stand der Technik angepasst werden: Computer werden immer schneller, die kryptoanalytische Forschung schreitet voran, und was gestern noch sicher war ist morgen vielleicht schon überholt.

Bis zu einem gewissen Grad kann man der höheren Rechenleistung moderner Computer mit längeren Schlüsseln beikommen, so werden heute in Deutschland anstelle von 1024 bit RSA oft 2048 bit RSA Schlüssel verwendet. Doch längere Schlüssel haben ihren Pferdefuß, wenn sie auf Chipkarten generiert und gespeichert werden sollen, wie dies z.B. bei der qualifizierten Signatur der Fall ist. Diese Chipkarten sind nämlich nichts anderes als Mini-Computer, die sich mit sehr langen Schlüsseln schwertun. Außerdem erzeugen längere Schlüssel auch längere Signaturwerte, und manch billiger Kartenleser hat damit ebenfalls ein Problem.

Neu Algorithmen sind der klügere Ansatz

Neue Signaturalgorithmen begegnen dem Problem auf eine andere Art und Weise. Sie sollen (in der Theorie) robuster gegen Angriffe sein. Damit können sie Hackversuchen dem Stand der Technik mit den selben oder sogar geringeren Schlüssellängen widerstehen. Nicht zuletzt diese Überlegungen haben seinerzeit zu der Entscheidung geführt, in Österreich anstelle von RSA das Signaturverfahren der elliptischen Kurven (ECC) für die Bürgerkarte zu verwenden.

Neue Algorithmen haben jedoch den Nachteil, dass sie ihre Widerstandsfähigkeit erst unter Beweis stellen müssen. Daher ist es üblich, dass Forscherteams auf der ganzen Welt neue Algorithmen experimentellen Angriffen aussetzen und sie so auf den Prüfstand stellen.

Wie sicher ist nun MQQ

Die Veröffentlichung der NTNU hat die Form eines Produktblattes, das neben den genannten Geschwindigkeitsangaben weitere Vorzüge des Algorithmnus preist: sicher gegenüber bekannten Attacken, sicher gegenüber quantenkryptographischen Attacken, und generell "keine Attacke besser als Brute-Force bekannt" (also simples Ausprobieren aller möglichen Schlüssel.

Anderes list man in einer Publikation der TU Darmstadt, die nun schon ein Jahr alt ist. In dieser Arbeit veröffentlichen die Forscher ihre Ergebnisse als "sehr effiziente praktische Kryptoanalysevon MQQ", mit der MQQ Systeme mit 160bit (dem von der NTNU empfohlenen Schlüssellänge) geknackt werden können. Eine Veröffentlichung aus 2009 zeigt sogar, dass ein 300 bit Schlüssel in weniger als 3 Tagen geknackt ist, und das mit einem durchwegs zivilen Rechner ("Quad-Core AMD Opteron Processor 8356" CPUs mit 2,3 GHz und 128 GB RAM). Damit wäre der neue MQQ Signaturalgorithmus wohl deutlich hinter dem, was ECC 256 (der Algorithmus auf den neuen Bürgerkarten) zu bieten hat.

Weitere Informationen

Produktblatt für den MQQ Signaturalgorithmus

MQQ Digital Signature Scheme

Presseaussendungen und Online-Artikel als Reaktion auf die Veröffentlichung

pressetext.austria

Computerwoche

Heise.de

Publikationen der TU Darmstadt zum Angriff auf MQQ

Algebraic Cryptanalysis of MQQ Public Key Cryptosystem by MutantXL (in Englisch)

Algebraic Algebraic Attack on the MQQ Public Key Cryptosystem (in Englisch)