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 sometimes broken due to reuse of 'one-time' cipher pages in practice, while VIC was not.

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 sixth digit of the Date

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

': Generate a random 5-digit Keygroup
  • ': Write the first 5 digits of the secret Date': Subtract from by modular arithmetic
  • ': Write out the first 20 letters from the secret Phrase': Sequence the first and second ten characters separately
  • ': Write out the 5-Digits from, then apply Chain Addition applied to create five more digits': The digit sequence '1234567890' is written out as an aide for encoding when creating
  • ': Addition of to - this is digit-by-digit by mod-10 arithmetic, i.e. no 'carrying' over tens to the next column': Encoding of the digits in under as the key: No used, presumably to avoid confusion
  • ': The Sequencing of : These are five 10-digit lines created by chain addition of . The last two non-equal digits are added to the agent's personal number to determine the key length of the 2 transpositions.
  • '': No used, presumably to avoid confusion ''

Message key derivation

': The first 'a' digits extracted from when transposed via . This transposition is done by writing out the columns of numbers underneath the digits in, beginning with the column of numbers underneath the digit ‘1', then the column beneath the digit ‘2’, and so on in numerical order, until 'a' digits have been written out. These digits are used as the key to the Columnar Transposition.
  • ': The next 'b' digits extracted from when transposed via . This transposition is done in the same manner as, but is carried on from the previous transposition, meaning it may start mid-column under the digit of where the last transposition left off. These resulting digits are used to key the Diagonal Transposition. : The Sequencing of, this is used as the key to the Straddling Checkerboard.

Example of key generation


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 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 filled in in order, followed by . and /.
5961328470
ATONESIR
6BCDFGHJKLM
8PQUVWXYZ./

An example encoding is below, where numbers :
MESSAGE: 'Attack at dawn. By dawn I mean 0500. Not 0915 like you did last time.'
Encoding of individual symbols:
A T T A C K A T D A W N 0 9 1 5
5 9 9 5 69 64 5 9 66 5 83 3 80 000 999 111 555 80
Final code:
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. The meaning of 'diagonal' in this case is that triangular disruption zones were employed to make the transposition irregular.
Keygroup insertion
The Keygroup is inserted into the ciphertext 'P' groups from the end; where 'P' is the unused sixth digit of the Date.
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:
  • 1234 + 6789 = 7913
  • 1234 - 6789 = 5555
    Sequencing
Sequencing in this context is ordering the elements of an input from 1-10. This occurs either to letters, or numbers. In the event of equal values, then the leftmost value is sequenced first. For example:
  • LETTERS: The word 'Octopus' is sequenced as '2163475' -
  • NUMBERS: The number '90210' is sequenced as '34215' -
    Chain addition
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' would have encodings as follows;.
So the output would be: '27067'.

Decryption

Decryption of the VIC Cipher is as follows:Extract the Keygroup - By knowledge of the sixth digit of the secret Date, remove the 5 digits of the Keygroup from the ciphertextGenerate the Message Keys - By using the knowledge of the various secrets generate the keys in the same manner as the encryption processDecrypt the Ciphertext - By using knowledge of the Message Keys for the transpositions and straddling checkerboard decrypt them

Cryptanalysis

The cipher is one of the strongest pen and 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 computers.