Re: [kitten] SPAKE preauth: generation of SPAKE2 secret input

Watson Ladd <watsonbladd@gmail.com> Wed, 13 May 2015 14:18 UTC

Return-Path: <watsonbladd@gmail.com>
X-Original-To: kitten@ietfa.amsl.com
Delivered-To: kitten@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 12EB11B2C9B for <kitten@ietfa.amsl.com>; Wed, 13 May 2015 07:18:11 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.4
X-Spam-Level:
X-Spam-Status: No, score=-1.4 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, J_CHICKENPOX_101=0.6, SPF_PASS=-0.001] autolearn=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 8JNFT-Pb1bh8 for <kitten@ietfa.amsl.com>; Wed, 13 May 2015 07:18:09 -0700 (PDT)
Received: from mail-wi0-x22f.google.com (mail-wi0-x22f.google.com [IPv6:2a00:1450:400c:c05::22f]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id EAE351B2CA4 for <kitten@ietf.org>; Wed, 13 May 2015 07:18:00 -0700 (PDT)
Received: by wizk4 with SMTP id k4so200856210wiz.1 for <kitten@ietf.org>; Wed, 13 May 2015 07:17:59 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=Xfl+n4BoHUmKZMGpYPAEF54TL1JSBlCv/8mH2tCj550=; b=oDJe4IRBZXTSLy9C4EcGi2XPG5gaGHgQlO0g1GXKzvv2aZM20BExPiBTN6CChZaUfO kVGivX5lzt1TW2QcnW614kEK9TGMLWtl7zmuh6dHsgUfwswBe7zfgRmzhKDututIM60h 7oQo5vp+2HbQYmarZ6micmPwm39oem34+g9IWJeGQSIwubupd9i974J47ufzEVvKn6H3 6/8OUbqynFvlI+wb570ky+/t6alL/KOSPwQVra8CDwo/LqGqfJWePYiG2tqshps4uFfV U1fb0V7oG0wJlqPTy45JqwKn5EHC6HbJft0tDmfl9AMoHFYLuhR8dG53xaxkKKhVez8C 2tWQ==
MIME-Version: 1.0
X-Received: by 10.194.123.4 with SMTP id lw4mr39586350wjb.94.1431526679565; Wed, 13 May 2015 07:17:59 -0700 (PDT)
Received: by 10.194.20.97 with HTTP; Wed, 13 May 2015 07:17:59 -0700 (PDT)
In-Reply-To: <1431525091.3260.26.camel@redhat.com>
References: <x7dk2wd6355.fsf@equal-rites.mit.edu> <20150512214740.GT7287@localhost> <1431525091.3260.26.camel@redhat.com>
Date: Wed, 13 May 2015 07:17:59 -0700
Message-ID: <CACsn0cm9AEG+oi8S+trhvyHpFFLF=-tG4Qazp5e6SgnS037K+Q@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: Nathaniel McCallum <npmccallum@redhat.com>
Content-Type: text/plain; charset="UTF-8"
Archived-At: <http://mailarchive.ietf.org/arch/msg/kitten/N2jhUq1eFxc_CchZGOj_iFz7TpU>
X-Mailman-Approved-At: Wed, 13 May 2015 07:47:54 -0700
Cc: kitten@ietf.org
Subject: Re: [kitten] SPAKE preauth: generation of SPAKE2 secret input
X-BeenThere: kitten@ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Common Authentication Technologies - Next Generation <kitten.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/kitten>, <mailto:kitten-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/kitten/>
List-Post: <mailto:kitten@ietf.org>
List-Help: <mailto:kitten-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/kitten>, <mailto:kitten-request@ietf.org?subject=subscribe>
X-List-Received-Date: Wed, 13 May 2015 14:18:11 -0000

On Wed, May 13, 2015 at 6:51 AM, Nathaniel McCallum
<npmccallum@redhat.com> wrote:
> On Tue, 2015-05-12 at 16:47 -0500, Nico Williams wrote:
>> On Tue, May 12, 2015 at 02:51:02PM -0400, Greg Hudson wrote:
>> > For CFRG curves (when they exist), we'll be done; CFRG curves
>> > accept
>> > uniformly distributed bytes as input and force them into
>> > appropriate
>> > form for a scalar.  For instance, for curve25519/ed25519, five
>> > bits of
>> > the input are forced to specific values.
>>
>> Will that be true for other CFRG curves?  I hope so, that'd be nice.
>>
>> > For P-256, P-384, and P-521, we need a large integer in the range
>> > of the
>> > group order, which is not bit-aligned.  The simplest option is to
>> > just
>> > decode the bytes as a bignum and let the resulting distribution of
>> > scalar values be somewhat non-uniform (a small fraction of scalar
>> > values
>> > are effectively twice as likely as the other ones).  I don't think
>> > this
>> > slight non-uniformity is a problem, and so far the people I have
>> > talked
>> > to have agreed.  But I'd like to check here, and will probably
>> > also need
>> > to solicit opinions from Walter Ladd and maybe others.
>>
>> Yes, this is really a question for Watson Ladd in particular and
>> CFRG in
>> general.
>
> I have CC'd Watson Ladd.

The question of whether or not a protocol requires a uniformly
determined scalar is not a function of the curve, but the protocol.
EdDSA is much more stringent than key agreement, for instance: the
same scalar conversion code is dangerous to use with it.  Of course,
the curve doesn't tell you how to sample values: that's an
implementation detail and the there is nothing about P256 or P521 that
stops you from doing it by modular reduction of values only slightly
larger than the curvesize.

>
>> My take is that the public values being of the for xG + wM, where x
>> should be a randomly and uniformly chosen scalar, the xG term will
>> cause
>> the public value to be as uniformly distributed as x regardless of
>> how
>> non-uniform w might be.  So I think there's no harm in picking a
>> simple
>> mapping from the long-term key to w, provided there's a way to
>> abstract
>> this (see below).

w is not distributed uniformly: far from it. The question of how far
from uniform x may be distributed is a subtle one, but my guess is
that even gross deviations from uniformity are fine, so taking a bunch
of bytes mod the curve order is ok. But rejection sampling or modular
reduction of longer strings are both easy to implement to sidestep
this issue.

>>
>> However, don't you run into the same problem when generating the
>> ephemeral scalars?  Or does OpenSSL provide a function for that?  If
>> distributions of both w and x are uniform, then I don't know if x's
>> mere
>> randomness is enough (again, a question for Watson L.).
>
> OpenSSL provides a function for generating a random scalar uniformly
> distributed within a given range. It works by generating n bytes of
> random data, where n is the smallest number of bytes that can
> represent the range. Then it checks to see if the generated random
> data is within the range. If it is, the value is returned. If it is
> not, it repeats the process until an appropriate random value is found.
>
>> > I don't know if there are likely to be additional considerations
>> > for
>> > other old curves.  For example, if the curve cofactor is not 1, do
>> > we
>> > need to make sure the scalar value is divisible by the cofactor?
>> >  This
>>
>> Yes.
>
> The SPAKE draft covers this scenario.
>
>> > ties into the larger question of whether we can really make SPAKE
>> > preauth work with arbitrary non-CFRG curves without additional per
>> > -curve
>> > specification.
>>
>> Can we define a curve abstraction that provides what we need?
>>
>>  - random2scalar(r)             -> scalar
>>  - randomscalar()               -> scalar
>>  - dh(s)                        -> public   # for Curve25519-like
>> curves
>>  - dh_sharedsecret(s, public)   -> secret   # for Curve25519-like
>> curves
>>  - scalarmult(s, point)         -> point    # generic; points are
>> opaque
>>  - add(point1, point2)          -> point
>>  - sub(point1, point2)          -> point
>>  - encode_point(point)          -> octet string
>>  - decode_point(octet string)   -> point
>
> Specifying an abstraction this tightly removes the possibility for at
> least one optimization. I'm not sure I want to get into the
> abstraction business.
>
>>  - point_x(point)               -> x scalar
>>  - point_y(point)               -> y scalar
>>  - make_point(x, y)             -> point
>>  ...
>
> I'm not sure what these are even used for.
>
>> Ideally CFRG should be providing this for its curves.  It should be
>> pssible to implement such things for other curves too.
>>
>> Some of the above abstractions are a consequence of CFRG electing to
>> leave point encoding to each curve for DH (and, if it were useful,
>> perhaps for signatures too, though that's a debate that hasn't
>> happened
>> yet).

SPAKE2 requires addition be supported. That rules out Kummer lines.
The CFRG has not specified a model and how to encode points on that
for addition to work. When they do I will modify the draft
accordingly.

However, I don't understand why the above abstraction isn't an
implementation detail only. All one has to provide to use this draft
are two generators and how to encode group elements. The algorithms
for addition, multiplication etc. will be documented in the CFRG
eventually. It's true that many groups only come with one canonical
generator, but any sort of hashing method will give you two
generators.

>
> I'm not sure this is necessary. I think it is sufficient to specify
> that the group OIDs MUST define things like point encoding and M/N
> values or MUST implicitly use SEC1 compressed and the M/N values
> generated using the technique in the SPAKE draft.
>
>> > Whatever we do needs to be well-specified (or we will have
>> > interoperability issues), and cannot contain inherent timing
>> > channels
>> > since it operates on a secret input.
>>
>> Yes.
>
> +1



-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.