how long of a password could the world's best computer crack?

[hahher]

if you encrypted a file with a password, let's say upper and lower case and numbers, how long of a password could be cracked in a year?

at what point would the gov give up on brute forcing the password to some super secret document [supposing they have access to world's greatest computer(s)]? i.e. if they knew the password was 16 characters they wouldn't bother with brute force method.

 

[f95toli]

Well. we can do a little handwaving:

Lets say we have computer that can perfom 2^12 operations/s (teraflop)

It takes about 10 operations to make one attempt

One year = 365*24*3600=31536000 s

So we can make 31536000*2^12/10 attampts in one year (about 1e10 atttempts)

Upper+lowercase+numbers gives us 35 ways to choose each charachter in the password

So if the oassword is 7 charachters long there are 6e10 combinations. so this should be enough,

Note:
1) Many systems will force you to use at leat one "special charachter" (!%<> etc), this increases the number of choices a lot and forces people to use relatively "complicated" password (as opposed to the name of their pet)

2) Very few people use "random" password such as "ajt934m", and a "real" cracker would use this to reduce the number of attempts, this speeds up the process a lot.

 

[Sunner]

I'm confused...how does upper+lower+number equal 35?
Wouldn't that be 26+26+10 ? Or in my case, 29+29+10

 

[f95toli]

true... I don't know how I came up with the figure 35

It should be 62, in which case 6 charachters would be just enough

 

[Sunner]

Originally posted by: f95toli
true... I don't know how I came up with the figure 35

It should be 62, in which case 6 charachters would be just enough

Goody, that means I don't need to feel like a stupid mofo for missing something obvious

 

[AnthraX101]

Wow, now this is a hard question. There is no practical answer to this. Every encryption algorithm uses its own keying methods. Let's look at a simple hashing method (MD5 and SHA0 (note, this has been replaced by SHA1, just using it as an example)):

Speed Paper

As you can see, on identical equiptment the SHA (35,504 key/s) is much slower then MD5 (50,002 key/s) (64 octet message). This can be considered to analgous to the keying of an encryption algorithm.

If you assume a -true- brute force (not one that simply uses leters/numbers in a hybrid attack), the brute force time is analgous to the length of the keying stream. A 10 character password is just as safe a a 100 character password. Rijendael, for instance, uses keys of up to 128, 192, or 256 bits. As you get higher key lengths, the processing time of finding a collision (Two different passwords that satisfy the same method) increases.

If you are attacking the password itself using a shortest-first method, it's still hard to say. You no longer have to worry about collisions. However there is still a limit of the effective length of your password. At some point it becomes more effective to attack either the user, the computer, or the algorithm. Exactly how long this is depends on the methods and skills of the attacker.

Now that I gave you that completely useless answer, I would suggest using at least an 8 character password with mixed letters, numbers, and special characters for something you don't want breached by casual attackers. 12 is a good limit for determined attackers, and I would use a long phrase for something you want secure at all costs.

AnthraX101

EDIT: A note about the post above. A teraflop is 10^12, not 2^12. That changes your numbers to require about a 12 character password, assuming a 10 operation attempt. For practical concerns, at this point in time a single desktop can bruteforce about 5-6 million keys per second of MD5 (at about 1.5-2ghz)

All that said, brute force is tending to go the way of the dodo. Most encryption works off of some sort of hashing function for keys, and at this point rainbow tables are becoming popular. This allows you to brute force all the keys once, and then store the answer. That way you only look up the answer later, and already know the question.

 

[f95toli]

I guess you can tell I was tired when I wrote the posts above....
It should of course be 10^12 (1e12),
which means that you need 11 charachters. This makes more sense.

I forgot to point out that a decent security system will prevent this kind of attack, there is simply no way to use brute force to for example hack a computer. Even if you are trying to decrypt a file it will be difficult because it takes more than 10 operations to test if a key works or not.

Where I work the rules for the passwors are: exactly 8 charachters long , both upper and lowercase, numbers and one special charachter; the main reason for these rules is that it forces the uses to ues complicated passwords, since you only have 3 logon attempts even a 4 charachter password would be safe if it was truly "random".

 

[Cogman]

Exactly 8 charactors? I would think that At least 8 charactors would be a safer rule, If it is exactly 8 charactors it reduces the number of possibilities a bit because you dont have to test for 9 charactors.

 

[f95toli]

Yes, but I guess it is just another way to force people to choose passwords that are are as "random" as possible and not simply use their "usual" password.

 

