DEADBEEF vs SHA1

[David Shaw <[e-mail]>]

Hi everyone,

I was thinking about Daniel Gillmor's proposal to include the complete fingerprint in signatures, and specifically this:

> But a devious attacker could potentially create a colliding Key ID (i
> believe collisions of the low 64 bits of SHA1 are within reach today,
> i'd love to be corrected if this is not the case) and cause the
> user-friendly MUA to assume it is in state B when it is actually in
> state A.  The attacker doesn't even need access to the message or
> signature in question to do this.  They'd only need to have been able to
> supply a key to the user at some time in the past.  (e.g. push a new
> subkey to the keyservers which a user pulls during a keyring refresh)

It occurred to me that it doesn't actually matter whether a 64-bit SHA-1 collision is feasible today or not.  There is a much easier collision that makes this attack trivial without going up against SHA-1 at all.

OpenPGP uses the 64-bit key ID to find the right key to verify a signature (via the issuer subpacket).  However that key ID doesn't have to be the lower 64 bits of the fingerprint like it is in V4.  In V3, it was the lower 64 bits of the modulus, which is trivial to set to whatever the attacker likes (i.e. the DEADBEEF key problem).  The problem is that the issuer subpacket doesn't differentiate between V3 and V4, so it's possible to make a DEADBEEF V3 key and use it to do a version rollback / denial of service attack against a V4 key.

For example, Alice's key (either V3 or V4) has a key ID of E435AEDF689E2211.  Mallory makes a V3 key, matches the key ID E435AEDF689E2211, and distributes it ahead of Alice.  Now any signatures that Alice issues will result in a "bad signature" error, since they will be verified against the wrong key.

To test, I made both Alice's and Mallory's key and tested with both PGP (9.10) and GPG (1.4 from git).  Basically, the attack works as expected.  Not surprisingly, once one key is imported, you can't import the other one without explicitly deleting the first.  When trying to import the second key, GPG fails with "key 689E2211 doesn't match our copy".  PGP silently ignores the new key.  Not allowing a new key to replace an old one does make some sense (after all, how would the implementation know which is "real" and which is "fake"?), but I can see this being a frustration.  Of course, this is a double-edged sword, since if Alice beats Mallory into the keyring, Mallory is locked out.

In terms of the issue that originally started this thread, the proposal to include and compare the complete fingerprint resolves this attack as well (slightly better in this case, in fact, since a V3 fingerprint can't even accidentally collide with a V4 one).

That said, however, (and switching over to implementation thoughts here) given how easy it is to make a V3 DEADBEEF key that collides with a real V4 key, I wonder if it would also be useful for implementations to simply refuse (or at least give the option to refuse) to import any V3 keys.  That might not have been feasible 10 years ago, but nowadays, I suspect most people would not even notice.  Standards-wise, that is fine as 4880 does not require V3 (discourages it, in fact: MUST NOT create, and only MAY accept).

I've pasted the test keys below if anyone wants to play with them.

David

p.s. the PKESK packet doesn't differentiate between V3 and V4 either but the attack is less obvious there - the victim would have to encrypt to the wrong key, and we at least theoretically have the means to discourage this via the web of trust.  It would still be an annoyance, though.

Alice:

-----BEGIN PGP PRIVATE KEY BLOCK-----

lQOYBE1b9LkBCADgluafn3zba/PMOZqlfNgma16vJ0lpZO9535NgJQEQulSLHzQx
vqoTRSF/KEGjzwWpPD1LLl0ZojeVAX6quGCM0n0wVncGU3TfurPpS9VB7/7R32gY
5eTgQqGx6pFY7KqReIYvIE5pkr5Dc8/eqZxOkQgzCFlH4h4itQqvo1TK35RpcUne
i0lHUEDaYySVYpIdAmOoMLgus5vU/bocwBfpo+GxdTkWtxoWY/4h/vY+lyO3r/qH
mDk9EddxAurR/TjtWe5INxuwXJIsGmmJDdFR7FJ1cAmsYLvF3QsH8qu/89zOZL9+
oV2vcVCPXoG+l0itmDrDY33rY9xP+rG2KL4XABEBAAEAB/0eVXisF0AnlBVnVbcZ
IkXrgoBVC0BeF3+aKA62uKjD1/bdR4dRhLK3TD9cS6qknlc3EWd8ml7WvH3iBplT
ePhewiXzJmqIad3qQ0RTfqY8yVZ92ufWHQ7kaft+6p4GXbN4AchV4HjWx4wifieV
p7ZF4k7c3a7Oslq8Tf7gfstQDyaDDO4d1fBWuE5C3roQI002zOm7XhtFCsc2ANK3
a7Lo1MGJHezacM6D+pNgUfpJaZnhtF6osXmO3ZRrqO47lgzN1K1HsiexvghmLC9r
GjupbOr5g9VFzuAey4SpQalXoL04Xm0rlmHRVdrCKQXeHVZ+MxkBw46GZ14UcjiD
6qSxBADvbwv2cx78Sb/BqS8anAICLcRDJ0rInVPoE/YIPs8GYaAwjXXlVQsFRWBc
rrH+pUZFHvvayKoXYPYtNO0za+1ZsRnFk6/uccasEHDai5bBrQNBgZ0vb/aHoqvx
i6LS3XVExKyb4220dyX7Azi6Q98SGKMQfnVbBLugCJqD66/laQQA8CDs2t+i10Ws
z6fAUWJems5RMJq9MktQ3jJ/CAkAuXrpxxX1EhhUZM8N9upPdzxY8Iwz0chHCcI4
PYrRNJVNIBH+HBDGFpBLqfcqkXMgUHJtIykD3sl37InQeHgSCP3QHgRF54bucOsu
SPdiO7CmyP5vZiZLza5oojPCLKFNl38D/jUuWOe676OJYZReR56jcq5wKGMGIkeE
jyhO8510c295kbGMWi+voVANaiLalY6YxY4VH2U+xO6CntZjNTZ2U+zuDDH5iywW
rhj+WrwreLewvosmGJ8nfBOIyjefM3DI5EC717L8PaIL730gFEGG5h65t6xbYYLB
b1un9f8zB3PiPzq0GUFsaWNlIDxhbGljZUBleGFtcGxlLmNvbT6JATgEEwECACIF
Ak1cKB8CGw8GCwkIBwMCBhUIAgkKCwQWAgMBAh4BAheAAAoJEOQ1rt9oniIRWSEH
/1bZWEjk/lQXElp81o7ERv/5RHo10bnbkoMl/QT0+5ROf9eaS1f3Vs5F2hMLSZoH
tPSWK6KBywijfFndLUIn2PdiisgPHRqv6cBg1gvfvJiYGdJQUQfJzEwFGyTgNviX
0CKDo8SiGDtrSH5IalnlZ1L0vZR8iTESQisOX5AlLTc45sDUnfWUmAddd+aQSKRu
1ZtWvgl3K/D4bMhFSenBXj4Ul0JekLZXPXBZbmf4zFrNUtzGsayksGq2qG4Z8F+f
BTcdozEV7V3k0sjlnS+s+uyaOPVT6Pui3n4oMV9XfEjCeJtjyg5j2xVqWFPSqvJA
6FZoXO7/Unul2mGfbY/Sg6M=
=cS7P
-----END PGP PRIVATE KEY BLOCK-----

Mallory:

-----BEGIN PGP PRIVATE KEY BLOCK-----

lQOaA01cLasAAAEIAOCW5p+ffNtr88w5mqV82CZrXq8nSWlk73nfk2AlARC6VIsf
NDG+qhNFIX8oQaPPBak8PUsuXRmiN5UBfqq4YIzSfTBWdwZTdN+6s+lL1UHv/tHf
aBjl5OBCobHqkVjsqpF4hi8gTmmSvkNzz96pnE6RCDMIWUf2ZZRTbUmnJGlWMW5N
0j4Kw95dG2cQQKFhhHT3PsP62iHrYP0P62cGCv5f9RwwNXpLS/c3hSpBTW44fr1j
qHtlDcOjdu4C2i/lqKOthQBjiW5scTl94Cn1HPr+xRwju8AJJ1e7jh5Y8k1SEYHG
wgWFHEVWplwIiajFMRPwpNvWkifJ5DWu32ieIhEAEQEAAQAH/A2L7JM6Ony9sTHj
U5mhwyPmHArykrIBvZQbUTdeZAcPRiQyGKLbfkS1ScTyt6raxNulX4kWXdU6/KFH
Os2vW1uDIrv0qy89f3IzP8DVqyJUCIm+MPg3fautOTWTEXtMoyktHOLgzvn9OO62
oJYsotn2U4lIeqIlkZD1y0TDCSY1SM7hT7Hhb2VDiwC0sD64wj1/WRBgBujcgl57
TrY+Px/mWWicdRawb6qPOicps6WuZULs0cgdf+tZxAdSZ5S7DJPNUtIrrG4grT1A
DIPDNUJy/ww5tp/E2wPDxji5JwVwEGXjn3cabHHa5fY8dslLfLNI736xEu8A//8A
AP//AAEEAO9vC/ZzHvxJv8GpLxqcAgItxEMnSsidU+gT9gg+zwZhoDCNdeVVCwVF
YFyusf6lRkUe+9rIqhdg9i007TNr7VmxGcWTr+5xxqwQcNqLlsGtA0GBnS9v9oei
q/GLotLddUTErJvjbbR3JfsDOLpD3xIYoxB+dVsQ2eQ1rt9oniIRBADwIOza36LX
RazPp8BRYl6azlEwmr0yS1DeMn8ICQC5eunHFfUSGFRkzw326k93PFjwjDPRyEcJ
wjg9itE0lU0gEf4cEMYWkEup9yqRcyBQcm0jKQPeyXfsidB4eBII/dAeBEXnhu5w
6y5I92I7sKbI/m9mJkvNt/AAAAAAAAAAAQQAkmUeSX+lSSVA2pBdjGN3KjNi/EdB
+bR9QJwFG8sRGAveAZ77FrqeLvKjEy8n7v87ahh1pLhgjH12VgR2h2giue9kY4t1
e1AeTBBk+SD8EDbOqFqMSoUtHA0MgOa97ErtOdA/yp05z1QfM+aCEufQSQLF1o/M
ml4rQaRVkf+k5QgyRbQZQWxpY2UgPGFsaWNlQGV4YW1wbGUuY29tPokBFQMFE01c
LavkNa7faJ4iEQECYS0H/1y57OK9C4iTvNl0KcSKvPfKMPikOMw8wCmY1sB0gYgg
nuPgsEMw64Hg/cG30JRBfcXZsaBviQ+nxijagBqeNf0zRMNzla1XIrtTWhD7fy0R
dYuAUZ8aIU4zwSYOHvgJraYG7rhRbKO3shlIQ+gfS6+toAz92OWC+IoYGGvEK1OL
owa0dzAkLCWI3nnT/MMkXUICpr+VlSI3u+iYKbK9WSFE9P3zCqdGkt+3LENQjV9z
c4VuyBUIqHuKU9krJxI7k6U3grYihq94oWYDEkTn8Q7KvGEygCnMdhFaeqtJZ3Ai
OA3548H3mkG3FAYemsC43l/Okn/3uz+xVrMJ4LgfxFk=
=ExMT
-----END PGP PRIVATE KEY BLOCK-----