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.

I have just read little about the Vernam cipher and the problems of implementing it.

But, in practice, would not the key, if generated by a commonly used programming language's Random() function (like Python's or Java's random functions from their standard libraries), be enough to make the message almost uncrackable if the key is as long as the message and the key is only known by the author of the text?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

The standard random number generator, in languages like Java or Python, does not generate real random numbers but pseudorandom numbers determined by an initial seed value. If an attacker can somehow guess or determine this seed value, they can reconstruct the entire sequence of pseudorandom outputs.

Furthermore, the default pseudorandom number generators in most languages are not cryptographically secure. In particular:

  • The set of possible seeds is typically rather small; for example, the seed may be a 32-bit integer, meaning that an attacker only needs to test 232 different seeds to find the correct one. On a modern computer, this can often be done in a few seconds.

  • Worse yet, the initial seed is often chosen based on some fairly easily guessable value, such as the system time. If such a seed is used, and if you know roughly when a key was generated, you can narrow down the range of likely seed values significantly.

  • Even if the seed is chosen securely (i.e. completely unpredictably) from a set large enough to resists brute force guessing, the algorithms used to generate the pseudorandom outputs from the seed are typically not designed to withstand cryptanalytic attacks. Thus, for many commonly used algorithms, the seed can be fairly efficiently reconstructed from the outputs.

The first two attacks above only require that the attacker has access to some ciphertext, and can try to decrypt it with keys based on different seeds and see for which seed the resulting decrypted data makes sense. The last attack generally requires a bit more, namely that the attacker must know at least part of the keystream — but if the attacker has the ciphertext and can guess part of the plaintext, they can easily obtain the corresponding parts of the keystream.

Of course, if you created your key based on a pseudorandom number generator that did not have any of these weaknesses, then the scheme you describe would be secure. Indeed, that is pretty much exactly what a synchronous stream cipher is.

share|improve this answer
1  
And, to be clear, a cipher based upon a keyed CSPRNG is not a Vernam cipher because the keystream is not truly random. This is the difference between a synchronous stream cipher and a one-time pad: one is computationally secure, the other has perfect secrecy. –  Stephen Touset Sep 9 at 21:02
    
Wikipedia states on OTP: "Given perfect secrecy, in contrast to conventional symmetric encryption, OTP is immune even to brute-force attacks. Trying all keys simply yields all plaintexts, all equally likely to be the actual plaintext." Does not that mean that as long nobody knows that I have used a PRG to produce the key, would not the cipher be considered perfectly secured since all attempts to bruteforce it would yeld all plaintexts? –  Rox Sep 11 at 18:17
    
@Rox: See Kerckhoff's principle: a secure cryptosystem should remain secure even if the attacker knows exactly how it works (and, in particular, how you produced your key). Besides, if someone trying to crack your cipher didn't already know that you used a standard PRNG, now they do, because you posted about it here. Mind you, even if they didn't know, they might guess it anyway, since it's such a common amateur mistake. –  Ilmari Karonen Sep 11 at 19:32

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.