VIC cipher


The VIC cipher was a pencil and paper cipher used by the Soviet spy Reino Häyhänen, codenamed "VICTOR".
If the cipher were to be given a modern technical name, it would be known as a "straddling bipartite monoalphabetic substitution superenciphered by modified double transposition."
However, by general classification it is part of the Nihilist family of ciphers.
It was arguably the most complex hand-operated cipher ever seen, when it was first discovered. The initial analysis done by the American National Security Agency in 1953 did not absolutely conclude that it was a hand cipher, but its placement in a hollowed out 5¢ coin implied it could be decoded using pencil and paper. The VIC cipher remained unbroken until more information about its structure was available.
Although certainly not as complex or secure as modern computer operated stream ciphers or block ciphers, in practice messages protected by it resisted all attempts at cryptanalysis by at least the NSA from its discovery in 1953 until Häyhänen's defection in 1957.

A revolutionary leap

The VIC cipher can be regarded as the evolutionary pinnacle of the Nihilist cipher family.
The VIC cipher has several important integrated components, including mod 10 chain addition, a lagged Fibonacci generator , a straddling checkerboard, and a disrupted double transposition.
Until the discovery of VIC, it was generally thought that a double transposition alone was the most complex cipher an agent, as a practical matter, could use as a field cipher.

History

During World War II, several Soviet spy rings communicated to Moscow Centre using two ciphers which are essentially evolutionary improvements on the basic Nihilist cipher. A very strong version was used by Max Clausen in Richard Sorge's network in Japan, and by Alexander Foote in the Lucy spy ring in Switzerland. A slightly weaker version was used by the Rote Kapelle network.
In both versions, the plaintext was first converted to digits by use of a straddling checkerboard rather than a Polybius square. This has the advantage of slightly compressing the plaintext, thus raising its unicity distance and also allowing radio operators to complete their transmissions quicker and shut down sooner. Shutting down sooner reduces the risk of the operator being found by enemy radio direction finders. Increasing the unicity distance increases strength against statistical attacks.
Clausen and Foote both wrote their plaintext in English, and memorized the 8 most frequent letters of English through the mnemonic phrase "a sin to err". The standard English straddling checkerboard has 28 character slots and in this cipher the extra two became "full stop" and "numbers shift". Numbers were sent by a numbers shift, followed by the actual plaintext digits in repeated pairs, followed by another shift. Then, similarly to the basic Nihilist, a digital additive was added in, which was called "closing". However a different additive was used each time, so finally a concealed "indicator group" had to be inserted to indicate what additive was used.
Unlike basic Nihilist, the additive was added by non-carrying addition, thus producing a more uniform output which doesn't leak as much information. More importantly, the additive was generated not through a keyword, but by selecting lines at random from almanacs of industrial statistics. Such books were deemed dull enough to not arouse suspicion if an agent was searched, and to have such high entropy density as to provide a very secure additive. Of course the figures from such a book are not actually uniformly distributed, but nevertheless they have much higher entropy density than passphrases and the like; at any rate, in practice they seem never to have been successfully cryptanalysed.
The weaker version generated the additive from the text of a novel or similar book, This text was converted to a digital additive using a technique similar to a straddling checkerboard.
The ultimate development along these lines was the VIC cipher, used in the 1950s by Reino Häyhänen. By this time, most Soviet agents were instead using one-time pads. However, despite the theoretical perfection of the one-time pad, in practice they were broken, while VIC was not. The one-time cipher could however only be broken when cipher pages were re-used, due to logistic problems, and therefore was no longer truly one-time

Mechanics overview

The secret key for the encryption is the following:
The encryption was also aided by the adversary not knowing a 5-digit Keygroup which was unique to each message. The Keygroup was not strictly a 'secret',, but it was at a location in the ciphertext that was not known to an adversary.
The cipher broadly worked as follows:
  1. Use the secrets above create a 50 digit block of pseudo random-numbers
  2. Use this block to create the message keys for:
  3. # A Straddling Checkerboard
  4. # Two Columnar transpositions
  5. Encrypt the Plaintext message via the straddling checkerboard
  6. Apply two transpositions to the resultant ciphertext through two columnar
  7. # A 'Standard' Columnar Transposition
  8. # A Diagonal Columnar Transposition
  9. Insertion of the Keygroup into the ciphertext - as determined by the Personal Number

    Detailed mechanics

