trying to identify the key of a vigenere cipher via brute force

Question

I'm working on a bit of an ARG game type thing that uses the vigenere cipher. what im wondering is the chance a player could brute force said cipher by simply checking all possible key sequences of the right length, that being 41 characters, for deciphering a sequence of about 1000 characters. its also using more character types than the usual 26, it has 77 unique characters. so what are the chances they could stumble across the correct key by almost (or entirely) complete luck? additionally, could i possibly make the cipher more secure by applying a secondary layer of defense (like converting to a different base or something) and thus making it harder to tell what the alphabet of the cipher is. assume the players already know that it somehow relates to a vigenere cipher and they already know the character length of the key.

Answer 1

If you only think about Brute Force as an attack, then we first have to compute the number of possible keys: $77^{41} = log_2(77^{41}) \approx 2^{260}$. For Brute Force this would end up in 259-260 Bit security. Common sense is, that 128 - 256 Bit security is already save. Therefore your Cipher would be secure, if Brute Force is the only possible attack and the probability for someone guessing the correct key is negligible.

On the other hand there are better attacks for Vigenere. (It took several hundred years to find efficient attacks, but today it is said to be unsecure) The Kasiski attack may be best suited to attack your cipher, because the attacker knows the length of the key.

How you may make it more secure: A secondary layer of security is in many cases not useful (either is does not archive the wanted security, it does not make anything more secure or in some cases even make security worse). Creating a good secondary layer is often difficult. One way to make your cipher more secure is using a bigger key. If you look at the Kasiski attack the attacker needs to know the length of the key. If you use different key length this may make that attack more difficult. You could also combine bigger key length with keys of different length.