# Can an adversary distinguish a private key from a pseudo-random string of the same length?

Apologies if this is a dumb question but allow me to describe the dilemma I have:

Suppose that I am protecting a private key on a device using a password & PBKDF2. The obvious attack would be an offline bruteforce by which an attacker would know the password used to protect the private key and would also have access to the private key.

For a very important & undisclosable reason, the password used to protect this private key has a small search space i.e. it is not complex and is of a short length.

The controls I have in my mind are:

1. Have the key pair generated on the device but send the public key to the backend. The public key will not be stored on the same device as the private key. This will mitigate the bruteforce attack as the attacker would not know if the decrypted blob is the private key without being able to correlate it to it's corresponding known public key. (Hope that makes sense)
2. Encrypt just the private key using PBKDF2 and provide no "Known Plaintext" to the adversary like -----BEGIN RSA PRIVATE KEY----- or -----END RSA PRIVATE KEY-----
3. The private key is used to generate a signature which is verified by the back end and this will have limited attempts thereby mitigating an offline attack
4. I will be using a salt and a slow derivation function

My hope is (and I could be wrong) is that the attacker would not be able to distinguish such a private key from other pseudorandom blobs received after decrypting it using various password attempts in a bruteforce attack. Am I correct in my understanding? Am I missing some fundamental mathematical understanding in the RSA cryptosystem or any asymmetric cryptosystem that debunks the above controls? I wish to understand if the distinguishability of a private key from a pseudorandom string (of the same length) is close to negligible.

• Have you thought about generating the private key from scratch everytime (using a key generation algorithm with the derived password hash as random seed)? – Daan Bakker May 20 '16 at 12:57
• Hi Daan, yes I did give it a thought but later discounted it as this would be a non-standard approach and also that getting this to work with RSA becomes more difficult. Is this what you mean? - crypto.stackexchange.com/questions/1662/… – Balthazar2012 May 20 '16 at 14:56
• Ok. Yeah that's what i meant. – Daan Bakker May 20 '16 at 18:39

Usually choosing a safe password and standard parameter for the PBKDF2 key derivation would be enough protect your cipher. If PBKDF2 is correctly used, the symmetric key you get as output is well generated and attacking the ciphertext is infeasible.

Protecting a private key as you're doing is a standard operation, usually the password is used (in PBKDF2) to generate a symmetric key which is used with a symetric algorithm (let's say AES) to protect your precious private key. AES is supposed to be secure even if an attacker is given access to a decryption oracle (i.e.: it can get decryption of every ciphertext he wish but yours, the challenge). So modifiing the plaintext (stripping the header) would not improve the security level.

After your edit. Let's imagine that someone saw almost all your password while you were typing it or know that it is included in a relatively small set.

You said that you would strip the "-----BEGIN RSA PRIVATE KEY-----" string, that means that the key is in PKCS#1 standard, so what you keep is a base64 encoded string corresponding the following DER structure:

RSAPrivateKey ::= SEQUENCE {
version           Version,
modulus           INTEGER,  -- n
publicExponent    INTEGER,  -- e
privateExponent   INTEGER,  -- d
prime1            INTEGER,  -- p
prime2            INTEGER,  -- q
exponent1         INTEGER,  -- d mod (p1)
exponent2         INTEGER,  -- d mod (q-1)
coefficient       INTEGER,  -- (inverse of q) mod p
otherPrimeInfos   OtherPrimeInfos OPTIONAL
}


(source)

So, an attacker could try to check for the value of $e$ (usually a standard value among 2 or 3) or check if $p \times q = n$, or ... So even if, in theory an RSA key is just a couple of integers, it is usually stored in a well known structure helping the attacker to recognize what he has found.

• Thanks for your response. Let me make the question a bit more difficult by stating that the password has a small search space. I'll update my question accordingly. – Balthazar2012 May 20 '16 at 9:46
• Thank you for the updated response. Makes sense and I agree. I guess this would also be applicable to other asymmetric cryptosystems like El Gamal, elliptic Curve too? – Balthazar2012 May 20 '16 at 10:49
• As thumb rule I would consider that if an attacker can guess (or retrieve) the secret key, the plaintext is completely understood. The mitigation you suggested in your question could save you from a not-so-determined attacker. I'd say that every thing we use on a computer has a particular structure that can leak some information. – ddddavidee May 20 '16 at 10:55
• One last question - Are there RSA implementations that do not use the Chinese remainder theorem to speed up the calculation? I am almost certain there won't be any as it would make the RSA computation slower. However, if there was an implementation that uses mod n instead of mod p & mod q, then only d & n would be stored as the private key. I think this wouldn't leak any information as the adversary would not know p,q to check if d corresponds to a guessed e. Your thoughts? – Balthazar2012 May 20 '16 at 11:47
• I think that if you control the implementation of the decryption/encryption function you can achieve something... you may strip some constants from the structure above, or replace them with random numbers (which are not used during decryption) or maybe even scramble the structure with a permutation you control. – ddddavidee May 20 '16 at 15:49

