Cipher Text

National Treasure

2007-01-01T18:15:00.000+01:00

Happy New Year!

Anyone remember National Treasure from 2004? The film itself, something of a Da Vinci Code style adventure starring Nicolas Cage, wasn't that great. However, it had some fun DVD extras. One was a short featurette on codes and ciphers, and in the background were various things flying about, including a few rather obscure historical cipher machines; none of these machines were mentioned in the featurette itself.

Your challenge, if you choose to accept it, is to identify the three cipher machines and the cipher machine component depicted in the following screen captures (click to enlarge).

Stuart Milner-Barry

2006-12-29T15:45:00.000+01:00

Cipher Text is back! Apologies for the lack of activity here for most of 2006, hopefully I'll be posting more frequently in 2007. Anyway...

Last week I revamped the Wikipedia entry for Sir Stuart Milner-Barry, chess player, civil servant, and the head of Hut 6 at Bletchley Park from October 1943. He is particularly remembered for co-authoring a letter directly to Winston Churchill requesting more resources for the codebreakers, bypassing the apparently ineffectual leadership at Bletchley Park. The letter, which was also signed by Alan Turing, Gordon Welchman and Hugh Alexander, outlined their needs for a relatively small number of additional clerical staff in order to carry out their work effectively. Milner-Barry delivered the letter in person to 10 Downing Street in October 1941. After reading it, Churchill, who was a keen consumer of Bletchley Park's product, memo'd his staff with the terse but unambiguous "Make sure they have all they want on extreme priority and report to me that this had been done." With "ACTION THIS DAY" stamped above it in big letters. It seemed to have the desired effect.

Herivel Tip

2006-02-18T11:25:00.000+01:00

Bletchley Park has announced a forthcoming lecture by WWII veteran codebreaker John Herivel, a Hut 6 mathematician who, within weeks of arriving at BP, had come up with a nifty bit of lateral thinking to help solve Enigma. Dubbed the Herivel tip or Herivelismus, it relied on Enigma operators taking a shortcut and not randomising the rotors after having set up the machine. If you're interested, I wrote up the details in a Wikipedia article. It was Hut 6's lifeline for a few months in the Summer of 1940 after the Germans had changed their indicating procedure, obsoleting the Polish techniques then in use.

Herivel's tip reminded me of combination locks, of the type with rows of dials of digits. On university campus, I've noticed that many people in a hurry don't really scramble their combination locks (for cycles, normally) very thoroughly -- maybe a quick flick of the dials with the thumb, or something of that sort. As a result, the state after a half-hearted scramble still reveals information about the secret combination. I did some tests (on a lock of my own, of course), and if you observe several of these states, and you have a reasonably accurate model of what weak scrambling method is being used, you can whittle down the possibilities pretty quickly. Still, a good old-fashioned pair of bolt cutters is less hassle...

Marian Rejewski on Wikipedia

2006-01-06T01:37:00.000+01:00

The Wikipedia article on Polish mathematician Marian Rejewski is currently going through the process to become a so-called "Featured Article", vetted entries that are eventually promoted on the main page and elsewhere.

Feel free to read the article and add any comments. The page for the Featuring process can be found here.

Despite having something of a girl's name, Rejewski was a veritable geek hero, solving the wiring of the German Enigma machine using some funky maths. It's more than possible that, without Rejewski's results, the British at Bletchley Park would have had little, if any, success with Enigma.

Rejewski also had a more exciting wartime experience than his counterparts at Bletchley Park, who were all off playing rounders in relative safety. From September 1940, Rejewski worked with a small unit on breaking Nazi ciphers from within occupied (well, Vichy) France, under the continual threat of discovery and arrest. After being nearly discovered by a detector van equipped with a radio antenna, the unit was evacuated. Aided by the French resistance, Rejewski worked his way to the border and attempted to cross over into Spain. He didn't have much luck at this point: robbed by his guide at gunpoint, captured by Spanish police only hours after crossing the border, and then interred for three months in prison.

After his release, he made his way to Britain. You might assume he would join the codebreakers at Bletchley Park on Enigma, since their work had built on his. Instead, he was assigned to a unit working on low-level codes; a decision that one former British codebreaker described as "like using racehorses to pull wagons". It's difficult to tell what motivated this apparent injustice -- perhaps a need for security, particularly since the British had developed more advanced techniques than those of Rejewski, and the future of Poland itself was uncertain. It's also possible that the relevant authorities did not know of the Polish contribution to the British work. Most of the few that had known were no longer immediately involved with Bletchley Park.

Regardless, Rejewski deserves to be remembered as one of the "greats" in crypto history.

National Cryptologic Museum

2006-01-05T17:56:00.000+01:00

Adjacent to the NSA headquarters in Maryland, USA is the National Cryptologic Museum, a museum of cryptology and NSA history open to the public. It's surely second only to Bletchley Park as the ultimate day out for crypto geeks (if geeks had days out, that is).

