Password Cracking Beyond 15 Characters and Under $500

got everything managed do you ready to go Travis yep just in the ball yep so next up is Travis Palmer pasture cracking beyond 15 characters and under $500 without burning down your house I assume without burning down your house or hopefully anybody else's right it generates a lot of heat man all right should be able to present excellent all right whenever you're ready all right so yeah this is cracking beyond 15 characters under $500 other titles for this talk for greener pastures are the computational wall or why xkcd advice is easy to understand and hard to do that second one is something that my management suggested and well we'll get to the reason behind that in a second

so I'm Travis I'm also a nerd so I go by the pseudonym tráfico I'm an O SCP osce and G mob if those letters mean something to you and has this tradition for speakers a couple of my favorite hobbies outside of security you're along the right side arma 3 D & E and BWC yes again I am a nerd and my beard is nowhere as magnificent as the last two speakers of this track so I'm gonna kill the video now so that you folks can get full screen slides and also well we've got a lot of content to cook through but as fast as I basically can so for this talk we're gonna start with a fair bit

of background before we get into the meat of things I should give a disclaimer I have limited time so I can't make this an all-inclusive introductory talk if you've never heard of hash gap before and are thinking where can I adopt one this talk is gonna be a little rough to follow just stick around you'll learn something and you'll definitely have some keywords to Google later so let's address well what should always be the first question why

I mean what freezes up terribly we're gonna have to click it we're gonna have to click it well large corporations still are using character minimums that were determined in 1985 by the Department of Defense to be resistant to offline brute-force attacks over a 1200 baud modem and even then they should have been rotated every couple of months they also have complexity requirements that should seem familiar because they become pervasive and are largely responsible for a lot of people honestly believing that taking almost any English word and adding a number in an exclamation point in the end makes it an acceptable password spoiler these policies in isolation have not magically become more secure since 1985 and are

still guarding very sensitive things thankfully most of these websites and companies have some additional safety nuts like detecting questionable login origins or to a Fae well it's set for Wikipedia which well doesn't and historically might have actually had one of the worst password policies on the Internet Thank You Troy Hunt for using a megaphone to broadcast a history here which I just why your fix were zero character passwords was a one character requirement there was also a large number of places where that eight character standard well isn't which frankly is a little baffling given some of the sensitivity here PCI is the payment card industry which this only covers the systems where the payment card info is stored and that seems a

little lackluster the other side of this imagine the kind of information somebody could collect getting in your facebook or pornhub account and imagine what they could do to your reputation by controlling it we just had a talk about this on the same track and then there's eBay and I shouldn't need to explain the level of financial ruin an auction site can bring up if somebody else is bidding for you yeah Wells Fargo a deserving punching bag perhaps but they just haven't wizened up that's a 14 character limit and is there seriously database with plaintext credentials limited to 14 characters in the back ends and there's Netflix it doesn't really make sense why Netflix accounts get hijacked all the

time I understand the want to make for pin for number pins usable but really finally we have a whole suite of devices in tech and I'll pick on Cisco because I love them so much that historically by default no password and the policy might get set by the person installing it but you know eight characters suggested this seems deeply questionable it's especially as a recommendation when again those passwords were determined to be only resistant to attack some networks in 1985 well I'm on the trend of bashing trustworthy sources I should also talk about NIST the National Institute of Science and Technology and what they say given that what they say often seeps into government regulation

special publication 800-53 be released in 2017 said the requirements should be 8 plus characters with no complexity because someone did the Cystic analysis and found out that people actually produce easier brute force passwords under complexity requirements like adding a number and an exclamation point they also say the maximal links should be at least 64 characters hmm a hint of where things might be going there's also this key section here that says increased password length is the key security control and to encourage passphrases you hear that the future is coming slowly and the late 80s might finally end soon the most recent guidance in February of this year my June at the first time it was published from NIST

and the FBI it was a lot more it's flicked on this 15 characters without other complex requirements is where we should be going in fact we should require it as soon as possible and this is in line with what a bunch of other experts and sources that aren't the largest tech companies have been saying for much much longer in fact a security consulting group that I greatly respect Black Hills Information Security makes the suggest in their clients and uses a more paranoid standard of 20 characters internal need though you might be asking okay why is Black Hills specifically on here well it's because I'm picking on them and we're about to listen to some snippets of audio from a webcast last

