Naked Science Forum
Non Life Sciences => Geek Speak => Topic started by: syhprum on 27/12/2017 14:42:22
-
The decrypting of enigma traffic with electromechanical computers only just worked due to sloppy operating procedures and lots of intelligent guess work.
How easy would it have been if modern computers had been available?
-
Many thousand lives, both civilians and military would have been saved, if faster computers with powerful software would have been available earlier.
What takes always time, is the analysis of the system used, and the Enigma created initially some considerable problems for the data scientists.
-
Cracking the Enigma code was assisted by having the plans of an Enigma. Machine available for study. And a group of highly skilled mathematicians to analyse it.
But today's computers would have been much faster than the electromechanical devices used to crack Enigma.
An even more interesting story is about Colossus, which was used to crack the more sophisticated German Lorenz code. The technology in this device led to the flowering of vacuum-tube computers after WW2. This was kept secret until the 1970s, so is less known than cracking Enigma.
-
Enigma was cracked by the very clever people at one end and the very human people at the other.
The second group had been told it was "uncrackable"- so they got sloppy.
If they had strictly followed good cryptographic practice then I don't think even today's supercomputers could "brute force" enigma.
https://en.wikipedia.org/wiki/Enigma_machine#Mathematical_analysis
-
The Blechtley people used very rudimentary relay logic on the hardware side and for the first time statistical analysis techniques to appraise each and every message received.
Forgotten seem to be the efforts of the many forgotten girls in the wire room, which painstakingly assisted in this intelligence effort.
Here i shall express my personal gratitude.
-
If the Allies had had access to modern computing, a back-of-the-envelope calculation suggests that a single one of today's smart phones should have easily outperformed all of the Allies' bombes-several hundred Bombes- and by a huge margin, and completed ALL of their daily runs in a tiny fraction of a second!
-
Several emulation program are available so that you can have your own Enigma machine on the screen, unfortunately they are 16 bit and need minor modifications to the normal 64 bit system to run
https://www.groovypost.com/howto/enable-16-bit-application-support-windows-10/
-
If the Allies had had access to modern computing, a back-of-the-envelope calculation suggests that a single one of today's smart phones should have easily outperformed all of the Allies' bombes-several hundred Bombes- and by a huge margin, and completed ALL of their daily runs in a tiny fraction of a second!
The bombes only worked because the Germans made mistakes like using predictable keys like HITLER and sometimes sending the same message twice.
-
Yes. If only they hadn't made mistakes. Someone should have given them a stern talking to, and told them not to make any more mistakes.
But modern computing can't change human nature. We f up a lot, particularly when doing cryptography. Cryptography is hard.
-
Would the Lorenz code ever have been cracked but for the fortuitous capture of a code book from a submarine.
Was it known that code books were in use and navel people instructed to hunt for them .
Did every lorenz machine have its own unique code book ?
-
Even with modern equiptment it is not easy to record teleprinter transmission from the HF band so how did German submariners do it with enemy vessels and air craft hunting them.
I understand that during a recent competition to decode Lorenz type transmissions Bletchly park came second because they were unable to receive the transmissions although during the war no doubt they had better facilities.
-
Was it known that code books were in use and naval people instructed to hunt for them .
Yes, ever since the use of cryptography, experts have known that the easiest way to crack a secret code is to have a copy of the codebook. Then its not so secret any more. (...provided the ones you are monitoring don't know that you have a copy of the codebook!)
So collecting the codebooks is the first priority of intelligence agencies - and destroying them is the first priority of the communications staff when it looks like they will be captured.
Secret codes are changed regularly - but if you have recorded many messages, you may be able to go forward in time, and monitor future communications for a while, and go back in time and decode some messages that were previously gibberish.
how did German submariners do it with enemy vessels and air craft hunting them.
Morse Code (well, the German-language equivalent).
It works very well with low signal strength and a poor signal-to-noise ratio. And the submarine doesn't need to transmit (hence giving away its position) to successfully receive messages.
See: https://en.wikipedia.org/wiki/Morse_code
-
Would the Lorenz code ever have been cracked but for the fortuitous capture of a code book from a submarine.
Was it known that code books were in use and navel people instructed to hunt for them .
Did every lorenz machine have its own unique code book ?
You seem to be confusing two things, Naval Enigma and Lorenz.
Lorenz was completely cracked without any code books at all (something that is considered one of the greatest intellectual achievements of the war) based on a 'depth' where two similar messages had been encrypted with the same key.
For Naval Enigma, the submarine gave them the code books.
https://en.wikipedia.org/wiki/German_submarine_U-559
Whether they'd be able to crack it without this is unknown- quite possibly not. They'd been stuck for several months prior to that; but they'd been stuck before.
-
How easy would (decryption) have been if modern computers had been available?
If modern computers had been available, the encryption method could have been much more sophisticated than in the Enigma machine.
- The Enigma machine used mechanical rotors which each had a unique electrical path. The rotors clicked forward one step after each key was pressed, producing a unique encryption for each letter, not affected by the letters around it. Even the tougher naval version of Enigma had "only" 151 trillion settings, which today we would describe as 50 bits of secret key to be determined in decryption.
- If we take a fairly modern encryption standard like AES 256 (the algorithm is publicly defined), the secret key is 256 bits long, and each extra bit in the key means it is twice as hard to decode. The data is encrypted in blocks of 128 bits, so the encryption of every character depends on 16 nearby characters; in some modes, the encryption of every character depends on every prior character in the message. To make it tougher, the encryption process is repeated 14 times (14 "rounds") for AES 256.
- With today's Public Key Encryption algorithms, key lengths are even longer - over 1000 bits. These algorithms are so processor intensive that they are rarely used to encrypt a whole message, but instead are used to transfer the encryption key for an encryption algorithm which is less computationally demanding.
The availability of increased computer power just steps up the battle between the encryptors and the decryptors to another level. National security agencies (who often play both roles) have divided loyalties in defining public encryption - they want the public to use methods that are hard for the public to decrypt (for now), but which are still feasible for them to decrypt.
This contradiction is visible in the GSM mobile phone standard, where encryption was intentionally weakened to make interception possible - and now any laptop can quickly decrypt GSM transmissions.
See: https://en.wikipedia.org/wiki/Cryptanalysis_of_the_Enigma#Security_properties
https://en.wikipedia.org/wiki/Advanced_Encryption_Standard#Security
https://en.wikipedia.org/wiki/Public-key_cryptography#Computational_cost
-
It depends what you mean by a trillion.
From WIKI
"Combining three rotors from a set of five, the rotor settings with 26 positions, and the plugboard with ten pairs of letters connected, the military Enigma has 158,962,555,217,826,360,000 (nearly 159 quintillion) different settings.[17]"
That's a whole different ball game from 151 trillion settings.
If your computer could test a billion possibilities each second (and that's unrealistic) then it would take 158 billion seconds to try all the possibilities.
That's 5000 years. They would still be trying to decode the instructions for stonehenge.
Even having multiple machines doesn't help much.
-
I understand some navel communications have only recently been decoded 75 years after they were sent but as you say a brute force technique is impossible so I do not know how it was done
-
I understand some navel communications have only recently been decoded 75 years after they were sent but as you say a brute force technique is impossible so I do not know how it was done
The easy way might be to ask the Germans.
-
It depends what you mean by a trillion.
From WIKI
"Combining three rotors from a set of five, the rotor settings with 26 positions, and the plugboard with ten pairs of letters connected, the military Enigma has 158,962,555,217,826,360,000 (nearly 159 quintillion) different settings.[17]"
That's a whole different ball game from 151 trillion settings.
If your computer could test a billion possibilities each second (and that's unrealistic) then it would take 158 billion seconds to try all the possibilities.
That's 5000 years. They would still be trying to decode the instructions for stonehenge.
Even having multiple machines doesn't help much.
Yeah, it does. 5000 machines isn't all that many. And don't forget modern machines are superscalar.
That's not an intractable number anymore, it's a 'how bad do you want it?' number. 5000 machines cost ~£5 million plus electricity and warehousing.
-
It depends what you mean by a trillion.
From WIKI
"Combining three rotors from a set of five, the rotor settings with 26 positions, and the plugboard with ten pairs of letters connected, the military Enigma has 158,962,555,217,826,360,000 (nearly 159 quintillion) different settings.[17]"
That's a whole different ball game from 151 trillion settings.
If your computer could test a billion possibilities each second (and that's unrealistic) then it would take 158 billion seconds to try all the possibilities.
That's 5000 years. They would still be trying to decode the instructions for stonehenge.
Even having multiple machines doesn't help much.
Yeah, it does. 5000 machines isn't all that many. And don't forget modern machines are superscalar.
That's not an intractable number anymore, it's a 'how bad do you want it?' number. 5000 machines cost ~£5 million plus electricity and warehousing.
You need something of the order of 1000 cycles to check a particular combination of settings, so I was assuming you were running something like 1000 machines in parallel to get a billion checks per second.
You think a wartime message that you translate a year later is still useful enough to stack up (and fuel) 5,000,000 machines?
How do you decide which of the thousands of messages sent and received is the one you need to put all that effort into?
It's clearly impossible.
So you need roughly 5 million machines grinding away for a year for each message decrypted.
There were (I guess) hundreds of Enigma machines, each of which was used for many messages each day- perhaps hundreds a day.
So you need a hundred sets of a hundred sets of 5 million computers.
That's about 5 computers for everyone on the planet
Good luck asking Mr Churchill for resources for that during a war.
Next time I tell you that something doesn't help much, you might want to look carefully at the numbers before assuming I'm wrong.
-
Nah. You don't need anything like 1000 clock cycles to prove that a particular guess is wrong. Most of them will fail in six memory lookups at the first hurdle.
-
There were (I guess) hundreds of Enigma machines, each of which was used for many messages each day- perhaps hundreds a day.
It was not quite that hard.
The code book used by the army told all of these hundreds of machines to use the same rotors, in the same sequence, and the same plugboard settings (so all these machines could communicate with each other). Crack one message to obtain these settings, and you will easily crack all other army messages for that day.
To crack the first message of the day, they picked a message that was the right length for “nothing to report”, and used some idiosyncrasies of Enigma to significantly reduce the space of possibilities (eg the Enigma would never translate a letter to itself - what sounds like a strength was a crucial weakness!).
The navy had more rotors and a different code book than the army.
-
Nah. You don't need anything like 1000 clock cycles to prove that a particular guess is wrong. Most of them will fail in six memory lookups at the first hurdle.
OK, for the sake of discussion, here's the start of an encrypted message
KLBV MUTJ TUG
Can you let us know how you would go about decoding it.
-
Did you start the plaintext in the conventional way, with the stationcode repeated?
-
No, but I can if you like.
Alternatively, feel free to come up with your own test data and show us how the process would work.
-
The thing is, even with brute force you still have to have a model of the plaintext data.
In addition you don't have enough letters in your plaintext. Because it's shorter than the keyspace, it's probable there's multiple valid plaintexts that could produce that encrypted output.
If we model the plugboard as an array P() and the wheel N's settings as WN() then a single round of the enigma is just:
P'(W1'(W2'(W3'(R(W3(W2(W1(P(x)))))))))) which is 9 lookups, i.e. 9 cache lookups.
And Enigma is symmetric, that's also the decoding pattern, so in around 18 lookups you can run the decryption process twice, and compare the first letter of the stationcode. And with some slightly sneaky modular maths I think you can bring that down to 9 lookups. And, as I noted, most processors are superscalar, and heavily pipelined, so they can test (say) 6 or 8 in parallel depending on how many cores there are in the processor. Given gigahertz clock rates, that is about a billion tests per second.
-
P'(W1'(W2'(W3'(R(W3(W2(W1(P(x))))))))))
Did you begin as a LISP programmer?
LISP = “Lots of Infuriating, Stupid Parentheses”
Or is this Functional Programming?
9 cache lookups
But seriously, I am not sure you can do it as a simple table lookup.
Enigma is a polyalphabetic cypher, ie after every letter, the rotors clicked around, creating a different letter translation, ie a different lookup table?
-
The lookup is just, in C:
rotorArray[rotorPosition + inputCharacter]
You can avoid having to worry about index overflow by making the array big enough (36*2) and repeating the rotor wiring settings on the end in the array, so you don't have to test for it or do modulo arithmetic on it.
Only the first rotor clicks on in most cases. You do have to worry about that but it doesn't change the order of magnitude of the answer; in most cases the second rotor doesn't click on.
edit: it's actually likely to be less than 9 lookups; you can cache a single lookup table for all the centre W2'(W3'(R(W3(W2())))))) permutations and reuse that over and over; that should bring it down to 5 lookups.
-
The thing is, even with brute force you still have to have a model of the plaintext data.
In addition you don't have enough letters in your plaintext. Because it's shorter than the keyspace, it's probable there's multiple valid plaintexts that could produce that encrypted output.
I know.
I also know I'm not the one who said " Most of them will fail in six memory lookups at the first hurdle."
So, show me how most of the zillion possibilities are excluded in 6 lookups.
Or accept that your assertion was- shall we say- optimistic.
It would also be instructive to see how many clock cycles it takes to actually "run" this
P'(W1'(W2'(W3'(R(W3(W2(W1(P(x))))))))))
I suspect it's over 1000
-
The thing is, even with brute force you still have to have a model of the plaintext data.
In addition you don't have enough letters in your plaintext. Because it's shorter than the keyspace, it's probable there's multiple valid plaintexts that could produce that encrypted output.
I know.
I also know I'm not the one who said " Most of them will fail in six memory lookups at the first hurdle."
So, show me how most of the zillion possibilities are excluded in 6 lookups.
The standard way that the Enigma was used was that the beginning of the plaintext was 3 characters, repeated.
So if you run a trial decrypt on the first and 4th character, and they aren't the same, then you've ruled out those settings and you can go onto the next.
Except when the rightmost wheel has rolled over and bumped the next wheel, which for the sake of this not being a cryptographic forum, only the rightmost wheel has moved.
So if: P'(W1'(W2'(W3'(R(W3(W2(W1(P(e1)))))))))) != P'(W1+4'(W2'(W3'(R(W3(W2(W1+4(P(e4))))))))))
Then you can stop immediately, and go onto the next wheel settings.
And that's the typical case: that they DON'T match. If they do match, you check the next letter of the station code, and only if they match do you check the third. That reduces the amount of work done per setting by thousands. If the result is a plausible station code then you can perform a much longer check on the rest of the alleged plaintext looking for plausible bigrams.
It would also be instructive to see how many clock cycles it takes to actually "run" this
P'(W1'(W2'(W3'(R(W3(W2(W1(P(x))))))))))
I suspect it's over 1000
Nah. It's 6 additions and 9 memory lookups, there's pipelining so the additions and lookups will happen in parallel, and the table lookups should fit in the on-chip caches. If they don't fit, then yes, it would be very slow, and you've picked the wrong processor for this workload. Also, processors these days are superscalar, so you can write the code to run several decode attempts running in parallel on different cores, this kind of thing parallelises really, really well.
-
Dear Wolfekeeper, respect for such an investigative and analytical mind... what a great effort.
I was born in Germany, and many students wanted to know how the Enigma code was broken, and to simulate the software on an IBM box. This was just a great fun part.
In reading about the Blechtley code people, they where the true Heros, using Relay logic, to do work which had never previously been done. Think, if their relay circuit was able to run at 1 hz per second, how long would your mainframe take with a similar clock rate.
What would you do, if you had to program your main frame with a patch panel, in machine code....?? You would be burning plenty of midnight oil... even today.
-
To be pendantic you don't run at 1 Hz per second Hz is the measure of frequency the per second is implied
-
It would also be instructive to see how many clock cycles it takes to actually "run" this
P'(W1'(W2'(W3'(R(W3(W2(W1(P(x))))))))))
I suspect it's over 1000
I coded it up in C and compiled it and ran it. It performed 1.76 billion encryptions in 44 seconds, which works out at about 25 nanoseconds per encryption on a single core. That's running on a shitty netbook Intel Atom processor with 1.4 Ghz clock speed.
This compares to the WWII bombes which could check up to 52 per second, and is 700,000 times faster, running single core, and should be nearly 3 million times faster multicore, but I couldn't be bothered to test that.
The two results are not entirely equivalent though, the bombe could be wired up using a diagonal board, and that should run a few times slower than this on a modern processor if you simulate that, but you wouldn't do that for a brute force attack.
-
this not being a cryptographic forum
Could you post a link to a cryptographic forum, please - I am interested in how these cryptic brute forces spend their surplus cycles!
-
with modern computers?
If you wanted the decryption algorithm to run even faster, you could compile the decryption code to an off-the-shelf programmable logic device like a gate array chip - ie put it in hardware. You can stack a lot of these chips in the space taken up by a general-purpose laptop.
If you had to do a lot of decryption using an established algorithm, you could produce a full-custom chip to implement the algorithm in hardware. The first one is more expensive than buying a commercial gate-array chip, but much faster for this one algorithm.