2
$\begingroup$

Suppose Alice seeds a cryptographically strong Pseudo Random Number Generator with a truly random number, and keeps it secret. Alice then uses the output of the PRNG to generate several 256-bit numbers in sequence. Each of those 256-bit numbers is then used as an ECDSA private key, public keys are generated from them, and those public keys are sent out in the open. The private keys are either kept secret, or destroyed.

An attacker, Mallory, collects a bunch of public keys, some of which belong to Alice. Two questions:

  1. If not told explicitly, can Mallory figure out which keys belong to Alice?

  2. If Mallory does know which keys belong to Alice, can he figure out any of the private keys (or the initial seed)?

My concern is that, since the private keys are mathematically related, information about their relation may be leaked through the ECDSA public key generation (Q = kG). Most implementations of ECDSA I have seen use a PRNG that is frequently re-seeded, like OpenSSL. Presumably, though, one could generate multiple keys sequentially without a re-seed occurring. That being the case, I assume the above is safe. I am, however, having a hard time coming up with a proof for it.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

The most important property of cryptographic PRNGs is that it's indistinguishable from true random numbers, unless you know the seed, or you have huge computational resources. Two important consequences of this requirement are:

  • You can't find the seed from observing the output
  • You can't predict more outputs from observing some of them.

An attacker who can do either of those, either has broken the cryptography used in the PRNG, or he has computational resources exceeding the security level of the PRNG. For typical security levels of at least 128 bits, nobody on earth has the required resources.

Improve this answer
$\endgroup$
5
  • $\begingroup$ That was my intuition as well, and thank you for the response. Here is my issue: If a and b are sequential outputs from a CSPRNG, calculating b from a should be intractable or impossible. This is as you said, and is indeed the requirement for a CSPRNG. However, I cannot figure out a way to logically prove that calculating public key Qb from Qa must also be intractable, given the above, and given that Qb = b*G and Qa = a*G. I agree with your intuition that it must be so ... but I just can't figure out a logical proof for it. $\endgroup$
    – Xor
    May 13, 2012 at 18:59
  • $\begingroup$ You can calculate Qb from PRNG output. You can calculate Qa from PRNG output. If you could calculate Qa from Qb, that would mean that one PRNG output would give you information about another PRNG output. That would be a violation of the PRNG's security property. $\endgroup$
    – David Schwartz
    May 14, 2012 at 2:39
  • $\begingroup$ According to WikiPedia, the only requirements for a CSPRNG are passing the "next-bit test" and withstanding "state compromise extensions". Qa does not give you information about a. So, being able to calculate Qb from Qa does not allow you to predict b from a. Thus, it does not violate either of the two requirements for a CSPRNG. Example: Suppose PRF(0) = 0, PRF(i) = PRF(i-1) + 1. It can be shown that Qb = Qa + G, and that b = a + 1. But neither b nor a can be calculated. $\endgroup$
    – Xor
    May 14, 2012 at 20:57
  • 1
    $\begingroup$ @Xor: Your reasoning is incorrect. A cryptographically-secure PRNG's fundamental security property is that no amount of past output give give you any information about future output. That means no function of past output can give you any information about any function of future output. "Qa does not give you information about a" is flat out false. With Qa, you can tell whether a given number is or is not a. $\endgroup$
    – David Schwartz
    May 15, 2012 at 2:10
  • $\begingroup$ @DavidSchwartz: First, let me say that I really appreciate your responses, as well as CodeInChaos's answer. I agree with your conclusions, and am mostly being pedantic for the sake of clarity and education. I have further things I would like to quibble on ... but the comment length restriction on StackExchange makes these discussions difficult, so I think I will have to cut the discussion short. Thank you again for your time and help. $\endgroup$
    – Xor
    May 15, 2012 at 3:31

Your Answer

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

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