How secure is Vigenere cipher for random data?

Question

Traditional situation

It is easy to crack a ciphertext encrypted by Vigenere cipher, if you know the plaintext is in a natural language like English. There are two methods to discover the key used to encrypt the plaintext. Either you know frequencies of certain characters that will occur more often than others (e for English) or you know a word that will occur in the plaintext (the, a, etc. for English).

Cryptographically secure random

What if the plaintext is actually CSR (cryptographically secure random) data, and you encrypt it using Vigenere cipher with a CSR key.

Let's say we reuse the key four times (to account for flaws if random is not CSR?). Also, the key is sufficiently large so that brute forcing it is not an option (for example, the key may be 1KB, and therefore the cipher and plaintext is 4KB).

Would it be possible to crack that, even though you are reusing the same key (the key is also CSR) but not as large as the plaintext data?

or: how secure is this relative to other methods for encryption/decryption?

Context

In case you ask yourself: 'why would you want to encrypt random data?':

Well, if the answer is no, and thus it is impossible to crack it. That would mean that once a shared secret is established between two persons, you could establish an information-theoretically secure connection, right? Because once you have a shared secret key 'A' of 1KB. Then you could create a shared secret key 'B' of 2KB using 'A' two times on newly random generated data. Then you could use 1KB of 'B' as a one-time pad on your actual plaintext communications in English. And you could use the other 1KB of 'B' for safely communicating the next 2KB sized key and so forth.

Answer 1

I agree it would be difficult (possibly impossible) to break a Vigenere cipher on random data that's never used and is simply random.

But your scheme where you use that random data as a one-time-pad would not have informational theoretic perfect security like a one-time-pad.

It will have the security of a Vigenere cipher -- the weakest link in the chain. You wouldn't be able to easily directly attack the Vigenere cipher on the random data, but you could easily attack the combination.

I mistakenly misremembered the Vigenere cipher with its primary operation being XOR not addition modulo character space. My mistake makes the attack on your scheme trivial due to properties of XOR. I'll call my mistaken scheme VigenereXOR.

The old example using VigenereXOR:

 import scipy
 rand_bytes=[scipy.random.random_integers(256) for i in range(512)] # 512 random bytes
 vig_key = "MYSECRET"*64
 vig_key_bytes = [ord(c) for c in vig_key] 
 encrypted_random = [(r ^ vk) for r,vk in zip(rand_bytes, vig_key_bytes)]
 message = "But your scheme where you use that random data as a one-time-pad would not have informational theoretic perfect security like a one-time-pad."
 message_bytes = [ord(c) for c in message]
 encrypted_message = [(r ^ m) for r,m in zip(rand_bytes, message_bytes)]

Now if an attacker observes both encrypted_random and encrypted_message, they can XOR them together, at which point they would have the original message simply encrypted with the Vigenere cipher as (A XOR B) XOR (B XOR C) = A XOR C; hence all the frequency attacks on the message Vigenere could be directly applied.

On the real Vigenere cipher:

 encrypted_random = [(r + vk) % 256 for r,vk in zip(rand_bytes, vig_key_bytes)]

there may be sophisticated attacks on it. At the very least you obviously do not have perfect security from the scheme. If the scheme had perfect security, then the length of the Vigenere key would be irrelevant and it obviously isn't -- a one character key could be used -- which would be trivially attackable. You may note that you can still construct (A + B mod 256) XOR (B XOR C) = ((A + B mod 256) XOR B) XOR C. (A + B mod 256) XOR B is not randomly distributed (e.g., if A = 8, then the only possibilities for (A + B mod 256) XOR B are 8,24,56,120,248 after trying all 256 values of B). Headway of this sort possibly can be made to make this attack much better than brute force.

It's a common textbook result (with a straightforward proof) that you can't get information-theoretic perfect security if your keyspace (what was exchanged prior to encryption) isn't at least as large as your message space. See Shannon's classic 1949 paper.