Securing private keys against brute force attacks on mobile devices

Question

I have a mobile application where I would like to store private keys securely. The security requirement implies that it should be very hard for attackers to be able to obtain the private key even if they had unlimited access to the mobile device. In order to achieve this level of security, the application employs symmetric cryptography with a key derived from a passphrase specified by the user and a salt specific to the device.

Ideally, this should be secure enough against a brute-force attack; however there a two limiting factors:

1. Since the private key must conform to a certain format, the decryption process can test the result of the process to see if it is valid or not. For example, if the private key was to be an RSA private key, the attacker would try various combinations of the passphrase and test to see if he can use the resulting plaintext as a valid RSA private key. Since the RSA private key must encode certain information in a certain way, if the decryption failed, the RSA engine would signal that the key is not valid. This gives the attacker a totally offline way of verifying his attacks. Preferably, the attacker should not be able to tell, without communicating with a server, if his decryption attempt was successful or not.

2. Since the application runs on a mobile device, the increased complexity of the Key Derivation Function does not help with Key Strengthening since an offline attack that has full access to the mobile device would presumably be undertaken on a more capable device with richer resources. Shortly, any increase in the number of rounds of calculation of the key derivation function would slow down the user experience (which acceptable to a certain limit) but would be immediately thwarted if the attack were to be performed on a desktop computer.

Could anybody offer me a solution to these problems? Specifically, does anybody know an asymmetric cryptography algorithm where the private key can be any random byte sequence (it could be fixed-length sequence, that doesn't matter), and the algorithm would still be able to produce ciphertext?

Answer 1

The private key for RSA is a fixed-length random byte sequence. You just happened to be looking at an ASCII encoding of it. Just store the key in a non-ASCII format and you should be good.

Answer 2

The security requirement implies that it should be very hard for attackers to be able to obtain the private key even if they had unlimited access to the mobile device.

That's just not possible.

Here's what an attacker can do:

1. Get the application in a state where the private key must be loaded in memory. Regular use of the application will cause this.
2. Dump the contents of the memory.
3. Slide through the memory bits trying all ranges of the known key length.

Since the key is in memory, it doesn't matter what clever scheme you came up with to generate it from pass-phrases and salts. Your application does all the work for the attacker. Classic case of failed security through obscurity.

This is how Blu-Ray was initially cracked. If the user has full access to a memory dump during application use, there's just no way to prevent them from getting the key this way.

Welcome to the world of DRM.

Answer 3

Modern symmetric ciphers are very resistant to known plaintext attacks. Where attacks have been discovered, they can require many plaintexts, and sometimes the plaintexts have to be adaptively selected.

Here, the attacker has a single, partial plaintext. I'd assume the workload to be essentially a brute-force search of the key space. If the symmetric key is randomly chosen from the entire keyspace, it is not feasible for an attacker to recover the private key from the ciphertext.

Indirect attacks are much more likely.

For example, something as simple as key-logging spyware is enough to defeat the best cryptography. Cold boot memory attacks or core dump analysis could be used too. These risks can be minimized by zero-izing secrets from memory immediately after use, but they can't be eliminated completely.

Since the key in this case is derived from a user-selected password, the effective key space is likely to be much smaller than the full key space. Mitigate that by requiring longer passwords that include all classes of characters. Also, don't discount key strengthening. Usual recommendations are for thousands of iterations of the key derivation function, but even if you can only afford a few hundred, that imposes a significant computation cost on an attacker.