Schneier on Security
A blog covering security and security technology.
« Car-Key Copier |
| Crypto Comic Book »
February 12, 2010
Nice article about a would-be spy and his homebrew pencil-and-paper cryptography.
Posted on February 12, 2010 at 11:21 AM
• 39 Comments
To receive these entries once a month by e-mail, sign up for the Crypto-Gram Newsletter.
and just think - he might have gone undected had he only use a spell checker :)
It's rather sad, he was apparently trained in cryptography but still used such simple cyphers. The book cypher is the best, since the key can be well hidden, but the other two are just silly.
The lesson I drew from this article is to once again consider your threat vectors carefully. He did a decent job of hiding his spy secrets but a terrible job of of preventing his legal jeopardy. Hiding the code on a piece of paper in his shoes. Yeah, that just looks innocent (sarcasm). Laptops existed in 2001. Even having that same data in several files on a computer in plain text would have made it much more difficult for the legal team to prove it had any connection to spying and in no way limited his ability to share that information with his contacts in Europe.
That seems so obvious to me that I can't help but wonder if that entire part of the story is simply made up. A code in his shoe. Come on, man.
Reminds me of a test I just did for a client. SSL is now unacceptable for government work due to failure to implement AES or 3DES. So everyone has shifted their protocol to TLS.
During testing I found that the TLS servers talking to IE 6&7 chose RC4 or other non FIPS compliant "weaker" ciphers anyway.
When I breifed the SAISO was told "Welllllllll...TLS 1 is mandatory but SSL3 is acceptable." Kibo FTW!
He was going to get caught no matter what spell-checker he used... he didn't think through it well at all, and he's a sloppy mind.
The guy is lucky to spend his life in a US prison. I can only imagine how things would have turned out for him if he had taken payment for secrets then forgot how to decrypt a whole section.
Hm. Random thought: Now that Google is scanning every book in sight, I wonder how hard it would be for them to break book codes by searching through the Google Books database for sequences of page/line/word that make semantic sense.
I wonder whether the NSA has wondered this too.
"a deal with the government to protect his wife from charges and get himself out of solitary confinement"
And this happened in America, not Iraq...
@5th It is likely his wife conspired along with him in his crimes, even though it isn't specifically mentioned in this article.
...and there was I hoping this article would be about cryptography and beer. You know, something like:
Code Bock & S-bock
Carlo Graziani >> Hm. Random thought: Now that Google is scanning every book in sight, I wonder how hard it would be for them to break book codes by searching through the Google Books database for sequences of page/line/word that make semantic sense.
I wonder whether the NSA has wondered this too.
Many years ago. The fun part is editions which depend on exact pagination and typefaces.
In general, criminals don't think that they'll get caught. It sounds to me like he was extremely worried about the possibility of trouble from his overseas contacts, but not about getting caught by American authorities. All his bizarre crypto stuff appears geared toward making sure that he can get his money and get back home without anybody changing the deal midway through. Seems plausible enough to me.
Fun story, but nope, no way, does not compute...
You expect us to think the Feds can not find CDs in a park? What about the NSA, CIA, etc?
Some many red flags, perhaps in early days, yes. But not 2001, and never in 2010+
Heck, a good dog might have been able to find the places where holes had been dug. Perhaps, even the Romans, could have gotten this guy.
Authorities often have a hard time finding entire bodies that arn't even buried, or buried deep. Consider that decaying bodies are far larger, and _stink_. I don't think that the three letter agencies have orbiting CD-ROM detecting satellites, but maybe I'm wrong...
The story is reminisant of the "Dimond Safe" story Bruce covered a while ago...
I won't say it came from the other end of the horse but the mouth I think not.
With regards book codes there are almost as many ways to use books for ciphers as there are books in the world.
You can even use them for "grills" with fixed pitch fonts.
One thing that should be noted is the simple addative cipher that can be used with a One Time Pad can also be used with a book.
If you just add one line of chars (mod26 or whatever) then it is not that difficult to break even without the book.
However the more lines you add the closer it aproximates the OTP.
Back in the 1980's it was said that four additive lines where sufficient to be effectivly unbreakable me I'm not so sure ;)
With the likes of project Gutenburg or as noted by Carlo Graziani Google getting "online book text" in several languages is not going to be that difficult.
However one book system that did amuse me is one that uses two pages of text as cordinates to another page of text.
You use a "message indicator" to pick three start points (pageA, sentanceA, pageB lineB, char inB, pageC, lineC, char inC). You then convert the sentance at the first (A) start point into a "frequency flatening matrix"
That is you take the first eight letters in "a sin to er" or "eat on irish lid" or other usefull phrase to remember the most frequently used letters in the laguage of the book. You assign these the single digits 0-7 the remaining letters of the alphabet get asigned the double digit numbers 80-99 (oh and two special chars such as '.' and ',' or figure/letter "shift" etc).
You then use this frequency flatening matrix to convert the text from the second (B) start point into numbers.
These numbers you use as a count to get the next char from the third (C) start point. This forms your faux OTP.
As simple as it sounds it is very error prone when done by a human but works well enough on a computer. And as many will note the faux OTP is not statisticaly flat (though that can be quite easily corrected ;)
There are any number of such systems that people have thought up and some people think them up for fun to make puzzels from to encipher a well known saying etc.
I find it fascinating that it should take the FBI codebreaker whiz "only" a couple of weeks to decode a rot-N message. Wouldn't it make sense, when you're approaching a code of completely unknown sophistication, to try the easy stuff FIRST? It can't possibly take more than three minutes to generate all 25 possibilities and scan them visually to see whether they resemble a human language, even if you have to code it up from scratch in Perl. Should give a good average return on investment given how many opponents turn out to be UNsophisticated.
Financial pressure appears to have been a factor. So the credit card company made say 6% on $116K, so about $7K/year, but the externalised cost to his nation which was how much? Millions? I'm rather interested by the process by which people draw issue boundaries, for example Bruce resolutely refuses to be drawn into a discussion about the cost / benefit of the foreign policies that result in many of the terrorist security threats he studies.
"I don't think that the three letter agencies have orbiting CD-ROM detecting satellites, but maybe I'm wrong..."
No but they do have "ground penetrating radar" that is usually good to 6ft these days especialy in what is essentialy "virgin forrest floor".
The thing about digging holes is it is very very difficult to get it right you need one heck of a sight more than just a shovel and a bit of plastic sheeting. You will actually need a brush, hand trowel, large knife, hardcore rammer, and several sheets of plastic.
The first and perhaps hardest part is to carefully remove the anual layers of leaf mould etc without mixing them up.
One way to do this is to "cut-n-lift" with the knife and either two sheets of plastic or one very stiff sheet about the size of an A3 sheet of paper. Essentialy you are cutting out your "turf" that has to be put back on top in the same place when finished.
You then need to dig down taking each of the different layers out in turn and putting them on different sheets of plastic.
The problem is as you do this you increase the "bulk" of each layer as you break it up.
When you have dug down deep enough you put your "bag" in and carefully put back that layer of soil back in. You then have to "knock it back" with the hardcore rammer to get the air etc out of it, and ensure the layer reaches the correct hight and density. Then the next layer and so on...
If you are trying to hide something then "virgin soil" is a very bad place to do it as Ground Penetrating Radar works on detecting anomolies. In a place like a city side walk the ground has been dug so often it is just one big acreation of anomalies. Out in the forest the soil may not have ever been dug by humans before...
So I'm siding with PackagedBlue on this one as Ground Penetrating Radar should have picked up clear indictions of soil disturbance even five years after it was dug in virgin soil...
I agree with the skeptics; it sounds more like a Dan Brown novel. That a supposed trained cryptanalyst even considered using a caesar cipher to protect important information is silly. That a team of professional cryptanalysts couldn't make heads or tails of it is absurd.
Yeah this whole taking weeks to break a Caesar shift thing is totally ridiculous, even if it was in German. I suck at programming, but even I could probably code something that could try to break a code based on a Caesar shift and check the words against different dictionaries.
Ditto on the comment above. What's sad is that a team of 12 NSA crypto analysts couldn't figure it out.
Either the story's bogus or there's a serious problem with NSA's code breaking abilities.
Hate to say it, but I'm siding with the naysayers. At the very least, the cryptanalytic effort and results were truly pathetic for the Caeser cipher. The yearbook I'd understand, but we were making and breaking better codes than the first in *high school.* That teams of NSA pro's could break the same kind of code... FAIL.
To all the "I don't believe they missed the caesar cypher" folks, I'm totally with you. It took me about 15 seconds to think up and type this on my computer:
for r in $(seq 1 25); do cat cypher.txt | caesar $r ; done
It says something about their programming skills.
Either the author is telling tales, or everyone in this story -- both the convicted spy and the people who caught him -- are absolute morons.
However, the basic facts of the Regan case can be confirmed elsewhere: the trial occurred as described, the defense did indeed portray him as a fool.
So, perhaps our domestic counterespionage efforts are run by people who wouldn't know a Caesar cipher if it bit them on the butt. A troubling thought.
It also reminds me of the early chapters of Bruce's Applied Cryptography. He mentions "classical" codes briefly, then dismisses them out of hand, partly because they're off-topic, partly because they're generally trivial to crack.
But this case, if true, demonstrates that these codes are worth knowing about, because real people use them for real shenanigans. And if it's your job to crack the code, you're going to look like a fool if you assume it's AES and it turns out to be Rot13.
Two hypotheses spring to mind, beside the author making things up:
1. FBI is deliberately spreading misinformation about how hard it is for them to break Caesar in a high-priority case, in the hope that small-time crooks will be suckered into thinking it safe to use.
2. Bureaucratic communications failure. The local case agent has no automated codebreaking tools, does not know a programming language, and figures it will take him hours to even have an attempt at Caesar with pencil and paper -- better ship it off to some central cryptanalysis department where they can probably go through those motions in minutes. On the other hand, the cryptanalysis desk assumes that their clients have already tried the standard easy codes (as regulation 12 C.I.P. 1127(d)(ii)(5) says they have to) and goes directly to work on more complex stuff.
@ Henning Makholm,
"On the other hand, the cryptanalysis desk assumes that their clients have already tried the standard easy codes"
Easy for whom?
Don't get me wrong but hand writen crypto is not the ordinary stuff of criminals thus LEO's and their LEA's Labs don't come across it that often. Which means their abilities are going to be minimal unless they have a personal interest (hobby) in the subject.
Although some people might be familier with the idea of making a frequency count few know what to do with it.
For instance with a Caesar in English language the charecteristic "RST" hump gets moved as well as the E&A spikes. I've met people (sadly no longer with us) who could actually read Caesar
The use of contact lists and binims/trinims is probably alien to them
However they could try reading the US Army Field Manual 34 40 2,
But in all honesty I would say they are wasting their time if they do. Not for any reason other than it is knowledge they are never likley to use, thus their time would be better spent else where.
Oh I'm not up on "regulation 12 C.I.P. 1127(d)(ii)(5)" which begs the question about how you are (as well as the track and Signaling system of a tram system in South West London ;) I guess hobbies come in all forms...
Like many others, I, too, was rather surprised that the Caesar code was so "difficult" to crack. I wrote a small awk script to do it in under 5 minutes. Of course, I had the advantage that I knew that it was a Caesar code, but still . . .
There used to be a Sunday puzzle in the San Francisco Chronicle called the Cryptogram which encoded messages in substitution ciphers that I did with pencil and paper back when I was in junior high and high school in the 1960s (no home computers back then). I wasn't any hot shot cryptanalyst and I could usually get the answer before the sun went down.
I'd think that with a straight Caesar code, the answer would jump right out at you, whether it was in German or not.
Either the reporter didn't get his facts quite right or there was some deliberate disinformation promulgated.
Some more thoughts on this case. 1, security pyschology, err, CEN SORE D, is vogue these days: why not this article?
2, while truth is stranger than fiction, 3, somebody let this play out for good old intel gathering, because many people were aware that a major terrorist event might happen, according even to the lame 9/11 commission report.
Can computer programs decrypt a strong test cypher that is then modified using notepad , before saving .
Eg:any program encrypting a sentance:
The cat jumped over the dog converted becomes:asdkasdagsuidgaisdkwjoteirutyierytksdfjsdknsldfkjskdfhksdfFRsdfsRREEG
Take this and you yourself know that you have to reverse the change before you use the program to decrypt it with the given password.
One could use "x(-2)-5 "as the default thus counting 5 places back from end , change to -2 places .(one can use their own formulae)
This means that the string FRsdfsRREEG becomes FRsdfsQREEG .
Can a computer or person be able to decrypt this .
Did this only out of interest and seems a viable way .One time pad on high octane sort of fun stuff.
If anyone for some unknown reason comes accross your password , it is useless.
bradlington: That achieves nothing more than effectively making "x(-2)-5" part of your password.
You have the choice between spending a certain amount of mental effort remembering the "x(-2)-5" bit, or spending the same mental effort on remembering a slightly more complex password for the underlying cipher.
If the latter does not give you at least as good an increase in security as the former, then the code you're using is worse than horrible, and you should worry about that instead.
@Clive - are you talking about finding the packages AFTER they decoded the coordinates and had dug that big hole, or are you talking about running ground-penetrating radar over an entire state park?
It sounds like the latter, in which case, I think it would take them a few hundred years to scan an average sized state park. I assume we're not talking about a few acres; the state parks around here are in the thousands of acres, and it's woods, much of it very difficult to even walk through, let alone run a penetrating radar over. I do geocaching and some of the areas I have been through have been very tough to get to, and sometimes even when you have the coordinates and are within 15 feet of the find, it can take a while to locate it, and these are not buried.
Exactly, and it's not like you can even count on the ground all having the same consitency in the area. It was a wooded area, no doubt with a good deal of wildlife, rocks, holes, etc. My guess is that if you were to scan the place with ground penetrating radar it would look like swiss cheese, with every single rabbit hole, sinkhole, buried stump, etc showing up as a change in density. I'm just not buying it.
"are you talking about finding the packages AFTER they decoded the coordinates and had dug that big hole, or are you talking about running ground-penetrating radar over an entire state park?"
After they decoded the coordinates and either just before or just after they dug the big hole.
GPR is quick over a small area (say 100 x 100 meteres or yards ;)
Soil resestivity tests are reasonably quick over larger areas of open ground (say 500 x 500 meters)
And there are various other air bourn tests that work over much bigger areas.
The problem is how virgin the ground is and how big the hole dug to bury the object.
GPR will pick up a small post hole, soil restivity possably not.
Something the size required to bury a body will be detectable from an air bourn system in flat open ground even a hundred years after the burial and despite the fact that the field has been top ploughed in more recent times.
But if this guy was burying hundreds of documents we are talking about quite a big hole, it is unlikly it was dug in an optimal way thus it may easily have been four or more foot or so in diameter. He did however show some good sense in some respects in that he did it in an aborial area. GPR will detect soil disturbance in such an area with only minor problems not so soil resistivity (tree roots are like poor conductors and go in various directions) and obviously trees mask the ground from many airbourn systems.
However they did know on thing that might well have aided their search even if they did not have anything other than an aproximate area. They knew that he had banged a buch of nails into a marker tree at each site.
How many trees can you check with a metal detector a day?
A single person could easily sweep a tree in 15 seconds with a standard security wand metal detector and walk to the next in another in less than 15 seconds. With a second person acting as trail finder / marker off you could be doing 1000 trees per two person team per day.
In open mature woodland (I don't know the actual terain we are talking about here so take this with a large pinch of salt) trees tend to be 50 feet diameter or so apart.
So as a poor aproximation you are looking at doing a standing avenue of trees 50,000 ft by 50 ft or 2,500,000 square foot a day. Which is aproximatly 500 * 500 meters area so four teams of two people could concevably do 1Km by 1Km area per day in the summer.
All considerably less risky than draging a GPR or soil geophysics package around. If people do ask then be honest and say you are looking for nails banged into trees. If people ask why say "do you know what a copper nail does to a tree?" and if they say no say "it kills it over about five years". If they then ask "but who would do that" say people setting up tempory hides for hunting/nature watching etc etc. You immediatly come across as a good guy and have the side effect you might actually stop some people banking nails into trees (three wins ;)
"My guess is that if you were to scan the place with ground penetrating radar it would look like swiss cheese, with every single rabbit hole, sinkhole, buried stump, etc showing up as a change in density."
You would be right to a certain extent but they all have charecteristics that distinquish them from each other.
As a very general and simplistic explanation,
When man diggs a hole it is markedly different to that of animals or roots of plants etc.
An animal generaly digs through layers and brings the spoil to the surface. Plant roots push the soil aside as they grow through. Thus the surounding layers remain intact.
However humans generaly dig a large hole put the object they wish to hide at the bottom and then chuck the soil back in, in a very random way breaking up the natural layers into places they should not be.
Thus a human made hole has a markedly different nature to one produced by a burrowing animal or growing plant root.
If your interested there used to be some stuff up on the web about it and I have some book refrences if you want them.
Oh and my iterest in Ground Penetrating Radar is a bit tangental. I was looking for any and all info a few years ago when designing a "cave radio" system.
Surprisingly there was at the time very little information on cave and other radio systems for emergancy tunnel and mine use (other than "radio waves do not penetrate the ground to any great depth" which is actually not compleatly true ;)
Homebrew cryptography is so easy. There are two good ways:
1. Nobody knows there is something to decrypt. If you do not expect to be there a message, you will not look for it. So a picture may hide a message very well (even if it would be easy to decrypt) or a story or playing a recorded music backwards.
2. Using user experience. It is nearly impossible to decrypt a message where you need private user experience as a background. Here an example. I made a phone call last thursday to a friend: "I call because of next weekend.", "Oh, great", "As usual?", "OK". So, what plan we agreed? This 'encryption' is hard to decrypt, right?
And if you can combine 1 and 2 you have an easy and effective homebrew encryption.
@Homebrewer: That is not encryption.
1 is steganography, 2 is a code.
Historically, the effectiveness of both against the efforts of a trained adversary has been grossly overestimated.
Item 2 is known as "veiled speech." Among professional eavesdroppers it is notoriously much weaker than its users think. It may be adequate for 1 or 2 messages, but when the channel is monitored for some time, it falls apart.
Even with your single message, a lot is already leaking. We know that you intended to do something on one of two days, which requires co-ordination with your friend. You have done this thing before, and intend to follow the same procedure. Your position in this group is that of the planner, but you are not in absolute authority. The phrase "I call because of ... " is stilted and overly formal for a call to a friend; possibly Homebrewer put that in for dramatic effect, but if the intercept target actually speaks like this, it suggests that English is not his native language, although he is well educated in this language.
More information could be had from a recording instead of a transcript: accent, tone of voice, etc. (For example: is "Oh, great" sarcastic or genuinely pleased? Is "OK" truculent, willing, or enthusiastic?)
The fact that the "usual" was agreed to, but nevertheless a coordinating call was required, suggests that either the date was previously unknown to the recipient, or else the "usual" plan does not occur often enough to be assumed.
The action being discussed is something that you fear being eavesdropped (although conceivably by a physical eavesdropper rather than a phone tap; maybe you just don't want your wife to know about the poker game.) Unfortunately in this case, the fact that there was to be no deviation from a previously agreed plan means that the recipient barely speaks, so we are not sure if he is also concerned about eavesdropping. If he was, that would increase the likelihood that you are concerned about a phone tap rather than a physical eavesdropper, which, in turn, would tend to suggest it might be a criminal enterprise. (Of course, you could just be paranoid -- but the fact that you actually are subject to a tap suggests otherwise!!)
That's what we can get out of 11 words. If the eavesdroppers had been monitoring this channel for some time, they could probably get a lot more. Now try my secret SMS (a coded message from a novel I am reading at the moment!), same number of words:
"Buyer set firm price, B4.19. (Howard Carson Cameron 2nd.)"
> GPR is quick over a small area (say 100 x 100 meteres or yards ;)
Only if the sled can move freely across the ground. In dense woods it could be excruciatingly slow. Of course I have no idea of the density of the woods where this occurred, but in the nearest national park to my current location there are plenty of patches were you would struggle to do more than 500 m per hour even without trying to drag a sled. Multiply that by by about 300 passes (to detect such a small target in a 100 m width) and you have about a week's gruelling work for each target site.
> Soil resestivity tests are reasonably quick over larger areas of open ground (say 500 x 500 meters)
Soil resistivity tests do not detect objects buried at a depth much less than the same order as the probe separation. Since this would likely be a very shallow burial, you would need an impracticably fine probe separation to detect anything.
> And there are various other air bourn tests that work over much bigger areas.
Only for large excavations.
> The problem is how virgin the ground is and how big the hole dug to bury the object. [...]
I believe, based on the description, that the hole would be no more than 1 ft square by a few inches deep. Plenty of holes like this are created by animals, the action of water, or rotting roots. Also as it was said that hikers walked past some of the pits while the FBI were at work, it is likely the area also contains many refilled pits from campers -- fire pits, and latrines.
> But if this guy was burying hundreds of documents we are talking about quite a big hole, it is unlikly it was dug in an optimal way thus it may easily have been four or more foot or so in diameter.
I disagree. The article doesn't really make clear how much was in each pit, but "thousands" of documents distributed among 19 pits suggests about 50 ~ 100 documents per pit. To take so many documents unnoticed -- indeed to have access to so many secret documents -- most of them are probably something like a technical memo: typically 2 to 4 pages, rarely more than half a dozen. Such a stack of documents is smaller than a ream of paper. You could bury it in a hole about 1 ft x 1 ft by a few inches deep. And since thieves are lazy, he was an office worker, and he was digging in the woods (notorious for the roots and rocks you strike about 2 mm below the surface!), I doubt he would have made it any deeper than the minimum he could get away with.
By the way, so we all can stop guessing the size of these parks, I looked them up.
Pocahontas State Park in Virginia is 7,600 acres or 3,100 hectares. Patapsco Valley State Park in Maryland is nearly double that: 14,000 acres or 5,700 hectares.
Schneier.com is a personal website. Opinions expressed are not necessarily those of BT.