Schneier on Security
A blog covering security and security technology.
« Friday Squid Blogging: Squid with Teeth |
| Hacking a Soda Machine »
November 19, 2007
Colossus Has Been Rebuilt
The World War II factoring machine, Colossus, is back online.
Not surprisingly, a modern PC is faster.
EDITED TO ADD (12/14): Some photos.
Posted on November 19, 2007 at 6:02 AM
• 14 Comments
To receive these entries once a month by e-mail, sign up for the Crypto-Gram Newsletter.
Just out of curiosity:
What is the "state-of-the-art" of the cryptanalysis againt rotor-machines nowadays?
Are they generally "broken" or is it possible to design secure machines given enough rotors and avoiding "bugs" like the Enigma's reflector?
Rotors appear to me as roughly equivalent to a number of fixed S-boxes, connected by a position-dependent permutation between each S-box.
That does not sound too bad, security-wise, does it?
Although I have never solved multi-rotor ciphers, I strongly suspect that rotor machines in general cannot be secure.
The trouble is, a lot of encrypted text is standardized blah-blah. The most common Enigma message was LAGE UNVERAENDERT (SITUATION UNCHANGED). It was 16 characters long, and due to the reflecting rotor no character could stand for itself (which would cause a short circuit). And it was enough to recover the day's key.
The American Cryptogram Association has a puzzle cipher, the Ragbaby, which is a single rotor cipher. With known text properly placed in the cipher, one reconstructs the rotor because you know the distance the two characters (plaintext and ciphertext) are apart on the wheel. The partial reconstructions allow the solver to divine other text elsewhere in the message, and continue the recovery of the rotor settings.
Similarly, the old Unix crypt() command, a single rotor cipher, is readily solvable the same way.
I'm not sure how to proceed when one rotor finally steps the next, but my cipher intuition tells me it is solvable.
And, PS. The Colossus was not used against the Enigma, but against the Lorenz (and IIRC Siemans) teletype ciphers. Bletchley Park called them the "fish" ciphers because BP named the German communications networks after various fish (Tunny, Stickleback, etc).
There were a number of crypto weaknesses of the Enigma machine, not least that a character never ciphered to itself. The other was that for a 26 character sequence it was a single wheel plus mirror machine. The Colossus and PC attacks were, I believe, a brute force attack based on these principles. The results are impressive even by today's standards.
However, what proved the weakness in the Enigma system was the human element: Messages sent in both a weaker and a stronger system; the same message sent with two different days code settings; and, messages from the same source sent with the same prefixes - all providing a vast number of known text strings that provided the less intelligent but mechanical bombes with the grist to, in some cases, break the day's codes in minutes rather than hours or days.
There's some interesting background to the breaking of these ciphers - by classic cryptanalysis, traffic-pattern analysis and also a sort-of injection-attack - in R.V. Jones's book "Most Secret War: British Scientific Intelligence 1939-1945" , London: Hamish Hamilton. ISBN 0 241 89746 7
The injection-attack trick was to shoot up an enemy lighthouse in a known location overnight - this would then force the encoding/transmission of a standard boilerplate damage-report form early in the day. Often this was the first message to be encoded by a given machine with that day's key-setting - intercepting this message and having a damned good idea of the content could vastly cut down the number of iterations needed to recover the day's key.
I visited Bletchley Park last spring, and got to see the Colossus working up close and personal! I have a couple of photos online
The second photo shows one of the members of the build-team operating it.
It's interesting to note that when I was there, someone asked the tour guide (not the guy in the photo) about how Colossus compared to modern computers. The tour guide told them that they had done some tests and found that modern PCs weren't significantly faster at the types of operations Colossus was designed for. I did mention that this was almost certainly not true, but I didn't want to be too much of a jerk about it.
Bletchley Park is also in the midst of rebuilding the a Bombe, one of the famous Enigma cracking machines, and there are a few pictures of that in my photoset, too.
@Stacy - Although the m4 project and Colossus attack different ciphers. The M4 project deserves some revisiting.
Bruce wrote of m4 here http://www.schneier.com/blog/archives/2006/02/...
Two of three messages fell quickly. The third refuses to yield and the network has been working on it for 20 months. Some of this is due to the network getting smaller. The other possibility is that the last message is not solvable with this approach as the message may be a special format, or garble.
@Tanuki - injection attacks have been reported elsewhere, such as Hinsley and Stripp’s Cobebreakers. Standing operations were setup to drop mines from planes in the same places in obvious sight of the enemy. The aircrews running these obviously observed missions must have thought the people that thought them up were daft.
@Paeniteo - interestingly, a soft-enigma , where you could have every possible rotor has a larger keyspace than DES. (I recall that excluded symmetrical rotors. It briefly conjures up absurd visions of fleets of supertankers following submarines around to carry the enigma rotors.) Of course, on top of the other problems of small key space, infrequent stepping, reflection, you get weak rotors.
If I read it right Churchill ordered details of Colossus destroyed and presumably development stopped, it left me wondering whether the UK would have developed it's own Intel if the UK had gone down a different path.
@David J. Bianco - Bletchley Park have now finished their Bombe rebuild project. It was switched on in July.
I read that the Brits were selling Enigma machines to other countries after the war, claiming that they were "unbreakable". The same article suggested that this was why Bletchley Park was kept secret for so long.
With regards to Colossus vs. modern PC's, one thing to keep in mind is that the claim might have been true ten years ago, even if it's not now.
'it left me wondering whether the UK would have developed it's own Intel if the UK had gone down a different path'
We had our own Intel: we had Ferranti and English Electric, there was a whole computer industry in the fifties a large number of whose high-up engineers had met one another during the war in an undisclosed location near Milton Keynes.
Unfortunately, we also had 1960s industrial policy, which forged ICL and then got terribly uncompetitive.
I've been away from a computer for awhile so I'm catching up on my RSS feeds and came across this story today.
I'm shocked and amazed no one mentioned this.
Probably one of my favorite movies ever.
Schneier.com is a personal website. Opinions expressed are not necessarily those of Co3 Systems, Inc.