3 ms·

Just to verify that we are on the same page. Are you claiming that given spacific x (and thus also h(x)) for a cryptographic hash function with output length n

Just to verify that we are on the same page. Are you claiming that given spacific x (and thus also h(x)) for a cryptographic hash function with output length n bits you can compute a y so that h(x) = h(y) in time 2^(n/2) with a reasonable probability of success without controlling the value of x? If so I would love to see a proof of concept, because I would expect the time to be 2^n/2 = 2^(n-1).

some_furry 5y ago
No, I wasn't talking about a specific X, I was talking about any X. Sorry if I screwed up my wording. The collision attack step isn't targeted, but once you've generated more than the birthday bound of keypairs, the probability of a collision increases. Given that there are approximately 2^252 valid Curve25519 public keys, there will most likely be 1 other valid Curve25519 keypair that produces the same exact 128-bit hash output (given the algorithm of SHA-256). But once you find one of these, you can attack the fingerprints for those users.
- ttybird 5y ago
  Still though, in order for this to work you also need the specific key of one of their peers, so at the end of the day you still need a second preimage attack. And to be honest while I consider this as a silly decision on their part the fact that it can't be used as a targeted attack makes it relatively useless. Even tor until recently used 80-bit keys (which is much, much worse than the 128 that this app uses). You previously claimed that this will cost an average of 2^64 key generations, but this is just to find two pks that cause collisions in the 128 bit output space - two pks which most likely are not used by any of their users (which are what, around 2^20 atm?) I would be interested in an updated estimate of how long such a collision would take when keeping this in mind.
  - ttybird 5y ago
    To be more specific, I personally estimate that it will take around 2^108 attempts on average to find one such key, which is much more difficult compared to an aes128 batch attack.

some_furry 5y ago

No, I wasn't talking about a specific X, I was talking about any X. Sorry if I screwed up my wording. The collision attack step isn't targeted, but once you've generated more than the birthday bound of keypairs, the probability of a collision increases. Given that there are approximately 2^252 valid Curve25519 public keys, there will most likely be 1 other valid Curve25519 keypair that produces the same exact 128-bit hash output (given the algorithm of SHA-256). But once you find one of these, you can attack the fingerprints for those users.

ttybird 5y ago
Still though, in order for this to work you also need the specific key of one of their peers, so at the end of the day you still need a second preimage attack. And to be honest while I consider this as a silly decision on their part the fact that it can't be used as a targeted attack makes it relatively useless. Even tor until recently used 80-bit keys (which is much, much worse than the 128 that this app uses). You previously claimed that this will cost an average of 2^64 key generations, but this is just to find two pks that cause collisions in the 128 bit output space - two pks which most likely are not used by any of their users (which are what, around 2^20 atm?) I would be interested in an updated estimate of how long such a collision would take when keeping this in mind.
- ttybird 5y ago
  To be more specific, I personally estimate that it will take around 2^108 attempts on average to find one such key, which is much more difficult compared to an aes128 batch attack.