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
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Robust Profiling for DPA-Style Attacks Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

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

verfasst von : Aurélie Bauer, Damien Vergnaud

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

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

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.

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 Improved Cryptanalysis of the DECT Standard Cipher
Nächstes Kapitel The Simeck Family of Lightweight Block Ciphers
Fußnoten
1
We remind that the 2-adic valuation of a number c denotes the largest power of 2 dividing c.
 
2
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.
 
3
One can easily reorder the random values \(r_i\) to make such an assumption true.
 
4
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)})\).
 
5
Here, the index e is defined such that \(\ell _1 = \ell _2= \cdots =\ell _e < \ell _{e+1} \le \cdots \le \ell _t\).
 
6
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.
 
7
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).
 
Literatur
1.
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)
2.
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
3.
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
4.
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
5.
Bleichenbacher, D.: On the generation of one-time keys in dl signature schemes. Presentation at IEEE P1363 Working Group meeting, November 2000. Unpublished
6.
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
7.
8.
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
9.
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
Metadaten
Titel
Practical Key Recovery for Discrete-Logarithm Based Authentication Schemes from Random Nonce Bits
verfasst von
Aurélie Bauer
Damien Vergnaud
Copyright-Jahr
2015
Verlag
Springer Berlin Heidelberg
Buch
Cryptographic Hardware and Embedded Systems -- CHES 2015

Print ISBN: 978-3-662-48323-7

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

Copyright-Jahr: 2015

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

Premium Partner

    Bildnachweise