Interpolation Cryptanalysis of Unbalanced Feistel Networks with Low Degree Round Functions

Arithmetisierungs-Orientierte Symmetrische Primitive (AOSPs) sprechen das bestehende Optimierungspotential bei der Auswertung von Blockchiffren und Hashfunktionen als Bestandteil von sicherer Mehrparteienberechnung, voll-homomorpher Verschlüsselung und Zero-Knowledge-Beweisen an. Die Konstruktionsweise von AOSPs unterscheidet sich von traditionellen Primitiven durch die Verwendung von algebraisch simplen Elementen. Zusätzlich sind viele Entwürfe über Primkörpern statt über Bits definiert. Aufgrund der Neuheit der Vorschläge sind eingehendes Verständnis und ausgiebige Analyse erforderlich um ihre Sicherheit zu etablieren. ... mehrAlgebraische Analysetechniken wie zum Beispiel Interpolationsangriffe sind die erfolgreichsten Angriffsvektoren gegen AOSPs. In dieser Arbeit generalisieren wir eine existierende Analyse, die einen Interpolationsangriff mit geringer Speicherkomplexität verwendet, um das Entwurfsmuster der neuen Chiffre GMiMC und ihrer zugehörigen Hashfunktion GMiMCHash zu untersuchen. Wir stellen eine neue Methode zur Berechnung des Schlüssels basierend auf Nullstellen eines Polynoms vor, demonstrieren Verbesserungen für die Komplexität des Angriffs durch Kombinierung mehrere Ausgaben, und wenden manche der entwickelten Techniken in einem algebraischen Korrigierender-Letzter-Block
Angriff der Schwamm-Konstruktion an. Wir beantworten die offene Frage einer früheren Arbeit, ob die verwendete Art von Interpolationsangriffen generalisierbar ist, positiv. Wir nennen konkrete empfohlene untere Schranken für Parameter in den betrachteten Szenarien. Außerdem kommen wir zu dem Schluss dass GMiMC und GMiMCHash gegen die in dieser Arbeit betrachteten Interpolationsangriffe sicher sind. Weitere kryptanalytische Anstrengungen sind erforderlich um die Sicherheitsgarantien von AOSPs zu festigen.

Arithmetization Oriented Symmetric Primitives (AOSPs) address optimization potential of evaluating block ciphers and hash functions as part of Secure Multi-Party Computations, in Fully Homomorphic Encryption, or in Zero Knowledge Proof Systems. Their design differs from traditional primitives by using algebraically simple building blocks. Many proposals natively work over prime fields as opposed to bits. Because the proposals have only recently emerged, an improved understanding and analysis is required to demonstrate their security. Algebraic cryptanalysis like interpolation attacks are among the most powerful attack vectors on AOSPs. ... mehrIn this thesis, we generalize a prior analysis using interpolation attacks with low memory complexity to the design paradigm of the recently proposed
GMiMC and its associated Sponge-based hash function GMiMCHash. More concretely, we propose a novel key recovery technique using root finding, demonstrate complexity improvements by combining multiple outputs, and apply some of the developed techniques in an algebraic Correcting-Last-Block Attack for Sponge constructions. Earlier work has
posed the open question whether low memory interpolation analysis is applicable in more general settings, which we answer positively. We give concrete recommended lower bounds for the parameters of the different scenarios considered. We conclude that GMiMC and GMiMCHash are secure against the interpolation attacks developed in this thesis. Further cryptanalytic efforts considering additional attack vectors are required to firmly establish the security of AOSPs.