[Mark R]

Well, lets estimate the most powerful machine that could be practicably built:

Let's assume optimized custom made brute-force password cracking chips - same size and construction methods as a state-of-the-art graphics processor like NV40.

A fully pipelined decryption circuit would probably need about 100,000 transistors. These could probably be built 1000 to a chip, and clocked at about 350-400 MHz - with a net throughput of up to 400,000,000,000 keys/sec.

As this would be a major government project with very high R&amp;D costs, mass production would help improve value for money. Let's assume 100,000 chips in parallel which could give 40,000,000,000,000,000 keys/sec.

Now assume a maximum working time of 1 week, for a super-secret document for a total of 2.4x10^24 keys searchable. This works out equivalent to approx 72 bit key length or 12 characters assuming upper/lower/numbers.

If you want to allow crunching for a whole year at a time, then this only buys you one more character - for a total of about 13.

Of course, there are other, more efficient, ways to break codes than to brute force keys.

However, breaking modern encyrption techniques is a major difficulty. Indeed, minor government agencies like the FBI don't usually try to break readily available encryption because it's too hard. Instead, they usually get the key by surveillance techniques - usually breaking-in and installing hidden cameras, key loggers, etc.

 

[f95toli]

One interesting note: I was once the user of a system with less strict rules, the only rule was that the password had to be at least 6 charachters long.
Anyway, when you sígned up for an account you were also asked to choose a password (which could be changed later). The sysop would tell the user NOT to use a word, place or name (the usual rules).
Now, the sysop always ran the choosen password through a test-routine (I think it was basically a simple dictonary cracker) to make sure it was "safe". The test took about 10s or so.
The amazing thing is that I was present 3 diffrent times when the test failed, meaning that the uses had choosen a password which was easy to crack. Apparantly this happened frequently, so about 10s after being told NOT to use a simple passwords the users still did...

Users are truly the worst security problem, much worse than any bug in windiws.

 

[Pex]

O.E. = hell.

 

[n0cmonkey]

Dictionary? Brute force? Known weaknesses in the method?

 

[silverpig]

Why don't you just memorize your passwords?

 

[NewBlackDak]

Originally posted by: f95toli
One interesting note: I was once the user of a system with less strict rules, the only rule was that the password had to be at least 6 charachters long.
Anyway, when you sígned up for an account you were also asked to choose a password (which could be changed later). The sysop would tell the user NOT to use a word, place or name (the usual rules).
Now, the sysop always ran the choosen password through a test-routine (I think it was basically a simple dictonary cracker) to make sure it was "safe". The test took about 10s or so.
The amazing thing is that I was present 3 diffrent times when the test failed, meaning that the uses had choosen a password which was easy to crack. Apparantly this happened frequently, so about 10s after being told NOT to use a simple passwords the users still did...

Users are truly the worst security problem, much worse than any bug in windiws.

This is why I assign passwords, and hand them out. I don't let the users change them, and every 6 months I change them.

 

[Wahsapa]

alt 2 5 5

 

[Runamile]

I once read something a while back that the NSA has backdoors into all encription algorithems. I know that sounds far fetched, but with the NSA you never know. Almost everything about their entire operation is very classified, the have some of the best hackers in the world, and they have a whole lotta money.

 

[DrPizza]

To go with what Runamile said, I doubt they'd use brute force to crack it. There are people whose jobs are to create better and better algorithms for cracking, etc.
Your assumption that "brute force" would be used is where you made your biggest mistake.

I'll offer this: If you have stuff that you want encrypted so that you and you alone can get it, then you better learn about encryption techniques and the mathematics involved, and write your own encrypting software. That way, only you know the encryption algorithm.

But, if you don't want to get too technical, and don't mind wasting memory (which is cheap anyways) here's an untested idea for you:
Assign each character a 2 digit number 00 = space, 01=a, 02=A, etc. Or, go with a 3 digit number if you need more than 100 characters. Pick random numbers in increasing order, say 23, 47, 48,63,95,...
Then to encrypt, simply generate a LONNNG list of numbers,
12390875510691234509875098346198723498715987136450918530923740981658739275174012394712305986547896584123...

The 23rd pair would be your first character, the 47th pair would be your 2nd character, the 48th pair would be your 3rd character, etc.
To generate the filler numbers, just generate random numbers. However, in doing so, design your random number generator such that the end result produces what appears to be a completely random set of numbers. In fact, upon consideration, I realized that if e=09, you will get a disproportionate amount of e's. Simply use 2 or 3 pairs to encode the letter e and alternate them.

