One of the examples apparently takes a list of leaked passwords from MySpace - and so what does it "crack" then? I think the phrase "high impact substrings" down in the explanation is the key, but it's not wholly clear to me what the ultimate purpose of this is.
The 'GA without a fitness score' idea seems interesting, but it would help to know what exactly the algorithm is trying to do.
"what is the input and output of this at a conceptual level?" Our input is the dataset we want to crack, and our output is the passwords that were successfully cracked. In a more conventional scenario, we would have a list of hashses that need to be cracked. So the steps are
1. pick parents at random
2. crossover and maybe mutate
3. hash the child
4. see if the hashed child exists as a password in our list of hashses we want to crack
5. if it does, add the child to the end of the container and pop the oldest organism from the front.
6. goto start
it will genetically run through all ngrams and check if it is in the pass list to determine how to advance the evolution of the algorithm
does this crack passwords genetically? well, yes and sorta
it's a proof of concept against an existing list of real leaked passwords, proving that it could efficiently crack a number of these real passwords real people were using to protect real personal data
but from there you have to extrapolate the effectiveness on all possible passwords..
if you train against the myspace list then the passwords would have to resemble myspace passwords
can you train the algo on the myspace list then try to crack nuclear codes? very unlikely, unless government officials are protecting their access with passes like 'WARMACHINEROX'
I chuckled, imagining how some government official changes his password right now.
Like substrings "pass" and "word" in "password".
[1]: http://www.genetic-programming.com/#_John_Koza%E2%80%99s_Pub...
For example (as I noted in private communication to John Koza) exploring the protocol-space of distributed consensus algorithms on top of something like Microsoft Research's IronFleet (with the GP generating Gafny code) appears to be both possible and imo a fruitful avenue for researchers in the field.
[p.s. Note that Genetic Programming is distinct from Genetic Algorithms.]
i noted in another comment that this ga cracker repo will only work on passes that resemble the ones it is trained on, but like all genetic algos is aggressively ineffective on inputs resembling anything else
as for programming the practice, it is embarrassingly redundant and consistent due to the structure of programming being based on grammars and logic
so imagine a program that has a data set
you need ten bits of information about that data set, like max, min, mean, etc..
so you write 10 individual functions to loop over the data and interpret it
that is all very consistent behavior and code
now imagine you write a simple genetic algorithm that can interpret your interests and write those simple loops for you on the fly
ten functions of 10 lines each is 100 lines of code
one function of 30 lines that can generate then discard those ten previous functions gives your program a 70 line and immeasurable man hour advantage
think if a search engine needed an engineer to explicitly write the discovery function of every possible query, it would be impractical, so instead you imagine generalisations that permit simple functions to take many varying inputs and produce many varying outputs
what i think the parent comment is suggesting is that these generalisation functions themselves could be built by computers and one possible method being genetic algorithms
furthering the abstraction
all puns intended
Also, for some reason I thought you actually used a LIFO stack. So, what if you did? My guess is organisms that put more offspring on the top of the queue would take longer to be popped from it, so that they'd have a better chance to produce more offspring. They would also benefit from organisms almost as successful as themselves (but not more).
Is this also a known approach, and if so, how well does it work?
Especially if you were to feed the training set with most-used password lists from leaked databases or similar.
Do you have any performance metrics against bruteforce for example?
I have not put them head to head, but the program seems to find passwords that are far outside the tractable search-space for a bruteforce attack. Passwords like the following are found withing a few hours:
34 a111111111111111111111111111111111
20 12345678900987654321
19 9876543211234567089
19 password12345678910
18 sexytinkerbell2013
18 prettyprincess4812
18 mickeymouseforever
18 littlepinkprincess
18 iloveyoumomforever
I think it's wrong to say you don't have a fitness function. Your fitness function is "Is this string a password?" and the score is binary. Why do you say there is no fitness function?
Also, in your examples, is "aaaaaaaaaaaaaaaa" really a password?
With regard to the fitness function, I think I agree with you that checking if the offspring matches a password will fall in the category of a fitness function albeit a binary one. I will update my description to include that, thanks.
With regard to if it is useful, I will let it stand or fall on its own merits. If people are going to use it to find bad passwords, then I would say yes it is. It might be pertinent to mention that I am interested in genetic algorithms in general and this is a good practical way of exploring my own theoretical ideas.
Yes, "aaaaaaaaaaaaaaaa" really is a password. Have a look at the rock_you list of passwords and sort them by length. There are some extremely long but silly passwords in there.
When I asked how useful this was, I assumed the organisms were removed from the front of the list. If you keep everything, then yes I can see how this can be used to crack passwords. It's not clear to me how it would be useful otherwise, as which organisms stay in the list is not homogeneously random, and so one organism might be quite unlucky (even though its offspring could have been very successful).
So basically this can be viewed as an accelerated brute-force of long/complex passwords?
This looks awesome, but without the GPU speed advantage I'm not sure how well it'll fare against the almost 80GH/s I can do on my desktop with cudahashcat.
It might be interesting to note that the older versions of hashcat seems to have supported reading candidate passwords straight from stdin. I have not played with that yet, but I suspect it might work a bit better.
I would be interested to hear what other kinds of problems you see it being used for.
You can look at the section "How it work" on my github page for some diagrams and a decently lengthy description.
In simple words: Each organism is a password(a string). Passwords can mix(have sex) with each other in novel ways to produce offspring. If the offspring(a mix of the parents) also matches a password, it is added to the list of organisms. Older organisms eventually die, so it is up to the offspring to keep producing offspring in order to preserve the genetic line. The result of this simulation is that high impact substrings like "love", "luv", "mother" and "fuck" stay for a very long time in the genepool since any organism that consists of at least one of them will have a better chance to produce a child that is a password(viable offspring).
If you still don't understand, feel free to ask more questions.
1. Finds the substrings that are popular in passwords. 2. Combines them to make likely passwords that haven't been tried yet. 3. Rinse and repeat
Useful against noob passwords - of which are there many in the wild - and more effective for some applications than the usual dictionary search.
But ineffective against randomised strings like KPF27k5ANv791P2Yi88xd88D7iALX3kH, or against XKCD random word salad passwords like QuantumGerundApoptosis as long as they include at least one unusual word.
[1] The stack is used in place of an explicit fitness function. I have nothing against fitness functions. But the bit about using a short stack instead, is really cool.
Edit: Woa. Hang on. New organisms are pushed to the back of the structure while dying ones are popped off the front- so that's a queue. My bad. But I still like it.
And is it really moral to do this? The only applications of this are pretty unethical.
As for the moral argument, even though this has probably been discussed at many different venues on many different occasions, I lean toward the sentiment that having good tools to gauge how good your password policies are is essential. Not to say that this is a good tool, but it is _a_ tool.
