4 ms·
At this point, how long would it take to brute-force an Enigma message on a modern home computer? Is it on the order of hours, or millennia? I found this: htt
by jfengel 3y ago
At this point, how long would it take to brute-force an Enigma message on a modern home computer? Is it on the order of hours, or millennia?
I found this:
https://crypto.stackexchange.com/questions/33628/how-many-possible-enigma-machine-settings#:~:text=Wikipedia%20is%20your%20friend%3A%20%22Combining,159%20quintillion)%20different%20settings.%22 https://crypto.stackexchange.com/questions/33628/how-many-po...
which says the key space is something like 10^20 or 10^23.
A modern supercomputer does something like 10^18 FLOPS. I assume that an enigma decryption is considerably more than a single floating point operation, but presumably just a few orders of magnitude.
So... if I'm reading that right, we're talking about months, perhaps?
- louwhopley 3y agoAlso curious!
- captaincrunch 3y agoIt would still take many orders of magnitude longer than the current age of the universe to brute-force decrypt an Enigma message on todays fastest desktop.
- deleted 3y ago[deleted]
- DavidSJ 3y agoHmm, the universe is over 10^17 seconds old and the key space is apparently only a few orders of magnitude larger, so this seems wrong.
- dgacmu 3y agoIt's only 2^69, or 512 exa-decryptions. A 4090 does 44 tera ops/sec (roughly 2^45), so we're left with 2^24 × ops per decode. If it takes 1000 ops to check a key, that's 2^34, or 16 billion seconds. About 500 years. Give or take a few centuries, it's very far from the age of the universe.
- aquova 3y agoAn episode of Computerphile attempted to answer the question - https://www.youtube.com/watch?v=RzWB5jL5RX0 https://www.youtube.com/watch?v=RzWB5jL5RX0. TL;DW: With some clever tricks, and the advantage of hindsight, it can be done reasonably quickly on a modern computer.
- DSMan195276 3y agoI'm not sure I'd count that as brute-force because his method can't decrypt every possible message. He's using a statistical test to determine whether a given configuration is better or worse and then uses that to narrow down the search space, but he clarifies it's not generic - it can't decrypt all possible messages (ones which trip up his tests) and also requires a minimum message length for the statistical tests to be effective. It's still extremely cool, don't get me wrong, but I don't think it's really what OPs asking. Given what's mentioned in the video (~12:50) and what some other commenters have mentioned I get the impression an actual brute-force is not really practical.
- remus 3y agoInteresting stuff. I guess it gets in to what counts as a a brute force, as most of the brute force attacks I've seen (e.g. password cracking) lean pretty heavily on clever maths and statistical hacks to reduce the search space as much as possible.
- DSMan195276 3y agoThat's fair, there's probably more gray area in the definition than I suggested. I think the difference to me is that this is exploiting a weakness in the encryption itself rather than just guessing what the likely combination is. For password cracking, you're typically not exploiting the encryption but rather what passwords are more likely to be used than others.
- WirelessGigabit 3y agoBut how do you know that the outcome you have is the right one? It's text. It's not something formatted. If I encrypted a JSON string, gave it to you, you can brute-force all day trying to parse the output as a JSON string. If it works, you probably have it right. But here? Because of how the Engima machine works you still get an output. And since we don't need to decode this output (like JSON to an actual JavaScript Object) we don't have that many ways of validating the output. It's German from 1945. Abbreviations, different (older) spelling, spelling mistakes, ... all make it really hard to distinguish real output from incorrect output.
- tehbeard 3y agoAs mentioned elsewhere, a signature of enigma ciphertext is that a letter can never encode as itself. This gives you some crude form of error checking. The rest of it as you mentioned makes it difficult to determine, data mining the possible results for common abbreviations from other plaintext could narrow.It down.
- sebzim4500 3y agoThat doesn't help at all because every key you try will lead to a candidate plaintext with no letters in common with the ciphertext.
- RichieAHB 3y agoI’m not sure being German or from 1945 has much to do with this. I’d think if I had some candidate plaintext that looked German and where a letter didn’t map to itself it’s likely to be right. Sure, you could argue that it’s not quite as unambiguous as JSON but, in the realm of all possible plaintext, I’d say JSON and 1945 German aren’t too far apart in terms of likelihood of getting a false positive on a string of non-trivial size. If you want a bit more certainty you could just try it on another string (which is the next step in the process either way), and then another. At least to me the constraints of “German and a char doesn’t map to itself” seem like pretty limiting factors here.
- 3y ago
- implements 3y agoIt’s an interesting question, but mechanical rotor encryption machines fell out of favour reasonably quickly after WW2 (early 1960s?) - which suggests that even with the limited computing resources of the time they were no longer secure ie you don’t need brute force to crack messages, some other cryptanalysis technique could do it. Edit: Though it might have been that purely electronic cryptographic machines were just cheaper and stronger by that point.