Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

Key-Recovery Attack on the ASASA Cryptosystem with Expanding S-Boxes

verfasst von : Henri Gilbert, Jérôme Plût, Joana Treger

Erschienen in: Advances in Cryptology -- CRYPTO 2015

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We present a cryptanalysis of the ASASA public key cipher introduced at Asiacrypt 2014 [3]. This scheme alternates three layers of affine transformations A with two layers of quadratic substitutions S. We show that the partial derivatives of the public key polynomials contain information about the intermediate layer. This enables us to present a very simple distinguisher between an ASASA public key and random polynomials. We then expand upon the ideas of the distinguisher to achieve a full secret key recovery. This method uses only linear algebra and has a complexity dominated by the cost of computing the kernels of \(2^{26}\) small matrices with entries in \(\mathbb {F}_{16}\).

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Known-Key Distinguisher on Full PRESENT
Nächstes Kapitel Online Authenticated-Encryption and its Nonce-Reuse Misuse-Resistance
Fußnoten
1
While a noticeable exception is the multivariate scheme R2 [14] that contains two S layers with small S-boxes, one weakness highlighted by attacks on R2 or its variant \(R2^-\) that were eventually discovered is the fact that the R2 S-boxes are not injective.
 
2
While the role of perturbations is essential in the case of the \(\chi \)-scheme since its variants without perturbations are reported in [3] to be vulnerable to efficient Gröbner basis attacks, in the case of the expanding scheme, perturbations are mostly introduced to provide some extra resistance against decomposition attacks that could potentially reduce the ASASA structure to the functional composition of two ASA structures.
 
3
We may also investigate the case of a reinforced ASASA scheme with more perturbation polynomials, i.e. with 96 “legitimate” outputs and \(p \ge 32\) perturbations. We easily find that our distinguisher works at least for \(p \le 90\). The same bound applies to the key recovery attack of Sect. 3 below.
 
4
Since the elements of Y are quadratic forms, their differentials are exactly the associated polar forms. This means that we may represent the derivations as elements of X, using the relation \((\delta f)(x) = f(x+\delta ) - f(x) - f(\delta )\); in this view, the space \(D^r\) is the direct sum of all the \(X_s\) for \(s \ne r\). However, we chose to use an explanation based on differentials, since this is both closer to the differential cryptanalysis point of view, and easier to generalize to polynomials of higher degree.
 
5
We note that in the (very unlikely) case where the computation of the space Y performed in Sect. 3.1 returned a space \(Y' \supsetneq Y\), the computation performed here will allow us to remove the few extra elements of \(Y'\): namely, since the elements of Z are quadratic forms in the elements of Y, the unneeded elements of \(Y'\) will not appear in these expressions. This means that, in practice, this step (Sect. 3.3) should be performed before the inner step (Sect. 3.2).
 
Literatur
1.
Biham, E.: Cryptanalysis of patarin’s 2-round public key system with S boxes (2R). In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 408–416. Springer, Heidelberg (2000)
2.
Billet, O., Gilbert, H., Ech-Chatbi, C.: Cryptanalysis of a white box AES implementation. In: Handschuh, H., Hasan, M.A. (eds.) SAC 2004. LNCS, vol. 3357, pp. 227–240. Springer, Heidelberg (2004)
3.
Biryukov, A., Bouillaguet, C., Khovratovich, D.: Cryptographic Schemes based on the ASASA structure: black-box, white-box, and public-key (extended abstract). In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 63–84. Springer, Heidelberg (2014)
4.
Biryukov, A., Shamir, A.: Structural cryptanalysis of ASASA. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 395–405. Springer, Heidelberg (2001)
5.
Daemen, J.: Cipher and hash function design strategies based on linear and differential cryptanalysis. Ph.D. thesis, Doctoral Dissertation, KU Leuven, March 1995
6.
De Mulder, Y., Roelse, P., Preneel, B.: Cryptanalysis of the Xiao – Lai white-box AES implementation. In: Knudsen, L.R., Wu, H. (eds.) SAC 2012. LNCS, vol. 7707, pp. 34–49. Springer, Heidelberg (2013)
7.
Ding-Feng, Y., Kwok-Yan, L., Zong-Duo, D.: Cryptanalysis of 2R schemes. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 315–325. Springer, Heidelberg (1999)
8.
Faugère, J.-C., Perret, L.: Cryptanalysis of 2R\(^{-}\) schemes. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 357–372. Springer, Heidelberg (2006)
9.
Goubin, L., Masereel, J.-M., Quisquater, M.: Cryptanalysis of white box DES implementations. In: Adams, C., Miri, A., Wiener, M. (eds.) SAC 2007. LNCS, vol. 4876, pp. 278–295. Springer, Heidelberg (2007)
10.
Matsumoto, T., Imai, H.: Public quadratic polynomial-tuples for efficient signature-verification and message-encryption. In: Günther, C.G. (ed.) EUROCRYPT 1988. LNCS, vol. 330, pp. 419–453. Springer, Heidelberg (1988)
11.
Michiels, W., Gorissen, P., Hollmann, H.D.L.: Cryptanalysis of a generic class of white-box implementations. In: Avanzi, R.M., Keliher, L., Sica, F. (eds.) SAC 2008. LNCS, vol. 5381, pp. 414–428. Springer, Heidelberg (2009)
12.
Newman, M.: Integral Matrices. Academic Press, New York (1972)
13.
Patarin, J.: Cryptanalysis of the matsumoto and imai public key scheme of eurocrypt ’88. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 248–261. Springer, Heidelberg (1995)
14.
Patarin, J.: Asymmetric cryptography with a hidden monomial. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 45–60. Springer, Heidelberg (1996)
15.
Patarin, J., Goubin, L.: Asymmetric cryptography with S-Boxes is it easier than expected to design efficient asymmetric cryptosystems? In: Information and Communications, Security, pp. 369–380 (1997)
16.
Rijmen, V., Preneel, B.: A family of trapdoor ciphers. In: Biham, E. (ed.) FSE 1997. LNCS, vol. 1267, pp. 139–148. Springer, Heidelberg (1997)
17.
Sturmfels, B.: Algorithms in Invariant Theory. Springer Science & Business Media, New York (2008)
18.
Wu, H., Bao, F., Deng, R.H., Ye, Q.-Z.: Cryptanalysis of Rijmen-Preneel trapdoor ciphers. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 126–132. Springer, Heidelberg (1998)
Metadaten
Titel
Key-Recovery Attack on the ASASA Cryptosystem with Expanding S-Boxes
verfasst von
Henri Gilbert
Jérôme Plût
Joana Treger
Copyright-Jahr
2015
Verlag
Springer Berlin Heidelberg
Buch
Advances in Cryptology -- CRYPTO 2015

Print ISBN: 978-3-662-47988-9

Electronic ISBN: 978-3-662-47989-6

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-662-47989-6_23