Vernam-Challenge-bar

The Vernam cipher is mentioned in dozens of cryptography books. It is simple and more secure than most other basic encryption methods. Can you solve the three Vernam challenges I am going to introduce today?

Everybody interested in historical crypto systems knows the Vernam cipher. The Vernam cipher is a special case of the Vigenère cipher – if the key used for a Vigenère encryption is as long as the message itself, it’s a Vernam encryption.

 

Vernam: simple but hard to break

The Vernam cipher works exactly like the One Time Pad, with the only difference that a One Time Pad key is a sequence of random letters, while the Vernam key is a phrase (usually taken from a book or newspaper).

As an example, let’s encrypt the famous Neil Armstrong quote “That’s one small step for a man, one giant leap for mankind”. As key we choose the phrase “We are one nation, we are one people, and our time for change has come” (it’s Barack Obama quote). Applying a Vernam encryption means that we add the key to the cleartext (A=0, B=1, C=2; if the result is greater than 25, we substract 26):

THATSONESMALLSTEPFORAMANONEGIANTLEAPFORMANKIND
WEAREONENATIONWEAREONEPEOPLEANDOURTIMEFORCHANGEHASCOME
-------------------------------------------------
PLAKWCAIFMTTZFPIPWSFNQPRCCPKINQHFVTXRSWARPRIAJ

The ciphertext is “PLAKWC…”. As you see, we didn’t need the last eight letters of the key.

The Vernam cipher is mentioned in numerous crypto books. It can be regarded as a compromise between a One Time Pad (unbreakable) and a Vigenère cipher (can be easily broken today).

It is clear that a Vernam cipher can be broken, but it’s not trivial. One approach is to guess a word in the cleartext or the key. If, say, the word MONEY is guessed correctly in the key and the resulting cleartext fragment is EETIN, we can conclude that the word MEETING appears in the cleartext. This provides us two more letters in the keyword, say EMONEYI, which lets us guess that THE stands before MONEY. We now have two additional key letters, which provides us two more cleartext letters. If we are lucky, we can reconstruct the whole cleartext this way.

In 2008, German crypto expert Tobias Schrödel published a hitherto unknown Vigenère cipher breaking method in Cryptologia. This attack is based on eliminating rare letter combinations in both the cleartext and the keyword. It requires a computer program that implements it (in fact, it is implemented in CrypTool 1). Tobias’ method is particularly helpful if the message is short compared to the keyword (e.g., if a 15 letter cleartext is encrypted with a seven-letter keyword). However, it requires that the keyword is a real word and not a random letter sequence.

It seems possible that Tobias’ method can also be used for attacking a Vernam cipher. His paper doesn’t mention this, but it’s certainly worth a try.

 

Three challenges

Though the Vernam cipher is well known among crypto experts, it has never been in wide-spread use. In fact, I don’t know a single case where a Vernam cipher was used in practice. In addition, there is very little literature about breaking a Vernam cipher. For this reason, I have created three Vernam challenges of different length. I am going to introduce them below. Of course, a shorter message is harder to break than a longer one.

All cleartexts and keyphrases are taken from the English language. I used CrypTool 1 to carry out the encryptions. Here are the challenges:

Challenge 1

WAFVRWRYQQZPHJSBBSPWGLZZVNVNFXNVCMPSGQHBAMUMYTEWVGZDRZMMERHBTIXHKHNTVRG

Challenge 2

MYXNKBFETHMVUIBLVHTEMOELVKKGMVV

Challenge 3

YADPNBXGWN

Can you solve any of these challenges? If so, please leave a comment and tell us the codebreaking method you have used.


Further reading: An unsolved cryptogram from 1834

Linkedin: https://www.linkedin.com/groups/13501820
Facebook: https://www.facebook.com/groups/763282653806483/

Subscribe to Blog via Email

Gib Deine E-Mail-Adresse an, um diesen Blog zu abonnieren und Benachrichtigungen über neue Beiträge via E-Mail zu erhalten.

