IETF Logo Mail Archive

Re: [Cfrg] Exposing the private key by signing "too many times"

Thomas Pornin <pornin@bolet.org> Thu, 14 April 2016 17:05 UTC

Return-Path: <pornin@bolet.org>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 538E712E33C for <cfrg@ietfa.amsl.com>; Thu, 14 Apr 2016 10:05:31 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.898
X-Spam-Level:
X-Spam-Status: No, score=-2.898 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RP_MATCHES_RCVD=-0.996, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
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 iHdsnC9AD_h4 for <cfrg@ietfa.amsl.com>; Thu, 14 Apr 2016 10:05:29 -0700 (PDT)
Received: from brontes.bolet.org (brontes.bolet.org [62.210.214.227]) by ietfa.amsl.com (Postfix) with ESMTP id 5CF2A12E06B for <cfrg@irtf.org>; Thu, 14 Apr 2016 10:05:29 -0700 (PDT)
Received: by brontes.bolet.org (Postfix, from userid 1000) id 2D04A20261; Thu, 14 Apr 2016 19:05:27 +0200 (CEST)
Date: Thu, 14 Apr 2016 19:05:27 +0200
From: Thomas Pornin <pornin@bolet.org>
To: Dan Brown <dbrown@certicom.com>
Message-ID: <20160414170527.GA22878@bolet.org>
References: <C33F3EC3-AF92-4BC0-8191-32839135BBBB@vpnc.org> <20160414144442.5709908.79799.15426@certicom.com>
MIME-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Disposition: inline
In-Reply-To: <20160414144442.5709908.79799.15426@certicom.com>
User-Agent: Mutt/1.5.21 (2010-09-15)
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/3lK3zjoWp2eMCnY4KuJvFeGJJ0I>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Exposing the private key by signing "too many times"
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.17
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Thu, 14 Apr 2016 17:05:31 -0000

On Thu, Apr 14, 2016 at 02:44:43PM +0000, Dan Brown wrote:
> Long ago DSA allowed biased ephemeral secrets, which Bleichenbacher
> exploited to extract the private key.
> 
> Not aware of history or survey papers on topic, sorry.

The attack is described in this report from Serge Vaudenay (section 5):

   http://www.ipa.go.jp/security/enc/CRYPTREC/fy15/doc/1002_reportDSA.pdf

Serge says that the attack was announced in February 2001; apparently,
according to that CHES 2013 article:

   http://www.iacr.org/archive/ches2013/80860105/80860105.pdf

the attack was also presented and discussed at an IEEE P1363 WG meeting
on November 15th, 2000.

To my knowledge it was never formally published.


Conceptually, this is a generalization of the dreaded "secret value
reuse". If you reuse the same k value in two distinct signatures (with
the same private key) then the private key is revealed. Bleichenbacher's
attack generalizes that result into leveraging a selection bias; plain
reuse just being an awfully large selection bias.


	--Thomas Pornin

v2.23.0 | Report a Bug | By Email