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

Russ Housley <housley@vigilsec.com> Sun, 17 November 2013 00:33 UTC

Return-Path: <housley@vigilsec.com>
X-Original-To: dsfjdssdfsd@ietfa.amsl.com
Delivered-To: dsfjdssdfsd@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 5F38011E8143 for <dsfjdssdfsd@ietfa.amsl.com>; Sat, 16 Nov 2013 16:33:22 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -102.247
X-Spam-Level:
X-Spam-Status: No, score=-102.247 tagged_above=-999 required=5 tests=[AWL=0.000, BAYES_00=-2.599, SARE_SUB_11CONS_WORD=0.352, USER_IN_WHITELIST=-100]
Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id aX-FgKFYGx0n for <dsfjdssdfsd@ietfa.amsl.com>; Sat, 16 Nov 2013 16:33:16 -0800 (PST)
Received: from odin.smetech.net (mail.smetech.net [209.135.209.4]) by ietfa.amsl.com (Postfix) with ESMTP id 1DCA711E8105 for <dsfjdssdfsd@ietf.org>; Sat, 16 Nov 2013 16:33:16 -0800 (PST)
Received: from localhost (unknown [209.135.209.5]) by odin.smetech.net (Postfix) with ESMTP id 9F0E2F24091; Sat, 16 Nov 2013 19:33:05 -0500 (EST)
X-Virus-Scanned: amavisd-new at smetech.net
Received: from odin.smetech.net ([209.135.209.4]) by localhost (ronin.smeinc.net [209.135.209.5]) (amavisd-new, port 10024) with ESMTP id fsm1wmG1w-7Y; Sat, 16 Nov 2013 19:32:44 -0500 (EST)
Received: from [192.168.6.24] (ip-64-134-184-113.public.wayport.net [64.134.184.113]) (using TLSv1 with cipher AES128-SHA (128/128 bits)) (No client certificate requested) by odin.smetech.net (Postfix) with ESMTP id 0870FF2400F; Sat, 16 Nov 2013 19:32:43 -0500 (EST)
Mime-Version: 1.0 (Apple Message framework v1085)
Content-Type: text/plain; charset="us-ascii"
From: Russ Housley <housley@vigilsec.com>
In-Reply-To: <431FFC44-0520-48DF-8D64-62BB2753C934@me.com>
Date: Sat, 16 Nov 2013 19:32:32 -0500
Content-Transfer-Encoding: quoted-printable
Message-Id: <FD1AC557-BD1E-4878-8005-908DC4480392@vigilsec.com>
References: <CAKDKvuw6EovCf6sv5SsY=NBqYKWxc1K9yV4TZjNFbHXBrt6rDQ@mail.gmail.com> <431FFC44-0520-48DF-8D64-62BB2753C934@me.com>
To: Arnold Reinhold <agr@me.com>
X-Mailer: Apple Mail (2.1085)
Cc: dsfjdssdfsd@ietf.org
Subject: Re: [dsfjdssdfsd] What has gone wrong with RNGs in practice
X-BeenThere: dsfjdssdfsd@ietf.org
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." <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: Sun, 17 Nov 2013 00:33:22 -0000

Arnold:

>> == What has gone wrong in practice and led to actual working attacks:
>> 
>> A. Not actually using randomness at all for something that needs some
>> or all of the properties of a random bitstring.
>> 
>> Example: Sony's implementation of ECDSA failed to actually change the
>> k value between signatures; they just had a constant.[1]
>> 
>> 
> ....
>> * Underdocumented, underexplained randomness requirements.
>> 
>> Before you sniff too loudly at Sony's mistake in [1]: Pretend that you
>> are a programmer in a hurry looking at FIPS 186-2, or your favorite
>> (early) standards-body description of DSA. How well does it explain
>> the importance of making 'k' completely unpredictable for each
>> message, and how well does it explain the consequences for failing to
>> do so?
>> 
> 
> I has also been suggested that Sony's failure to generate unique k's could have been caused by a compiler that optimized the k=crypto_random(); call out of a loop.  Whether that happened or not in the Sony case, the possibility should be dealt with in any RNG standard, as the consequence of a repeated k is easy recovery of the private key. Perhaps there should be a requirement that two (or more) test signatures be generated at application startup to verify independent k's are being generated, as code that worked initially could later be recompiled with different optimization settings for a new release.. 

There should be a self-test part of the specification that detects this type of failure.  It should not be hard to turn the FIPS 140 test suite into a good-enough-to-continue / fail test.  This would envolve generating 10,000 random bits and doing some statistical checks.

Russ