nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Fault Attacks on UOV and Rainbow

verfasst von : Juliane Krämer, Mirjam Loiero

Erschienen in: Constructive Side-Channel Analysis and Secure Design

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Multivariate cryptography is one of the main candidates for creating post-quantum public key cryptosystems. Especially in the area of digital signatures, there exist many practical and secure multivariate schemes. The signature schemes UOV and Rainbow are two of the most promising and best studied multivariate schemes which have proven secure for more than a decade. However, so far the security of multivariate signature schemes towards physical attacks has not been appropriately assessed. Towards a better understanding of the physical security of multivariate signature schemes, this paper presents fault attacks against SingleField schemes, especially UOV and Rainbow. Our analysis shows that although promising attack vectors exist, multivariate signature schemes inherently offer a good protection against fault attacks.

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 Fast Analytical Rank Estimation

Nächstes Kapitel Towards Optimized and Constant-Time CSIDH on Embedded Devices

Nur mit Berechtigung zugänglich

Rainbow has been submitted to the call for post-quantum cryptography standardization by the US American National Institute of Standards and Technology (NIST) in November 2017 [10] and was selected Round 2 Candidate in January 2019 [1].

The same authors published their work additionally in [15].

Due to the above construction, the security of multivariate public key schemes is not only based on the MQ-Problem, but also on the EIP-Problem (Extended Isomorphism of Polynomials) of finding the composition of

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-16350-1_11/481349_1_En_11_IEq27_HTML.gif

[20].

To clarify Step 2. of [14, p. 9]: It is essential to cause a new fault on the central map for each message (i.e., for each iteration over Steps 1 - 4) and not use the same faulty map for all messages. Using the same faulty map for more than one message will not reveal new information about T, as for two messages \(h^{(l_1)}\) and \(h^{(l_2)}\) - signed with the same faulty central map - \(\delta ^{(l_1)}\) and \(\delta ^{(l_2)}\) will be multiples component-wise, since the attack would both times target the same column of T.

Note that this does not imply that one of the quadratic coefficients is changed. This representation only serves as an illustration.

In Table 1 of [14] the authors state that the number of faults for STS type schemes - they erroneously consider UOV and Rainbow to be STS schemes - is exactly \(n-1\). This is incorrect in two different ways: (1) According to the dimension of T, the number of faults does not depend on n, but on m. (2) The number of faults is not exactly \(m-1\), but at least \(m-1\). In Sect. 3.5, we describe a special case where more faults need to be injected.

The same formula holds for UOV schemes.

Actually the parameters q and n are indirectly connected, since in fields with small q the parameter n has to be chosen larger in order to ensure security.

The first three tuples of parameters are taken from [20] for the year 2018, the last one is the original suggestion from [11].

The same situation would occur if an entire column of

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-16350-1_11/481349_1_En_11_IEq201_HTML.gif

was equal zero. However, this cannot happen since the maps are expected to have full rank.

Round 2 submissions - post-quantum cryptography—CSRC (2019). https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions. Accessed 14 Feb 2019

Albrecht, Bulygin, S., Buchmann, J.A.: Selecting parameters for the rainbow signature scheme - extended version. IACR Cryptology ePrint Archive 2010, p. 437 (2010)

Blömer, J., da Silva, R.G., Günther, P., Krämer, J., Seifert, J.P.: A practical second-order fault attack against a real-world pairing implementation. In: 2014 Workshop on Fault Diagnosis and Tolerance in Cryptography, pp. 123–136 (2014)

Bogdanov, A., Eisenbarth, T., Rupp, A., Wolf, C.: Time-area optimized public-key engines: \(\cal{MQ}\)-cryptosystems as replacement for elliptic curves? In: Oswald, E., Rohatgi, P. (eds.) CHES 2008. LNCS, vol. 5154, pp. 45–61. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85053-3_4CrossRef

Braeken, A., Wolf, C., Preneel, B.: A study of the security of unbalanced oil and vinegar signature schemes. In: Menezes, A. (ed.) CT-RSA 2005. LNCS, vol. 3376, pp. 29–43. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-30574-3_4CrossRef

Bulygin, S., Petzoldt, A., Buchmann, J.: Towards provable security of the unbalanced oil and vinegar signature scheme under direct attacks. In: Gong, G., Gupta, K.C. (eds.) INDOCRYPT 2010. LNCS, vol. 6498, pp. 17–32. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-17401-8_3CrossRef

