This was a comment I posted on bcrypt-ruby/bcrypt-ruby#43 (before I realized that issue was 5 years old!) which got deleted so I moved it here.
Let's make the attack concrete to see if it works. I have a dictionary of 232 candidate passwords I want to try against a user account. I know the user's salt. There is no rate limiting. Ideally, it should take 232 online queries to search through all of my candidate passwords. Here's the attack:
- Using my knowledge of the salt, I hash ~216 random preimages until I find one for every possible 2-byte prefix of the hash.
- Now I send each of those 216 preimages in turn to the server and observe the side-channel. I may have to repeat this a few times in order to improve the SNR, let's say 100 times. So in 100*216 online queries I learn the first 2 bytes of the hash.
- Now that I know the first 2 bytes of the hash, I do 232 offline work to hash all of my candidate passwords a