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

"Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com> Fri, 03 January 2014 17:01 UTC

Return-Path: <sfluhrer@cisco.com>
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 0CADC1ADFE6; Fri, 3 Jan 2014 09:01:59 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -7.54
X-Spam-Level:
X-Spam-Status: No, score=-7.54 tagged_above=-999 required=5 tests=[BAYES_20=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, J_CHICKENPOX_35=0.6, RP_MATCHES_RCVD=-0.538, SPF_PASS=-0.001, USER_IN_DEF_DKIM_WL=-7.5] 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 T-Znzat59Iaa; Fri, 3 Jan 2014 09:01:56 -0800 (PST)
Received: from alln-iport-4.cisco.com (alln-iport-4.cisco.com [173.37.142.91]) by ietfa.amsl.com (Postfix) with ESMTP id 7DDE41ADFDF; Fri, 3 Jan 2014 09:01:56 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=3943; q=dns/txt; s=iport; t=1388768509; x=1389978109; h=from:to:cc:subject:date:message-id:references: in-reply-to:content-transfer-encoding:mime-version; bh=eEv/w4PfgDwk5USLk9Pnz+CaTVZTIJjJyBYWJrv9l4c=; b=U0LcLG+PwvuyYdlmtQxjsk3h4FxS1ODG4tSHSl//6ZyQI2f5vOngmKoX e2vrISfruAgzta1dWiIyeXryYtyePFKe+gLFgAFJdR22Yqm1YkiF2X77p V3gBcHza9DFm7XkQq6XBTZbfcW1mVLCr4jvAPXo82N0pupAq3jxwd1W/o w=;
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AgMFAIHsxlKtJV2a/2dsb2JhbABYgwuBDbkKgQ0WdIIlAQEBBDo/DAQCAQgOAwQBAQsOBgkHMhQJCAIEAQ0FCId8wx4Xjl0xBwYSgwyBEwEDqiuDLYIq
X-IronPort-AV: E=Sophos;i="4.95,598,1384300800"; d="scan'208";a="10367365"
Received: from rcdn-core-3.cisco.com ([173.37.93.154]) by alln-iport-4.cisco.com with ESMTP; 03 Jan 2014 17:01:48 +0000
Received: from xhc-aln-x15.cisco.com (xhc-aln-x15.cisco.com [173.36.12.89]) by rcdn-core-3.cisco.com (8.14.5/8.14.5) with ESMTP id s03H1mB0029817 (version=TLSv1/SSLv3 cipher=AES128-SHA bits=128 verify=FAIL); Fri, 3 Jan 2014 17:01:48 GMT
Received: from xmb-rcd-x04.cisco.com ([169.254.8.230]) by xhc-aln-x15.cisco.com ([173.36.12.89]) with mapi id 14.03.0123.003; Fri, 3 Jan 2014 11:01:47 -0600
From: "Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com>
To: Trevor Perrin <trevp@trevp.net>, "David McGrew (mcgrew)" <mcgrew@cisco.com>
Thread-Topic: [Cfrg] Requesting removal of CFRG co-chair
Thread-Index: AQHO/ZzptS1O68R/sUixHXXzj4UYk5pjN00AgAByKICAAGMrgIAElTSAgAqnRoA=
Date: Fri, 3 Jan 2014 17:01:46 +0000
Message-ID: <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>
In-Reply-To: <CAGZ8ZG07QGL4mD1+XpDgm-5GHuhZEg2WRUvF20zRM_ZPNFLOUQ@mail.gmail.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-originating-ip: [10.86.245.240]
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
Cc: "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: Fri, 03 Jan 2014 17:01:59 -0000

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