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

"Dan Harkins" <dharkins@lounge.org> Sat, 04 January 2014 08:27 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 BFBB41AD7C5; Sat, 4 Jan 2014 00:27:13 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -3.267
X-Spam-Level:
X-Spam-Status: No, score=-3.267 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, IP_NOT_FRIENDLY=0.334, J_CHICKENPOX_35=0.6, 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 YnzIs-941tB3; Sat, 4 Jan 2014 00:27:11 -0800 (PST)
Received: from colo.trepanning.net (colo.trepanning.net [69.55.226.174]) by ietfa.amsl.com (Postfix) with ESMTP id 0B0881AD939; Sat, 4 Jan 2014 00:27:11 -0800 (PST)
Received: from www.trepanning.net (localhost [127.0.0.1]) by colo.trepanning.net (Postfix) with ESMTP id 6AEE710224008; Sat, 4 Jan 2014 00:26:58 -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:26:58 -0800 (PST)
Message-ID: <c0c5b263d1b77bdda9f0382c502355c8.squirrel@www.trepanning.net>
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: Sat, 4 Jan 2014 00:26:58 -0800 (PST)
From: "Dan Harkins" <dharkins@lounge.org>
To: "Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com>
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: Trevor Perrin <trevp@trevp.net>, David McGrew <mcgrew@cisco.com>, "cfrg@irtf.org" <cfrg@irtf.org>, "irtf-chair@irtf.org" <irtf-chair@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:27:14 -0000

  Scott,

  Thank you for this very constructive comment. I appreciate the
suggestion on improving the draft. I will look at it closely. Your
help is most appreciated.

  regards,

  Dan.

On Fri, January 3, 2014 9:01 am, Scott Fluhrer (sfluhrer) 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).
>
> 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?'
>
>
>
> For the record, a better implementation of my suggestion in dragonfly
> would be:
>
>        found = 0
>        counter = 1
>        n = len(p) + 64
>        do {
>          base = H(max(Alice,Bob) | min(Alice,Bob) | password | counter)
>          temp = KDF-n(seed, "Dragonfly Hunting And Pecking")
>          seed = (temp mod (p - 1)) + 1
>          if (seed < p)
>          then
>            x = seed
>            if ( (x^3 + ax + b) is a quadratic residue mod p)
>            then
>              found_x = x
>              found = 1
>            fi
>        } while((found == 0) || (counter < k))
>
>        x = found_x
>        y = sqrt(x^3 + ax + b)
>        if (lsb(y) == lsb(base))
>        then
>          PE = (x,y)
>        else
>          PE = (x,p-y)
>        fi
>
> (this stops on the last acceptable 'x' value found; you could try to
> select the 'middle-value'; I picked the last because it was the easiest to
> specify).
>
> As for determining if a value is a QR, the easiest way to do it without
> leaking any information in the time taken would be to blind the value
> randomly, as in:
>
>     temp = (x^3 + ax + b mod p)
>     r = 1 + random(p-2)      /* Random value between 1 and p-1) */
>     temp = (temp * r * r) mod p
>     if random(2)                   /* 0.5 chance */
>         temp =  (temp * qr) mod p
>         bit = 0
>     else
>         temp =  (temp *qnr) mod p
>         bit = 1
>     fi
>     /* At this point, temp takes on all values between 1 and p-1 with
> equal probability */
>     output = bit ^ legendre_symbol(temp, p)
>
> where qr, qnr are fixed values which are respectively a quadric residue,
> and quadratic nonresidue mod p, and are the same size (and so the
> multiplications take the same amount of time).
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg
>