Show HN: Cracking passwords with a simple genetic algorithm

https://github.com/lyle-nel/siga

by lyle_nel • 10 years ago

149 58 10 years ago

github.com

saganus2• 10 years ago

Interesting approach.

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?

lyle_nel21• 10 years ago

Yes the training set should be representative of the candidates you want to crack, also the larger the training set is, the better it seems to perform. It is also important to note that, as passwords are being cracked they become part of the training set. So the program can start of completely blind then it will figure out common structures as the simulation progresses.

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

Phemist• 10 years ago

So XKCD style correcthorsebatterystaple-esque passwords would fall in no time?

sundarurfriend• 10 years ago

I don't understand, what is the input and output of this at a conceptual level?

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.

lyle_nel21• 10 years ago

There is total separation between the myspace list and the rest of the program. The only thing the simulation can do is query hit or miss. Through these hits and misses it figures out what are the words inside the myspace list. The situation is exactly the same when the list is full of md5 hashes, except we hash the candidate password now before we check for a hit or miss.

"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

lyle_nel21• 10 years ago

I changed the example since I realised that it is a bit hard to understand. The example now shows how to crack a list of md5 hashes. All I did was convert the myspace list to md5 hashes. You can now try and crack the myspace list in the program's md5 mode. Sorry for the confusion.

ivoras• 10 years ago

I think it's about finding substrings which are (very) likely to appear in passwords.

Like substrings "pass" and "word" in "password".

StavrosK• 10 years ago

The fitness function is "how many passwords did this individual match", basically.

lyle_nel21• 10 years ago

Not really, there is no fitness function, there is only some implicit selection pressure. Remember, a single individual is a single password(a string). The program does not keep track of how many viable offspring a parent produces. All an organism does is have sex with other strings in the hope of producing viable offspring(another cracked password). This carries the genetic information on to the next generation while the older generation keeps dying indiscriminatingly, whether they were fit or not since there is no fitness function.

justifier5• 10 years ago

adding possible combinations of characters, ngrams, from the 'organisms' file and checking them against a leaked password list, apparently tested on the 'rock_you' list of leaked myspace passwords, which is ommitted from the repo but the repo has a standin empty file where you put your own list of leaked passwords

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'

krick• 10 years ago

unless government officials are protecting their access with passes like 'WARMACHINEROX'

I chuckled, imagining how some government official changes his password right now.

lvs• 10 years ago