Regrettably, I've not had chance to visit -- it's a bit of a trek from the UK -- but the next best thing is a superb set of photos posted to Flickr by Austin Mills which document a large proportion of the museum's exhibits. The photos are high enough resolution to be able to read the captions and see the details of the various machines.

From the archives: Mercury

2006-01-01T17:40:00.000+01:00

I had chance to spend a day at the UK National Archives a couple of weeks ago, and came across a file (AVIA 65/977) discussing cash awards to the designers of Mercury, an on-line cipher machine used by the RAF from 1950 to the 1960s. I wrote up all the information I could glean about this machine in a Wikipedia article.

Mercury embodies a similar principle to the US SIGABA (ECM Mk II) machine: some rotors control the movement of other rotors. It would appear that Mercury was an independent reinvention of the concept, as the ECM was around a decade older. The ECM concept had been kept secret from the UK by the US, and a Combined Cipher Machine (CCM) was used instead for inter-allied communication.

Another feature of Mercury appears to be that of "double rotors". Exactly how this worked wasn't clear from the PRO documents, but one plausible guess is that there were two independent wirings inside each rotor core, and that these wirings could be set in 26 offsets from each other, and optionally reversed. The current would pass once through the "inner" wiring, and then back again through the "outer" wiring. Ordinary Typex rotors had a "double" contact feature used to improve the reliability of the electrical contacts; this could have been pressed into service as a double rotor feature. Each pair of double rotors would, of course, step together.

British rotor machine: Singlet (BID/60)

2005-11-14T15:03:00.000+01:00

It's fun to see more information on rotor machines entering the public domain. For example, the Swiss NEMA machine was declassified in 1992. More recently, lots of information on the Soviet rotor machine Fialka (M-125) has been published on the Internet. There's even been a loosening of information about the US/NATO KL-7 system.

This year, a British rotor machine named Singlet (BID/60) was put on display at Bletchley Park in the superb Enigma and Friends exhibit put together by David White and John Alexander. There doesn't seem to have been much -- if anything -- written about this machine in the open literature.

The caption at Bletchley Park reads: "Singlet was used mainly by the British intelligence services C. 1949 / 50 onwards. This is a `Cold War' machine using wired rotors to achieve secure messages. We are very grateful to the Foreign and Commonwealth Office and GCHQ for this opportunity to show `Singlet' here at BP."

Singlet has windows and stepping levers for ten rotors. The rotor tube appears to be a detachable section, labelled BID/60/3, while the base unit is labelled BID/60/1. There is a hint of a connection to the KL-7 in this naming. According to George Mace on Jerry Proc's KL-7 page, the KL-7 components were originally labelled as follows: "the base unit was AFSAM 7/1 (aka KLB), rotor stepping unit AFSAM 7/2 (aka
KLA) and rotor basket AFSAM 7/3 (aka KLK)." The rotor tube, stepping levers and the keyboard are also all somewhat suggestive of some sort of link or common ancestry with the KL-7.

Some photos can be found on Wikipedia/Commons: 1, 2, 3, 4 and 5.

"Cryptography is not Sudoku"

2005-11-11T13:02:00.001+01:00

In 2002, David Kahn gave a speech to an NSA audience arguing that "cryptanalysis is dead". However, he went on to say that, "though traditional cryptanalysis may be dead, and may have been mostly a corpse for half a century, other opportunities, perhaps more opportunities, lie ahead." Kahn suggested increased opportunities for interception, side-channel attacks, placing back-doors in exported equipment and software, and so forth.

Maybe Kahn is right. I toy around with the following pet conspiracy theory: the recent promotion of codebreaking puzzles and competitions on the NSA and GCHQ websites is misdirection, and an indication that these agencies aren't actually doing a lot of pure cryptanalysis any more. Why would a codebreaking agency call attention to the fact that it breaks codes? Well, a target nation could think, "NSA and GCHQ are about using mathematics to read ciphers. They might still be breaking the systems of [insert developing country here], but our methods are mathematically impregnable, so we don't need to be concerned". Meanwhile, GCHQ or the NSA are compromising their communications through other means.

Anyway, enough with the tin-foil hat stuff. My apologies. Moreover, there's the occasional rumour that cryptanalysis is actually alive and well, as in the recent case of Iraqi leader Ahmed Chalabi. Wikipedia relates the story:

"In June 2004, it was reported that Chalabi gave U.S. state secrets to Iran in April, including the fact that one of the US's most valuable sources of Iranian intelligence was a broken Iranian code used by their spy services. Chalabi allegedly learned of the code through a drunk American involved in the code-breaking operation. Chalabi has denied all of the charges."

Who knows what lies behind this story? Still, a couple of days ago, a reporter speculated that Chalabi broke the codes himself, as he has a doctorate in mathematics. I very much enjoyed the incredulous comments given at the Orbus Quintus blog by "badgerminor" in response.

Sudoku is great fun, by the way.

CryptoKids

2005-11-08T22:53:00.000+01:00

"We're the CryptoKids and we love cryptology. What's cryptology? Cryptology is making and breaking codes. It's so cool."

This is a little weird.

