Running key cipher

Last updated

In classical cryptography, the running key cipher is a type of polyalphabetic substitution cipher in which a text, typically from a book, is used to provide a very long keystream. The earliest description of such a cipher was given in 1892 by French mathematician Arthur Joseph Hermann (better known for founding Éditions Hermann). Usually, the book to be used would be agreed ahead of time, while the passage to be used would be chosen randomly for each message and secretly indicated somewhere in the message.

Contents

Example

The text used is The C Programming Language (1978 edition), and the tabula recta is the tableau. The plaintext is "Flee at once".

Page 63, line 1 is selected as the running key:

errors can occur in several places. A label has...

The running key is then written under the plaintext:

Plaintextfleeatonce
Running keyERRORSCANO
CiphertextJCVSRLQNPS

The message is then sent as "JCVSR LQNPS". However, unlike a Vigenère cipher, if the message is extended, the key is not repeated; the key text itself is used as the key.[ clarification needed ] If the message is extended, such as, "Flee at once. We are discovered", then the running key continues as before:

Plaintextfleeatoncewearediscovered
Running keyERRORSCANOCCURINSEVERALPL
CiphertextJCVSRLQNPSYGUIMQAWXSMECTO

To determine where to find the running key, a fake block of five ciphertext characters is subsequently added, with three denoting the page number, and two the line number, using A=0, B=1 etc. to encode digits. Such a block is called an indicator block. The indicator block will be inserted as the second last of each message. (Many other schemes are possible for hiding indicator blocks.) Thus page 63, line 1 encodes as "AGDAB" (06301).

This yields a final message of "JCVSR LQNPS YGUIM QAWXS AGDAB MECTO".

Variants

Modern variants of the running key cipher often replace the traditional tabula recta with bitwise exclusive or, operate on whole bytes 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

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.)

Ciphertext appearing to be plaintext

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 ], 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. [1] 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 [2] . As a result, the entropy per character of both plaintext and running key is low, and the combining operation is easily inverted.