Kommentare (26)

  1. #1 Martin Gillow
    U.K
    3. Oktober 2018

    You say that you “do not know a single case where a Vernam cipher was used in practice”.
    During WW2, the Lorenz SZ40/42 (as cracked by Colossus at Bletchley Park), the Siemens T-52 Geheimschreiber and the Siemens T-43 are all based on the Vernam cipher. See http://www.cryptomuseum.com/crypto/vernam.htm

  2. #2 Klaus Schmeh
    3. Oktober 2018

    @Martin Gillow:
    The T-52 and the Lorenz machine don’t use a Vernam cipher in the sense I defined it here (the following page uses the same definition as I do: https://www.dcode.fr/vernam-cipher-vigenere). The cipher these machines used is adding a pseudorandom binary sequence to a binary cleartext. Today, this is called a streamcipher.
    The terminology is confusing, as Gilbert Vernam invented a crypto system that adds a binary string to a binary cleartext. This method is sometimes referred to as Vernam cipher, too, but it’s not identical to the one decribed here.

  3. #3 Narga
    3. Oktober 2018

    Oh wow, I got the third one: WASHINGTON and CALIFORNIA

  4. #4 Klaus Schmeh
    3. Oktober 2018

    @Narga: Great, this is correct. I guess, this was a dictionary attack.

  5. #5 Narga
    3. Oktober 2018

    @Klaus: I assumed you had taken a short phrase like “tobeornottobe” to make it more complicated and thus did not try a dictionary. Which would have made things easier in this case.
    Instead I just extended the scoring of my standard vigenere breaker to generate and then add a score for the key. It’s having a hard time with the longer ones, though…

  6. #6 Gerd
    3. Oktober 2018

    So the third one has a key that is as long as the message? Note this is not a Vernam cipher, and the solution given in #3 is as arbitrary as any other solution…
    I think an attack on a Vernam cipher should depend on the repeating key.

    Gerd

  7. #7 Klaus Schmeh
    3. Oktober 2018

    @Gerd: The Vernam cipher, as defined here, has no repeating key.
    I admit, this is confusing. There are two different definitions of the Vernam cipher in existence. The definition I use was taught at the University of Karlsruhe when I first learned about cryptography. It is also used on this page: https://www.dcode.fr/vernam-cipher-vigenere.
    Other sources, like Marc and Paul’s Cryptomuseum page, use the term “Vernam Cipher” differently. Their definition is equivalent to a stream cipher.
    It is certainly true that the name “Vernam cipher” for the cipher I described in my article does not make much sense, as it was not invented by Vernam. Does anybody know a better name? I have never heard of any other name being used for it.

  8. #8 Klaus Schmeh
    3. Oktober 2018

    >the solution given in #3 is as arbitrary as any
    >other solution
    If we assume that both the key and the cleartext need to be English words or phrases (a constraint that is stated in my post), this is not correct. There might be other solutions, but certainly not many.

  9. #9 Rossignol
    Paris, France
    4. Oktober 2018

    This cipher is known as Running key cipher:
    https://en.wikipedia.org/wiki/Running_key_cipher

    Solved by W. Friedman in Riverbank Lab. pub #16
    Methods for The Solution of Running-Key Ciphers
    https://www.marshallfoundation.org/library/digital-archive/methods-solution-ciphers/

    I found three articles in Cryptologia about the running key cipher.

  10. #10 Klaus Schmeh
    4. Oktober 2018

    @Rossignol: Thanks. “Running key cipher” is the term I am going to use from now on.

  11. #11 Norbert
    6. Oktober 2018

    For challenge no. 1, a quadgram-scoring-based attack yielded the following beginning:

    INTHETRADITIONOFTHE
    ONMONDAYNIGHTWEWILL

    The rest is unclear yet. Too bad both lines end with a word break… I am afraid it is a pencil-and-paper job (an Excel sheet helps).

  12. #12 Narga
    6. Oktober 2018

    @Norbert: with the same approach I got “STARTOURATTACK” / “ENLIGHTENMENTS” next. I guess that S at the end belongs to a new word…

    How do you do the monospace formatting in a comment? Is there an overview somewhere on which commands can be used to format comments here?

  13. #13 Marc
    6. Oktober 2018

    @Narga,
    use the HTML tags “code” “/code”

    • #14 Norbert
      6. Oktober 2018

      Yes, but there are some certain caveats: WordPress will continue to condense several spaces in a row to a single space character, even within a “code”-tag. To avoid this ruining your monospaced text, replace space characters by the html entity “non-breaking space”: [ampersand]nbsp[colon]. The same happens to “.”, use e.g. [ampersand]period[colon].

  14. #15 Marc
    6. Oktober 2018

    @Narga
    your key STARTOURATTACK doesn’t work !

  15. #16 Narga
    6. Oktober 2018

    Sorry, maybe not clearly written: I gota few words more than Norbert for challenge #1 out of my quadgram scorer.
    INTHETRADITIONOFTHEENLIGHTENMENTS
    ONMONDAYNIGHTWEWILLSTARTOURATTACK

  16. #17 Marc
    6. Oktober 2018

    @Narga
    Ok!

    Did you use hill climbing ? Because i use quingram score but didn’t get this solution. For the third challenge i got the same solution as you (WASHINGTON and CALIFORNIA)!

    • #18 Narga
      6. Oktober 2018

      @Marc: Yes, I used a very crude hill-climbing (randomly changing letters in the key) and quadgram-letter scoring.

      Thanks for the formatting hint!

      I also in the meantime tried scoring with dictionaries and all sorts of combinations of n-grams. But no luck. It seems pencil and paper or excel would do better, as Norbert said. The length of the text does not seem to play a major role in the difficulty of the deciphering (besides the obvious case of using only one or two words). Longer text is actually just more work to decode (unless a well-known text is used).

      I read this paper here https://www.aclweb.org/anthology/P12-2016 and got interested in using the viterbi algorithm (even though they think their method is better).

  17. #19 Rossignol
    Paris, France
    7. Oktober 2018

    I am not skeptical about this solution:

    INTHETRADITIONOFTHEENLIGHTENMENTSALONSTHATHELPED
    DRIVETHEAGEOFREASONANDT
    ONMONDAYNIGHTWEWILLSTARTOURATTACKMEETYOUATNINE
    ATSPRINGFIELDNORTHSTATION

    • #20 Narga
      7. Oktober 2018

      Very nice! Congratulations! What method did you use to solve it?

  18. #21 Rossignol
    Paris, France
    7. Oktober 2018

    I searched for the best quadgrams of the key but from the end backwards.
    I found the end of the message SPRINGFIELDNORTHSTATION and the end of the key DRIVETHEAGEOFREASONANDT
    For “DRIVE THE AGE OF REASON” Google give me this link

    https://www.skeptic.com/eskeptic/15-11-04/

    and the key phrase “In the tradition of the Enlightenment salons that helped drive the Age of Reason and the public interest…”

  19. #22 Klaus Schmeh
    7. Oktober 2018

    Great! Now challenges 1 and 3 are solved.
    Challenge 2 is still unsolved.

  20. #23 Rossignol
    Paris, France
    7. Oktober 2018

    Possible beginning of solution for challenge #2

    AUTUMNLEAVESHAVEC
    MEETYOUATMIDNIGHT

  21. #24 Narga
    8. Oktober 2018

    finally!

    AUTUMNLEAVESHAVECHASEDTHESUMMER
    MEETYOUATMIDNIGHTATMILLERSQUARE

  22. #25 Rossignol
    Paris, France
    9. Oktober 2018

    Good work. Not easy to find! Congrats.

  23. #26 Klaus Schmeh
    10. Oktober 2018

    @Narga, Rossignol: Great, your solutions are correct! This proves that virtually any running key cryptogram can be solved.