4 ms·

>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 de

>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 10mo ago
>> 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 10mo ago
  >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 10mo ago
    They didn't personally attack you. They (correctly) attacked 64-bit identifiers.
    - upofadown 10mo ago
      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?
      - tptacek 10mo ago
        No, again, they were attacking 64-bit identifiers.
      - some_furry 10mo ago
        > 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-the-birthday-bound/ 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.
        amluto 10mo ago
        > 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.)

amluto 10mo ago

>> 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 10mo ago
>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 10mo ago
  They didn't personally attack you. They (correctly) attacked 64-bit identifiers.
  - upofadown 10mo ago
    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?
    - tptacek 10mo ago
      No, again, they were attacking 64-bit identifiers.
    - some_furry 10mo ago
      > 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-the-birthday-bound/ 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.
      - amluto 10mo ago
        > 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.)