Top

Published in:

2015 | OriginalPaper | Chapter

Practical Key Recovery for Discrete-Logarithm Based Authentication Schemes from Random Nonce Bits

Authors : Aurélie Bauer, Damien Vergnaud

Published in: Cryptographic Hardware and Embedded Systems -- CHES 2015

Publisher: Springer Berlin Heidelberg

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We propose statistical cryptanalysis of discrete-logarithm based authentication schemes such as Schnorr identification scheme or Girault-Poupard-Stern identification and signature schemes. We consider two scenarios where an adversary is given some information on the nonces used during the signature generation process or during some identification sessions. In the first scenario, we assume that some bits of the nonces are known exactly by the adversary, while no information is provided about the other bits. We show, for instance, that the GPS scheme with 128-bit security can be broken using only 710 signatures assuming that the adversary knows (on average) one bit per nonce. In the second scenario, we assume that all bits of the nonces are obtained from the correct ones by independent bit flipping with some small probability. A detailed heuristic analysis is provided, supported by extensive experiments.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter Improved Cryptanalysis of the DECT Standard Cipher

next chapter The Simeck Family of Lightweight Block Ciphers

We remind that the 2-adic valuation of a number c denotes the largest power of 2 dividing c.

Obviously once \((r_1, \ldots ,r_t)\) has been retrieved, the signers’ secret key x can easily be recovered. Theoretically only one of the \(r_i\)’s is really necessary to retrieve x, but we see in the following that recovering one such element requires in fact to retrieve all \(r_i\)s simultaneously.

One can easily reorder the random values \(r_i\) to make such an assumption true.

We remind that \(\gamma \) is only defined when \((\upvartheta _{1}^{(k-1)}, \ldots ,\upvartheta _{t}^{(k-1)}) \ne (r_1^{(k-1)}, \ldots ,r_{t}^{(k-1)})\).

Here, the index e is defined such that \(\ell _1 = \ell _2= \cdots =\ell _e < \ell _{e+1} \le \cdots \le \ell _t\).

This theorem states that no combination of code and decoding procedure can jointly achieve arbitrarily reliable decoding when the code rate exceeds the capacity of the channel.

In particular, in both cases, one gets before pruning \(\mathcal {N}^{(T-1)} = 2^T\) at iteration T (instead of \(\mathcal {N}^{(T-1)} = 2^{tT}\) for a naive approach).

Bauer, A., Vergnaud, D.: Practical key recovery for discrete-logarithm based authentication schemes from random nonce bits. Full version of the paper, Cryptology ePrint Archive (2015)

Bellare, M., Goldwasser, S., Micciancio, D.: “Pseudo-random” number generation within cryptographic algorithms: the DSS case. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 277–291. Springer, Heidelberg (1997) CrossRef

Bellare, M., Namprempre, C., Pointcheval, D., Semanko, M.: The one-more-RSA-inversion problems and the security of Chaum’s blind signature scheme. J. Cryptol. 16(3), 185–215 (2003)MathSciNetCrossRef

Bellare, M., Palacio, A.: GQ and Schnorr identification schemes: proofs of security against impersonation under active and concurrent attacks. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 162–177. Springer, Heidelberg (2002) CrossRef

Bleichenbacher, D.: On the generation of one-time keys in dl signature schemes. Presentation at IEEE P1363 Working Group meeting, November 2000. Unpublished

El Gamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 10–18. Springer, Heidelberg (1985) CrossRef

Feige, U., Fiat, A., Shamir, A.: Zero-knowledge proofs of identity. J. Cryptol. 1(2), 77–94 (1988)MathSciNetCrossRef

Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987) CrossRef

Girault, M.: Self-certified public keys. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 490–497. Springer, Heidelberg (1991) CrossRef

10.

Girault, M., Poupard, G., Stern, J.: On the fly authentication and signature schemes based on groups of unknown order. J. Cryptol. 19(4), 463–487 (2006)MathSciNetCrossRef

11.

Halderman, J.A., Schoen, S.D., Heninger, N., Clarkson, W., Paul, W., Calandrino, J.A., Feldman, A.J., Appelbaum, J., Felten,E.W.: Lest we remember: cold boot attacks on encryption keys. In: van Oorschot, P.C. (ed.) Proceedings of the 17th USENIX Security Symposium, July 28–August 1, 2008, San Jose, CA, USA, pp. 45–60. USENIX Association (2008)

12.

Henecka, W., May, A., Meurer, A.: Correcting errors in RSA private keys. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 351–369. Springer, Heidelberg (2010) CrossRef

13.

Heninger, N., Shacham, H.: Reconstructing RSA private keys from random key bits. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 1–17. Springer, Heidelberg (2009) CrossRef

14.

Horster, P., Petersen, H., Michels, M.: Meta-El-Gamal signature schemes. In: ACM CCS 1994: 2nd Conference on Computer and Communications Security, pp. 96–107. ACM Press (1994)

15.

Kuwakado, H., Tanaka, H.: On the security of the elgamal-type signature scheme with small parameters. IEICE Trans. 82–A(1), 93–97 (1999)

16.

De Mulder, E., Hutter, M., Marson, M.E., Pearson, P.: Using Bleichenbacher’s solution to the hidden number problem to attack nonce leaks in 384-bit ECDSA. In: Bertoni, G., Coron, J.-S. (eds.) CHES 2013. LNCS, vol. 8086, pp. 435–452. Springer, Heidelberg (2013) CrossRef

17.

FIPS PUB 186–2: Digital Signature Standard (DSS). National Institute for Standards and Technology, Gaithersburg, MD, USA (2000)

18.

Nguyen, P.Q., Shparlinski, I.: The insecurity of the digital signature algorithm with partially known nonces. J. Cryptol. 15(3), 151–176 (2002)MathSciNetCrossRef

19.

Paterson, K.G., Polychroniadou, A., Sibborn, D.L.: A coding-theoretic approach to recovering noisy RSA keys. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 386–403. Springer, Heidelberg (2012) CrossRef

20.

Percival, C.: Cache missing for fun and profit. In: Proceedings of BSDCan 2005

21.

Poupard, G., Stern, J.: On the fly signatures based on factoring. In: ACM CCS 1999: 6th Conference on Computer and Communications Security, pp. 37–45. ACM Press, November 1999

22.

Schnorr, C.-P.: Efficient signature generation by smart cards. J. Cryptol. 4(3), 161–174 (1991)MathSciNet

Title: Practical Key Recovery for Discrete-Logarithm Based Authentication Schemes from Random Nonce Bits
Authors: Aurélie Bauer
Damien Vergnaud
Publisher: Springer Berlin Heidelberg
Book: Cryptographic Hardware and Embedded Systems -- CHES 2015
Print ISBN: 978-3-662-48323-7

Electronic ISBN: 978-3-662-48324-4

Copyright Year: 2015
DOI: https://doi.org/10.1007/978-3-662-48324-4_15

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner