Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
    
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. –  Xor May 13 '12 at 18:59
    
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. –  David Schwartz May 14 '12 at 2:39
    
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. –  Xor May 14 '12 at 20:57
1  
@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. –  David Schwartz May 15 '12 at 2:10
    
@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. –  Xor May 15 '12 at 3:31
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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