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

Avi <avi.wiki@gmail.com> Thu, 20 January 2011 16:37 UTC

Received: from hoffman.proper.com (localhost [127.0.0.1]) by hoffman.proper.com (8.14.4/8.14.3) with ESMTP id p0KGb5no061176 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Thu, 20 Jan 2011 09:37:05 -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 p0KGb5Yq061175; Thu, 20 Jan 2011 09:37:05 -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 mail-ew0-f43.google.com (mail-ew0-f43.google.com [209.85.215.43]) by hoffman.proper.com (8.14.4/8.14.3) with ESMTP id p0KGb3MV061167 (version=TLSv1/SSLv3 cipher=RC4-MD5 bits=128 verify=FAIL) for <ietf-openpgp@imc.org>; Thu, 20 Jan 2011 09:37:04 -0700 (MST) (envelope-from avi.wiki@gmail.com)
Received: by ewy22 with SMTP id 22so358464ewy.16 for <ietf-openpgp@imc.org>; Thu, 20 Jan 2011 08:37:02 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:reply-to:in-reply-to:references :from:date:message-id:subject:to:cc:content-type; bh=1F+riRajksYNoIicw1B3yWlsUYawIBXUlPi+rKbjV7Q=; b=fhhj9zVEoxWok1Nx9OVxbI/4hYWIt60V9aMplQO9hcBIldS3Vnk0J+sC84w0NBTxub bPDQZGg/Ug45td35QdLi251CnGlxdDwsBVyp10TXSGTVF4siJJ5cnlLGzvUFDFHf54Z3 R/SQhXK+yK8yW4ntBoNVEv1xhpzY7gdhAxuHo=
DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:reply-to:in-reply-to:references:from:date:message-id :subject:to:cc:content-type; b=rX5HUNR3xYmJ10da1sgOft0lucGJQWXUKWKeTPjkHk3v8eDg8td/Jt1d7DPQMeXHTz V4VGJMW6KmR2wQ5FJCJxDgLhBCYpa1ahZkJim8Azt+BQmRGxZ64u3pI8a57XnwTh3GMm OXOAEmViSO9vzcQiwLCux8BRN/JtS4Soz8jQk=
Received: by 10.213.104.143 with SMTP id p15mr3180932ebo.68.1295541422209; Thu, 20 Jan 2011 08:37:02 -0800 (PST)
MIME-Version: 1.0
Received: by 10.213.21.129 with HTTP; Thu, 20 Jan 2011 08:36:32 -0800 (PST)
Reply-To: avi.wiki@gmail.com
In-Reply-To: <4764FF65-D26A-40A2-98F9-53A9857BD41E@callas.org>
References: <E1Pf1WI-0007aL-EN@login01.fos.auckland.ac.nz> <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>
From: Avi <avi.wiki@gmail.com>
Date: Thu, 20 Jan 2011 11:36:32 -0500
Message-ID: <AANLkTikKT40F=dG7zmjM+T2SRMm2HDqQrVHT-+nmh_A+@mail.gmail.com>
Subject: Re: including the entire fingerprint of the issuer in an OpenPGP certification
To: Jon Callas <jon@callas.org>
Cc: IETF OpenPGP Working Group <ietf-openpgp@imc.org>
Content-Type: multipart/alternative; boundary="0015174c3ffe433b5c049a49be94"
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>

-----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%, but it is still possible. Heck,
the possibility of ANY id would be mathematically 0, but each
key would still have an ID.

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. 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 :).

- --Avi
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (MingW32) - GPGshell v3.77
Comment: Most recent key: Click show in box @ http://is.gd/4xJrs

iJgEAREKAEAFAk04ZIU5GGh0dHA6Ly9wZ3AubmljLmFkLmpwL3Brcy9sb29rdXA/
b3A9Z2V0JnNlYXJjaD0weEY4MEUyOUY5AAoJEA1isBn4Din525cA/R7idYB5pitE
chXetB0o7Kvp1/DEmyv/sCG/dkt4dMlLAP9QtALK5BngB+pMWCt1bxA3wTcRH33J
MO6qv7HAGBTNpQ==
=hQBO
-----END PGP SIGNATURE-----


----
User:Avraham

pub 3072D/F80E29F9 1/30/2009 Avi (Wikimedia-related key) <avi.wiki@gmail.com
>
   Primary key fingerprint: 167C 063F 7981 A1F6 71EC  ABAA 0D62 B019 F80E
29F9


On Thu, Jan 20, 2011 at 11:00 AM, Jon Callas <jon@callas.org> wrote:

>
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> A side-effect of this is something that's either an obvious extension or in
> the spec already.
>
> Section 3.3 says: "Implementations SHOULD NOT assume that Key IDs are
> unique."
>
> It's said that since 2440, for the following reason...
>
> In PGP1 days, Vinnie started working there and told me that he'd generated
> a key and gotten a certain error when putting it into the keyserver. I was
> thrilled, because that error was a duplicate keyid error. We'd been having
> debates over this ourselves. Being a software engineer, I tend to consider
> assuming that a database key is unique is bad form. I recognize that
> pseudo-random 64-bit numbers don't collide easily at all, but assuming
> uniqueness is something that is easily coded around. That key was my proof
> that engineering-wise, don't assume uniqueness.
>
> Sadly, he had deleted the key and just generated a new one, so that key is
> the Nessie of key ids. It's a crypto-cryptologist's dream, the true random
> collision. And we will never know if it was genuine. Sigh.
>
> Nonetheless, that led to that clause in 3.3, and I assert that if an
> implementation breaks because of a keyid collision, the implementation has a
> bug.
>
> So you can consider a keyid to just be a database key. The way we do it now
> (truncating a fingerprint) is a fine way to do it, but the underlying
> principle is that an implementor really needs to code around the eventuality
> that there will be a collision and do some right thing.
>
> Yeah, I know it's easier said than done, but that doesn't make it false.
>
> I forget what Terry Pratchett novel has it, but in one of them he has a
> discussion that anything that is a million-to-one against is a certainty.
> The million-to-one thing *will* happen. Cryptographers need to keep that
> principle in the back of their head, too.
>
>        Jon
> -----BEGIN PGP SIGNATURE-----
> Version: PGP Universal 2.10.0 (Build 554)
> Charset: us-ascii
>
> wj8DBQFNOFwGsTedWZOD3gYRAtyVAJ40VCHrrUkG2Dc+Bi7fKQA5VZlCeQCfRQVc
> Xs4TmguHftMh9uE/+b5Lqfw=
> =B98X
> -----END PGP SIGNATURE-----
>
>