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

"Dan Harkins" <dharkins@lounge.org> Sat, 04 January 2014 08:24 UTC

Return-Path: <dharkins@lounge.org>
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 55A8F1AD8ED for <cfrg@ietfa.amsl.com>; Sat, 4 Jan 2014 00:24:24 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -3.867
X-Spam-Level:
X-Spam-Status: No, score=-3.867 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, IP_NOT_FRIENDLY=0.334, RCVD_IN_DNSWL_MED=-2.3, SPF_HELO_PASS=-0.001] 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 0mWDKks-jj90 for <cfrg@ietfa.amsl.com>; Sat, 4 Jan 2014 00:24:22 -0800 (PST)
Received: from colo.trepanning.net (colo.trepanning.net [69.55.226.174]) by ietfa.amsl.com (Postfix) with ESMTP id A43CF1AD7C5 for <cfrg@irtf.org>; Sat, 4 Jan 2014 00:24:22 -0800 (PST)
Received: from www.trepanning.net (localhost [127.0.0.1]) by colo.trepanning.net (Postfix) with ESMTP id C74F610224008; Sat, 4 Jan 2014 00:24:14 -0800 (PST)
Received: from 69.12.173.8 (SquirrelMail authenticated user dharkins@lounge.org) by www.trepanning.net with HTTP; Sat, 4 Jan 2014 00:24:15 -0800 (PST)
Message-ID: <d6f0d93f0e63bb4732b1592edfce997a.squirrel@www.trepanning.net>
In-Reply-To: <CAGZ8ZG07QGL4mD1+XpDgm-5GHuhZEg2WRUvF20zRM_ZPNFLOUQ@mail.gmail.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>
Date: Sat, 4 Jan 2014 00:24:15 -0800 (PST)
From: "Dan Harkins" <dharkins@lounge.org>
To: "Trevor Perrin" <trevp@trevp.net>
User-Agent: SquirrelMail/1.4.14 [SVN]
MIME-Version: 1.0
Content-Type: text/plain;charset=iso-8859-1
Content-Transfer-Encoding: 8bit
X-Priority: 3 (Normal)
Importance: Normal
Cc: David McGrew <mcgrew@cisco.com>, "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 08:24:24 -0000

  Trevor,

On Fri, December 27, 2013 7:56 am, Trevor Perrin wrote:
> 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?

  That is a good description of a problem. I now see how poor the
text is that describes the hunting-and-pecking loop. I wish you
would have put it in the form of a constructive comment, or at least
separated this signal from the general noise of your posts. But
nevertheless, I see that that section is poorly worded, I understand
your comment, and will address it in a subsequent version of the
draft.

  A sincere thank you for this comment!

  Dan.