back to index
M4 Project

Hill climbing algorithm performance:

How many restarts will the hill climbing algorithm need to decrypt a message? Was a particular break lucky? Is there a correlation between the flatness of character distribution in the ciphertext and the number of restarts needed?

It is easy to test any theory: Generate a large number of random encryptions of the same plaintext and count the restarts that are required for a successful break.


Tests on the Looks signal:

Have a look at the results for 1000 random encryptions of the plaintext.

The first column contains the number of restarts needed for each ciphertext, the second column contains the IC of the ciphertext.

You can see that 66.3% of random encryptions yield with zero restarts and 81.3% with a single restart. This suggests that the settings of the actual break were not particularly favourable.

It can be seen that zero-restart breaks occur with wildly varying ciphertext ICs. I can see no correlation between the number of restarts and the IC of the ciphertext.


Tests on the Schroeder signal:

These tests were performed on the plaintext of the Schroeder signal truncated to 100 letters:

Results for 1000 random encryptions

The single column contains the number of restarts needed for each ciphertext.

Statistics:


  Restarts:          Success:

     0                14,3%

     1                23,6%

     5                50,5%

    10                66,4%

    30                84,9%

   100                97,0%

Simulated worst case (100 letter Schroeder message):

I tested how many restarts it would take in practice to break the most resistant encryption of the Schroeder message. The answer was 350. Keep in mind that this particular encryption was the most resistant one out of 1000.


Conclusion:

If the plaintext of the unbroken signal has about the same characteristics as the Schroeder signal, if the signal is not an Offizier message and if we are not dealing with a particularly resistant encryption, hopefully less than 100 restarts are needed.



Contact:

Stefan Krah <website @ bytereef.org>