How to Store Passwords Safely?

Modern internet life makes passwords indispensable to everyone — operating systems have boot passwords (user passwords), apps have login passwords, and some even have transaction passwords. The sheer variety makes users’ heads spin: they either reuse less-than-robust passwords or have to depend on password-storage services such as 1Password. I often wonder whether there is a way to derive all passwords from a single master password, much like a Bitcoin BIP44 wallet derives its keys.

As it happened, this morning I read a Signal (an encrypted messaging tool) blog post, Technology Preview for secure value recovery), which describes how they use Intel’s SGX technology to create a “secure enclave” for safely protecting passwords. The post introduces a way to derive passwords:

1. Use the Argon2 algorithm to stretch the user password into a 32-byte key, stretch_key.
2. Using stretch_key as the key and “auth key” as the message, derive a temporary encryption key, auth_key, with HMAC-SHA256.
3. Using stretch_key as the key and “master key” as the message, derive part of the master key, partial_key, with HMAC-SHA256.
4. Use a cryptographic-grade random number generator to generate a 32-byte seed.
5. Using partial_key as the key and seed as the message, derive the master key, master_key, with HMAC-SHA256.

Once master_key exists, for any application we can derive the key it needs in a similar way. Thus, from a simple user password we generate a series of secure keys and ultimately a secure master key; then, much like BIP44, we can derive the password an application needs from the master key and a string describing that application.

In this process, the random seed used to generate the master key is crucial and must be saved, because creating or recovering any application password requires this seed and the user password to obtain the master key. So we need to store it, but storing it in plaintext greatly undermines security. Therefore we encrypt the seed with auth_key and store the result on disk for later use. The user password yields auth_key, which can decrypt the encrypted seed. The Signal blog post focuses mainly on how to use SGX technology to prevent brute-force attacks; for me that is not very actionable, but the password-derivation method was a real inspiration. So I modified the original algorithm slightly:

1. In addition to randomly generating the seed, randomly generate the salt Argon2 needs; store the salt and the encrypted seed together on disk.
2. All HMACs use Blake2s (Blake2s has SHA-3-level security, excellent performance, and built-in HMAC support).
3. Encrypting the seed with auth_key uses the ChaCha20 algorithm (one of TLS 1.3’s recommended algorithms, providing 256-bit security).

Then, with itching hands, I implemented a simple little tool in Rust: cellar.

Using cellar is easy. First initialize a cellar:

$ cellar init
Creating cellar "$HOME/.cellar/default.toml"
Password: [hidden]
Your cellar "$HOME/.cellar/default.toml" is created! Feel free to use `cellar generate` to create or display your application password.

This creates ~/.cellar/default.toml in your home directory, recording the randomly generated salt and the encrypted seed:

$ cat ~/.cellar/default.toml
salt = "C6TQW8joYp2XoIkvaCNfo0ihJ3OacxlTbx68_oW8pF4"
encrypted_seed = "bHn5Lu3yX0g68rRJ4lTOwAvx_uMDFaBnZ_WMkJSU8TM"

After that, you can use cellar generate to derive an application password:

$ cellar generate --app-info "user@gmail.com"
Password: [hidden]
Password for user@gmail.com: FLugCDPDQ5NP_Nb0whUMwY2YD3wMWqoGcoywqqZ_JSU

The entire codebase is only 220 lines and took me less than three hours (most of the time went into getting familiar with the documentation for a few libraries). If you’re interested, take a look at github.com/tyrchen/cellar. The current code is only an MVP; while security is fine, usability is still low. I’ll polish it gradually when I have time. If you want to try it right away, you can cargo install:

$ cargo install cellar

Of course, if your machine doesn’t have a Rust toolchain, install one first:

curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh

So far cellar has only been tested on OSX and CentOS; it should work on other platforms as well, though I’m not entirely sure.

Thoughts on Using Rust

Around May or June I led the team through a systematic study of Rust, after which I wrote the odd bit of throwaway code here and there. After reading Signal’s post, I could not contain my excitement — finally I could use Rust to build a tool that seemed to have some actual use! Overall, my impression is that Rust has expressiveness comparable to Ruby and performance comparable to C++ (if used correctly), plus a type system slightly inferior to Haskell’s but capable of crushing most mainstream languages, making coding in Rust a pleasure (except for the slow compile times). A small tool like this can be completed in about 200 lines (including unit tests, property-based tests, and a simple benchmark); I doubt it would be so easy to achieve with Python, Elixir, or Node.js.