Comment by some_furry | Hacker News Reader

Comment by some_furry | Hacker News Reader

Parent Full thread

> However this is only applicable if your friend is the one that is attacking... themselves.

> The only thing that matters here is 2nd preimage resistance, which still has 128 bits of security.

Nope.

Let's assume I have root on the Threema servers and have fully pwned their infrastructure, and want to substitute someone's public key to attack the app. (Remember: The minimum threat model for end-to-end encryption is that the server is evil.)

Alice pushes (3ma_id, pk) to the server, and chats with Bob legitimately. Bob suggests Alice talk to his drug dealer, Dave.

When Alice goes to talk to Dave, instead of (3ma_id, pk) the compromised server sends Dave (3ma_id, pk') where (SHA256-128(pk) == SHA256-128(pk')) and the sk that corresponds to pk' is known to the attacker.

In this situation, a visual inspection of the fingerprint will reveal nothing amiss. The QR code will still validate.

This attack can be leveraged in both directions to make Man-in-the-Middle possible, and the fingerprint mechanism will fail.

The full set of keys and substitutions here looks like this:

  Alice -> Bob:  (A_id, A_pk)
  Alice -> Dave: (A_id, M_pk1)
  Bob -> Alice:  (B_id, B_pk)
  Bob -> Dave:   (B_id, D_pk)
  Dave -> Bob:   (D_id, D_pk)
  Dave -> Alice: (D_id, M_pk2)

  SHA256-128(A_pk) == SHA256-128(M_pk1), A_pk != M_pk1
  SHA256-128(D_pk) == SHA256-128(M_pk2), D_pk != M_pk2

Now Alice's communications with Dave are tapped by a MitM (the attacker) and the fingerprint fails to stop it. And you only need a collision of a partial SHA-256 hash to pull the attack off. You don't need a preimage attack.

instead of (3ma_id, pk) the compromised server sends Dave (3ma_id, pk') where (SHA256-128(pk) == SHA256-128(pk'))

I can't see how the server can create pk' just with a collision attack in this case if pk is not controlled by them. Looks to me like they need a 2nd preimage attack.

But maybe I am just stupid.

I updated the article to describe it: https://soatok.blog/2021/11/05/threema-three-strikes-youre-o...

The attacker knows (pk, SHA256-128(pk)). They can generate another (sk', pk') where SHA256-128(pk') == SHA256-128(pk), but pk' != pk. This will cost an average of 2^64 key generations. Expensive, but feasible.

If you're law enforcement trying to catch international arms/drugs traffickers, and your suspects are using Threema, it's a valid attack strategy.

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).

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.

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.

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.

Reply on news.ycombinator.com