4 ms·
The target fitness function is clever. Basically, it is "symmetric difference cardinality". That is, the closer the bits in the hash result for the candidate a
by DannyBee 11y ago
The target fitness function is clever.
Basically, it is "symmetric difference cardinality".
That is, the closer the bits in the hash result for the candidate are to the target hash result, the better it considers the candidate (in particular, cardinality of symmetric difference for a bitset is the count of the number of one bits in the symmetric difference. It then sets the fitness to mean lower is better, so the smaller the number of different bits, the better it considers the candidate)
This means it just tweak input key bits through mutation until the result comes out right. Now, in theory, there should be no correlation, so this should be no better than random search, but ...
- j2kun 11y agoThis violates everything I know about hash functions, so it's amazing that it works. Has anyone tried this for industry standard hash functions?
- komaromy 11y agoAn ideal hash function would have perfect avalanching; that is, changing one bit of the input would result in a 50% chance of each of the output bits being flipped. While modern cryptographic hash functions have at least really good avalanching, definitely enough to resist a genetic search, I'm not sure that it's perfect. Home-brewed crap like what Petya was using is unlikely to be very good at it at all.
- Houshalter 11y agoThe first random number generator I learned about was super simple. Middle squares. You take a number, multiply it by itself, and take the middle bits. Because of the way the binary multiplication algorithm works, the bits are pretty thoroughly scrambled and not correlated to the input. I'm not sure if there aren't clever ways to undo it, but at least it would resist such a simple method like that.
- j2kun 11y agoSounds like Blum-Blum-Shub https://en.wikipedia.org/wiki/Blum_Blum_Shub https://en.wikipedia.org/wiki/Blum_Blum_Shub
- a39fa31c 11y agoKlondike has had a closer look as to why the genetic algo could work at all: https://klondike.es/klog/2016/04/12/cryptanalyzing-petya/#more-307 https://klondike.es/klog/2016/04/12/cryptanalyzing-petya/#mo...