To attack the cipher, a cryptanalyst may 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 (for more detailed explanation refer to 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 almanacs 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 , 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 novels as part of their key material, many sources confuse the book cipher and the running key cipher. They are really only very distantly related. The running key cipher is a polyalphabetic substitution, the book cipher is a homophonic substitution. Perhaps the distinction is most clearly made by the fact that a running cipher would work best of all with a book of random numbers, whereas such a book (containing no text) would be useless for a book cipher.

See also

Related Research Articles

In cryptography, a block cipher is a deterministic algorithm that operates on fixed-length groups of bits, called blocks. Block ciphers are the elementary building blocks of many cryptographic protocols. They are ubiquitous in the storage and exchange of data, where such data is secured and authenticated via encryption.

<span class="mw-page-title-main">Cipher</span> Algorithm for encrypting and decrypting information

In cryptography, a cipher is an algorithm for performing encryption or decryption—a series of well-defined steps that can be followed as a procedure. An alternative, less common term is encipherment. To encipher or encode is to convert information into cipher or code. In common parlance, "cipher" is synonymous with "code", as they are both a set of steps that encrypt a message; however, the concepts are distinct in cryptography, especially classical cryptography.

<span class="mw-page-title-main">Cryptanalysis</span> Study of analyzing information systems in order to discover their hidden aspects

Cryptanalysis refers to the process of analyzing information systems in order to understand hidden aspects of the systems. Cryptanalysis is used to breach cryptographic security systems and gain access to the contents of encrypted messages, even if the cryptographic key is unknown.

<span class="mw-page-title-main">One-time pad</span> Encryption technique

In cryptography, the one-time pad (OTP) is an encryption technique that cannot be cracked, but requires the use of a single-use pre-shared key that is larger than or equal to the size of the message being sent. In this technique, a plaintext is paired with a random secret key. Then, each bit or character of the plaintext is encrypted by combining it with the corresponding bit or character from the pad using modular addition.

In cryptography, a substitution cipher is a method of encrypting in which units of plaintext are replaced with the ciphertext, in a defined manner, with the help of a key; the "units" may be single letters, pairs of letters, triplets of letters, mixtures of the above, and so forth. The receiver deciphers the text by performing the inverse substitution process to extract the original message.

<span class="mw-page-title-main">Transposition cipher</span> Method of encryption

In cryptography, a transposition cipher is a method of encryption which scrambles the positions of characters (transposition) without changing the characters themselves. Transposition ciphers reorder units of plaintext according to a regular system to produce a ciphertext which is a permutation of the plaintext. They differ from substitution ciphers, which do not change the position of units of plaintext but instead change the units themselves. Despite the difference between transposition and substitution operations, they are often combined, as in historical ciphers like the ADFGVX cipher or complex high-quality encryption methods like the modern Advanced Encryption Standard (AES).

<span class="mw-page-title-main">Caesar cipher</span> Simple and widely known encryption technique

In cryptography, a Caesar cipher, also known as Caesar's cipher, the shift cipher, Caesar's code, or Caesar shift, is one of the simplest and most widely known encryption techniques. It is a type of substitution cipher in which each letter in the plaintext is replaced by a letter some fixed number of positions down the alphabet. For example, with a left shift of 3, D would be replaced by A, E would become B, and so on. The method is named after Julius Caesar, who used it in his private correspondence.

<span class="mw-page-title-main">Stream cipher</span> Type of symmetric key cipher

A stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream (keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystream, to give a digit of the ciphertext stream. Since encryption of each digit is dependent on the current state of the cipher, it is also known as state cipher. In practice, a digit is typically a bit and the combining operation is an exclusive-or (XOR).

<span class="mw-page-title-main">Symmetric-key algorithm</span> Algorithm

Symmetric-key algorithms are algorithms for cryptography that use the same cryptographic keys for both the encryption of plaintext and the decryption of ciphertext. The keys may be identical, or there may be a simple transformation to go between the two keys. The keys, in practice, represent a shared secret between two or more parties that can be used to maintain a private information link. The requirement that both parties have access to the secret key is one of the main drawbacks of symmetric-key encryption, in comparison to public-key encryption. However, symmetric-key encryption algorithms are usually better for bulk encryption. With exception of the one-time pad they have a smaller key size, which means less storage space and faster transmission. Due to this, asymmetric-key encryption is often used to exchange the secret key for symmetric-key encryption.

<span class="mw-page-title-main">Vigenère cipher</span> Simple type of polyalphabetic encryption system

The Vigenère cipher is a method of encrypting alphabetic text where each letter of the plaintext is encoded with a different Caesar cipher, whose increment is determined by the corresponding letter of another text, the key.

In cryptography, unicity distance is the length of an original ciphertext needed to break the cipher by reducing the number of possible spurious keys to zero in a brute force attack. That is, after trying every possible key, there should be just one decipherment that makes sense, i.e. expected amount of ciphertext needed to determine the key completely, assuming the underlying message has redundancy.

In cryptography, an initialization vector (IV) or starting variable is an input to a cryptographic primitive being used to provide the initial state. The IV is typically required to be random or pseudorandom, but sometimes an IV only needs to be unpredictable or unique. Randomization is crucial for some encryption schemes to achieve semantic security, a property whereby repeated usage of the scheme under the same key does not allow an attacker to infer relationships between segments of the encrypted message. For block ciphers, the use of an IV is described by the modes of operation.

<span class="mw-page-title-main">Autokey cipher</span> Classic polyalphabet encryption system

An autokey cipher is a cipher that incorporates the message into the key. The key is generated from the message in some automated fashion, sometimes by selecting certain letters from the text or, more commonly, by adding a short primer key to the front of the message.

A polyalphabetic cipher is a substitution, using multiple substitution alphabets. The Vigenère cipher is probably the best-known example of a polyalphabetic cipher, though it is a simplified special case. The Enigma machine is more complex but is still fundamentally a polyalphabetic substitution cipher.

<span class="mw-page-title-main">Tabula recta</span> Fundamental tool in cryptography

In cryptography, the tabula recta is a square table of alphabets, each row of which is made by shifting the previous one to the left. The term was invented by the German author and monk Johannes Trithemius in 1508, and used in his Trithemius cipher.

In cryptography, a block cipher mode of operation is an algorithm that uses a block cipher to provide information security such as confidentiality or authenticity. A block cipher by itself is only suitable for the secure cryptographic transformation of one fixed-length group of bits called a block. A mode of operation describes how to repeatedly apply a cipher's single-block operation to securely transform amounts of data larger than a block.

<span class="mw-page-title-main">Ciphertext</span> Encrypted information

In cryptography, ciphertext or cyphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext that is unreadable by a human or computer without the proper cipher to decrypt it. This process prevents the loss of sensitive information via hacking. Decryption, the inverse of encryption, is the process of turning ciphertext into readable plaintext. Ciphertext is not to be confused with codetext because the latter is a result of a code, not a cipher.

<span class="mw-page-title-main">Substitution–permutation network</span> Cipher design construction

In cryptography, an SP-network, or substitution–permutation network (SPN), is a series of linked mathematical operations used in block cipher algorithms such as AES (Rijndael), 3-Way, Kalyna, Kuznyechik, PRESENT, SAFER, SHARK, and Square.

In cryptography, confusion and diffusion are two properties of the operation of a secure cipher identified by Claude Shannon in his 1945 classified report A Mathematical Theory of Cryptography. These properties, when present, work together to thwart the application of statistics and other methods of cryptanalysis.

In cryptanalysis, Kasiski examination is a method of attacking polyalphabetic substitution ciphers, such as the Vigenère cipher. It was first published by Friedrich Kasiski in 1863, but seems to have been independently discovered by Charles Babbage as early as 1846.

References

  1. American Cryptogram Association. "The ACA and You" Archived 2016-04-03 at the Wayback Machine . 2016.
  2. "Cryptology: Running-Text Ciphers – Cryptanalysis According to Friedman". www.staff.uni-mainz.de. Retrieved 2024-01-10.