December I'm not sure if I the next slide my son's computer he's got a gaming computer it takes 8 minutes to crack an LM hash if you take the same 14 character password it would take 4.3 billion years policy that they said in its password policy was secure forever because secure but I mean this technology changes this is warfare right everything is moved counter move we have electronic countermeasures you have electronic counter countermeasures and then it goes up above that and I lose track so okay so we're getting questions about have you run the Google comment word attack against pass phrases so like if you just glued words into a cracker that doesn't that crack passphrases sure

yes it does how many combinations of forward passwords Arthur so how long is that going to take you what if you start using words from a foreign dictionary what if you start putting salts into those words like but I just I think it for forwards and if you start using special characters as a spacer between your words and things like this the question is are you more secure than you were with eight but yes there are attacks against everything so so daring kind of summarize this up this from the field kind of our results but I just didn't want to talk about it we have no success with people who have 15 character passwords approaches zero and

we have tried these things now we're constrained in our time normally we don't have more than a week or so to do our password guessing whereas attacker according to Verizon report they've got like what nine months something like that okay another question Jason yes so this questions come up a few times are spaces legal yes they they are spacious special character and they are very good and I'm just gonna cut it right there so there's a couple of things here and they do give good recommendations it's solid reasoning behind this it's impossible to save an LM hash and when you have more than 15 character passwords so if those really old Windows domains yeah this is

really where you need to be going just to be absolutely certain and they have a couple of other pointed recommendations but perhaps the most interesting thing mentioned is that they have been given hashes from a domain with that 15 character passphrase policy specifically to crack them and the amount that can crack in one week approaches zero basically no success well pack it in presentation over that's all folks know you're not buying that well good because neither am i and i should address the final reason I'm here presenting on this topic in particular which unfortunately does mean we have to have another quick sound bite incubator looking at passwords so passwords are something that's highly audited because it's it's

very easy to do if you're an auditor and you're trying to assess whether somebody's passing muster you can have this rule set and you can walk in and either they pass or they fail and you'll see a lot of that and a lot of companies have this password policy to come straight out of audits eight characters and three or four of uppercase lowercase special characters and numbers I just rattle it off it's been almost 20 years of that so um you know we looked at that though and as we went through the red teaming we found that one step and what we call the kill chain if a attacker were successful and we actually give

them a leg off we actually bring hackers on and bring them in as take employees because a laptop of the password they start and we found one step in the kill chain was taking all the passwords and cracking them and they would run computers with with graphic processing unit augmentation and they've run for hours and they be able to crack a few passwords and hopefully they find a privileged account and then they were off to the races so while there was only one step in what I call the kill chain we decide you know we want to win that battle and here we are compliant but it's just not getting it done I'm just meeting meaning

compliance so we Bram some some math on the whiteboard and we said well what if we went out to a really long password 15 characters but got rid of all that complexity requirements and you know I have a lot of a lot of people with high math SAT scores on my team let's put it that way so we have some great whiteboard battles and you know how much better would it be and that sort of thing what kept creeping in there because of kind of that tick box mentality was what we have to have complexity everybody but we said well let's just try it out so the math held and we felt pretty good about it and

then around that time the National Institute of Standards and Technology NIST released an updated standard and they said what length is king you can get it longer password you get rid of some of that stuff as long as you look for commonly used passwords and block them out so long story short we did it and it took about 90 days to roll it in and the impact has been substantial and the only reason we're able to do that is because we innovated and created this this thing that we called the Kraken that every single day tries to crack all the passwords in the company and we see the success rate of that machine just dropping precipitously sod and I'm gonna

cut him there but yeah that informations public now so let's quickly recap it 15 characters no complexity yes we cracker on domains if you remember my job title yes the above and transitioning to that 15 characters standard was definitely a good idea but well given the existence of this presentation you might guess that it wasn't a silver bullet and it wasn't so we just start talking about that math that Jerry mentioned now the math might hold up but the equation isn't necessarily realistic there is more than one way of approaching this problem and I've heard the argument spun multiple different ways the first of which is it's inconceivable to crack 15 character password because brute-forcing

through all the possible numbers and lowercase letters is 1.6 sextillion combinations which is yes huge massive you're not going to crack that on modern hardware unless you're the NSA another argument I've heard that comes from a better standpoint is assuming the passphrase is made up of words and there are a lot of words around five characters or more so you can say that a 15 character passphrase is probably three words which is extremely difficult and you'd have to go through more than 50 quadrillion options to be sure okay big number but certainly smaller than the last one and the last argument I've heard and perhaps the most educated of these straumann arguments is based on the common

