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

[Dan Brown <[e-mail]>]

> -----Original Message-----
> From: Watson Ladd [mailto:[e-mail]]
> 
> On Wed, May 6, 2015 at 8:39 AM, Dan Brown <[e-mail]>
> wrote:
> > Accordingly, I now amend my proposal to k = F(m,a,t) where F is some
> > to-be-specified cryptographically strong deterministic function, m is
> > the message, a is the actual long-term (signing) key, and t is a
> > temporal value (tweak/nonce), preferably secret and unpredictable, or at
> least non-repeating, optionally fixed (including empty: reducing the signature
> scheme to an outright deterministic signature scheme), and not under any
> influence from an adversary.
> 
> I think that if we worry about kleptography, t should not be used.

[DB] Good catch.  So, that cost should be weighed against the gains from using t.

Just to expand: is your concern about the following kleptographic malware? The malware lets multiple t values be generated (honestly), say t_1, t_2, ... t_n, and then search the corresponding k_1, ..., k_n for a value k_i that suffers from bias needed to make a lattice attack work? The kleptographic malware then lets k=k_i through to per a normal signature.

> 
> >
> > When k is used in signatures, this approach could be called tweakably
> deterministic signatures, although I would prefer to call it message-dispersed
> signatures (to avoid the silly pitfall I mentioned of over-generalizing the value
> of determinism in key generation).
> >
> > The changes my previous proposal have brought my current proposal closer
> to deterministic signatures than to purely randomized signatures. The tweak
> value t helps to address some of the potential pitfalls of purely deterministic
> signatures that I listed in my previous email.  Please let me know if you think
> the cost of tweaking outweighs the gains I described.
> >
> > So, I'm not intending to be critical of deterministic signatures, or to
> support/defend past pure PRNG-based or underspecified randomized
> signatures, but rather to be in support something slightly securer than either,
> by combining the good features of both randomized and deterministic
> signatures.  Yet more reasons and responses in-line below.  So, please take
> them with a grain of salt, and read them in the light of trying make things
> securer.
> 
> How is this proposal more secure, i.e. what properties does it have, that
> protocols rely on, that EdDSA doesn't?
> 
[DB] Maybe I was unclear above: the tweak tries to address the issues I labelled 3a..3h in the first email I sent.  If you have time to spare, then please consider these issues.  I think you know that Bernstein responded to 3a...3h already, so I would fully understand if you didn't want to waste any time.

> 
> Let me see if I have this correct. You're arguing that an implementor, told to
> compute k=F(m, x), and go through some more steps, will skip that step. Fine:
> they evidently skipped the random number generation step. But at that point
> we might as well specify an implementor who skips over comparison steps in
> signature verification.

[DB] Wasn't there were real world examples (goto fail???) of signature verification steps being accidentally skipped?  I'm trying to see if the point of your paragraph is to compare realisms of two failure modes, or to just give up on protecting against attack X because we cannot protect against attack Y. ASIDE: implicit certificates, e.g. SEC4 (includes IPR), can _sometimes_ address this failure to verify a cert, because of instead of a verification step to miss it absorbs the authentication right into the use of the public key.

I think I originally described the examples 3a...3h in sufficient detail, with at least a paragraph each.

> 
> What DJB is arguing is that the implementor missed the *per-message*
> random generation, a much more subtle issue then failing to compute a
> different random number each time. Why, just yesterday I had a student tell
> me the odds of rolling a 6 with two dice should be 1/6, not 5/36.
> 

[DB]  I didn't hear Bernstein's argument that way.  I know well that math works by the subtlety of k being re-used across different messages, but as far as I know, in the 2010 attack, the implementer use just one k for every single signature?  Or maybe I'm wrong: perhaps the implementer did some kind of subtle mistake of using the same k_1 for the first signature of each message, and then another k_2 for every the second signature of each message?  Are you saying that kind of subtle mistake is more likely than some kind of larger bungle?

> 
> But you've offered no assessment of why we should analyze these failures.
> Why are these the most likely? By contrast we know kleptography is a real
> issue.

[DB] I provided my assessment in one paragraph for each of the points 3a..3h.

> >
> > This aims to be a middle-ground between randomized and fully deterministic
> signatures, an effort to combine the best of both methods.
> >
> > I'm theoretically wary of mixing in a, but yes, if F is sufficiently one-way etc.,
> then it's totally intuitively fine.
> 
> In the EdDSA scheme, the signing key consists of x a discrete logarithm of the
> public key, and z, a key for the PRF. It's a trivial exercise to show that using
> k=H(z,m) is secure if H is a PRF from {0,1}*->bit strings of the correct length,
> and the length is long enough for the group being used.
> 

