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 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.