Re: [Cfrg] Requesting removal of CFRG co-chair

Trevor Perrin <trevp@trevp.net> Sat, 04 January 2014 02:50 UTC

Return-Path: <trevp@trevp.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 5ED231AE03A for <cfrg@ietfa.amsl.com>; Fri, 3 Jan 2014 18:50:23 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.978
X-Spam-Level:
X-Spam-Status: No, score=-1.978 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FM_FORGED_GMAIL=0.622, RCVD_IN_DNSWL_LOW=-0.7] 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 V4nfd0pqBAnh for <cfrg@ietfa.amsl.com>; Fri, 3 Jan 2014 18:50:21 -0800 (PST)
Received: from mail-wg0-f54.google.com (mail-wg0-f54.google.com [74.125.82.54]) by ietfa.amsl.com (Postfix) with ESMTP id E61291ADFE0 for <cfrg@irtf.org>; Fri, 3 Jan 2014 18:50:20 -0800 (PST)
Received: by mail-wg0-f54.google.com with SMTP id n12so13864320wgh.33 for <cfrg@irtf.org>; Fri, 03 Jan 2014 18:50:13 -0800 (PST)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc:content-type; bh=YXn/ZfCFLHyNLwWrXZMRpnn1ShnTeu6sDVMK06A1oyw=; b=U1TYX4iBNqIWYmB0u3KMoKb21lOVX3PfUlTfx4+Jb41ds3SLaK7dctjKJSR3kyydha NkWw2pD1OS92fjKajY52n81nukMsc44dUiSvR/lYTYr3wIwy83N8l1E96I9VwxKCIy7W tBKCFfGAxd347eIxfiFLQps5mBvYRP9MSyN3AML6uI7gMpclTGCs8JHB36a4eH/ccHm5 vktlgVAptA97GLDV1h3Wb/lKTbfD8Ra243ZNKjfU01Q1nPCpzPhUdnkwAbAqI7MkUxPn y7LGmOKHMy4oB//vx9ygJYvsV9e20MZUGBNN/i99VfUAQBnC+2cPe6N7eROAbuCibffR uTFQ==
X-Gm-Message-State: ALoCoQlS8a+jU95ezGef1PzDoaot+t7mH9hUFeFwPD8zlgj555v+mN69C/L7CMEtK2fAXbRZSxHt
MIME-Version: 1.0
X-Received: by 10.180.108.162 with SMTP id hl2mr4137165wib.56.1388803812988; Fri, 03 Jan 2014 18:50:12 -0800 (PST)
Received: by 10.216.214.134 with HTTP; Fri, 3 Jan 2014 18:50:12 -0800 (PST)
X-Originating-IP: [166.137.186.235]
In-Reply-To: <A113ACFD9DF8B04F96395BDEACB340420B77CACE@xmb-rcd-x04.cisco.com>
References: <CAGZ8ZG2f9QHX40RcB8aajWvEfG0Gh_uewu2Rq7bQGHYNx6cOmw@mail.gmail.com> <52B91820.9090706@cisco.com> <CAGZ8ZG02+o=Qm0gUQiVF9H_=wfn+wQt8ahY1ntLHNsELXbvtVg@mail.gmail.com> <52B9CB13.9020500@cisco.com> <CAGZ8ZG07QGL4mD1+XpDgm-5GHuhZEg2WRUvF20zRM_ZPNFLOUQ@mail.gmail.com> <A113ACFD9DF8B04F96395BDEACB340420B77CACE@xmb-rcd-x04.cisco.com>
Date: Fri, 3 Jan 2014 18:50:12 -0800
Message-ID: <CAGZ8ZG2adT1e8ctUUCwpPRNMrgguhAEd=z-ENJNP-E4SbFOOYg@mail.gmail.com>
From: Trevor Perrin <trevp@trevp.net>
To: "Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com>
Content-Type: text/plain; charset=ISO-8859-1
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Requesting removal of CFRG co-chair
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: Sat, 04 Jan 2014 02:50:23 -0000