requirement of eight characters doubling that gets you just about 15 character requirement and so maybe we could think about past races as just multiple passwords combines in which case the lowest margin for cracking is just trying all the combinations of two relatively common passwords or common passwords which if you're using the RockYou dictionary well that's still over two hundred and five trillion which they'll say is unreasonable well I'm here to tell you that all of these arguments that say cracking past 15 characters regardless of reasoning can be undermined and they can be undermined by only three factors what are those factors you might ask are you just teasing us is this a timeshare scheme and disguise No the big secret

weaknesses humans inconceivable I know specifically humans are bad at big numbers human packed humans pack complexity on the ends the ends of passwords or pass phrases and humans packet similar humans pick similar things similar things to other humans common things are common because they're commonly picked before I get too far we should define some limits to what is reasonable and I should address the other part of the clickbait II title for this talk why the 500 other limit well besides it being a nice round number that's easy to pitch it's also the roundabout cost of entertainment system and you can safely assume that every type of threat actor you might needing to be worried about including

low stack and your script kiddies has access to this amount of money it's also an amount that can pack a pre sizable punch regardless of the path you take either owning a cracking rig or renting out cloud computing 500 ollars is more than up to go off and build a small cracking system out of a use GPU from ebay and some outdated desktop which should net you around 53 Giga Giga hashes a second against ntlm well you can go the route of the cloud and an AWS 500 ollars gets you 68 hours on a spot instance which yes might get preempted probably won't though with 8v 100 GPUs which you can do manually or you can use a management tool like coal

fires NPK to manage the spot instances for you and both scale and automate the attack if you are an attacker and what you're planning on doing is a series of short running attacks instead of waiting 68 hours for all the results wine automates fitting up 68 instances and just get the results in one sadly NPK doesn't work too well with Google Cloud which appears to be cheaper and you can actually squeeze out 83 hours of time on an instance with 8100 GPUs which besides being terrifically cheap brings us to a terrifying theoretical max of 180 9.3 peda hashes of ntlm we can guess not mega not Giga not tera hedda 189 quadrillion if we compare that

to that last straw man argument of the rock addiction - on top of itself sure theoretical isn't real performance but the difference isn't off by a factor of a thousand times although humans are bad with big numbers which brings us around to the second strum at argument and I'd like to throw in an alternate equation mostly jokingly that is still very conservative for how many guesses it takes to crack a three-word passphrase all of the passwords that aren't obsolete to the 3rd power divided by the number of people in the organization or the number of hashes an attacker has to crack all of which is divided by the factor of human laziness squared how do

you quantify human laziness don't ask me but trust me the value of that variable always seems to be greater than one the very conservative hypothesis here is that people making a passphrase are going to use words from languages they know and can think of during the duress of password creation I did say this was going to be very conservative which tends to be a lot more limited set in fact I'm gonna say right now and support later that pool to pick from four people it seems to be somewhere between 32,000 at 64 thousand words which bring these brings me to a point where we need to break out a lot of math because under minor number one people are bad at big

numbers thankfully people are good at spotting trends after they have all the information and I've done a lot of math for you up front here so let me give you something that's hopefully a lot easier to parse this is a chart of the actual computational limits of combining words together an attack for a single 20/80 TI on ntlm hashes which i pick only because it's consumer GPU and i have access to one the horizontal axis of this chart is the number of words in a passphrase the vertical axis is the size of the dictionary or perhaps a more useful way to think about it the rarest word and a password that can be cracked because the

logical attacker is going to use a list of words by frequency the bigger the list is the rare the words are gonna be in it and as for everything else the numbers in the boxes are the amount of minutes to complete an attack in that search face of the passphrase and the coloration tells you how long that time is relative to minutes hours days weeks months or years because I'm not gonna lie I don't know off the top of my head how many minutes are in a week now going down or to the right exponentially increases the amount of work needed and there are some jumps and difficulty that are sharp and this is where the idea of

a computational wall comes in a seemingly sudden increase in difficulty that you just can't go over but of course this is only the chart for a consumer GPU what about if you 100 well it's actually not that much different there are reasons why a V 100 should be much better but it isn't a variable for this chart anyway what if we had more than one GPU what if we have eight just like those cloud instances well the charts gonna shift down a little bit and open up some options those of you that notice the size of the numbers we're dealing with in the vertical axis already probably have some nightmares to take home but I'm gonna make sure

