32-bit (short ID) collisions: New milestone(?) reached

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

32-bit (short ID) collisions: New milestone(?) reached

Gunnar Wolf
Hi all,

For the full version, please read my post:

    http://gwolf.org/node/4070

In short: In Debian, we found two keys sharing the «9F6C6333» short
ID, sporting the same name in them, but one of them is *not*
recognized by the supposed owner. Not only that, this key is signed by
three keys (not (yet?) uploaded to the global keyring) B29B232A,
F2C850CA and 789038F2 — Those are also the three short IDs for the
keys signing the legitimate key.

There are several tools relying on this (now very) weak 32-bit scheme;
the first such tool we found was precisely the «PGP pathfinder & key
statistics» service, which fails badly: Even specifying the full
fingerprints, I do get three (absolutely fake!) trust path into the
impostor:

    http://pgp.cs.uu.nl/mk_path.cgi?FROM=AB41C1C68AFD668CA045EBF8673A03E4C1DB921F&TO=88BB08F633073D7129383EE71EA37A0C9F6C6333&PATHS=trust+paths

And the main reason I am writing this mail: SKS listings all show this
32-bit ID only. It does differentiate when keys collide on their short
keyids, but it promotes users using a weak representation; IMO we
should change SKS to show either long keyids or the full fingerprint.

Greetings,

_______________________________________________
Sks-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/sks-devel
Reply | Threaded
Open this post in threaded view
|

Re: 32-bit (short ID) collisions: New milestone(?) reached

Kristian Fiskerstrand-6
On 06/04/2016 12:43 AM, Gunnar Wolf wrote:
> Hi all,

..

>
> And the main reason I am writing this mail: SKS listings all show this
> 32-bit ID only. It does differentiate when keys collide on their short
> keyids, but it promotes users using a weak representation; IMO we
> should change SKS to show either long keyids or the full fingerprint.
>

You can't trust the output from keyservers for this data to begin with,
so at this point it is moot, you need to download the key in question
and perform your own calculation of the fingerprint as part of a
bilateral exchange of information out of band to validate the key.

