[Cfrg] NUMs/rigidity security (Re: [CFRG] Safecurves v Brainpool / Rigid v Pseudorandom)

Adam Back <adam@cypherspace.org> Thu, 16 January 2014 12:05 UTC

Return-Path: <adam@cypherspace.org>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 523681AE2A7 for <cfrg@ietfa.amsl.com>; Thu, 16 Jan 2014 04:05:02 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Level:
X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_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 t_CbXFVhxcyB for <cfrg@ietfa.amsl.com>; Thu, 16 Jan 2014 04:05:01 -0800 (PST)
Received: from mout.perfora.net (mout.perfora.net [74.208.4.194]) by ietfa.amsl.com (Postfix) with ESMTP id 0730D1AE097 for <cfrg@irtf.org>; Thu, 16 Jan 2014 04:05:01 -0800 (PST)
Received: from netbook (c107-70.i07-27.onvol.net [92.251.107.70]) by mrelay.perfora.net (node=mrus2) with ESMTP (Nemesis) id 0Le6Ka-1VZymZ0PYS-00qPAy; Thu, 16 Jan 2014 07:04:44 -0500
Received: by netbook (Postfix, from userid 1000) id 5D9082E283F; Thu, 16 Jan 2014 13:04:36 +0100 (CET)
Received: by flare (hashcash-sendmail, from uid 1000); Thu, 16 Jan 2014 13:04:35 +0100
Date: Thu, 16 Jan 2014 13:04:34 +0100
From: Adam Back <adam@cypherspace.org>
To: David McGrew <mcgrew@cisco.com>
Message-ID: <20140116120434.GA26078@netbook.cypherspace.org>
References: <20140113230750.6111382.6841.8590@certicom.com> <52D48450.3070701@akr.io> <810C31990B57ED40B2062BA10D43FBF5C1F190@XMB116CNC.rim.net> <52D59C35.10807@cisco.com> <810C31990B57ED40B2062BA10D43FBF5C2217A@XMB116CNC.rim.net> <52D72201.6030803@cisco.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Disposition: inline
In-Reply-To: <52D72201.6030803@cisco.com>
User-Agent: Mutt/1.5.21 (2010-09-15)
X-Hashcash: 1:20:140116:mcgrew@cisco.com::iGHBr4UQAqW5aoxP:03rVG
X-Hashcash: 1:20:140116:dbrown@certicom.com::GZ5sunVX5qXuKiV1:000000000000000000 0000000000000000000000001vkw
X-Hashcash: 1:20:140116:cfrg@irtf.org::S7fqqmFBeYC7UQli:00001Jir
X-Hashcash: 1:20:140116:adam@cypherspace.org::lQ9zmgI8q1sw3PiR:00000000000000000 0000000000000000000000001qsL
X-Provags-ID: V02:K0:7sq/vAhR9jxTagoPwsgTsvNzqdbLkB2VgR10Q5XbUyG cHq+0fP3WvtEJUVT8jsCkYo9kzxYSsfibV0xCCeIs289wsCJQ/ 1NsCx9GCa0qCLTWJbk7wFC38pWcbqUkrI7zMDirBKr/69Sfi6W o25OVhH3TcYaTcDxK8IDgy8DVjiUkqJHQqZ6mqsbnE16n/malH r0IBz1s6nYWk2oTmi2TNoKG9k5XWexCtiZza2q0Nfax9dBBGPK gW8AtlyuBLdPVl/OfMzlO/7eoxgeYd4LvqGBecFgTCSpxh2i9n 25YGoo1TFwP9S/ximYhSU5KQdHS7pI+YmNxpxf7aR01Z+97zG9 NP3p7XacoyAHubB03dzfkoIW12Kkh3PSUolU2amZR
Cc: Dan Brown <dbrown@certicom.com>, Adam Back <adam@cypherspace.org>, "'cfrg@irtf.org'" <cfrg@irtf.org>
Subject: [Cfrg] NUMs/rigidity security (Re: [CFRG] Safecurves v Brainpool / Rigid v Pseudorandom)
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Thu, 16 Jan 2014 12:05:02 -0000

You know in principle we ought to stick to something with low entropy for
the NUMs/rigidity seed.  I commented previously for example that someone can
do a fair bit of grinding by building a catalog of headlines, quote
dictionaries, and permuting their punctuation, white space etc.  Also
permuting arbitrary implementation choices (encoding, endianness, equally
plausible rigid choices, etc) So possibly the digits of pi are more
convincing than some obscure literary quote or a headline.  The point is to
start from an ungrindable starting point, with canonicalized choices at each
step.  I think so far the NUMS argument is probably gamable to a non-trivial
extent due to the above effects.

ie for secure NUMs you actually need to canonically encode all fo the
arbitrary choices in a standardized language, sort them, and select the
arbitrary choices at all levels, using the deterministic PRNG seed off pi. 
And even the PRNG design itself needs to be standardized, otherwise its
design variants also admit yet more bits.

The NUMs argument is good but so far is probably itself gameble, we need a
NUMs standard to remove as many of those variabilities as possible.

Adam

ps people might want to trim the quoted text in places, I almost missed some
comments they were that many pages down of recursive unedited quoting!