The Brewing Problem Of PGP Short-ID Collision Attacks

[phoronix]

Phoronix: The Brewing Problem Of PGP Short-ID Collision Attacks

Using short PGP key IDs is proving to be insecure with real attacks having started this summer...

http://www.phoronix.com/scan.php?page=news_item&px=Short-PGP-Collision-Attacks

[balouba]

One major issue is that the codebase of gnupg uses longids (so not shortids but not the full fingerprint either) everywhere instead of the full fingerprint.
I always wonder what the fuck they were thinking about/high on when they decided this was going to be a good idea.
This means that if you run any trust operation in gpg and the longid has seen a collision it may incorrectly trust the key (while with short ids, *you* can incorrect type/trust a shortid but gpg would not.. gpg uses a longid internally)

[Fry-kun]

Why not assign an english word to each quadruple hex segment, leading to a schema similar to https://xkcd.com/936/
Words are MUCH easier to read and compare by humans, even though the phrases would be mostly nonsense.
Similar words can be discarded; there are over 150k words in Oxford English Dictionary; it should be possible to get 65k non-similar ones

[starshipeleven]

Why not assign an english word to each quadruple hex segment, leading to a schema similar to https://xkcd.com/936/
Words are MUCH easier to read and compare by humans, even though the phrases would be mostly nonsense.
Similar words can be discarded; there are over 150k words in Oxford English Dictionary; it should be possible to get 65k non-similar ones

Uhm, I'm not sure about what you're saying here. Are you saying that instead of the gibberish 2575k3gvjhf2u4826r4t268 IDs it should output words?

Issue with words in crypto is that you open the door to dictionary attacks, so instead of increasing entropy you VASTLY reduce it, that comic assumes that cracking a password can be done only by brute-force and not with a dictionary of words to try (or to assemble).

[stikonas]

Uhm, I'm not sure about what you're saying here. Are you saying that instead of the gibberish 2575k3gvjhf2u4826r4t268 IDs it should output words?

Issue with words in crypto is that you open the door to dictionary attacks, so instead of increasing entropy you VASTLY reduce it, that comic assumes that cracking a password can be done only by brute-force and not with a dictionary of words to try (or to assemble).

It does not help dictionary attack at all. If every hex segment corresponds to one of the 65k words then the whole thing will have exactly the same entropy as hex fingerprint. It will be longer in words but probably easier to compare.

[Mystro256]

Uhm, I'm not sure about what you're saying here. Are you saying that instead of the gibberish 2575k3gvjhf2u4826r4t268 IDs it should output words?

Issue with words in crypto is that you open the door to dictionary attacks, so instead of increasing entropy you VASTLY reduce it, that comic assumes that cracking a password can be done only by brute-force and not with a dictionary of words to try (or to assemble).

Indeed.

Fry-kun The example in the xkcd comic is only really useful for imputed passwords. Normally you would have a key stored on your computer and the crypto software would handle it for you. Although you could protect the key with a password like that to add an extra layer of security.

[droste]

That's not what he was saying. The ID itself will not change with his system, only the representation.

Right now the key is a series of 1 and 0s. Every x (a group) of them are translated right now to a letter, number or something else so we can read it (so for display purposes). What he proposed is using larger groups and then translate to complete words instead of single letter, numbers, ... (for display only!).

This doesn't change the attack space reagrding cryptographie as you just change the visual representation. Another way would be do show a pattern of colors or something like that instead of letters, numbers, ... (though this would be not that good, because there are color blind people ;-)).

[starshipeleven]

(for display only!).

Yeah, that's what I was thinking too but I think what he said is unclear, if he is talking of public key IDs what he says is 100% fine as that's a public key anyway, otherwise it is not.

In general also that comic is so wrong on basic crypto that I tend to assume people posting it are also saying some atrocious blasphemy.

[Fry-kun]

I was only talking about the signature representation shown to the user (which is what the article is about).
The actual key would not change at all -- and I agree with GW, it's best to not show this to the user at all unless necessary. But when it IS shown, it would be a lot more helpful to show it in an easily readable format.
In fact, both hex code and the "word salad" can be displayed at the same time to the user -- she can pick what to look at.. but most users would probably choose the words

I only mentioned the comic because the way words are used and put together is similar to what I'm suggesting.

[Fry-kun]

This problem actually exists any time users are asked to verify a signature. How many of you compare just the first few and last few digits of md5/sha## sums?

Here's a contrived example based on the keys from the article (suppose someone matches first two and last two segments!):

Fake Linus Torvalds: ABAF 11C6 32D8 69AE E438 F74B 6211 AA3B 0041 1886
Real Linus Torvalds: ABAF 11C6 5A29 70B1 30AB E3C4 79BE 3E43 0041 1886

With a word salad approach:

Fake Linus Torvalds: lopsided crate threatening hydrant peep bumpy art work earth spurious
Real Linus Torvalds: lopsided crate symptomatic equal kaput chunky kettle include earth spurious

Even with an even-spaced font, it's hard to confuse the two



(random words from https://www.randomlists.com/random-words)