[upofadown]

>And it wants to identify keys by 32-bit truncated hashes.

That's 64 bits these days.

>I should really not have to even think about the interaction between decryption and verification.

Messaging involves two verifications. One to insure that you are sending the message to who you think you are sending the message. The other to insure that you know who you received a message from. That is an inherent problem. Yes, you can use a shared key for this but then you end up doing both verifications manually.

[amluto]

>> And it wants to identify keys by 32-bit truncated hashes.

> That's 64 bits these days.

The fact that it’s short enough that I even need to think about whether it’s a problem is, frankly, pathetic.

> Messaging involves two verifications. One to insure that you are sending the message to who you think you are sending the message. The other to insure that you know who you received a message from. That is an inherent problem. Yes, you can use a shared key for this but then you end up doing both verifications manually.

I can’t quite tell what you mean.

One can build protocols that do encrypt-then-sign, encrypt-and-sign, sign-then-encrypt, or something clever that combines encryption and signing. Encrypt-then-sign has a nice security proof, the other two combinations are often somewhat catastrophically wrong, and using a high quality combination can have good performance and nice security proofs.

But all of the above should be the job of the designer of a protocol, not the user of the software. If my peer sends me a message, I should provision keys, and then I should pass those keys to my crypto library along with a message I received (and perhaps whatever session state is needed to detect replays), and my library should either (a) tell me that the message is invalid and not give me a guess as to its contents or (b) tell me it’s valid and give me the contents. I should not need to separately handle decryption and verification, and I should not even be able to do them separately even if I want to.

[upofadown]

>The fact that it’s short enough that I even need to think about whether it’s a problem is, frankly, pathetic.

Please resist the temptation to personally attack others.

I think you mean that 64 bits of hash output could be trivially collided using, say, Pollard's rho method. But it turns out that simple collisions are not an issue for such hashes used as identities. The fact that PGP successfully used 32 bits (16 bits of effort for a collision) for so long is actually a great example of the principle.

>...encrypt-then-sign, encrypt-and-sign, sign-then-encrypt...

You mean encrypt-then-MAC here I think.

>...I should not even be able to do them separately even if I want to.

Alas that is not possible. The problem is intrinsic to end to end encrypted messaging. Protocols like PGP combine them into a single key fingerprint so that the user does not have to deal with them separately. You still have to verify the fingerprint for people you are sending to and the fingerprint for the people who send you messages.

[tptacek]

They didn't personally attack you. They (correctly) attacked 64-bit identifiers.

[upofadown]

They were attacking an entire community. Perhaps I should have complained about being deliberately provocative.

But to the point, how long should something like a key fingerprint be?

[some_furry]

> How long should something like a key fingerprint be?

At least 128 bits for most threat models. 192+ is preferable for mine.

https://soatok.blog/2024/07/01/blowing-out-the-candles-on-th...

My threat model assumes you want an attacker advantage of less than 2^-64 after 2^64 keys exist to be fingerprinted in the first place, and your threat model includes collisions.

If I remember correctly, cloud providers assess multi-user security by assuming 2^40 users which each will have 2^50 keys throughout their service lifetime.

If you round down your assumption to 2^34 users with at most 100 public keys on average (for a total of 2^41 user-keys), you can get away with 2^-41 after 2^41 at about 123 bits, which for simplicity you can round up to the nearest byte and arrive at 128 bits.

The other thing you want to keep in mind is, how large are the keys in scope? If you have 4096-bit RSA keys and your fingerprints are only 64 bits, then by the pigeonhole principle we expect there to be 2^4032 distinct public keys with a given fingerprint. The average distance between fingerprints will be random (but you can approximate it to be an order of magnitude near 2^32).

In all honesty, fingerprints are probably a poor mechanism.

[upofadown]

>...and your threat model includes collisions.

OK, to be clear, I am specifically contending that a key fingerprint does not include collisions. My proof is empirical, that no one has come up with an attack on 64 bit PGP key fingerprints.

Collisions mean that an attacker can generate two or more messaging identities with the same fingerprint. How would that help them in some way?

[amluto]

> attacker advantage of less than 2^-64

Why so high? Computers are fast and massively parallel these days. If a cryptosystem fully relies on fingerprints, a second preimage of someone’s fingerprint where the attacker knows the private key for the second preimage (or it’s a cleverly corrupt key pair) catastrophically breaks security for the victim. Let’s make this astronomically unlikely even in the multiple potential victim case.

And it’s not like 256 bit hashes are expensive.

(I’m not holding my breath on fully quantum attacks using Grover’s algorithm, at high throughput, against billions of users, so we can probably wait a while before 256 bits feels uncomfortably short.)

[tptacek]

No, again, they were attacking 64-bit identifiers.

[amluto]

> I think you mean that 64 bits of hash output could be trivially collided using, say, Pollard's rho method. But it turns out that simple collisions are not an issue for such hashes used as identities.

No. I mean that 64 bits can probably be inexpensively attacked to produce first or second preimages.

It would be nice if a decentralized crypto system had memorable key identifiers and remained secure, but I think that is likely to be a pipe dream. So a tool like gpg shouldn’t even try. Use at least 128 bits and give three choices: identify keys by an actual secure hash or identify them by a name the user assigns or pass them directly. Frankly I’m not sure why identifiers are even useful — see my original complaint about keyrings.

>> ...I should not even be able to do them separately even if I want to.

>Alas that is not possible. The problem is intrinsic to end to end encrypted messaging. Protocols like PGP combine them into a single key fingerprint so that the user does not have to deal with them separately.

Huh? It’s possible. It’s not even hard. It could work like this:

$ better_gpg decrypt_and_auth --sender_pubkey [KEY] --recipient_privkey [KEY]

Ciphertext input is supplied on stdin. Plaintext output appears on stdout but only if the message validates correctly.

[upofadown]

>I mean that 64 bits can probably be inexpensively attacked to produce first or second preimages.

Keep in mind that you would have to generate a valid keypair, or something that could be made into a valid keypair for each iteration. That fact is why PGP got along with 32 bit key IDs for so long. PGP would still be using 32 bit key IDs if it wasn't that someone figured out how to mess with RSA exponents to greatly speed up the process. Ironically, the method with the slowest keypair generation became the limiting factor.

It isn't like this is a new problem. People have been designing and using key fingerprint schemes for over a quarter of a century now.

>$ better_gpg decrypt_and_auth --sender_pubkey [KEY] --recipient_privkey [KEY]

How do you know that the recipient key actually belongs to the recipient? How does the recipient know that the sender key actually belongs to you (so it will validate correctly)?