Re: [Cfrg] Elliptic Curves - signature scheme: randomised or not (ends on May 13th)

[Nico Williams <[e-mail]>]

On Sun, May 10, 2015 at 11:33:18PM -0700, Andrey Jivsov wrote:
> I agree that signing algorithms like ECDSA are sensitive to the
> leaking of a few bits of nonces per signature. However, a secure
> DRBG/KDF used throughout is considered mandatory nowadays. Nonces,
> long-term key generation, IVs, session keys, etc, should be obtained
> via good DRBG/PRF anyway.

"Sure, and I want a pony too."

Statefulness is difficult to implement.

Consider OpenSSL.  Till now OpenSSL has thankfully not needed to use
file locking.  If it had to...  The thought of OpenSSL using POSIX file
locking makes me shudder with fear.  As it is one really does not need
to worry too much about N copies of OpenSSL in one process (besides some
of those N being out of date) for N>1 -- just make sure that the right
version is loaded and linked at run-time for each dependent.

Or consider any other software implementation.  To make it work reliably
one would really need an IPC mechanism to talk to a daemon so it does
all the signing because then it can have a single lock around the
signing state.

Even accepting that complication, compare the result to a deterministic,
state-less signature function!

(This is not even considering the difficulty in synchronously updating
persistent state, or arranging to be able to survive occasional failures
to do so.)

Test vectors go out the window, unless we specify every detail of state
keeping so that the state can be made explicit... further complicating
implementations _and_ applications.

> Your list got me thinking regarding the issue of fault attacks on
> deterministic signatures.
> 
> I will use the EdDSA as an example. Consider an EdDSA signing on a
> smartcard.
> 
> EdDSA algorithm, in its canonical version, includes a message M in
> the calculation of the hash twice: once to calculate the ephemeral
> private value r for R=r*G, and second, to calculate a multiple of
> the long-term private signing key 'a' during the calculation of S.
> {R,S} is the signature. Assume that a smartcard signature
> implementation requires transfer of the M to the smartcard twice,
> due to limited memory on the smartcard and that the EdDSA
> cryptographically enforces that the two hashing operations are
> performed sequentially. As a result, the signing operation provides
> a reliable method to affect the second hashing, but not the first. A
> user (or malware) can change the M to M' at the appropriate moment,
> affecting the second hashing, which should be a realistic task with
> a sufficiently large message.
> 
> The second hashing in the EdDSA algorithm is done over data that the
> user knows, specifically, H'=Hash(R, A, M'). It can be observed that
> one valid signature and one invalid, generated as described above,
> will recover the private key 'a'. Hint: the deterministic r remains
> the same and is canceled out by subtraction.

This can be fixed by replacing M with H(M) in the second hash, since
H(M) will be of fixed size and the smartcard can compute it as it
computes the first hash.

Perhaps we should add 'online' to the list of required attributes (which
so far should be: deterministic, and state-less).

Nico
--