Charlap, L.S., Rees, H.D., Robbins, D.P.: The asymptotic probability that a random biased matrix is invertible. Discrete Math. 82(2), 153–163 (1990)MathSciNetCrossRef

Chen, A.I.-T., et al.: SSE implementation of multivariate PKCs on modern x86 CPUs. In: Clavier, C., Gaj, K. (eds.) CHES 2009. LNCS, vol. 5747, pp. 33–48. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04138-9_3CrossRef

Czypek, P., Heyse, S., Thomae, E.: Efficient implementations of MQPKS on constrained devices. In: Prouff, E., Schaumont, P. (eds.) CHES 2012. LNCS, vol. 7428, pp. 374–389. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33027-8_22CrossRef

10.

Ding, J., Chen, M., Petzoldt, A., Schmidt, D., Yang, B.: Rainbow - algorithm specification and documentation, November 2017. https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Round-1-Submissions

11.

Ding, J., Schmidt, D.: Rainbow, a new multivariable polynomial signature scheme. In: Ioannidis, J., Keromytis, A., Yung, M. (eds.) ACNS 2005. LNCS, vol. 3531, pp. 164–175. Springer, Heidelberg (2005). https://doi.org/10.1007/11496137_12CrossRef

12.

Faugère, J.-C., Levy-dit-Vehel, F., Perret, L.: Cryptanalysis of MinRank. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 280–296. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85174-5_16CrossRef

13.

Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1990)

14.

Hashimoto, Y., Takagi, T., Sakurai, K.: General fault attacks on multivariate public key cryptosystems. In: Yang, B.-Y. (ed.) PQCrypto 2011. LNCS, vol. 7071, pp. 1–18. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25405-5_1CrossRef

15.

Hashimoto, Y., Takagi, T., Sakurai, K.: General fault attacks on multivariate public key cryptosystems. IEICE Trans. 96-A(1), 196–205 (2013)

16.

Kipnis, A., Patarin, J., Goubin, L.: Unbalanced oil and vinegar signature schemes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 206–222. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48910-X_15CrossRef

17.

Kipnis, A., Shamir, A.: Cryptanalysis of the oil and vinegar signature scheme. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 257–266. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0055733CrossRef

18.

Okeya, K., Takagi, T., Vuillaume, C.: On the importance of protecting \(\Delta \) in SFLASH against side channel attacks. In: Proceedings of the International Conference on Information Technology: Coding and Computing, ITCC 2004, vol. 2, pp. 560–568 (2004)

19.

Park, A., Shim, K.A., Koo, N., Han, D.G.: Side-channel attacks on post-quantum signature schemes based on multivariate quadratic equations. IACR Trans. Crypt. Hardware Embed. Syst. 2018(3), 500–523 (2018)

20.

Petzoldt, A.: Selecting and reducing key sizes for multivariate cryptography. Ph.D. thesis, Darmstadt University of Technology, Germany (2013)

21.

Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)MathSciNetCrossRef

22.

Steinwandt, R., Geiselmann, W., Beth, T.: A theoretical DPA-based cryptanalysis of the NESSIE candidates FLASH and SFLASH. In: Davida, G.I., Frankel, Y. (eds.) ISC 2001. LNCS, vol. 2200, pp. 280–293. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45439-X_19CrossRef

23.

Tang, S., Yi, H., Ding, J., Chen, H., Chen, G.: High-speed hardware implementation of rainbow signature on FPGAs. In: Yang, B.-Y. (ed.) PQCrypto 2011. LNCS, vol. 7071, pp. 228–243. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25405-5_15CrossRef

24.

Yi, H., Li, W.: On the importance of checking multivariate public KeyCryptography for side-channel attacks: the case of enTTS scheme. Comput. J. 60(8), 1197–1209 (2017)MathSciNetCrossRef

25.

Yi, H., Nie, Z.: High-speed hardware architecture for implementations of multivariate signature generations on FPGAs. EURASIP J. Wirel. Commun. Networking 2018(1), 93 (2018)CrossRef

Titel: Fault Attacks on UOV and Rainbow
verfasst von: Juliane Krämer
Mirjam Loiero
Verlag: Springer International Publishing
Buch: Constructive Side-Channel Analysis and Secure Design
Print ISBN: 978-3-030-16349-5

Electronic ISBN: 978-3-030-16350-1

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-16350-1_11

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner