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, 2^{64} 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 (2^{16})
operations per collision, so this is something like (2^{16}) 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 2^{56} operations, compared to which
2^{24} 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*2^{27}==
2^{32} 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 2^{30},
a reduction of 2^{18}. 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}==2^{27}. So, no breakeven point, like
I'd previously suggested. I guess 8:00 PM must be past my bedtime.
Fixed.
**

ekr,

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