COMSEC: June 2007 Archives


June 13, 2007

Paul Hoffman asks (in comments):
Is this really easier than a dictionary attack after one unsuccessful attempt? I guess that this attack works when the APOP password is not in any attack dictionary or algorithm, but I would still like to see a comparison between the work effort for the attack and a very deep dictionary run. Note that the dictionary attack is *much* less likely to raise suspicions since there is only one failure, not many.

So, the first thing you need to realize is that this is a byte-by-byte attack. For simplicity, ignore dictionary attacks and assume that you have a 64-bit password. Searching that entire space takes, you got it, 264 operations (all offline). Now, say you mount the Leurent-Sasaki attack on only the last byte. This requires intercepting average 256 (worst case 512) connections and finding a collision for each of those connections. It seems to be a little hard to map the cost of finding a collision directly onto hash operations, but Luerent reports about 5 seconds per collision, so we're probably looking at order 100,000 (216) operations per collision, so this is something like (216) operations. But look what's happened here: we now know the last byte of the password, so we can mount a search on the remaining bytes. Searching the remaining bytes requires only 256 operations, compared to which 224 is negligible. So, we've reduced our computational complexity by around a factor of 256, admittedly at the cost of intercepting a lot more connections.

If we could extend this technique to the whole password we'd need to intercept about 8*256 connections and do about 8*227== 232 hash computations, so we'd have reduced the work factor by about a factor of two. However, as I mentioned in the original post, this technique can only be used to extract the last three bytes of the password. To make a long story short, Leurent estimates that with 8 character passwords with 6 bits of entropy per password this brings the work factor down to 230, a reduction of 218. This is obviously a big improvement.

Of course, this improvement depends on a fairly unrealistic assumption about the entropy of the password. In general, the lower the entropy, the more attractive dictionary search looks, and with typical passwords, it probably is better, especially when you factor in the negative effects of interfering with the user's connections.

UPDATE: Roy Arends points out that I apparently can't multiply and that 8*24==227. So, no breakeven point, like I'd previously suggested. I guess 8:00 PM must be past my bedtime. Fixed.


June 11, 2007

So, I'd been going around saying that the collision attacks against MD5 and SHA-1 were pretty useless against real protocols. At ECRYPT, Dan Bernstein pointed out to me that someone has actually used a collision attack successfully against APOP, an old challenge-response style protocol. The paper, by Leurent, is here (and rediscovered by Sasaki here).

The way that APOP works (like pretty much all challenge-response protocols) is that the server sends the client some challenge (a fresh value) M and the client sends back F(K,M) where K is the shared key and F is some function. In modern systems, people tend to like HMAC for F but APOP was designed before HMAC and in an era where people were pretty loose about hash functions. APOP computes the response as: MD5(M || K). This turns out to enable an attack, provided that the attacker can control the challenge.

The basic attack allows the attacker to determine one character of the password. Say he thinks the last character is C The attacker generates two colliding messages M1 and M2 with a special structure.

  • They are one hash block long.
  • The last byte of M1 is C.
  • The last byte of M2 is also C [fixed -- EKR]

So, we have:

  • M1 = xxxxxxxxxxC
  • M2 = yyyyyyyyyyC

Where X and Y are arbitrary and come out of the collision finding algorithm (actually, these are longer, but nobody wants to see 63 xs.).

The attack then requires the user to authenticate twice. The first time the attacker gives the challenge xxxxxxxxxx. This causes the user to return H(xxxxxxxxxx || P1 || P2 || P3 || ... Pn) where P1 is the first character of his password, P2 is the second, etc. The second time the attacker sends yyyyyyyyyy and gets back H(yyyyyyyyyy || P1 || P2 || P3 || ...). Now, here's the key point: these challenges have been specifically arranged so that the first byte (P1) of the password lines up with the last byte of the first hash block. If P1 == C then the two first hash blocks will collide. And since P2 ... Pn are the same, the entire hash output will collide. In other words, if the attacker has guessed C correctly, then the responses to these two different challenges will be the same. Otherwise they will not be (with high probability).

We've now extracted the first character of the password. That's not bad, but what about the rest? Well, it's straightforward to extend this once we know the first character. We build two new messages:

  • M1 = xxxxxxxxxP1C
  • M2 = yyyyyyyyyP1C
And we can repeat the same procedure extracting the password one character at a time.

This attack strategy has been known for quite some time and is originally due to Preneel and van Oorschot. However, the bottleneck was always that finding collisions was too expensive. The discovery of efficient paths for finding collisions changes that. If it's easy to find collisions, then this method becomes very practical.

Of course, "easy" is where things get complicated. There are two factors to consider here. The first is that it can be difficult to control the collision values, so you don't always get to choose that the last n characters of the colliding blocks are equal. Indeed, Leurent reports that he can only recover the first three bytes of the password. The second complication (and this applies only to APOP) is that in APOP challenges are RFC-compliant message ids, and the colliding blocks above most likely contain non-ASCII characters and so don't fit. Implementations which check for compliance are probably not vulnerable. However, Leurent reports that he's successfully mounted this attack on a variety of clients and it works, which isn't too surprising. Note that improved collision-finding techniques could lead to relaxation of both of these constraints.

The bottom line here is that if you're using APOP without TLS you should probably stop. On the other hand, if you're using APOP without some kind of encryption you should have stopped long ago...