Bleichenbacher Attacks

Daniel Bleichenbacher has published various attacks against cryptographic systems, for example: Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1, CRYPTO '98. Reference [8] of that paper describes simpler direct attacks on RSA: Why and how to establish a private code on a public network, Goldwasser, Micali, and Tong, FOCS 1982.

The attack of interest here is described in:

Using Bleichenbacher's Solution to the Hidden Number Problem to Attack Nonce Leaks in 384-Bit ECDSA: extended version, Elke De Mulder, Michael Hutter, Mark E. Marson, and Peter Pearson, J Cryptogr Eng (2014) 4:33-45. Original version: eprint.iacr.org/2013/346; CHES'2013 presentation

GLV/GLS Decomposition, Power Analysis, and Attacks on ECDSA Signatures with Single-Bit Nonce Bias, Aranha, et. al., ASIACRYPT 2014

Preliminary Results

Example which takes just a few seconds to find 21 bits of a 40-bit EdDSA private key (x), given an initial 3-bit key leak and 3000 signature samples:

  qbits = 40 , b = 3 , L = 3000 , nbits_max = 22
  Reduce:
  L =  3000 , n = 1099511627776 , nbits = 40
  L =  2999 , n = 4294967296 , nbits = 32
  L =  2998 , n = 268435456 , nbits = 28
  L =  2987 , n = 33554432 , nbits = 25
  L =  1167 , n = 4194304 , nbits = 22
      0.0742836 secs
  Generate FFT input
      3.20653 secs
  Call fft
      16.785 secs
  Done fft
  w = 0b1001010000111110000001000000000000000001
  x = 0b1001010000111110000000100001001101110101
  21 bits correct out of 40

FFT in C for Python

  fft(X,inv=False,pre=True,nmax=0)

    Overwrites X with FFT, with bit-reversed result locations.

    X must be a list of complex values, and len(X) must be a power of 2.

    If inv is true then the inverse FFT is computed.

    If pre is true then the FFT W factors are precomputed and saved.
    This can improve speed but requires extra memory equivalent to that used by X.

    Returns indices of the nmax largest result absolute values.

src/

To be continued...

A related attack based on the non-uniformity of random numbers mod q is described in:

Evaluation Report on DSA, Serge Vaudenay, 2013. See section 5.

Hash-Function based PRFs: AMAC and its Multi-User Security, Mihir Bellare and Daniel J. Bernstein and Stefano Tessaro, 2016. Version: 20160216:211135, see appendix A.

Related references on the hidden number problem:

Hidden Number Problems, Barak Shani, PhD Thesis, The University of Auckland, 2017.

On the Bit Security of Elliptic Curve Diffie-Hellman, Barak Shani, 2016.

The Multivariate Hidden Number Problem, Steven D. Galbraith and Barak Shani, 2015.

Solving Hidden Number Problem with One Bit Oracle and Advice, Adi Akavia, CRYPTO 2009.

Related references on lattice basis reduction:

Practical, Predictable Lattice Basis Reduction, Daniele Micciancio and Michael Walter, 2015.

BKZ 2.0: Better Lattice Security Estimates, Yuanmi Chen and Phong Q. Nguyen, ASIACRYPT 2011.

Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems, C. P. Schnorr, M. Euchner, 1993. Also in Math. Program. 66, 181-199 (1994).