Puzzles Endanger, Then Save, a Nation: The Spy Who Couldn’t Spell

While working on our multi-part series of posts about the history of codebreaking in America during the 20th century, I mentioned that some of the recent revelations about the National Security Agency were the result of Edward Snowden’s actions during his time as a government contractor.

What you might not know is that he has not been the only contractor to sneak information off of government computers in that fashion: a decade before Edward Snowden, there was Brian Patrick Regan.

Regan was a career soldier in the Air Force who eventually reached the rank of Master Sergeant and worked in signals intelligence.

Buried under hundreds of thousands of dollars in credit card debt, Regan decided his only way out of financial ruin was to try to sell US government secrets to a foreign government. He copied page after page of sensitive documents from national defense systems and snuck them out of his office, eventually amassing more than 15,000 pages, CD-ROMs, and other material in his home.

He would later bury bundles of these documents in various locations, including state parks, concealing the GPS coordinates of these valuables caches through a complicated series of encryptions where letters and numbers became three-digit sets.

You see, Regan had spent a fair amount of time studying cryptography, and fancied himself a top-shelf codemaster.

Regan used another set of encryptions of lesser complexity when he attempted to contact agents of the Libyan, Iraqi, and Chinese governments in order to sell off the treasure trove of secrets he’d amassed during his time at the National Reconnaissance Office.

One of these packets — a collection of three parcels intended for Libya — ended up in the hands of an FBI agent named Steven Carr.

From The Spy Who Couldn’t Spell by Yudhijit Bhattacharjee:

In the first envelope was a four-page letter with 149 lines of typed text consisting of alphabets and numbers. The second envelope included instructions on how to decode the letter. The third envelope included two sets of code sheets.

One set contained a list of ciphers. The other, running to six pages, listed dozens of words along with their encoded abbreviations: a system commonly known as brevity codes. Together, the two sets were meant to serve as the key for the decryption.

Some of the document had already been decrypted by FBI agents, and it revealed a member of the US intelligence community — claiming to be CIA, which was unverified, but definitely someone with top secret access — was trying to sell government secrets.

And this person had terrible spelling.

Brian Patrick Regan suffered from severe dyslexia. And, despite concerted efforts to perfect both his encryptions and his plan to net millions by selling government secrets, that dyslexia would be one of the clues that led Steven Carr to Regan’s doorstep.

It took Carr six months to connect Regan to the Libyan package, but once he did, surveillance on Regan began immediately.

When Regan attempted to board a plane to Zurich in 2001 — intending to meet with Iraqi and Libyan embassy officials — he was nabbed by the FBI and taken into custody.

Again, excerpted from The Spy Who Couldn’t Spell:

On searching Regan, officials found a piece of paper tucked between the inner and outer soles of his right shoe, on which were written addresses of Iraqi and Chinese embassies in Europe. The other materials they found on him and in his belongings were more mystifying. In a trouser pocket, Regan was carrying a spiral pad containing a page with 13 words that didn’t add up to anything: like tricycle, rocket and glove.

He had another 26 random words scribbled on an index card. Among the contents of Regan’s wallet was a piece of paper with a string of letters and numbers that read “5-6-N-V-O-A-I …” And in a folder he was carrying in his duffel bag were four sheets with handwritten lines of three-digit numbers.

FBI cryptanalyst Daniel Olson decoded some of the messages found on Regan when he was captured, but he had failed to unravel the multi-stage encryptions that concealed where Regan had buried his secret parcels. The government knew which state parks, but with acres and acres of possible hiding places, they needed more precise information.

And those parcels were the key, because they weren’t just packages to be sold to the highest bidder. No, those parcels doubled as a ransom in order to secure a better deal for himself with the US government. He wanted to blackmail the government for a reduced sentence.

They were his insurance plan.

As Thomas G. West said in Seeing What Others Cannot See, a book about visual thinking and dyslexia, “It’s not hard for a dyslexic to think ‘out of the box’ because they have never been in the box.”

Thankfully, Regan eventually realized that cooperation was in his best interest, and he revealed that each of the elaborate three-digit codes concealed a backdoor key built into the code itself.

Regan designed them this way so that, if he forgot the actual details of the encryption, all he would need is the starter word, a spark that would unlock the built-in key and help him decode the entire message.

This backdoor key system worked in a similar fashion to the Vigenere cipher, where a keyword or key phrase served as the entry point for a longer string of encrypted text. The trouble is… you need to know the cipher word or source in order to crack the code.

For example, during World War II, German agents in Europe used Daphne du Maurier’s Rebecca as the basis of a code for transmitting intelligence from Cairo to support a campaign by the Axis powers against the Allies in North Africa.

The discovery of the book among the possessions of two German radio operators who didn’t read English ultimately led to the breaking of the code, which in turn led to the capture of the German spies in Cairo.

Regan revealed the cipher words for the various hiding spots in state parks — which used cipher words from sources as peculiar as Regan’s own high school yearbook — and soon, the FBI recovered all but one of the buried parcels.

But Regan couldn’t remember the cipher word for the last one.

Daniel Olson would then step in, having learned some of Regan’s techniques as they uncovered the other parcels, and partially decrypting the remaining message enough to spark Regan’s memory. Regan finally came up with the last cipher key, and the final parcel was recovered.

Yes, once again, puzzly perseverance had saved the day!

Regan was found guilty on two counts of attempted espionage and one of gathering national defense information, and sentenced to life imprisonment with parole. Which, quite honestly, is getting off easy, considering that prosecutors were seeking the death penalty for his treasonous acts. (If prosecutors had gotten their way, he would’ve been the first person executed for espionage since the Rosenbergs in the ’50s.)

For the full story, including more in-depth explanations of Regan’s elaborate encryptions, check out The Spy Who Couldn’t Spell by Yudhijit Bhattacharjee.


Thanks for visiting PuzzleNation Blog today! Be sure to sign up for our newsletter to stay up-to-date on everything PuzzleNation!

You can also share your pictures with us on Instagram, friend us on Facebook, check us out on TwitterPinterest, and Tumblr, and explore the always-expanding library of PuzzleNation apps and games on our website!

Puzzle History: Codebreaking and the NSA

ohr577n

[Image courtesy of NSA.gov.]

The National Security Agency has been in the news a lot over the last few years.

It arguably all started with Edward Snowden and the revelations about government surveillance, both domestic and foreign, that emerged in his wake. Between President Trump’s intimations of Obama-era wiretapping (which also supposedly involved England’s GCHQ) and recent news stories about NSA contractor Reality Winner leaking information, the NSA continues to draw mainstream attention in the 24-hour news cycle.

When you factor in the declassification of codebreaking intel during and after World War II, we know more about the NSA’s inner workings than ever before.

You might be asking what the NSA has to do with puzzles. Well, everything. Because the NSA was born as a codecracking organization.

enigma

The NSA was founded in November of 1952, but its formative stages began during World War II, as codebreakers were recruited in the U.S. starting in 1943. Not only were they tasked with tackling the German ENIGMA code, but their secondary mission was to solve “the Russian problem.” This group was known as Signals Intelligence, or SIGINT.

William Friedman, one of the early figures in American codebreaking, described cryptanalysis as “a unique profession, demanding a peculiar king of puzzle-solving mentality combined with patience. So staffing this new organization was a curious endeavor.”

Those who were recruited came from all walks of life:

Career officers and new draftees, young women math majors just out of Smith or Vassar, partners of white-shoe New York law firms, electrical engineers from MIT, the entire ship’s band from the battleship California after it was torpedoed by the Japanese in the attack on Pearl Harbor, winners of puzzle competitions, radio hobbyists, farm boys from Wisconsin, world-traveling ex-missionaries, and one of the World’s foremost experts on the cuneiform tablets of ancient Assyria.

04/11/14 imitation game - bletchley park, milton keynes

A large campus was built that echoed the style and efforts of Britain’s Bletchley Park, including Alan Turing’s calculating machines, the bombes. Efforts on both sides of the Atlantic centered on cracking ENIGMA, the German codes used in all sorts of high-level communications. The teams worked alongside the bombes to try to determine which of the 456, 976 possible codes was being used in a given piece of communication.

It was a truly Herculean effort.

But while nearly half the staff focused on the Germans, others focused on cracking Russian codebooks, where words were translated into four-digit codes. Often, decrypting these codes involved “brute force” efforts, poring through numerous messages to pair up messages that used similar numerical groups, meaning they used the same cipher.

This would only work if the Soviets were lazy in their production of so-called “one-time pads,” encryption devices that had a particular code, which would be used once and then thrown away. Brute force codebreaking revealed that some of the one-time pads had been used more than once, a lapse in Soviet security that could work to the advantage of U.S. intelligence.

That deduction led to another stunning discovery: cracking the system used in encrypted messages to tell agents which encryption was used in a given missive. You see, each encoded message contained within it a code that dictated the cipher necessary to decrypt the message.

The Russians would later complicate this work by employing multiplexers: devices that would transmit numerous messages at once, making it harder to separate one message from another in the same dispatch.

hqdefault6

[Image courtesy of Virtantiq.com.]

The Germans would unwittingly aid the US in their Russian codebreaking efforts when a POW camp in Bad Aibling, Germany, was captured by the US army, and they uncovered a German device designed to “de-multiplex” Russian messages. The device was called the HMFS, because Hartmehrfachfernschreiber, while a great deal of fun to type, is hard to say quickly.

After World War II ended, U.S. intelligence consolidated their efforts on “the Russian problem,” continuing their work unraveling the Russian codebooks. Slowly, the codemasters began determining which organizations in the Soviet government used which codes. Even if the codes weren’t broken yet, it helped the intelligence community organize and prioritize their efforts.

The problem? They had a very tight timeframe to work in. Those duplicated codebooks were produced during a very small window of time in 1942, and only issued to Soviet agents in the three years that followed. By 1947, SIGINT analysts knew the Soviets would soon run out of the duplicated pads. Once they did, those recurring patterns of encrypted numbers would stop, and the best chance for cracking the Soviet codes would be lost.

Still, there was reason to be encouraged. Some important code words had been identified. TYRE was New York City, SIDON was London, and CARTHAGE was Washington; ENORMOZ appeared often enough that they determined it referred to atomic bomb research in Los Alamos.

It would also be revealed, through careful analysis of decrypted intel, that Soviet agents were embedded in both the U.S. Justice Department and in England’s Bletchley Park campus. The Justice Department agent was identified and tried, but released after the court found insufficient evidence to place her under surveillance in the first place.

This was one consequence of the secrecy surrounding codebreaking: an unwillingness to reveal their codebreaking success by turning over evidence of it. (As for the Bletchley Park spies, one was identified in 1951 and confessed in 1964. The other was never identified.)

By this time, the Russians had gone over ENIGMA machines captured during the German retreat, and had unraveled not only how the devices worked, but how to improve upon them. This would lead to the next-generation Russian Fialka machine.

fialka

With ever-increasing complexity when it came to encryption, thanks to increased automation, codebreaking evolved into not just intelligence work, but intelligence analysis. After all, if you don’t know something is important, you don’t necessarily give it the attention it deserves. As researcher Stephen Budiansky put it, “The top translators at Bletchley were intelligence officers first, who sifted myriad pieces to assemble an insightful whole.”

It also led to bigger, faster machines, like Goldberg and Demon, two computation machines designed to more efficiently pore over the vast amount of encrypted information being intercepted by the various U.S. intelligence services.

In 1948, though, the game changed. It changed so dramatically that November 1, 1948, is still remembered in NSA circles as Black Friday.


I hope you’re enjoying this look at the early days of America’s codebreaking efforts. Part 2 will continue next week, with a look at the rise of the NSA, Cold War cryptography, and more!

[Quotes and certain photos were sourced from Code Warriors: NSA’s Codebreakers and the Secret Intelligence War Against the Soviet Union by Stephen Budiansky.]


Thanks for visiting PuzzleNation Blog today! Be sure to sign up for our newsletter to stay up-to-date on everything PuzzleNation!

You can also share your pictures with us on Instagram, friend us on Facebook, check us out on TwitterPinterest, and Tumblr, and explore the always-expanding library of PuzzleNation apps and games on our website!

Codecrafting with Crosswords!

We’ve discussed ciphers and codecracking numerous times in the past, and rightly so. It’s a style of puzzling that has literally affected the outcomes of battles, helped shape key historical moments, and changed the face of spycraft.

And it’s a puzzle form that continues to evolve to this day. We’ve moved far beyond the simple one-to-one replacement encryptions of your standard newspaper cryptogram, and intrepid solvers are always looking for newer and more devious ways to conceal their messages.

Tumblr user Cipherface has cooked up a pretty ingenious system that actually uses another style of puzzling in its execution: crosswords.

tumblr_nfh6mgvdtf1t4n39mo1_540

Here’s how it works. You write your message out in the open spaces of the crossword, ignoring the black squares.

tumblr_nfh6mgvdtf1t4n39mo2_r1_1280

Then, map out this diagonal path as the first step to encrypting your message.

tumblr_nfh6mgvdtf1t4n39mo4_r1_1280

Do the same with the puzzle’s answer key, and you’ve got your running key, the text used to substitute letters for the letters in your actual message.

table2

Then you run your message through the tabula recta, a table where you use the letter you want revealed and the letter in your running key to pick the letter in your encryption.

tumblr_nfh6mgvdtf1t4n39mo5_r1_540

Here, we can see Cipherface mapping out the encrypted message using this method.

From the Tumblr writeup:

The idea is to use a crossword puzzle for the transposition and the answers to the previous weeks puzzle as a running key. And the blank spaces are used to insert nulls into the final ciphertext. You then mail it to a friend who uses the date it was mailed to decide which puzzle to use for decryption.

It’s a pretty clever way to leave your encryption key in plain sight, and yet keep your messages secret. The running key keeps changing, so it’s more effective than traditional running keys, which stayed the same for longer periods of time.

Not to mention, using the puzzle’s publishing date? What a quick and easy way to keep your friend informed in an innocuous way. You’d just need to decide ahead of time which newspaper to use.

And it figures. The best way to make a puzzle better? Add another puzzle.


Thanks for visiting PuzzleNation Blog today! Be sure to sign up for our newsletter to stay up-to-date on everything PuzzleNation!

You can also share your pictures with us on Instagram, friend us on Facebook, check us out on TwitterPinterest, and Tumblr, and explore the always-expanding library of PuzzleNation apps and games on our website!

The Diabolical Long Division Brain Teaser!

From time to time, I’ll receive an email with a brain teaser I’ve never seen before. Sometimes they come from friends, or fellow puzzlers. Other times, PuzzleNationers will ask for my assistance in solving a puzzle that has flummoxed them.

That was the case with today’s puzzle, and I’ll admit, this one was a bit of a doozy to unravel.

longdiv1

Yup, an entire long division problem with only a single digit set. No letters or encryption to let us know which digits were repeated, as there are in Word Math puzzles published by our friends at Penny Dell Puzzles.

Just a 7 and a bunch of asterisks. “Is this doable?” the sender asked.

Yes, this is entirely doable, friend. Let’s break it down step by step.

First, we need to know our terminology. The 8-digit number being divided is our dividend. The 3-digit number we’re dividing into it is the divisor. The 5-digit number on top is our quotient.

For the other lines, let’s label them A through G for ease of reference later.

longdiv2

There we go. Now, where do we go from here? We start with what we know.

We know that 7 is the second digit in our quotient.

So our divisor, times 7, equals the number on line C. That’s a 3-digit number, which means the first number in our divisor is 1. Why? Because if it was 2, 2 times 7 would give us 14, which would be a 4-digit number on that line.

longdiv3

That means the quotient is somewhere between 100 and 142. (Why 142? Easy. I divided 1000 by 7, and 142 is the last 3-digit number you can multiply 7 against and still end up with a 3-digit answer for line C. 143 times 7 is 1001, which is too high.)

What else do we know from the puzzle as it stands?

Well, look at lines E and F. We bring both of the last two digits in the dividend down for the final part of the equation. What does that mean?

Remember how long division works. You multiply the divisor by whatever number gets you closest to the given digits of the dividend, subtract the remainder, bring down the next digit from the dividend, and do it all over again until you get your answer.

You multiply the first digit of the quotient times the divisor to get the number on line A. You multiply 7 times the divisor to get the number on line C. You multiply the third digit of the quotient times the divisor to get the number on line E.

Following this route, you would multiply the fourth digit of the quotient against the divisor to get the number on line G. But bringing just one digit down didn’t give us a number high enough to be divided into. Instead of needing more lines (H and I, in this case), we bring the last digit of the dividend down and press onward.

That means the fourth digit of the quotient is 0, because the divisor went into the dividend zero times at that point.

longdiv4

And there’s more we can glean just from the asterisks and what we already know. We know that every one of those 4-digit numbers in the equation begin with the number 1.

How do we know that? Easy. That first number in the divisor. With a 1 there, even if the divisor is 199 and we multiply it times 9, the highest possible answer for any of those 4-digit numbers is 1791.

So let’s fill those numbers in as well:

longdiv5

Now look at lines D, E, and F. There’s nothing below the 1 on line D. The only way that can happen is if the second digit in line D is smaller than the first digit on line E. And on line F, you can see that those first two columns in lines D and E equal zero, since there’s nothing on line F until we hit that third column of digits.

That means the second digit on line D is either a 0 or a 1, and the first digit on line E is a 9. It’s the only way to end up with a blank space there on line F.

longdiv6

I realize there are a lot of asterisks left, but we’re actually very close to knowing our entire quotient by now.

Look at what we know. 7 times the divisor gives us a 3-digit answer on line C. We don’t yet know if that’s the same 3-digit answer on line E, but since it’s being divided into a 4-digit number on line E and only a 3-digit number on line C, that means the third digit in our quotient is either equal to or greater than 7. So, it’s 7 or 8.

Why not 9? Because of the 4-digit answers on lines A and G. Those would have to be higher than the multiplier for lines C and E because they result in 4-digit answers, not 3. So the digit in the first and fifth places in the quotient are higher than the digit in the third. So, if the third digit in the quotient is 7 or 8, the first and fifth are either 8 or 9.

So how do we know whether 7 or 8 is the third digit in the quotient?

Well, if it’s 7, then lines C and E would have the same 3-digit answer, both beginning with 9. But line C cannot have an answer beginning with 9, because line B is also 3 digits. The highest value the first digit in line B could have is 9, and 9 minus 9 is zero. But the number on line D begins with 1, ruling out the idea that the numbers on lines C and E are the same.

That makes the third digit in the quotient 8, and the first and fifth digits in the quotient 9.

longdiv7

We know our quotient now, 97809. What about our divisor?

Well, remember before when we narrowed it down to somewhere between 100 and 142? That’s going to come in handy now.

On line F, we know those first two digits are going to be 141 or below, because whatever our divisor is, it was larger than those three digits. That’s how we ended up with a 0 in our quotient.

So, the number on line D minus the number on line E equals 14 or below. So we need a 900-something number that, when added to a number that’s 14 or below, equals 1000 or more. That gives us a field from 986 to 999.

And that number between 986 and 999 has to be divisible by 8 for our quotient to work. And the only number in that field that fits the bill is 992. 992 divided by 8 gives us 124, which is our divisor.

longdiv8

From that point on, we can fill out the rest of the equation, including our lengthy dividend, 12128316.

longdiv9

And there you have it. With some math skills, some deduction, and some crafty puzzling, we’ve slain yet another brain teaser. Nice work everyone!

[After solving the puzzle, I did a little research, and apparently this one has been making the rounds after being featured in FiveThirtyEight’s recurring Riddler feature, so here’s a link.]


Thanks for visiting PuzzleNation Blog today! Be sure to sign up for our newsletter to stay up-to-date on everything PuzzleNation!

You can also share your pictures with us on Instagram, friend us on Facebook, check us out on TwitterPinterest, and Tumblr, and explore the always-expanding library of PuzzleNation apps and games on our website!