Re: [dsfjdssdfsd] What has gone wrong with RNGs in practice

[Nick Mathewson <[e-mail]>]

On Fri, Nov 15, 2013 at 9:42 PM, Theodore Ts'o <[e-mail]> wrote:
> On Fri, Nov 15, 2013 at 11:36:14AM -0500, Nick Mathewson wrote:
>> CC. Theoretically unsound pool constructions
>>
>> See for example the recent paper on the Linux /dev/*random devices'
>> constructions [10].
>
> CC is a bit vague, and is redundant with AA, BB, and EE in your list.
>
> The assertion made in [10] is that an attacker who can control all of
> the entropy inputs in such a way that defeats the entropy estimator
> (which is EE), could result in a failure of guarantees such as BB
> (recovery after compromised state).
>
> Whether or not an attacker could control all entropy inputs in such as
> way that it could defeat the entropy estimator was not actually shown
> in [10], and I'm not entirely sure that insisting on a theoretical
> model which requires that a design should be robust against by
> arbitrary control of the entropy sources (as opposed to auditing the
> entropy sources actually *used* by the RNG) is a all that useful ---
> but that's aside from the point I'm trying to make here, which is if
> you're going to have a list of potential RNG failures, they should be
> a specific set of things that you can look for, and not something
> vague and overarching such as "bad design of the RNG pools".


Let me try to clarify what I meant by CC.  I agree that my original
wording was sloppy, and even though I was listing issues which to my
(limited!) knowledge have never actually led to a serious attack,
that's no excuse for being vague.  (To my further discredit,
re-reading what I wrote, I don't think it actually *could* have meant
what I meant it to mean, and the example I chose was a stupid one too.
Whoops.)

So here's what I should have said:

== What has gone wrong, and is probably bad, but has not (AFAICT) led
to any publicized attacks yet:

[...]

CC. Unproven cryptographic properties

We have (and continue to come up with) several definitions of what it
means for an RNG construction to be secure. We have some constructions
which we can prove to meet these definitions (though they may have
other issues), and some which don't seem to have security proofs but
which many reasonable practitioners believe to be secure anyway.

*All things being equal*, we would expect to have more confidence in
constructions where we can prove something useful about their security
properties.

(However, I am not personally aware of any example ad-hoc
cryptographic RNG constructions which lacked a security proof,
survived close scrutiny by sensible practitioners, and then later
turned out to be much more broken than expected in some cryptographic
way.  That' s why I'm classifying this as "probably problematic"
rather than "actually leading to attacks."  But if there's a counter
example, I would be excited to learn about it so that I can strengthen
my "you should probably make sure you have a proof" argument.)

((Further, I am aware that "all things" are never quite "equal", and I
would personally sidle away from quite a few current proven
constructions for other engineering reasons.))

best wishes,
-- 
Nick Mathewson