everyone else has them too and the two word column that is more than 16 million words in 20 minutes basically every word actually in use from every language spoken by at least 1% of the world's population fits in here with room to spare for a couple extra million common passwords and the three word column that is every non obsolete word in the English language that is testable in a matter of hours and the forward column we have a sizable chunk of commonly used words where a targeted attacks a scraping from memos or websites or targeting individual people makes sense now before I get too excited someone I'm sure has been thinking okay cool but that's ntlm what about a slower actually

quote unquote secure hash well here's the same chart for five twelve eunuchs and you'll notice there's still viable attacks on two in three word passphrases and here's B krypter Blowfish configured the UNIX defaults although we do lose a lot of capability we can still go after two word pass phrases as an attacker this chart does make me sad but the reality of most corporations using Windows is that there will be some where something using a hash like ntlm for quite a while to come and as far as the individual user is concerned they need to have a passphrase that isn't going to get cracked when the hashes get dumped either inside their institution or when

a website that they use it's all of its passwords done by SQL injection and let's be real a lot of major websites and companies keep on getting caught with their pants down and we only find out they're using a fast hash the hard way not to mention the difficulty of computing hash is a linear factor in a world where computing power it's increasing exponentially so I'm going back to the other chart because it's time to get into the attacker mindset and play a game of bad recommendations they're first up is Google and yes the advice is old but the advice much like their policy hasn't been updated in more than a decade I love sandwiches isn't a

great example and that mix of leet-speak in case shifting doesn't actually do much for the difficulty I'll be generous and say it makes about a hundred times harder in terms of the rarity the slide shows were various walls various words fall on Google's own most searched words and the most frequently occurring words in the English Wikipedia that's the G number and the W number the fact of the matter here is that the underlying phrases crackable in under three minutes and so even giving them the benefit they doubt on the difficulty of guessing leet-speak substitutions it's crackable in 244 minutes and I should also mention the recommendation put forth in the absolute latest NIST an FBI

recommendation because they suggested a passphrase voices protected 2020 we are but then suggested that a passphrase that's even better is director month learned truck because the words are unrelated while those words might seem unrelated but they all have one thing in common and that's that they're all AI searingly Khan the rarest word here is truck and hoo boy that's in the top 4,000 words regardless of the list you choose for common words are not safe from offline which does bring up another perhaps more viral recommendation xkcd 936 now a lot of people have used this as password advice including management IntercontinentalExchange and the matter of it is the math in ex-ac DS advice as written is fine because it was written

to handle an online attack where the rate of guessing is only 1,000 a second now there is a claim here that the average user shouldn't have to worry about attacks and cracks on a stolen hash but I'm here to tell you from experience the average user doesn't attend a security conference and reuses passwords the average user also works at a company and if that company is larger than a couple dozen people they should worry about stone there dumps hashes both from their infrastructure and their websites that the users are using both professionally and personally a for common passwords yeah isn't safe from offline attacks if anything the xkcd example is actually a little stronger than intended because staple

isn't actually that comment of a word it's number 11,000 367 on the Wikipedia frequency list and just completely off the end of the Google list and the low of entropy xkcd says is a common word well if we say common words are words that are in the first 2048 and the attackers well they're gonna win all the way out to six word phrases yes really six now there are some caveats and the real world isn't as simple as the excel sheet so before we get into rovol the results and the mechanics of attacks we should very quickly cover the things that are going to be ever-present when attacking these passwords using a GPU the first of which is the dictionaries

and specifically the size of the dictionaries there is a lot of bandwidth to go around for operations within a GPU and its memory but transferring data to the GPU while PCIe gen3 by 16 is only 16 gigabytes a second max theoretical not real world and that might seem like a lot but that is against 16 billion theoretical byte that's 16 billion theoretical bytes per second and modern GPU can do twenty six billion real hashes of passphrase per second and one of these numbers doesn't fit within the other and also is real not theoretical the other limitation to be mindful in terms of what kind of attacks are possible is the nature of CUDA unified device architecture I'm not

gonna talk about the AMD equivalent for sake of time cores on the GPU and what they can do which is well not a lot they were built to do lots of single instruction multiple data computations on matrices and vectors of your graphics which means lots and lots of units that can do arithmetic Hale use and not a lot of space or silicon devoted to controlling the nature of single instruction mobile data means groups or in this diagram rows of Al use all need to be doing the same thing at the same time and those instructions in a significant portion of the data need to fit into a smaller shared cache and oh right the instructions is better be