It's not accurate to say there's no fitness function. There is a fitness function, but it is not a continuous function. (There's no way to have a GA without some notion of fitness.)

lyle_nel21• 10 years ago

There is no explicit function that decides which organisms are more fit than others. But you are right that there is selection pressure since all organisms have the same lifetime(they are eventually popped from front as newer ones are pushed to back). This means that if they did not produce viable offspring, the genetic information does not stay in the simulation.

YeGoblynQueenne4• 10 years ago

Like I say above (my comment was tongue-in-cheek but) I really like the idea of a FIFO queue rather than an explicit fitness function. I'm thinking of writing a little a-life/learner thingy just for fun at some point and I'll definitely nick your idea. Is it a common approach in genetic algorithms? Is there some research on it?

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?

chirau• 10 years ago

Would you care to explain like I am 5? Layman's terms... What are you doing and how are you doing it?

lyle_nel21• 10 years ago

The topic assumes some knowledge of genetic algorithms as well as password hashing.

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.

TheOtherHobbes• 10 years ago

Even simpler, it:

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.

YeGoblynQueenne4• 10 years ago

It uses a stack [1]. Therefore, I like it <3

[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.

lyle_nel21• 10 years ago

That's correct. It is a queue

ryanlol• 10 years ago

How fast can it go? And alternatively, how fast can it go with hashcat?

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.

lyle_nel21• 10 years ago

When using hashcat, it will run as fast as hashcat's dictionary mode. Since we are being cute with named pipes, hashcat thinks its reading a dictionary. There is a caching problem with hashcat though, that is why I set the segment size to 1, so that it can update siga's gene pool as often as possible. I am optimistic that there might be a solution to that so that we can leverage hashcat to its full potential.

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.

Vendan2• 10 years ago

one thing to note is that the gpu hashcat uses a very complex cacheing, which basically boils down to a buffer per password length, i.e. a buffer for 12 character passwords, a buffer for 13 character passwords, and shoves passwords in accordingly. Once a password buffer hits a certain threshold, they all get sent to be cracked. This means you may not get feedback for a certain length try for a while, if it's not a common length. One thing to consider would be to figure out that threshold and keep things internally until you hit it, so you can fill a buffer in one shot. Realistically, you aren't going to get around this very easily, as this buffering is done for performance reasons, in that some of the kernels used rely on same length passwords for performance increases.

eternalban2• 10 years ago

~OT: I predict John Koza's Genetic Programming [1] approach will enjoy a revival in the near future. We've discussed the impact of the recent crop of "AI" systems on various work fields, but my bet is on IT programming being one of the earlier successes of having machines doing grunt work.

[1] http://www.genetic-programming.com/#_John_Koza%E2%80%99s_Pub...

mrfusion• 10 years ago

Sounds interesting. Can you expand on why?

justifier5• 10 years ago

because these genetic algorithms are best suited for consistent behaviour

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

eternalban2• 10 years ago

There are interesting developments in formally defined and verified programs (including implementations). For certain domains that are non-intuitive, exploring the solution-space is now much nearer in reach.

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.]

Houshalter• 10 years ago

This is really cool. I'm surprised just finding common substrings through evolution works so well. Wouldn't just using the existing substrings in a dictionary work better than mutating new and random ones?

And is it really moral to do this? The only applications of this are pretty unethical.

lyle_nel21• 10 years ago

I have found that top say 2000 ngrams from a large password list is a good starting population. That being said, it learns the structure of passwords surprisingly fast if you start of with purely random organisms.

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.

chm2• 10 years ago

It's not clear to me what this does, or if it's useful. You have a fixed-length vector of strings and you make cross-overs between elements in the vector based on non-uniform random distributions. That is to give more chances to younger offspring to procreate. Then you apparently remove the oldest (i.e. first) strings in the vector, and replace them by appending offspring. But then you also mention you are not deleting older organisms. I'm a bit confused.

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?

lyle_nel21• 10 years ago

The part about not deleting organisms, is a small caveat that I omitted in most of the discussion since it makes the algorithm just a bit harder to understand. To clarify that point, since you asked, the organisms can be popped from the front of the container if we provide a maximum population size. If we do not provide a maximum population size, we do not delete the organisms. Older organisms do however lie dormant due to the non-uniform distribution, thereby providing the same advantage as selection while preserving a greater degree of genetic diversity. If there is anything else that is not clear to you then I am open to any questions you might have. I will help where I can to clarify things.

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.

chm2• 10 years ago

Wow, I am surprised about the "aaa..." password. Thanks for clearing that up.

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?

antirez2• 10 years ago

I loved this, since it's a different approach to genetic programming (with the FIFO list) that could work in different kinds of problems. Also the way it is applied to password cracking itself, is an extremely interesting way to exploit the non-random properties of real world passwords.

lyle_nel21• 10 years ago

I really appreciate your enthusiasm. It is one of the core concepts and passwords seemed to be a good way to explore my FIFO idea in a practical manner. It might well have been done before, but from preliminary searches I could not find anything on it(not that I searched really hard). Due to its simplicity, I suspect it will lend itself to some pretty efficient implementations.

I would be interested to hear what other kinds of problems you see it being used for.

antirez2• 10 years ago

Not sure exactly what would be another application, but it's a mental model that looks "general", when we have a few prerequisites, that is, not just a solution, but multiple solutions to a given problem (find a password among many hashes in this case), and where solutions could be related in some way so that using the past solutions could restrict the search space.

Show HN: Cracking passwords with a simple genetic algorithm

Related Stories