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

Arnold Reinhold <agr@me.com> Sun, 17 November 2013 00:06 UTC

Return-Path: <agr@me.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 ACE9811E80E6 for <dsfjdssdfsd@ietfa.amsl.com>; Sat, 16 Nov 2013 16:06:02 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -5.725
X-Spam-Level:
X-Spam-Status: No, score=-5.725 tagged_above=-999 required=5 tests=[AWL=0.522, BAYES_00=-2.599, RCVD_IN_DNSWL_MED=-4, SARE_SUB_11CONS_WORD=0.352]
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 PKXNFe1BB2+k for <dsfjdssdfsd@ietfa.amsl.com>; Sat, 16 Nov 2013 16:05:56 -0800 (PST)
Received: from st11p01mm-asmtp001.mac.com (st11p01mm-asmtp004.mac.com [17.172.204.239]) by ietfa.amsl.com (Postfix) with ESMTP id D618711E80E2 for <dsfjdssdfsd@ietf.org>; Sat, 16 Nov 2013 16:05:56 -0800 (PST)
Received: from new-host-3.home (pool-108-7-220-89.bstnma.fios.verizon.net [108.7.220.89]) by st11p01mm-asmtp001.mac.com (Oracle Communications Messaging Server 7u4-27.08(7.0.4.27.7) 64bit (built Aug 22 2013)) with ESMTPSA id <0MWD001PKS9FLO90@st11p01mm-asmtp001.mac.com> for dsfjdssdfsd@ietf.org; Sun, 17 Nov 2013 00:05:39 +0000 (GMT)
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10432:5.10.8794, 1.0.14, 0.0.0000 definitions=2013-11-16_02:2013-11-15, 2013-11-16, 1970-01-01 signatures=0
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 spamscore=0 suspectscore=2 phishscore=0 adultscore=0 bulkscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=7.0.1-1308280000 definitions=main-1311160224
Content-type: text/plain; charset="us-ascii"
MIME-version: 1.0 (Mac OS X Mail 7.0 \(1822\))
From: Arnold Reinhold <agr@me.com>
In-reply-to: <CAKDKvuw6EovCf6sv5SsY=NBqYKWxc1K9yV4TZjNFbHXBrt6rDQ@mail.gmail.com>
Date: Sat, 16 Nov 2013 19:05:37 -0500
Content-transfer-encoding: quoted-printable
Message-id: <431FFC44-0520-48DF-8D64-62BB2753C934@me.com>
References: <CAKDKvuw6EovCf6sv5SsY=NBqYKWxc1K9yV4TZjNFbHXBrt6rDQ@mail.gmail.com>
To: Nick Mathewson <nickm@torproject.org>
X-Mailer: Apple Mail (2.1822)
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:06:03 -0000

On Nov 15, 2013, at 11:36 AM, Nick Mathewson <nickm@torproject.org> wrote:

> 
> == 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.. 

Arnold Reinhold