PS, although the short keyid is used in listing, the 64 bit long keyid
is used for cross-references, this is a convenience factor and not
related to any security (as keyservers doesn't provide any, users have to)
--
----------------------------
Kristian Fiskerstrand
Blog: https://blog.sumptuouscapital.com
Twitter: @krifisk
----------------------------
Public OpenPGP certificate at hkp://pool.sks-keyservers.net
fpr:94CB AFDD 3034 5109 5618 35AA 0B7F 8B60 E3ED FAE3
----------------------------
"We all die. The goal isn't to live forever, the goal is to create
something that will."
(Chuck Palahniuk)


_______________________________________________
Sks-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/sks-devel

signature.asc (465 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: 32-bit (short ID) collisions: New milestone(?) reached

Christoph Egger-9
In reply to this post by Gunnar Wolf
Hi!

Gunnar Wolf <[hidden email]> writes:
> There are several tools relying on this (now very) weak 32-bit scheme;
> the first such tool we found was precisely the «PGP pathfinder & key
> statistics» service, which fails badly: Even specifying the full
> fingerprints, I do get three (absolutely fake!) trust path into the
> impostor:
>
>     http://pgp.cs.uu.nl/mk_path.cgi?FROM=AB41C1C68AFD668CA045EBF8673A03E4C1DB921F&TO=88BB08F633073D7129383EE71EA37A0C9F6C6333&PATHS=trust+paths

Moving this to full fingerprints is pretty high on my TODO list for a
while .. though old consumers seem to be pretty unhappy with any change
to the data so this needs fixing as well (the website being the only
exception). Hope I can get it done this summer ...

You shouldn't trust the data there fwiw .. the mining script doesn't
actually *check* any signatures and blindly believes what it says on the
envelope. Might change as well when I fix the collector but we'll see.

  Christoph

--
9FED 5C6C E206 B70A 5857  70CA 9655 22B9 D49A E731
Debian Developer | Lisp Hacker | CaCert Assurer

_______________________________________________
Sks-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/sks-devel
Reply | Threaded
Open this post in threaded view
|

Re: 32-bit (short ID) collisions: New milestone(?) reached

Kristian Fiskerstrand-6
In reply to this post by Gunnar Wolf
On 06/04/2016 12:43 AM, Gunnar Wolf wrote:
> Hi all,
>
> For the full version, please read my post:
>
>     http://gwolf.org/node/4070

This doesn't seem to reference the [evil32] keyring that seems to have
been [included in the public network], btw. Nothing new there and
irrelevant from a security perspective.

References:
[evil32] https://evil32.com
[included in the public network]
https://sks-keyservers.net/status/key_development.php

--
----------------------------
Kristian Fiskerstrand
Blog: https://blog.sumptuouscapital.com
Twitter: @krifisk
----------------------------
Public OpenPGP certificate at hkp://pool.sks-keyservers.net
fpr:94CB AFDD 3034 5109 5618 35AA 0B7F 8B60 E3ED FAE3
----------------------------
Qui audet vincit
Who dares wins


_______________________________________________
Sks-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/sks-devel

signature.asc (465 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: 32-bit (short ID) collisions: New milestone(?) reached

Gunnar Wolf
Kristian Fiskerstrand dijo [Sat, Jun 04, 2016 at 01:16:16AM +0200]:
> > For the full version, please read my post:
> >
> >     http://gwolf.org/node/4070
>
> This doesn't seem to reference the [evil32] keyring that seems to have
> been [included in the public network], btw. Nothing new there and
> irrelevant from a security perspective.

Yes, I saw that, and was intrigued not to find any suspicious matching
keys in the public network. I guess I didn't know how to look — Do you
have an example of keys coming from evil32?



_______________________________________________
Sks-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/sks-devel
Reply | Threaded
Open this post in threaded view
|

Re: 32-bit (short ID) collisions: New milestone(?) reached

Kristian Fiskerstrand-6
On 06/04/2016 01:26 AM, Gunnar Wolf wrote:

> Do you have an example of keys coming from evil32?

0xA6B2BBAD94C09C7F


--
----------------------------
Kristian Fiskerstrand
Blog: https://blog.sumptuouscapital.com
Twitter: @krifisk
----------------------------
Public OpenPGP certificate at hkp://pool.sks-keyservers.net
fpr:94CB AFDD 3034 5109 5618 35AA 0B7F 8B60 E3ED FAE3
----------------------------
Uxor formosa et vinum sunt dulcia venena
Beautiful women and wine are sweet venom


_______________________________________________
Sks-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/sks-devel

signature.asc (465 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: 32-bit (short ID) collisions: New milestone(?) reached

Kristian Fiskerstrand-6
In reply to this post by Gunnar Wolf
On 06/04/2016 12:43 AM, Gunnar Wolf wrote:
> There are several tools relying on this (now very) weak 32-bit scheme;
> the first such tool we found was precisely the «PGP pathfinder & key
> statistics» service, which fails badly: Even specifying the full
> fingerprints, I do get three (absolutely fake!) trust path into the
> impostor:

I'd like to take a bit of time to comment on this. The web of trust in
the abstract is all nice, but ultimately services such as the pathfinder
is only a tool to guide in how you can find a direct path. It is not a
replacement for actually properly configuring the trustdb and doing
(local) signatures of external keys that are to be used in the validity
calculation. So I fail to see an issue in this case, really, a simple
tool can be fooled, but the underlying model is sound.

--
----------------------------
Kristian Fiskerstrand
Blog: https://blog.sumptuouscapital.com
Twitter: @krifisk
----------------------------
Public OpenPGP certificate at hkp://pool.sks-keyservers.net
fpr:94CB AFDD 3034 5109 5618 35AA 0B7F 8B60 E3ED FAE3
----------------------------
"We can only see a short distance ahead, but we can see plenty there
that needs to be done."
(Alan Turing)


_______________________________________________
Sks-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/sks-devel

signature.asc (465 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: 32-bit (short ID) collisions: New milestone(?) reached

Jeffrey Johnson-5

> On Jun 4, 2016, at 4:44 PM, Kristian Fiskerstrand <[hidden email]> wrote:
>
> On 06/04/2016 12:43 AM, Gunnar Wolf wrote:
>> There are several tools relying on this (now very) weak 32-bit scheme;
>> the first such tool we found was precisely the «PGP pathfinder & key
>> statistics» service, which fails badly: Even specifying the full
>> fingerprints, I do get three (absolutely fake!) trust path into the
>> impostor:
>
> I'd like to take a bit of time to comment on this. The web of trust in
> the abstract is all nice, but ultimately services such as the pathfinder
> is only a tool to guide in how you can find a direct path. It is not a
> replacement for actually properly configuring the trustdb and doing
> (local) signatures of external keys that are to be used in the validity
> calculation. So I fail to see an issue in this case, really, a simple
> tool can be fooled, but the underlying model is sound.
>

I think that the effect of downloading a key with a collision in 32bits from an SKS
key server can be stated somewhat more simply/strongly (though I am sure
Kristian knows all this).

So a key, possibly the wrong key, possibly the wrong key(s) for an entire Wot
chain are downloaded from SKS key servers, all with collisions on 32bit keyid’s.

In order to verify, the issuer 8-octet keyid present in the signature packet is what
would typically be matched against the truncated digest of the key parameters: a mismatch
is identical to signature failure.

Comparing only 32bits of the issuer id in the signature, or assuming that the 32bit
retrieval id applies to a pubkey without actually verifying the digest, are rather broken
implementation(s) imho. But even if the signature verify is attempted
with the wrong (because of a 32bit collision) pubkey, the signature is not going
to match: the signature algorithms will surely fail (and if not, there’s a much
more serious problem than 32bit keyid collisions resulting in the wrong pub key
being used).

This also applies to the signatures in the entire WoT chain, assuming that the
signature(s) are verified. It may not be obvious why the signature’s are not
verifying because of the 32bit collision confusion, but the verify result will almost
certainly be a failure.

If the key retrieval is flawed (because of widespread use of 32bit keyid’s), there is
little likelihood of a false verification when the retrieved pubkey is used. There is
the risk of confusion and the possibility of broken implementations that do not
verify retrieved information: but that needs to be corrected in implementations imho.

hth

73 de Jeff




> --
> ----------------------------
> Kristian Fiskerstrand
> Blog: https://blog.sumptuouscapital.com
> Twitter: @krifisk
> ----------------------------
> Public OpenPGP certificate at hkp://pool.sks-keyservers.net
> fpr:94CB AFDD 3034 5109 5618 35AA 0B7F 8B60 E3ED FAE3
> ----------------------------
> "We can only see a short distance ahead, but we can see plenty there
> that needs to be done."
> (Alan Turing)
>
> _______________________________________________
> Sks-devel mailing list
> [hidden email]
> https://lists.nongnu.org/mailman/listinfo/sks-devel


_______________________________________________
Sks-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/sks-devel