Are you sure you really want to do this? According to my calculations, (assuming I didn't make a mistake) that is at minimum 62^16 possible passwords, just counting letters (both cases) and numbers. This comes out to 4.767240e+28 possibilities. Assuming you can check 1,000,000,000 passes per second, it would take you 1.510647e+12 years to check all of them.

What most password cracking programs do is use a dictionary of words and/or phrases, and make variations on those (ie. convert letters to numbers, i -> 1, o -> 0, etc.) and check all of those. Brute forcing large passwords is very time consuming.

There are a number of good password cracking programs out there already to check your systems, such as John the Ripper.

I want to design a password cracker (I swear to you that I'm not using this for nefarious means, it will be used by my Network Security business), that tries every possible character combination for a 16 character password.

And you would use that to do what exactly? Explain to your customers that they need 17 character passwords to be safe?

Having a tool that unerringly cracks passwords isn't much good for anything but nefarious purposes. It wouldn't provide any insight into how good a password may or may not be.

The fact that the problem is too big for you to easily solve is a good thing. In fact, it's the whole reason we use passwords in the first place.

-sauoq
"My two cents aren't worth a dime.";

But let's stop there and think about something ... since you are wanting to put together every possible combination of characters that can be used in a password ... well, if your program finishes before you die, you will crack every password ever thought of, and no password will be good enough. Maybe you should concentrate on detecting the use of a password cracker instead, and how to track down the dog that is trying to compromise your system.

jeffa

L-LL-L--L-LL-L--L-LL-L--
-R--R-RR-R--R-RR-R--R-RR
B--B--B--B--B--B--B--B--
H---H---H---H---H---H---
(the triplet paradiddle with high-hat)

You could create N number of threads and pass each one different pieces to work on.

If you're interested in speed, I would not use Perl threads... ;-)

Liz

Some points to consider:

• As stated, given current hardware it'll take many, many years to crack a password the way you're doing it, so we need another approach.
• How do you know the passwords are 16 characters? What about 15, 14, etc? Which characters are you assuming to be in the password?
• You have to narrow the possible spread of passwords. Have automated methods of gaining as much information as possible. If passwords are randomly generated, attack the algorithm that generates them. If they're created in such a way to be memorable, take this into account. Obtaining the target's password generation policy would obviously be a major advantage (remember, insiders can perform the attack as well).
• Have you considered alternatives? Some of them aren't that great, but given your approach they would probably be a good starting point. Check out John the Ripper for one of the better ones.
• How is this going to run undetected? That's a much greater problem. Proper logging is essential to security.
• Finally, are you focusing too much on password cracking? Often there are many weaker points of entry you can exploit. If passwords are truly randomly generated 16-char (alpha-U/L, numeric, punctuation/symbols) strings, you're not going to be able to crack them and will have to find a different point of entry.

If you're looking for a general security resource, you should take a look at Practical Unix & Internet Security, 3rd Edition, it's a damn good book, one of the best I've ever read on security.

Best of luck with the security company :)

A few more points:


• The only reason you would need to check all possible passwords is to crack a password -- if you are looking to test security check for weak passwords (dictonary words). There is no other reason to try such a silly task.
• The only ways someone would be able to crack a password on your system are If they know a user name, if they have access to the file or store that contains the password, or have unfettered access to "try" passwords against that store. Look to stop these 3 things and find weak passwords and you are as secure as you can be (password wise at least)
  
  -Waswas

Other people have discussed the security aspect, I want to point out something different: the illusion of randomness

When I have to search for something by brute forcee, as you are suggesting here, I feel the same urge to randomize my guesses. But, unlike horseshoes and nuclear war, a miss is as good as a mile. It doesn't matter is you have one position wrong or 16. For each character position in the password, there is one correct character and 60, 70, 80 wrong ones. None of the wrong characters are closer in any sense. The enemy will not be intimidated into surrendering by your scatter-bombing.

If you run many tests of trying to reverse-engineer a password, both scatter-bombing and boring iteration will, on average, require N/2 guesses, where N is the total number of potential possibilities. Sometimes you get it right the first time, sometimes you have to spend all 1,500,000,000,000 years. In non-average cases, scatter bombing doesn't help, either. There is an equal probablity that the password you want to decode is aaaaaaaaaaaaaaab or deadbeefcakebabe. The iterator will get the first one on the second guess; the scatter bomb may not get there for a few million years.

deadbeefcakebabe might not be a good selection for a password, by the way.

--
TTTATCGGTCGTTATATAGATGTTTGCA

it'll never happen, but were i to go about it i would do it like this...

• grab one of the cheap broken random number generators, i'm thinking of the kind that are like 8 bits that cycle through some pattern based on their last value plus they cover all 255 values once and once only before they repeat. so if you had 3 bits and you started at 4 you might get 4,5,3,7,6,2,0,1, and repeat 4,5,3,7,...

• stick together 16 of those 8bit pseudo-random cyclers, seed them all with 0 if you picked different generators for your different bytes, if you used the same generator for all 16 of your bytes you'll have to seed them (and keep track of the seeds) with random numbers.

• run 255 cycles and you have 255 pseudo-random passwords. increment the seed of the last generator and cycle off 255 more passwords. repeat incrementing the seed of the last generator untill it rolls back around to 0 (or the number you seeded it with (don't forget to wrap at 255->0)), then you increment the second cyclic pseudo-random generator and repeat, repeat, repeat.

• eventually you'll get to where your seeds are 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,254 (or maybe 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 if your inital seeds were 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 ) and presto, you've generated every possible 16 byte password in a pseudo-random order without ever doing the same password twice.

• as a bonus you even get the ones with characters that aren't likely to be allowed as passwords for the system (and wouldn't likely be checked by some of those fancier programs).

good luck.

if you happen to find a good 128 bit pseudo-random cyclic generator let us know!

I am really curious though. What type of serious application would require to crack the password? Is it about checking security of your system ? If it's so and applying your method, it sounds like a safe bet before even you begin looking for the programs. May be we can suggest something alternative, knowing more about your application.

artist

Is it about checking security of your system ?

Judging by his post I'd assume it's for checking system's he's authorized to perform audits on.

May be we can suggest something alternative, knowing more about your application.

Most of the major password cracking programs out there just aren't that good. They don't allow for the flexibility to customize your rules. Anyone who's half decent at cracking won't just sit down and brute force it, they'll look for the weakest link, find out everything they can and construct a profile of the user, then make very targeted guesses at their password. You'd be amazed how effective this can be.

WOW!!!!

I definitely did not expect to get this many posts so fast. Thank you to all who commented on this subject, even if your post was a negative towards me. There's so many things to comment on here, I hope I get them all.

1.) First off, I'm not a hacker, not at least in the sense that I only do it when I'm asked and/or paid to do so. I don't call myself a hacker, I don't even think of myself as a hacker. Hackers/Crackers whatever you want to call them are who I'm paid to stop. This will not be a hacking tool.

2.) I fully understood the hopelessness of this before I posted, I had just hoped that someone who knew more of algorithms than myself might know of a way that by randomizing the order, I might be given a considerably better chance of guessing.

3.) Now some of you are probably asking why I would bother asking if I already knew this, well, I don't know everything, I thought someone might know something I didn't. I mean, there's people on here talking about things that I've never even considered, I figured it was worth the effort.

4.) For those of you who suggested a dictionary attack, thank you. I have actually already implemented this, in fact, the script that I use right now is fairly similar to the attacking method that L0phtCrack uses, if any of you are familiar with that. It not only uses a dictionary attack, but also a hybrid attack that takes a dictionary file and combines it with a brute force attack, prepending or appending characters to the dictionary string. This gets those tricky passwords like 123pass. It also does some common letter substitution if you tell it to, so like 123p@ss.

5.) For those of you who talked about password strength and how if I could brute force one I could brute force them all eventually, I'm aware of this. That's why I check them with my Dictionary/Hybrid script. This brute force thing was purely research, and I would likely have never have used it for anything but.

6.) I know that 16 characters would've taken unreasonably long, it was just the first number that came to my head. Actually if I chose to try to implement something like this, it would probably more like seven or eight characters. L0phtCrack uses a brute force method on that many characters and can actually usually finish within a couple days, although I'm not sure how they do it.

7.) For those who said that I knew nothing or that my business makes no money, I feel sorry for you. I don't know why people feel they need to attack others to make themselves look more important. I actually know quite a bit about security, and my business does quite well. It's paid for my partner and I to go to school, our appartment bills, my car payments, taking my girl out, and many long nites at the bars. ;P

8.) To those who backed me up against these attacks, thank you. I'd hate to think this was the kind of community where you get flamed for asking a question.

