[dsfjdssdfsd] Blum-Blum-Shub ambiguity in 4086 ...

Dan Brown <dbrown@certicom.com> Mon, 17 March 2014 14:43 UTC

Return-Path: <dbrown@certicom.com>
X-Original-To: dsfjdssdfsd@ietfa.amsl.com
Delivered-To: dsfjdssdfsd@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com []) by ietfa.amsl.com (Postfix) with ESMTP id 373241A041D for <dsfjdssdfsd@ietfa.amsl.com>; Mon, 17 Mar 2014 07:43:08 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001] autolearn=ham
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id dPTknmDpGPqh for <dsfjdssdfsd@ietfa.amsl.com>; Mon, 17 Mar 2014 07:42:55 -0700 (PDT)
Received: from smtp-p01.blackberry.com (smtp-p01.blackberry.com []) by ietfa.amsl.com (Postfix) with ESMTP id 6779E1A0401 for <dsfjdssdfsd@ietf.org>; Mon, 17 Mar 2014 07:42:55 -0700 (PDT)
Received: from xct108cnc.rim.net ([]) by mhs211cnc.rim.net with ESMTP/TLS/AES128-SHA; 17 Mar 2014 10:42:47 -0400
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT108CNC.rim.net ([fe80::8dc1:9551:6ed8:c618%17]) with mapi id 14.03.0174.001; Mon, 17 Mar 2014 10:42:46 -0400
From: Dan Brown <dbrown@certicom.com>
To: "dsfjdssdfsd@ietf.org" <dsfjdssdfsd@ietf.org>
Thread-Topic: Blum-Blum-Shub ambiguity in 4086 ...
Thread-Index: Ac9B7i5ZEVD92qlgTACcsVmMMe395g==
Date: Mon, 17 Mar 2014 14:42:44 +0000
Message-ID: <810C31990B57ED40B2062BA10D43FBF5C59197@XMB116CNC.rim.net>
Accept-Language: en-CA, en-US
Content-Language: en-US
X-MS-Has-Attach: yes
x-originating-ip: []
Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg=SHA1; boundary="----=_NextPart_000_003B_01CF41CD.A1226240"
MIME-Version: 1.0
Archived-At: http://mailarchive.ietf.org/arch/msg/dsfjdssdfsd/dLGTXNKL4pvwK1kuG_cUKTgFBjQ
Subject: [dsfjdssdfsd] Blum-Blum-Shub ambiguity in 4086 ...
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: Mon, 17 Mar 2014 14:43:08 -0000

Two issues:


1.      If it is unclear to me from the 4086 description of BBS whether the
state s_i is to be updated after each output. I believe that the state
should be updated to improve backtracking resistance.  (Otherwise, it would
be affected by a similar weak backtracking attack to the one DSS RNG, i.e.
current state compromise the latest output can be distinguished from

2.      Does the secret state include p and q?  If so, then the BBS suffers
from a more severe backtracking attack: recovering the current state allows
recovery of all the previous states, because p and q allows one to compute
square roots.  This would undermine forward security applications.


Best regards,


Daniel Brown

Research In Motion Limited