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

Marcus Brinkmann <marcus.brinkmann@rub.de> Thu, 23 January 2020 23:48 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 7EB7C12001A for <openpgp@ietfa.amsl.com>; Thu, 23 Jan 2020 15:48:51 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Level:
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, RCVD_IN_DNSWL_NONE=-0.0001, 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=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 8_NMSeO8aK87 for <openpgp@ietfa.amsl.com>; Thu, 23 Jan 2020 15:48:49 -0800 (PST)
Received: from out2.mail.ruhr-uni-bochum.de (out2.mail.ruhr-uni-bochum.de [IPv6:2a05:3e00:c:1001::8693:2ae5]) (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 E25D0120019 for <openpgp@ietf.org>; Thu, 23 Jan 2020 15:48:48 -0800 (PST)
Received: from mx2.mail.ruhr-uni-bochum.de (localhost [127.0.0.1]) by out2.mail.ruhr-uni-bochum.de (Postfix mo-ext) with ESMTP id 483f9m3ts6z8S6M for <openpgp@ietf.org>; Fri, 24 Jan 2020 00:48:44 +0100 (CET)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=rub.de; s=mail-2017; t=1579823324; bh=PRhuqcK6OTmuJxdcTqBr1AaZ112lDp4HonhQLzPq+RY=; h=Subject:References:From:To:Date:In-Reply-To:From; b=Ug+chy/33alajqNQ5UXlL/avRDYcBiCJsw/KbJePgVfQ2y01Q+z5230UJgBJIe/Ub NyJxc0/tGDSGnwJ2EpiB1W037MOFqU0ie/qRG3Dm4X7VIrmhzIxjfJPTIapmFuIqVc OM+VlRYO40T+pNo34NMYGyNZ6v3EXx3cZN7IyMQo=
Received: from out2.mail.ruhr-uni-bochum.de (localhost [127.0.0.1]) by mx2.mail.ruhr-uni-bochum.de (Postfix idis) with ESMTP id 483f9m2Fq4z8S4K for <openpgp@ietf.org>; Fri, 24 Jan 2020 00:48:44 +0100 (CET)
X-RUB-Notes: Internal origin=IPv6:2a05:3e00:c:1001:5054:ff:fe37:b9e4
X-Envelope-Sender: <marcus.brinkmann@rub.de>
Received: from mail1.mail.ruhr-uni-bochum.de (mail1.mail.ruhr-uni-bochum.de [IPv6:2a05:3e00:c:1001:5054:ff:fe37:b9e4]) by out2.mail.ruhr-uni-bochum.de (Postfix mi-int) with ESMTP id 483f9l6mzbz8S47 for <openpgp@ietf.org>; Fri, 24 Jan 2020 00:48:43 +0100 (CET)
X-Virus-Status: Clean
X-Virus-Scanned: clamav-milter 0.102.1 at mx2.mail.ruhr-uni-bochum.de
Received: from [192.168.142.139] (p5DCA495B.dip0.t-ipconnect.de [93.202.73.91]) by mail1.mail.ruhr-uni-bochum.de (Postfix) with ESMTPSA id 483f9k6JNxzysk for <openpgp@ietf.org>; Fri, 24 Jan 2020 00:48:42 +0100 (CET)
References: <d8321b24-8836-2702-6b01-242b4cab932f@rub.de> <e4dc8c25-2282-17a8-7e64-cee55f43be84@kuix.de>
From: Marcus Brinkmann <marcus.brinkmann@rub.de>
To: IETF OpenPGP <openpgp@ietf.org>
Message-ID: <602eeb15-fccf-fe61-7b28-7dea35d3af15@rub.de>
Date: Fri, 24 Jan 2020 00:48:43 +0100
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.3.0
MIME-Version: 1.0
In-Reply-To: <e4dc8c25-2282-17a8-7e64-cee55f43be84@kuix.de>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 8bit
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/u-S9v9Dvi0CM8qStw_TvSO7w8vI>
Subject: Re: [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: Thu, 23 Jan 2020 23:48:52 -0000

Hi,

On 1/23/20 11:56 PM, Kai Engert wrote:
> On 22.01.20 15:31, Marcus Brinkmann wrote:
>> * 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.
> 
> Does this mean, anyone can create a key pair that has the same
> fingerprint as I have on my business card, by spending that amount of
> money?

No. That is something that we would call a "second pre-image attack" on
your fingerprint.  The collision attacks described in the paper generate
two colliding files from scratch.  So, the attacker could come up with
two entirely new keys that have identical fingerprints.  As I said, I
don't know any attack that would be enabled by such two keys, but it is
concerning, because software might not be prepared for that to happen.

Pre-image attacks are much harder than collision attacks (which are
easier due to the "birthday paradox").  However, it is not good practice
to hold on to a cryptographic hash function for a long time just because
one narrow particular application of it has not been demonstrated
publicy to be broken in practice yet.  We pretty much know the
progression in which hash function attacks improve, and interest in
researching an obsolete hash function decreases pretty rapidly.  I'm
glad the authors spent the time and money to demonstrate their optimized
attacks on SHA-1, but such expenses will be increasingly hard to justify.

> Does this mean, comparing a 20 bytes (40 hex digits) fingerprint, as
> printed by e.g. GnuPG 2.2.x, is no longer a reliable way to verify you
> have obtained the correct key?
The answer to this would formally be "yes", because after creating two
such keys, the attacker could first show you one key, and, later on show
you the other key and if the only thing you remember about the first key
is the fingerprint, you have no way to notice the swap.

The question if this is an actual problem (i.e.: violates a security
goal that the user is actually interested in) is more difficult to
answer and depends on many details.  Figuring this out would require a
careful review of OpenPGP implementations and applications using OpenPGP.

Thanks,
Marcus

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