[DB] I guess I misremembered EdDSA: I thought it used k =H(x,m).  Are z and x are truly independent?  Then why Bernstein object to my original proposal k = F(s,m) where s is a secret by saying that s might be constant, and then predictable?  Maybe there's a connection between z and x in EdDSA?  Is x = H(z,z) or something?

> >>
> >> It's not enough to _tell_ people that k has security consequences---
> >> something that has been said again and again since the original ElGamal
> paper in 1985.
> >
> > At least some old standards do more than warn about security: they specify
> steps to generate k, HMAC_DRBG.  Yes, this requires entropy to be secure, but
> so does the long-term key.
> 
> It's easy to have standards that specify secure ways of doing things.
> Oddly enough, I still have a job breaking systems. Test vectors are far more
> likely to be run then extensive audits. I have seen systems (and once written
> one!) that don't use long enough k for modular reduction, that don't ensure
> adequate seeding of the random number generator, etc, etc, etc. Many
> implementations of cryptography aren't written by experts. They are
> occasionally written from Wikipedia articles.
> 

[DB] Ok, how do your "test vectors" work, given that the signer has a secret signing key?  Do you substitute in test key for the signing key?  Why cannot that be done for a seeded PRNG implementation: just feed in a test seed?

> 
> I don't have access to ANSI X9.62-2005. But let's consider the impact of the
> Debian bug, or the FreeBSD-CURRENT bug. Even if the authors of the ECDSA
> module had taken care to carefully seed the approved random number
> generator, they would have generated an extremely limited number of
> possible k. How does including HMAC_DRBG test vectors fix this problem? We
> know the causes of these failures: where do they fit in your analysis?
> 
[DB] Entropy deficiency is an orthogonal issue, but if a has enough entropy, then k = F(m,a,t) should be fine, just like the deterministic k=F(m,a) should be good. If t does not enough entropy, then k = F(m,a,t) reduces to k = F(m,a). 

So, the way to use HMAC_DRBG, or any DRBG, is not instantiate it anew for each secret or key needed.  That would be a mis-use of any DRBG. I don't think that's what happened in the 2010 attack.  If a DL-based signature with a DRBG in the intended way, i.e. as a deterministic DL-based signature is used in the intended way, then all is dandy, provide the initial seeds are good.

> Deterministic functions are much easier to test. We can pick vectors to stress
> common issues, automate comparison testing, etc. I don't know how to do the
> same for nondeterministic functions.
> 
[DB] Sure, that's why X9.62 includes test-able algorithms for key-generation.

> >
> > So, what I was getting at: A good implementation might work really hard to
> protect against say simple power analysis, e.g. Montgomery ladder and the
> blinding techniques.  Great, but what if differential power/timing analysis is
> able average out the blinding effect, and detect the very minute remaining
> signal from the Montgomery ladder?  Are you saying such iterative side
> channel attacks are fully preventable? If so, then great, else doesn't changing k
> every time seems to help reduce this threat?  In other words, wouldn't this
> provide "defense-in-depth" or "multi-factor side-channel-protection", etc.  The
> way I see it, randomized signatures, or the tweaked deterministic signatures
> I'm proposing, seem to theoretically require less side-protection than fully
> deterministic signatures.
> 
> One of the standard countermeasures against side channels is to compute [k]P
> as [k+r]P-[r]P for a random r the same size as k. Of course, an attacker
> attacking an implementation using this method knows slightly more than if we
> compute a different [r]P every time:
> they know each set of traces sum to the same number. I don't see how this
> helps much. (Mike Hamburg would know better).

[DB] Again, blinding is a good method.  It needs a good random r, so it does not save much on that account compred to random k.  If k is used, say, a thousand times, can the relative traces of [k+r]P and [r]P, which are related by k, leak out some info about k?  Maybe nobody thinks so now, but if the k were different, then we needn't worry so much about it.

> > In some of the cases 3b...3g, it would not require a transfer of a mistake from
> one piece of code to another. An implementer might have a common key
> generation unit: shared between the ephemeral and static keys, shared
> between signatures and key exchange, per some kind of centralization
> strategy.  In such cases, the fault might arise without any transfer of a code.
> 
> How is this risk mitigated by your approach? If we assume that they make a
> "common key generator", then your specification of F(m,a,t) was entirely
> ignored, as was DJB's proposed k=F(m, z). 

[DB] The common key generator would have an optional input: like the SP 800-90 and /dev/random (you can write to it).  The convention in my scenario would be that callers to the key generator write to the optional input before calling it: much like deterministic obtain a secret by making it depend on the message.

So, I'm not saying that DJB or you would implement things in this way, just that somebody else might.

> However, in testing with selected
> test vectors the deviation from your proposal can't be detected, while from
> DJB's it's easy.
> 
[DB] Oh: t should be specified in my proposal to generated using a DRBG, per the traditional state-of-the-art ECDSA implementations.  

These can be test vectored easily by supplying all the seed inputs, and corresponding outputs.

