Schneier on Security
A blog covering security and security technology.
« College Degrees in Homeland Security |
| Tracking Vehicles through Tire Pressure Monitors »
April 9, 2008
NSA on the Enigma
Excellent and well-written article.
Posted on April 9, 2008 at 1:52 PM
• 20 Comments
To receive these entries once a month by e-mail, sign up for the Crypto-Gram Newsletter.
Having read several books on Enigma, only having read this do I clearly understand how it worked. Well written.
For fun, here's a "paper" Enigma machine (sans ring-settings and plugboard).
Simon Singh's "The Code Book" has a detailed description of the history and mathematics involved in breaking Enigma.
It is one of the best books on a technical subject I have ever read.
An interesting read. I couldn't help but think of Cryptonomicon while reading it. Most people don't realize that without the contributions of those clever mathematicians and cryptanalysts, the Allies might not have won the war.
The curious thing is, after February 1942, Doenitz had what essentially amounted to positive confirmation that the Allies had been reading the three-rotor Naval enigma, since the decline in sinkings that had begun in the Spring of 1941 was suddenly reversed with the introduction of the fourth rotor. He must have felt that his suspicions had been justified by the evidence, at that point.
Nonetheless, when the war turned against the U-Boats again in the Spring of 1943, there is no evidence that I'm aware of that he (or anyone else in the German High Command) felt that there was a new problem with Enigma communications, and no further serious cryptological reform was attempted. I wonder why his intuition failed him the second time, when it had been reliable the first time.
It shows how the German Navy sticking to policy and procedure paid off in a big way as compared to their military counterparts. Unfortunate for the allies, of course.
From the article: The Germans connected the plugboard to the input rotor alphabetically. Later, when the British learned of this simple connection, they were astonished. They had never tried an alphabetic connection in their early attempts to break the Enigma.
Interesting detail: "Woman Enigma Cracker Was Dissed"
How can you check to see if your home is being monitored by hidden cameras, and whether your computer is being remote monitored?
As a woman renting a room a room in someone else's home, it's very important to ensure your privacy has not been violated.
Is there some security program you can run on your computer, or some gadget you can buy to scan and see if a camera is hidden somewhere in your home.
Thanks for the link the that really well written story! It's also the first story I've read that says anything about the success of the German cryptanalysis.
Note the U-110 incident was the basis for the movie "U-571". Except in the Hollywood version, it wasn't the Brits who scored the coup, it was the USians.
This makes no sense:
"Since the German cipher clerk determined the initial rotor settings, they had to be sent to the intended recipient in the clear, that is, unenciphered. The first three letters of the code group, sent unenciphered, told the receiver where to set the rotors. The following six letters were the ciphered letters (repeated) of the settings for the rest of the message. They were sent twice in order to avoid garbles in transmission. For example, the clerk might send HIT in the clear.
The receiver set his Enigma rotors to read HIT through the windows and then typed the next six letters in the message, KOSRLB. These were the indicators. The letters that lit up (LERLER) told him where to reset his rotors. Changing his rotor settings to read LER through the windows, the receiver now decrypted the rest of the message. "
As I understand it, the message key was encrypted with the daily key, so in the above example, HIT would never be sent.
This was really interesting. I live near Dayton, so I have read a fair amount about the NCML. But although "brute forcing" a rotor machine is fairly self-explanatory, I was always curious how they arrived at a "crib" (as they call it here) to decide when they had a valid decode. Neat.
Had a brief look and notice one or two very obvious errors but no the less it is interesting.
The most obvious error is the 26^3 number of rotor steps. This is actually not true to a design fault in the odmeter movment.
I will finish looking at it and see how many more I can spot over the weekend 8)
It appears that the major attacks on Enigma were due to a single fault in the construction: The reflector, which prevents a letter enciphering to itself - thus making the whole "crib" approach possible.
The rest appear to be operational or protocol errors (such as enchipering the same text in a weak and a strong cipher).
I wonder how a rotor machine (suitably enhanced to use, e.g., 16 rotors out of 256, and NO reflector ;-) would stand against "modern" cryptanalysis.
Probably DES made research into the area obsolete, but are rotor machines, as an algorithm class, considered completely "broken" nowadays?
to answer bonsai, google 'spyfinder camera detector" to find a cheap devise that can be used to find the reflection of a laser pulse from a camera lens.
all cameras have some lens and every lens will refract to this devise I assume.
there is another cheap devise called a camera detector, this one detects the radio fresquencies that a transmitting camera is sending and just beeps.
Some more expensive ones will actually detect the radio emanations from the beat frequency ocillator. this will help locate the devise as its sensitive to proximity.
We were at Bletchley Park yesterday, and it was amazing to see the Mk2 Colossus rebuilt and working with it's 60 year old valves and tape reader reading 5000 characters a second.
Tony Sale has his virtual Colossus program here for those wanting to try their hand at cracking Lorenz.
p.s. Hut 8 is now open for Turing fans.
There is an interesting side story to the Enigma at blackbag
The use of a reflector it's self was not a significant weakness.
Most of the original attacks relied on using "messages in depth" that had a common indicator.
It was the use of a reflector that was,
1) incapable of encrypting to it's self, and
2) a very small alphabet size, used with
3) very structured messages, that were
4) two or more times in length the size of the alphabet.
As well as still looking at messages in depth.
It is one of the reasons block ciphers have 64 or more bits, their alphabet is then effectivly 2^64 bits and also why they should never be used in "Code Book" mode.
Also it is unlikley that a message would be 2^65 * 64 bits (2^71 or aprox 10^24) long.
This however might just be a consideration for a designer of a secure Database or backup system ;)
As for rotor based systems being secure they only substitute the alphabet they do not in any way effect it's fundemental structure so like all fixed key short duration stream ciphers they will always fall prey to certain classes of attack.
So as an "off the top of my head" analysis of your example of 16 rotors would be a stream cipher with a fixed key length of 26^16 (say 2^75 if my brain is working)
Which you could argue would be aproximatly similar to using a 64bit block cipher in counter mode under a fixed key as a stream cipher generator.
That is you might consider it for occasional private use between a couple of people but not for any mainstream use (where you would expect messages to appear in depth).
I don't know if others would take a different view but it would be interesting to hear their reasoning.
Hi Clive, thanks for your late but insightful answer!
A question: When you assume the complexity to be 26^16 don't you assume 16 fixed rotors in a fixed order?
How is it that rotor choice would not affect complexity?
Or do you mean the maximum length of the keystream before it repeats? Still, there would be numerous such keystreams, depending on which rotors are used.
How does RC4 fit into that picture? It seems like is has a very small alphabet, as well but it is successfully used for enormous messages (AFAIK it is even the case that the major weakness of RC4 is in short messages, as the early keystream bytes might leak key bits).
RC4 looks like one large rotor to me that changes permanently. The same notion could be applied to a multi-rotor machine (the substitution function of all rotors combined changes permanently, too).
I could imagine that RC4's changes of its rotor are - despite its simplicity - more "chaotic" than the changes that a rotor machine does...
As for your usage suggestion, that's more or less exactly what I had in mind -- I do not aim to replace SSH/SSL/GnuPG with rotor machines... ;-)
Schneier.com is a personal website. Opinions expressed are not necessarily those of Co3 Systems, Inc.