Pages

Monday 20 January 2014

A look at the second Feynman cipher [part 1]

In 1987, someone posted a message to an internet cryptology list, saying that Caltech Physics Professor Richard Feynman was given three samples of code by a fellow scientist at Los Alamos. Only one of the three was ever solved (see elonka.com).

The second cipher is as follows (I'm going to refer to it as "F2", feynman cipher 2 throughout the post):

XUKEXWSLZJUAXUNKIGWFSOZRAWURORKXAOSLHROBXBTKCMUWDVPTFBLMKEFVWMUXTVTWUIDDJVZKBRMCWOIWYDXMLUFPVSHAGSVWUFWORCWUIDUJCNVTTBERTUNOJUZHVTWKORSVRZSVVFSQXOCMUWPYTRLGBMCYPOJCLRIYTVFCCMUWUFPOXCNMCIWMSKPXEDLYIQKDJWIWCJUMVRCJUMVRKXWURKPSEEIWZVXULEIOETOOFWKBIUXPXUGOWLFPWUSCH

The first cipher was a plain route cipher, decrypting to some Chaucer. F2 has 261 characters, which factors into a rectangle 9*29, which means it could be a route cipher like the previous one, or a combination of route cipher and some other cipher. We will jump right into some analysis following this guide: Identifying unknown ciphers.

First of all, the monogram frequencies look nothing like English, so we can confidently rule out a plain transposition/route cipher. Next, the Index of coincidence is 0.045, which is too low to be a substitution cipher. From here I can reasonably confidently conclude it is not a transposition, monographic substitution or combination of these.

Another major signal is the presence of 26 characters; this means it can't be a cipher based on a 5 by 5 or 6 by 6 grid such as playfair, foursquare, phillips etc.

There are also all 26 characters appearing, so it is not ADFGX/ADFGVX or Polybius square. It is probably not trifid, since trifid uses 27 characters.

We can actually go further and rule out digraphic ciphers like bifid, hill, playfair and foursquare because the number of characters is odd. What does this leave? It leaves all the vigenere-type ciphers like gronsfeld, porta, autokey, beaufort etc.

Next steps

I will have to eventually make some assumptions and start cracking, but it is good to narrow the playing field a bit first. From here I am going to assume it is a Vigenere-type cipher with possibly some route-type transpositions going on. If we want to break route transpositions, we need to first identify the candidate routes we want to try. This will involve slicing up the 9*29 into various routes. Of course, the previous cipher was split into 75*5, so this one may actually be 3*87 instead of 9*29, but we can try that later.

If our block of text looks like:

XUKEXWSLZJUAXUNKIGWFSOZRAWURO
RKXAOSLHROBXBTKCMUWDVPTFBLMKE
FVWMUXTVTWUIDDJVZKBRMCWOIWYDX
MLUFPVSHAGSVWUFWORCWUIDUJCNVT
TBERTUNOJUZHVTWKORSVRZSVVFSQX
OCMUWPYTRLGBMCYPOJCLRIYTVFCCM
UWUFPOXCNMCIWMSKPXEDLYIQKDJWI
WCJUMVRCJUMVRKXWURKPSEEIWZVXU
LEIOETOOFWKBIUXPXUGOWLFPWUSCH

Then we can read off letters in various directions e.g.


XUKEXWSLZJUAXUNKIGWFSOZRAWURORKXAOSLHROBXBTKCMUWDVPTFBLMKEFVWMUXTVTWUIDDJVZKBRMCWOIWYDXMLUFPVSHAGSVWUFWORCWUIDUJCNVTTBERTUNOJUZHVTWKORSVRZSVVFSQXOCMUWPYTRLGBMCYPOJCLRIYTVFCCMUWUFPOXCNMCIWMSKPXEDLYIQKDJWIWCJUMVRCJUMVRKXWURKPSEEIWZVXULEIOETOOFWKBIUXPXUGOWLFPWUSCH

XRFMTOUWLUKVLBCWCEKXWUEMUJIEAMFRUFUOXOUPTWPMEWSXVUPOVTSLTSNYXROLHVHOTCCOZRTAJRNJFJOWGULMUWUBUSZGCMKAXIVHBIVBXBDWVMWRIUTDUTCMKUNKJFWYSXXKCVWKPKWPIMZOOOPUXGUKRRJXRUWWBCSCEKGFDRWVLDPOSVMURRLSWOPCIZIYELZTWDSYIEFRFOUVTQIPABIJVVKWWWLWCFFDZUUMYNSCJVSRKDVQCWXCOEXTXMIUH

HUIMXTXEOCXWCQVDKRSVJCSNYMUUZDFFCWLWWWKVVJIBAPIQTVUOFRFEIYSDWTZLEYIZICPOWSLRRUMVSOPDLVWRDFGKECSCBWWURXJRRKUGXUPOOOZMIPWKPKWVCKXXSYWFJKNUKMCTUDTUIRWMVWDBXBVIBHVIXAKMCGZSUBUWUMLUGWOJFJNRJATRZOCCTOHVHLORXYNSTLSTVOPUVXSWEMPWTPUOXOUFURFMAEIJUMEUWXKECWCBLVKULWUOTMFRX

HCSUWPFLWOGUXPXUIBKWFOOTEOIELUXVZWIEESPKRUWXKRVMUJCRVMUJCWIWJDKQIYLDEXPKSMWICMNCXOPFUWUMCCFVTYIRLCJOPYCMBGLRTYPWUMCOXQSFVVSZRVSROKWTVHZUJONUTREBTTVNCJUDIUWCROWFUWVSGAHSVPFULMXDYWIOWCMRBKZVJDDIUWTVTXUMWVFEKMLBFTPVDWUMCKTBXBORHLSOAXKRORUWARZOSFWGIKNUXAUJZLSWXEKUX

OEXTXMIUHRKDVQCWXCUMYNSCJVSWLWCFFDZUABIJVVKWWRFOUVTQIPZTWDSYIEFOPCIZIYELSVMURRLSWFDRWVLDPOWWBCSCEKGGUKRRJXRUIMZOOOPUXKCVWKPKWPNKJFWYSXXUTDUTCMKUXBDWVMWRIAXIVHBIVBUBUSZGCMKJOWGULMUWZRTAJRNJFLHVHOTCCOSLTSNYXROWSXVUPOVTXOUPTWPMEEAMFRUFUOKXWUEMUJIUKVLBCWCEXRFMTOUWL

ORUWARZOSFWGIKNUXAUJZLSWXEKUXEKMLBFTPVDWUMCKTBXBORHLSOAXKRXDYWIOWCMRBKZVJDDIUWTVTXUMWVFTVNCJUDIUWCROWFUWVSGAHSVPFULMXQSFVVSZRVSROKWTVHZUJONUTREBTMCCFVTYIRLCJOPYCMBGLRTYPWUMCOIWJDKQIYLDEXPKSMWICMNCXOPFUWUUXVZWIEESPKRUWXKRVMUJCRVMUJCWHCSUWPFLWOGUXPXUIBKWFOOTEOIEL

LWUOTMFRXECWCBLVKUIJUMEUWXKOUFURFMAEEMPWTPUOXTVOPUVXSWORXYNSTLSOCCTOHVHLFJNRJATRZWUMLUGWOJKMCGZSUBUBVIBHVIXAIRWMVWDBXUKMCTUDTUXXSYWFJKNPWKPKWVCKXUPOOOZMIURXJRRKUGGKECSCBWWOPDLVWRDFWSLRRUMVSLEYIZICPOFEIYSDWTZPIQTVUOFRWWKVVJIBAUZDFFCWLWSVJCSNYMUCXWCQVDKRHUIMXTXEO

LEIOETOOFWKBIUXPXUGOWLFPWUSCHWCJUMVRCJUMVRKXWURKPSEEIWZVXUUWUFPOXCNMCIWMSKPXEDLYIQKDJWIOCMUWPYTRLGBMCYPOJCLRIYTVFCCMTBERTUNOJUZHVTWKORSVRZSVVFSQXMLUFPVSHAGSVWUFWORCWUIDUJCNVTFVWMUXTVTWUIDDJVZKBRMCWOIWYDXRKXAOSLHROBXBTKCMUWDVPTFBLMKEXUKEXWSLZJUAXUNKIGWFSOZRAWURO

I am going to start with these 8 routes, and try to break them assuming they are any of the following: vigenere, vigenere-autokey, beaufort, variant beaufort, porta. I 'll also have to search all keys with lengths 2-20, and I'll be using the method described here.

Sources of Difficulty

While the code for the above tests is running, I thought I'd look at reasons why these experiments may not work. First is that it is not a cipher from the vigenere family, or perhaps it is e.g. a running key cipher, i.e. something I've not tried. Second is that the actual route is one I've not tried. The 8 routes from the 9*29 square are above, but i'll also have to try the same 8 routes from the 29*9, 3*87 and 87*3. There are many other routes I can't try. The last source of error I can see is mismatch between the plaintext language and the english model I am using to score fitness. The first cipher is Chaucer, which is old English and doesn't match up with modern english very well. There is a chance the cipher is in German or French or something too, in which case I probably won't break it.

The results of the above testing: I have run Vigenere, Vig-Autokey, Beaufort, Porta and variant Beaufort crackers on 64 possible routes for key lengths 3-20. I am fairly certain that if F2 was one of these ciphers it would have been broken. In the next post I'll broaden the search a bit.

4 comments:

  1. What do you make of the repeated "CJUMVR" string? Is it really in the original or could there have been a transcription error?

    If removed, that would make it 255 characters long, or possibly 15x17, so maybe you could try your analysis on that.

    ReplyDelete
    Replies
    1. I don't think it is a transcription error, this sort of pattern appears suprisingly often in english text (repeated blocks of 6 characters). This pattern can happen if e.g. a vigenere cipher is used with a key length that is a multiple of 6. I think this is an indicator that the cipher used has a block size of 3 or 6 e.g. length 3 or 6 hill cipher.

      Delete
  2. This comment has been removed by the author.

    ReplyDelete