Reply To: Optimising a stochastic hill climbing attack?

[pufferfish101007]

Partially answering my own question here:
– If there are local optima, increasing the threshold won’t help because the hill climbing always goes uphill
– This is backed up by some testing: if I log the counter every time it gets to a multiple of 1000, once it gets to a sufficiently large number (usually only about 1000), it doesn’t go back down, i.e. it has reached an optimum
– This suggests that the keyspace-fitness mapping is not convex and so does have local optima
– So the best solution would be to run multiple hill-climbers in parallel and pick the fittest
Some confirmation that this is correct would be nice – I do wonder if anyone else has actually resorted to this method of decipherment yet at this stage in the competition of if it’s just me…
As a side note about improving performance – I tried utilising the ‘faster’ method outlined in Thomas Jakobsen’s paper (which doesn’t involve decoding the text at any point in the attack and instead shuffles the distribution matrix around) and found it to be significantly slower (which is probably [at least in part] due to the fact that I’m using tetragram fitness rather than bigram fitness – and also computing power has increased by a lot since 1995!)