Re: [Cfrg] Structure in the S-box of the Russian algorithms (RFC 6986, RFC 7801)

"Stanislav V. Smyshlyaev" <smyshsv@gmail.com> Mon, 11 February 2019 06:44 UTC

Return-Path: <smyshsv@gmail.com>
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 E5707130DDA for <cfrg@ietfa.amsl.com>; Sun, 10 Feb 2019 22:44:46 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.998
X-Spam-Level:
X-Spam-Status: No, score=-1.998 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, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
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 DU45bgtprtma for <cfrg@ietfa.amsl.com>; Sun, 10 Feb 2019 22:44:43 -0800 (PST)
Received: from mail-qt1-x82e.google.com (mail-qt1-x82e.google.com [IPv6:2607:f8b0:4864:20::82e]) (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 779AD12870E for <cfrg@irtf.org>; Sun, 10 Feb 2019 22:44:43 -0800 (PST)
Received: by mail-qt1-x82e.google.com with SMTP id y20so10916543qtm.13 for <cfrg@irtf.org>; Sun, 10 Feb 2019 22:44:43 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=op5EXwuc4NaV8GPjnrzn0AS2uSH/OT7tzOeB3h5iUds=; b=fmyzBVmZ7FVNVQ2tjmdJCRPEdKS+46z2g4PwvV8sFW2H5WQ0su/hbX1d03Ak5hAmxx 93buIk19ZZP0j2b1vpL9YwufZNjk/LMQ6/PxV1cwg2Uuo5OIN6lB0jezc9CcV64iatxY LRpQXKRWglNzXxBMby/FFwy+CgR8R3ta5wA6ZpE75o8tqX1qnJ4nqtmYSiTJTnvCqbn0 TUJweVkFpJpyqoV4BeCxdfTcRGiESzoznkw+j4lW7OLOcwHllM29RJwdsdXallp3E+4s WYelEGCwVtO6j48XQAm8G+wYDF3mW4iV5r1Lk+xG5t3aZNSWQWzXaIyNIlqiCKii7qrM Lozw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=op5EXwuc4NaV8GPjnrzn0AS2uSH/OT7tzOeB3h5iUds=; b=uZtcnmsAhB1BS/Yx2RIq+uwAhlbiYlDrTmYoGKwelZGyLSKJSAsXZYzteFs+/SqtpI 16gVbbseAObE9xIQgjkkSvmR+u2Y8iihIlAb9V4XZQgmem5Ikep5QcEnyh247ko1xR12 /ii/FOXimSmPUGcjhfHNaC3w2Qu4koLYowDy7oRvYhiGmbvRoq+B/RayuhgM8873RXGh CTNvNCaO3lcm9UVnEidh2ujlVvGZ4miALg7XDME9nTgBX+SJIbW71v7ZCqo/H1gaiaQy ixHrvwqw2NSs9IoF3Db/cE5NWw+qOSb5Nc/+t6dtAi6e6VE0lIR/glDO5jGlq9IUGJku 99/Q==
X-Gm-Message-State: AHQUAuZxehFciYLlzyyWRgcjny2mwSBR1zYgpuGxAgxTECOfPKYqDFPD sqT64s80ix9o+joJIKLwFCQqvyV2VwE6v+EL2HA=
X-Google-Smtp-Source: AHgI3IbaX35aGj6ZEJjf3Ldh65gSFzmeuoKqBLIDQQZXNw+xaPmqqlXQmD15feQ2KFEDp0GHAc44NOtQkC2xzIu6OSs=
X-Received: by 2002:ac8:3341:: with SMTP id u1mr7366545qta.58.1549867481993; Sun, 10 Feb 2019 22:44:41 -0800 (PST)
MIME-Version: 1.0
References: <47911132.8757406.1549835386894.JavaMail.zimbra@inria.fr> <CAHOTMV+EtVP0xf8-pGpJZJLorYvNWaTuQ1+JXN2TuB7jOdsbPg@mail.gmail.com>
In-Reply-To: <CAHOTMV+EtVP0xf8-pGpJZJLorYvNWaTuQ1+JXN2TuB7jOdsbPg@mail.gmail.com>
From: "Stanislav V. Smyshlyaev" <smyshsv@gmail.com>
Date: Mon, 11 Feb 2019 09:42:43 +0300
Message-ID: <CAMr0u6k+awvZLRuCvCY_a+NokvqtgvL0gsAedmzUvDXvzvFWTA@mail.gmail.com>
To: Tony Arcieri <bascule@gmail.com>
Cc: Leo Perrin <leo.perrin@inria.fr>, CFRG <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="000000000000b694d5058198a432"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/pVgTbAX8J0dLeU1yTgZ2_CKeMMw>
Subject: Re: [Cfrg] Structure in the S-box of the Russian algorithms (RFC 6986, RFC 7801)
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: Mon, 11 Feb 2019 06:44:47 -0000

Dear Tony,

In response to your tweet
https://mobile.twitter.com/bascule/status/1094832386271932416
and this message of yours.

I am not able to comment anything on the principles of the generation of
Streebog and Kuznyechik S-Boxes - I've always been working in a commercial
company that develops software and was never invlolved in synthesis of
Russian cryptoprimitives.

But I can tell you everything about the process of generation of Edwards
curves, since my colleagues and I were the ones who generated them (and
later proposed for standardization in addition to older Weierstrass ones) –
since we needed to increase performance of digital signatures used in our
products.

You are totally right that W had not been selected according to modern good
principles of deterministic (and verifiable) search of suitable parameters.
It would be better if it was, but most of the curves that existed that time
were not even generated with parameters equal to hash values of some data
(with "verifiable pseudo-random" parameters).

But those curves were generated in 2012 - they reflected best practices and
state-of-the-art of that time. And Streebog was used for the obvious reason
- it was a new hash function that was standardized in Russia (as a part of
GOST R 34.11-2012 standard) and available for me and my colleagues.

Best regards,
Stanislav


пн, 11 февр. 2019 г. в 09:30, Tony Arcieri <bascule@gmail.com>om>:

> On Sun, Feb 10, 2019 at 1:50 PM Leo Perrin <leo.perrin@inria.fr> wrote:
>
>> This situation is unlike anything else in the literature. [....] Still,
>> at the moment, I don't know of any attack leveraging my new decomposition
>> as the partition in the input is the partition in multiplicative cosets
>> (and not additive ones). Nevertheless, I can't think of a good reason for
>> the designers of these algorithms to use this structure and, worse, to keep
>> this fact secret; especially since the presence of such properties demands
>> a specific analysis to ensure that the algorithms are safe.
>>
>
> Streebog was used as the hash function for the elliptic curve generation
> procedure for 512-bit Edwards curves standardized in GOST R 34.10-2012. I'm
> curious, even hypothetically, if this attack could be combined with an
> attacker-controlled hash input (W) to maliciously influence curve parameter
> selection.
>
> Thread:
> https://mailarchive.ietf.org/arch/msg/cfrg/1L7W2lPu4MtcHOfjoTFn_mmGPG4
>
> A selected email below with an interesting passage highlighted...
>
> ---------- Forwarded message ---------
> From: Stanislav V. Smyshlyaev <smyshsv@gmail.com>
> Date: Wed, Jan 28, 2015 at 6:14 AM
> Subject: Re: [Cfrg] 512-bit twisted Edwards curve and curve generation
> methods in Russian standardization
> To: Alyssa Rowan <akr@akr..io <akr@akr.io>>o>>, cfrg@irtf.org <cfrg@irtf.org>
>
>
> Dear Alyssa,
>
> 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).
>
> --
> Tony Arcieri
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>