2

All cryptographic algorithms I know of that satisfy Kerckhoffs's principle rely upon secure random number generation. Assuming the existence of a 'numerical oracle' capable of perfectly predicting the outcome of any random number generator, is a Kerckhoff-compliant algorithm possible?

CC BY-SA 3.0
2
  • Why not just say "assuming all algorithms are deterministic"? Also, Kerchoff's principle is mostly irrelevant to modern cryptography, since it is implicit in every security definition.
    – fkraiem
    Sep 13, 2017 at 6:01
  • 1
    Would passphrases be allowed, or is there some kind of oracle present inside my head as well? I haven't noticed it before, that's for sure. Sep 13, 2017 at 11:51

2 Answers 2

2

All secure cryptography requires a secrete key, it can be a symmetric shared secret or an asymmetric key pair with secret private key. The question is how do you get a secret if there are no secure random number sources. Note there are natural sources of random numbers which don't rely on cryptography for their security, but the question said the oracle can predict any RNG including predicting radioactive decay and cosmic rays, and the number I'm thinking of. That is an impressive oracle you have there. If there is no initial secret, and anything we do to try to create an initial secret is detectable by the oracle then anything the legitimate user can do so can the attacker. A secret is how we differentiate between legitimate users and attacker, the attacker is assumed to not know the secret. With all secrets given up by the Oracle there is no difference between legitimate and attacker and no secure cryptography.

CC BY-SA 3.0
2

As Meir Maor notes, generating a cryptographic key that cannot be guessed by an attacker necessarily requires some randomness. One you have a secret key, though, most modern crypto can in fact be done securely without needing any additional randomness.

In particular, most modern symmetric-key authenticated encryption schemes only require each message to be tagged with a nonce. While this nonce value can be chosen at random, the only real requirement is that it needs to be unique for each message encrypted with the same key. Thus, it's perfectly possibly to use e.g. a sequential message ID or even a sufficiently high-resolution timestamp as the nonce.

Also, there are even schemes such as SIV mode that provide nearly perfect authenticated encryption even when used without a nonce. The only thing such "deterministic authenticated encryption" schemes leak (besides the message length, which all general-purpose encryption schemes reveal to some extent) is whether or not two messages encrypted with the same key and the same associated metadata are exactly identical.

For public-key encryption, the need for randomness is more critical. For example, if one were to encrypt a message with a public key without randomizing it in any way, then an attacker could simply guess a possible value for the message, encrypt it in the same way using the same public key and compare the results to see in they match.

However, as long as each user of the encryption system has some (not necessarily shared) secret key of their own that is not known to potential attackers, they can use it to seed a cryptographic pseudorandom number generator and use its output as a substitute for true randomness. As long as the generator is secure, and sufficient care is taken to ensure that its output is never reused, this is just as good in practice as true randomness.

CC BY-SA 3.0

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.