Note: this section tracks the calculations by referring to or similar. This is to align with the notation stated in the CIA archive description.

Pseudorandom block derivation


Personal Number: 6
Date: 13 Sept 1959 // Moon Landing - 13 Sept 1959 
Phrase: 'Twas the night before Christmas' // from 'A visit from St. Nicholas' - poem
Keygroup: 72401 // randomly generated
: 72401 // Keygroup
: 13919 // Date - truncated to 5 digits 
: 69592 // subtract from 
: TWASTHENIG HTBEFORECH // Phrase - truncated to 20 characters
: 8017942653 6013589427 // via Sequencing
: 6959254417 1234567890 // from and chain addition, then '1234567890'
: 4966196060 // add to 
: 3288628787 // encode with , helps 
: 3178429506 // The Sequencing of 
: 5064805552 // BLOCK: Chain addition of for 50 digits
: 5602850077
: 1620350748
: 7823857125
: 5051328370
Last two non-equal digits are '7' and '0', added to Personal Number means that the permutation keys are 13 and 6 digits long.
: 0668005552551 // first 13 digits from block
: 758838 // next 6 digits from block
: 5961328470 // Sequencing of

Message encryption

Straddling checkerboard

Once the key has been generated, the first stage of actually encrypting the Message is to convert it to a series of digits, this is done via a Straddling checkerboard. The key for the checkerboard is based on . Then a pre-agreed series of common letters used on the second row. The example below uses the English mnemonic 'AT ONE SIR', however the Cyrillic mnemonic used by Hayhanen was 'snegopad', the Russian word for snowfall.
The remaining cells are filled in, with the rest of the alphabet/symbols filled in in order.
5961328470
ATONESIR
6BCDFGHJKLM
8PQUVWXYZ./

An Example encoding is below:
MESSAGE: 'Attack at dawn. By dawn I mean 0500. Not 0915 like you did last time.'

59956 96459 66583 38765 88665 83376 02538 00005
55000 00080 87319 80000 99911 15558 06776 42881
86667 66675 49976 0287-

Transpositions: columnar transposition

The message is transposed via standard columnar transposition keyed by above.
The message is then transposed via Diagonal Transposition keyed by above.
Keygroup insertion
The Keygroup is inserted into the ciphertext 'P' groups from the end; where 'P' is the Personal Number of the agent.
Modular Addition/Subtraction
Modular addition or subtraction, also known as 'false adding/subtraction', in this context is digit-by-digit addition and subtraction without 'carrying' or 'borrowing'. For example:
Sequencing in this context is ordering the elements of an input from 1-10. This occurs either to letters, or numbers. In the even of equal values, then the leftmost value is sequenced first. For example:
Chain Addition is akin to a Linear-feedback shift register, whereby a stream of number is generated as an output to a seed number. Within the VIC Cipher chain addition works by taking the original number, false-adding the first two digits, putting this new number at the end of the chain. This continues, however the digits being added are incremented by one. For example, if the seed was '90210', the first 5 iterations are shown below:
90210 // Initial seed value
90210 9 // 9 = 9+0
90210 92 // 2 = 0+2
90210 923 // 3 = 2+1
90210 9231 // 1 = 1+0
90210 92319 // 9 = 0+9; note how the first '9' generated is being fed back in
Digit encoding
The encoding step replaces each digit in a number with one from a key sequence that represents its position in the 1-10 ordering. It should be seen that by writing out the series '1234567890' underneath each value from 0-9 has another above it. Simply replace every digit in the number to be encoded with the one above it in the key sequence.
Key6013589427
Aide1234567890

For example the number '90210' is would have encodings as follows;.
So the output would be: '27067'

Decryption

To decrypt the VIC Cipher is as follows:
The cipher is one of the strongest pen+paper ciphers actually used in the real world, and was not broken by the NSA at the time.
. However, with the advent of modern computing, and public disclosure of the algorithm this would not be considered a strong cipher. It can be observed that the majority of the entropy in the secret key converges to a 10-digit number . This 10-digit number is approximately 34 bits of entropy, combined with the last digit of the date would make about 38 bits of entropy in terms of Message Key strength. 38 bits is subject to a Brute-force attack within less than a day on modern computing.