Re: [Cfrg] 512-bit twisted Edwards curve and curve generation methods in Russian standardization

"Stanislav V. Smyshlyaev" <smyshsv@gmail.com> Thu, 29 January 2015 10:06 UTC

Return-Path: <smyshsv@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id E9B741A0149 for <cfrg@ietfa.amsl.com>; Thu, 29 Jan 2015 02:06:09 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Level:
X-Spam-Status: No, score=-1.999 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, HTML_MESSAGE=0.001, SPF_PASS=-0.001] autolearn=ham
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 DidoPCYCdgO2 for <cfrg@ietfa.amsl.com>; Thu, 29 Jan 2015 02:06:07 -0800 (PST)
Received: from mail-oi0-x231.google.com (mail-oi0-x231.google.com [IPv6:2607:f8b0:4003:c06::231]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 718B71A010C for <cfrg@irtf.org>; Thu, 29 Jan 2015 02:06:07 -0800 (PST)
Received: by mail-oi0-f49.google.com with SMTP id a3so25043342oib.8 for <cfrg@irtf.org>; Thu, 29 Jan 2015 02:06:06 -0800 (PST)
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=+S4TU2cfYavuPUGjiUaz0kBdjGVHkhI0etXTXxQ8MP4=; b=uae+E3v/dytPhn/wq7Ak2JZqJWKOOkDbB7FdeFrhNdhWb8i5VcPApkfhewKBOJwQ4a UgNTsjwCg+1iKK5NfUaN2cx3dBFy5C++ocA5wJ07EK7mEhsaMiQulyDS1WYAXo+lKcTM hpOVhWX8hwbUodBsbUpkyOQl/fMIB8ZMFQo1kiLFM0LZe0f9q/rt7T3nOP2fPvMBnOmA 5VM2m3N1Kk+wtQu6hi9AEUrJL/rGRzacepxzq9v2PUxdsvugGYHdR5MU3/40YG43ShHM 94kHxVVgLZX0iiGBC/CNR887cDhLuqXHNmBpRECm8QZ33DEVnmznwvMvaDsWlagfJqxv moVg==
MIME-Version: 1.0
X-Received: by 10.60.133.20 with SMTP id oy20mr4286819oeb.55.1422525966734; Thu, 29 Jan 2015 02:06:06 -0800 (PST)
Received: by 10.182.5.103 with HTTP; Thu, 29 Jan 2015 02:06:06 -0800 (PST)
In-Reply-To: <CAHOTMVK63wE1PNypoJ_Ems734UMD_vEOq-muYLzNvVPMWwv==g@mail.gmail.com>
References: <CAMr0u6=prmjMv7e+S5UAGVw+uCQWPk-f86Koa04GVx8CZs4J4Q@mail.gmail.com> <C877C13D-0178-4BDD-BC58-4E7C417600D1@akr.io> <CAMr0u6=pgV8P19zoEbztCas20XX68V40wN-3qwrbqAxQeMpJQg@mail.gmail.com> <CAHOTMVK63wE1PNypoJ_Ems734UMD_vEOq-muYLzNvVPMWwv==g@mail.gmail.com>
Date: Thu, 29 Jan 2015 14:06:06 +0400
Message-ID: <CAMr0u6=L-OtiZtT0HnuBha55nv7vKApii4F2N4AoEMDjKs-daA@mail.gmail.com>
From: "Stanislav V. Smyshlyaev" <smyshsv@gmail.com>
To: Tony Arcieri <bascule@gmail.com>
Content-Type: multipart/alternative; boundary="047d7b47204eee59e0050dc7a2b1"
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/Vn27bxPMQOFZkj1aJMyESahkm7s>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] 512-bit twisted Edwards curve and curve generation methods in Russian standardization
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Thu, 29 Jan 2015 10:06:10 -0000

Hello, Tony,

> I totally understand that a property that occurs with 2^{-18} (as
Bernstein did with BADA55 curves) can be forced to exist in the selected
curve. The example that I posted earlier is the specific curve that is
standardized in Russia, by a group of experts where the condition mentioned
by Paul ("a group where even if a single person is trusted") is satisfied
("trusted" for us, not for the international community and CFRG, I suppose).

> When we generated our curves and fixed base points, the main problem that
we addressed was to ensure that for all protocols that make use of elliptic
curves and require "provably unknown" logarithms of some points (for
example, password protected key establishment, PAKE, EKE, PACE, etc.) can
obtain such a property: x-coordinates of base points and constant points
for prototocols are chosen by hashing some random seeds – we don't want
only a blind belief of randomness of such points (the most painful example
here is Dual EC DRBG, of course). We look at curve generation problem in a
similar way: we cannot be secure against the unknown bad properties of
curves that occur with probability of 2^{-18} – even if the procedure is
totally "rigid". But at least we can be sure that if some bad property of
our curves is found, we would know that this couldn't be a "backdoor" that
can be exploited only by developers of the curve, who know some logarithms,
preimages etc. (again, as with DUAL EC DRBG).

> If to talk about new curves for CFRG document, the usage of deterministic
("rigid") procedure is quite reasonable, we agree here. We've posted our
curve because we think that it can be interesting for CFRG to look at one
of the urves that have been standardized for all Russian cryptographic
community. We'll post some specific comments to the current draft later
today.


We know about BADA55 curves, we tried to explain our position on them in my
reply to Alyssa; for now I don't have anything to add. Anyway, thanks for
taking part in the discussion. We'll try to formulate our comments and
suggestions for the current draft later today.

Kind regards,

Stanislav


2015-01-28 20:22 GMT+03:00 Tony Arcieri <bascule@gmail.com>:

> On Wed, Jan 28, 2015 at 6:14 AM, Stanislav V. Smyshlyaev <
> smyshsv@gmail.com> wrote:
>
>> As we believe (and as it has been mentioned earlier during discussion at
>> CFRG), the initital seed value doesn't have to be chosen explicitly in case
>> of trust in basic hash function properties – to gain some "backdoor-type"
>> properties of the curve with d = hash(W), one has either to combine such
>> algebraic properties of a curve with properties of a hash function (for a
>> trivial example, to have an ability to obtain a hash preimage) or to choose
>> a very probable "backdoor-type" property of a curve (such that it is
>> possible to obtain by random choice of a curve).
>>
>
> Hi Stanislav,
>
> Dan Bernstein and Tanja Lange have already demonstrated that such
> "verifiably random" generation procedures can be used to surreptitiously
> tweak specific curve parameters:
>
> http://safecurves.cr.yp.to/bada55.html
>
> I for one would not feel particularly inclined to trust a curve generated
> with this method, and would personally prefer the sort of rigid curve
> generation approach that this committee and others have been working on to
> any curve with large unexplained mystery constants.
>
> --
> Tony Arcieri
>