How does Android L achieve strong encryption with a low entropy passphrase?

Question

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?

Answer 1

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.

Answer 2

I don't know if this is how Android does it, but a hardware-backed secure storage device can block repeated attempts that are made too quickly, making your assumption of 0.1 guesses per second invalid. Suppose it initially allows one attempt every 0.01 of a second, but it doubles the time between attempts with each failure after the first five. After a mere 50 attempts, you'll have to wait 250 thousand years before you can try again (and it will have taken you 250 thousand years to get this far). But as long as you can always enter your passcode correctly in 10 attempts or fewer, you'll never notice any delay.

Answer 3

Generation of a key and use of a pass-phrase is two different things. Keys, for example in asymmetric cryptography, are generated using entropy coming from the computer environment (like /dev/urandom, which might or might not be a good entropy source, but that's another debate). So the key itself has nothing to do about the pass-phrase. The pass-phrase will just be used to encrypt the key itself into a container designed to store the key.

If someone wants to decrypt you disk data, they need the key. Finding the key should be next to impossible in the right conditions. If done properly, breaking the encryption of the key container should be impossible as well without the key.

Regarding brute-forcing the key, it could in fact be a trivial operation if the attacker had access to the encrypted key-file, considering the low key-space. It's the device responsible to make that encrypted key-file not available to the attacker.

From your linked article I read:

Obtaining a raw copy of a disk partition is usually not possible on most commercial devices, but can be achieved by booting a specialized data acquisition boot image signed by the device manufacturer, exploiting a flaw in the bootloader that allows unsigned images to be booted (such as this one), or simply by booting a custom recovery image on devices with an unlocked bootloader (a typical first step to 'rooting').

These attacks, if not impossible, requires some investment (in term of time, or money). All security is a trade-off.

I also read:

Assuming that the implementation is similar to that of the hardware-backed credential store, disk encryption keys should be encrypted by an unextractable key encryption key stored in the SoC, so obtaining a copy of the crypto footer and the encrypted userdata partition, and bruteforcing the lockscreen passphrase should no longer be sufficient to decrypt disk contents.

Which should solve the latter problem.

Answer 4

I think the following four approaches more or less cover all possibilities for what could be done:

• Use an expensive (in terms of CPU time) key derivation function. However slowing down the attacker by any factor this way will slow down legitimate attacks by the same factor. And realistically the attacker will be able to use more CPU power than is present on a single mobile device, and the attacker can likely wait longer for an answer than what a user is willing to wait upon unlocking the device. As you have correctly realized, this approach requires more entropy than one million different possible passphrases could achieve.
• Use tamper resistant hardware. Put the key in a specialized piece of hardware which will limit the number of attempts to extract the key to a specified rate, and decrease that rate upon failed attempts. Possibly even destroying the key after a large number of failed attempts. This only works against an adversary who cannot take this hardware apart and extract the key from inside.
• Use an online service. If you have access to an online service, then that service could provide part of the computation needed and enforce a rate limit. A blinded RSA operation could achieve this without leaking any information about the key or the encrypted data to the online service. But not very practical, since the device might not have access to a network connection every time you want to unlock it.
• Use quantum memory. This is basically a variation of the tamper resistant hardware, but enforces the destruction of the key after a maximum number of attempts by relying on quantum physics. Also impractical, because I don't think anybody have successfully designed quantum memory which can hold data nearly long enough to use it for persistent data.

Of the above the tamper resistant hardware does sound like the most practical approach.