I suppose this wouldn't be incredibly difficult to crack if someone knew how you were encoding, but it'd be difficult. To further have fun with it... after you generate it, encrypt it using a 2nd method.

 

[Matthias99]

Originally posted by: Runamile
I once read something a while back that the NSA has backdoors into all encription algorithems. I know that sounds far fetched, but with the NSA you never know. Almost everything about their entire operation is very classified, the have some of the best hackers in the world, and they have a whole lotta money.

While it's possible that they have backdoors into major commercial products like Microsoft Windows, there are a number of encryption algorithms that are provably secure (or, at least, secure unless you have a way to find prime factors of extremely large numbers quickly, which is what that black box in "Sneakers" did ). And there are no such visible hooks into open-source operatings sytems like Linux.

I know someone who worked for the NSA, and while they can do a lot of stuff, they can't backdoor their way into mathematically secure encryption algorithms.

 

[biostud]

Originally posted by: f95toli

1) Many systems will force you to use at leat one "special charachter" (!%<> etc), this increases the number of choices a lot and forces people to use relatively "complicated" password (as opposed to the name of their pet)

You don't have a pet called 34r%&amp;xxG?

 

[iwantanewcomputer]

Originally posted by: Wahsapa
alt 2 5 5

see, this guy uses random characters in his passwords

 

[dnuggett]

I know someone who worked for the NSA, and while they can do a lot of stuff, they can't backdoor their way into mathematically secure encryption algorithms.

They sure can. Most algorithms aren't built from scratch and follow certain predictability. They re-create advanced algorithms everyday.

 

[eigen]

Originally posted by: dnuggett

I know someone who worked for the NSA, and while they can do a lot of stuff, they can't backdoor their way into mathematically secure encryption algorithms.

They sure can. Most algorithms aren't built from scratch and follow certain predictability. They re-create advanced algorithms everyday.

Can you elaborate, as your post makes no sense.. What do you mean by follow certain predictability. Do you mean that the algorithmn is known, of course it is, all secrecy lies in the key. Do you mean that ciphers are built around the principles of diffusion and dependncy on the key. so what it falls back to the key. Of course the stucture of the cipher does lend itself to attacks (linear and differential cryptananalysis increasing along with ellipitic and linear/equation solving attacks) bu that is the nature of the game. In saying that the NSA can just go around breaking ciphers implies that the NSA can go around solving NP-complete problems at will. They may be able to but you certainly don't know that.

 

[Shalmanese]

Originally posted by: NewBlackDak

This is why I assign passwords, and hand them out. I don't let the users change them, and every 6 months I change them.

Which means that all that happens is that users stick their current password on the bottom of their keyboards with a post-it note and any hacker could rip through your entire building in 1/2 an hour pretending to be a janitor and your system is compromised.

Furthermore, you get so many calls from people claiming to have forgotten their password that it would be quite trivial to social engineer you into giving an outside agent a users password.

The best and most easiest way I've found to make people choose secure passwords is the acronym method. Think of a short string that is significant to you, "Mary had a little lamb and his fleece was white as snow" is the canonical one so obviously don't choose that one . Anyway, convert it into an acronym and you get mhallahfwwas. That's a perfectly adequate password but it can be obfusicated more. To me, if I tried to say that out loud, it would sound like em-holla-fwaz so emhollafwaz would be a better password. Then, sticking random substitutions and capitals would get eMh0l/afWa2. And the added benifit is that it's MUCH easier to remember than a random string.

 

[dnuggett]

Originally posted by: eigen

Originally posted by: dnuggett

I know someone who worked for the NSA, and while they can do a lot of stuff, they can't backdoor their way into mathematically secure encryption algorithms.

They sure can. Most algorithms aren't built from scratch and follow certain predictability. They re-create advanced algorithms everyday.

Can you elaborate, as your post makes no sense.. What do you mean by follow certain predictability. Do you mean that the algorithmn is known, of course it is, all secrecy lies in the key. Do you mean that ciphers are built around the principles of diffusion and dependncy on the key. so what it falls back to the key. Of course the stucture of the cipher does lend itself to attacks (linear and differential cryptananalysis increasing along with ellipitic and linear/equation solving attacks) bu that is the nature of the game. In saying that the NSA can just go around breaking ciphers implies that the NSA can go around solving NP-complete problems at will. They may be able to but you certainly don't know that.

No, I cannot elaborate.