The NSA have a new kids site featuring the "CryptoKids", cartoon animals each with a passion for a different aspect of the fun world of SIGINT and Information Assurance.

The gang includes Crypto Cat (speciality: cryptography), Decipher Dog (cryptanalysis), Joules (engineering), Slate (mathematics), T. Top (computer science), Rosetta Stone (language analyst) and Sergeant Sam (Central Security Service). Each character has their own biography, and there's tons of games and activities: codes and ciphers, things to make at home, colouring pages, online games, recruitment information...

...wait...recruitment information? Oh yes. On the home page, there's a large button that says, "How can I work for NSA?" After all, "it's never too early to start thinking about what you want to be when you grow up". In fact, the entire thing seems to be something of a get-'em-while-they're-young recruitment project: the slogan is "America's CryptoKids: Future Codemakers and Codebreakers".

Don't forget, kids, "without NSA/CSS, American leaders wouldn't be able to talk to one another without the bad guys listening and they wouldn't be able to figure out what the bad guys were planning".

Personally, I would have thought that few kids old enough to be seriously contemplating a future in intelligence work would be young enough to still enjoy the capers of a gang of anthropomorphised cartoon animals (and a gang geekier than your average chess club, to boot), but I'm not complaining...I've got colouring-in to do!

RSA-640 factored

2005-11-08T12:36:00.000+01:00

One of the RSA challenge numbers, RSA-640, has been factored:

RSA-640 = 3107418240490043721350750035888567930037346022842727545720161948823
       2064405180815045563468296717232867824379162728380334154710731085019
       19548529007337724822783525742386454014691736602477652346609

Factor 1: 1634733645809253848443133883865090859841783670033092312181110852389
       333100104508151212118167511579

Factor 2: 1900871281664822113126851573935413975471896789968515493666638539088
       027103802104498957191261465571

The number, which carries a US$ 20,000 prize for its solution, was factored by F. Bahr, M. Boehm, J. Franke and T. Kleinjung using GFNS. The computation took 5 months on eighty 2.2 GHz Opteron CPUs.

RSA-640 is not the largest challenge number to be factored so far -- RSA-200 is larger (despite the confusing name, RSA-200 is 663 bits long, compared to RSA-640, which is 640 bits). RSA-200 was factored in May 2005 by the same team.

Cryptographic Hash Workshop

2005-10-31T23:22:00.000+01:00

A workshop on hash functions is underway today (31st of October) and tomorrow (1st of November) in Maryland, US. Sponsored by NIST, the aim is to respond to the recent collision attacks on SHA-1. Bruce Schneier has been liveblogging from the workshop.

Polish Pronounciation 101

2005-10-30T18:17:00.000+01:00

If you've read about the history of the solution of the German Enigma machine, hopefully you'll have found out at least a little about the valuable contribution of Polish codebreakers Marian Rejewski, Jerzy Różycki and Henryk Zygalski. These mathematicians broke Enigma many years before World War II, and passed on their techniques to the British only weeks before the invasion of Poland in September 1939. This gave British codebreakers at Bletchley Park a tremendous flying-start in breaking Enigma.

That's all well and good, and is now firmly established in the literature.

