Re: [Cfrg] Dual_EC_DRBG

On Thu, Jan 2, 2014 at 8:06 PM, Dan Brown <dbrown@certicom.com> wrote:
> Happy New Year to all.
>
>> -----Original Message-----
>> From: Alyssa Rowan
>> Sent: Monday, December 30, 2013 10:11 AM
>>
>> On 27/12/2013 20:43, Dan Brown wrote:
>>
>> > Repeating myself, nobody showed how the alternative P&Q could be
>> > backdoored.
>>
>> Yes, they did. Even with another point, Dual_EC_DRBG still doesn't produce
>> uniform random numbers (2^28 distinguisher¹, and a p=0.0011 consecutive
>> bit predictor² - both of which are practical attacks).
>
> 1) I too wrote about the same bias in Appendix B of:
>
> http://eprint.iacr.org/2006/117
>
> At the end of that paper, I try to suggest that the bias does not have an impact for nonces or keys. I also try to say that if indistinguishability from uniform bit strings is needed, then more bits can be truncated from the point, which is consistent with what the standards allow.
>
> This indistinguishability, under sufficient amounts truncation, say half the bits, seems a reasonable conjecture.

The standard actually says that for efficiency only 16 bits should be
removed. Tanja Lange points out that at the time "everyone" knew that
much more truncation was required.

>
> To motivate a real-world need for such indistinguishability, my eprint cited one-time pads.  Certainly one-time pads (e.g. stream ciphers) do need full indistinguishability, but in real cryptographic systems, an RNG is not really meant to provide the service of a one-time pad, because, for a one-time pad to useful, i.e. to permit decryption, it has to be reproducible.  Reproducibility undermines the main service provided by an RNG, which is unpredictability, at least in the sense of forward secrecy.  So, in retrospect, it seems that I gave a false motivation.

You do realize this is about expanding a short seed to a longer
sequence indistinguishable from random and not constantly feeding in
data?

>
> Perhaps, a better motivation would have been some information-theoretic crypto scheme, such as secret sharing.  This is outside my area of expertise.  Also, neither ANSI nor NIST standardize such info-theoretic algorithms, so at the time I thought it irrelevant, though I see now that to be a too narrow view.
>
> In summary, I agree that there are feasible distinguishers, but I fail to see how these particular distinguishers lead to practical attacks (see further specifics below "forbid") on uses of the RNG.
>
>
> 2) Though this is not a backdoor in the usual narrow sense (that somebody needs to possess a secret key to open), I am sympathetic to your concern that this is an intentional weakness.  Maybe somebody on this list knows of a better name for such an intentional open weakness?
>
>
> 3) S&S [your ref 1] advanced the understanding of the bias by amplifying the distinguisher using longer outputs. That kind of amplification is fairly well known, and I should have thought about it.
>
> S&S also conclude that the Dual_EC_DRBG is insecure, but without giving an applied example attacks (see further specifics below "forbid"), and, IIRC, without acknowledging that that some truncation parameters seem to resist the bias attack.
>
>>
>> So, if you use it to generate k for (DSA|ECDSA) signatures... or, heaven
>> forbid, a key...
>
> 1) What your does your ellipsis mean? (BTW, an elliptical implication, which is a clever, implicit pun.)
>
> 2) Your comment on k is a very interesting research question, at least to me.  My research on DSA|ECDSA indicates that there is a gap between the known necessary and sufficient conditions for the k value used in DSA and ECDSA signatures.  An impressive series of research papers, leading up to one by Bleichenbacher, shows it necessary that k avoids certain types of arithmetic bias.  My theoretical work (see ECC 2001, and Advances in ECC, Ch. 2) shows that a certain sets of conditions and models, including the k being chosen uniformly, may be sufficient for the security of ECDSA, against certain types of forgery.  The gap is that it is unknown whether certain other kinds of bias in k affect security, because they are not covered by the known attacks or the known security proofs.
>
> For a contrived example, what if k was chosen such that its SHA-3 digest ends in the bits 011.  This is bias that anybody could test, yet would not seem to lead to any attack on DSA or ECDSA.
>
> More to the point, if k was the output of Dual_EC_DRBG, and this led to an attack, then in my view this would be a new, and major result, surpassing Bleichenbacher's attack by a long shot because it exploits much less bias, and more importantly a much different type of bias.  If you are aware of such an attack, then maybe inform the CFRG (or just remind me if it is well known).