To basically summarize Ricky Demer's answer, regardless of how "random-looking" your private key is, an attacker can always recognize the correct private key as long as they have access to at least one of the following:

1. the public key,
2. both the ciphertext and the plaintext of a message encrypted using the public key, or even
3. only the ciphertext, as long as the plaintext is recognizably non-random.

As long as the attacker has access to at least one of these, they can test each candidate private key simply by trying to decrypt a message using it, and seeing if the decryption is successful and the resulting plaintext looks correct.*

To prevent this type of attack, you would (among other things) have to keep the public key hidden from the attacker — which would make it no longer public, and thus defeat most of the benefits of using public-key crypto in the first place. About the only situations where I could see this making any sense at all would be as part of a "defense in depth" strategy, or perhaps in a scenario involving two distinct types of attackers with different capabilities and goals, with only one type having access to the "public" keys.

In any case, if you did want to make your private keys indistinguishable from random, the easiest way would probably be if you did not store the private key at all, but instead stored a random seed value from which the private key could be deterministically derived. Of course, this would be easier if, instead of RSA, you used some other public-key encryption scheme with a simpler key generation process, such as ElGamal or IES.

*) As Ricky Demer notes in their answer, the ciphertext-only attack scenario could potentially be defeated or at least mitigated by a hypothetical public-key encryption scheme that was specifically constructed to yield plausible-looking random fake plaintext when decrypting with the wrong private key. Constructing such an encryption scheme would be difficult, however, and it would have to be tailored to a specific application; no general-purpose encryption scheme can have such a property, since what constitutes random plausible-looking plaintext must necessarily depend on the nature of data being encrypted, and the attacker's prior knowledge of it. In any case, no standard general purpose public key encryption scheme like RSA has this feature.

I'll start with a point corresponding to ddddavidee's edit: ​ If there exists a PKE scheme,
then there exists one for which private keys can trivially be distinguished from randomness.

Just modify the key generation algorithm to append so that the new private keys end with length(original_private_key) zeros, and modify the decryption algorithm to ignore those.

another thing: ​ If there exists a PKE scheme, and the adversary does
not have the "public" key but decryption needs that too, then the
private keys can easily be made indistinguishable from random.

Just have the new public keys also include a symmetric key and have the
new decryption algorithm start by using that symmetric key to decrypt
the "private key" under a scheme with pseudorandom ciphertexts.

possibly useful to you: ​ If the adversary does not have the "public" key and
decryption does not use the public key and the adversary does not have
"a vector of encryptions ... encryption of the private key]]"
as described below, then I have no clue.

There could be some PKE scheme such that
decryption does not use the "public" key and
the scheme retains honey encryption's security against adversaries with
the encrypted private key but neither the "public" key nor the password.

Main Result:
If the adversary has (the public key or) a vector of encryptions of [a vector of plaintexts
which the adversary has an efficient way of testing that's somewhat reliable against
[guesses given just the public key and the length of the encryption of the private key]],
then what you seem to be after is impossible.

(If the adversary has the public key, then the adversary can get such a vector by just picking
a long random plaintext and encrypting it.) ​ One can try predicting the plaintext vector by decrypting the ciphertexts with a random string of appropriate length as the "private key". ​ Thus, when the test is "somewhat reliable" in the sense I described,
it must have a noticeable probability of rejecting such decryption attempts.
However, by correctness of the PKE scheme, that test must have negligible
probability of rejecting the decryptions with the actual private key.

I suppose that attack could be made less efficient by making decryption slow, but if the adversary has (the public key or) a plaintext-ciphetext pair for [a plaintext that the adversary has an efficient highly-reliable way of testing], then I can't think of any situation in which
making decryption slow would be any better than just increasing the pbkdf's difficulty.

• nice approach. I need to read it more carefully. I limited my answer to the "standard used" crypto, taking as input the example given in the question by the poster. – ddddavidee May 20 '16 at 15:47