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

Tony Arcieri <bascule@gmail.com> Mon, 11 February 2019 06:29 UTC

Return-Path: <bascule@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 B4EC6130DDA for <cfrg@ietfa.amsl.com>; Sun, 10 Feb 2019 22:29:44 -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 Oz6WEoa21JpK for <cfrg@ietfa.amsl.com>; Sun, 10 Feb 2019 22:29:42 -0800 (PST)
Received: from mail-ot1-x334.google.com (mail-ot1-x334.google.com [IPv6:2607:f8b0:4864:20::334]) (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 19E2812894E for <cfrg@irtf.org>; Sun, 10 Feb 2019 22:29:41 -0800 (PST)
Received: by mail-ot1-x334.google.com with SMTP id w25so15589150otm.13 for <cfrg@irtf.org>; Sun, 10 Feb 2019 22:29:41 -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=+DdmqphBhrbYNgluzoMbyDVMF20Do0DLwqRyFolVozI=; b=N2elb3BcFnzD2VRXryR1mJKn/bObHwoCoSWP/1bOvl3HIH2H9I1xrWjLK7wPCRB4E5 QFhYSWqbM07M79QW+oud7CA9xSvyIapF1QqPvuE+B5lMYye8omWwIOzscoylVcUb9CWq wM12aCCzSL+y7RUU/JTVXaGu5iqWrVAVGOXw7hw7ieKqwL6BmjvvatWJtLJpNHJkeZ7H TYpEtdKbUqaoXtEZpnutAMgBCb6b7lWcC6TmjBA+t0FOxe2rGWcUK74WC8uVcrVc5Mee +HAN2+2X8/hB1ylRazz7A4gERvSNU/vIAM8zF6PseKBElF2nBQIwPkn2a+5VcM3m46uh ftVw==
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=+DdmqphBhrbYNgluzoMbyDVMF20Do0DLwqRyFolVozI=; b=AbfamShH65r2p2RRTjB3pns9y4rQJFLAqjOFCTI3FunaI/si6M2KbG3/43ytUCVulV 0oD9QcbtyZjSxeq+wUkK2RWrZKM7bk/KyorSsRVnccBtqrXa89ssZIdHCPL0FAxiRkof /xgmIhkXUKlAxyxIEkp0yMpvqodPCVE3d8xRltBSBV+NmRgMu0yPfq5euknc904o5HAJ GxJ2A4EMZT6LCeIXoS1vHUuDsqVMYHxsKNEQ2cMIOT9VKsDJotOTlxcclFFvA8//tfLW dGkT+20J9zBF9emclc8tSshhq0AGKjmAVK9ieqccU5X65ZHF45C27qKlH0HENHDWTu/G QI8Q==
X-Gm-Message-State: AHQUAuaNEQ+oACDunvwBri2BlU8q8gso0rhXVC4SRYCnLOjtoGwHZfKL GldTjGgwXCheunm06avIH8KbZFFeISIjWfYDvEc=
X-Google-Smtp-Source: AHgI3IbNguicjIZ6VjMsj+0BweQbPAvQOSFJHl4LTEqj4z4I9Aaxr2EEBxssEhfkJOz1NODueNISIeMF/34Y6qh/ZGQ=
X-Received: by 2002:a05:6830:1115:: with SMTP id w21mr25707937otq.316.1549866580858; Sun, 10 Feb 2019 22:29:40 -0800 (PST)
MIME-Version: 1.0
References: <47911132.8757406.1549835386894.JavaMail.zimbra@inria.fr>
In-Reply-To: <47911132.8757406.1549835386894.JavaMail.zimbra@inria.fr>
From: Tony Arcieri <bascule@gmail.com>
Date: Sun, 10 Feb 2019 22:29:29 -0800
Message-ID: <CAHOTMV+EtVP0xf8-pGpJZJLorYvNWaTuQ1+JXN2TuB7jOdsbPg@mail.gmail.com>
To: Leo Perrin <leo.perrin@inria.fr>
Cc: CFRG <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="000000000000005db20581986ffb"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/AGK48qbldZJ1hZvf8exvB2XXy88>
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:29:45 -0000

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>io>, 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