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

Trevor Perrin <> Sat, 04 January 2014 02:50 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 5ED231AE03A for <>; Fri, 3 Jan 2014 18:50:23 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.978
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 ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id V4nfd0pqBAnh for <>; Fri, 3 Jan 2014 18:50:21 -0800 (PST)
Received: from ( []) by (Postfix) with ESMTP id E61291ADFE0 for <>; Fri, 3 Jan 2014 18:50:20 -0800 (PST)
Received: by with SMTP id n12so13864320wgh.33 for <>; Fri, 03 Jan 2014 18:50:13 -0800 (PST)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; 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 with SMTP id hl2mr4137165wib.56.1388803812988; Fri, 03 Jan 2014 18:50:12 -0800 (PST)
Received: by with HTTP; Fri, 3 Jan 2014 18:50:12 -0800 (PST)
X-Originating-IP: []
In-Reply-To: <>
References: <> <> <> <> <> <>
Date: Fri, 03 Jan 2014 18:50:12 -0800
Message-ID: <>
From: Trevor Perrin <>
To: "Scott Fluhrer (sfluhrer)" <>
Content-Type: text/plain; charset="ISO-8859-1"
Cc: "" <>
Subject: Re: [Cfrg] Requesting removal of CFRG co-chair
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-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)
<> wrote:
>> -----Original Message-----
>> From: Cfrg [] On Behalf Of Trevor Perrin
>> Sent: Friday, December 27, 2013 10:57 AM
>> To: David McGrew (mcgrew)
>> Cc:;
>> 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:

Dan and Kevin's reception:

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."

"Kevin reports to TLS WG chairs that CFRG did not find any problems
with Dragonfly."