On Fri, Jan 3, 2014 at 9:01 AM, Scott Fluhrer (sfluhrer)
<sfluhrer@cisco.com>; wrote:
>
>
>> -----Original Message-----
>> From: Cfrg [mailto:cfrg-bounces@irtf.org] On Behalf Of Trevor Perrin
>> Sent: Friday, December 27, 2013 10:57 AM
>> To: David McGrew (mcgrew)
>> Cc: cfrg@irtf.org; irtf-chair@irtf.org
>> Subject: Re: [Cfrg] Requesting removal of CFRG co-chair
>>
>>
>> I'm still not sure what you're asking.  Let's just look at a crude
>> analysis of the "40-loops" countermeasure Kevin endorsed, comparing
>> CFRG draft-00 vs draft-01/draft-02.
>>
>> Let's assume that modular square roots are calculated via modular
>> exponentiation, and that Legendre symbol calculations take less time.
>> Let's also ignore the variable time taken by a Legendre symbol
>> calculation and other conditional logic, and just count the number of
>> ops.
>>
>> In draft-00, the hunt-and-peck loop in 3.2.1 performs Legendre symbol
>> calculations until it finds a square (probability ~1/2), at which
>> point a square root is performed.  So:
>>  - 1 modular exponentiation
>>  - Variable number of Legendre symbol calculations
>>    - geometric distribution with mean ~2, variance ~2
>>
>> In draft-01 and draft-02, the hunt-and-peck loop continues until it
>> completes 40 loops, with a probability ~1/2 of performing a modular
>> exponentiation on each iteration.  So:
>>  - Variable number of modular exponentiations
>>    - binomial distribution with mean ~20, variance ~10
>>  - 40 Legendre symbol calculations
>>
>> The 40-loops algorithm was intended to reduce timing variance but
>> instead increases it, and increases computation cost as well.  So I
>> think "ineffective" is a fair description.  Do you agree?
>
> I think we agree that what Dan specified in the draft is broken.  However, I believe that's because Dan got it wrong (and I was busy elsewhere, and did not review the draft).

Hi Scott,

In 2012 I can imagine you were thinking of something like your below
pseudocode.  However, Dan seems to have understood your 2012 messages
as saying that simply performing 40 loops of the draft-00 algorithm
was a sufficient timing-attack countermeasure.  I don't think we can
blame Dan entirely for that - your messages weren't as clear and
detailed as your current pseudocode.

In any case, I think everyone now agrees Dan's understanding, embodied
in CFRG drafts 01 and 02, is incorrect.  Work still needs to be done
to ensure individual loop iterations don't leak secret info.


> I believe my suggestion is an improvement (but still needs caution; the checking if x^3+ax+b is a QR must be done in constant time, or in random time via blinding; I believe that in this case blinding is easier).
>
> Now, I believe the issue is 'did Kevin endorse my suggestion, or did he endorse Dan's implementation?'

Kevin seems to have shared Dan's understanding.  Or at least: he
considered the issue resolved in drafts 01 and 02, and made no effort
to look more deeply into the timing question.


Scott's proposals:
http://www.ietf.org/mail-archive/web/cfrg/current/msg03260.html
http://www.ietf.org/mail-archive/web/cfrg/current/msg03265.html

Dan and Kevin's reception:
http://www.ietf.org/mail-archive/web/cfrg/current/msg03262.html
http://www.ietf.org/mail-archive/web/cfrg/current/msg03263.html
http://www.ietf.org/mail-archive/web/cfrg/current/msg03264.html


Kevin's endorsement of draft-01 and draft-02:

"The design looks mature, it addresses a real need, and no one has
raised any issues."
http://www.ietf.org/mail-archive/web/cfrg/current/msg03383.html

"Kevin reports to TLS WG chairs that CFRG did not find any problems
with Dragonfly."
http://www.ietf.org/mail-archive/web/cfrg/current/msg03707.html


Trevor