43

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?

  • 3
    It's worse than that - there are 389112 valid combinations -- some combinations are invalid because you can't skip over an adjacent dot (unless it's already been used. You can reduce the search space even farther by excluding "difficult" combinations that many people might not use. – Johnny Mar 4 '15 at 8:00
49

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.

  • 2
    I think you should clarify that the use of indirection also means that the main storage is always protected with a strong key even if the users password is something farcically bad. – Dan Neely Mar 3 '15 at 14:37
  • 1
    @D.W. Plenty of current high-end Android phones do contain tamper-resistant hardware. Whether that hardware is used for anything other than DRM keys is a different matter. I explicitly stated that the benefit is only in case that tamper-resistant storage is present and used, I've edited my answer to make this more apparent. – Gilles Mar 3 '15 at 19:05
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.

  • Only if the hardware-backed secure storage device uses tamper-resistant hardware and uses it for storing the filesystem encryption key (which is encrypted under the PIN and stored somewhere in persistent storage; if that's not stored in tamper-resistant hardware, an attacker with physical possession of the device can presumably dump it out). So, unless tamper-resistant hardware is involved somewhere, I don't think it's possible to block an attacker with physical control of the phone from dumping the contents of all persistent storage and then doing offline PIN guessing – D.W. Mar 4 '15 at 0:37
  • @D.W.: Well, the phrase "hardware-backed secure storage device" quoted in the question and again in this answer literally means "tamper-resistant hardware" – Ben Voigt Mar 4 '15 at 21:53
2

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.

  • 1
    This answer misses the point. Sure, the disk data is encrypted with some high-entropy encryption key K. However, knowledge of the PIN is enough to unlock the disk data (the legitimate software has a way to gain access to the disk data). Therefore, somewhere there's a copy of K encrypted under the PIN, stored somewhere on persistent storage. An attacker who dumps that plus the encrypted disk data can do offline PIN guessing. – D.W. Mar 3 '15 at 17:47
  • That's the point of the "unextractable key encryption key stored in the SoC" in the last quote. I did not detailed it as it seems quite straight forward. – M'vy Mar 4 '15 at 8:17
1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.