simple and something can actually do because it's something it's not actually implemented and it's not gonna work and this is where we have to say quick thank you to the hash cottage on the Ripper Deb's because oftentimes the best bet in those programs is the best way I actually do it on a GPU anyway and you're better off just finding a workaround so thank you to those dents let's talk techniques and results first dictionary attacks basically checking through a massive list of passwords in a file with or without GPU generating some additional similar candidates to crack through rules we'll do more on that later IntercontinentalExchange we've been running a dictionary attack during the period Jerry mentioned in that sound

bite and we rolled out the 15 character policy and as you can see this graph of the average length of a crack password well the policy wasn't just successful it caused some rapid jumps and links when it actually started getting forced and after implantation the average length evened out despite some outlying spikes this is of course the less interesting half of this story this is the graph of the percentage of passwords that are cracked in dictionary attacks yes that number in the upper left is 50% dictionary attacks are very good when you have a dictionary of passwords made under the same password policy targeted and yes dictionaries also aren't very good after people change their password out under

significantly differed and better policy and start picking things that just aren't going to be in a dictionary anymore in fact if we overlay the two graphs we see multiple downward shifts in the number of crack passwords even after the average cracked password says puffs 15 they have it's the length of those cracks they have sir it's about 15 characters as further enforcement for changing crack passwords was rolled out until it settled somewhere around the one-percent range didn't approach zero it held down near a certain percentage there's always somebody picking and REE picking a terrible password these graphs are trimmed so it doesn't show anything that's happened particularly recently but I assure you straight dictionary attacks have not had

much success but they've also definitely not gone zero sorry Black Hills so let's talk Combinator attacks attacks centered around combining multiple dictionaries or the same dictionary onto itself the attacks pretty straightforward we've already kind of talked about in those computational limit slides so let's get right into the results and well here is the charts of every s phrase password longer than 15 characters ever attracted in your account no exchange that was crackable with the small dictionary of words or common passwords and organized to reflect the charts from that computational wall part of the presentation earlier and in order to do this item modify an algorithm for dissecting passwords called CXC BBN I highly recommend it but it does have one

particular issue and that it doesn't handle common separators like spaces between passwords and a passphrase and apparently the creator's just didn't think that was important and still haven't added it anyway I digress a password a passphrase is slotted here when you fix the algorithm based on how many elements usually words but sometimes a common password CX CBN believes it's made up of and the rear the rarity of the rarest element is based on the number of us is required which should roughly dictate the size of the source dictionary required we can see there's a rather precipitous drop-off somewhere between 30 2016 4 thousand along with a pretty significant preference for three element pass races which hmm might have had something to do

with certain recommendation package with the policy mmm-hmm now this is neat Mel but what about other data sets say not from this company well I considered calling up various companies with a 15 character policy and seeing if they're willing to give me their password hashes but it seemed unlikely so I kinda had to artificially make one here's the results from over 37 million hashes from the have I been poned version two collection where every password known to be less than 15 characters long has been stripped out and this is really only possible because 90% of this list has already been cracked both of the attacks here are pretty shallow and short running and a large cart a large part

because I only need to prove a point and also the hashed right here is going to be artificially terrible this is going to be a recurring theme because when you cross-check 30 million hashes for a match it slows you down a little bit most domains do not contain 37 million people that being said this is one point one four percent of all the pass phrases in the dataset in one attack in less than three minutes are you scared yet good because this is an example of what happens when you use a lot more candidates and you actually start checking for combinations of passwords inside a pass rates if you still remember that third strawman argument oh

this is the entire RockYou data set on top of itself and yeah you can do it and it takes one day in 16 hours in this very weird case on one GPU we're cross-checking 37 million hashes normally this only takes 16 minutes on a single machine and AWS or Google cloud to do this and it cost single-digit dollars now that I've got the would-be crackers it's sighted there are some technical shortfalls with hash cut that need to be quickly noted the combination mode only takes two files input so you're gonna if you want to use this with hash ket and you do want to use this with hash cap you're gonna have to make some intermediary dictionaries to