But a key question remains, at least for a native English speaker: how on earth do you pronounce the names of these Polish heroes? Well, I finally grew tired of constantly butchering their names ("Marian Ray-Joo-Sky", "Jersey Rose-Icky" etc), so I asked a Polish contributor (User:Halibutt) on Wikipedia if he might record their pronounciations for me. He kindly obliged, and has so far contributed pronounciations for Marian Rejewski, Jerzy Różycki, Henryk Zygalski, Biuro Szyfrów (the Polish Cipher Bureau), Pyry (the location where the Polish passed their techniques over to the British), and Maksymilian Ciężki (head of the Cipher Bureau's German section).

To listen to the sound clips, click the link after the name on the Wikipedia article. You'll need to be able to play Ogg Vorbis files (a free audio codec), and this page gives instructions on how to do this for various common media players.

User:Halibutt might well be willing to record other Polish pronounciations if anyone has any suggestions.

Peter Gutmann's Godzilla Crypto Tutorial

2005-10-29T19:22:00.000+01:00

Peter Gutmann's Godzilla Crypto Tutorial has been updated. This nifty resource consists of 784 slides, and whizzes through the major topics in modern, applied cryptography. It's likely to be just the thing if you need to cram crypto.

The Eight-Rotor Printing Enigma

2005-10-25T23:47:00.000+01:00

The German military versions of the Enigma are well-known because of the historical significance of their decipherment during World War II. However, there are some other lesser-known commercial versions of Enigma, and a remarkable example of one of these is on display in a museum in Budapest (first picture, courtesy Eric Tischer). While the standard German military model had 3 rotors, and even the high-security M4 machine used on U-boat networks had 4 rotors, this rare early Enigma model had no less than 8 rotors.

A paper by Louis Kruh and Cipher Deavours ("The Commercial Enigma: Beginnings of Machine Cryptography," Cryptologia, 26(1), pp. 1–16, 2002) includes a copy of a flier for this machine, titled "The Printing Enigma". This machine, which dates from the 1920s, is distinct from two other large and bulky early commercial Enigma variants (models A and B)

According to the flyer, the machine weighed about 50kg, and measured 65cm by 45cm by 35cm (length, width and height). It printed "the plaintext in original form with letters, numbers, punctuation, word divisions". I presume it did this using a figure shift mechanism, rather than having rotors with a large number of contacts, as that the rotors seem to be labelled A-Z. The machine also printed the ciphertext into rows of 50 and groups of 5 letters. There's not much information on it cryptographically, other than the somewhat obscure claims that it had "17,576 periods / each period is 15,777,450 symbols" and that "any one of the 227,304,461,200 can be input in half a minute".

If anyone has any more information about this machine, I would love to hear about it. I'd also be interested to know the translations of the words on the large keys, which seem to be labelled "Ziffernu Zechen Zwischenraum" and "Buchstaben Zwischenraum".

KASUMI broken

2005-10-22T12:14:00.000+01:00

KASUMI, also termed A5/3, is a block cipher used to secure 3GPP mobile phone communications. Israeli researchers Eli Biham, Orr Dunkelman and Nathan Keller have discovered a related-key rectangle attack on KASUMI that can break all 8 rounds faster than exhaustive search. The paper is to be presented at ASIACRYPT 2005 in December, but there is a technical report available online.

The attack requires 2^54.6 chosen plaintexts and ciphertexts, each of which has been encrypted under one of four different keys, and has a time complexity equivalent to 2^76.1 KASUMI encryptions. Clearly, this is not a practical attack by any stretch of the imagination (the alarmist title of this post notwithstanding), but it's an interesting result, and it invalidates some proofs about the security of the 3GPP protocols that had relied on the presumed strength of KASUMI.

Biham, Dunkelman and Keller have previously found serious flaws in the GSM stream ciphers A5/1 and A5/2.

Bletchley Park Mailing List

2005-10-18T17:45:00.000+01:00

The Bletchley Park mailing list has thrown up some interesting bits of news in the last few days. First up was a link to a Telegraph article on the finding of the original Zimmermann Telegram decrypt. The story's a little too involved to go into here in any detail, but the gist is that during World War I, Germany got caught red-handed scheming against the United States by British codebreakers. When this was made known in the US, public opinion shifted, catalysing the entry of the United States into the war (we're told). If so, then it's quite probably the most influential single piece of decipherment in history. The news is that GCHQ have managed to unearth the original decrypt which was presented to the American ambassador in London. (A different version of the decrypt is pictured here). I was also interested to read that GCHQ have an anonymous "official historian" who's working on a secret history of the organisation.

The second bit of news is an update on the Colossus rebuild, headed by Tony Sale. According to Sale, the Psi wheels are working; previously, I gather, only the Chi wheels were operational. This means that the Colossus rebuild can now emulate the Lorenz cipher machine and decrypt ciphertext into plaintext on machine, although just one character at present! Apparently, when the Motor wheels are hooked up, the rebuild should be able to perform a standard WWII procedure whereby the Colossus was used to decrypt the first few characters of a message to check the settings on the wheels.

Thirdly and finally, it seems there's some more news at Bletchley Park. Rather than being open all year round, they are now closing for winter (at least for normal visitors), from 1st of November 2005 to 1st April 2006. Quite a shame, really. The Trust are also selling off land and leasing part of Block D to property developers English Partnerships in order to raise money. There's rumours of a change in director, too.

KL-7 rotor machine on the HMS Belfast

2005-09-27T18:02:00.000+01:00

I was recently in London and had chance to spend a few hours on board HMS Belfast, a retired British warship now serving as a floating museum on the Thames. The ship was pretty fascinating (that is, it had big guns), but my main motivation for visiting was to have a look at their KL-7 cipher machine. The KL-7 was an advanced NSA rotor machine design (think "souped-up Enigma") introduced in the 1950s and used within NATO.

Although some details are still classified, quite a lot of information has emerged about how the machine worked. We (that is, the plebs with no security clearance) know that it used a scrambler consisting of 8 rotors, each with 36 contacts. It appears that some of the contacts were used in a "loopback" arrangement; that is, 10 of the contacts at the end of the scrambler were wired to 10 of the contacts at the start of the scrambler. This meant that the machine operated on a 26-letter alphabet, but that some outputs represented current which had passed several times through the scrambler. Here's a diagram of how this sort of thing works:

This feature would make cryptanalysis much more complex, as an attacker would have to take into account that an output could represent one, two, or more passes through the rotors.

One detail that's not yet known is precisely how the rotors stepped. We do know that one of the middle rotors was stationary during encipherment, and that each rotor had a detachable ring of plastic around its circumference with a series of bumpy bits. These operated microswitches to control the stepping.

While it was great to see a KL-7 exhibited on board the Belfast, I was a little miffed to find that it was poorly illuminated and, more damningly, that it was not even labelled.

Heilbronn Institute

2005-09-07T12:01:00.000+01:00

