Re:Hack-petya mission accomplished – Petya ransomware decryptor
by j2kun on Monday April 11, 2016 @07:41PM
(#11476048)
This violates everything I know about hash functions, so it's amazing that it works. Has anyone tried this for industry standard hash functions?
Re:Hack-petya mission accomplished – Petya ransomware decryptor
by komaromy on Monday April 11, 2016 @08:13PM
(#11476225)
An 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.
Re:Hack-petya mission accomplished – Petya ransomware decryptor
by Houshalter on Tuesday April 12, 2016 @03:45AM
(#11477853)
The 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.
Re:Hack-petya mission accomplished – Petya ransomware decryptor
by j2kun on Tuesday April 12, 2016 @01:41PM
(#11481745)
Sounds like Blum-Blum-Shub https://en.wikipedia.org/wiki/Blum_Blum_Shub
Re:Hack-petya mission accomplished – Petya ransomware decryptor
by a39fa31c on Wednesday April 13, 2016 @03:49AM
(#11486463)
Klondike has had a closer look as to why the genetic algo could work at all: https://klondike.es/klog/2016/04/12/cryptanalyzing-petya/#mo...
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 ...