go after those three and for element pass raises being mindful ooh of exponential file size it's also a similar deal for hybrid mode which only takes one word list and one mask file you could use other programs and pipe in candidates but you pay the piper when doing so on a fast hash you can only transfer so many things for a PCI you the other thing hash guide isn't going to do for you is generate variants of a passphrase candidate with spaces and capitalization that people are actually going to be generally using which well from what I've seen you're gonna want to use title case sentence and lower case both within without spaces easiest way

to do this is with individual rules on a Combinator attack starting with a pre-process dictionary that already has the spaces between capitalized words and then you can just manipulate it you sign off you with the J and K rules to get these spaces and capitalization desired which on the topic of it's another shortfall you can only use one set of rules for word lists in combination mode yes sorry if you want to check lots of different things using girls like common words in between two words you're going to need a honking massive bash file or another program to manage it for you and this is actually what trusted sex hate crack is doing behind the scenes when

they for what they call middle or thorough combinator text alright enough about the conditions of commentators we're not gonna go back there let's move on to Prince attacks which despite the other name for the attack has actually nothing to do with the artist formerly known as Prince is a acronym for probability infinite change elements but its purpose is simple take the path of least resistance and find more passphrases sooner by outputting shorter length candidates first not only is the search space a little bit smaller but we can also expect to find more passphrases here because people tend to pick passphrases close to the minimum required effort this overlap of least resistance motivation is just great for

an attacker how does Prince work well and adjusts a word list it sorts all the contents by length and puts them into separate lists and then begins producing candidates at the minimum the specified length out of the lists of various links iterating through all the possible combinations of lists until all the options are exhausted at which point it moves on to making longer candidates now after the explanation of how Prince works you might be wondering okay why not just use Combinator's of length cut lists aren't Princeton hash get separate programs when I have to pay the piper wasn't that terrible for performance and you just say that a couple minutes ago well yes you do have to pay the piper

and you could manually manage all these attacks with a Combinator but it gets pretty crazy to manage all the lists and combinations for three and forward elements it's doable but you really need another programmer script or some solution that circumvents this and comes right on back to one of the undermining factors this is the positions of dictionary elements in pass phrases here at the bottom and larger numbers mean more pass phrases contained an element straight out of a dictionary in that position and this is again data from inner accountant let's change and there's some one heck of a disparity between the last position in the pass phrase and the rest the pass phrase in terms of how likely it is to contain a

dictionary word that's because humans pack complexity on the ends mostly on the end but sometimes on the beginning so the fix for prints is terrible hash rate on fast hash is when it's piped in its rules because when you use the default hash cat well you can beat in an entire file that can however many rules you want and you're pretty in the clear here but there's kind of a one problem it's most the rule sets out in the internet and that are actually big enough to make use of all the GPUs horsepower while they're not focused on these prefixes and suffixes that are tacked on on the ends for that one you're gonna need something else

which I actually have you covered I made a particular word list that is thrown up and a github repo that will be mentioned a little bit later that contains 4175 rules and soon to come also be releasing a prefix and suffix lists based on the frequency data of the crack passwords in the haven't been poned version to list and this really just focuses on previous instance 20/20 your exclamation point your exclamation point number you get it so let's talk at success rates for prints now the kicker here is we'll be making use of the rulers dimensions so there's not going to be any single element passphrases but we see a repeat of an earlier trend

namely a sudden drop-off between thirty two thousand sixty four thousand and some clustering around three elements including that suffix or prefix so yeah it's it's almost like everybody's doing the same thing Oh like kinda bar and well this works really well for assessing up pass phrases but what about a larger data set well we can also see the reason people like using prints attacks both of these attacks are the RockYou password dictionary at the source and both I stopped at the same time at 1/8 the runtime of the rock you on top of itself Combinator and that entire that complete attack I had mentioned earlier in the Combinator section that took one day in 16 hours

and I'll it got five point eight two percent well these are getting almost half of that in 1/8 the time they manage to concentrate a significant portion of that success very early in the cracking the other comparison to note here is while these are kind of the same attack with one exception and that prince was basically unrestricted for one of these attacks head there's for some reason it might just be this data set might be others but there's a significant man it man to focusing on only three element passphrases and that's because we're also using that role Syd mentioned earlier trying to fix the prefixes and suffixes but it does still show up here and it's notable again - right here is

