Author's here. Reading the comments I feel like clarifying a couple of things :)
--- Clarification 1 ---
The goal of "hashing/reduction" step is to sort all possible passwords into M buckets. Then when a hint request comes in, we check if the typed-in password is in the same bucket as the one we have on file.
That's it.
One way to do this classification is described above. It is not the only way. One can take an MD4 of a string, extract the middle byte and call it a class ID. That would work as well (though it would require computing password "class" upon user registration, when the password is still in a clear). What we want is for related strings such as "password" and "passworf" to be in different classes, and this maps naturally to using cryptographic hashes.
--- Clarification 2 ---
The indicator pictogram has exactly two states - black and gray. The gray state is animated by randomizing its pattern to provide visual feedback on typing. It does not indicate if the currently typed password is "closer" to or "farther" from the target one. The gray always means just one thing - the password is invalid.
Thank you for clarifying, it makes a lot more sense now. I see how you could use bcrypt for actual authentication and some much faster method for hinting.
I think part of the confusion lies in the flow diagram, which maps "stored password hash" to "reduction". In your "class ID" example, what is the difference between the stored password hash and the reduction? What is the purpose of the stored password hash if you always reduce it the same way? Why not just store the reduction? I suppose you might employ a two-phase reduction process (one static and one dynamic), but is this really necessary? What is the advantage?
--- Clarification 1 ---
The goal of "hashing/reduction" step is to sort all possible passwords into M buckets. Then when a hint request comes in, we check if the typed-in password is in the same bucket as the one we have on file.
That's it.
One way to do this classification is described above. It is not the only way. One can take an MD4 of a string, extract the middle byte and call it a class ID. That would work as well (though it would require computing password "class" upon user registration, when the password is still in a clear). What we want is for related strings such as "password" and "passworf" to be in different classes, and this maps naturally to using cryptographic hashes.
--- Clarification 2 ---
The indicator pictogram has exactly two states - black and gray. The gray state is animated by randomizing its pattern to provide visual feedback on typing. It does not indicate if the currently typed password is "closer" to or "farther" from the target one. The gray always means just one thing - the password is invalid.