Doing key stretching right

While configuring my new laptop, I've recently spent some time thinking about my threat model and how full-disk-encryption fits in the picture. I came to the conclusion that I do need reasonable guarentees regarding protecting both the confidentiality and integrity of it but that I also depend on its availability (which didn't use to matter much to me). Translating the good old CIA triad into practical terms means that I do not want to be relying on the presence and good operation of my smartcard anymore to unlock my laptop.

Most people in my situation seem content with either entrusting their Full Disk Encryption keys to their TPM or using a very long passphrase and calling it a day. I am not one of them.

Both of these options suck. Trusting the TPM has repeatidely been proven to be a terrible idea (infineon rng bug but also extracting bitlocker keys from a TPM) and using exclusively a passphrase isn't an option either. I am convinced that attacks have become so cheap to conduct by the average attacker that we are on the wrong side of doable, no matter how "strong" one think his passphrase might be. First and foremost, the attacker may not be paying for the ressources he uses (depending on your own model: has access to a botnet or is getting the taxpayer to foot the bill), but even if he is, the econnomics are in his favour. Nowadays you can rent time on specialized hardware (GPUs of FPGAs), priced by the second, bidding on over-provisionned capacity directly from major cloud providers! I am looking at you AWS spot fleet instances!

This brings me to talk about something I see people do wrong time and time again: key stretching. The idea is simple, make offline bruteforce attacks against your secret as expensive as possible to a potential attacker. The tradeoff is obviously that you will have to commit resources to make this harder. How much resources depends on the algorithm and parameters you pick... but as you will probably find out, readily available tools are very far from using the state of the art.

Let's do a bit of history here and talk about the different options for storing authentication credentials and how they came to light, starting from the naive approach to what is currenty state of the art. Developers need support too highlights that decent information on the topic is hard to come by and isn't reaching its intended audience.

1. The most naive option is to store the password itself and just compare it when required. The attack is obvious: grab the password from the medium and use that.
2. The less naive approach is to hash the password using a cryptographically secure hash function. The attack there is to use precomputation and rainbow tables. To protect against that attack, people have started introducing salt: data that is unpredictable to the attacker and will be stored alongside the hash and mixed in as required. The attacker can't pre-compute anything anymore (since he doesn't know the salt in advance).
3. This has been good enough and worked well for decades, but Moore's law has ruined it, making the unpractical practical again (straight brute-force). The industry has adapted and solutions have involved key stretching algorithms. First generation algorithms like PBKDF2 (what's used by WPA for WiFi passphrases, but also by LUKS) were just iterating over the same "fast" hash function. This has quickly evolved towards slower hash functions like bcrypt and then pushing towards the same idea, hash functions designed specifically to be slow and resource intensive (both in CPU cycles and memory) like scrypt and more recently argon2id. Nowadays there is even a competition on who will come up with the least efficient scheme at https://password-hashing.net/.
4. These are great choices but we can do better than that. Fondamentally what you want is to prevent the attacker from parallelizing his attack and to do that, the best solution is to force him to use something he can't scale. Force him to attack it "online". Mobile phones do it right and have proven to defeat powerful attackers, so why shouldn't your laptop?

In part 2 we will explore how one can do it easily with a TPM.