6 ms·
> Last, but not least, it fires up a genetic solver which gets us the key in a few seconds. That's pretty impressive! On the other hand, is it a general vulner
by d33 11y ago
> Last, but not least, it fires up a genetic solver which gets us the key in a few seconds.
That's pretty impressive! On the other hand, is it a general vulnerability of Salsa that genetic solvers can break it? Sounds like a huge vulnerability.
- api 11y agoIt's probably a crap hand rolled key derivation function instead of a proper hash.
- CiPHPerCoder 11y agohttps://github.com/leo-stone/hack-petya/blob/master/main.go#L107-L108 https://github.com/leo-stone/hack-petya/blob/master/main.go#... Looks like it used a [1-9a-xA-X]{8} key. Even with a CSPRNG that's only 46 bits of entropy. You can brute force that in 2-3 hours with adequate hardware.
- matt_wulfeck 11y agoDon't these things generate a unique key for each file?
- AnimalMuppet 11y agoEven if they do, the per-file keys must be algorithmically-derived from the master key. (Otherwise, how can it unencrypt the files after you pay the ransom?)
- vetrom 11y agoUser-space malware, sure. Petya does a full-disk encryption.
- Godel_unicode 11y agoOff topic - this might be the single most uttered phrase in crypto reviews in the last year.
- deleted 11y ago[deleted]
- danbruc 11y agoI was wondering the same thing, I would naively have expected that genetic algorithms are absolutely useless for attacking cryptographic functions because the search space is full of local extrema. Maybe the used version is really a lot weaker. I would also like to know why the author chose this solution, it would probably have been one of the last things I would have considered. Maybe he observed something that pointed in that direction?
- lazyjones 11y agoI don't really understand the matrix substitution used, but the fact that the genetic algorithm works like it does seems to suggest it's about as secure as a Vigenère cipher (working on bit strings). Unless the genetic solver doesn't provide any speedup and is just ignorantly used instead of a brute force approach. It's extremely unlikely that Salsa itself is vulnerable though.
- lkowalcz 11y agoYeah, my first guess would be that the genetic solver is degenerating to basically a brute force search here (which is feasible in this weak instance). Will have to take a look to confirm...
- knicholes 11y agoFor a genetic algorithm to make beneficial mutations, one needs a fitness function. What would the fitness function be if the password either works or it doesn't?
- DannyBee 11y agoThe 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.
- deleted 11y ago[deleted]
- RUBwkVjwLsDKgPw 11y agoIt's a 16-bit version of Salsa20, which is far less secure. Proof: this project. I have no clue what possessed the author to do this. Stop hand-rolling crypto, people! Ransomware needs security too. :(
- an_account_name 11y agoIt's a way of sponsoring community-led crypto research.
- mangeletti 11y agoMy guess is that the authors wanted to ensure they could encrypt a full disk quickly.
- arviewer 11y agoMaybe it's just a test to see how quickly this was broken.
- PeCaN 11y agoOn the other hand, it's not a critical security application. If someone breaks it, you just don't get a little money. If the exploit becomes widespread, you can update the malware. The author probably wanted to be able to somewhat quickly encrypt/decrypt a full disk on potentially slow hardware.
- CamperBob2 11y agoEven a poorly-implemented homebrew encryption function would have been better than using a broken implementation of a common, trivially-recognizable function. It was easy for them to run this code through an SMT solver because it was easy to obtain the original source code. It would have been smarter to bundle the ransomware with a 32-bit DOS extender so the known-good Salsa implementation could be used unchanged.