Image of the glider from the Game of Life by John Conway
Skip to content

Checksums in Passwords? Uh, okay.

Introduction

As most of my readers know, I have a rather extensive yet easy-to-use web-based password generator. I've spent a lot of time doing password research (a couple ideas mine, most not), and have implemented most of these into the project. These include, but are not limited to:

  • Expansive language support
  • Verbal unambiguity
  • Visual unambiguity
  • Memorability
  • Compact density
  • Programmatic prediction
  • Versatility
  • Accommodating complex requirements
  • Entertainment
  • Checksums

That last idea was just recently committed to the project, and I think it might have some value, albeit with some tight controls and possibly little reward for the cost.

Bubble Babble

When I started developing my password generator, Tony Arcieri suggested on IRC that I implement Bubble Babble. I think he meant it mostly as a joke, but already being somewhat familiar with it having to do with SSH keys, I looked into it. Bubble Babble is an encoding specification designed for SSH fingerprints. The goal is to make the fingerprints pronounceable, such as when comparing host keys on first use. Antti Huima designed the specification, and built in a checksum to detect transmission errors. But for a password generator, I initially ignored implementing the checksum, and just implemented "xVCVC-CVCVC-...-CVCVC-CVCVx", where "C" is a random consonant from the spec and "V" is a random vowel also from the spec.

But then I got thinking, would it really be that big of a deal to implement Bubble Babble's checksum? Would it impact the character count for similar security margins? Would users even notice or care? It seemed obvious that the answer was to try it and see, so try it I did. For example, here is a Bubble Babble password before I implemented the checksum: "xuduh-taren-rezyd-gefik-bixux", and here's one after implementing the checksum: "xuval-zoder-cykeh-lyvin-lyrax". The former has approximately 78 bits of security, but the check will fail, while the latter has 72 with a valid check. Both are five pronounceable pseudowords.

However, the check isn't easily identifiable, as it's integrated throughout the entire string, and calculating the check is rather involved. One noticeable identifier is if Bubble Babble is encoding an odd number of bytes versus an even number of bytes. If the number of bytes is even, then the format of the string will have a third "x": "xVCVC-CVCVC-...-CVCVC-CVxVx". That doesn't mean that every even-numbered byte-encoded Bubble Babble string that has three "x"s has a valid check, but even numbered bytes with a valid check will have three "x"s. Regardless, stripping off the checksum isn't really a thing, due to being tightly integrated with the full string.

Okay. Now that it's implemented in Bubble Babble, is there any practical value to it? I could only think of one possible scenario.

A Scenario With Tightly Controlled Authentication

Suppose an organization has a credential management system (CMS) that requires employees to use their built in password manager and password generator. The password generator generates Bubble Babble passwords with valid checksums. When a new employee is hired and their account is setup, the CMS generates a random Bubble Babble password, hashes it, and stores it on disk for authentication. If at any point the employee wants to change their password, the CMS prevents them from supplying their own password, and they must use the builtin generator.

When staff authenticate, all client-side software checks the password for a valid checksum before sending it to the authentication server. If the check fails, the user has entered their password incorrectly, and must try again. If the check succeeds, the software sends the password to the authentication servers for hashing and verification.

The employee could attempt to bypass the client-side check by just sending the password to the authentication server directly, but it would be pointless as if verifying the password hash still fails at the authentication server, the employee still has to retype their password.

Okay, but why? Well, assuming the organization is using a best practice password hashing function with an appropriate cost factor, then authentication is expensive. People frequently mistype passwords and that cost on the server can be mitigated with client-side checksum validation.

But shouldn't users just copy-paste their passwords from the password manager? Absolutely yes they should. The most secure password is the one you don't know. However, there may be scenarios where pasting the password out of the CMS isn't practical, such as hooking up a crash cart to an unresponsive server or logging into your workstation when first getting into the office.

More Checksums

So if there is value here, are there other places where I've implemented a binary-to-text encoding scheme as a password generator that has a formally defined checksum in its specification? Yes, Crockford's Base32 and Bitcoin's BIP39.

In the case of Crockford's Base32, the checksum extends the base-32 character set to 37 characters, and the checksum is calculated modulo 37 against the bytes. It's rather trivial.

In the case of Bitcoin's BIP39, the bytes (which must be a multiple of 4 bytes) are hashed with SHA-256, and the leading bits of the digest are appended to the original entropy bytes to make the final bitstring a multiple of 11 bits, which is then converted to words and presented as a mnemonic, the final word being the "check word".

Screenshots

Below are some screenshots of the current state of affairs with the Bitcoin, Bubble Babble, and Base32 generators when at least 70 bits of security is required. The styling and such in each container might change as the project matures, such as "Integrated checksum" in the lower right-hand corner, but the checksum will remain.

Prior Work - Letterblock Diceware

While I did start thinking of this independently on my own, there is prior work that should be acknowledged. I just discovered it last night when doing web searches for password and passphrase generators with checksums. It was partly that discovery actually that lead to the creation of this post.

On August 12, 2020 Arne Babenhauserheide created Letterblock Diceware as an approach to physically and practically carrying Diceware with you. Unfortunately, Diceware ships 7,776 words with indices, and at best, this is several pages of printed paper with 5 dice, which isn't practical to carry around. So he created a 6x6 table of "pronounceable" and "memorable" digits, letters, and bigrams that can fit on a business card. Roll 2d6, one for the row the other for the column, and record the intersection for your password character. Four 2d6 rolls create a "block" worth about 20 bits of security. Four blocks produces about 80 bits of security as a result.

However, as a weak checksum, add the row numbers of two consecutive blocks modulo 4, and insert the resulting character between the two blocks. For example, if you rolled for two blocks as {col, row}:

  • {2,1}: A
  • {6,3}: t
  • {2,1}: A
  • {3,5}: U
  • {1,4}: 48
  • {2,1}: A
  • {2,4}: FK
  • {3,3}: N

Then your blocks are "AtAU" and "48AFKN" (or "4AFN" if you prefer). The rows however are "1, 3, 1, 5, 4, 1, 4, & 3". Adding these up modulo 4 returns (1+3+1+5+4+1+4+3) % 4 = 2, which yields "-" for the check. Thus, the resulting password would be "AtAU-4AFN" (I would have done modulo 6 instead. Then the check is uniform, and it could be printed as one more column on the card).

He also mentions the same scenario that I did in this post as well (emphasis mine):

Letterblock passwords use 55 letters that are unambiguous in handwriting and safe to use in URLs, grouped in blocks of four letters to make them easier to remember, with separators that work as weak checksum to catch many typing errors before even sending the password to the server, with weak optimization for legibility by creating 8 passwords and choosing the one with bigrams that are closest to regular prose.

It's worth noting that upstream Diceware also ships tables to be used with dice, although they're not designed for memorability.

Conclusion

There you have it. Three password generators in my web-based password generation project that now ship with checksums without reducing security or reducing the end user experience. I haven't made an actual release yet, as there is a bit more work I want to do prior to that. However, I'm sure there are other scenarios where passwords with checksums have value, as authentication is ubiquitous, and I couldn't possibly list every possible authentication scenario. Play around with it and let me know what you think. I would be very interested in your feedback.

Post a Comment

Your email is never published nor shared.