Reply To: Optimising a stochastic hill climbing attack?
I’ll throw in my (rambling and incoherent) thoughts on this too. My team has settled on using stochastic hill-climbing for all the ciphers so far this year, and haven’t had it fail yet.
TLDR: I do think the answer to your optimisation problem is the modified annealing that madness suggests, perhaps described most simply as letting the algorithm settle for a slightly worse key every so often, in order to avoid local maxima. I believe the pseudocode for this is in the Cadenus chapter of madness’ (brilliant) book.
As has been said, for monoalphabetic (and often polyalphabetic) ciphers there is no need for annealing, a threshold of 10k – 100k works perfectly well. For other ciphers though it’s a different story.
More complex hill-climbers – optimal threshold
You’re right to assume that the optimal threshold is dependent on the length of the ciphertext, however through some iterative testing over the summer I was able to determine that a much more significant factor is the period (e.g. key length in vigenere or transposition). I’ve used a threshold of 100 * period in these hill-climbers, and for polyalphabetic texts with a length/period of >80 I’ve got consistently good results. Here are the results of testing on all of the polyalphabetic exercises in madness’ book (the time values are in seconds {shocking!} but in my defence the program is run on free remote servers for the purposes of collaboration, which significantly increases processing time by a factor of 10-20 – please view them in relation to each other)
cipher length period length/period success? time
214 7 30 failed
154 3 51 failed
396 7 56 failed
327 5 65 failed
850 10 85 quite close 1440
509 5 100 almost perfect 1140
831 6 140 almost perfect 637
2279 15 152 almost perfect 3900
1181 7 169 almost perfect 698
970 5 194 almost perfect 338
647 3 216 perfect 119
713 2 356 perfect 68.6
2062 4 516 almost perfect 273
– almost perfect: Almost all (99%) letters correct, keys easily reconstructible
– quite close: Quite a few letters wrong, but keys can be reconstructed
– failed: Not enough recognisable English to confirm that the program worked
As you can see the greater the value of length/period, the better the result. If your threshold was solely based on length, long periods would likely return more gibberish since the key space has 26*period dimensions, so there are many ‘adjacent’ keys.
The time to decrypt was determined more by the period (decryption of the polyalphabetic occurs for each cycle of the hill-climber so it’s order is multiplicative to the overall order {a sub-process}, and the longer the period, the more slices have to be monoalphabetically decrypted).
More complex hill climbers – optimal annealing
All this aside (I seem to have got distracted), the biggest difficulty when moving from monoalphabetic to transposition is that the fitness function over key space has much more noise, so there are many more local maxima. The solution to this is to allow the program to select a slightly worse key every so often. But how much worse, and how often? These optimisation questions are quite tricky to solve, and I doubt I’ve got the answer. With some testing I did get values for a step down frequency (percentage of slightly worse keys chosen, 5 in madness’ example #post-91915) and a margin (how close the fitness needed to be to the current best key to be considered ‘slightly’ worse, also 5% in madness’ example). My values were different to madness’ choices in the example algorithms: most interestingly (to me at least), the optimal-ish margin I found was actually dependent on the period (key length)! I think this can be rationalised by considering the fact that long periods have higher local maxima, so a more extreme step down is required to move towards the global maximum. I’ll keep the exact function I use secret until the end of this year’s challenge just in case it turns out to actually be a good choice. After that I’ll be too old to compete so I’ll discuss it, but it’s probably not the best choice anyway.
Wow I’ve gone on too long, if you’re not bored reading this then congrats. Happy hill-climbing all.