After upgrading to Android L on my Nexus 5, I was pleased to find that I can enable encryption using a pattern as the passphrase.

However, it soon got me thinking. I'm guessing the encryption key is ultimately derived from the pattern which is very low entropy. I did a back-of-the-envelope calculation and I found that the total number of unique patterns on a 3x3 grid of dots come to just under a million. Even at 0.1 guesses per second, it would take a mere 115 days to search the entire keyspace.

I started reading around and discovered a write-up detailing how Android does disk encryption. It seems to claim that Android L will use hardware-backed secure storage for storing and deriving the encryption key so it can essentially allow low entropy passphrases to still have the same amount of security.

However, I don't quite understand why. Why does using a hardware-backed secure storage device suddenly allow low entropy passphrases to acheive strong security? Am I just missing something blatantly obvious?

Chip-based banking cards typically use a 4-digit PIN. It would take at most a few hours to try them all if the card didn't protect against brute force attempts. The card protects against brute force attempts by bricking itself after 3 consecutive failures. The adversary does not have access to a hash of the PIN (there are physical protections in the card that make it extremely hard to read its memory), but only to a black box that takes 4 digits as inputs and replies “yes” or “no”. The key to security here is that the adversary can only make online attempts, not offline attempts. Each attempt requires computation on the defending device, it is not just a matter of doing the math.

An Android phone or any other computer can do the same thing with its storage encryption key. The key is not derived from the passphrase (or pattern), but stored somewhere and encrypted with the passphrase. Most storage encryption systems have this indirection so that changing the passphrase doesn't require re-encrypting the whole storage, and so that the storage can be effectively wiped by wiping the few bytes that make up encrypted key (the storage encryption key is uniformly random, so unlike a key derived from a passphrase it isn't subject to brute force: the adversary needs to obtain at least the encrypted storage key to gain a foothold).

If the adversary can read the encrypted storage key, then they can make fast brute force attempts on the key on a cluster of PCs. But if the storage key is stored in tamper-resistant storage, then the adversary is unable to read it and can only submit passphrase attempts to the device, so the device can apply policies like “limit the rate of attempts to 3 per minute” or “require a second, longer passphrase after 10 failed attempts”.

The new feature in Android L is upstream support for an encrypted storage key that isn't stored on the flash memory (from which it can be dumped with a bit of soldering or with root access), but instead in some protected memory (which may be accessible to TrustZone secure mode only). Not all phones running Android L have such protected memory however, and even if it's present, there's no guarantee that it's used for the encryption. All Android L changes is providing the requisite code as part of the basic Android image, making it easier for phone vendors to integrate.

Android provides an API to check whether the application keychain storage is in protected memory). I don't know if there's a corresponding API to check the protection of the storage encryption key.