9.) For those of you who suggested I look for other exploits, I look for them all, that's why I'm paid. It's important to check password strength, I'm sure you're aware of that. One of the uses I had planned for this script was to help me in situations where my client does not give me an admin account. Normally I test password strength by pulling back the hash file (you need admin rights for this) and then cracking it with L0phtCrack, well, in some circumstances clients do not feel like giving me one of these accounts. It would be easier for me to find the pass for the admin account so that I could pull back the hash to test the password strength of the users rather than try to dictionary attack over NetBIOS on each machine.

10.) In any case, I think that there must be a way to do this in a reasonable time for a password of say 8 characters in length max. L0phtCrack is able to do so, and usually gets the passes within a few hours. Perhaps L0phtCracks brute force attack uses something that I'm not aware of to narrow the possibilities.

In any case, thank you for all of your comments.

Some of what you said reminded me of a so-called security audit we once had performed at a company I used to work for...

For those of you who suggested I look for other exploits, I look for them all, that's why I'm paid.

This statement worries me a little bit. How exactly do you go about looking for ALL exploits? I am not saying that you don't do a thorough job... I may know that no matter how hard you look, and no matter how hard you try, you can't possibly catch everything.

Trouble is, any non-technical person you talk to probably believes that you are truly going to find any possible hole.

Normally I test password strength by pulling back the hash file (you need admin rights for this) and then cracking it with L0phtCrack, well, in some circumstances clients do not feel like giving me one of these accounts.

During that time, one of the auditors wanted either administrative rights to our domain, or a copy of the password hash to test against. I would hope you would see why we would be very against this happening. We would have been significantly more comfortable if we had been asked to run it ourselves, and report back on the results.

To give away every username and password on our domain to an outside company like that is most definitely not a very secure thing to do. As a matter of fact, I would hope to lose points on a security evaluation for giving in to such a request :). We'd have to trust the individual with each of those passwords, and we then are trusting everyone in their organization with those passwords. Your findings would be useless shortly afterwards, because the only thing we could do after giving that to you would be to force password changes across the entire company. (not fun!)

In any case, I think that there must be a way to do this in a reasonable time for a password of say 8 characters in length max. L0phtCrack is able to do so, and usually gets the passes within a few hours.

8 character passwords would go A LOT quicker than 16 character passwords. If we assume uppercase, lowercase, and digits, each character you tack on to the password will take 62 times longer to crack. So going from 8 characters to 9 will bring you up from hours to days. Going from 9 to 10 characters brings in into months, and the 11th character brings us up to many years.

I don't think anyone here said brute forcing an 8 character password was impossible, what they are saying is brute forcing a 16 character password is FAR from twice as hard. I guess the moral of the story here is to make sure your passwords are 10 or 11 characters long, eh? :p

One of the uses I had planned for this script was to help me in situations where my client does not give me an admin account.

This presents a much larger problem, doesn't it? If you can hit against a password hash on a local box, you can try combinations MUCH faster than trying to make login attempts. I'm assuming this is what you are doing, since we are comparing to l0pht. I would hope you would already know that this would probably be fruitless, even with an 8 character password.

Now some of you are probably asking why I would bother asking if I already knew this, well, I don't know everything, I thought someone might know something I didn't.

If you were aware of this, I am sure you would have gotten much friendlier responses if you had mentioned this in the original post.

Anyway, I most definitely do not consider myself to be a security expert... But I do have to say that almost everyone I have ever had the pleasure of working with who CLAIMED to be an expert in these matters was frighteningly ignorant of way to many things.

This statement worries me a little bit. How exactly do you go about looking for ALL exploits? I am not saying that you don't do a thorough job... I may know that no matter how hard you look, and no matter how hard you try, you can't possibly catch everything.

Well, when I conduct an audit, we do both external as well as internal testing. We usually start with some enumeration of the system, port scans and the like. Using the results we know what services are running on the computers at that time. Based upon further inspection, i.e. determining what version and what product is exactly running, we can learn quite a bit about what vulnerabilites might be present on a given port.

At that point we conduct further probing, we may attempt to exploit a hole, to see if the hole exists. On top of this manual testing, we also run two vulnerability analysis tools, Nessus and Retina. Nessus is freeware, you're welcome to check it out, Retina has a bit of a hefty price tag. This programs use the port scan results that we feed them and test against thousands of known vulnerabilities to determine if the service(s) are vulnerable to a certain exploit.

