7 ms·
Show HN: Cracking passwords with a simple genetic algorithm
- saganus 11y agoInteresting 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_nel 11y agoYes 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 11y agoSo XKCD style correcthorsebatterystaple-esque passwords would fall in no time?
- lyle_nel 11y agoAlmost yea. In a few hours it manages to find these horse related passwords. 15 strawberryhorse 15 ilovehorses1995 15 ilovehorses1994 15 ilovehorses1234 15 horselover4ever
- aidos 11y agoCool system. For clarity though, those aren't xkcd style passwords. They're words that form a normal pattern. Xkcd requires that the words are randomly generated.
- cheshire_cat 11y agoSorry for going slightly OT but I think more people should know this: xkcd style passwords are actually called diceware passwords [1], the wikipedia article [2] links to arstechnica that reported in 2014 [3] that the original author upped his recommended diceware password length to at least 6 (random) words. You can obviously always use a bigger dictionary too (as long as you choose truly random). [1] http://world.std.com/~reinhold/diceware.html http://world.std.com/~reinhold/diceware.html funny enough, chromium doesn't like the ssl versions the site uses "ERR_SSL_FALLBACK_BEYOND_MINIMUM_VERSION" [2] https://en.wikipedia.org/wiki/Diceware https://en.wikipedia.org/wiki/Diceware [3] http://arstechnica.com/information-technology/2014/03/diceware-passwords-now-need-six-random-words-to-thwart-hackers/ http://arstechnica.com/information-technology/2014/03/dicewa...
- justifier 11y agothis is easier to understand with a bit of math.. let's say you have a pad lock with a 4 number combination, each of those numbers being a ring of 6 numbers themselves(o) we have four 'slots' with six possible numbers for each slot that means there are a total of 1296 combinations, (possible values)^(slots), 6^4=1296 a contemporary computer can do 1300 calculations perceptually instantaneously now we look at randall and diceware's suggestion of using a series of words to bulk out your password, since a word in english is built of a possible combination of 26 character alphabet the possible values becomes 26 for a four letter word, all possible combinations of those 26 characters becomes 26^4=456,976 possible combinations, again, all values can be computed in nanoseconds what i think randall and diceware is hoping to achieve is a higher permutation value with little tax on the user's memory conceptually [c,o,r,r,e,c,t,h,o,r,s,e,b,a,t,t,e,r,y,s,t,a,p,l,e] is 25 characters long with each 'slot' having 26 possible combinations.. 26^25~23x10^34, that is a huge number of possible permutations which makes brute forcing finally impractical but here is where the whole thing starts to break down a bit.. because the suggestion is to use real words to aide in remembering which negates character length in lieu of number of words that also means that figure above is significantly less because the first in that list of 456,976 permutations is ['a','a','a','a'] which would be invalid in regard to existing words, so in reality that 450,000 figure is significantly less 'correcthorsebatterystaple' can be broken into 25 characters 'slots' or 4 word 'slots': [correct,horse,battery,staple] what was 26^25, is now (possible words)^4 we can keep going, look at randall's most recent book(i), using the 1000 most used words possible words becomes 1000 and 4 slots we are looking at 1000^4=1,000,000,000,000 possible permutations which will take a contemporary laptop a few hours, respectively, to churn out all this broken into a chart: 81 = 3**4 : [(3),(3),(3),(3)] 253 = 3**5 : [(3),(3),(3),(3),(3)] 256 = 4**4 : [(4),(4),(4),(4)] 456976 = 26**4 : [(26),(26),(26),(26)] 1000000000000 = 1000**4 [(1000),(1000),(1000),(1000)] ~230000000000000000000000000000000000+ = 26**25 : [(26),(26),(26),(26),(26),(26),(26),(26),(26),(26),(26),(26),(26),(26),(26),(26),(26),(26),(26),(26),(26),(26),(26),(26),(26)] ~640000000000000000000000000000000000000000000+ = (26*2+10)**25 : [(62),(62),(62),(62),(62),(62),(62),(62),(62),(62),(62),(62),(62),(62),(62),(62),(62),(62),(62),(62),(62),(62),(62),(62),(62)] what this is showing you, is that anything that makes things easier for you also will make things easier for a cracker for best security increase the number of characters when possible avoiding words.. using a combination of lowercase(26 characters) and upper case(26 characters) and numbers(0-9, 10) for 26+26+10=62 possible values.. and put those characters in as many slots as you can muster (o) http://www.padlocks4less.com/media/catalog/product/cache/1/image/9df78eab33525d08d6e5fb8d27136e95/c/o/combination_padlocks_2.jpg http://www.padlocks4less.com/media/catalog/product/cache/1/i... (i) https://xkcd.com/thing-explainer/ https://xkcd.com/thing-explainer/
- minitech 11y agoNo, the point of that style of password is that you choose the words randomly. Random words are just easier to remember than random characters.
- sundarurfriend 11y agoI 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_nel 11y agoThere 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_nel 11y agoI 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 11y agoI think it's about finding substrings which are (very) likely to appear in passwords. Like substrings "pass" and "word" in "password".
- StavrosK 11y agoThe fitness function is "how many passwords did this individual match", basically.
- lvs 11y agoIt'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_nel 11y agoThere 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.
- YeGoblynQueenne 11y agoLike 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?
- lyle_nel 11y agoThe queue structure is one of my own ideas. It is possible that it has been done before, but I did not check. There does not seem to be a lot of research on this topic. That being said, it is a nice toy problem to explore genetic algorithms and diversity. Regarding the stack approach, I would suspect that new genetic information would immediately be lost since a new organism dies before having much chance to produce offspring. In the off chance it manages to produce offspring, those offspring would also be lost almost immediately since they get popped first. If you are really curious, you can change line 163 in vivarium.cpp from a pop_front() to a pop_back() to see what happens.
- chirau 11y agoWould you care to explain like I am 5? Layman's terms... What are you doing and how are you doing it?
- lyle_nel 11y agoThe 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 11y agoEven 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.
- lyle_nel 11y agoYes it is completely useless against random strings as one would expect, but with word salad it not completely useless. For example, it can find words like "tequieromuchogerald" and "paulaalejandrailove" easily enough. I haven't fully explored its ability to do this, but I suspect starting with a dictionary of words instead of a random population might aid it in finding XKCD like random passwords. In general I don't disagree though, passphrases if chosen correctly can be completely intractable to a password cracker.
- YeGoblynQueenne 11y agoIt 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_nel 11y agoThat's correct. It is a queue
- ryanlol 11y agoHow 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_nel 11y agoWhen 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.
- Vendan 11y agoone 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.
- eternalban 11y 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_Publications http://www.genetic-programming.com/#_John_Koza%E2%80%99s_Pub...
- mrfusion 11y agoSounds interesting. Can you expand on why?
- justifier 11y agobecause 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
- eternalban 11y agoThere 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 11y agoThis 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_nel 11y agoI 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.
- chm 11y agoIt'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_nel 11y agoThe 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.
- chm 11y agoWow, 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?
- antirez 11y agoI 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_nel 11y agoI 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.
- antirez 11y agoNot 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.