More on collisions and APOP

| Comments (1) | COMSEC
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.



8*2^24 == 2^27 and not 2^32

Leave a comment