How can Active Directory compare a users previous passwords when setting a new one?

Question

This is for a college assignment. At our College they use Microsofts's Active Directory to run their network.

Every month we get asked to change our passwords and when we do so it won't accept any of the previous five passwords we have used, or similar passwords. For example if my password was 'secretpassword1', next month I couldn't use 'secretpassword2'.

However the only way that I can see this being done is if there is either a flaw in the hashing algorithm used to store the passwords; the passwords aren't hashed but encrypted; or worse they are stored in plaintext.

After a quick Google-Fu session it appears that Active Directory will store passwords in regular Windows hashes. So can anyone explain this?

Cheers

P.S. This may be our imagination; perhaps you can reuse a password that is slightly different?

Answer 1

The old passwords are stored (in hashed format) in the AD database. As part of the password change process, this gets checked and/or updated.

Answer 2

It's easy to do if you generate the variants from the new password, not the old password.

Imagine an algorithm that takes a password, and generates a few hundred simple variants of it. So for an input like password1 it would generate the following variants:

PASSWORD1
PasSSword1
password2
password
P@aaW0RD2
....

and a few hundred others. (Note that one of those variants is "password".)

Password crackers have algorithms like these and use them against word dictionaries to generate guesses.

Using this algorithm, we can perform the following steps:

1. a user sets their first password to be "password". The system stores hash("password"), and uses this hash to compare whenever a user logs in.

2. Several weeks later, the user changes their password to "hunter2". The current password hash is changed to hash("hunter2"). hash("password") is stored in the list of N historical password hashes.

3. Several weeks after that, the user attempts to change their password to "password1". During this change attempt the following steps are performed.

3a) the new password is available in the clear, because the user just entered it. "password1" is used as input to the variant generation algorithm described above. A few hundred variant passwords are generated (in the clear).

3b) for each variant password, the hash of that password hash(variant) is calculated, using the salt for each old password. As noted above, one of the variants of "password1" is "password", so in our list of variant hashes we will have hash("password"). We end up with V variant hashes to test for each old password, V*N hashes total.

3c) The correctly salted version for each variant hash is tested against the current hash, and the previous hashes, for a total V * N binary array comparisons.

3d) One of the variant hashes is hash("password") and one of the stored N historical hashes is also hash("password"). These hashes match exactly, so the password is rejected.

This technique requires V*N hashes to be generated, where V is ~500 and N is ~10. This will only take a few seconds (even with PBKDF2, bcrypt or scrypt) and can be easily performed without disk access.

A note on salt: Changing the salt whenever you change the user's password (which you should definitely do) does make things a bit harder, but you still only need to generate a linear number of hashes, no matter how big your salt is.