Re: [Cfrg] On the (non-)randomness of the S-box of Streebog and Kuznyechik

Stephen Farrell <stephen.farrell@cs.tcd.ie> Mon, 05 August 2019 18:02 UTC

Return-Path: <stephen.farrell@cs.tcd.ie>
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 54ADD1202E3 for <cfrg@ietfa.amsl.com>; Mon, 5 Aug 2019 11:02:46 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -4.299
X-Spam-Level:
X-Spam-Status: No, score=-4.299 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_MED=-2.3, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=cs.tcd.ie
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 Z0vh3NK_bD1X for <cfrg@ietfa.amsl.com>; Mon, 5 Aug 2019 11:02:43 -0700 (PDT)
Received: from mercury.scss.tcd.ie (mercury.scss.tcd.ie [134.226.56.6]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 42CC61202D8 for <cfrg@irtf.org>; Mon, 5 Aug 2019 11:02:42 -0700 (PDT)
Received: from localhost (localhost [127.0.0.1]) by mercury.scss.tcd.ie (Postfix) with ESMTP id E84BCBE56; Mon, 5 Aug 2019 19:02:39 +0100 (IST)
X-Virus-Scanned: Debian amavisd-new at scss.tcd.ie
Received: from mercury.scss.tcd.ie ([127.0.0.1]) by localhost (mercury.scss.tcd.ie [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id NCDttkE_UNHD; Mon, 5 Aug 2019 19:02:38 +0100 (IST)
Received: from [10.244.2.138] (95-45-153-252-dynamic.agg2.phb.bdt-fng.eircom.net [95.45.153.252]) by mercury.scss.tcd.ie (Postfix) with ESMTPSA id E0F18BE51; Mon, 5 Aug 2019 19:02:37 +0100 (IST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cs.tcd.ie; s=mail; t=1565028158; bh=NWRW+asG4g8vlq4P8wuKrAxKFH2vwwoT5sD/vh4uKWw=; h=To:References:From:Subject:Date:In-Reply-To:From; b=t+I8EkVc+Y0Kigsnhj+sbG+xZ/XYn39+a7XcL/9WVyv48Wi04JLr6RtvoUKEYghuC c0gdSYGTsN2XGnaUUHpcWEGccPyDhmI2zo2Zu+JTcyXEw7DLBhaaWAGoXmi2HL+Nq6 HiTDQmD0/Ti4dzd1bboPGefL/E+nA6y1X980jm/U=
To: Leo Perrin <leo.perrin@inria.fr>, cfrg <cfrg@irtf.org>
References: <1327417226.25659372.1565019306532.JavaMail.zimbra@inria.fr>
From: Stephen Farrell <stephen.farrell@cs.tcd.ie>
Openpgp: id=5BB5A6EA5765D2C5863CAE275AB2FAF17B172BEA; url=
Autocrypt: addr=stephen.farrell@cs.tcd.ie; prefer-encrypt=mutual; keydata= mQINBFo9UDIBEADUH4ZPcUnX5WWRWO4kEkHea5Y5eEvZjSwe/YA+G0nrTuOU9nemCP5PMvmh 5Cg8gBTyWyN4Z2+O25p9Tja5zUb+vPMWYvOtokRrp46yhFZOmiS5b6kTq0IqYzsEv5HI58S+ QtaFq978CRa4xH9Gi9u4yzUmT03QNIGDXE37honcAM4MOEtEgvw4fVhVWJuyy3w//0F2tzKr EMjmL5VGuD/Q9+G/7abuXiYNNd9ZFjv4625AUWwy+pAh4EKzS1FE7BOZp9daMu9MUQmDqtZU bUv0Q+DnQAB/4tNncejJPz0p2z3MWCp5iSwHiQvytYgatMp34a50l6CWqa13n6vY8VcPlIqO Vz+7L+WiVfxLbeVqBwV+4uL9to9zLF9IyUvl94lCxpscR2kgRgpM6A5LylRDkR6E0oudFnJg b097ZaNyuY1ETghVB5Uir1GCYChs8NUNumTHXiOkuzk+Gs4DAHx/a78YxBolKHi+esLH8r2k 4LyM2lp5FmBKjG7cGcpBGmWavACYEa7rwAadg4uBx9SHMV5i33vDXQUZcmW0vslQ2Is02NMK 7uB7E7HlVE1IM1zNkVTYYGkKreU8DVQu8qNOtPVE/CdaCJ/pbXoYeHz2B1Nvbl9tlyWxn5Xi HzFPJleXc0ksb9SkJokAfwTSZzTxeQPER8la5lsEEPbU/cDTcwARAQABtDJTdGVwaGVuIEZh cnJlbGwgKDIwMTcpIDxzdGVwaGVuLmZhcnJlbGxAY3MudGNkLmllPokCQAQTAQgAKgIbAwUJ CZQmAAULCQgHAgYVCAkKCwIEFgIDAQIeAQIXgAUCWj6jdwIZAQAKCRBasvrxexcr6o7QD/9m x9DPJetmW794RXmNTrbTJ44zc/tJbcLdRBh0KBn9OW/EaAqjDmgNJeCMyJTKr1ywaps8HGUN hLEVkc14NUpgi4/Zkrbi3DmTp25OHj6wXBS5qVMyVynTMEIjOfeFFyxG+48od+Xn7qg6LT7G rHeNf+z/r0v9+8eZ1Ip63kshQDGhhpmRMKu4Ws9ZvTW2ACXkkTFaSGYJj3yIP4R6IgwBYGMz DXFX6nS4LA1s3pcPNxOgrvCyb60AiJZTLcOk/rRrpZtXB1XQc23ZZmrlTkl2HaThL6w3YKdi Ti1NbuMeOxZqtXcUshII45sANm4HuWNTiRh93Bn5bN6ddjgsaXEZBKUBuUaPBl7gQiQJcAlS 3MmGgVS4ZoX8+VaPGpXdQVFyBMRFlOKOC5XJESt7wY0RE2C8PFm+5eywSO/P1fkl9whkMgml 3OEuIQiP2ehRt/HVLMHkoM9CPQ7t6UwdrXrvX+vBZykav8x9U9M6KTgfsXytxUl6Vx5lPMLi 2/Jrsz6Mzh/IVZa3xjhq1OLFSI/tT2ji4FkJDQbO+yYUDhcuqfakDmtWLMxecZsY6O58A/95 8Qni6Xeq+Nh7zJ7wNcQOMoDGj+24di2TX1cKLzdDMWFaWzlNP5dB5VMwS9Wqj1Z6TzKjGjru q8soqohwb2CK9B3wzFg0Bs1iBI+2RuFnxLkCDQRaPVAyARAA+g3R0HzGr/Dl34Y07XqGqzq5 SU0nXIu9u8Ynsxj7gR5qb3HgUWYEWrHW2jHOByXnvkffucf5yzwrsvw8Q8iI8CFHiTYHPpey 4yPVn6R0w/FOMcY70eTIu/k6EEFDlDbs09DtKcrsT9bmN0XoRxITlXwWTufYqUnmS+YkAuk+ TLCtUin7OdaS2uU6Ata3PLQSeM2ZsUQMmYmHPwB9rmf+q2I005AJ9Q1SPQ2KNg/8xOGxo13S VuaSqYRQdpV93RuCOzg4vuXtR+gP0KQrus/P2ZCEPvU9cXF/2MIhXgOz207lv3iE2zGyNXld /n8spvWk+0bH5Zqd9Wcba/rGcBhmX9NKKDARZqjkv/zVEP1X97w1HsNYeUFNcg2lk9zQKb4v l1jx/Uz8ukzH2QNhU4R39dbF/4AwWuSVkGW6bTxHJqGs6YimbfdQqxTzmqFwz3JP0OtXX5q/ 6D4pHwcmJwEiDNzsBLl6skPSQ0Xyq3pua/qAP8MVm+YxCxJQITqZ8qjDLzoe7s9X6FLLC/DA L9kxl5saVSfDbuI3usH/emdtn0NA9/M7nfgih92zD92sl1yQXHT6BDa8xW1j+RU4P+E0wyd7 zgB2UeYgrp2IIcfG+xX2uFG5MJQ/nYfBoiALb0+dQHNHDtFnNGY3Oe8z1M9c5aDG3/s29QbJ +w7hEKKo9YMAEQEAAYkCJQQYAQgADwUCWj1QMgIbDAUJCZQmAAAKCRBasvrxexcr6qwvD/9b Rek3kfN8Q+jGrKl8qwY8HC5s4mhdDJZI/JP2FImf5J2+d5/e8UJ4fcsT79E0/FqX3Z9wZr6h sofPqLh1/YzDsYkZDHTYSGrlWGP/I5kXwUmFnBZHzM3WGrL3S7ZmCYMdudhykxXXjq7M6Do1 oxM8JofrXGtwBTLv5wfvvygJouVCVe87Ge7mCeY5vey1eUi4zSSF1zPpR6gg64w2g4TXM5qt SwkZVOv1g475LsGlYWRuJV8TA67yp1zJI7HkNqCo8KyHX0DPOh9c+Sd9ZX4aqKfqH9HIpnCL AYEgj7vofeix7gM3kQQmwynqq32bQGQBrKJEYp2vfeO30VsVx4dzuuiC5lyjUccVmw5D72J0 FlGrfEm0kw6D1qwyBg0SAMqamKN6XDdjhNAtXIaoA2UMZK/vZGGUKbqTgDdk0fnzOyb2zvXK CiPFKqIPAqKaDHg0JHdGI3KpQdRNLLzgx083EqEc6IAwWA6jSz+6lZDV6XDgF0lYqAYIkg3+ 6OUXUv6plMlwSHquiOc/MQXHfgUP5//Ra5JuiuyCj954FD+MBKIj8eWROfnzyEnBplVHGSDI ZLzL3pvV14dcsoajdeIH45i8DxnVm64BvEFHtLNlnliMrLOrk4shfmWyUqNlzilXN2BTFVFH 4MrnagFdcFnWYp1JPh96ZKjiqBwMv/H0kw==
Message-ID: <3bb0c4d9-9f08-3717-3149-4bc5efa3eb62@cs.tcd.ie>
Date: Mon, 5 Aug 2019 19:02:37 +0100
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.8.0
MIME-Version: 1.0
In-Reply-To: <1327417226.25659372.1565019306532.JavaMail.zimbra@inria.fr>
Content-Type: multipart/signed; micalg=pgp-sha512; protocol="application/pgp-signature"; boundary="4Xrzv3XhJafLYUCtskVOnpF5oD75jHiTZ"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/gxJ8GdFv9wrh6G7lY4qlQBUe0rg>
Subject: Re: [Cfrg] On the (non-)randomness of the S-box of Streebog and Kuznyechik
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, 05 Aug 2019 18:02:47 -0000

Hiya,

On 05/08/2019 16:35, Leo Perrin wrote:
> Because of these observations, I insist that the designers of these
> algorithms have provided cryptanalysts with misleading information.
> There cannot be any good reason for this, which is why I think these
> algorithms cannot be trusted, and thus that RFC 6986 and 7801 should
> be deprecated.
Actually, this might need to be (at least partly) handled outside
CFRG by the IETF, as there is at least one standards track DNSSEC
RFC (RFC8624 [1]) with a normative reference to 6986.

There are also other documents with references to these RFCs, you
can see which documents reference 6986 at [2] and 7801 at [3]. (I
didn't check any of the others of those out myself though.)

However, the DNSSEC situation may be less bad than it seems, as
8624 says:

"
   GOST R 34.11-94 has been superseded by GOST R 34.11-2012 in
   [RFC6986].  GOST R 34.11-2012 has not been standardized for use in
   DNSSEC.
"

Does the structure you've discovered also exist in GOST R 34.11-94?

If it did, then there'd be a good case (IMO) to further deprecate use
of DNSSEC hash function #3, but if not, then perhaps the correct thing
is some kind of erratum to the effect that 6986 really ought not be
a normative reference in 8624 but rather RFC5831 ought be what's
referenced.

There is a similar statement about the related signature algorithm
(code point #12) defined in RFC7091 that also has a normative
reference to 6986.

Complicating matters a bit more, both code points are defined
with a "MUST NOT" implementation recommendation (which I don't
really understand;-) in RFC8624.

In general I would support CFRG deprecating any algorithms for
which there is significant doubt. I have not myself verified that
the structure Leo has found is real, but assuming it is then IMO
that'd be sufficient reason to deprecate these algorithms. But, I
think deprecating algorithms ought be done taking into account
existing deployments as well as the severity of the issue with
the algorithm. I'm not familiar with how widely these algorithms
are deployed.

For Leo: if you think these algorithms ought be deprecated then
writing an I-D to that effect would be what you'd want to do. If
you wanted help from someone more familiar with IETF/IRTF process
crap, I'd be happy to try help as needed.

Cheers,
S.

[1] https://tools.ietf.org/html/rfc8624
[2] https://datatracker.ietf.org/doc/rfc6986/referencedby/
[3] https://datatracker.ietf.org/doc/rfc7801/referencedby/