4
$\begingroup$

It is argued that the Vigenere cipher is easy to break using the Babbage's solution. But this solution counts on finding the repetetive occurences of letter groups(words if you will). What if my key is thousand letters long. Wouldn't it then be very unlikely that the same word gets ciphered with the same portion of the key resulting in making it almost impossible to break?

$\endgroup$
2
  • $\begingroup$ It'll be unlikely, but not as unlikely as early 21st century ciphers such as AES. AES has unlikelihood of $2^{-128}$, where as Vigenere might be somewhere around $2^{-16}$ $\endgroup$
    – DannyNiu
    Jul 22, 2022 at 8:31
  • $\begingroup$ If your message is shorter than the key you'll be fine. But if a plaintext message is at least 3 times the message length, a simple n-gram based beam search will recover it nearly perfectly. $\endgroup$ Jul 23, 2022 at 9:27

3 Answers 3

6
$\begingroup$

Yes, it would become harder, if just because you'd first have to find the size of the key, and then you can probably not use the old technique.

Would it be secure? No, of course not. Finding words is maybe the easiest way to analyze using pen and paper, but there are many other ways of leaking information. You could just brute force for each position, and then check if the results make sense at each location (modulus the length of the key, but that can also be brute forced). Note that a cipher is considered broken if any information is leaked, and Vigenère starts leaking information at position N, i.e. the first character of a repeated key.

Of course, if your plaintext is shorter than your key then you don't have any repetition, and then it becomes a one-time pad. The more repetition you have of the keyword the more data points (which can all be paired together) and getting the solution will therefore become much easier with every 1000 ciphertext characters added.

$\endgroup$
5
  • $\begingroup$ Would not the randomly same character groups be a problem? Do you imply with your answer that it is still breakable with a key that is a thousand characters long? $\endgroup$ Jul 22, 2022 at 8:44
  • $\begingroup$ Say that you try a key at position zero and at position N you get a Q or a Z for that same key character. Since those letters are less likely then the key is likely wrong, and the other position is not likely to have the calculated plaintext character as well. Information leakage thus broken. That's really all it takes. $\endgroup$
    – Maarten Bodewes
    Jul 22, 2022 at 8:55
  • 1
    $\begingroup$ It is probably useful to mention the two-time pad, since this is how you would attack a Vigenere ciphertext that is not much longer than its key. You also need the key length, but you will do most-probable-first exhaustive search for this. $\endgroup$
    – K.G.
    Jul 22, 2022 at 9:07
  • 2
    $\begingroup$ Also, if you have a lot of ciphertext relative to key length, the usual algorithms just work… $\endgroup$
    – K.G.
    Jul 22, 2022 at 9:09
  • $\begingroup$ Yeah, determining the key size is the hardest part, otherwise just a many-time pad as before. You really don't want your security rely on determining the key size because that's still relatively easy (and for most ciphers we consider it a configuration parameter which is, as such, known in advance). $\endgroup$
    – Maarten Bodewes
    Jul 22, 2022 at 9:20
1
$\begingroup$

The attack does not necessarily depend on words, so much as just letter frequencies in English (or whatever language, asssuming statistics are not flat).

Yes, for obvious reasons longer keys take more computation to find...

... but, nevertheless, with a message at least three times the length of the key, it does seem that the statistical attach succeeds very well. Years ago, when I read about this, I could hardly believe it, and did quite a few experiments, and ... became convinced. :)

$\endgroup$
1
$\begingroup$

The difficulty of breaking long-key Vigenere in a ciphertext-only setting will depend on the amount of times your key is being reused while encrypting the plaintext, the type of plaintext, and the length of the key. Very little key repetition will, however, be sufficient for a practical break in realistic settings of these parameters.

The dependence of ciphertext-only security on these parameters is not always completely intuitive. For instance, if we consider the two time pad (i.e. key roughly half as long as the plaintext) and natural language plaintext and denote by $n$ the key length, then breaking the cipher probably becomes easier (not harder) as $n$ increases. Indeed, recognizing the period is the same problem as recognizing the difference of two natural plaintexts as nonrandom, which is easy for large $n$. Having recovered the period, plaintext recovery requires finding both $p_1$ and $p_2$ given $p_1 - p_2$, where $p_1$ and $p_2$ are the first and second half of the plaintext. Solving this for modestly large $n$ can be given as a (relatively difficult but doable) exercise to an undergraduate cryptography student. If the type of data is images and not English, then finding good approximations $p_1$ and $p_2$ can be done simply by looking at the difference.

Apart from these considerations, it is worth noting that security against ciphertext-only attack is an incredibly weak notion of security by the standards of modern cryptography. While breaking the two-time-pad in this setting takes a little bit of work, defeating it e.g. in a setting where partially chosen plaintext is allowed is totally trivial.

Summing up, Vigenere only becomes secure when the size of all plaintext encrypted under one key is fairly close to the size of the key itself.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.