Re: A PRNG based on the DLP

Kristian Gjøsteen <kristiag+news@xxxxxxxxxxxx> (07-01-08 09:03:47):

Nah. Given the internal state, I can easily decide if the output
string came from the generator or if it is random, since the
Legendre symbol gives me the least significant bit of the discrete
logarithm.

Yes, but you (as an attacker) can't apply it, since E bits of the
result are missing. But if you want to make sure, just drop the
least bit from the output.

It's a valid attack. Now you drop the least significant bit, but how
many more such attacks exist?

You don't even need to drop it. Unless you know the full value of S,
you can't apply the Legendre symbol. You can, but it won't give you any
information about log_G S, only about log_G (S mod 2^(B - E)).


This is a general problem when you haven't got a security proof: How
many subtle attacks have you missed?

True. But how could one prove security at all, before it's proven that
either P = NP or P != NP? BBS is secure, as long as the factoring
problem isn't solved. Currently we're stuck with proving insecurity,
and proving equivalence to certain (yet) unsolved problems. What one
needs to prove here is its equivalence to the DLP.


Second, given the output you can recover the previous state using
2^(E/2) operations, so E has to be pretty large.

Yes, so far I have not set any constraints for this generator to be
secure. As you say, however, I would recommend E >= 128.

That should be E >= 256 for a 128 bit security level. Given B-E bits
of X and all of G^X mod P, I can compute the remainder of X using
Shank's BSGS in 2^(E/2) time and space. This gives one lower bound on
E. Can you do better?

Yes, E >= 256 of course.

But we must have missed something. The BSGS attack won't work at all,
because the attacker does not have the full value of G^X mod P in any
step. They always get only part of it. So the attacker must break into
the system and steal S in the first place, to be even able to apply the
BSGS method at all. And _then_ they will need 2^(E/2) further steps to
get to past values.

This was the main reason for developing this generator. The attacker
can only get the current and future values, but no past ones, because
that would mean solving the DLP, even though some information about
those values might be known already. I don't know of any other such
generator. If there is one, it must be based on some problem in NP (or
worse).

So IMO there is nothing wrong with using this PRNG (possibly combined
with some other) for key generation. Just to make sure, that the PRNG
of a compromised system won't reveal all keys generated with it.


Regards,
E.S.
.

Relevant Pages

  • Re: Where do the random numbers come from?
    ... Which part of the protocol is too slow? ... Diffie-Hellman key exchange is too slow for you, ... key exchange so that an attacker can't fake it. ... the best-known random number generator used for non- ...
    (comp.security.ssh)
  • Re: ID revisited ... ( Yet another reason for abandoning numerical
    ... a given piece of data is difficult to guess by an attacker. ... A cryptographically secure pseudo-random number generator is usually ... A stream cipher: a completely deterministic finite state machine ... An entropy gathering and seeding mechanism: ...
    (talk.origins)
  • Re: ID revisited ... ( Yet another reason for abandoning numerical
    ... a given piece of data is difficult to guess by an attacker. ... A cryptographically secure pseudo-random number generator is usually ... A stream cipher: a completely deterministic finite state machine ... An entropy gathering and seeding mechanism: ...
    (talk.origins)
  • Re: A PRNG based on the DLP
    ... generator has a maximal entropy of slightly less than E bits. ... this generator has one major advantage. ... Yes, but you (as an attacker) can't apply it, since E bits of the result ... This is a general problem when you haven't got a security proof: ...
    (sci.crypt)
  • Re: general question how to choose parameters
    ... > the problem that applies here: The Legendre symbol of the message will ... I just define the set of plaintext M to be the subgroup of ... Now given the ciphertext C it won't give any further information to the ... g is a generator of a group of order q. ...
    (sci.crypt)