Subject: [Cfrg] Avoiding nonces when possible (was RE: [saag] RFC6358 (was: Re: Obligations of Candor))

From: Dan Brown <[email-masked]>
Date: Mon, 16 Jun 2014 18:19:48 +0000

Dear CFRG,

Adding a narrow, technical point to this discussion, so I've brought it back
to CFRG from SAAG.  (Hope that's correct procedure.)

Can we also avoid the random nonces from future versions of TLS and other
IETF crypto standards? (Does SSH use them? I knew a couple weeks ago, but
already forgot.) (I vaguely recall Watson Ladd already something to TLS, but
do not recall if it was avoiding the finished message or dropping the
nonce.)

Certainly, the random nonces serve a security function in some ciphersuites,
such as avoiding replay attacks and so on.  But why would random nonces be
needed in DHE or ECDHE, which have random public keys?  (I vaguely recall
that there was some arcane reason discussions over at TLS that might explain
this.  If so, then surely there's some workaround?)

Random nonces seem too easy a channel for exfiltration of secrets.  Case in
point: the attack on TLS  with a backdoored Dual_EC depends on the random
nonces.

More generally, it seems to me that the random nonces could also be
exploited if generated by corrupt or faulty implementations.  I was
surprised to learn how long faulty implementations such as goto fail/cleanup
and heartbleed could go undetected. I think it adds value to standards if
their implementations are more fault-tolerant, and possibly even harder to
corrupt.  For example, RNGs, as in the case of those RSA keys with a shared
prime would also undermine security.  E.g. if the nonce has 40 bits entropy,
and then the ephemeral key has an added 40 bits of entropy, so with a total
80 bits of entropy.  If the nonce hadn't been exposed, then the ephemeral
public DH key would be pretty strong, with 80 bits, but now it has only 40
bits of entropy relative to the nonce, making it quite weak.  As usual, this
can be fixed by fixing the RNG, but the point is that TLS should not amplify
the defect in the RNG.

Even if corrupt or faulty implementations are out of scope for IETF/IRTF,
(because, perhaps, implementations are the responsibility of the implementer
not the standard?), other corrupt RNG standards might exploit the TLS
nonces, by leaking the state. If IETF specs transmit random nonces but don't
specify the RNG, they may always open to such problems.

Of course, exfiltration could also be via other channels, not just nonces.
Probabilistic signatures are a known channel (ECDSA, RSA-PSS).
(Deterministic ECDSA solves this problem for a corrupted RNG, but not for a
corrupted ECDSA signing implementation.  Another option is eliminate the
channel, by using a more verifiably deterministic signature algorithm such
as Full-Domain RSA signatures, or to even drop using signatures, as in MQV,
keeping in that the ephemeral keys must be still be protected, see below.)
Other potential channels include IVs and ephemeral public DH keys.  (IVs can
be potentially be protected using the methods in the recent BPR paper we
discussed on an earlier thread on this list, which also aims to protect
against certain limited types of corrupted implementations.)  Ephemeral
public keys are needed forward secrecy, replay resistance, and so on, so
that would be a difficult channel to eliminate.  Maybe IETF/IRTF should do
something similar of ECDHE private keys as was done for ECDSA private keys:
dive into the RNG spec and mandate certain aspects. E.g. ensure the RNG
state is updated for every single ECDHE key generation, allow no additional
inputs or entropy updates (unless we're super sure that the RNG state and
state update function is strong enough to protect it malicious inputs). 

Best regards,

Dan

> -----Original Message-----
> From: saag [mailto:[email-masked]] On Behalf Of Stephen Farrell
> Sent: Monday, June 16, 2014 12:48 PM
> To: Trevor Perrin
> Cc: Tanja Lange; Watson Ladd; S Moonesamy; [email-masked]
> Subject: [saag] RFC6358 (was: Re: Obligations of Candor)
> 
> 
> 
> On 16/06/14 17:15, Trevor Perrin wrote:
> > On Mon, Jun 16, 2014 at 8:39 AM, Stephen Farrell
> > <[email-masked]> wrote:
> >>
> >> Well, the IETF hasn't had a DUAL-EC problem really. We don't afaik
> >> refer to that in any RFC that I can think of, at least not directly.
> >> And when the various extended random proposals were made those were
> >> not adopted thankfully.
> >
> > Not true - see RFC 6358:
> >
> > http://www.ietf.org/mail-archive/web/tls/current/msg11753.html
> 
> Ah, I guess yes you're right. Thanks for the correction.
> 
> Though there's no such extension defined I think, right? In which case
there's no
> actual harm done to the protocol, though perhaps a bit of process harm
maybe.
> 
> Does anyone have a use for 6358 or should we obsolete it or make it
historic?
> 
> S.
> 
> 
> >
> > Trevor
> >
> >
> 
> _______________________________________________
> saag mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/saag