[openpgp] OpenPGPv4 long keyid collision test cases?

"David Leon Gil" <coruus@gmail.com> Fri, 13 December 2013 15:10 UTC

Return-Path: <coruus@gmail.com>
X-Original-To: openpgp@ietfa.amsl.com
Delivered-To: openpgp@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id DC2AF1AE309 for <openpgp@ietfa.amsl.com>; Fri, 13 Dec 2013 07:10:06 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.693
X-Spam-Level:
X-Spam-Status: No, score=-0.693 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, HTML_MESSAGE=0.001, SPF_PASS=-0.001, TRACKER_ID=1.306] autolearn=no
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 6ri_Hz3M1N2I for <openpgp@ietfa.amsl.com>; Fri, 13 Dec 2013 07:10:03 -0800 (PST)
Received: from mail-yh0-x229.google.com (mail-yh0-x229.google.com [IPv6:2607:f8b0:4002:c01::229]) by ietfa.amsl.com (Postfix) with ESMTP id D4CE31AE2FC for <openpgp@ietf.org>; Fri, 13 Dec 2013 07:10:02 -0800 (PST)
Received: by mail-yh0-f41.google.com with SMTP id f11so1554814yha.14 for <openpgp@ietf.org>; Fri, 13 Dec 2013 07:09:56 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:date:message-id:from:to:subject:content-type; bh=SWJ0bGEDiB9bd9wTkyiWs0nHtQY+ikaz3tPCcCj/5nc=; b=IV10gNvCs/EPsGgVAiQGvCOuTk2r7+IDh4PSw51Q4dCjN0VxoB346tvXUYSTwYSs87 HfZNsZ7N06s1jaTJ+XpnJ50s2Jt5fGfWBYmQtGYpc3y6rjbqowQjRpOCqRHgVssJzfAj JbfVW1ZGkjjAeBxwaaJY1XgBYp0m3rAJyK1HVH1448d38NWTCoPq5y5rwDxIjF4yt4tC FvrJ0TxvnQnTRtBJglO8miHvXRTtPq+DvLvoaxf7VVP0KbRGxM3Qh7EPpNs0P0m2+uyl Sb5ZFwNeFjuiVyQXOnvBERPaZKBTPJhBDUhbxeOxDtI2AJq/aX0YuTalJMX78C9lI/TH ikDA==
X-Received: by 10.236.74.73 with SMTP id w49mr2350632yhd.87.1386947396399; Fri, 13 Dec 2013 07:09:56 -0800 (PST)
Received: from [127.0.0.1] (ec2-54-235-159-173.compute-1.amazonaws.com. [54.235.159.173]) by mx.google.com with ESMTPSA id q9sm3374272yhk.16.2013.12.13.07.09.54 for <openpgp@ietf.org> (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Fri, 13 Dec 2013 07:09:54 -0800 (PST)
MIME-Version: 1.0
X-Mailer: Nodemailer (0.5.0; +http://www.nodemailer.com/)
Date: Fri, 13 Dec 2013 07:09:54 -0800
Message-Id: <1386947394098.1ce462e@Nodemailer>
X-Orchestra-Oid: A3585368-D800-488D-B2DA-70A3354DAE24
X-Orchestra-Sig: d35218fdb449df693fe47f2049f42726fd47e0a7
X-Orchestra-Thrid: 2CC1C56A-9B07-438F-B466-5CF568B63221
X-Orchestra-Thrid-Sig: 90c8b86650b00295cfe9e66f45916fe5e6c31cde
X-Orchestra-Account: 2e69a42e147f7448f0fa7f704338c45814ddae8d
From: David Leon Gil <coruus@gmail.com>
To: openpgp@ietf.org
Content-Type: multipart/alternative; boundary="----Nodemailer-0.5.0-?=_1-1386947394654"
X-Mailman-Approved-At: Fri, 13 Dec 2013 09:13:15 -0800
Subject: [openpgp] OpenPGPv4 long keyid collision test cases?
X-BeenThere: openpgp@ietf.org
X-Mailman-Version: 2.1.15
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: <http://www.ietf.org/mail-archive/web/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: Fri, 13 Dec 2013 15:12:34 -0000

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256


I recently needed a pair of OpenPGPv4 keys that collided on long key id. So far as I could tell, there aren't any test-cases around. (Maybe I'm missing something somewhere?)


In any event, I thought that developers of OpenPGPv4-implementing software might find these useful as test-cases for correct behavior in the presence of 64-bit key id collisions. (It's not clear to me, for example, that GnuPG's current behavior is correct, or its output particularly useful when faced with such a collision.)


(These have valid self-certifications of a UID, and so should be importable even by GnuPG.)




Fingerprint: 9E669861368BCA0BE42DAF7D *DDA252EBB8EBE1AF*


- -----BEGIN PGP PUBLIC KEY BLOCK-----


mQINBFJtd/UBEACpw/psXoGNM8RHczviD7FnGdjMQPEJQ+nuWQ2AEGYouulg5hFv
0ChuSQVLiqQht2k5K2liyW1MeXoJ8tr9nSn/Zi9nttc0Wo6K7pvrDD40r2HNg305
qLCzItr5st3x8cq2cIXvN4LOm2rqpBLZ/sqMmNiW2Y7/aAQqV1xtR35joHqamWHD
UPOmzBMs07YSUjXgC1EMx8kWQSV6cuARj93kxWj8R6eoYHHfrWCEGR313wov6QST
zIfVU7FqQqOmdLW3LaPHxcrI/TjsnkUN99qdlpjJH/YW925LDPJHAkliqPP5AvhU
F9KbY2F8mcIZBCDd8TH+xXynuN3BbIU4kCwVbdx/tcpO1npuJcKB1Go/udyow/Ei
Z3nHzJsCVkezvopek77wnwPaP0nAb7f4iIY3gJCoGirOx6N075TgF6MBe00q9oFE
y4rvnUnU9/QzOOes95eUMhM+9eK1cuLFEV5t47DfxRdq+fQip3FJ2l6v19sZvQ0G
j06pjYqg0of273rG8oXcDrFjb1Zqhj8x1mLl6u7d/ide5wTm9HylBWcYKQjIJJAi
WIScxEPIOINDJKgsKTuKtoyNvISJ3xUeS1yzxiIb3YGLIyPgFFx0vFyqJfbkXq70
m1n2xnJlkTidfzbZvc6EA7vRGSDYK6FqqhlGhc7UypUEVW8FM/jZNAOS6QARAUGt
tCg5RTY2OTg2MTM2OEJDQTBCRTQyREFGN0REREEyNTJFQkI4RUJFMUFGiQI3BBMB
CgAhBQJSg/uTAhsDBQsJCAcDBRUKCQgLBRYCAwEAAh4BAheAAAoJEN2iUuu46+Gv
+Z0P+wQhkLwm+WGcEsS98Lei9O7hit/k4g/VkLUUQV7BOR3n8uRZIFkdOtpvrFU3
aKf246uCy6GM48Oh+1U2cv5InX/WEuKaFo5uF6t79wyt18BUn1weDcU+DQdOSG4f
fSnNa55wkN0l0svW4fGIthjmDTz6HZFntYD+9A20wZAqpPIs+vyG9Jp+e9E9Y/W/
EFQbNlxHHb9+BMT2+DtNP+HSl3MPFlQPKOLZxyLAU5uzT0Sa0LxhrQy5FgkW6Jog
sbAJVM9z0pZw+grzGPciM66ZW1rxeICvbYsdWLytRjqxpY8GS8XudyseUGd+dZim
ptarsrE5yfSMg2gW5Z1PTc0tEMXJLUwtpyzQjpFpbb7dPuo2TUp09LgZKX63WCbS
Nb1RTaGfkeYudOTo2rh4Jfg+Tb/JRpO6clo0rxAq8nPH2WmG+9TB8Zbb7YRzGWuV
/e5SeVNR+zY8tXZKnmUIH1HIprc+BtT6Bupdvd0CT14Mg9MmsFvUXofwHLa4gahr
8/iG9y3uHSA6Rhz++yOpyOmNvO1LDxsYNaRCIXQJbqgNwF5YNYlMPsEeY/CG7FOb
Afv7rHiYtRRQfz2P4OF900DJO7QL9gdNXJ1+Hajy/5Lvvl7qwqMG4GvVQEsgFc5O
jjFCUhE2i20j2kEMxvA5RLBH/fOoGARn87tiKSfb+pqLNZQb
=fDJ8
- -----END PGP PUBLIC KEY BLOCK-----


Fingerprint: A55120427374F3F7AA5F1166 *DDA252EBB8EBE1AF*


- -----BEGIN PGP PUBLIC KEY BLOCK-----


mQINBFKD+38BEADSv5l4xOx9hCRJVcybq6yK5hTpGSFf3xo1bkhoMvyC62ehb4jD
MDLwwNRyzCBEWQJLbq/LLizPFN2qXFJpXJcsuqsHNYRtDqDBEjtriRQwSqHnqTXt
c0K46FYHldCJQ4/tBXxPI+WwtXjcNRWaV7n2BvR/Jk+B5e4Zz3LPnN0C4w5vORHs
hN1jil8A3Hs/F+OmlQYrU8ZtNwTpSo2EXxe2fVgSDCsKRyNsPZj++OyujPzW+yaN
lJ9I/q6s9gvX9o9o7nwZbqBETipWsdRK6RfBdTKpnyLNordbWwWTk6GxN8T5Ppit
P6a3UlQ71VuflcswCTmEQ1pEfZrlRFKa9psBOW+cZLNxT9h0jGFMh6/B3w48Sag+
cFcPBFWParC+cAXBIURDxT9G6bzNLogg7YKoaPsyiXnLDH2VJUCXs27D2wPJL24Q
S7npvsg63MPPssWgG5cauLznmNR4y5pQi6oH/C10v0zrUJy6FPJzQhYRhWOvhtz6
j88RGMrFNNCdB2VACtn699D+ixu3nRlXHIKCT+xLSfgslVYifmJOCNljBLGHOQ1e
FJxQuNVpmmxjvk/8kqK+pHLB9Qn6M1ZYzip7OyUL3OAWabCabgEw2bQmUhiBWD3u
buv0WAVOJEAFvBCAeYNQzrQMY+Rc3RnvynG4pI6Tbo8wC6/IJcDOw516JwARASB3
tChBNTUxMjA0MjczNzRGM0Y3QUE1RjExNjZEREEyNTJFQkI4RUJFMUFGiQI3BBMB
CgAhBQJSg/uTAhsDBQsJCAcDBRUKCQgLBRYCAwEAAh4BAheAAAoJEN2iUuu46+Gv
9L0P/3tFu0LOZ/dAPjUNfKJCZqcIuVnD5xShMTsUbVx+QoXMy7rt4iRLD7ofGi/I
vTAZehxk3sk/Slx5nbews+3NItyw6mcaP9HlmwKNr6k7BC2kJHcCxH4DNzhmIx1H
3T/CggtHX42JBYKlGf22y+M8jAbvsPOUfTznx96mYNrOY6s1dJyn0kRleqJ8+tGj
/5+0y90iZnGCa0FtacQkKUPkXwVodeZVxk8z5OEipShYKc+8dl+5WsvOzHqLC/KY
xCGRb4JaqEMwouLNg8dTNAXXUvFGqJNDX4+andggogmI1hdD9xExfSU9cAGegg2t
vvveC4S+CCHd+zt88iK5ze6F61RxwYhhNbkuFGjdgNGCpHtG/BQhKnYJuKEbq3oi
mgNyxJERlfgaWXveiMG0AmACXN+jCkTtqZjQnsg2N2QDL3tjY7usmuiwRL1aVOFG
Kw5/Cc+2nDeANS3Xi1403Ni269b1c6kNSoLe4zd0WsbO3Kouds8F8EQfeheXQe97
ZxuvBOMsR9wHC3f0sl/vfxCGdUC+khmKk5taKnUeUFJmVmh5ghlVy8FySHGB0QHO
zd8GUl59rFpQJNpNFQW2YKDhrcjxIr2AeJrdoDI6NsQ02+Qtep/bbq53hqtAD4jF
t3S8vBbTXtRk6g2qn4ojF4SOIc8SAiZcURgVFuSJX8ngFbO4
=OEw/
- -----END PGP PUBLIC KEY BLOCK-----


The keys, in binary form, will shortly be available at https://github.com/coruus/cooperpair


(Another few colliding pairs, somewhat less lovely, will also be available there eventually with the private key parameters, in case anyone would like to generate more complex test-cases; 64-bit issuer ids are used so commonly that I suspect it would be useful to test some edge cases that arise as a result.)


Apologies if this is otious and I am missing some obvious source of examples of these. (I noted many comments online that generating 32-bit preimages was 'embarassingly easy'; but no one seems to have bothered to make the time/space tradeoff.)


Cheers,


dlg


(Based on current AWS spot prices for a system similar to the one these were generated on, it costs << 0.05USD to generate 64-bit key id collisions. I arrived at the strategy used to generate these independently, but dkg suggested it in an earlier message on this list. Props, as the young folk today say.)
-----BEGIN PGP SIGNATURE-----


iQIcBAEBCAAGBQJSqyKgAAoJELU0F64QAAAArqoP/jaJX11UEcCG+mrVzyWHrX19RLdKbyWCsR65
FudC9mltMXDN9aZQmqOnfjbX3lAncyzpG8rbMJsh7d5D+sKEVdbeU7vVKbf5KlZLO061Bl54g6ee
1gKBBwOu2WeFHBX0AJgLeBMdvZWEZnOu+VkGcmbn2NYVk4ZXmQP0HtZcd7Iu3W2JBnJyrJSZUB9t
vGamu5YYJccsbsRwtoiQepS6VALFNtgSk+z39ySxCGGL3pUOGZExhPzW+3/TLmPwZCZfFKJG1H5p
rR/4kt4VVuRo8IZ30D9A5qwP5wlbHJhwH+iwJjh/vgKxnG0EWl9fnuEX3hF2fBXoD82zIWQjGIgK
IYARJVAk3rf2zJRLf0TPdx5X9XvyG0n1dc9DtSMfYD9RSHF2EIq40N1UxslDaKOhjbkm1tqFqalV
Gs2I6goJrRMDe79cHRZFYA4mSX96ElZXS3IyB+VG/VQQLJDGP5Z+q/NjqY/L27R0ltFSAasbWuMp
pCouHdXuQqfRD03FhllSlwRvF/rop58PqLec02/vRHZLAsb6wwzEGKyxh+cD0Bemt63FuGhBN4Se
WOCcDVUx9luIt90iKkIZvqZc7Wh74GPyqh76N6Y+88X2xefh+zoOdYd8pC2mzaZYW2wnansH4pX8
NtxsgVo092D9TXn4dbCsNy427CGiz/ah/y84zFHq
=m8t9


-----END PGP SIGNATURE-----



—
Sent from Mailbox for iPad