Android KeyStore Encryption Scheme Broken, Researchers Say

The default implementation for KeyStore, the system in Android designed to store users credentials and cryptographic keys, is broken, researchers say.

The default implementation for KeyStore, the system in Android designed to store user credentials and cryptographic keys, is broken, researchers say.

In a an academic paper published this week, researchers argue that the particular encryption scheme that KeyStore uses fails to protect the integrity of keys and could be exploited to allow an attacker to modify stored keys through a forgery attack.

KeyStore, which performs key-specific actions through the OpenSSL library, allows Android apps to store and generate their own cryptographic keys. By storing keys in a container, KeyStore makes it more difficult to remove them from the device.

Mohamed Sabt and Jacques Traoré, two researchers with the French telecom Orange Labs, claim the scheme associated with the system is “non-provably secure,” and could have “severe consequences.”

The two point out in their paper “Breaking Into the KeyStore: A Practical Forgery Attack Against Android KeyStore,” that it’s the hash-then-encrypt (HtE) authenticated encryption (AE) scheme in cipher block chaining mode (CBC) in KeyStore that fails to guarantee the integrity of keys.

In a forgery attack, an attacker could exploit the weakness to reduce the length of symmetric keys protected by the system. The crux of the attack is based around tricking a victim into installing a malicious app on the device that can be granted read-write permission on the KeyStore directory.

For instance, if an attacker got an application to trust its symmetric key and transform 256-bit HMAC keys into 32-bit ones, a third party that controls the network could break any protocol based on the weak keys. The attack “lulls users into a false sense of security” by transforming the keys, undetected, the researchers say.

“The purpose of the forgery attack is that given a ciphertext of a symmetric key, the adversary can fabricate another ciphertext that decrypts to a shorter key,” the paper reads.

When the app asks KeyStore to generate a cryptographic hash function, or HMAC tag, over each message, KeyStore returns a weak key. Since the system refuses to store weak, short keys, it’s easy for a party to modify the content of those messages before forwarding them to a server.

Sabt broke down the scenario for Threatpost in layman’s terms on Wednesday:

“The scenario works as follows: An application generates a key for its own purposes. The malicious application cuts the key down using our forgery attack. Then, the application protects its data using the weak key. It sends its protected data to a synchronization server (or a cloud storage server). Naturally, the server does not have the key, so it cannot have access to the data. Later, the application tells the server that it needs its data. Here, an attacker can modify the data because they were protected by a weak key.”

Sabt understands why some may question the practicality of the attack; after all, a user would have to agree to install an app that requires KeyStore read/write permissions. What makes it an interesting attack, Sabt claims, is that in principle Android restricts access to the folder, meaning only the KeyStore user is allowed to see or modify its contents.

“The success of our attack depends on how likely the malicious application is to bypass the access control mechanisms of Android,” the two say, adding that this could be done by executing arbitrary code, through code injection or reuse, or obtaining root or kernel-level privileges.

According to the paper, the researchers have been able to carry out their attack on the latest Android build, android-6.0.1_r22 and that to their knowledge, it’s the first cryptanalysis-based attack against KeyStore.

“Intuition often goes wrong when security is concerned,” the two write, “Unfortunately, system designers still tend to choose cryptographic schemes not for their proved security but for their apparent simplicity. We show, once again, that this is not a good choice, since it usually results in severe consequences for the whole underlying system.”

The researchers caution the scenario is only an example, but stress a new “class of threat” could stem from the attack.

“In the paper, I only described one scenario exploiting the vulnerability concerning the KeyStore AE encryption,” Sabt told Threatpost, “However, experience shows that such vulnerabilities could be exploited in unexpected ways years after being discovered.”

Sabt, a PhD candidate working at Orange Labs and Traoré, a research engineer at Orange Labs, plan to present their research in Greece in September at ESORICS, the European Symposium on Research in Computer Security.

The two disclosed their research to Google in January and while the Android security team acknowledged the attack and confirmed the encryption scheme is slated for removal, Sabt claims that he hasn’t received an update from the team when exactly the fix will come.

The two recommend that system designers keep the hash-then-encrypt scheme but use it with another encryption mode, working alongside cryptographers to find the best option.

“A key lesson from this paper is that cryptographers and system designers must work closely together,” Sabt and Traoré write, “Bridging the perilous gap that separates these communities will be essential for keeping future systems secure.”

Like many Android systems, KeyStore does receive periodic updates from Google. Last year the company patched a privilege escalation vulnerability in the system that could have been abused if a malicious app called on a specific API in the system, something that could’ve led to memory corruption and code execution. In 2014, researchers fixed a nasty stack-based buffer overflow in KeyStore that affected most Android users. An attacker could have exploited the vulnerability in Android 4.3 and earlier devices to gain access to a device’s lock credentials, encrypted and decrypted master keys, and so on.

While Google has updated KeyStore with new features recently, Sabt and Traoré claim the company hasn’t reviewed the system’s “security correctness” and argue  that security by “feature-enhancing is disappointedly misleading.”

“Security in modern systems still does not withstand a simple cryptanalysis,” the two say, “Our attack demonstrates that any theoretical weakness concerning the security of a cryptographic scheme could be utilized to break the whole system.”

Researchers discovered a flaw in a popular mobile processor used in Android devices last week. Researcher Gal Beniamini described how the encryption in devices running Qualcomm chips, more than half of Android devices currently in use, can be bypassed. The KeyMaster module, a layer inside KeyStore designed to protect keys from extraction, is dependent on an environment powered by Qualcomm. In a write up, corroborated by Duo Security, Beniamini claimed attackers can reverse engineer code used by both.

Suggested articles

Discussion

Subscribe to our newsletter, Threatpost Today!

Get the latest breaking news delivered daily to your inbox.