Re: [Cfrg] I-D Action: draft-irtf-cfrg-spake2-08.txt
Greg Hudson <ghudson@mit.edu> Sat, 27 April 2019 16:07 UTC
Return-Path: <ghudson@mit.edu>
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 876061200B7 for <cfrg@ietfa.amsl.com>; Sat, 27 Apr 2019 09:07:02 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -4.201
X-Spam-Level:
X-Spam-Status: No, score=-4.201 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_MED=-2.3, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
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 fu_BsOzhEek7 for <cfrg@ietfa.amsl.com>; Sat, 27 Apr 2019 09:06:59 -0700 (PDT)
Received: from outgoing.mit.edu (outgoing-auth-1.mit.edu [18.9.28.11]) (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 F1300120195 for <cfrg@ietf.org>; Sat, 27 Apr 2019 09:06:58 -0700 (PDT)
Received: from localhost (SMALL-GODS.MIT.EDU [18.9.55.42]) (authenticated bits=0) (User authenticated as ghudson@ATHENA.MIT.EDU) by outgoing.mit.edu (8.14.7/8.12.4) with ESMTP id x3RG6uJH014507 for <cfrg@ietf.org>; Sat, 27 Apr 2019 12:06:57 -0400
From: Greg Hudson <ghudson@mit.edu>
To: cfrg@ietf.org
References: <20190313034352.GE8182@kduck.mit.edu>
Date: Sat, 27 Apr 2019 12:06:56 -0400
Message-ID: <x7dv9yze8kf.fsf@mit.edu>
MIME-Version: 1.0
Content-Type: text/plain
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/yo4nTivdheV3u51WgxenR_3wa8k>
Subject: Re: [Cfrg] I-D Action: draft-irtf-cfrg-spake2-08.txt
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: Sat, 27 Apr 2019 16:07:03 -0000
I did some additional digging, and want to make sure I've laid out my argument clearly. Apologies for the length. The -08 draft made two changes to the non-augmented SPAKE2 description which I believe are misguided: * The private x and y coefficients were in "[0, p*h) divisible by h" but are now in "[0,p)". In other words, x and y were changed from scaled coefficients (divisible by h) to unscaled coefficients. * A verification step was added: "Upon receipt of T, B computes T*h and aborts if the result is equal to I" with clarification "A and B multiply protocol messages from each peer by h so as to avoid small subgroup attacks, but the result of the multiplication is not used for operations other than the comparison against I and the non-multiplied value is used in subsequent calculations." I want to address the verification step first. To do so, I want to consider the simpler scenario of a Diffie-Hellman key exchange over a curve with cofactor 1. In this algorithm, each party picks a private coefficient from [0,p) and sends xP or yP, and each party computes K=xyP by multiplying its private coefficient by the other party's public point. Should each party check whether the other party's public point is I (or equivalently, if K=I), and throw it out? The cases for throwing out K=I are that everyone will know the shared point, and that the party in a position to do the verification doesn't contribute anything to the result (xI=I for all values of x). Note that this verification step causes legitimate executions of the algorithm to break in the unlikely case that either party happens to pick x=0 or y=0; this can be fixed by selecting the private coefficients from (0,p) instead of [0,p). K being non-secret isn't an interesting attack; an attacker can achieve the same result by executing the algorithm correctly and then revealing K to the world. The non-contributory behavior (the ability to force a specific channel key) does pose a problem if channel-binding is used by an authentication protocol on top of the unauthenticated DH channel. Checking for K=I foils this attack, but an implementor might leave this step out while still interoperating. A better way to foil this attack at the protocol level is to hash the shared point together with the public keys to derive the channel key; this measure is more robust because if an implementor leaves out that step, they won't interoperate. (See [1] for a related example of this robustness argument.) Note that RFC 7748 section 6.1 specifies "a key-derivation function that includes K, K_A, and K_B". The question of contributory behavior is discussed in the context of Bernstein description of X25519 [2]. (X25519 is more complicated because the cofactor is 8, and it uses Montgomery coordinates which admits points on the twist, but the question still holds for cofactor 1 and more traditional coordinates). The issue is also discussed in RFC 7748 section 6 and 7; the RFC notes that "Protocol designers using Diffie-Hellman over the curves defined in this document must not assume 'contributory behaviour'" and permits an optional verification check that K!=I, but notes that many implementations don't do it. If the curve has cofactor h>1, there are two additional considerations for malicious public points (see also [3]): 1. There are additional points of small order. For instance, if h=8, there is one point of order 2, two points of order 4, and four points of order 8. Sending any of these low-order points results in a small number of possible values for the shared key, similarly to sending I. 2. There are additional points of order p times divisors of h. For instance, if h=8, there are p-1 points of order 2p, 2p-2 points of order 4p, and 4p-4 points of order 8p. Sending any of these points results in a large number of possible values for the shared key--but if the attacker can find out what the shared key is, they can test its order and extract a few low-order bits of the other party's private coefficient. A simple way of eliminating these extra concerns is to pick private coefficients which are scaled by h, i.e. from [0,hp) divisible by h. This change introduces two extra multiplications by h into the algorithm, one during public point generation and the other during the computation of K. Multiplying a point within the p-order subgroup by h produces another point within the subgroup, with the same range of possible values (since h is relatively prime to p). Multiplying a curve point outside of the p-order subgroup by h results in a point within the subgroup (e.g. a point of order 8p, multiplied by 8, has order p; a point of order 4, multiplied by 8, has order 1). This technique is sometimes called "clearing the cofactor". X25519 (RFC 7748 section 5) does this when massaging random bytes to a scalar value; note that in this massaging, the three lowest-order bits are set to 0, forcing divisibility by 8. Let's return to SPAKE2. In SPAKE2, the public points are masked by adding wM or wN: T=xP+wM and S=yP+wN. The computation of the shared point unmasks the other party's public point by subtracting wM or wN: K=x(S-wN) or K=y(T-wM). The final step is still to multiply by your own private coefficient, just as in Diffie-Hellman. Is a verification step necessary in SPAKE2? I think it is unnecessary and undesirable, for the following reasons: * If S or T is a point of small order such that hT=I, the shared point K still has a contribution from the legitimate party, -xwN or -ywM, with the full range of the prime-order subgroup as possible results. Even if the attacker can learn K, they cannot use it to launch an offline attack against w, because they do not know x or y. * SPAKE2 key derivation folds in the public points, again forcing contributory behavior, and foiling an MITM attack by an attacker who knows w. (In this attack the attacker sends T=wM to one party and S=wN to the other, forcing K=0 for both parties, in an attempt to get both parties to use the same key in order to foil channel binding.) * Verifying S and T breaks the unlikely case where x=0 or y=0. Verifying K breaks the unlikely case where xP=-wM (e.g. if x and w both happen to be 0, but also in other cases). * The Abdalla-Pointcheval paper [4] does not describe any verification step. Although I don't believe they considered groups with stray elements outside the prime-order subgroup, they must have considered the identity element. Clearing the cofactor is of value in SPAKE2, as it is in Diffie-Hellman. For example, if an attacker sends a point T of order 8p, T-wM will also have order 8p, and the order of K=y(T-wM) will reveal a few low-order bits of y. Choosing y from [0,hp) divisible by h means those low-order bits are always 0, so no information is revealed. Therefore: * We should used scaled (divisible by h) coefficients in SPAKE2, as the -07 draft did, in order to clear the cofactor * We should not add a verification step. * SPAKE2+ should use a scaled (divisible by h) w1 value, to clear the cofactor when computing Z and V. This would be a change from -07. [1] https://mailarchive.ietf.org/arch/msg/cfrg/3co2iEaaeKRDixtML3OKo9aV9cU [2] http://cr.yp.to/ecdh.html#validate [3] https://safecurves.cr.yp.to/twist.html [4] https://www.di.ens.fr/~mabdalla/papers/AbPo05a-letter.pdf
- [Cfrg] I-D Action: draft-irtf-cfrg-spake2-08.txt internet-drafts
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-spake2-08.… Greg Hudson
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-spake2-08.… Benjamin Kaduk
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-spake2-08.… Greg Hudson
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-spake2-08.… Paterson Kenneth
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-spake2-08.… Greg Hudson
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-spake2-08.… Paterson Kenneth
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-spake2-08.… Benjamin Kaduk
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-spake2-08.… Greg Hudson
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-spake2-08.… Paterson Kenneth
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-spake2-08.… Chris Wood
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-spake2-08.… Greg Hudson
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-spake2-08.… Eike Kiltz
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-spake2-08.… Eike Kiltz
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-spake2-08.… Greg Hudson