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

Nick Mathewson <> Sun, 17 November 2013 03:24 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 073EB11E821A for <>; Sat, 16 Nov 2013 19:24:20 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: 0.542
X-Spam-Status: No, score=0.542 tagged_above=-999 required=5 tests=[AWL=-0.291, BAYES_20=-0.74, FM_FORGED_GMAIL=0.622, J_CHICKENPOX_21=0.6, NO_RELAYS=-0.001, SARE_SUB_11CONS_WORD=0.352]
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id LQn-qC9boH9A for <>; Sat, 16 Nov 2013 19:24:19 -0800 (PST)
Received: from ( [IPv6:2a00:1450:4010:c03::22c]) by (Postfix) with ESMTP id 2BBEF11E83DE for <>; Sat, 16 Nov 2013 19:24:18 -0800 (PST)
Received: by with SMTP id ep20so3932672lab.3 for <>; Sat, 16 Nov 2013 19:24:18 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20120113; h=mime-version:sender:in-reply-to:references:date:message-id:subject :from:to:cc:content-type; bh=Z3acNPrHLp4ISFrUoKPYdv+MEtD9IiXzhS/ANdWt79I=; b=xKjRd96XAuw4xod5hWq+77m2SJLeP8Y41vEkxlJR42cB53GHfsPU0yb/8cTgyDvulc YD2DS4NFew9rQHwSRbOD9pHwuwXoC1v3hBIHLdzt6ixt3f9XyWmy9A6fb68AKXiNE7tJ 2W09Z19IHS47lR8/XayFInZ853XzaPpT2yHAL00NumTnu1O94MbbxZvfmeK9YlV6fbN9 9aGznQkkWUikZmOiO8qRRvUx5lEgAdc/Dnyj4ISGD/mQJmIMsxOEnsxJEChRmrtfIK1x OR985eRvU+QtbU7ivwj/JxYAOMb5uFuyvcGvmCT95ATuwRyyqytqZX6cEeQ5pqweE8Ft mt4Q==
MIME-Version: 1.0
X-Received: by with SMTP id c10mr698007lae.48.1384658658107; Sat, 16 Nov 2013 19:24:18 -0800 (PST)
Received: by with HTTP; Sat, 16 Nov 2013 19:24:18 -0800 (PST)
In-Reply-To: <>
References: <> <>
Date: Sat, 16 Nov 2013 22:24:18 -0500
X-Google-Sender-Auth: q23WUMqzyq-G9VI35NGZifpuTXA
Message-ID: <>
From: Nick Mathewson <>
To: Theodore Ts'o <>
Content-Type: text/plain; charset="ISO-8859-1"
Subject: Re: [dsfjdssdfsd] What has gone wrong with RNGs in practice
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: "The dsfjdssdfsd list provides a venue for discussion of randomness in IETF protocols, for example related to updating RFC 4086." <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Sun, 17 Nov 2013 03:24:20 -0000

On Fri, Nov 15, 2013 at 9:42 PM, Theodore Ts'o <> 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.

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

(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