[openpgp] "SHA-1 is a Shambles" and forging PGP WoT signatures

Marcus Brinkmann <marcus.brinkmann@rub.de> Wed, 22 January 2020 14:31 UTC

Return-Path: <marcus.brinkmann@rub.de>
X-Original-To: openpgp@ietfa.amsl.com
Delivered-To: openpgp@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 64D3E1200F4 for <openpgp@ietfa.amsl.com>; Wed, 22 Jan 2020 06:31:38 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Level:
X-Spam-Status: No, score=-2 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_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=rub.de
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 Aty4wX92KLGm for <openpgp@ietfa.amsl.com>; Wed, 22 Jan 2020 06:31:33 -0800 (PST)
Received: from out1.mail.ruhr-uni-bochum.de (out1.mail.ruhr-uni-bochum.de [IPv6:2a05:3e00:8:1001::8693:3595]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 577BC1200F1 for <openpgp@ietf.org>; Wed, 22 Jan 2020 06:31:33 -0800 (PST)
Received: from mx1.mail.ruhr-uni-bochum.de (localhost [127.0.0.1]) by out1.mail.ruhr-uni-bochum.de (Postfix mo-ext) with ESMTP id 482nsG2YStz8S6C for <openpgp@ietf.org>; Wed, 22 Jan 2020 15:31:30 +0100 (CET)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=rub.de; s=mail-2017; t=1579703490; bh=UUxDbd0USwiXnClA7jIuEaiMNYqWxAES4Arn50UlNig=; h=To:From:Subject:Date:From; b=QEdlwhjAYENIZV6YPQ3cNt8OXR4G3sQ0IBVzbI7E8i9ZlrrEtmZT3fDVMYs3xKrAM NGpcRjlxpLs8af8bGcTlsMMwg50OU2zk9lRD/5MILTiTg+pLPpdykegm9tUEaLiAyp NYmsfyz8b+ZEHRLw9sW9iRBeH0hcqZ5yMJLjYG+M=
Received: from out1.mail.ruhr-uni-bochum.de (localhost [127.0.0.1]) by mx1.mail.ruhr-uni-bochum.de (Postfix idis) with ESMTP id 482nsG18Gvz8S5s for <openpgp@ietf.org>; Wed, 22 Jan 2020 15:31:30 +0100 (CET)
X-Envelope-Sender: <marcus.brinkmann@rub.de>
X-RUB-Notes: Internal origin=IPv6:2a05:3e00:c:1001:5054:ff:fe37:b9e4
Received: from mail1.mail.ruhr-uni-bochum.de (mail1.mail.ruhr-uni-bochum.de [IPv6:2a05:3e00:c:1001:5054:ff:fe37:b9e4]) by out1.mail.ruhr-uni-bochum.de (Postfix mi-int) with ESMTP id 482nsF5R9Gz8S5N for <openpgp@ietf.org>; Wed, 22 Jan 2020 15:31:28 +0100 (CET)
X-Virus-Status: Clean
X-Virus-Scanned: clamav-milter 0.102.1 at mx1.mail.ruhr-uni-bochum.de
Received: from [IPv6:2a05:3e00:9:2100:3870:dcb7:49cd:d8e0] (dyn-0e8ddc947bcd078300129000.nds.ipv6.ruhr-uni-bochum.de [IPv6:2a05:3e00:9:2100:3870:dcb7:49cd:d8e0]) by mail1.mail.ruhr-uni-bochum.de (Postfix) with ESMTPSA id 482nsB0L8Kzyv6 for <openpgp@ietf.org>; Wed, 22 Jan 2020 15:31:26 +0100 (CET)
To: openpgp@ietf.org
From: Marcus Brinkmann <marcus.brinkmann@rub.de>
Autocrypt: addr=marcus.brinkmann@rub.de; keydata= mQINBFZU6WABEADoVonKbB/tV0v25cm39DaSZyN7it70RhTZHLESbpDiHCwiAMi74MK/HB/q VR9LZDkTDF1x5xUnxxMHa2rpxO329dlk5dQFq1iELxIC/yBCEh5HMLT5MkWqwb8UkINYpaFU csQdPvdC2RzZ4Wt5/xX/6mvSnA4g7hSmUKwIiDX6489Fj5jHK3i0UQFnzKty3O7mqSbedTHs ym2q6fPcIlEOvU6unzxJRK4bgfW2NBM6aMqgLeQkKYIkd1Q/OXEWCXC4hQJepak+n34ChIrV RRHIBJ0GHRkEgHQgQUqPLS0fJlMYCaSZFmOAaqmigxVn1ErG3jTnFQPbPkfE5SCssFP2grNV N1ikJzOEpBLYA/4pOaJzSnZ0xx9aKPdUsyBksKmCsLQNiRt4ZTNFpJ2DJ8NbXYAFkrcu15og lrB//CVQj3CfkzUbpyfcwJHAho1K6XaPybI14znuorTJF3ml0qDd3XDkcmnF58s4hfvGHQtz +CEW+85gUF+T9jKLpwNGcNdBhbvdE6d3cSbR7dXeZsxiA4AmqqEhH6SnVmkSqmhX4+k6RksE MrHJnzefTyA4kXIR2QvD60nZXqta35VhhCzIcpkUpxcwABBR7C8nCxiGV7wNmGECgHv+Zl/O hQhWF1Ld1G93xCg7D+Nz0RerRdwtBOUatmCp+2HRTcRXNOW8jQARAQABtCNNYXJjdXMgQnJp bmttYW5uIDxtYXJjdXNAZ251cGcub3JnPokCTgQTAQgAOBYhBDyw6EQWrVL34YZUGIiwjVpX tiFABQJYvsfeAhsDBQsJCAcCBhUICQoLAgQWAgMBAh4BAheAAAoJEIiwjVpXtiFAYdQP/jvj o7gm3tcDn8E2Pj2aOd8ajpKEajc3GZ4iDDXngTSPjvuQwB2PgUtfpzpOZW065OMXzMi3+XN9 ZY77Vp4xKhVh2+wxXd3b7jJArTfEave4RfVGlkWJXTrg2zbbwad/suZUT1Nqla4j0S6X7mtR oDVUFVivl7/9dGF4Ctldzms9uE0YktQs9xDl72igOhJX+RtGmM1rTgyncaSPam8KBQPYvLA+ bdTao/bB5wsW7PFBv2r2QOZthe/FGWbWanLuj2nQwdOvfr8RXKabTOzqPmBZwWCNSIfkzjCK m2KzpDkXghiJfK9jOgBSE4tGPieInZj6RSB2r848Uykshmwp0tFFMLIuJbn24czCLRwOuKbg IiWR9SzgENJwDqalBOjOS9jEGVsCzM0YctY6gMURbfv7RNevI7Q4rS6Tw4PmgCN4e8B69O5n Z0Ipf+brUfWL9rcsd9+Ugm8fpK8vykQpcRqYt+pSo5l6acZGgAa2AA8cxh87qbWQihB0ZiRo 2EH0t2DF8NDo32XHnQcuOR0R7JxhcJ3XCUaJr0SNSS3j4BVSE7Yso8T2hP7JdpwdFU88SUgC lX7DJspHtOYAIFldejMaFN3BDVx8+SgqDyEpGCHH04p3X95Wsev8ThRNpQ0dPqheOj2UKJWy ceddqC3VkGUpuTS9Q7xQBdwsX1Inp06ruQINBFZU6WABEAC3meKoeQn4r37Z1WCvl/lRVgwY LIEwGX94WCZODxPPEy2zTWStj45yv1ZrSI0HyAqssZzXPelOFJzlM8M+iccxIMRgjnnGJJR0 YqYUdraf1Z2YQk/x2WjYNUg0blChdyeqwBhLAQKtnPOKkTPZBBGzPjsS+JeB8yN5r4vouFGM G+CmYFUy4oCmcmuUrdLm9NlzM5ituyTJsPG9CDO834e4qlZsNW/yEzyPsYDW0PxJxgEe/WjL sDJ0aiwaDhBpR8/i2FfEUTGXl+6wvdXR9lhddBoiUCVlNRu9jiKVxv2JVJepcZa9B/atJwcs DAkZJgnjP0qRybixx/wo14KromgWVBGwpZ89sFEgZF6HcxPMKuWtieIORzs9kb0jpMFi1hW9 xi60UBHikrpDG9MnwA35d1lg/9kUlrF1nqTnyoz43UxntlgQejl6JcBR2Poaaib3ZtCR34yx slFz4znXBermA2eEvusEmjYJlxPWozW18grbSYUr1tCmjvKZAIMrspVx37+WSm/4fy8Mq9iq hkIweFQM10GL+fRQOGJTpSY/KiGxmkaTPtj9iaovJOcGAjUzzreGhi4toIrWWULPNKS6vuV4 VgMBF4XxIcVqC9I43yzJ6/cYciwL9bxoWQ4EpHuIG3sewvOWbceeDO9j9DRSd9E6GX67Nzrr uDPXOoge2QARAQABiQIfBBgBAgAJBQJWVOlgAhsMAAoJEIiwjVpXtiFAHBwP/3x5953X/1jR 2AegR6oHSF0HAD8kMnKLP5cwLqrOzUpCwqzFGBCbYdvxrWG106jyvcZdUvtBSGd8n1FuE2Wr pQrKgNjdRG65cN2kduk/w66Oq57EqSuO/r6OnadG9hgVZ1YP/QUsL6n4oF7coD0CJiH98UyL w1yP3Em1ONX8ditvMVHNudVC1VoEN1BFjIX9VWqWoU843vPct9wKi6jLYHHAX3UpnEJtfqLH Cj554s+0yhMhoaAIfNQZWU9iKzldM6Y0j8DJ/YBSThhw9S/TX7mClhXArJ/iPJSr6FPhlQMM cZRQaSiQu1gDL76I5G03SkBWCnXbSpeNtTeMiSpsA58c8rpr2T4giCiV29FPgEj4We2/jBrB cwWA/XjSLE2RNOnF2G65dVxHAlaCc84lC2+bh9kVU+Tb+9YDWfHyNO+pNk/Lpaef2Kg6ScKm te6+wVkWQZFTU8mgkHZqFvQk29RnV02phRTM0ryvWWldNgf3vzztS3iyD3GrJCPcxjm24cAf lp+7JfQ4qV/ec598k++HI4r3SfmSFKFcsxh+073p+oVjs5kIHxM0SExdjKewLOE3BKQYjn1r 17xWXogKlIGbTEluQ4Odyh4n88/iA8ZLNPKjvjno7UuwBsZyJxdaTOXlQYt+ZRZNfIBSWqv0 U9fYtp9qPuy4vCfkycCucIgO
Message-ID: <d8321b24-8836-2702-6b01-242b4cab932f@rub.de>
Date: Wed, 22 Jan 2020 15:31:26 +0100
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.4.1
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="------------04332C14DE5F76CD3DAC75F1"
Content-Language: en-US
X-Virus-Scanned: clamav-milter 0.99.4 at mail1.mail.ruhr-uni-bochum.de
X-Virus-Status: Clean
Archived-At: <https://mailarchive.ietf.org/arch/msg/openpgp/h-6vCMDFFKhVXpXLC6gAt9tK7r8>
Subject: [openpgp] "SHA-1 is a Shambles" and forging PGP WoT signatures
X-BeenThere: openpgp@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: "Ongoing discussion of OpenPGP issues." <openpgp.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/openpgp>, <mailto:openpgp-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/openpgp/>
List-Post: <mailto:openpgp@ietf.org>
List-Help: <mailto:openpgp-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/openpgp>, <mailto:openpgp-request@ietf.org?subject=subscribe>
X-List-Received-Date: Wed, 22 Jan 2020 14:31:38 -0000

Hi,

I have now read the paper "SHA-1 is a Shambles"[1,2] by Gaëtan Leurent
and Thomas Peyrin, and want to bring to your attention the significance
of the included work for OpenPGP.

Key findings: The authors significantly improve the identical-prefix and
chosen-prefix collisions for SHA-1, demonstrating that chosen-prefix
collisions are possible at a cost of 45k USD.  They also demonstrate how
to use a chosen-prefix collision to transfer a signature that binds a
photo-ID to a key to a crafted other key with a chosen user ID.

Some more explanations:

The attack works as follows: The attacker prepares a public key packet
for a 8192 bit RSA key, and assigns an arbitrary user ID for which the
attacker wants to get a certificate from the victim.  The attacker also
prepares another public key packet for a 6114 bit RSA key, followed by a
user attribute packet with an innocent (honest) photo id. The JPEG
format allows arbitrary trailing data hiding the user ID under attack.

A signer that signs the photo id will inadvertently also sign the
contained user ID.  The signature can then be transfered to the
colliding 8192-bit key with that user ID, because the signed hash is
identical (the JPEG is hidden in the public exponent of the larger key).

The attack is not stealthy and can be detected before and after the
signature is made (for example by the user id in the jpeg or by the jpeg
in the public key).

Some observations and recommendations:

* Obvious: do not use SHA-1 in signatures. GnuPG 2.x now forbids them,
but GnuPG 1 users should be aware of that issue (among many other issues
in GnuPG 1).

* Large key sizes in RSA seem to make the attack simpler compared to
short key sizes in ECC (which does not offer enough rooms for a
collision block).

* Do not sign photo ids.  In fact, photo ids are problematic in many
other ways and should be deprecated and not be used anymore. Support for
user attribute packets should be dropped from the standard.

* The authors could have easily created colliding public keys with
identical (160 bit SHA-1) fingerprints, at the cost of 45k USD.
Although I don't know about any attack made possible by owning such a
pair of keys, the pure existence of a fingerprint collision could cause
problems in some appliations, triggering potential bugs in code that
assumes fingerprints can never be identical.

* The attack complexity is 2^63.4, while long key IDS are 64 bit.  Long
key ID collisions based on the birthday collision have been demonstrated
as early as 2013 [3, 4].  Just based on the bit complexity, a pre-image
collision for long key IDs seems within reach now (up to an unknown
constant factor).

Thanks,
Marcus

[1] https://sha-mbles.github.io/
[2] https://eprint.iacr.org/2020/014.pdf
[3] "OpenPGPv4 long keyid collision test cases?" (David Leon Gil)
https://mailarchive.ietf.org/arch/msg/openpgp/Al8DzxTH2KT7vtFAgZ1q17Nub_g
[4] "The Long Key ID Collider" (Chris Wellons)
https://nullprogram.com/blog/2019/07/22/

-- 
Dipl.-Math. Marcus Brinkmann

Lehrstuhl für Netz- und Datensicherheit
Ruhr Universität Bochum
Universitätsstr. 150, Geb. ID 2/461
D-44780 Bochum

Telefon: +49 (0) 234 / 32-25030
http://www.nds.rub.de/chair/people/mbrinkmann