Naked Science Forum
Non Life Sciences => Geek Speak => Topic started by: syhprum on 29/03/2022 10:19:41
-
I would expect modern computers to easily decode traffic encodered with 3 disk machines but what of more complex encoders ?
-
Faster computers since 1940s will help by a factor of millions. Modern laptops have a "clock speed" around 2.5GHz
- The Bombe machine which cracked the Enigma code was electromechanical and had a "clock speed" around 25Hz. https://en.wikipedia.org/wiki/Bombe#The_British_Bombe
- The Colossus machine that cracked the harder Lorenz code was based on thermionic valves (like old-fashioned light bulbs) and had a "clock speed" of 5kHz. https://en.wikipedia.org/wiki/Colossus_computer#Design_and_construction
- Colossus had no electronic memory; the Gigabytes of RAM on a modern laptop provides a significant speed boost, as pre-computed tables can provide a significant speedup.
But the analysis by mathematical experts also reduces the search time by an additional factor of millions.
Reportedly, when the mobile phone standards were being developed, some countries argued for weaker encryption, so their security agencies could listen in more easily. By the time that mobile network standard was replaced, the encryption could be cracked on a laptop computer in minutes. And software to crack it appeared within months after the standard was published.
-
By the end of WWII Bletchley Park was reading Tunny code from the 12-rotor Lorenz encoder and the US Navy was reading 7-rotor Japanese naval codes.
There was a significant element of luck involved where operators made repeats such as "HH" to sign off, and in one case actually repeated an entire message with a different encoding, but it's within the scope of modern computers to crack these mechanical codes by "brute force" - in effect, whizz through all possible combinations until you get some recognisable German or Japanese words.
It would be interesting to learn how the Axis got on with cracking Allied codes. Any suggestions for reading matter?
-
If the German "command" hadn't told their forces that the machines were uncrackable (or if the soldiers had had the nous to realise it anyway) then they might not have got sloppy with the way they used the machines.
If they had used them properly, I don't think today's computers would have been able to brute force the codes quickly enough to be useful (at least, not without massive numbers running in parallel).
-
The history books I've read only mention two critical "sloppinesses", one army (the whole message resent in Tunny) and one naval ("HH" signoff from a naval Engima) but there's a lot more to it.
Monitors were able to distinguish individual morse operators from their particular rhythms and could track a particular unit with direction-finding aerials, which gave further clues as to the probable content of a message. This was also the basis of a double-cross: the US army placed "known" operators where they wanted the enemy to believe that troops or equipment were being assembled, and got them to send lots of spoof traffic suggesting much local activity.
-
Most of the decoding relied on the rigid message structure in the messages, as they all, like weather forecasts, either had a very well defined structure, with known words in them in known positions, or a very easy to guess preamble and postamble to all the messages, so that all your decoding had to do to brute force the approach was to run through, looking for this known set of characters in this known position, like a date, and then you would have a very much reduced set of combinations that would produce this.
Also assisted by the quirk of Enigma that an encrypted letter would never be the same letter coming out, which helped in eliminating a lot of the combinations off the bat, saving computation time. The breakthroughs came because the same message was sent two times in each case, using the same settings, because the far end operator ran it through as it was sent, and at the end the paper was printed with garbage, not the expected end of message, indicating an error. Thus the request to resend, and the sending operator did not follow protocol, and use the next setting number in the code book, a way so all messages were only sent once, and then the code was not used again, a one time pad that means the messages have to be decrypted individually. Instead sent using the same number, but crucially the beginning was the same, and only in the body of the message did the operator start to use abbreviations for words, so the message after encryption was somewhat shorter, but had the same information.
This allowed the brilliant decoders to decode this message, and also work out that the sequence numbers were a single digit change in the one wheel, which made it possible to start each day with the previous one's decoded results, and thus massively reduce the amount of decoding time.
Remember the Enigma machine went out with a code book, which gave, for each machine, a set of code wheel start positions for each day, a set of pegboard wire settings for the current code book, and then a set of start positions for each message, which was also logged with the message cleartext in a code log. For submarines this book would be for a 6 month period, though superceded with a new book every time they came into port after 3 to 5 months. For the rest there were monthly or weekly code books, and every so often the Command would be paranoid, and swap out all code books to new ones.
Modern computers can easily do the brute force decoding with the original messages, simply because they can run through the entire 7 digit code space in a few minutes, looking for those known sequences, and storing the settings that gave them. Then you got a smaller set of locks of letters and numbers that would be parsed as to then having the correct preamble, and that, in the blocks of characters that came out, you could have correct phrases and words in there, passing those ones to the operator to read.
Remember your smartphone is equivalent, in processing power, to all the computing power in the world in 1945, including all the university computers, and so much more faster as well by orders of magnitude. Thus unbreakable codes then are merely a few minutes of work, and those Enigma machines were all sold on by the UK government to other countries after the War as a secure "unbreakable" communication method, which was Ultra Secret in the UK that those messages could still be read, using those original 1940's era machines which went to the Intelligence services, and which were maintained till the 1970's, when the last countries stopped using them.
-
the sending operator did not follow protocol
If they had used them properly,
-
Modern computers can easily do the brute force decoding with the original messages, simply because they can run through the entire 7 digit code space in a few minutes,
It's not just a 7 digit code (Which would be about 23 bits of entropy).
It has about 67 bits.
Good luck breaking that with your smart phone.
https://en.wikipedia.org/wiki/Enigma_machine#:~:text=Combining%20three%20rotors%20from%20a,quintillion%20or%20about%2067%20bits).
-
Did not say it would be a few seconds, but the decoders and encoders will run on any modern smartphone that can run the apprpriate languages.
however this is a nice enough video by Brady about it.
-
Did not say it would be a few seconds
Nobody said you had.
but you did say "Modern computers can easily do the brute force decoding with the original messages, simply because they can run through the entire 7 digit code space in a few minutes"
And it's not 7 digits, is it?
It's 21 digits.
That's... "significantly" more difficult.
Imagine that all the phone has to do is "count" to 10^21
My phone has a clock rate of about 2 GHz and it has a few processors so lets say it can count at 10GHz
So it will take about 10^11 seconds to count through all the combinations.
If Caesar had used an Enigma machine, we still couldn't have brute forced the codes by now.
-
Breaking the Enigma code had a powerful head-start when the Germans sent one to their embassy in Poland.
- The Polish secret service took it apart, recorded everything and reassembled the whole thing, in 1 night.
- When Germany invaded Poland, all of this research was transferred to the UK.
- The Germans later added extra code wheels, but the work already done made this extra complexity manageable.
I understand that the more complex Tunny code was cracked without actually seeing a real machine.
-
A decoding machine spews out a string of letters/words how does it know when to stop ?
-
A decoding machine spews out a string of letters/words how does it know when to stop ?
The Enigma-type machine put out 1 character for every character on the input.
- Characters stop coming out when you stop typing on the keyboard.
Traditionally, secret codes were presented as a sequence of 5 characters, then a space, in columns across the page
- that way you could clearly see if there was a character inserted or missing (and you could expect the message to be scrambled past that point)
- To make sure that the message took up a whole block of 5 characters, a few random characters were added on the end
- Internal message structures would tell you where the message ended and the gibberish started
- If one character was misread, that character would be scrambled, but the rest of the message would be ok
Modern block cyphers encode larger block of characters - eg 8 characters (DES-64), or 16 characters (AES)
- This allows you to have an astronomical number of possible functions from input to output.
- If you misread one of these characters, the whole block of characters is mangled.
- To discourage operating on multiple blocks in parallel, some cyphers encrypt the remainder of the message with the encrypted value of the message so far. The disadvantage is that if you misread 1 bit, the entire message after that block is unreadable.
https://en.wikipedia.org/wiki/Advanced_Encryption_Standard
-
A decoding machine spews out a string of letters/words how does it know when to stop ?
When the output is recognisable.
For example (per the video) when it's the German for "weather observation" or whatever.