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

Annie Yousar <> Mon, 19 October 2020 10:20 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 044473A0A5E for <>; Mon, 19 Oct 2020 03:20:26 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -0.346
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: (amavisd-new); dkim=pass (1024-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id WsYegsSNMLXJ for <>; Mon, 19 Oct 2020 03:20:24 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 1F9453A0A49 for <>; Mon, 19 Oct 2020 03:20:22 -0700 (PDT)
Received: from (mailbox []) by (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 <>; Mon, 19 Oct 2020 12:20:19 +0200 (MEST)
Received: from [] ( []) (authenticated bits=0) by (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 <>; Mon, 19 Oct 2020 12:20:19 +0200 (MEST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple;; s=mailbox; t=1603102819; bh=Ldy6A2J2YhfizckJdR8CocD3Ppxghy75aCYKavJhShs=; h=To:References:From:Subject:Date:In-Reply-To; b=cZK+EkuRsC53UPkMXboXfNyeBmsCsBB2MrwbihZr22fZ8BEjCdA8O6ylXRlS6whYH nJU/DXxh3MdFWOUkvG6nks7+tu9xdic2RXB6pFnvpYMCWBeGWh3kcxZDgrpzv2xcY6 qoyToVRozmVBdd2Dwx/FdOImwFStJcc8Ab1AZh2g=
References: <> <> <> <>
From: Annie Yousar <>
Autocrypt:; 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: <>
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: <>
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 ( []); Mon, 19 Oct 2020 12:20:19 +0200 (MEST)
Archived-At: <>
Subject: Re: [Cfrg] RGLC on draft-irtf-cfrg-spake2-13 (rejection sampling vs. modulo reduction)
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-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

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.


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