[TLS] (EC)DSA potential problems (ECC "brittleness")

[[e-mail] (Martin Rex)]

Peter Gutmann wrote:
> Yaron Sheffer <[e-mail]> writes:
> 
> >I think we've been through all these arguments (on both sides of the issue)
> >over the last week, with the exception of "ECC brittleness". Can you please
> >clarify what you mean by that?
> 
> So with RSA-authenticated DH all you need to do is use a constant-time modexp
> on the server when you sign and pre-encode the PKCS #1 expected result and use
> a constant-time memcmp() on the client when you verify and you're OK.  If you
> did that ten years ago then you're safe against pretty much everything that's
> come along since then.
> 
> With ECDLP-based algorithms in contrast there's a whole range of issues you
> need to take into account, the worst of which is the distressing propensity of
> the DLP algorithms to leak the private key if you get even the tiniest detail
> wrong.  Not only do you have to get all of these finicky details exactly
> right, but every now and then someone points out a new issue that you then
> need to retroactively patch into your existing code base.  For example if you
> used the recommended (until not too long ago) way to generate your k for 
> (EC)DSA then you'd leak a tiny bit of your private key on each signature
> (again, that nasty propensity of DLP algorithms to leak the private key).
> That's what I meant by ECC, and DLP in general, brittleness.


Which
  "recommended (until not too long ago) way to generate your k for (EC)DSA"
are you referring to specifically?

Is or was this part of FIPS 186-x for DSA--or some X9.xx document for ECDSA
that do not have (not having coughed up the $$), and is that specific
issue sufficient to enable the attack described in this paper:

  Jean-Charles Faugere, Christopher Goyet and Guenael Renault
  "Attacking (EC)DSA Given Only an Implicit Hint"

  http://www-polsys.lip6.fr/~goyetc/doc/ImplicitECDSA_Goyet.pdf


(My own understanding of the crypto math is rather poor)


What's also irritates me is that every intentional weaknesses or bias in
a DRNG could enable this attack.  IIRC, EC_Dual_DRNG has both, a bias
and a weaknesss.  It also makes me feel uneasy about secret RNG designs
such as Intels RDRAND--on top of the Problem that RDRAND expands
1.5 GBit/s alleged real randomness into 6 GBit/s weakened output
(rather than the reverse, compressing it).


The fact that TLS requires a new and independent signature on the
(EC)DHE params in ServerKeyExchange on every full handshakes makes
it easy to obtain (EC)DSA signatures in large numbers and short time
through successful and therefore unsuspicious "full TLS handshakes".


Btw. where would one find the information necessary to implement
(EC)DSA safe with respect to the state-of-the-art?  The references
in rfc4492 (ECC for TLS) and rfc6460 (Suite B Profile for TLS)
appear somewhat static:
  http://tools.ietf.org/html/rfc6460#section-7
  http://tools.ietf.org/html/rfc4492#section-10

Wouldn't it make sense to first ensure that implementors _know_ what
known problems they have to watch out for TODAY (which is not necessarily
part of the original algorithm specs), before we ask them to prefer/migrate
to such algorithms?


-Martin