Re: [Cfrg] 40 bit loop and DragonFly

David Jacobson <dmjacobson@sbcglobal.net> Tue, 07 January 2014 03:00 UTC

Return-Path: <dmjacobson@sbcglobal.net>
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 F0EA41ADF5A for <cfrg@ietfa.amsl.com>; Mon, 6 Jan 2014 19:00:03 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.101
X-Spam-Level:
X-Spam-Status: No, score=-0.101 tagged_above=-999 required=5 tests=[BAYES_40=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_NONE=-0.0001] 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 dly2PJZ2lzCd for <cfrg@ietfa.amsl.com>; Mon, 6 Jan 2014 19:00:02 -0800 (PST)
Received: from nm3-vm9.access.bullet.mail.bf1.yahoo.com (nm3-vm9.access.bullet.mail.bf1.yahoo.com [216.109.114.104]) by ietfa.amsl.com (Postfix) with ESMTP id 74E4E1ADF53 for <cfrg@irtf.org>; Mon, 6 Jan 2014 19:00:02 -0800 (PST)
Received: from [66.196.81.160] by nm3.access.bullet.mail.bf1.yahoo.com with NNFMP; 07 Jan 2014 02:59:53 -0000
Received: from [98.138.226.242] by tm6.access.bullet.mail.bf1.yahoo.com with NNFMP; 07 Jan 2014 02:59:53 -0000
Received: from [127.0.0.1] by smtp113.sbc.mail.ne1.yahoo.com with NNFMP; 07 Jan 2014 02:59:53 -0000
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sbcglobal.net; s=s1024; t=1389063593; bh=AaNJbkjIz5BtMm6kNFEvLdcEVVcQC4R2uvGLYtTjrdg=; h=X-Yahoo-Newman-Id:X-Yahoo-Newman-Property:X-YMail-OSG:X-Yahoo-SMTP:X-Rocket-Received:Message-ID:Date:From:User-Agent:MIME-Version:To:Subject:References:In-Reply-To:Content-Type:Content-Transfer-Encoding; b=cvb4LtccqyRjmTOGAu0mJWbp+Noo7cO4SPZvWd2mCaxNjVQX0EtxofWxfrwXgAlQ4Yaf9BZNRr+eAoJme7dsxYlcgYNWLQPr6HW32/aNXt4sTIq8TNuZpaBgskBdA0IbK08R0R2ZrvzOy2duYPavz5EHkCB1rg3UGekTN3m3+1I=
X-Yahoo-Newman-Id: 65491.76243.bm@smtp113.sbc.mail.ne1.yahoo.com
X-Yahoo-Newman-Property: ymail-3
X-YMail-OSG: D5_OuUIVM1lz7q9MNcPpNQDOsePbMPv0533yeOs83pM8s4V Nd.pue1oGwxTULXkMvdcqTZFXxA6q6lg0CSjIfyCwVbAV8ZX_3ezPiUb1i1X TaGiVVWmSZrCKIHdbq5P9HpAkbxctEzTM8V7tJRzbly9n04nL84Gd_v5UHBl 9jXT1kSPRuXYjcTHaQo1TWWhhZMke4idf7MbxQZCUimAUpM_ipr4_nAX0Kvn xvujvCI1Jtbpa3lvbUvLvhUZrOULgV89v5x2STk0HeovuzQyTgYfUbF1FrHC 160PdTtakq9lbgp3QjoUONgY_UNCaGstc9U9C3vwm9dcw4Maq2XkdKXaTkWJ hjrC6JT84oLuX8utC.h4yJUSbEA8aFql3GC6mXuZEuSOd6FvzU6AXfyiMY2n vKfPsLA8RYr2RzX0BCaLp6RY0l2jiBWKQPY3Iv03uz4.5YcpifG4CZseXyid zq5GpV6kiOd0EyH5Z2iGIiLJFSQhYd8dPSR3AZC1DLwK6O9X4A1iOQHw51l7 mIVEDpTeIhLy78tIaAdnWMIHv4_WTd4g4byiU0UB7KXxgFZlHj4vswwcVDWO ZI2wwLwKEhW_wjXUpIRVMwQ--
X-Yahoo-SMTP: nOrmCa6swBAE50FabWnlVFUpgFVJ9Gbi__8U5mpvhtQq7tTV1g--
X-Rocket-Received: from [192.168.1.64] (dmjacobson@99.120.97.155 with plain [98.138.84.52]) by smtp113.sbc.mail.ne1.yahoo.com with SMTP; 07 Jan 2014 02:59:53 +0000 UTC
Message-ID: <52CB6DA7.1020000@sbcglobal.net>
Date: Mon, 06 Jan 2014 18:59:51 -0800
From: David Jacobson <dmjacobson@sbcglobal.net>
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:24.0) Gecko/20100101 Thunderbird/24.2.0
MIME-Version: 1.0
To: "Igoe, Kevin M." <kmigoe@nsa.gov>, "'Scott Fluhrer (sfluhrer)'" <sfluhrer@cisco.com>, "'cfrg@irtf.org'" <cfrg@irtf.org>
References: <3C4AAD4B5304AB44A6BA85173B4675CABA99F80C@MSMR-GH1-UEA03.corp.nsa.gov> <A113ACFD9DF8B04F96395BDEACB340420B77D4CC@xmb-rcd-x04.cisco.com> <3C4AAD4B5304AB44A6BA85173B4675CABA9A0B90@MSMR-GH1-UEA03.corp.nsa.gov>
In-Reply-To: <3C4AAD4B5304AB44A6BA85173B4675CABA9A0B90@MSMR-GH1-UEA03.corp.nsa.gov>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Subject: Re: [Cfrg] 40 bit loop and DragonFly
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: Tue, 07 Jan 2014 03:00:04 -0000

On 1/6/14 8:46 AM, Igoe, Kevin M. wrote:
> [snip]
> 4) That just leaves multiplying sqrt((r**2)*f ) = r*sqrt(f)
> by (1/r) => need to calculate 1/r, which can be done either
> by an exponentiation or by the extended Euclidean algorithm.
> Since the extended Euclidean algorithm is variable time, it
> might leak information about r, so exponentiating by p-2 is
> the safer alternative.  Fortunately, this only has to be done
> once, not "40" times.
>
>

Isn't this easy?  Choose a random non-zero b from the same field as r.  
Compute b*(r*sqrt(f)) and b*r.  Compute 1/(b*r).  Since all values of b 
are equally likely and the attacker does not know b, any leakage from 
the inverse that makes some values of b*r more likely gives no 
information at all about r.  Now compute (b*(r*sqrt(f)) * (1/(b*r))  = 
sqrt(f).

      --David