Re: [Cfrg] RGLC on draft-irtf-cfrg-spake2-13 (rejection sampling vs. modulo reduction)

Annie Yousar <a.yousar@informatik.hu-berlin.de> Mon, 19 October 2020 10:20 UTC

Return-Path: <a.yousar@informatik.hu-berlin.de>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 044473A0A5E for <cfrg@ietfa.amsl.com>; Mon, 19 Oct 2020 03:20:26 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.346
X-Spam-Level:
X-Spam-Status: No, score=-0.346 tagged_above=-999 required=5 tests=[DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, NICE_REPLY_A=-0.247, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=informatik.hu-berlin.de
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 WsYegsSNMLXJ for <cfrg@ietfa.amsl.com>; Mon, 19 Oct 2020 03:20:24 -0700 (PDT)
Received: from mailout1.informatik.hu-berlin.de (mailout1.informatik.hu-berlin.de [141.20.20.101]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 1F9453A0A49 for <cfrg@irtf.org>; Mon, 19 Oct 2020 03:20:22 -0700 (PDT)
Received: from mailbox.informatik.hu-berlin.de (mailbox [141.20.20.63]) by mail.informatik.hu-berlin.de (8.15.1/8.15.1/INF-2.0-MA-SOLARIS-2.10-25) with ESMTPS id 09JAKJBi029913 (version=TLSv1.2 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK) for <cfrg@irtf.org>; Mon, 19 Oct 2020 12:20:19 +0200 (MEST)
Received: from [192.168.2.107] (p2e57c021.dip0.t-ipconnect.de [46.87.192.33]) (authenticated bits=0) by mailbox.informatik.hu-berlin.de (8.15.1/8.15.1/INF-2.0-MA-SOLARIS-2.10-AUTH-26-465-587) with ESMTPSA id 09JAKJTK029883 (version=TLSv1.2 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK) for <cfrg@irtf.org>; Mon, 19 Oct 2020 12:20:19 +0200 (MEST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=informatik.hu-berlin.de; s=mailbox; t=1603102819; bh=Ldy6A2J2YhfizckJdR8CocD3Ppxghy75aCYKavJhShs=; h=To:References:From:Subject:Date:In-Reply-To; b=cZK+EkuRsC53UPkMXboXfNyeBmsCsBB2MrwbihZr22fZ8BEjCdA8O6ylXRlS6whYH nJU/DXxh3MdFWOUkvG6nks7+tu9xdic2RXB6pFnvpYMCWBeGWh3kcxZDgrpzv2xcY6 qoyToVRozmVBdd2Dwx/FdOImwFStJcc8Ab1AZh2g=
To: cfrg@irtf.org
References: <CAMr0u6n0SVGpWkBc=ZLMoS-SQZta=TxbUZP13Pq=3QBxdMpUdg@mail.gmail.com> <46021e35-cb24-d372-13a9-9fb8e70c6a74@web.de> <CACsn0ckRcT1EHMQg2uS-aHuR0Ru8otWWQLmmL7q5VengHB8v4g@mail.gmail.com> <633ecac9-a4dc-cf9c-0d6f-b3ead71994f5@web.de>
From: Annie Yousar <a.yousar@informatik.hu-berlin.de>
Autocrypt: addr=giessmann@informatik.hu-berlin.de; prefer-encrypt=mutual; keydata= xlIEXgvhABMIKoZIzj0DAQcCAwTQ8aTR8t1myluI1AP2rsxyOkCJHgXi+R/EG+G/mCOpbUT5 Z3ohns8ki38HQoLrioDb+IK5uZenyCJu5KavT6MLzTVFcm5zdCBHIEdpZXNzbWFubiA8Z2ll c3NtYW5uQGluZm9ybWF0aWsuaHUtYmVybGluLmRlPsLAJQQTEwgAdhYhBCIuZ+oqolOpZ0CK vp96MRnfkRDrBQJeC+EBAhsDBQkUt8J/BQsJCAcCBRUKCQgLBBYCAwE4Gmh0dHA6Ly93d3cu aW5mb3JtYXRpay5odS1iZXJsaW4uZGUvfmdpZXNzbWFuL2dwZy1jcC50eHQCHgECF4AAIQkQ n3oxGd+REOsWIQQiLmfqKqJTqWdAir6fejEZ35EQ670QAQDwC3crlc+od6dvJTmMNeuOz7ov 38yB3pvCMMLLILicGgEA9zqmCjmaHal0gy/xGFStt8DDO05rEEEUIRDNKC6B3jfOwMUEXhNL cAELwMYaTIWytvv/gOy8YNYFirNdGeXAbqQe5fz/8Suey0b4aJ6yyZqef/91vlbWKcvzt3Ij hAy06LHvLSkGZwfH4rK3FAUvs5qzvP0xGGlkpNmcO3SMe2/1rYa/9n63NPT9pjimhO6jZUdC qNct3yj4TEOBLehGQCc5WnB8fisjEYaWSk2Z8/Q7dIx7b/Wthr/2frc09P2mOKaE7qNlR0Ko 1y3fKPhMQ4Et6EZAJzlaQ3Ikztd3Slpwj2NSBN7KP3ElpGMzv/bcYpa9g8PqykGbTm+gHEcY hAluv/tAzEhahCR9PqBGkQUjog4y3n0weSxsD5kNUkbzFG0BP/+h5n0aQmT7CXZd/7m+ud7t J7j5Io0S39qtc0dmUPkvwzjMzt342KF3kc5QSGq6qxQprY7S49Ym9pEut+57ix9LzDFmEXbZ DRI6984SeyGfgfYjmqHWlXnuG2Tamg8G++y4GYgx19kVnd1atMTxOYsFQHaFyL4ILM7wUZtX O7kAF0AAAcKPBBgTCAAgFiEEIi5n6iqiU6lnQIq+n3oxGd+REOsFAl4TS3ECGwwAIQkQn3ox Gd+REOsWIQQiLmfqKqJTqWdAir6fejEZ35EQ61yjAQC3kpin6MO1WztmHw7/YzlXia0bIkCf 5+nTZnAPL6IrygD9HaND5f4vU5axUmWLaplhQ878M3yXGTagcDpU+ZVch+g=
Message-ID: <a2f26442-ac2e-896d-3f35-dcc9a8c0ffcb@informatik.hu-berlin.de>
Date: Mon, 19 Oct 2020 12:20:18 +0200
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101 Thunderbird/68.12.1
MIME-Version: 1.0
In-Reply-To: <633ecac9-a4dc-cf9c-0d6f-b3ead71994f5@web.de>
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
X-Virus-Scanned: clamav-milter 0.102.3 at mailbox
X-Virus-Status: Clean
X-Greylist: Sender succeeded STARTTLS authentication, not delayed by milter-greylist-4.6.1 (mail.informatik.hu-berlin.de [141.20.20.50]); Mon, 19 Oct 2020 12:20:19 +0200 (MEST)
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/OvMaDOT-2OGrsBEqAIutj-_YD2U>
Subject: Re: [Cfrg] RGLC on draft-irtf-cfrg-spake2-13 (rejection sampling vs. modulo reduction)
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Mon, 19 Oct 2020 10:20:26 -0000

Hi Björn, Watson,
there are *two* common solutions for "re-uniforming" from [0,2^N-1] to
[0,q-1], where the bitlength of q is n, and N>n (usually N=n+64 or
greater).

Pick r randomly and uniformly from [0,2^N-1] and
1. compute r mod q, or
2. compute r*q div 2^N

If you put all the 2^N values in to q boxes with one of these methods
you get all boxes filled with 2^64 or 2^64+1 values. Hardly you will see
here the differences.
The second method uses one multiplication (shift is not counted) instead
of modulo operation and may be a bit faster and easier to implement than
rejection sampling.

/Ann.




Am 2020-10-19 um 11:26 schrieb Björn Haase:
> Hi Watson,
> 
>> On 19.10. 2020 Watson Ladd wrote:
> 
>> Thank you! I will add such a warning to the security section and
>> advise the use of either reduction of a double length string or
>> rejection sampling.
> 
> Indeed you are right. With my mind focused on "constant time"
> implementation all the time, I
> did discard the cheap option of the rejection sampling too early. In
> fact, we won't
> leak any useful information with rejection sampling even if it's not
> constant time.
> 
> On the other hand there is a non-negligible risk of leakage when
> reducing a double-length string (in addition to the code bloat).
> 
> Therefore I'd advocate to recommend rejection sampling only and not
> double-length-string reduction
> (and this should also be the way to do for CPace on the
> short-Weierstrass curves).
> 
> Still there might worth pointing to the risk of a possible variable-time
> issue when re-using code from libraries that were written for
> conventional DH key exchange. I have seen implementations that just set
> the top-most bit of the secret scalar (loosing half a bit of security)
> during the sampling process in order to make sure that the windowed
> scalar multiplication algorithm runs in constant time.
> 
> If we have such a scalar multiplication algorithm with a uniformly
> sampled scalar, there is some risk
> of getting a variable execution time behaviour...
> 
> Maybe some note in the security section in the form:
> 
> "Some scalar multiplication algorithms designed for conventional ECDH
> key exchange might not run in constant time when using uniformly sampled
> secret scalars. Implementations should verify this aspect."
> 
> could be worthwile.
> 
> Yours,
> 
> Björn
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>