[Cfrg] Notice on chosen-prefix collisions for SHA-1

Thomas Peyrin <thomas.peyrin@gmail.com> Fri, 10 May 2019 14:09 UTC

Return-Path: <thomas.peyrin@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id E0E7A120096 for <cfrg@ietfa.amsl.com>; Fri, 10 May 2019 07:09:37 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.999
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, 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 ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id 6sb-Gt5y-C9m for <cfrg@ietfa.amsl.com>; Fri, 10 May 2019 07:09:36 -0700 (PDT)
Received: from mail-vs1-xe2e.google.com (mail-vs1-xe2e.google.com [IPv6:2607:f8b0:4864:20::e2e]) (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 EEFEA12001E for <cfrg@irtf.org>; Fri, 10 May 2019 07:09:35 -0700 (PDT)
Received: by mail-vs1-xe2e.google.com with SMTP id j184so3680894vsd.11 for <cfrg@irtf.org>; Fri, 10 May 2019 07:09:35 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:from:date:message-id:subject:to :content-transfer-encoding; bh=U+kWlPdx2g0/fMxeZfWsz9VVcNFImk4aFr+qsLAv7mQ=; b=EFJ+Ec9LWhQOerl7bnt01dSOPJZ2kPVHpxwClQ9+DAEXebvpw9CgrEGJuouy8mLBN3 Z3CdjajVQeHsaO1eWovwE1xsH+jC+MKmyipDxJ0iGR/N/6Ka09ZdAShMtcAUa7GT4Ai6 R8Byx+3JolVPy/eTasnAnCdx1a4Bb0q7VZckbZe1cbuc3C/o6ISgY4oOr1i4vtQpdCuM u9MG+zSwi6axaT3XbdWOHSMqCqJ9XTB3vc/PpjCpbpEPFpeDP1ksbjqWpNLg2+ebiGXc QIfZkeMMZgGiP1cafLQb0xy32YtezZjgO/HCL3Ai6o1YaDhcx/basd9rldUtduvdDa3m AaXw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to :content-transfer-encoding; bh=U+kWlPdx2g0/fMxeZfWsz9VVcNFImk4aFr+qsLAv7mQ=; b=bnnh7Ii93iYAvZT6dfCgsqKPwBbdMKKinc1iltQWjiaXRtBe5YRxx6mweiz5ftiiFc fu92POoMt1ByoTOAQLuQYqXnlpyZ+lvJqXAKJIltK/OewMSvkSycOky/S2WS1rjexxhJ ZnQiVlLLXOPhtbVIKyZOOINrFucoaVJ1G5wxcwN1sOmW+OigsZ91l5CbPe5T5YWKdzts UgNoCpVcMpS0Bebb6Lbnhp26sFDt6r3X5ZOj/iCURJXF/wWIEJNlA74JyUHM1TXySmeM AFErG0oCWh+nc39g6rbT7RYOMstvp2QV2bKJVrJGR3Oa6vgnPce+aEMoY9X0iRF32RNw r/7g==
X-Gm-Message-State: APjAAAUsK3rx/H8vH5JlA9binKXOjK6R95+qwjzAf1U5Syu8G2SaKnNp Nas5liDWSwvqjnHtNEnoVKpT46/gTC8E6tV1vfa5chVwbWU=
X-Google-Smtp-Source: APXvYqy64UOHvrI4q5tbNsGlAdHPGpEt89XphEnGxV5TSuXPVodVKKwXBhRw1kasCf3p6BoVQMmkB2IXRdDjw7JSIc4=
X-Received: by 2002:a67:6945:: with SMTP id e66mr6275024vsc.44.1557497374758; Fri, 10 May 2019 07:09:34 -0700 (PDT)
MIME-Version: 1.0
From: Thomas Peyrin <thomas.peyrin@gmail.com>
Date: Fri, 10 May 2019 22:09:19 +0800
Message-ID: <CAA0wV7TziOQ7EWHOtFYnCxcK4OqfCMNNXp+vRKM7ogheDWqZQw@mail.gmail.com>
To: cfrg@irtf.org
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/NhiGvOFzcEw108YLwF_ndyfB1k4>
Subject: [Cfrg] Notice on chosen-prefix collisions for SHA-1
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: Fri, 10 May 2019 14:09:38 -0000

Dear CFRG members,

We, Gaetan Leurent and myself, would like to emphasize some results we
will present in a few days at Eurocrypt 2019 [LP19]. ePrint version
available here: https://eprint.iacr.org/2019/459.pdf

[TL;DR] Chosen-prefix collisions for SHA-1 hash function are now
practical (cost lower than 100K $), all hope is lost.

As you might know, SHA-1 hash function has been broken theoretically
since 2005 [W+05] and an actual collision was computed in 2017 [S+17].
This clearly makes SHA-1 a function to avoid, but even though
deprecation efforts have been conducted since many years, SHA-1 is
still used in several security products and RFC standards (TLS 1.2,
git, ...)

Finding a collision attack breaks the hash function, but the actual
damage that can be done with such a collision is somewhat limited as
the attacker will have little to no control on the actual data that
collides. A much more interesting attack is to find a so-called
chosen-prefix collision, where the attacker can freely choose the
prefix for the two colliding messages. This was for example used to
create rogue-CA for MD5 [S+09] and in general chosen-prefix collision
attacks have a huge impact on security [BL16].

Yet, these chosen-prefix collisions are believed to be much harder to
find than classical collisions. For SHA-1, the best previous search
method required 2^77 SHA-1 evaluations [S13], which remained out of
reach in practice. In our article, we explain how to drastically
reduce the cost of finding chosen-prefix collisions for SHA-1, down to
almost the same cost as finding a classical collision. With some
additional improvements that we are currently working on, we evaluate
that one can find a chosen-prefix collision for SHA-1 with a budget of
less than 100K US$. We therefore recommend to avoid SHA-1 at all cost,
especially for use in certificates/digital signatures.

[BL16] Karthikeyan Bhargavan, Gaëtan Leurent, "Transcript Collision
Attacks: Breaking Authentication in TLS, IKE and SSH", NDSS 2016
[LP19] Gaetan Leurent Thomas Peyrin, “From Collisions to Chosen-Prefix
Collisions - Application to Full SHA-1”, Eurocrypt 2019
[S+09] Marc Stevens, Alexander Sotirov, Jacob Appelbaum, Arjen K.
Lenstra, David Molnar, Dag Arne Osvik, Benne de Weger, “Short
Chosen-Prefix Collisions for MD5 and the Creation of a Rogue CA
Certificate”, Crypto 2009
[S13] Marc Stevens, “New Collision Attacks on SHA-1 Based on Optimal
Joint Local-Collision Analysis”, Eurocrypt 2013
[S+17] Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini,
Yarik Markov, "The first collision for full SHA-1", Crypto 2017
[W+05] Xiaoyun Wang, Yiqun Lisa Yin and Hongbo Yu, “Finding Collisions
in the Full SHA-1”, Crypto 2005