[dsfjdssdfsd] Discussion: Malicious Entropy Attacks: Eggs, and Baskets

Alyssa Rowan <akr@akr.io> Tue, 11 March 2014 19:15 UTC

Return-Path: <akr@akr.io>
X-Original-To: dsfjdssdfsd@ietfa.amsl.com
Delivered-To: dsfjdssdfsd@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 5F80D1A07BE for <dsfjdssdfsd@ietfa.amsl.com>; Tue, 11 Mar 2014 12:15:37 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.003
X-Spam-Level:
X-Spam-Status: No, score=-0.003 tagged_above=-999 required=5 tests=[BAYES_20=-0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id dhufPGjkQkfP for <dsfjdssdfsd@ietfa.amsl.com>; Tue, 11 Mar 2014 12:15:35 -0700 (PDT)
Received: from entima.net (entima.net [78.129.143.175]) by ietfa.amsl.com (Postfix) with ESMTP id BC5C81A075F for <dsfjdssdfsd@ietf.org>; Tue, 11 Mar 2014 12:15:34 -0700 (PDT)
Received: from [10.10.42.10] (cpc5-derb12-2-0-cust796.8-3.cable.virginm.net [82.31.91.29]) by entima.net (Postfix) with ESMTPSA id 7B5E560369 for <dsfjdssdfsd@ietf.org>; Tue, 11 Mar 2014 19:15:28 +0000 (GMT)
Message-ID: <531F6068.4080907@akr.io>
Date: Tue, 11 Mar 2014 19:13:44 +0000
From: Alyssa Rowan <akr@akr.io>
MIME-Version: 1.0
To: dsfjdssdfsd@ietf.org
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Archived-At: http://mailarchive.ietf.org/arch/msg/dsfjdssdfsd/8DUibI-vXrRqta58V47IfDT5twg
Subject: [dsfjdssdfsd] Discussion: Malicious Entropy Attacks: Eggs, and Baskets
X-BeenThere: dsfjdssdfsd@ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: "The dsfjdssdfsd list provides a venue for discussion of randomness in IETF protocols, for example related to updating RFC 4086." <dsfjdssdfsd.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/dsfjdssdfsd>, <mailto:dsfjdssdfsd-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/dsfjdssdfsd/>
List-Post: <mailto:dsfjdssdfsd@ietf.org>
List-Help: <mailto:dsfjdssdfsd-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/dsfjdssdfsd>, <mailto:dsfjdssdfsd-request@ietf.org?subject=subscribe>
X-List-Received-Date: Tue, 11 Mar 2014 19:15:37 -0000

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

djb posted a blog <http://blog.cr.yp.to/20140205-entropy.html> last
month which presents some interesting viewpoints on RNG design,
examining a hypothetical¹ scenario in which a malicious entropy source
to an otherwise good RNG can cause the sorts of havoc an attacker
dreams of.

It advocates that instead of the common
continuous-entropy-pool-injection designs we see today, a better
approach might be to make RNGs with a sharp transition between two
states:-

A. An entropy-gathering 'setup' state, collecting enough entropy for
   one really good 256-bit key, reading more-trusted entropy sources
   after less-trusted ones and using a high-cost hash function (to
   really increase the work a malicious entropy source would have to
   do); and then,

B. A 'running' state, which uses that key, holds it securely, and runs
   a good deterministic random bit generator to generate as much
   randomness as we need [up to some limit].

Specifically, djb advocates running A -then- run B (presumably, up to
some defined limit, as no DRBG is sound _ad infinitum_, then we'd have
to block and go back to A to gather another key?).

This is the exact opposite of what we usually do today, which would be
to run A continuously in parallel (possibly in many pools) and using B
in limited quantities to extract randomness from the running pool/s if
and when we need it.

I think that's a fascinating concept: although it runs counter to
usual existing practice, it does so specifically to minimise the
opportunity an attacker has to manipulate the RNG state. (One wonders
about the effect that might have on the window for an attacker to
observe the RNG state, although this _might_ be more defensible as
once in state B, it doesn't seem to provide them with an in-band path
to then exfiltrating it? Out-of-band exfiltration could be a problem
no matter which way you sliced it, although if it occurred, it would
be a live problem for longer, until the next re-key.)

It relies entirely on the DRBG to be strong for our external
prediction resistance. While this has potential pitfalls, it also has
potential benefits. After all, the DRBG is the deterministic element
of an RNG: the testable, easily-verifiable part (at least, compared to
the entropy sources). We already know several approaches that'll
probably work well (e.g. HMAC_DRBG; CTR_DRBG; a strong stream cipher
like ChaCha20 with a monotonically-increasing counter, maybe?) as well
as, of course, ones which infamously won't work out so well (e.g.
Dual_EC_DRBG).

I'm not completely sure if this type of "discrete-setup" RNG is a good
balance, but it's certainly an interesting one about which others may
have some thoughts...?

___
1. *Currently* hypothetical, but alarmingly possible for a sufficiently-
   determined attacker with a penchant for malicious microcode - and we
   know sufficiently-determined and funded attackers exist, and like
   weak RNGs. Maybe we could even see a PoC someday?

- -- 
/akr
-----BEGIN PGP SIGNATURE-----

iQIcBAEBCgAGBQJTH2BoAAoJEOyEjtkWi2t6hE4P/3SmC3EDQvLbIUHxahpWj7j7
hd94kNr4IfByMKqwk7zMw6pW1qFsdrKvbFp7ZwEC/ZglbUptZ1taQyVDMX/ii9ZD
z7lbGDwWJN6XtLR5hn6sU5m1wkUdCHJ6FeQKgMH7sLu9tRilG6XekuYVu7bcpluQ
FJpt5MbgPjRAz43uDCO9FQrEfI0IljIIlmdmJWIAREvvaJfXwV/RnBf2mrTMUTFm
I+tyvaJn7TLc3w3L0tU+7MbRghq8UP611qeeTjpsn3HUjY6xUvSaKzeGL4J6xV3U
tq8kVc6sWCe85W8OcV2yXi7fYYAuxbxSPops83mRb2YH0Ks8Pk68o3PCvty79YpS
NeSM/jiYe0GGr3mtEXsIeYirVSdLxJuEP0lUxqSHABgHS8MsxrHQOgcR//s0V/B5
GiBwvE3xE2tf55WgGomPhs2Kqmpa6nsagwrkY6YLk5W+bV12WiCIM447DKzu86mg
O4n6DrQ7h8MMwSIt2qb90Cye48IncuXczJWIVJK3ZO6TMBR1JemwSM1WP35GUtH9
QdOAKPr+zWEwAangT8ztx05XrPAq5cxzclX9ykrF43HQhizjicX9KgcsGSR3GAYe
1b3Y9IbLQc6xMWg0iOjs6Yoo3ngiF4Z8Z75n8lbl3/PoolywGRGj3unpyvSQ4qVM
ByE6GO0YsjeIbrMo/tNs
=PuzB
-----END PGP SIGNATURE-----