I don't trust schemes because they haven't been attacked, but because
they have reductions.

>
> 3) Schnorr has a very interesting result, albeit rather theoretical and in the generic group model, that most forms of bias in an ECC key do not make the ECDLP any easier.  It is known that some forms of bias, such as a small key lead to weaker ECDLP.  So, again there is a gap.  Any further closure of this gap would be significant.  Again, I am forced to wonder if you know something here that I don't.  I couldn't find such an attack in S&S.
>
> 4) I am less familiar with other key types, e.g. RSA, AES, and HMAC.  I vaguely recall that certain types of bias in RSA and RC4 secret keys undermine the security. I feel that this is an important area of research.  If it could be shown that the bias from Dual_EC_DRBG undermines some similar computational-based crypto scheme, then this would be an improvement in research.

Why bother when we can use something that doesn't have these issues
like HMAC_DRBG?

>
> 5)  Of course, it is always prudent to try to make all keys to uniform, if only because that maximizes the min-entropy.  (Also, it makes security proofs easier, I think.)  That's why I formulated that TPP in the my eprint of the Dual_EC_DRBG, and used the indistinguishability as the security definition.  I think now, I would also examine unguessability specifically (see next point).
>
> 6) I've since wondered a little what the more important threat models, i.e. security definitions, for a DRBG would be.  Indistinguishability is certainly very nice, especially for information-theoretic crypto, but unguessabiltiy is more important.  So, if unguessability can rely one weaker assumptions than indistinguishability, then this would be worthwhile to understand.  I touched upon the unguessabilty of Dual_EC_DRBG in my 2006 eprint, but haven't looked at the problem since 2007.  Anyway, I don't yet know what the best security definition for a DRBG would be.  Maybe the researchers on "randomness extractors" have something that could be converted over to DRBG, namely entropy condensation.

Do you understand how cryptographic proofs work? At each step two
games are shown equivalent, with some success probability reduction.
Most of the equivalences depend on indistinguishability from random.
Replace with unguessability and the whole edifice drops apart. The
whole game is based on each piece fitting into the slot carved out
from it. What does the weaker notion of "unguessability" let you do?
Unguessability is also equivalent to indistinguishability: if a
polynomial-time algorithm cannot predict a sequence of bits with
greater than .5 probability at each bit, it cannot distinguish it from
random.

By contrast, the ROM is a nicer model to work in than the standard
model: some schemes get slower to make them work in the standard
model. This is worth having the ROM.
>
>>
>> It is thoroughly unsuitable as a CSPRNG, and is obviously broken by design, as
>> was widely pointed out at the time, even before we knew for sure NSA had a
>> hand in it.
>>
>> > I would even want them to clearer.
>>
>> I would want it removing from the standard entirely, as thoroughly and
>> completely discredited.
>
> 1) Just wondering: do you also dispute that benefit of having an RNG whose security basis is number-theoretic?  What about just for algorithm agility?
>
> I still personally recommend number-theoretic RNGs for security: mainly because I feel more confidence in ECC, and other number-theoretic algorithms, than in symmetric crypto algorithms.  My feeling here is rather vague, and largely based on familiarity, but also philosophically based on ECC and RSA being something innate, whereas symmetric key seems devised.  But I could easily understand how others have the exact opposite feeling.  So, I generally did not expect much adoption of number-theoretic RNGs.

If AES breaks a number-theoretic RNG doesn't help us here. In for a
penny, in for a pound.

