Secure random password generation


Ideally you never use a password, but sometimes, you have to anyway. One very common scenario is in signing up for a web application. Such passwords can be stored on the server, hashed with a fast algorithm such as MD5, and over which you have no control. You do not want your password to be cracked at any point, even if an attacker obtained the hash database at some point via e.g. SQL injection. Or in another scenario, you need a password for full-disk encryption to be secure against fast offline brute force attack should your laptop/drive be stolen or covertly imaged.

If you have to use a password, the best way to create a secure one is not by trying to think up one yourself. Humans are notoriously bad at coming up with truly random data. Even if you start with a phrase or use 1337-speak, spell backwards, or capitalize your password, it might look secure, but it adds little randomness. Password crackers still routinely crack such passwords, and it is hard to be sure how secure your password is.

Many geeks proudly advocate XKCD's method of selecting a few common words, but as described, it only provides about 44 bits of entropy. This is secure against online brute force (550 years at 1000 guesses/sec). But in the common attacks described above (offline brute force) it quickly fails against most common cracking software, like oclHashCat, which can easily reach 1 billion guesses/sec on a single common computer. Indeed, if an adversary spent a little bit more effort, with an FPGA box, speeds of 18 billion keys/sec can be reached, which will crack the password in at most 16 minutes.

To be secure against offline brute force, you should generate a password you can demonstrate to have a bitlength resistant to brute force. The best offline brute force attack to my knowledge is somewhere around 64-72 bits, so you could use a bitlength of 80 bits (10 bytes), or if you want to be theoretically secure, you could use a bitlength of 128 bits (16 bytes). You could double XKCD's suggestion and use 8 random words, but that ends up being very long to type. Although not as memorable as a sequence of words, I prefer using a shorter string generated by encoding raw random bytes as base64. This is also easy to generate automatically if you need to generate a password in your scripts, and was the original motivation for this post. Here's an example of how you can generate a 20-character password with 120 bits of entropy in some common languages:

Powershell

$randomBytes = new-object byte[] 15
(new-object System.Security.Cryptography.RNGCryptoServiceProvider).GetBytes($randomBytes)
$password = [System.Convert]::ToBase64String($randomBytes)

Linux/Unix shell

head -c 15 /dev/random | base64

Ruby

require 'securerandom'
password = SecureRandom.base64(15)

Python

import os
import base64
password = base64.b64encode(os.urandom(15))

Java

javax.xml.bind.DatatypeConverter.printBase64Binary((new SecureRandom()).generateSeed(15));

Of course, it does assume your operating system or language's secure random bit generator does in fact securely provide random bits. For a variety of reasons, I still trust those more than any alternatives, even given the recent NSA revelations, but feel free to substitute another random bit generator if you'd like.

  1. #1 by Carson on October 6, 2013 - 11:03 am

    Hey,

    thanks for sharing. Inspired, I made my own in Erlang in a few minutes, you can post it as well if you want to:

    makepass() ->
    io:format(base64:encode_to_string(crypto:rand_bytes(15))).

    Its a full-fledged function, ready to be used in any module.

    Have a nice day.

    Carson

Comments are closed.