Content deleted Content added
→Example: small clarification on meaning of indicator block |
m gnoming at 4am |
||
| (46 intermediate revisions by 37 users not shown) | |||
Line 1:
{{short description|Type of polyalphabetic substitution cipher}}
{{refimprove|date=March 2016}}
In classical [[cryptography]], the '''running key cipher''' is a type of [[polyalphabetic
== Example ==
Page 63, line 1 is selected as the running key:
{| class="wikitable" style="text-align:center"
|-
! align="left" | Plaintext
| f || l || e || e || a || t || o || n || c || e
|-
! align="left" | Running key
| E || R || R || O || R || S || C || A || N || O
|-
! align="left" | Ciphertext
| J || C || V || S || R || L || Q || N || P || S
|}
{| class="wikitable" style="text-align:center"
|-
! align="left" | Plaintext
|f || l || e || e || a || t || o || n || c || e || w || e || a || r || e || d || i || s || c || o || v || e || r || e || d
|-
! align="left" | Running key
|E || R || R || O || R || S || C || A || N || O || C || C || U || R || I || N || S || E || V || E || R || A || L || P || L
|-
! align="left" | Ciphertext
|J || C || V || S || R || L || Q || N || P || S || Y || G || U || I || M || Q || A || W || X || S || M || E || C || T || O
|}
== Variants ==
Modern variants of the running key cipher often replace the traditional ''tabula recta'' with bitwise [[exclusive or]], operate on whole [[byte]]s rather than alphabetic letters, and derive their running keys from large files. Apart from possibly greater entropy density of the files, and the ease of automation, there is little practical difference between such variants and traditional methods
=== Permutation generated running keys ===
== Security ==▼
A more compact running key can be used if one combinatorially generates text using several start pointers (or combination rules). For example, rather than start at one place (a single pointer), one could use several start pointers and xor together the streams to form a new running key, similarly skip rules can be used. What is exchanged then is a series of pointers to the running key book and/or a series of rules for generating the new permuted running key from the initial key text. (These may be exchanged via [[public key]] encryption or in person. They may also be changed frequently without changing the running key book.)
Perhaps surprisingly, the security is usually fairly poor. This is because the [[information entropy|entropy]] per character of both plaintext and running key is low, and the combining operation is easily inverted. This means a [[cryptanalysis|cryptanalyst]] can run 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. Eventually it is likely that the running key will be recognised, and the jig is up. This process is sometimes performed as a simple puzzle, for recreation.▼
=== Ciphertext appearing to be plaintext ===
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. Pairs of plaintext and running key characters are far more likely to be high frequency pairs such as 'EE' rather than, say, 'QQ'. This 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).▼
Traditional ciphertext appears to be quite different from plaintext. To address this problem, one variant outputs "plaintext" words instead of "plaintext" letters as the ciphertext output. This is done by creating an "alphabet" of words (in practice multiple words can correspond to each ciphertext output character). The result is a ciphertext output which looks like a long sequence of plaintext words (the process can be nested). Theoretically, this is no different from using standard ciphertext characters as output. However, plaintext-looking ciphertext may result in a "human in the loop" to try to mistakenly interpret it as decoded plaintext.
An example would be BDA (Berkhoff deflater algorithm){{Citation needed|reason=Can't find any explanation about this out there|date=October 2019}}, each ciphertext output character has at least one noun, verb, adjective and adverb associated with it. (E.g. (at least) one of each for every [[ASCII]] character). Grammatically plausible sentences are generated as ciphertext output. Decryption requires mapping the words back to ASCII, and then decrypting the characters to the real plaintext using the running key. Nested-BDA will run the output through the reencryption process several times, producing several layers of "plaintext-looking" ciphertext - each one potentially requiring "human-in-the-loop" to try to interpret its non-existent [[semantic]] meaning.
=== Gromark cipher ===
The "Gromark cipher" ("[[Gronsfeld cipher]] with mixed alphabet and running key") uses a running numerical key formed by adding successive pairs of digits.<ref>American Cryptogram Association.
[http://cryptogram.org/docs/acayou16.pdf "The ACA and You"] {{Webarchive|url=https://web.archive.org/web/20160403131720/http://cryptogram.org/docs/acayou16.pdf |date=2016-04-03 }}.
2016.</ref>
The [[VIC cipher]] uses a similar [[lagged Fibonacci generator]].
▲== 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.
▲
▲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.
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).
== Confusion ==
Because both ciphers classically employed [[novel
== See also ==
Line 75 ⟶ 87:
* [[Topics in cryptography]]
{{
== References ==
{{Reflist}}
[[Category:Stream ciphers]]
| |||