The ominously-named Heilbronn Institute is due to open next month. It's being established as a partnership between Bristol University and a obscure little British intelligence agency known as GCHQ. Apparently, the institute will be pursuing a research programme "into key areas of mathematics of interest to GCHQ".

Each researcher will get to spend half their time on their own personal stuff, and the other half working on GCHQ projects. The director is Elmer Rees (one of the world's leading mathematicians working in the field geometry, according to Wikipedia), and the deputy director is Richard Pinch, a "civil servant living in Cheltenham", albeit a civil servant with research interests in "computational number theory, the arithmetic of elliptic curves, algebraic combinatorics and public-key cryptography".

An illustrated guide to IPsec

2005-09-01T20:19:00.000+01:00

"An Illustrated Guide to IPsec" is an excellent introduction to IPsec, written by software/network consultant Steve Friedl. I've read a number of overviews of IPsec recently, and this is by far the clearest explanation I've found of the basic AH/ESP, Tunnel/Transport Mode stuff. A little while back Steve wrote "An Illustrated Guide to Cryptographic Hashes", which was similarly lucid and helpful. Hopefully, he'll be writing some more crypto tech-tips soon.

While the article is a good explanation of the basics of what IPsec does, sadly, the article doesn't really cover why IPsec is the way it is. I'd like to read an "apology" for IPsec, explaining the somewhat complex, convoluted and perplexing architecture, and what the expected uses are for the various modes.

MD5 collision visualised

2005-08-31T12:52:00.000+01:00

On this webpage, there's an illustration showing of the evolution of the internal state in an MD5 hash collision. I really need to sit down at some point and make the effort to understand the technical details of the MD5 collision attack. Here's the reference:

Xiaoyun Wang and Hongbo Yu, How to Break MD5 and Other Hash Functions, EUROCRYPT 2005 [7].

Review: Digital Fortress

2005-08-22T13:16:00.000+01:00

Dan Brown is famous as the author of The Da Vinci Code. One of his earlier efforts was Digital Fortress (available online here) a book about the NSA and codebreaking. Now, I don't mind it when writers who, when dealing with complex real-life topics, sometimes play a little fast-and-loose with the nitty-gritty details. After all, this is fiction, right? Sometimes changing details serves to improve the story. Sometimes it only matters that the author gets the broad picture across, because only geeks care about the minutiae. Well, in this novel Brown fails to get anything right; the plot is weak and contrived, the characters are ludicrous, the broad picture is incomprehensible and, yes, he gets the crypto details completely wrong.

Fortunately for me, I have a twisted sense of humour. I enjoyed reading this, solely because of the old "it's so bad it's good" thing.

So. This is a lazy review. Summary: the novel is bad, and very bad if you're crypto-savvy. Here are some choice quotes as evidence:

If Susan’s body had been lanky and awkward as a teenager, it sure wasn’t now. Somewhere along the way, she had developed a willowy grace—slender and tall with full, firm breasts and a perfectly flat abdomen. David often joked that she was the first swimsuit model he’d ever met with a doctorate in applied mathematics and number theory.
“Exactly. An algorithm that resists brute force will never become obsolete, no matter how powerful code-breaking computers get. It could become a world standard overnight.”
Susan pulled in a long breath. “God help us,” she whispered.
Enigma was history’s most famous code-writing machine—the Nazis’ twelve-ton encryption beast. It had encrypted in blocks of four. (The real Enigma weighed 12 kg - ed.)
Encryption algorithms were just mathematical formulas, recipes for scrambling text into code. Mathematicians and programmers created new algorithms every day. There were hundreds of them on the market—PGP, Diffie-Hellman, ZIP, IDEA, El Gamal. TRANSLTR broke all of their codes every day, no problem. To TRANSLTR all codes looked identical, regardless of which algorithm wrote them. (and to Dan Brown, software, compression methods, key-agreement algorithms, public-key encryption schemes and block ciphers all seem identical - ed.)
“I don’t understand,” she argued. “We’re not talking about reverse-engineering some complex function, we’re talking brute force. PGP, Lucifer, DSA—it doesn’t matter. The algorithm generates a key it thinks is secure, and TRANSLTR keeps guessing until it finds it.”
Caesar, she explained, was the first code-writer in history. When his foot-messengers started getting ambushed and his secret communiqués stolen, he devised a rudimentary way to encrypt this directives. He rearranged the text of his messages such that the correspondence looked senseless. Of course, it was not. Each message always had a letter-count that was a perfect square—sixteen, twenty-five, one hundred—depending on how much Caesar needed to say. He secretly informed his officers that when a random message arrived, they should transcribe the text into a square grid. If they did, and read top-to-bottom, a secret message would magically appear. (Brown's just described a columnar transposition cipher. I know it's a subtle point, but Caesar actually invented what's confusingly known as the Caesar cipher, a simple substitution cipher - ed.)
Over time Caesar’s concept of rearranging text was adopted by others and modified to become more difficult to break. The pinnacle of non computer-based encryption came during World War II. The Nazis built a baffling encryption machine named Enigma. The device resembled an old-fashioned typewriter with brass interlocking rotors that revolved in intricate ways and shuffled cleartext into confounding arrays of seemingly senseless character groupings. (It seems the only type of encryption Brown understands is transposition, but sadly none of the systems he names were transposition schemes. The Enigma didn't "shuffle cleartext", nor did the Caesar cipher. Most importantly, the rotors were made chiefly from rubber or bauxite, not brass. OK, OK, I'm nitpicking now... -ed.)

There's more, but I don't want to spoil them for you ;-)

Permanent home for Colossus rebuild

2005-08-19T13:51:00.000+01:00

It seems that some controversy about the future of the Colossus computer reconstruction at Bletchley Park has been resolved. Some background:

The Colossus computers were computing devices built during World War II to break high-level German teleprinter ciphers at Bletchley Park. They have a claim to being the first digital computers, but they were kept secret until the 1970s.

Tony Sale and his team have invested around 6,000 man-days over the last 10 years painstakingly constructing a functioning replica of a Colossus. The rebuild is sited in H Block at Bletchley Park, where an original Colossus was installed during WWII, and is quite an awe-inspiring bit of kit. For many people, it's the crowning exhibit at Bletchley Park.

Last year, Bletchley Park Trust decided to put H block up for sale. Quite why they did this, I don't know, but possibly to raise cash to keep the museum running. Their decision drew criticism from various quarters. One objection was that H block was of historical importance: the building is the "world's earliest purpose-built building erected specifically for electric computers". Moreover, selling H block would mean that the Colossus rebuild would have to be relocated. Tony Sale argues that moving the Colossus would be "a very complex and difficult operation and it is quite likely that Colossus would never work again." That, of course, would have been a tragedy.

Well, the news is that it seems the Colossus rebuild is now secured. I don't claim to understand the politics involved, but it seems that Bletchley Park Trust have acquired funding which means that H block will be kept, and the Colossus rebuild will be able to remain in its current position. See the press release issued today. On Sale's Codes and Ciphers Heritage Trust there's more information about H block.

Hopefully this means the Colossus rebuild will be available for viewing by the public again soon.

Tags: Cryptography, Bletchley Park, Colossus

Spooks with large hands

2005-08-18T16:45:00.000+01:00

A one-time pad (scanned in by Marcus Ranum from a book called KGB/CIA). I want one!

Visas for Chinese crypto researchers

2005-08-17T14:47:00.000+01:00

Here's a news article on why a number of Chinese crypto researchers, including two of the discoverers of the collision attacks on SHA-1, Xiaoyun Wang and Hongbo Yu, were unable to get visas to present their work at CRYPTO 2005. Actually, it doesn't really explain why, just that they were unable, despite the intervention of NIST. Seems pretty daft to me.

I enjoyed Adi Shamir's satirical take on this at the CRYPTO rump session, where he suggested that Wang having "attacked US government systems" and having expressed a desire to "create collisions" might have contributed to the visa problems...he even got away with using a September 11 fireball picture to make his point.

SHA-1 attack complexity reduced

2005-08-17T03:44:00.000+01:00

At the CRYPTO 2005 Rump Session, Adi Shamir just delivered a new result on behalf of Xiaoyun Wang, Andrew Wao and Frances Wao, on SHA-1. The complexity of the best attack for finding collisions is lowered from 2⁶⁹ to 2⁶³. Shamir speculates that it might now be plausible to search for SHA-1 collisions using a distributed Internet search.

CRYPTO 2005

2005-08-14T22:41:00.000+01:00

This year's CRYPTO 2005 starts today (14th) over in Santa Barbara, California, US, and ends on the 18th. Keep an eye out on Michael de Mare's blog (Cipher Boy) as he's threatened to blog a little from the conference.

Update: The CRYPTO rump session will be webcast this year, starting on Tuesday August 16th at 7:00pm Pacific (which I believe is GMT-7 in Daylight Savings Time, so that's 3.00am on the 17th of August British Summer Time).

Update 2: Slight change, apparently. It now starts at 7:30pm Pacific Daylight Time (3.30am BST). It'll be in Apple's Quicktime format, with a 300kb bitrate.

Cryptoogle

2005-08-14T13:42:00.000+01:00

Cryptoogle is not the world's first search engine for dead people; it's not even a Google project. Instead, it's a rather fun idea for encryption. The idea is that you encrypt information with a password that's a valid Google search term. A Blowfish key is generated from the search results, and is used to encrypt the plaintext.

So why do this? I'm not sure, really. The author argues that, because Google's search results change, the key will automatically expire at some point in the future. He also claims that this prevents dictionary attacks because an adversary is limited with the number of Google queries which can be made.

Well, there are much better ways of doing this sort of thing, of course, and deriving your secret key from information pulled over the insecure Internet is certainly not a workable strategy, but I thought it was a fun idea anyway.

Court case falls apart because of MD5 insecurities

2005-08-11T01:33:00.000+01:00

According to a post on the cryptography mailing list, an Australian court threw out a case against an (allegedly) speeding motorist because the speed camera images were secured using MD5. The defence argued that MD5 was a "discredited piece of technology". Indeed, the MD5 hash function was shown to have a weakness last August when a team of Chinese researchers announced that there was a practical method to generate collisions.

But it's not totally clear what's going on here. One possibility is that the speed cameras digitally sign the evidence, or more specifically, the MD5 hash of the evidence. To tamper with the evidence, you'd need to mount a second preimage attack, but, as far as I'm aware, nobody's come up with a way of doing this.

Another possibility is that the camera simply prepends the evidence with the MD5 hash, which provides no integrity guarantees, but that's got nothing to do with the security of MD5 per se.

Still, there's a great quote from the defence lawyer Denis Mirabilis: "People have shown it [the algorithm] has been hacked and it's open to viruses."

Update: Slashdot have just covered this.

US crypto export rules

2005-08-10T16:30:00.000+01:00

Apparently, in the US you have to declare a national state of emergency in order to continue on with various export restrictions on cryptography (Bruce Schneier informs us). I don't really care, to be honest. I'm just glad to be living in the great United Kingdom, an enlightened nation where the government doesn't have any draconian cryptography laws.

New chief spook

2005-08-09T15:05:00.000+01:00

The NSA have a new director, a Keith B. Alexander. He started work on the 1st of August, and he is the sixteenth director since NSA was created in 1952. The agency rotate the directorship amongst the Army, Navy and Air Force; Alexander is US Army, while his predecessor, Michael Hayden, was from the US Air Force.

One-time pads on paper tape in 2005!

2005-08-09T13:45:00.000+01:00

While browsing Dirk Rijmenants blog, I came across a link to Austrian company Mils Electronic. This company sells encryption products that implement one-time pads and proprietary ciphers; ring any warning bells? Well, rather than making any judgments on the company or their products, I thought I'd mention a few facts that distinguish this company from a stereotypical OTP snake-oil vendor.

First, they were founded in 1946, and have been doing one-time pads ever since. Second, they seem to be pitching their products at governments. Third, amongst other things, their random number generator can output to a...wait for it...5-channel paper tape puncher (pictured above left).

5-channel paper tape -- as in, pretty much the same one-time pad implementation Gilbert Vernam patented in 1919. I'm flabbergasted. Who's still using this stuff? I reckon you'd need a little over 4 meters for each kilobyte of information you encrypt.

The BID list

2005-08-08T15:29:00.000+01:00

British government crypto devices seem to all be assigned a BID code, one for each type of device. Because I'm a geek, I went and Googled and chucked together a list of BID codes together with any info about these devices I could find, although the details of most of them remain classified. I like the codenames, too -- they sound very mysterious and cloak-and-dagger, names like ALBERCOR, CRUCIBLE, NOREEN and, er, KITCHENMAID. Hmm, maybe not so cool after all ;-)

If anyone has any more info on BID devices, let me know.

All Hackers Need To Know About Elliptic Curve Cryptography

2005-08-05T12:56:00.000+01:00

In what's been touted as the "last ever" issue of hacker-zine Phrack, released at the beginning of this month, there's an article overviewing elliptic-curve cryptography together with a sample implementation. Written by the shadowy "f86c9203", it overviews a little bit of basic algebra and outlines a couple of key-agreement protocols. "Rootkits and backdoors seem to be interesting applications", claims the article, although it's not quite clear what great benefit ECC brings to your average black hat over conventional public-key crypto...I guess it just sounds cool, right?

ECRYPT Stream Cipher Project

2005-08-04T12:21:00.000+01:00

The ECRYPT Stream Cipher project is a project run by ECRYPT (an EU programme for cryptology and watermarking) to identify "new stream ciphers that might become suitable for widespread adoption". It guess this will be something a little like the Advanced Encryption Standard (AES) competition, but for stream ciphers rather than block ciphers (and they're just evaluating the designs, and not selecting a single standard). The call for primitives was first issued in November 2004, and they received a whopping 34 designs by the deadline last April. Some famous(ish) names have submitted or co-submitted designs, including Joan Daemen (MOSQUITO), Eli Biham (Py), Bruce Schneier (Phelix) and Daniel J. Bernstein (Salsa20).

Eli Biham and Jennifer Seberry note that their submission "Py" is pronounced "Roo, a shorthand for Kangeroo". This is because it's written in the Cyrillic alphabet, apparently. Ah..hah. A worthy attempt to carry on the recent tradition for bizarrly-named and unpronounceable cryptographic primitives, then.

The project has advertised for four "profiles" of stream ciphers that they're looking for, distinguishing between those that perform well on hardware and software, and those that include authentication built-in and those that do not.

It's going to take a while, though. By July 2006, they'll be selecting a subset of the designs as finalists, with the project due to complete in January 2008. Still, it looks like it'll be a lot of fun, with researchers finding flaws with each other's ciphers. There's a discussion forum and a list of papers.

If you're lucky, I might blog a little about each of the designs -- won't that be a treat?

sci.crypt problems

2005-08-03T10:03:00.000+01:00

The cryptography newsgroup sci.crypt appears to be having a few problems. In Google Groups, the very useful archive of past messages has vanished, and on my ISP's news server, the group doesn't even appear in the list of groups. According to one post, "sci.crypt is under massive attack, there are lots of forged cancel messages." Sounds unpleasant, although quite how cancel messages work — and how they might be forged — remains a mystery to me!

But even when working normally, sci.crypt is afflicted with a fairly poor signal-to-noise ratio; the good stuff is often buried under the copious output of trolls, cranks and flamewar participants...typical Usenet, really. An alternative that's worth checking out is the cryptography forum on the Security Forums website. One of those PHP-powered bulletin-board things, it seems to have some useful discussions and helpful regulars willing to answer newbie questions (without biting their heads off à la sci.crypt).

Review: M-209 simulator by Dirk Rijmenants

2005-08-03T00:33:00.000+01:00

I've finally got round to trying out Dirk Rijmenants' M-209 simulator. The M-209 (right) was a portable cipher machine used by the US in World War II (and afterwards), and was originally designed by Swedish engineer Boris Hagelin (even more info here).

For me, the M-209 (and related Hagelin machines which use the same mechanism) is quite possibly the most fascinating crypto machine ever made. Part of the appeal is that it's completely mechanical (unlike the Enigma machine, which was both mechanical and electrical in operation). From the outside, an M-209 appears to be a rather boring, green, lunchbox-shaped tin, but inside there's a fiendish array of pinwheels, gears, cogs, lugs, bars and other bewildering mechanical components. Maybe I'm just unduly scared by moving parts (I'm a CompSci/Maths person), but these machines certainly look how you'd want your cipher machine to look if you were trying to dissuade the enemy from even starting an attempt to crack your codes.

Appearances can be deceiving, of course, and the truth is that the M-209 was not particularly secure, and certainly less so than Enigma. In WWII, the Germans were reading M-209 traffic, although the machines were used only for low-level tactical communications. The machines were also used by the US in the Korean war, and devices using the same sort of "pin-and-lug" mechanism stayed in use even into the 1970s in various parts of the world.

Anyway, getting back to the simulator: if you want to tinker with this piece of cryptographic history, and if you don't fancy shelling out the USD$1000-4000 for which antique M-209's typically exchange hands on eBay, this excellent freeware software emulation of the machine (left) is the next best thing (for Windows only, sadly). Dirk wasn't content merely to reproduce the cryptographic operation of the device (which is more-or-less a simple stream cipher), but has painstakingly copied the appearance and construction of the M-209, even down to the screws. To operate, you have to turn the various (on-screen) knobs and handles, and the output is printed on (on-screen) tape, just like the real thing. Stuart Savory has tested the machine's output against that of a museum's M-209 and found them to be compatible. Being so faithful to the original has an inevitable downside, however, as the M-209 isn't a particularly intuitive device to operate, and you'd probably need to do some reading first if you're not already familiar with the machine. Besides the help files, another option would be to watch the original US Army M-209 training video.

Dirk has also created an excellent Enigma simulator in the same vein, and I'm looking forward to what he comes up with next!

GCHQ dispose of hard disks by dipping into nuclear reactor (allegedly)

2005-07-26T18:39:00.000+01:00

I just purchased Net Spies by Andrew Gauntlett from the local Oxfam bookshop. Published in 1999, it covers various issues about Internet privacy, including encryption. What made me buy the book, however, was not the exciting prospect of a pop-sci treatment of the perils of "The Net", but the following anecdote:

Paul Baccus, a technical engineer with an Oxfordshire based data-recovery firm, describes an extreme method of data-erasure: when GCHQ decommission old computers, they adopt a unique and somewhat extreme practice to ensure that no data can ever be recovered from discarded disks. Armed police escort unwanted GCHQ tapes and hard disks from GCHQ directly to the nuclear power station at Sellafield. There, they are dipped into the nuclear reactor, where the high levels of radiation permanently destroys the data. It also renders the remains of the disk highly radioactive further discouraging any attempt to recover residual data.

Yikes! But, hmm, I have to admit, I'm fairly skeptical about this. I mean, the expense of lugging the disks and tapes all the way over to Sellafield with armed police etc -- why not just blow the tapes up on site or something? I do get the feeling Net Spies might be a little flakey on that old minor issue of factual accuracy; I skimmed the book and found the following clanger:

A mechanical device known as the `Enigma machine' encoded the German's orders...Alan Turing, mathematician and father of modern computing, finally cracked the code in 1941 by constructing the world's first computer, which was named `Colussus'.

Well, it was called "ColOssus", wasn't constructed by Turing, and wasn't built to crack Enigma, but the thought was there, I suppose. (MSN Encarta have a similar mistake in their "Computer" article, so perhaps we can be forgiving).

If anyone has any information on GCHQ's methods of data erasure, delusional or otherwise, do let me know (assuming it's unclassified, of course, *cough*).