News for hackers. Stuff that matters.
Re:Hack-petya mission accomplished – Petya ransomware decryptor by d33 on Monday April 11, 2016 @04:21PM (#11474783)
> 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.

Re:Hack-petya mission accomplished – Petya ransomware decryptor by RUBwkVjwLsDKgPw on Monday April 11, 2016 @06:57PM (#11475814)
It'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. :(

Re:Hack-petya mission accomplished – Petya ransomware decryptor by PeCaN on Monday April 11, 2016 @10:58PM (#11476915)
On 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.

Re:Hack-petya mission accomplished – Petya ransomware decryptor by CamperBob2 on Saturday April 23, 2016 @02:41PM (#11556795)
Even 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.

Re:Hack-petya mission accomplished – Petya ransomware decryptor by an_account_name on Monday April 11, 2016 @07:16PM (#11475918)
It's a way of sponsoring community-led crypto research.
Re:Hack-petya mission accomplished – Petya ransomware decryptor by mangeletti on Monday April 11, 2016 @08:43PM (#11476368)
My guess is that the authors wanted to ensure they could encrypt a full disk quickly.
Re:Hack-petya mission accomplished – Petya ransomware decryptor by arviewer on Tuesday April 12, 2016 @04:38AM (#11478022)
Maybe it's just a test to see how quickly this was broken.
Re:Hack-petya mission accomplished – Petya ransomware decryptor by knicholes on Monday April 11, 2016 @05:28PM (#11475252)
For 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?
Re:Hack-petya mission accomplished – Petya ransomware decryptor by DannyBee on Monday April 11, 2016 @05:54PM (#11475446)
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 ...

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)
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...
Re:Hack-petya mission accomplished – Petya ransomware decryptor by danbruc on Monday April 11, 2016 @06:01PM (#11475508)
From a quick look at the code it looks like something derived from the key is compared with some value on the encrypted disc, i.e. a key verification check. Like you store passwords, you hash the password and compare it with the stored hash to check whether it is valid. You can then, at least theoretically, use the hamming distance as a fitness function and this seems to be what the code does.

  return int(bitset.From(c.qwords()).SymmetricDifferenceCardinality(target_bitset))
What really confuses me is how this can possibly work for a cryptographic function where any change in any one of the input bit is supposed to, on average, flip half of the output bits. But then again I am not curious enough to analyze the code in detail.
Re:Hack-petya mission accomplished – Petya ransomware decryptor by SolarNet on Monday April 11, 2016 @06:59PM (#11475824)
It looks like the implementors failed to follow the recommended usage and design (and indeed common sense) of the algorithm:

* They used 16 bit math instead of 32 bit math (with, I'm assuming, a 32 bit output size rather than the recommended 64 bit output). Which has the effect of looking like 10 rounds, but it's a rather more serious security failure.

* They generated keys in the alphanumeric range (instead of the full byte range) significantly reducing entropy.

All which seems to have weakened it substantially (understatement).

Re:Hack-petya mission accomplished – Petya ransomware decryptor by danbruc on Monday April 11, 2016 @07:11PM (#11475873)
I read that on the GitHub page but I am still having a hard time imagining that those changes weaken the function enough to become attackable by a genetic algorithm. According to my intuition even relatively weak cryptographic functions should be pretty hard to tackle by genetic algorithms due to the complex structure of the search space with many extrema. Maybe I will have a closer look tomorrow, I am starting to get really curious.
Re:Hack-petya mission accomplished – Petya ransomware decryptor by SolarNet on Monday April 11, 2016 @09:10PM (#11476493)
I think the limited key space is a large part of the answer, 46 lopsided choices is easier to learn about than 256 equally distributed choices. The smaller word width probably makes the memory requirements reasonable.
Re:Hack-petya mission accomplished – Petya ransomware decryptor by danbruc on Monday April 11, 2016 @04:34PM (#11474857)
I 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?
Re:Hack-petya mission accomplished – Petya ransomware decryptor by lazyjones on Monday April 11, 2016 @05:22PM (#11475216)
I 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.
Re:Hack-petya mission accomplished – Petya ransomware decryptor by lkowalcz on Tuesday April 12, 2016 @01:02AM (#11477371)
Yeah, 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...
Re:Hack-petya mission accomplished – Petya ransomware decryptor by api on Monday April 11, 2016 @04:38PM (#11474877)
It's probably a crap hand rolled key derivation function instead of a proper hash.
Re:Hack-petya mission accomplished – Petya ransomware decryptor by Godel_unicode on Monday April 11, 2016 @05:40PM (#11475350)
Off topic - this might be the single most uttered phrase in crypto reviews in the last year.
Re:Hack-petya mission accomplished – Petya ransomware decryptor by CiPHPerCoder on Monday April 11, 2016 @04:47PM (#11474947)
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.

Re:Hack-petya mission accomplished – Petya ransomware decryptor by matt_wulfeck on Monday April 11, 2016 @05:40PM (#11475353)
Don't these things generate a unique key for each file?
Re:Hack-petya mission accomplished – Petya ransomware decryptor by vetrom on Monday April 11, 2016 @07:18PM (#11475926)
User-space malware, sure. Petya does a full-disk encryption.
Re:Hack-petya mission accomplished – Petya ransomware decryptor by AnimalMuppet on Monday April 11, 2016 @06:51PM (#11475778)
Even 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?)