>
> There are other number-theoretic algorithms.  If they have been standardized and proven secure, then they deserve consideration too.  But I doubt that their standards have received as much attention as the Dual_EC_DRBG.  Anyway, I haven't studied any of these, so cannot recommend them personally.
>
> Have there been any advances in the security analysis of the Dual_EC_DRBG algorithm since 2007?  Even though people seem motivated to discredit it?  If not, then I would argue that is a good sign, but also for other unaffected NIST DRBGs.
>
> I haven't really studied the HMAC_DRBG, Hash_DRBG or CTR_DRBG from NIST SP 800-90A.
>
>
> 2) Over the last few days, I've been trying to see things from a wider perspective.
>
> My position on the standard has recently changed.
>
> Implementers (and users) may have placed more trust in the standard than I thought, and they may have been less informed about the widely publicized potential backdoor than I thought.
>
> In other words, all the publicity may have been ineffective at preventing the alleged backdoor from being exploited, contrary to my belief.  The standard should not have included the default P&Q.
>
> That all said, despite the deficiency of the standard, I feel implementers still have some responsibility to keep up with the news and research about crypto, given that standards need to be stable documents for interoperability.

A major vendor of cryptographic software was paid $10 million to make
it the default, and didn't change it until this year. And you call
that unexploited? What on earth was that $10 million for? The CMPV
process was insisting implementors use the default P&Q.

>
> In summary, my position on the standards, and standards process, is not well-defined.
>
> To clarify my past position, I said "not subverted standard", but I did not mean to rule out a backdoor in the default P&Q, just that the publicity would render any subversion inoperable, and that there could other things than standards enabling such subversion.  But now I see that I was wrong.
>
> My position on the algorithm Dual_EC_DRBG, with properly random, backdoor-free, P&Q is the same as in 2007 (see also bias discussion above), which is that it is secure.

And of course your employer has the patent on it.

>
>>
>> > Reported, yes.  But AFAIK, not published.
>>
>> Unless you know of another EC-based RNG published by NIST in 2006, all
>> doubt has been removed that it is, in the NSA's words, 'enabled'.
>>
>
> Reports I've seen say "suggest" or "reported", which leaves doubt.  Please send me the links to the correct reports.
>
> Personally, I still don't know for sure if the default P&Q are backdoored, but it would be prudent for implementers and users to assume that they are.
>
>> Moreover, the internal NSA memo discussed by NYT might literally name
>> you, given your name is on the patent³ along with Vanstone, so I would
>> understand why you might have a vested interest in its publication.
>> You'd have to ask NYT for that, I suppose.
>>
>> I'm going to ask you directly, Dan: Have you had any contact with the  SIGINT
>> Enabling Project that you know of? I mean, you even talk specifically about
>> "escrow keys" in that patent. That seems directly relevant to their work.
>
> 1) No contact that I know of.  I never heard of "SIGINT Enabling Project" until the recent news.

So you discover this backdoor in a NIST standard, and then do what?

>
> 2) At some point, I clued into the possibility of a backdoor, and, among other things, tried to make sure the possibility was at least publicly known, at first quietly: with a patent, and with a comment within my March 2006 eprint.  Later, others raised much more publicity, which seemed sufficient to me.  I had expected such publicity to cause the proposers, X9F1 and NIST to withdraw the default P&Q from the standard.

And you didn't submit a public comment to NIST or a letter to CRYPTO?
You had a footnote in your March 2006 paper, not a note explaining
that the backdoor was real as your patent indicates you knew. The
discovery by S&F in 2007 got publication: why not a two-for-one in
2006? In 2005 you filed for a patent instead of telling everyone this
was broken. These actions don't seem like the actions of someone
trying to promote strong cryptography in an open process: they seem
like the actions of someone trying to set up then an excuse that
"well, I told you but you didn't listen" when the truth finally
emerged.

This is really a big tangent from the work of the CFRG, but it
illustrates that we should be very conservative in what we do and not
accept a few member's word as gospel. Well-known implementors and
cryptographers have been known to make big blunders, and if they do
not say they know of an attack, they might be lying. By contrast, if
they have a proof or an attack, you can always ask them to show it.

Sincerely,
Watson

>
>>
>> ___
>> 1. Shoenmakers & Sidorenko [2006] <http://eprint.iacr.org/2006/190.pdf>
>> 2. Gjøsteen [2005], comments to draft NIST SP 800-90A
>> 3. <http://patents.justia.com/patent/8396213>
>
>
> ---------------------------------------------------------------------
> This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg
>

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin