Principia Discordia

This might not be news to some, but it's something I picked up while doing research for my security course, and I figure it might be something worth looking at.

General-Purpose Graphics Processing Unit (GPGPU) programs are a new type of program that specialize in using a computer's graphics card to assist the CPU in computing resource-heavy tasks. The power of GPUs lies in their ability to perform parallel processing: whereas a CPU can only handle a few threads of logic (general rule of thumb is number of cores x2), GPUs can handle hundreds of logic threads simultaneously (how many exactly depends on the graphics cards in question). Current applications of the theory lean towards math-heavy work like protein folding or physics simulations, but some more practical applications have recently been developed, namely password crackers.
http://gpgpu.org/ (http://gpgpu.org/)



Summary: By using both CPU and GPU, password cracking utitlies can increase their bruteforce password guess rate astronomically. An example would be the ighashgpu cracker.
http://mytechencounters.wordpress.com/2011/04/03/gpu-password-cracking-crack-a-windows-password-using-a-graphic-card/ (http://mytechencounters.wordpress.com/2011/04/03/gpu-password-cracking-crack-a-windows-password-using-a-graphic-card/)

QuoteI'm going to use the NTLM hash here. If you are wondering what NTLM is, your Windows (NT and above) logon passwords are not stored as plain text but encrypted as LM and NTLM hashes. They are not reversible and hence supposed to be secure. LM hashes can easily be broken using Rainbow Tables but NTLM hashes are relatively stronger. But that's not stopping us from cracking them.

For comparison, I'm going to use another popular and free security tool – Cain & Abel. This is an excellent tool for breaking different passwords, using the CPU.

To crack a password, you need to have the NTLM hash of that password. Fortunately, Cain & Abel has a hash calculator. So let's do some password cracking.



A password with 5 characters

Using Cain, I generate a random password "fjR8n" whose NTLM hash is "AA8251D1BB587ABFAE6403194216041F" without quotes of course.

As you see, Cain has taken about 24 seconds to crack the password at the rate of 9.8 million passwords/sec.


Let's see what ighashgpu has to offer.


The password is found in less than one second. Secondly look at how many passwords the GPU has churned out per second. Dude, it's 3.334 billion passwords.




A password with 6 characters

Let's now take "pYDbL6" as the 6 character password. The NTLM hash for that password is CB898E9CA230D14413756875DD8BF71D.

Now that Cain reports it would take approximately 1 hour and 30 minutes to crack our password. Note that this is the maximum time Cain would take to crack the password. It could even be less than that, depending on the password.

What about ighashgpu?

Ighashgpu finds the password in staggering 4 seconds. Also note that the maximum time it would take to crack a 6 character alphanumeric password is about 17 seconds. See the difference between GPU and CPU computing?

3.33 billion passwords/sec against Windows password hashes is scary. Period. 8-12 character passwords, everyone.

Fuck. :aaa:

http://xkcd.com/936/
(http://imgs.xkcd.com/comics/password_strength.png)

If you have access to the hashed password, doesn't that also mean you already have access to the filesystem?

Quote from: Golden Applesauce on September 22, 2011, 12:52:33 PM
If you have access to the hashed password, doesn't that also mean you already have access to the filesystem?

Yeah, that's true.

Quote from: Golden Applesauce on September 22, 2011, 12:52:33 PM
If you have access to the hashed password, doesn't that also mean you already have access to the filesystem?

The author addressed a similar question in the comments section of the article.  He didn't go into any details, but said if the machine has a working dvd drive or usb port, then it's possible to get the hashed passwords.  I'm not sure, maybe he meant if the bios isn't locked down and/or is set up to boot from dvd/usb.

Quote from: Precious Moments Zalgo on September 22, 2011, 03:37:44 PM

Quote from: Golden Applesauce on September 22, 2011, 12:52:33 PM
If you have access to the hashed password, doesn't that also mean you already have access to the filesystem?

The author addressed a similar question in the comments section of the article.  He didn't go into any details, but said if the machine has a working dvd drive or usb port, then it's possible to get the hashed passwords.  I'm not sure, maybe he meant if the bios isn't locked down and/or is set up to boot from dvd/usb.

Yeah he would have meant boot from CD usb. I needed access to my interns pc after he finished so I just put in the ubuntu disc and made myself a root account.

Quote from: Lenin McCarthy on September 22, 2011, 09:39:49 AM
http://xkcd.com/936/
(http://imgs.xkcd.com/comics/password_strength.png)

is that true?? a long password trumps a short complex one?

Quote from: Cramulus on September 22, 2011, 04:50:48 PM


is that true?? a long password trumps a short complex one?

If I'm not mistaken, that's due to the power of the exponential power.

And that they're using brute force.

the forum thread for that particular comic is pretty lengthy...
i guess the argument against it is that an attack that limits to concatenated dictionary attacks will rejoice at the choice...

Quote from: Iptuous on September 22, 2011, 05:54:57 PM
the forum thread for that particular comic is pretty lengthy...
i guess the argument against it is that an attack that limits to concatenated dictionary attacks will rejoice at the choice...

yeah, but even with that, ones that long, getting not just the words in the correct order, but all of the letters to spell the words.

that's some serious clock time.

Quote from: Faust on September 22, 2011, 04:22:12 PM

Quote from: Precious Moments Zalgo on September 22, 2011, 03:37:44 PM

Quote from: Golden Applesauce on September 22, 2011, 12:52:33 PM
If you have access to the hashed password, doesn't that also mean you already have access to the filesystem?

The author addressed a similar question in the comments section of the article.  He didn't go into any details, but said if the machine has a working dvd drive or usb port, then it's possible to get the hashed passwords.  I'm not sure, maybe he meant if the bios isn't locked down and/or is set up to boot from dvd/usb.

Yeah he would have meant boot from CD usb. I needed access to my interns pc after he finished so I just put in the ubuntu disc and made myself a root account.

There's various things about hash cracking:

theoretically, in security it is assumed that as soon as an attacker gains physical access to your machine, it's no longer your machine. there's just too many ways they can mess with it or plant back doors.

this GPGPU thing is just yet another way to make it even easier :)

it is possible that someone's document files are encrypted, unless you're logged in (this is actually a simple checkbox "HD encryption, yes/no?" during Ubuntu installation, you're lucky your intern did not enable it,  Faust :) ).

so in that case, as soon as you get physical access to the machine, you can boot from USB or CD, and the only thing you can get at is either a harddisk full of encrypted noise or the hashed passwords of the login accounts (these need to be available, otherwise the login program cannot check the one-way-hash of what you typed in with the one-way-hash of the correct password to determine whether to let you in or not).

so in that case, you grab the hashes, crack them and pwn the box w00t mad h4xx0r sk1llz etc etc




another much more widespread scenario--well I'm not sure if it actually happens more than the above scenario (since hacking attacks with physical access (https://encrypted.google.com/search?q=evil+maid+attack) are by their nature often kind of secretive), but the following scenario just affects much more people, in general (and even you!) :

When hackers gain access to some big website or server, one that has many, often 100,000s, user accounts. Big forums, social websites, that sort of stuff. Now if they coded their shit properly, they will never save their passwords in plaintext in the database, specifically because of the possibility of this particular event happening, instead, they will save a salted one-way-hash of the passwords.

Now the hackers got this huge database dump of one-way-hash salted passwords, and the thing about one-way-hashes is that it is supposedly very hard to go the other way (i.e. get the password from the salted hash).

This happens really really quite often, with rather big websites and forums (Gawker, to name one). This is why it is so important to never ever re-use a password on different websites, that's the only was you the user can protect yourself, instead of relying on the big corporate websites implementing their security properly (which they won't).

And the GPGPU thing makes this many, many times faster and easier for the attacker.

That's why this is kinda a big deal.

But not really. Because the sad thing is, implementing a correct password hashing scheme is really really hard and 99% of most people are doin it wrong. In fact, the very SMF software running this forum is doing it wrong.

For example you could already do this without GPGPU program because you can just rent a couple of boxes worth of computing from Amazon S3 until they're doing it fast enough.

Or you wait a few years, and computers get 10x as fast :)

---

Here's my advice for if any of you [coders] ever happens to think to need to implement a correct password safekeeping hashing scheme. THIS is THE ONLY RIGHT WAY TO DO IT:

USE BCRYPT (http://codahale.com/how-to-safely-store-a-password/)

Why BCrypt? Because it's SLOW AS HELL, as opposed to MD5 or SHA256, which are designed for speed. BCrypt is in fact designed for SLOW. Afaik it has a variable setting so you can tell it how slow you want it to be. Just in case the computers get unexpectedly faster in the near future, you can just crank up your BCrypt slowness all the fucking way up to 11 :D

yes this can make you safe from GPGPU attacks as well.

---

Oh and to answer Cram

Quote from: Cramulus on September 22, 2011, 04:50:48 PM
is that true?? a long password trumps a short complex one?

Yes. This is absolutely true.

Think about it like this.

With digits, how many numbers can you make with four digits chosen from 0-9?
The answer is: 10⁴ = 10,000. This is the short complex password.

How many numbers can you make with twelve digits chosen from just 0-3?
The answer is 4¹² = 16,777,216. This is the long (three times longer) password chosen from a much simpler alphabet.

Does that clear it up?

There's been a lot of discussion about that particular XKCD cartoon. It's not always as simple as that. Some sites do not allow long passwords (which is stupid and retarded, yes, but as we are very aware, that only seems to make it more likely for people to do it that way). In fact, there even are websites that silently truncate your password and only look at the first 8 characters of it. You need to check that, by deliberately misspelling the last letter of your long password and see if it errors on you.
In all fairness, I made a programming error once on a website for myself that did exactly this. It took me weeks before I wondered why I never seemed to mistype my rather long passphrase.

Also if you want to use different passwords for different sites, using many words long passwords, is also not going to make them very memorable.

(Solution: Just write them down on a piece of paper in your wallet) (if you can keep your creditcard secure, you can also keep the piece of paper secure)

Finally, there's one solution that's strictly better than using long passwords, and that is to use a proper password manager such as KeePass.

Basically this allows you to do both things, because it will generate completely random (very complex) long passwords for you. That's about as secure as you can get.

Then it stores them encrypted under a single passphrase (which you will need to remember, but it's just one).

You can carry around KeePass on a USB stick or put the password file on your DropBox account, so you can use it anywhere.

No, I don't do this either. But it's the best solution.

My personal strategy is to practice and try to be good at memorizing complex passwords :)

Quote from: Iptuous on September 22, 2011, 05:54:57 PM
the forum thread for that particular comic is pretty lengthy...
i guess the argument against it is that an attack that limits to concatenated dictionary attacks will rejoice at the choice...

No. If you read the comic, you'll see that he takes that into account:

he only counts 11 bits of entropy for each word in the long password:

11 bits has 2¹¹ = 2048 combinations.

So he is assuming that the dictionary from which he picks the random words only has 2048 words in it

that's a pretty fucking tiny dictionary.

most password dictionaries are in the 100,000s.

except he uses four words, so the amount of combinations is 2048 * 2048 * 2048 * 2048 = 2⁴⁴ = 17,592,186,044,416

that's how long you'll be guessing IF you take the optimal approach of only guessing "four concatenated dictionary words" GIVEN that you know exactly from which 2048 words they were taken.

if you don't know that, you'll be guessing even much much longer :)


it's a pretty good approach. the downsides are only of a practical manner, the theory is absolutely sound.

i see.
and the practical downside being how you mentioned that you would have to should have different, very long passwords for each website, thus negating the 'easy to remember' part?

If you use something like Diceware (http://world.std.com/~reinhold/diceware.html) to generate your words, then you are choosing from a dictionary of 7776 words.  Each word will add 12.9 bits of entropy.  A totally random password of any printable ASCII character has 6.5 bits of entropy per letter.  A four word Diceware password and a password of eight random printable ASCII characters will be approximately equally difficult to crack (51.6 vs 52 bits of entropy).

Trip, watching you hold court on the intricacies of computer cryptology is pretty damn sexy, I gotta tell you.

Quote from: Iptuous on September 22, 2011, 06:16:28 PM
i see.
and the practical downside being how you mentioned that you would have to should have different, very long passwords for each website, thus negating the 'easy to remember' part?

Pretty much. There were some other practical concerns mentioned, but I forgot what they were. So they must not have been very important :)

Problem is, discussion threads about this comic/scheme, a lot of smart people are very wrong, of whom I really expected should know their shit about password strength, best practices and why you can't counter an argument about password strength in terms of bits of entropy with "but if you got a real clever dictionary attack ..." (because "bits of entropy" really is an objective measure of password strength)

Quote from: LMNO, PhD (life continues) on September 22, 2011, 06:23:48 PM
Trip, watching you hold court on the intricacies of computer cryptology is pretty damn sexy, I gotta tell you.

8)

You should read Neal Stephenson's Cryptonomicon, slightly less funny than Snow Crash but it more than makes up for it in awesome story. It involves Alan Turing being fabulous and solving the Enigma codes, hidden Nazi Gold treasure (and the logistics of moving it out of a jungle), hackers and high-tech investments, and lots of people knowing their shit about crypto--which is a lot more about common sense and "knowing that they know you know what they know you know"-reasoning than really complex math.

Quote from: Iptuous on September 22, 2011, 06:16:28 PM
i see.
and the practical downside being how you mentioned that you would have to should have different, very long passwords for each website, thus negating the 'easy to remember' part?

Yes, unless you have an easy to remember system, for a while I would add the first letter +1 (a becomes b) of the name of a site to the end of my regular password.

Quote from: Faust on September 22, 2011, 08:04:15 PM

Quote from: Iptuous on September 22, 2011, 06:16:28 PM
i see.
and the practical downside being how you mentioned that you would have to should have different, very long passwords for each website, thus negating the 'easy to remember' part?

Yes, unless you have an easy to remember system, for a while I would add the first letter +1 (a becomes b) of the name of a site to the end of my regular password.

i hardly see how adding the letter 'x' to the end of your passwords differentiates them at all.
.
.
.
:wink:

. . . . ... . . . . .... . :argh!:

So, I should probably change my password, and that might explain my GF's choice of password for our router. A string of gibberish and then this longass sentence. It was not fun typing it in on my kindle.

Wow, suddenly my habit of using the full names of book characters or compounding two random things I can see doesn't seem so silly.

Quote from: Nigel on September 23, 2011, 09:55:34 PM
Wow, suddenly my habit of using the full names of book characters or compounding two random things I can see doesn't seem so silly.

Yup, that's a good strategy.

Although "things you can see" is a known pattern, I catch myself doing that as well when thinking up a new password. So I guess there must be some dictionary out there containing "stuff likely to be in eyesight of an office/desk/computer" :)

Quote from: Triple Zero on September 23, 2011, 10:40:52 PM

Quote from: Nigel on September 23, 2011, 09:55:34 PM
Wow, suddenly my habit of using the full names of book characters or compounding two random things I can see doesn't seem so silly.

Yup, that's a good strategy.

Although "things you can see" is a known pattern, I catch myself doing that as well when thinking up a new password. So I guess there must be some dictionary out there containing "stuff likely to be in eyesight of an office/desk/computer" :)

I usually do things like the name of a street and establishment, or a landmark... two things that are related, so that I'll remember them, but unlikely to be associated in anyone's head. Such as "Fremont Place Irving fountain" or "Madison Finnegan wind sock".

I still have correcthorsebatterystaple stuck in my head.   

Quote from: Jasper on September 23, 2011, 11:11:09 PM
I still have correcthorsebatterystaple stuck in my head.   

Me too.

Zero, what is the optimum password length in terms of both symbols and words? Or is it "as long as you can make it"?

Quote from: ϗ, M.S. on September 24, 2011, 01:34:32 AM

Quote from: Jasper on September 23, 2011, 11:11:09 PM
I still have correcthorsebatterystaple stuck in my head.   

Me too.

Zero, what is the optimum password length in terms of both symbols and words? Or is it "as long as you can make it"?

As long as you can make it, without you yourself forgetting it.

It seems as if even phrases that make perfect sense would be very secure passwords.

Quote from: ϗ, M.S. on September 24, 2011, 01:34:32 AM

Quote from: Jasper on September 23, 2011, 11:11:09 PM
I still have correcthorsebatterystaple stuck in my head.   

Me too.

Zero, what is the optimum password length in terms of both symbols and words? Or is it "as long as you can make it"?

Theoretically:

A) They get better as they get longer, for the amount of possibilities, especially if you add in a symbol here and there.
B) They get "worse" as they get longer because you're more likely to forget them, as well as at some point it will become inconvenient to type a whole paragraph just to log in.

Now if you multiply A*B, you'd get an cost/benefit curve with a maximum somewhere. Unfortunately you can calculate A (benefit), but B (cost) is very personal, so you're going to have to sort of determine it experimentally.

TL/DR: What GA said ;-)

---

Co-incidentally, this morning I came across this very good password strength calculator + article on best practices and stuff:

https://www.grc.com/haystack.htm

The calculator demonstrates very nicely Cram's initial question of whether/how password length really trumps password complexity (which it does).

And the text on the page contains all sorts of good advice. Not all of it I 100% agree with, but they take the cautious approach, be sure to read the "One Important Final Note" about halfway.

One thing I don't agree with is that they're assuming once a cracker decides they're going to do an exhaustive password search, they're going to try the combinations in random, or worse, alphabetical order. Not true. They're still going to use some sort of heuristic to make the more likely passwords be tried first. This is very important and I have read about tools that are capable of this (would love to write one, too).

For instance, in the FAQ they say your password is news.

Bruteforce difficulty of this is 26⁴, four characters out of an alphabet of 26 lowercase letters.

- if you add one lowercase character to it, say newsy, difficulty becomes 26⁵, so it'll take 26 times as long to bruteforce this password versus the original.

- if you add a symbol to it, say news!, you get a bigger alphabet, there's 33 symbols that you can easily type on a standard keyboard¹, so in addition to the lowercase letters your alphabet is 33+26 = 59 characters. Length is five, so you get 59⁵ possibilities. That number is 1564 times as large as 26⁴ (the FAQ on the site says 1530 but I did the calculation and it's 1564. close enough, either way).

It's the second statement I disagree with. news! is not 1500 times as hard to crack as news. Why? Because adding an exclamation mark is the most common thing people do when they decide "hey let's add a symbol". A password cracker will probably try bruteforcing in this order:

- all 26⁴ possible passwords of 4 characters lowercase
- all 26⁴ possible passwords of 4 characters lowercase, with the first character changed to uppercase
- all 26⁴ possible passwords of 4 characters lowercase, with a ! tacked at the end
- all X * 26⁴ possible passwords of 4 characters lowercase, with some numbers at the end: 1, 0, 123, two digit birth years, four digit birth years, birthdates ...
- all 36⁴ possible passwords including 10 common l33tspeak symbols
- ...

as you can see, even though in the end the cracker will have exhaustively searched all possible passwords, he's not trying them in alphabetical or lexicographical order.
most password cracking tools are based on the key concept of "transformations", such as "first character to uppercase" or "append an exclamation mark". the cracker will think up all sorts of creative probable transformations, and the cracking tool makes sure they are all applied first to the word dictionary, then to the exhaustive search, all the while making sure there are no duplicates, and that the transformations that the cracker decides are most probable are searched first.

I tried to think about probable transformations and in my rough guess, adding the exclamation mark would be about the third thing I'd try, in order of likelihood. That makes adding an exclamation mark only THREE times as difficult as no exclamation mark.

But it all depends on what your adversary is doing, or thinks you will do.

¹ They are ~`!@#$%^&*()_+=-[]{}\|'";:/?.,<> and the space character.

---

Quote from: Nigel on September 24, 2011, 05:10:57 AM
It seems as if even phrases that make perfect sense would be very secure passwords.

Yes.

Although, absurdist phrases that are very crazy have two advantages:

- they're much harder to guess, because there's so much more possibilities
- because they paint such a crazy image in your mind, they are also much easier to remember

So it's win/win, really :)

Then change it up a bit with symbols, and you get what Assange used for his wikileaks PGP password. Very secure.

Then finally, what went wrong with Assange? It got printed, because it's printable.

Seriously, when you get to the Wikileaks level of secrecy, there's more you can do to secure your password and Assange should have known this, because I read it in an article many years ago.

Once you made yourself the perfect password that is so fucking clever, you'll feel pretty fucking clever, and you'll get the urge to tell people about it.

Now Assange might like to show how clever he is, but he's not stupid so he didn't do that.

The journalist, however, was a stupid fuck, so because the password he was given was so fucking obviously clever ("A_Diplomatic_History_Since_19xxsomethingorother%", something like that), he decided to print it in his book! Yaaaaay!

The simple solution the article presents to this problem is to make the password not only clever, but also highly embarassing, offensive, and something you definitely would not want to tell other people or put in print:

niggerFUCKSHITDAMN_theH0L0C4USTisaLIE+irapedmybabydaughterfor$$$

This would probably have never made it into print. Hell, I almost feel bad for posting those words here. That's how good it works.

i use lastpass (https://lastpass.com/) to save all my passwords - it has a nifty extension for pretty much every browser under the sun, that can automatically fill password forms etc.

the really cool thing about it is that it comes with a random password generator that creates randomised passwords exactly to what you want -- I used it to generate 30 character randomised passwords w/ both cases, numbers and symbols for all of my critical sites (gmail, amazon, some torrenting sites)

Yes. Password managers such as LastPass or KeePass are currently undoubtedly the most secure way of handling passwords. Better than the tips 'n tricks discussed for strong password generation ITT so far.

truly random 30 characters alphanumeric mixed case + symbols is about as secure as it gets.

(except for 31 characters :P )

those passwords are encrypted with a single passphrase, and depending on what your password manager supports, even two-factor authentication, often in the form of "will only work if you have this USB stick with an even bigger key on it plugged into the computar".

Quote from: Triple Zero on September 24, 2011, 09:35:04 AM

niggerFUCKSHITDAMN_theH0L0C4USTisaLIE+irapedmybabydaughterfor$$$

Am I a bad person for giggling like a madman when I read this?  Probably.



Also, I was talking to a computer security guy over the weekend about this, and he said while the theory is sound, most of the top level hackers don't use pure brute force... they've developed something akin to a crypto AI that makes informed decisions regarding password behaviors.  Or something.  You guys may have already been talking about this; i'm having trouble following the more in-depth parts of this thread.

Yes, that's sort of like the part where I explain how you can bruteforce, but if you choose the order in which you try all combinations such that the more likely combinations are checked for first, you're going to find the right password much sooner.

There's some really smart and creative analytic tricks to optimize the order, but they're probably a well-guarded secret, because I have only rarely heard about it.

One obvious trick of course, is to customize for your target audience. But how exactly to do that, is quite a black art :)