Re: [Cfrg] draft-irtf-cfrg-randomness-improvements-00 vs currently-deployed alternatives

[Christopher Wood <[e-mail]>]

Hi Bryan,

Apologies for the delay. Please see inline below.

On Wed, Jun 13, 2018 at 8:07 PM Brian Smith <[e-mail]> wrote:
>
> Stanislav V. Smyshlyaev <[e-mail]> wrote:
> > About deterministic signature functions.
> >
> > Actually the worst case scenario we are defending against is a complete
> > breakdown of all existing entropy sources (say, because of failure of
> > hardware RNG) on a certain computer.
>
> The draft says "In the NAXOS key exchange protocol, raw entropy output
> x is replaced by H(x, sk), where sk is the sender's private key.
> Unfortunately, as private keys are often isolated in HSMs, direct
> access to compute H(x, sk) is impossible. An alternate yet
> functionally equivalent construction is needed. [...] Implementations
> SHOULD apply this technique when indirect access to a private key is
> available and CSPRNG randomness guarantees are dubious"
>
> If the private key `sk` is available to the user then one could use
> NAXOS or a variant of it.
>
> If the private key `sk` is not available but the HSM lets the user
> choose the nonce then the user can extract `sk` from the HSM by using
> the standard ECDSA attack, and then use NAXOS or a variant of it.
>
> If the private key `sk` is not available and the HSM rightly doesn't
> let the user choose the nonce then the only way one can follow the
> recommendation to use a deterministic signature function is if the HSM
> implements deterministic ECDSA itself. But it is really uncommon for
> an HSM to implement deterministic ECDSA, especially because
> deterministic ECDSA is non-compliant with all specifications for
> ECDSA. Note: I'm not saying this is good or bad.
>
> The main consequence of this is that, practically speaking, it seems
> like one can't really use deterministic ECDSA except in cases where
> one could also use NAXOS or a similar thing. Thus the "e.g.,
> deterministic ECDSA [RFC6979]" seems to contradict "direct access to
> compute H(x, sk) is impossible."
>
> Similarly, APIs for HSMs generally don't let one choose the salt for
> PSS signature generation, though in some implementations one can set
> the salt length to zero to get a deterministic PSS signature. However,
> other work on PSS in TLS has already tried to make it so an
> implementation (e.g. mine and a few other new implementations) need
> only support specific non-zero lengths of salts. Thus one probably
> can't rely on deterministic PSS being available either.
>
> Similarly, TLS 1.3 says that we must use PSS instead of PKCS#1
> signatures so a TLS 1.3 implementation wouldn't need to implement
> PKCS#1 signing. Further, everybody knows that we shouldn't use the
> same private key for two different algorithms, so if we have an RSA
> private key for use with TLS 1.3 then we shouldn't use it to make
> PKCS#1 signatures; ideally the HSM would enforce that.
>
> Thus, the requirement that "Sig MUST be a deterministic signature
> function" seems unrealistic except in cases where a new mechanism may
> not even be useful since NAXOS or similar would work fine.
>
> > The problem
> > occurs in another case  - when a random value used in ECDSA/EC-RDSA is
> > obtained from the same potentially broken entropy source.
>
> Right. One the one hand you don't want to trust the ECDSA's
> implementation's RNG. On the other hand, ECDSA implementations don't
> generally expose APIs that let you replace their RNG unless they also
> give you the raw private key, in which case we wouldn't need to use
> ECDSA to derive the initial key.
>
> > Of course it would be better to mix-in entropy, but we'd like to stress that
> > the main reason of using the techniques described in our draft is to address
> > the possible worst-case scenarios of having no working entropy sources –
> > when we cannot rely on any mixed-in entropy at all.
>
> The point I'm trying to make is subtle:
> 1. Obviously, we don't want to rely on having any entropy.
> 2. Less obviously, if there is entropy available then it seems silly
> to ignore it.
>
> > In fact the
> > problem we're trying to address here is the following. If we do not have any
> > actual entropy, then, in case of using our techniques, we'll leverage the
> > security of such worst-case scenarios – but – if we also have two equivalent
> > environments (two cloned virtual machines, for example) and two tags are
> > equivalent, then we can do nothing at all: no entropy and no differences
> > between two environments would lead to completely equivalent outputs.
>
> There are four cases to consider:
> 1. A working entropy source is available, and the two tags are the same.
> 2. A working entropy source is available, and the two tags are different.
> 3. The entropy source is broken, and the two tags are the same.
> 4. The entropy source is broken, and the two tags are different.
>
> In your paragraph above, you are describing case #3. But what about case #1?
>
> BTW, I think that you and I may be thinking of different use cases for
> draft-irtf-cfrg-randomness-improvements-00. The question I original
> set out to answer is "Would it be better to use
> draft-irtf-cfrg-randomness-improvements-00 instead of RFC 6979 when
> implementing ECDSA?" From re-reading the draft I think that target use
> case might have been more about "How can we strengthen key agreement
> (e.g. ECDH)?"
>
> Since I posted my question I actually came up a few with more
> questions, but the general question I think is still unanswered is
> "Why is this mechanism better than using other established
> mechanisms?" In particular, why is this mechanism better than a
> variant of NAXOS or better than using the HMAC DRBG? Speaking from my
> own experience and motivation for reading the document, that's the main
> question that I think is left unanswered in the draft.

I think the delta between what's proposed and what's implemented is
small. This is what's proposed:

  PRF(KDF(G(x) || H(Sig(sk, tag1))), tag2)

Here, G(x) is the CSPRNG, which uses whatever entropy is available at
the time on the caller, which
is not necessarily where the signature is computed. The input to the
KDF is thus effectively whatever
randomness is available and a function of the private key, which I'll
denote as r. The construction then
simplifies to:

  PRF(KDF(r), tag2)

This is basically HKDF -- Expand(Extract(r), tag2, x). (I would prefer
it be rewritten using this common terminology
to make it more readable.) It could also be recast as the HMAC DRBG as
outlined in Section 3.3 of RFC 6979
by setting entropy_input to r and nonce to bits2octets(H(tag2)), for example.

So the difference between this and NAXOS or HMAC DRBG as specified in
Section 3.3 is how the private key
is used. In both NAXOS and RFC 6979, it's assumed the caller has
direct access to the private key, which is not
the assumption here. That's the extent of the difference, as I see it.
Do you think unifying terminology around RFC
6979 would help emphasize that difference?

Thanks,
Chris