pretty abysmal so these timings these attacks go much much quicker when you actually have an instance or more GPUs to work with and not checking 37 million hashes and speaking of fast it's about time I get to the new and shiny weird level Markov chains for going after pass phrases that are at their core phrases what our word level Markov chains well the simplest explanation I can give is that it's an over glorified state model to store relationships between groups of words and for this example we'll do a to a 2 gram model think 2 elements in the state and if the phrase were used for the training is the cows eat grass a 2

gram model will record state transitions for the cows to eat and cows eat to grass obviously this isn't terribly useful model by itself but imagine if it had some more training data say some hundreds thousands or millions of sentences the intent here is to build up a model of the relationships between groups of words and if we want to be more accurate we can also increase the number of elements in the state and raise the number of gram at the model of the three now there is one pre-existing proof of concept for this that I could find that actually would generate output fast enough to be useful in password cracking sadly however it was single-threaded

written in a mix of c-sharp and c++ and designed for a Windows compile target which simply wouldn't do for my purposes on Linux so I created something in similar in Python that's parallel uses existing libraries and is a little more multi-platform the nature of Python how well does it do well the astute members of the audience when I showed this table on the right of every passphrase crack that was Combinator findable might have noticed some members that are a little too far to the lower right based on the computational complexity charts we went through before let me tell her that chart for you now the very student view might also infer that I did not in fact

have the limit unlimited access to 81 hundreds and also this chart is strangely positioned in the slide almost as if it extends further to the right well it does I had a single 20 atti for my research and I was also heavily timebox so everything here that the shade of green not from accommodator attack admittedly not a delusion results but come on years little years with accommodating attack but not have yielded some of these and a couple out of the six and seven element column do you any idea how long ten to the thirteen minutes is it's millennia clearly I'm very happy but what about the much larger dataset well it's a similar story these attacks are very

quick even on a stunted artificial case here and I'll be doing a couple of words but admittedly they don't pull on too much only tens of thousands you know whatever the other fact here likely at play here is there just isn't that many pass phrases that are also phrases that exist in this data set and the three and four word area and while I'm here I'd also like to point out there's an accuracy trade-off I did that thing again where I did almost the same attack twice well the difference is for the two forward attacks one of these attacks is to Graham yellow ones three green sighs the model the accuracy of the model and

well there's an accuracy trade-off here it's pretty intense actually the three Graham got a little over half as much but took only 1/12 the time now before people get too uninterested here I really should show them much more impressive slide which is what happens when you put this to use on even longer phrases and well there really shouldn't be much out here in this search space but people seem really content to just use phrases at this length probably because they're these should be safe according to most everyone's advice and these aren't even really common phrases they're actually just kind of normal phrases here's some examples of what isn't safe anymore that entire left side is actual

passwords and these probably aren't past phrases or passwords you were expecting to leave here knowing or crackable and certainly not crackable in one two or nine hours speeds barely over one Giga hash a second do you have nightmares yet because everything here was generated by a Markov model in a simple hash cat rule set and we didn't do any targeting no dumb passwords as input no cherry-picking shanigan x' the training data is completely agnostic admittedly it does produce some strange candidates sometimes and i've collected some of the reader ones i've seen on the right I don't know how we went from intrauterine pressure catheters to Kiwi or Kiwis I can only assume one of the

websites scraped for the trend ghetto was a blog post about making Kiwi or Kiwis with an embedded catheter cowboy advertisement I really don't know now I should head off some common questions I'm anticipating some of you familiar with haschke might be thinking doesn't ash that already have Markov chains why can't they do this well yes it does it has a premade model for character level predictions when you start trying to stretch it out to 15 character passwords and what you want is basically multiple actual word world multiple actual words that model foals are part really quickly not to mention it doesn't store relationships between words and it will basically never finish because the search space is at least 333

sextillion combinations are depending on the particular mascar use them and if you're thinking haven't you tried GPT 2 or some other machine learning algorithm my answer is have you considered hash rates Markov chains are actually a really good fit for this because they are quick especially compared to massive models like GPU 2 which by itself is more than 5 gigabytes intends to take multiple seconds to pop out a single prediction we need millions of predictions per second for it to be remotely viable and password cracking the other side of this is the more advanced models are focused on making paragraphs and complete pages currently need sentences there are very few passphrases have seen that resemble more

than a sentence fragment alright head back out of the weeds here time to wrap up and summarize because if you're not an attack you you've probably been sitting through this talk mildly terrifying for some kind of recommendation allow me to wait allow me free to let you wait slightly longer by addressing the red teamers first red teamers please don't cop-out 15 character passwords or pass phrases are hard but they aren't that hard to crack even against a be you should at least be doing Combinator's prints attacks and Markov chains for the duration of your engagement don't pretend that your results should approach 0 it should never be 0 and there will always be somebody who picks

