Re: [Cfrg] RGLC on draft-irtf-cfrg-spake2-13

Björn Haase <bjoern.m.haase@web.de> Sun, 18 October 2020 20:54 UTC

Return-Path: <bjoern.m.haase@web.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 C55D23A0C4C for <cfrg@ietfa.amsl.com>; Sun, 18 Oct 2020 13:54:19 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.442
X-Spam-Level:
X-Spam-Status: No, score=-0.442 tagged_above=-999 required=5 tests=[DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, NICE_REPLY_A=-0.247, RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=0.001, 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=web.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 kDz8EOwiF9Th for <cfrg@ietfa.amsl.com>; Sun, 18 Oct 2020 13:54:17 -0700 (PDT)
Received: from mout.web.de (mout.web.de [212.227.15.3]) (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 272F13A0C44 for <cfrg@irtf.org>; Sun, 18 Oct 2020 13:54:16 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=web.de; s=dbaedf251592; t=1603054452; bh=LxbgKoGGaJyOzOXGWOJiYyOyJb919e12KREAOyAgSto=; h=X-UI-Sender-Class:Subject:To:References:From:Date:In-Reply-To; b=Fp8E5Cn9AzVBTadl12eUWcc9NSGvU1NSWY+exw6Q1X7rx1hmqy2bU1wbUOoCR0/Kh 1QKIGhKCYhG+d2hFj+B2F7snIj3j2cZPWc5xG0nNS1AdgI12zrzjdtrrUW9xaqRT3P qN+Go/OZGTHplsgj6CApuifWdiDV4cGv847IXdfo=
X-UI-Sender-Class: c548c8c5-30a9-4db5-a2e7-cb6cb037b8f9
Received: from [192.168.178.21] ([109.90.104.251]) by smtp.web.de (mrweb002 [213.165.67.108]) with ESMTPSA (Nemesis) id 0Lw189-1kMjiT25vh-017kOK for <cfrg@irtf.org>; Sun, 18 Oct 2020 22:54:12 +0200
To: cfrg@irtf.org
References: <CAMr0u6n0SVGpWkBc=ZLMoS-SQZta=TxbUZP13Pq=3QBxdMpUdg@mail.gmail.com>
From: =?UTF-8?Q?Bj=c3=b6rn_Haase?= <bjoern.m.haase@web.de>
Message-ID: <46021e35-cb24-d372-13a9-9fb8e70c6a74@web.de>
Date: Sun, 18 Oct 2020 22:54:05 +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: <CAMr0u6n0SVGpWkBc=ZLMoS-SQZta=TxbUZP13Pq=3QBxdMpUdg@mail.gmail.com>
Content-Type: multipart/alternative; boundary="------------C1EC9CDC951F543224DF477A"
X-Provags-ID: V03:K1:aI3o1EpznXpgoOjP0KQwIcuSCMwj3ccKtSYUrEs0N6+AsHRl6Xn Crw6UvYdawHifQHPaKg8cHi8TJ30gnLiDNJGCfnwqtOZHUYCXqrfAtcr3+I5tszghkBe/z4 2YLJPU/pnS3r7BqvRsiavnmLlu8auOrvXVD0EwdFohrKvg+aYuBW1bRN5uu5nGt0qIT6HW2 hSWlc5oHPgStUiuWKT+YQ==
X-UI-Out-Filterresults: notjunk:1;V03:K0:M7GtehEIlSI=:u9dvnGlIQEwtIELhsn8WdZ 99xk0AARp3nsmWRFWaEyI7VG6gEVRyHEMcQw/flrF1RUmEPRZyNaPonqOJZ8svcd0hGWzE5V/ FVw5ctSe8Jf0BefyzDT0C8BZN+xbRbsQMXXI3qQnFahh8o4juUusQkiUvtxWkvE/KM9zAVlZv 2m2+qHNDJQJLxx2rjmaFl8DApHIZHc8j+GbIUgOBOF2uelckYdg55QxgkqCz7AFyoHxsedSUi bezHncnd4Y9dl3p5QTmJnMz0QxneJ1ACgSW0P1oEYl+4I8vMY5LwOQkDU4aEszmgdmkC+6Bzd Q/H6kSJlk5vMn0R2J7m+uBIarpEJmW6G7hfqZiU1wcHJUQp+U5THyeTwTUDoVsn+2K9+ja8uZ BmbuoobJr9Pkz2LjiXZNw1mfOwqgVBSkqLO44KazzicXvzXo/9r7t2ut23NQS98PWdyDW3CsV owl4UmPAnHKRNRY/01PigaqV227RNMq+L/crrksEiQ3cvusShIYi/6F3dvwONXhrUpc87i9e5 AMhMtMwAAWirrMNGZVE42KASIrU/6ixS3pgBspc+hcnNdqbOS8B8KaYnZuXPDtH+zCkjRA7uy fQo6D+zxpVuI20N2maCo4C2BhZVfQuBkJ+WLlwFViCrepw1m5Vcci8qj2as5So9JzplGfYfnu gTvp5FU3sitZ2VqXcL48V1Llc+tRhZ6FHtAPjnd/H4UE6Ql5IalaqJyG2cgYtWVUsdnz+uaKT UI0+YsN+pmWHXmGv0UWS4KEn5ujOpt2Z3t7J/5Li1+u1I7d9G6Qaf7Bo/ILZf4hGwnTnzTiKJ sVKFDgm8y/Zk2PKLt3ZpbXvLsPYwgKOgKrIGeGcdhbuBLuE3ZR/+2Qme8ecXPHpa62I4UzKE8 Av7QPoCsu7cgTxws1Vgg==
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/mtfNMJUgLoN4-0TS7wlCsJFTTUg>
Subject: Re: [Cfrg] RGLC on draft-irtf-cfrg-spake2-13
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: Sun, 18 Oct 2020 20:54:20 -0000

Hello CFRG and Watson,

I have reviewed the draft and think that is quite clear and readable.

In the course of the detailed specification for CPace, we have just
stumbled over a possible implementation pitfall, that might also apply
in the same form to implementations for SPAKE2. The topic is likely only
a theoretical problem and might likely be classified as "overly picky".
I'm not aware of any feasable attack, but still it might be worth adding
a hint in the text.

The problem that we found out when digging through the details for CPace
is, that it is not uncommon for Diffie-Hellman secret scalar sampling
algorithms out in the wild to have a slight bias.

If you generate the secret scalars just by using a standard RNG, you
likely will get a uniform distribution between [0,2^l - 1) for some l
but not something uniform modulo the group order.

Your current specification is explicit and completely secure with
requiring that the secret scalars have to be sampled randomly *and*
*uniformly*:

>   To begin, A picks x randomly and uniformly from the integers in
>   [0,p), and calculates X=x*P and T=w*M+X, then transmits pA=T to B.
>
>   B selects y randomly and uniformly from the integers in [0,p), and
>   calculates Y=y*P, S=w*N+Y, then transmits pB=S to A.

In fact, I believe that many implementations for Diffie-Hellman will just generate a random number
and won't care about uniform distribution in [0,p). When scanning briefly, I've even seen
implementations having some bits set to a fixed value for Diffie-Hellman (also for short Weierstrass
curves, not only the clamping for X25519 and X448).
Typically such a structure (unlike the case for ECDSA signatures) should not be so critical for
ephemeral Diffie-Hellman.

Still for the case of SPAKE2 and CPace such a
bias could in theory allow for some sort of offline password test, since if X and Y only come from a
fraction of the entire group. If one has a distinguisher for the structure in the secret scalar,
one would be able to rule out some values of W*m and thus some passwords. (I don't actually believe that
such a distinguisher exists (it might have to solve the DDH?) in practice.)

 From an implementation-security point of view, I think that for most curves, one should probably
drop the uniformity requirement, as any additional calculation involving the secret scalar that one
implements for getting uniform distribution might leak information on the secret scalar...
 From a theory point of view, the transmitted points on the wire only include zero information if pA
pB could be any arbitrary point on the curve...

The possible implementation attack might generate more risk than advantage in practice.? We might
actually be better of with leaking a small, but negligible and un-exploitable amount of information.?

So, summing up, it might be worth discussing this topic and adding a recommendation. At least it might
be worth adding a note, that some Diffie-Hellman code might not actually consider the
uniformity requirement and come up with a suggestion how to realize the uniformity.

For curves such as Curve25519 I'd clearly suggest to drop the uniformity requirement because the order
of the curve is extremely close to a power of two that any problem could be ruled out.
I'm not so decided regarding curves such as Brainpool or P256 where the order is further away from a
power of two.

There it might be possible to recommend to sample some more bits and reduce the result modulo the
group order. In the Hash2Curve draft they are doing something similar IIRC (however regarding the
field primes).

As stated before, I think that either option would have its advantages. My gut feeling would be that
one might be better of with skipping the uniformity requirement.?

I'd be happy to discuss this topic in some more depth, because the exact same consideration applies to
CPace if it's used on curves different from Curve25519 (i.e. with p significantly different from 2^l).

Yours,

Björn.

Am 14.10.2020 um 08:06 schrieb Stanislav V. Smyshlyaev:
>
> Dear CFRG participants,
>
> This message is starting 2 weeks RGLC on
> draft-irtf-cfrg-spake2-13 ("SPAKE2, a PAKE"), that will end on October
> 29th 2020. If you've read the document and think that it is ready (or
> not ready) for publication as an RFC, please send a message in reply
> to this email or directly to CFRG chairs (cfrg-chairs@ietf.org
> <mailto:cfrg-chairs@ietf.org>). If you have detailed comments, these
> would also be very helpful at this point.
>
> The document has undergone many reviewing during the PAKE selection
> process (see https://github.com/cfrg/pake-selection/). Later there was
> another review (of -12 version) by Scott Fluhrer (thanks, Scott!),
> https://mailarchive.ietf.org/arch/msg/crypto-panel/ZYeiXy4J5whuW2Thvqx1jcxq8Xs/.
>
>
> SPAKE2 was not selected as a result of a selection process, but since
> it predated the contest, the chairs decided not to stop it (and only
> it, not any other PAKEs), asking the authors to add the corresponding
> disclaimer in the draft: "This document predated the CFRG PAKE
> competition and it was not selected.".
>
>
> Thank you,
>
> Stanislav, for CFRG chairs
>
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg