5 ms·

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

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?

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 ago
  This 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 ago
    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.
    - Houshalter 11y ago
      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.
      - j2kun 11y ago
        Sounds like Blum-Blum-Shub https://en.wikipedia.org/wiki/Blum_Blum_Shub https://en.wikipedia.org/wiki/Blum_Blum_Shub
- a39fa31c 11y ago
  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/#more-307 https://klondike.es/klog/2016/04/12/cryptanalyzing-petya/#mo...
danbruc 11y ago
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.
- SolarNet 11y ago
  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).
  - danbruc 11y ago
    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.
    - SolarNet 11y ago
      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.

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?

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 ago
This 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 ago
  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.
  - Houshalter 11y ago
    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.
    - j2kun 11y ago
      Sounds like Blum-Blum-Shub https://en.wikipedia.org/wiki/Blum_Blum_Shub https://en.wikipedia.org/wiki/Blum_Blum_Shub
a39fa31c 11y ago
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/#more-307 https://klondike.es/klog/2016/04/12/cryptanalyzing-petya/#mo...

danbruc 11y ago

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.

SolarNet 11y ago
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).
- danbruc 11y ago
  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.
  - SolarNet 11y ago
    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.