Re: including the entire fingerprint of the issuer in an OpenPGP certification

Peter Pentchev <roam@ringlet.net> Thu, 20 January 2011 22:51 UTC

Received: from hoffman.proper.com (localhost [127.0.0.1]) by hoffman.proper.com (8.14.4/8.14.3) with ESMTP id p0KMpVI7077875 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Thu, 20 Jan 2011 15:51:31 -0700 (MST) (envelope-from owner-ietf-openpgp@mail.imc.org)
Received: (from majordom@localhost) by hoffman.proper.com (8.14.4/8.13.5/Submit) id p0KMpVsP077874; Thu, 20 Jan 2011 15:51:31 -0700 (MST) (envelope-from owner-ietf-openpgp@mail.imc.org)
X-Authentication-Warning: hoffman.proper.com: majordom set sender to owner-ietf-openpgp@mail.imc.org using -f
Received: from praag.hoster.bg (praag.hoster.bg [77.77.142.10]) by hoffman.proper.com (8.14.4/8.14.3) with ESMTP id p0KMpTW6077868 for <ietf-openpgp@imc.org>; Thu, 20 Jan 2011 15:51:30 -0700 (MST) (envelope-from roam@ringlet.net)
Received: from middenheim.hoster.bg (middenheim.hoster.bg [77.77.142.11]) by praag.hoster.bg (Postfix) with ESMTP id D5B7C8CAE5 for <ietf-openpgp@imc.org>; Fri, 21 Jan 2011 00:51:27 +0200 (EET)
Received: from straylight.ringlet.net (host86.office-vpn.int.hoster.bg [10.100.10.86]) (Authenticated sender: roam@hoster.bg) by mail.hoster.bg (Postfix) with ESMTP id 5C2F95C455 for <ietf-openpgp@imc.org>; Fri, 21 Jan 2011 00:51:14 +0200 (EET)
Received: from roam (uid 1000) (envelope-from roam@ringlet.net) id 416024 by straylight.ringlet.net (DragonFly Mail Agent) Fri, 21 Jan 2011 00:51:14 +0200
Date: Fri, 21 Jan 2011 00:51:14 +0200
From: Peter Pentchev <roam@ringlet.net>
To: Avi <avi.wiki@gmail.com>
Cc: Jon Callas <jon@callas.org>, IETF OpenPGP Working Group <ietf-openpgp@imc.org>
Subject: Re: including the entire fingerprint of the issuer in an OpenPGP certification
Message-ID: <20110120225114.GB4981@straylight.ringlet.net>
References: <CFCF61BD-9281-4F09-AD31-C5AAC38315FE@callas.org> <4D354A08.1010206@iang.org> <87lj2isgm8.fsf@vigenere.g10code.de> <58216C60-3DFD-4312-B514-19243ED4220A@callas.org> <4D36010A.30205@fifthhorseman.net> <4D360E46.1080208@epointsystem.org> <4D3615A5.1050700@fifthhorseman.net> <3B73CC58-35BE-460D-8378-4869DB00BA30@callas.org> <4764FF65-D26A-40A2-98F9-53A9857BD41E@callas.org> <AANLkTikKT40F=dG7zmjM+T2SRMm2HDqQrVHT-+nmh_A+@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="X1bOJ3K7DJ5YkBrT"
Content-Disposition: inline
In-Reply-To: <AANLkTikKT40F=dG7zmjM+T2SRMm2HDqQrVHT-+nmh_A+@mail.gmail.com>
User-Agent: Mutt/1.5.20 (2009-06-14)
X-MailScanner-ID: 5C2F95C455.2AEF1
X-hoster-MailScanner: Found to be clean
X-hoster-MailScanner-SpamCheck: not spam, SpamAssassin (not cached, score=0.001, required 10, autolearn=disabled, UNPARSEABLE_RELAY 0.00)
X-hoster-MailScanner-From: roam@ringlet.net
X-hoster-MailScanner-To: ietf-openpgp@imc.org
X-Spam-Status: No
Sender: owner-ietf-openpgp@mail.imc.org
Precedence: bulk
List-Archive: <http://www.imc.org/ietf-openpgp/mail-archive/>
List-Unsubscribe: <mailto:ietf-openpgp-request@imc.org?body=unsubscribe>
List-ID: <ietf-openpgp.imc.org>

On Thu, Jan 20, 2011 at 11:36:32AM -0500, Avi wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA512
> 
> Even more strongly, there is the difference between "almost
> never" and "never". Even if there were an infinite number of key
> id's along the real number continuum, the possibility of a
> collision is mathematically 0%,
	
...I believe you mean "practically 0%", since mathematically,
it is definitely not 0% :)

> but it is still possible. Heck,
> the possibility of ANY id would be mathematically 0, but each
> key would still have an ID.

Same here, ITYM "practically" or "virtually" 0 :)

> Here, we are dealing with a discrete distribution, so there
> /are/ mass points (be they VERY very small) at each ID, so yes,
> it is 100% certain that eventually, not only will there be a
> collision, but every key will have a collision.

Theoretically, this is not necessarily true.  It depends a lot on the
hashing algorithm used - it is completely possible to design a hashing
algorithm that would produce a certain digest for one input value and
one input value only - hell, it's trivial to design one based on another
hashing algorithm: "If the input is 'abcd', produce SHA1('abcd'); else,
if SHA1(input) == SHA1('abcd'), produce SHA1('abcde'); else, produce the
same result as SHA1(input)."

I'm pretty much certain that for SHA1 your statement would be true, but
I'm not certain if it has been proved - greater minds here would
probably know: has anyone looked into that, and has it been proven that
there does not exist any sequence of bytes which would have an unique
SHA1 hash, that is, against which it is impossible to do a preimage
attack?

> It may be
> though, that the waiting time may be longer than the heat death
> of the universe for the latter, so we don't have to worry about
> that too much :).

G'luck,
Peter

-- 
Peter Pentchev	roam@ringlet.net roam@FreeBSD.org peter@packetscale.com
PGP key:	http://people.FreeBSD.org/~roam/roam.key.asc
Key fingerprint	FDBA FD79 C26F 3C51 C95E  DF9E ED18 B68D 1619 4553
Hey, out there - is it *you* reading me, or is it someone else?