5
$\begingroup$

Given a weak entropy private key and its associated public key. Can we predict low entropy from the private key by examining the public key?

In other words, is the low entropy from the private key in some ways 'reflected' in the public key?

What signals a public key can give in case of a weak private key?

$\endgroup$

1 Answer 1

4
$\begingroup$

Since the private key is a value, it's entropy is undefined. We could define the entropy (per key) of a process generating the private key, but we'll stick (except in 3) to the usual modeling of asymmetric key generation as a process producing both the public key and the private key from a random generator. We thus reformulate the question as:

Can we detect low entropy at the output of the random generator from the public key alone?

Sometime, depending on the nature and profoundness of the random generator defect, on the cryptosystem, and one how many public keys was examine. Situations where that's possible include:

  1. When the generator twice outputs the same value, and we can see that it twice generated the same public key.
  2. The generator's output during a key generation is, with sizable probability, among a known set small enough to be predicted, and we know the key generation algorithm (part of the standard theoretical hypothesis in crypto). We can apply the key generation algorithm to this set, and test if the public key is among the results. That can also yield the private key.
  3. As a variant of the above, in cases where defects of the generator conspire to make the private key similarly restricted to a small set, and the public key can be efficiently computed from the private key. The later applies to many cryptosystems based of the Discrete Logarithm problem in some public group (ElGamal encryption, Schnorr signature, DSA, ECDSA, EdDSA). It also applies to RSA when the private key contain $e$, or/and $e$ is small enough to be guessable.

For many cryptosystems, these methods are the best known to detect a low-entropy source from the public key. For others including RSA (and more generally most cryptosystem relying on the difficulty of integer factorization), there are better ways. For example, if the prime number generator used to generate $p$ and $q$ of an RSA key returns values in a list of $2^{40}$ unknown (and un‑guessable) primes, that's detectable with good probability from about $2^{20}$ public keys (it also recovers matching private keys for some of the public keys). That's the GCD attack, and it happened, more than once.

$\endgroup$
6
  • $\begingroup$ Note that these are ways to detect low entropy. I don't think there would be any generic way to show low entropy all if not most of the time (other than trying out private keys and see if they match the public key of course, assuming you know the distribution). $\endgroup$
    – Maarten Bodewes
    Feb 23, 2021 at 20:22
  • $\begingroup$ The GCD attack is fairly generic. It will work for any method where we have a low entropy pool of primes and the private key generation is randomly selected from this pool (need not be uniform). And we can imitate the key generation process. It will not work if we for example pick only a single prime properly and the other one in a related fashion to the first prime but the latter is unlikely to happen by accident, the former has. $\endgroup$
    – Meir Maor
    Feb 24, 2021 at 9:38
  • $\begingroup$ @MeirMaor I'm more wondering what happens when the CS-PRNG is seeded with low entropy. In that case I suppose you just need to "brute force" the seeds / private key and then match with the public key (the prime pairs are defined, but not yet put in a table, basically). $\endgroup$
    – Maarten Bodewes
    Feb 24, 2021 at 12:30
  • $\begingroup$ Any CS-PRNG seeded with low entropy can be detected with the GCD attack using aproxiamelty 2^(entropy/2) examples. That is for the detection of the flawed technique but a full brute force of the low entropy seed will be needed to actually factorize a specific key. $\endgroup$
    – Meir Maor
    Feb 24, 2021 at 12:51
  • 1
    $\begingroup$ @MeirMaor: that assumes that the RSA key generation queries the CS-PRNG separately for each prime. That needn't be the case - for example, the various algorithms in 186-4 generate both from a single seed (and hence the GCD won't show anything, unless the same seed is used twice, and thus generates the same public key twice) $\endgroup$
    – poncho
    Feb 24, 2021 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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