Editing Running key cipher (section)

== Security and cryptanalysis ==

If the running key is truly random, never reused, and kept secret, the result is a [[one-time pad]], a method that provides [[perfect secrecy]] (reveals no information about the plaintext). However, if (as usual) the running key is a block of text in a [[natural language]], security actually becomes fairly poor, since that text will have non-random characteristics which can be used to aid cryptanalysis: for example, [[William F. Friedman]] suggested a [[ciphertext-only attack]] during WWI against most frequent letters encoded by other most frequent letters.<ref>{{Cite web |title=Cryptology: Running-Text Ciphers – Cryptanalysis According to Friedman |url=https://www.staff.uni-mainz.de/pommeren/Cryptology/Classic/7_Aperiodic/AnalFR.html |access-date=2024-01-10 |website=www.staff.uni-mainz.de}}</ref> As a result, the [[information entropy|entropy]] per character of both plaintext and running key is low, and the combining operation is easily inverted.

To attack the cipher, a [[cryptanalysis|cryptanalyst]] may run [[Known-plaintext attack|guessed probable plaintexts]] along the ciphertext, subtracting them out from each possible position. When the result is a chunk of something intelligible, there is a high probability that the guessed plain text is correct for that position (as either actual plaintext, or part of the running key). The 'chunk of something intelligible' can then often be extended at either end, thus providing even more probable plaintext, which can in turn be extended, and so on (for more detailed explanation refer to [[Autokey cipher#Cryptanalysis|Autokey cipher]]). Eventually it is likely that the source of the running key will be identified, and the jig is up.

There are several ways to improve the security. The first and most obvious is to use a secret mixed alphabet tableau instead of a ''tabula recta''. This does indeed greatly complicate matters but it is not a complete solution. As exploited in Friedman's method, pairs of plaintext and running key characters are far more likely to be high frequency pairs such as 'EE' rather than, say, 'QQ'. The skew this causes to the output [[frequency distribution]] is smeared by the fact that it is quite possible that 'EE' and 'QQ' map to the same ciphertext character, but nevertheless the distribution is not flat. This may enable the cryptanalyst to deduce part of the tableau, then proceed as before (but with gaps where there are sections missing from the reconstructed tableau).

Another possibility is to use a key text that has more entropy per character than typical English. For this purpose, the [[KGB]] advised agents to use documents like [[almanac]]s and trade reports, which often contain long lists of random-looking numbers.

Another problem is that the keyspace is surprisingly small. Suppose that there are 100 million key texts that might plausibly be used, and that on average each has 11 thousand possible starting positions. To an opponent with a massive collection of possible key texts, this leaves possible a brute force search of the order of <math>2^{40}</math>, which by computer cryptography standards is a relatively easy target. (See permutation generated running keys above for an approach to this problem).