If an implementers fails by generating t with the wrong deterministic algorithm, then the test vectors will catch it.  If an implementer fails by not supply adequate seeds for t, but adequate seeds for a, then all is fine.

> >
> > If you are trying to dismiss comment 3h as theoretical, then why not just say
> so, otherwise I'm just confused.
> 
> See my upthread note about the trivial argument. Down below you reproduce
> this argument. So what exactly makes you think 3h is a problem, given the
> obvious work-around?
> 

[DB] I'm not sure what your "upthread argument" is.  

> >
> > I don't think you're proposing to follow Olson literally by using an alternative
> key instead of the signing key, because you pointed out the risk in my proposal
> that the alternative key might be predictable, and that you have not specified
> EdDSA in this way (as I recall).  So, I'm wondering what you're getting at here.
> 
> In ECDSA, k, the key, is fed to SHA-512 to produce l and r, each 32 bytes. l is
> then hashed with the message to produce the commitment value, and r is the
> discrete log of the public key. Obviously this introduces an annoying
> dependence on the distinguishability of SHA-512 outputs from 64 byte random
> strings, but granting that assumption this is exactly Olson's solution.
> 

[DB] Ok.

> 
> You've never explained what assumption you want to make on F, so it's
> entirely unclear if you actually are relying on a weaker assumption.
> In fact, as I argue down below, for most hash functions you actually aren't.
> 

[DB] 

> >
> > Anyway, are we going to use AES, SHA256, or what, for deterministic
> signatures?  That question is for future CFRG discussion, I suppose. Out of
> order, sorry.
> >
> > On the 3h topic of proofs, do the proposals for deterministic signature
> already have security proofs?  Since they involve the static signing key, the
> existence of such proofs seems to contradict the position of Koblitz and
> Menezes.
> >
> > Anyway, I hope there's never attack on AES, but if there is, then I can imagine
> it being only be some kind of obscure theoretical PRF attack, where the
> attacker is allowed to freely choose the plaintext blocks in some clever way,
> thereby inducing a minute amount of bias in the ciphertext blocks.  In this
> situation, AES might still be perfectly good to use in a PRG, as in AES-CTR
> encryption, and for running CTR-DRBG, because the PRF attacker lacks control
> of the plaintext blocks needed to induce the bias. Such a mixed situation would
> be similar to how SHA1 is deemed okay for some uses despite collision attacks,
> etc., and SHA2 is still okay despite key-extension attacks, and so on.
> >
> > Although I am impressed by the work done on AES, maybe I don't have as
> much confidence in it as you, first, because I have not directly worked in the
> area, and second, RC4 is widely used, yet has problems meeting the much
> milder PRG goals.
> >
> > To bring this PRF discussion back to signatures: suppose we use a
> deterministic signature based on AES, and the attacker has some strange
> plaintext block pattern that causes a minute bias in the ciphertext blocks, i.e.
> PRF attack.   As above, perhaps this would have no impact on AES-CTR,
> because the attacker never controls the counter plaintext blocks.  But small
> biases are risky for DL signatures, because the lattice attacks make them
> sensitive to this.  In this unlikely situation, generating signature k values
> generated with something more like AES-CTR, i.e. a traditional CSPRNG/DRBG,
> rather than more like AES-ECB, i.e. a deterministic signature mechanism, might
> be better.
> 
> Nobody other than you has actually proposed using AES for a PRF in this
> application. (There are several efficiency reasons not to). But let's consider

 [DB] Well, one can use NIST SP 800-90A CTR-DRBG with FIPS 186-4 version of ECDSA.

> what failure of of the compression function of an Merkel-Damgård hash
> function like SHA2 to be a PRF in the message argument means for one-
> wayness and collision attacks.
> 
> Your hypothetical attack involves a set S of blocks b such that C(k,b) has some
> easily recognizable property for a higher proportion of k then expected for a
> random function. My attacker computes a large number of k_i, and then
> calculates all C(k_i, b). Since these C(k_i,
> b) are not uniformly distributed, the probability of collision increases above
> that expected for a random function. So we are relying on PRF assumptions
> when signing with SHA2.
> 
> (A PRF distinguisher for H(k,m) gives a PRF distinguisher for C.
> What's harder is to work out the exact constants in the above).

[DB] Let's crunch the numbers a little here.  

Suppose C is SHA-1, and that my hypothetical attacker knows a secret set S of 2^20 blocks b such that C(k_i,b) has first bit 0 for all k_i.  My hypothetical attacker could probably exploit this to extract a deterministic signer's key with about 2^20 messages, probability near to one, and rather little computation.  Your collision-finder has a minutely increased chance of finding a collision in SHA1, which won't help to find the private key.  Just ball-parking the probs here: 2^40/2^160=2^-120 versus 2^40/2^159=2^-119.

You're quite right.