Forum

Challenge "The SIGABA Challenge — Part 1"

Challenge "The SIGABA Challenge — Part 1"  

  By: admin on Feb. 29, 2020, 12:29 p.m.

The SIGABA was a highly secure encryption machine used by the US for strategic communications in WWII. It is believed that the German codebreakers were unable to make any inroads against SIGABA. In this part of the series of challenges, you are provided with a partial known-plaintext, and some information about the key settings.
Read more...

Re: Challenge  

  By: Greko on April 8, 2021, 6:07 p.m.

Hi all,

I recently solved this challenge but it still bothers me the performance of my attack.
As this is part-1 of this series I ran the "simplest" attack indirectly suggested by
the additional files of this challenge. I would be interested to know what was the intended
or even the lowest time complexity required to actually solve this challenge. Of course
this is also hardware dependent and compiler-flags dependent.

My attack required about 57 core hours on a 2.4 GHz machine without any optimisation
flags set while compiling. Using 4 cores for the attack that results in about 14.2 hours
that the attack was running. I am quite sure that this is far from optimal as scaling this
complexity for the next parts would mean that they are not practically solvable beyond
part-2, but they have actually been solved (even part-2 would require about 15 days on 4 cores).
However, it is unclear to me how close was the performance of my attack to the intended
one when the challenge was created.

Would it be possible for the author or any of the solvers to share the performance
of their attacks? That could help me understand where my attack stands and what margin
of improvement could be possible (especially implementation-wise). I am particularly
interested in what was the intended time complexity when this challenge was created.

Thank you in advance.

Best regards,
Greko

Re: Challenge  

  By: jerva on April 12, 2021, 8 p.m.

Hi, yes I have solved #1 to #6 and am happy to indicate some outline of what I have done. As you know #3-#6 are Level III, which MTC3 suggests “represent current research topics that are believed to be very difficult to solve. Thus, practical solutions may not even exist and ready-to-run tools almost certainly do not.” So these should not be easy.

Ultimately the challenges need to be broken into phases or use MITM – simply because the overall keyspace is > 2^95 which won’t submit to brute force. Stamp and Chan (Stamp, Mark & Chan, Wing. (2007). SIGABA: Cryptanalysis of the full keyspace. Cryptologia. 31. 201-222. 10.1080/01611190701394650) indicate a two phase method whereas Lasry (A Practical Meet-in-the-Middle Attack on SIGABA, in the challenge material) uses MITM.

The challenges get 26^2 times harder at each challenge, as an extra pair of letters become undefined. The breaking into phases can likely make each phase only around 26 times harder. But even then, #6 is 26^5 times harder than the one you have solved. So even generously assuming you are prepared to allow as much as a year of computer time to solve #6, you’d need to be solving #1 in under 3 seconds to use the same method – which I suspect is the problem you’ve identified.

And Dr Lasry, in his MITM paper, speaks of taking ‘a few days’ to solve something equivalent to #2. So (unoptimised) that method would not scale.

So you either need a bigger computer or a better method, perhaps both. What I have done (outline only) is conceptually based on Stamp and Chan’s work in that I solve for likely candidates of Cipher rotor settings first, then only apply a second phase to the most likely. Specifically I use dynamic programming to tame the exponential growth in the Phase 1 element. In effect that means reusing results from previous calculations rather than following different paths and hence seeing exponential growth.

I do that phase on a GPU using CUDA. It is work that is well suited to a GPU. The downside is that this is holistic - effectively you have to do as much work for #6 as #1. So I don’t use that method for #1,#2,#3 as simple brute force enumeration is easier, but it is very good for #4,#5,#6.

Another downside is that the dynamic programming loses some signal to noise, so I then have to reprioritise based on actually enumerating the most likely paths in full, but there are vastly fewer to check.

The next stage of course is to match the result to a specific location in the Control and Index wheel settings. I think I’m happy to hint that you can take the index wheels out of that equation, which makes things about a million times easier. And again, this phase was well suited to CUDA on a GPU.

None of this was easy and did take me some time, but it was interesting, and I’m glad I did it. My early code probably wasn't much faster than yours.

So, can you use your current code to hope to solve #6? No. Is No 6 possible to solve in days with the right code on a domestic computer? Yes.

jerva

Re: Challenge  

  By: Greko on April 13, 2021, 8:34 p.m.

Dear jerva,

Thank you very much for your detailed reply! I really appreciate it.

This is way more information than what I asked for. It definitely helps
a pontential solver to take the right path. Also, I think it is very
motivating that now everybody knows that these challenges do not require
access to an extremely powerful computer in order to be solved.
I just hope that this does not spoil too many details about the
attack and thus reduce the fun.

On my side I must admit that I come from a more purely mathematical background,
so I am not familiar with the term "dynamic programming" and using GPUs.
Therefore I cannot assess on the spot the improvements which you are suggesting.
However this project could serve as a good excuse for me to learn all these stuff.

What I implemented was the MITM attack described in the paper of Dr. Lasry in C
language. But it seems that this is one of the cases where we cannot solve our
problems using the same ideas with which we created them.

Best regards,
Greko


Currently 13 guests and one member are online.
Powered by the CrypTool project
© 2009-2021 MysteryTwister team