These tools generate large reports, which we then test manually again and distill into a finalized report. Perhaps when we conduct an audit there is some we miss, you can look at it as a snapshot of the network at that time, so if you come in after the audit and load up some new service, its not going to be on the report, so I guess in that sense we can't be sure we catch everything, but as far as our tools go, experience has proven them to be extremely reliable. Reliable enough that at that current point in time where the audit is taking place I'd be at least 95% sure that we caught everything. Of course there could be a new vulnerability out on a service that a plugin for the tools has not been developed, but I can't really control that, and we usually check the most recent ones manually anyways.

Trouble is, any non-technical person you talk to probably believes that you are truly going to find any possible hole.

This is true of any situation where you as a business are marketing yourself to someone whom you are technically superior too. There is a measure of trust that is associated with all business, and I back my business 100%. We have had only good responses to the business we conducted. Not to brag, but we recently finished an audit for a division of the university that I attend and we received much praise for our work, this from a company who had been audit a year prior by one of the "big" security companies.

During that time, one of the auditors wanted either administrative rights to our domain, or a copy of the password hash to test against. I would hope you would see why we would be very against this happening. We would have been significantly more comfortable if we had been asked to run it ourselves, and report back on the results.

Then I'd love to do an audit for you! You'd be doing part of my work. This goes back to your point about being technically savvy. I don't think that all that many places would have the staff to do such a thing. I'm not going to spend time to teach them, it wouldn't make sense, that's why there paying me to be there. Besides, how many places have the spare workers?

To give away every username and password on our domain to an outside company like that is most definitely not a very secure thing to do. As a matter of fact, I would hope to lose points on a security evaluation for giving in to such a request :).

In the contract that both myself and the clientel sign off on, I state that all passwords must be changed after the audit. This is for two reasons, number one being exactly what you said. You don't want me to have your passwords, and heck I don't want them either! If some massive vulnerability comes out the week after we do an audit and you didn't take the time to patch it, I don't want someone to think that I hacked them with the passwords that I got from the audit! Its as much for our protection as there's. Secondly, and most importantly, almost all business that we conduct audits for do not have any password policy in place. If this is the case, we put one into place with the assisstance of the Network Administrator and then force everyone to change their password to fit the new criterion.

Hope this clears some things up. I never thought I'd be defending my business at posting this, but such is the nature of my business. In any situation, I will likely be looked upon as a hacker first, and an aspiring security professional last.

Your network security business isn't going to make a lot of money, which is exactly as it should be as it is blatently obvious from this post, you know nothing about the subject.

BTW. I collect $50 bill serial numbers. If you have any, could you send them to me so I can photograph them for my collection please? I'll send em straight back. Honest.

On some of the later replies you talk about checking password strength even though you do not have an admin account. You may want to look in to merlyn's experiences about checking into password quality without advance, expressed written consent from your client's legal department.

Yes, thanks, others have mentioned this to me. I'm yet to read the story entirely, but I have contracts that the clientel must sign off on. I also have my own personal lawyers that have reviewed the contract.

hmmm. replying to one's own post... something i have sadly done before, but, but...

it seems 14 characters can now be dealt with (lanman & mswin) in *14* secs

cannot resist pointing out to those interested the timely & academic link from the politech list, mailed this morn:

http://lasecwww.epfl.ch/pub/lasec/doc/Oech03.pdf. imho a great example of how hash statistics/methodology can be leveraged. ). if nothing else the article should emphasize the importance of good hash design...

wufnik

in the world of the mules there are no rules

Yeah, but if you read the article you notice that the set of characters is limited (no difference between upper and lower case), and the 14 chars are split into two sets of 7 chars before encrypting - both halves can be attacked separatedly.

This means that the key space of the domain tried is about 0.03% than that of Unix passwords, if we restrict ourselves to alphanumerical passwords, like the article does. The precalculated data used in the article fits on 2 CDs. Assuming it scales lineary, for an attack on alphanumerical Unix passwords, you'd need about 12 million CDs (the keyspace is 3000 times as large, and there are 4096 seeds).

The orginal poster asked about 16 character passwords, including "special" characters. If we assume the special characters are all printable ASCII characters that aren't letters or digits, we have a key space of 95**16. Compare this to the keysize of 36**7 of the article, the former is a tad more. If we scale the 2 CDs of the article to the problem of the OP, we'd need more than 10**21 CDs. And that's assuming you need the same amount of bytes to store a password, or crypted password, which seems unlikely.

If the OP has a billion computers, each of them capable of checking 2**32 (4G) keys per second, it would take the OP almost 325 thousand years to exhaust the key space.

Abigail