Wandering Thoughts archives

My standard for clear idioms in personal code

At least for personal code, I've decided that my standard for what I consider the clearest idiom for something is usually what first comes to mind when I try to write code to do the something. My idea here is that if a particular approach is what came to mind first when I tried to solve the problem, it is quite likely to be obvious to me what the code is trying to do when I reread it in the future because clearly this particular approach is what is on the top of my mind.

(The purpose of clear code is to communicate to future readers of the code what it does. For personal code, the future reader that I care most about is me.)

This does imply that what I consider the clearest idiom can change over time. This isn't just a matter of me becoming more familiar with a programming language or a library; sometimes it is because I don't always remember some algorithms and approaches all of the time, and what I remember clearly can shift.

For example, recently I wrote rounding up as 'nbits / 8 + !!(nbits % 8)' (as expressed in C). A commentator gently pointed out that this is equivalent to the shorter '(nbits + 7) / 8'. At the time I wrote the original code, the first version is what occurred to me. But now that I have been poked about it, the shorter version is in my mind; if it sticks, my clear idiom for doing rounding up will have changed.

(I will probably still be able to understand what my old code is doing, since the old version is still relatively clear and easy to reason through.)

Random passwords are not necessarily good passwords

I was recently writing a random password generator and in the process it occurred to me that there is an important difference between random passwords and good passwords, because we mean different things by those terms.

A truly random password is one that an attacker can't guess better than through random chance even if they know your password generation algorithm, so that on average they would have to try half of all of the possible passwords before successfully guessing yours.

(How many possible passwords there are is based on how many bits of information are in the password.)

However, a good password is a password that will not be found by an attacker that is trying common password patterns (or the password patterns that are feasible for them to brute-force). A truly randomly generated password necessarily has a chance to be a bad password, unless you took explicit steps to exclude the space of bad passwords from what your random process can generate (which reduces how many bits of randomness are in the password).

How likely is it that a randomly generated password will be a bad password? If you are using general enough categories, you can use the difference in the number of bits of information. For example, if our password generation alphabet is letters plus digits and we consider all-letter passwords to be too weak, then there's a four bit difference in the total bits and thus our truly random password generator has a one in sixteen chance of generating a bad password.

I suspect that the best way to get rid of bad passwords is not to try to tweak your random password generator to exclude them, because that may have hard to understand effects on how many bits of information its generated passwords really have. Instead I would check the generated password for badness and, if it is bad, generate another.

How many bits of information are in a password?

The number of bits of information in a password are a function of the alphabet that the password is drawn from and how many characters long it is. The formula is:

nbits = ceil(log2(len(alphabet)) * nchars)

So what does that mean? Let's take the case of 8 character long Unix passwords, and do a table:

(The version of 'all punctuation' I'm using is Python's, and has 32 characters.)

As we can see, conventional Unix passwords are not all that strong. Nor does lengthening them help a lot; at the most generous assumption, you need 20 characters to get a 128-bit password.

The same result can be applied to passphrases for SSH keys and the like. If your passphrase is lower case plus spaces, you have about 4.75 bits of information per character and you need 27 characters to get 128 bits.

(The number of bits of information in a password is how many bits of randomness it has and thus how many random bits you need to generate as strong a random password as you can get, and an indicator of how strong a cryptographic key it is.)

A suggestion for HMAC signature construction

Here is a useful safety tip if you are constructing HMAC signatures for structured messages, things that you want to parse later: put a format version number into either the key or the message.

If you want messages in the old format to fail signature checks so that the rest of your code doesn't have to deal with them, put the version number into the key. Put it into the message if you want your code to gracefully deal with several generations of message formats; each will still verify, but the messages label what format they're in.

You need to do this because otherwise your old messages, in the old message formats, still have valid signatures; after all, you signed them yourself earlier. (This is obvious once you think about it, but not necessarily before you do; I got lucky in some recent code I wrote, because when I changed the message format I also changed the key a bit.)

(This applies to any hashed signature approach in general, but why bother to reinvent the crytographic wheel? If you need hashed signatures, just use HMAC unless you have a really good reason otherwise.)