Using HoneyWords to Catch Password Crackers

Dear Bitwarden Employees and Bitwarden Community,

As I am sure many of you know, Ronald L. Rivest is well known in the world of cryptography.

He is the creator of MD5 and MD6.

He is the ‘R’ in CLRS (Introduction to Algorithms).

He is the ‘R’ in RSA (Rivest-Shamir-Adleman). This very website has its root and Intermediate certificates signed using the RSA algorithm.

Ronald L. Rivest and Ari Juels both wrote an excellent paper on how to distinguish real users, password crackers, and simple failed login attempts (https://dspace.mit.edu/bitstream/handle/1721.1/90627/Rivest_Honeywords.pdf?sequence=1&isAllowed=y).

The idea of this paper “Honeywords: Making Password Cracking Detectable” is simple:

Have multiple accounts for a user–each entry with its own unique verification hash.

Rivest and Juels recommended to have at least 20 such fake accounts for each user.

After reading the paper, I have come up with the following password verification technique.

  1. When the user types in the username and password, the Bitwarden client app will

salt the user’s password with their username as salt using PBKDF2:

H_1 = PBKDF2(password || username)

Of course, this is meant to be a strong hash.

It should take at least 0.5 seconds and no

more than 1 second.

H_1 is sent to the server for verification.

Now, there are multiple fake accounts for each user–each with its own unique

verification hash.

Verification hashes use a simple message digest algorithm

for verification (e.g. SHA256 or BLAKE2b)

Let us call this Verification hash: V

This is fine since we already made the client do the tough computation,

H_1, beforehand.

How will the server distinguish between the fake verification hashes

and the real one for each user?

Using a message digest algorithm, hash H_1 with a cryptographically

secure salt. To do this easily, a table file should exist called

a salt table. In the salt table, a cryptographically secure salt

is mapped to each username formatted like this:

username | salt

So the second hash made in the verification process is:

H_2 = V(H_1 || salt)

All queries in the password database will actually be indexed using the

verification hash H_2–especially since multiple verification hash

entries for each username will exist in that password database table.

The server will find H_2 and check to ensure that the correct username

is mapped to H_2. If either H_2 is not found or the correct username

is not mapped to H_2, then obviously it is an incorrect login

and the user is denied access.

If both H_2 is found in the password database and it is mapped to the

correct username, then one more additional step needs to take place.

To tell if the specific H_2 queried for that user is the real hash,

the server should perform the following HMAC:

H_3 = HMAC(H_2 || salt_2)

I prefer using HMAC-BLAKE2b.

salt_2 can be found in the same password database entry as

H_2 for that user.

A separate table will be available–the HoneyChecker table–

that will have a full list of valid H_3 hashes.

If the server finds a hash in the HoneyChecker table

matches the H_3 hash recently computed–its the real

user. Otherwise, a password cracker was attempting to

impersonate the real user.

Summary:

  1. We have three tables necessary for verification:

Salt Table (Formatted Like This):

username | salt

  1. Authentication Table (Formatted Like This):

H_2 = PBDKDF2( ( H_1 = PBKDF2(password || username) ) || salt ) | username | salt_2

  1. HoneyChecker Table

H_3 = HMAC-BLAKE2b(H_2 || salt_2)

If the server fails to find H_2 mapped to the correct username, it is an incorrect login.

If the server finds H_2 but fails to find a matching H_3

in the HoneyChecker Table, a cracker was trying to get

access.

Please let me know what all of you think of this procedure.

I thank anyone for any responses they send back to me.

Hi @fosres!

Thank you for the detailed request! Based on some internal discussion, it may not be possible to feasibly generate honeywords that are equivalent to real passwords.

Some of that is based on this paper, which seems to indicate that the Rivest generation method may not be sufficient for this use-case, as well as some other issues with generating realistic decoy paswords.

But of course, if anyone has other thoughts, a healthy discussion is always good for those who enjoy hashing those things out :smiley:

1 Like

Hello Trey Greer,

Thanks for replying. I will look at the paper and respond if I have any more comments.

Have a happy New Year!

2 Likes

Thank you, you as well!

Well Trey Greer, I am now convinced you are right. Honeywords are actually not as effective as Rivest and Juels advertised. The paper you cited made that clear. All four of Rivest and Juels’ methods failed against Wang’s methods. Thanks for letting me know.

2 Likes