hello spring 2020 as their passphrase blue teen your turn finally do the math that applies to your situation and do a little more than just gather some people that score highly on SAT a decade or more ago in a recompensed room and whiteboard it if intercepted or dumped hashes or personal password reuses our concern for you and it almost always should be feel free to use my math and represent it unless your organization is cracking its own passwords you won't know what people are using recommend the best behaviors but plan for the worst which brings me to something that can maybe serve as a starting point for what to pass along to end users and this is my personal

recommendation and a starting point so you better bet it's fairly paranoid but the intent here is to make sure a hash can't be cracked in $500 for expense regardless of the type of hash which means making an illogical unlikely phrase of five or more relatively uncommon words that are thematically unrelated we're talking about diabetic unicorn traps Chicago tunnel as a passphrase and unless you force these hacker to use a large dictionary combining all the different types of words cities structures fantasy creatures verbs medical conditions and use some words that are uncommon you're going to be building your security posture with some cracks already built into the foundation especially if you're working with fast hashes all right any

questions all right let's see here none in the GoToWebinar I did see a couple people mention that their brains might have exploded from them the math on a few of those slides there yeah I said we'll apologize I have a bad habit of trying to pack a ton in but it is recorded so yeah if you could have your pocket this morning yeah it's wonderful stuff how difficult is it to get started cracking on these for the red team that's one question I see well so I mean I can put it this way all of the data that was collected here was with attacks using only one GPU so admittedly I was targeting pretty fast hashes but I have

a personal machine that's been cooking away at the right of me and I have a machine for my corporate environment that remains inside the corporate environment that we do cracking on to crack our own domain and that one again doesn't have very much in it so you definitely can get going with just a consumer GPU and as far as good places to start yes we got one I knew at least one as far as getting started I will say the hash Catman page is a little hilariously daunting and it actually doesn't have all of hash Katz's line arguments in it so you actually have to go to hashtag org if you want all of the

information on it and I would strongly recommend seeking out because there have been a lot of videos in the past by other people who speak a lot slower than I do and are much better at explaining things than I do yeah um yeah hopefully that GPU gets do some fun stuff not just cracking passwords gets to do some halflife Alex something like that yep ah let's see I know I saw at least one other one in here is there any password cracking that uses machine learning to come up with better algorithms than these straight up learning what people generally do yeah so there are a couple of things that people have put forward though they tend to still at they're

like core work off of Markov chains and that is a lot to do with when you're doing this like convoluted neural network or you're doing this back learning neural network whatever neural network you're using for a machine learning algorithm once it gets to the point of machine learning you're spending a lot of computing power just making candidates when you could have been spending that computing power trying candidates so for the Markov chain the tax that I've been doing I I am okay with a bunch of Afghanistan in the Honda Accord weekend today it's coming out of this even though that's almost guaranteed not going to be somebody's password it took me less than one nanosecond to come up

with and it can immediately be just tossed in the pile with the rest of the candidates and one of the candidates won't be much better off and yes you can get the slides the slides are up on Schedule D or however you want to pronounce it schedule you can just tell just the schedule website skin I call it skin um let's see so one question GT X 1080 Ti or two atti I guess that's asking like but given the cost difference you know I'm sure 1080 T eyes are much cheaper than so eighty guys yeah I I cannot remember off the top of my head what those benchmarks are for a 1080 CI but I'm gonna guess almost

immediately based on what I've seen the ebay prices for and personally taken advantage of the ebay prices for your tenet ET eyes are probably a lot easier to get ahold of and you can get them for around three to four hundred bucks easy there's a lot of crypto people still offloading them I need to bring them like yeah yeah you can absolutely slot these in even if you don't need a video Szalai to work for haps got to eat all of your GPU thank you so that's definitely an option okay yeah I think that person was just saying that they saw both on the sides and they weren't clear which one it was that you

were using both yeah that's between corporate machines or personal machines is the answer for that one well sadly I do not have a twenty ATT item okay gotcha all right I think that's it for the for the questions you probably want to go check out the track one channel in the in the discord see if there's any that I'm I missed in there and there's a lot of good chat in there about about your talk very good stuff alright Thank You Travis thank you