Schneier on Security
A blog covering security and security technology.
« FBI Stoking Fear |
| Terrorism Survival Bundle for Windows Mobile »
November 28, 2008
1941 Pencil-and-Paper Cipher
Fascinating photo and explanation.
Posted on November 28, 2008 at 6:30 AM
• 31 Comments
To receive these entries once a month by e-mail, sign up for the Crypto-Gram Newsletter.
So does anyone know how secure a pen and paper cipher can be (other than OTP)?
Given enough time, you can do everything a computer can. Just remember to burn the papers with your computation after you're done.
And don't forget to burn the papers appropriately, that is, mix up the ashes thoroughly. Usually text written on burned but otherwise undisturbed paper can be read with the plain eye.
The main difficulty with pencil-and-paper ciphers is getting enough entropy in the key to make it secure against computer cryptanalysis. I used a deck of cards in Solitare because I couldn't think of anything easy-to-use that had anywhere near enough entropy.
@Dunn: Bruce made a pencil-and-paper cipher called "Solitare" for Neal Stephenson's book Cryptonomicon. It's meant to be done by hand using a deck of cards, but stand up to a full computer-based cryptanaylisis.
Unfortunately, it turned out to have some bias in its PRNG:
Still, I'm hoping some cryptographer will take up the challenge of making a strong pencil-and-paper crypto.
It is interesting to note the paper strips.
First off they are numbered at the top (1-18 as far as I can see). But also they are (oddly) of differing alphabet length, sugesting there is a previous stage that was not recorded.
The two first stages both appear to be 18 columns wide
I'm not sure what the intermediate step is (the one that looks like filling under the bell curve)
Then there is the odd maths at the top right of the squared page (whish I could read all the digits).
My gut feeling on the paper strips is that the person is anagraming a transposition cipher of (possibly) 18 chars wide (or 3/6/9/12/18) possibly found from a simple letter pair spacing test.
But the odd lengths sugests there is some previous stage, unfortunatly I can not read the letters well enough to tell how the stages relate to each other 8(
The paper strips are just transcribing the columns from the pyramidal tableau handwritten on the graph paper above it; the columns are muddled up, but they're numbered.
The sum at the top right reads "99+56=155=146+9". The '55' is repeated, but that might be just because of the crossing out. If you read the message down in columns, there are 11 columns of 9 (99) and 7 columns of 8 (56)--probably he was just counting the characters in the message.
Further to what jim has seen I note that the "pyramidal tableau" consists of two parts (upper and lower) in different colours or densities.
It would appear that the lower part is directly related to the tableau above (11 cols of 9 and 7 cols of 8) and the upper pyramidal hat written above it.
Hmm time for some more eye strain.
I've just spotted something interesting. If you read across the middle rows of the paper strips, you see the original message. I don't know where the extra characters at the tops and bottoms come from, though.
A transposition (anagram encryption)cypher can be detected because it's letter frequencies are the same as the native language.
I'd imagine that there is an inherent weakness in this technique because the frequency of pairs of letters is also well defined.
-Taping Khan Gyp Shiv-
It's an anagram cypher. The key is the arrangement of the columns from 1-18. You write down your message in 18 columns, rearrange them according to the key, and then read down the columns grouping in 5s.
You wouldn't need all that pyramid stuff if you were encrypting, but it would probably make it easier to decrypt, since it would be tricky to get your rows to line up. You'd figure out how many rows you needed, complete the pyramid, type up the columns and then just line them up and read off the message. Since the cryptographer has the original message in front of him, I suspect that what he's doing is double checking to make sure it was encrypted correctly.
Chess board, or better yet, Go board, could be used for fairly extensive cryptographical operations if you were inclined to do so..
I'm pretty sure (non-valid) Go board shapes can have enough entropy to a last computer attack.
(Normal Go has 19x19 grid with 3 possible states in each intersection. Also, bigger boards have been used infrequently.)
I suspect as you can read the middle lines you are unlike me not using a mobile phone with an 1.25 x 2 inch screen.
With regard to the pyramid hat or extra chars (as I cannot read them) I'm guessing that they are a cyclic offset backwards and forwards in the original cipher text. And that the plain text you see is where the correct offset jybes.
"A transposition (anagram encryption)cypher can be detected because it's letter frequencies are the same as the native language."
It is fairly easy to avoid or fake with a simple post cipher encoding stage.
If you remember either,
"a sin to err" or "eat on irish"
They give you the most frequently used letters in written English. If you assign the first seven to the numbers 1-7 and the other letters of the alphabet to 80-99 (selecting one for figure/punctuation shift) then you have effectivly flattened the frequency charecteristics of the plain text.
If you use an number OTP to encrypt and then use the above to post code the numbers back to letters it looks very much like a transposition cipher (and reduces the amount of morse etc required).
Likewise if you use a transposition cipher and post code to numbers it looks like you have used an OTP.
Obviously you would make it a little bit more difficult by using something like a pass phrase (from a book etc) to jumble the letter to number mappings.
Either method adds considerable effort to Eve and friends workload when analysing the cipher text.
There are other similar tricks using nulls etc to make life hard, but one of the simplest is "Russian Coupling" where you split the message in two at a known point and send the second half first.
@Clive: Blimey. If you're reading on a mobile phone, I see what you mean about eye strain--it's hard enough on a full-sized monitor.
Re the extra characters: Exactly right. Because the columns are scrambled and of different heights, some of the letters end up in the wrong columns when the ciphertext is written out in the grid (the dark section of the tableau). So you copy letters from the previous/next columns into the pyramidal section to make sure that each letter appears at least once in its proper column. Then you can just line them up, as he's done at the bottom.
I don't know, I just remember Etaoin Shrdlu. Then again, I'm probably dating myself by saying that.
Personnally I find "Estonia" easiest to remember. As long as you avoid mixing it up with Latvia or Lithuania.
RC4 is feasible as a pencil and paper cipher. (Actually it's easier with a set of tiles and a grid, saves an awful lot of erasing that way)
The problem is key management - asymmetric crypto is hard hard hard.
Ah - so the use of the hat diagram is decryption only. This suggests that the suspicion of the original post (on the other blog) is incorrect - this *is* decoding, not encoding.
Back to the picture - the message size calculation was used, along with the advance knowledge of "18 columns" to split the message into "hat tree strips", where the beginnings and endings of strips 'overlap'. The calculation in the top corner is likely needed to determine the size of the hat diagram, and the overlap needed along the way.
The strips are then moved back and forth, and up and down, until portions of the message start to appear - for example "DUNN", or "SECHS". Then clusters of strips can likely be moved together - back and forth, and up and down - until the entire message starts on the first full line, and the whole message can be read beginning to end.
The hat diagram strips would only be needed during the code-breaking process. Even decoding would assume that you knew the "key order", and thus the strips would be unnecessary.
This also suggests that the key is dynamic. If the key was *not* always changing, you would only have to break it once, and you then just decode.
I did notice that when I looked more closely at the key sequence, the numbers appears to show pattern. Perhaps the key was structured to depend on a date or other information so that although the key always changed, it was predictable enough to allow the working key to be generated from a memorized process. Although you would have to make notes while encrypting, you could destroy those quickly, and there would be no written code book to give you away if you were searched.
You'll notice that as he built the hat diagram on the quadrille paper, the letters that were added at the top of the grid were in a different color (or perhaps in pencil as opposed to pen. And you'll notice the up-and-down line that is sketched in at the bottom of the original grid.
The letters that were added above the original grid and the letters below the divider line do not have to appear in the plaintext. (Or rather, they do need to appear, but they need to appear either at the top of the pliantext grid or at the bottom, but they don't need to appear at both. The letters in between appear only once, and have to be a part of the plaintext, where they stand.
The top of the orginal grid and the line at the bottom mark the limits within with each column can be shifted.
Speaking of paper & pen cyphers: Are there any public key versions out there?
From my perspective it appears that this photo shows the successful decipherment of a single columnar transposition. One reason is that the photo shows the plaintext message but not the actual code word used as a key for the transposition.
This was not necessary top secret information, because single columnar transpositions were bread-and-butter ciphers for cryptanalysts before the second world war. The US Army Signal Intelligence Service (Friedmann, Kullback, Sinkov) was clearly capable of breaking such ciphers as well as the Germans -- for instance Figl at the Secret Police (Reichsicherheitshauptamt).
The cryptanalysis method used was Anagramming. The cipher text was seperated into stripes (columns of the transposition). The cryptanalysts looked then for stripes with good contact, meaning that the contained a higher number of probable bigrams (e.g. TH or the famous QU for English). Columns belonging together in the plain text must contain a higher number of probable bigrams. Most cryptanalyis books for classical ciphers explain it.
The American Cryptogram Association is probably the US group most knowledgeable about such ciphers. Members still practice on what used to be military-grade ciphers before machine cryptography became widespread.
If you can get a copy of Cryptanalysis, by Helen Fouche Gaines (I think that's the right title), it will give you a lot of information on ciphers like this.
"RC4 is feasible as a pencil and paper cipher. (Actually it's easier with a set of tiles and a grid, saves an awful lot of erasing that way)"
Would a Scrabble board be good then? :)
Perhaps you could get some sort of randomness from picking out the letters from the bag/box...
Häyhänen's cipher, commonly referred to as "VIC" after his codename, was considerably more complicated than just a straddling checkerboard. It used 3 stages, of which a straddling checkerboard was the main component of stage 2. It also used a lagged Fibonacci generator modulo 10 (a.k.a "chain addition"), and two variable width columnar transpositions with random message keys, the second of which was a disrupted transposition. The lagged Fibonacci generator is a potentially very strong component, although curiously the one they used is *not* maximal period.
What all this illustrates, I guess, is that it is certainly possible to create secure pencil-and-paper ciphers, IF you are prepared to take a sufficiently long time on the encipherment of each letter.
"Check out the SECOM cipher, it's a little complex but VERY secure."
There are a couple of things wrong with it that will make it both stronger in use and easier to send correctly.
The first part of it turning the letters into numbers and flatening the frequency is very much as I described further up this blog page.
However when building the letter to number "checkerboard" it should be from a key phrase.
The seven letters should be selected from a larger set in,
"Eat On Irish L" = aehilnorst
And used in the order they are found in the key phrase.
The last three unique letters in this key phrase should be used to pick the gaps.
So the pass phrase of,
"The time of man is but four score years and ten,
For women it is a greater lot of plus ten years"
theioan and ars = 189 which gives a top row of,
The other non "Eat On Irish L" chars in the passphrase shold be pulled as they are,
The remaining non used "Eat on irish l" letters should be put in reverse alphabetical order (srl), followed by the special charecter (*) and then any unused non "eat on irish l" letters (jkqvxz).
This string is pre appended to the used non "eat on isrish l" letters and split into the two lots of ten,
The numbers should be scrambled by asigning 12...90 to the first ten unique letters that are not in the "eat on irish l" set.
Then reading back wards from the end of the pass phrase the numbers are selected uniquly in revers order.
So with the passphrase,
"The time of man is but four score years and ten,
For women it is a greater lot of plus ten years"
The numbers are,
Giving the first encoding checkerboard as,
A second checkerboard needs to be made up from a different passphrase, which is used after the transpositions to convert the numbers back into alpha charecters. The special charecter gets converted to any random single digit number that is not easily confused with a letter (23456789).
Although the system might be known to the enamy the use of different checkerboards and passphrases renders it virtualy impossible to break without knowing the three pass phrases in use.
And just to make it more difficult, whilst still in the number form, split the message at some passphrase derived point and swap the two parts over.
Surprisingly with a little practice and squared paper it is actually not a difficult system to use.
You can also add "hidden" security/"turned" checks fairly easily as well.
Just remember what ever method you use for your key phrases they should only be used once and not from a recognised source like a news paper etc otherwise the system can be broken...
I have come up with a cipher idea that I believe (in my mind) pretty secure. Any ideas how I can have it tested?
Schneier.com is a personal website. Opinions expressed are not necessarily those of BT.