The numbers are ... misleading ... and choosing NTLM hashes seems like bordering on misinformation.
Taking SHA-1 (which YOU MUST NOT USE for password hashing blah), it manages 63 billion a second. To try all the passwords for that in the alphanumeric space:
I don't think this is misinformation. You would be surprised at the number of IT people who have no clue how fast NTLM hashes can be brute-forced. Spreading this knowledge is good.
Ranting about NTLM, I am also shocked at how many people are unaware of the pass-the-hash vulnerability enabled by the mere possession of hashes, without having to brute-force them: http://www.youtube.com/watch?v=DkbBCR_vfRQ (disclaimer: I made this video and was a developer for Metasploit/Nexpose).
> I don't think this is misinformation. You would be surprised at the number of IT people who have no clue how fast NTLM hashes can be brute-forced. Spreading this knowledge is good.
That's just depressing, considering how long this has been a problem.
Advice has been, for many years, to avoid using passwords 14 chars or less to force use of NTLMv2.
> You would be surprised at the number of IT people who have no clue [...]
No, you're right. It's widespread lack of knowledge, and letting people know that some stuff is not secure, and other stuff is more secure if you have a complex passphrase, is important.
LinkedIn used unsalted SHA-1, had their passwords leaked, and within a month 90-95% of leaked passwords were cracked[1].
Admittedly LinkedIn isn't a critical application calling for people's most secure passwords - but it's evident that only 5-10% of users use passwords that take more than 1 month to crack when hashed with SHA-1.
Admittedly LinkedIn isn't a critical application calling for people's most secure passwords
People re-use passwords. Often it's not access to the LinkedIn account that's the problem, but that that same password will give you access to their email account, after that, you have everything.
Yes, you're right about that. I only included that proviso because I've seen people on HN report that, while they use a complicated, hard-to-remember password for important sites (gmail, paypal) they use weaker/easier to remember/reused passwords on less important sites (HN, reddit, facebook, linkedin).
Depending on how widespread this behaviour is, while 90-95% of linkedin passwords were easily cracked, that might not generalise to all sites.
I'm kind of rusty on algorithmic information theory (I'm an artist, heh)! Is there such a thing as (formalized) upper limit of what we could do as far as computing combinations go? I know of Kolmogorov complexity (vaguely), but what are the hard limits and challenges of just prodding through (faster and faster as tech goes forward) combinations until success? I plan on developing a story around that and make a movie out of it - so any help would be appreciated (you guys can contact me via email if you want).
"what are the hard limits and challenges of just prodding through (faster and faster as tech goes forward) combinations until success?"
According to current theory of physics, every computation needs at least a certain amount of energy. So if you want to do many computations today, you will have to use a certain amount of energy today. Now lets say, you have a machine that turns any matter into energy without any loss. You put in m mass and you get out e=mc^2 energy. Problem is: You cannot get more matter into that machine today then is around you in a radius of 24 light hours.
So that would be a hard limit.
But quantum computers have proven to break that limit. One theory is that using a quantum computer means using computers in an unlimited number of parallel universes. So there is no limit to the number of calculations you can do. (See David Deutsch and his theories about parallel universes)
I think there are theories about the limits of what a quantum computer can calculate. But I dont know them. Would be interesting to read about it if there is something published.
Then again, what might look like a "hard limit" today will probably not do so tomorrow. Some time ago the "lower limit on energy per calculation" sounded like a hard limit. Then quantum computers came along and blasted through it.
> According to current theory of physics, every computation needs at least a certain amount of energy.
This is not, strictly speaking, true. You are talking, I believe, about Lanadauer's principle [1]. This states that it is the destruction of entropy that costs energy. There are computational methods that can theoretically avoid these energy losses [2]. In fact, Lanadaer theorized about reversible computing in his original paper [3].
Bremmerman's limit, mentioned below, is more applicable.
I read a reference someone posted somewhere once (sorry to not be more specific) that sounded pretty convincing.
Apparently it takes a minimum amount of energy to flip one bit in a conventional (non quantum) computer.
In order to brute force a 128 bit key, you'd need some sort of 128 bit register. Multiply the amount of energy needed per bit flip and the result implies there are never likley to be enough power plants on Earth to iterate through all the combinations (let alone perform the computations required to test the candidate key).
Hope this helps, perhaps this is enough for you to find the original reference.
I'm mapping through all the concepts I need and try to grasp, at least, basic knowledge about it. It helps I'm math literate (to an extent), but I still have a long way to go before I have a believable premise (+ a magic/unknown factor to make an interesting story) before I contact an expert in information theory to make it even more believable. I suspect this will be the king of "nerd" movies, but I don't care - it's something I would watch, that is all that matters for that project.
The problem with all of this is that security specialists (of which I am one, guilty as charged) have historically campaigned for more complex passwords. This worked well for conventional (non-clustered, non-accelerated) password cracking mechanisms.
Sadly, this starts to fall apart with accelerated and/or distributed cracking. On average I crack a few hundred passwords a week, and more often than not organisations have what I call seed words (e.g. the password reset word or common words used throughout the organisation) and the majority of passwords are variants of them.
My own ability to crack passwords for most algorithms (within a reasonable timeframe) tends to cap at dictionary words with number and letter substitution and somewhere around the 8-10 character mark. Using a phrase means that as an attacker you have to account for other people using more complex but shorter passwords. I'd still suggest getting capitalisation, punctuation or at least a number in your phrase but the bulk of the keyspace comes from the length rather than complexity plus the fact that the people carrying out these attacks are normally cracking more than one password at a time.
For a few years now (since around the time of Oeschlin's paper[1]) I've been advising customers to use longer passwords made of phrases and things they can remember for passwords they regularly use[2] and randomly generated passwords of some length stored in a password safe[3] for things they might forget. The goal of this advice is to make it harder for people to crack passwords and to reduce the volume of passwords people have to remember.
It's worth pointing out that length is not important, only entropy is important. If you create a really long phrase by forming a sentence from very common English words, the entropy is actually really low, and if everyone started doing this you can bet your boots the password crackers would catch up.
However you create your password you should take a stab at calculating the entropy (and incidentally a 10 character truly random password with alphanumeric+specials will be very hard to crack - it's the fact that the passwords are mutations of a seed word that makes them weak, and not their short length)
> It's worth pointing out that length is not important, only entropy is important.
Theoretically yes, as long as you assume the equivalent of a spherical cow in a vacuum.
We've (the security community) become very good at enforcing password schemes that are hard for users to remember and easier for computers to crack. While you could correctly assert that a 30 character long lower case letter only phrase has less entropy than a 15 character sequence of randomly generated numbers, letters of mixed case and punctuation, it makes no odds to me - I'm getting neither of them in a reasonable timeframe.
The reason for this is that if you look at the way web site passwords and company passwords are compromised it's not a single account that's hacked. It's going to be the domain or the database of password hashes. Because you're running all of these through a cracker at once you can't (as an attacker) generally afford to waste the time going through combinations of dictionary words with permutations, especially if you know that if you crack a big enough percentage of passwords you've got the access you need and can move on.
Cracking one 10 character random password with alphanumeric and special characters is a problem of scale with the password generaton algorithm. Depending on the algorithm used you can wait for appropriate rainbow tables to appear to increase your chances, for a cryptographic flaw in the algorithm or for moore's law to catch up. Trying to exhaust the same keyspace for a 30 character password (bearing in mind that the attacker is unlikely to know whether or not your password is high or low entropy, especially if other cracked passwords imply a high entropy policy is in place) is going to be much harder, and will only likely take place if no results of value have been found earlier on.
I absolutely agree, and I didn't mean to imply otherwise with my post.
> it makes no odds to me - I'm getting neither of them in a reasonable timeframe
There's nothing wrong with a passphrase as long as it can't be gotten in a reasonable timeframe, obviously! My point about generation stands, though - no password scheme stands in a vacuum, and if whatever you do catches on, you can guarantee software will be made to exploit the low entropy passwords on that scheme (for example, attacks can now include tricks like taking the website name - LinkedIn - and performing common mutations to generate passwords to attempt: L1nk3dIn1)
If it became really common, people would make rainbow tables for it too. All you'd need to do is create a reduction function that maps back into the set <passwords formed from concatenating common words> :)
This applies to all forms of password generation though: ultimately, entropy is important, and if you care about your security you should know whether the entropy levels of your passwords afford you the security you want or need.
> It's worth pointing out that length is not important, only entropy is important.
Entropy is important, but multi-word passwords stills being efficient since their alphabet is quite large when compared with common alpha-symbolic-numeric passwords.
For example, a completely random password with 12 digits and upper/lower case letters have (26+26+10)^12 = 3.226e21 possibilities. Quite good unless you need to memorize this thing. I use such nonsense things for password stored in my password safe.
A password with four very common words (among the 1000 most common words in the user's native language, which I assume the attacker know) have 1e9 possibilities -- very bad. Relevant XKCD for explaining how bizarre is an English text with such restricted vocabulary: https://xkcd.com/1133/
A password with five words selected among the most 4000 words of the user's native language have 1.024e+18 possibilities. Put some uncommon/random/made-up word in the mix is enough to make a direct attack on the password non-viable and force the attacker to search for more elaborated methods. Plus side: is easy to memorize.
I should point out that multi-word passwords have at least one disadvantage: if you can figure out which letters were used and/or the password's length, and you know the password is multi-word, then it becomes easier to derive what the password was.
So, for example, if you used a multi-word password on your ATM machine, and someone aimed an infrared camera at the machine after you left and retrieved the set of buttons that you pressed, the game would be over if your password were short--or at least much closer to being over if it were long.
Alternatively, an attacker could eavesdrop on your keyboard sounds and capture the timing of the clicks, thereby inferring candidate sets of letters. Or they could examine how much oil is on each key of your keyboard, or how much each key is worn, and adjust for the stats on the English language, etc.
Or, as in the ATM case, an agent could interrupt you right after you've entered your password on a false pretext ("Excuse me, I need help.") and surreptitiously take an in infrared photo of your keyboard. This is plausible in many semi-public scenarios (bank teller, etc.)
I think the saving grace here is that a sufficiently long password uses most letters in the English alphabet--but it is still prone to attack if you can at least get the relative ordering of some of the letters, or you know the password's length (by listening to the number of keyboard clicks, for example).
Yes - I didn't mean to imply passphrases are not good, I just meant that sufficient entropy is required no matter what you do.
By the way, it's a bit easier to discuss bits of entropy rather than number of possibilities. Assuming each possibility is equal (which is NOT true if you pick the password yourself, rather than randomly) then the entropy would be the logarithm of the no. of possibilities. Generally people use base 2, so:
Random 12 digits alphanumeric: 71 bits of entropy
Four common words: 30 bits of entropy
Five words: 60 bits of entropy
The multi-GPU cracker on the frontpage today would take 500,000 years to crack the 5 word password if it was stored via bcrypt (according to the article, which sadly did not specify the work factor). The four common words one, however, would fall in just four hours!
P.S. It isn't actually hard to remember a complex password. Almost anybody can do it! The passphrase method is actually not dissimilar to the technique I use. Say the password started "OK53B3" (I just generated this in LastPass). OK, let's figure out a way to remember it. OK, I thought of a way to remember the first two letters ;) 53.. 54 cards in a deck with the jokers, so we've lost a joker. "OK, guys, we've lost a joker" "B3" sounds like someone with a few missing teeth saying "be free!" so I'm imagining a toddler throwing the joker out of the window going "be thfree!"
Very rapidly this will shortern as your memory of it strengthens with repetition (if you're entering this password every day - I recommend using a password manager so you have just one secure password you enter every day). After a few days it will be "OK missing joker be three" etc then just the password itself. After a bit longer it just becomes muscle memory - I couldn't actually recite it easily anymore, but I type it in seconds.
The important thing though from an entropy perspective is that whether you are making a story for your passphrase or for your password, the story comes second. Generate the password / passphrase and then create a story, this assures that each possibility is equal as I mentioned earlier (if they are unequal, there is less entropy).
Of course, I recognise that even with a good memorisation technique, passphrases still beat out f%8D( from a learning curve, ease of use, and accessibility standpoint. The reason I've stuck with the ugly and relatively short passwords is purely so I can type them in as fast as possible!
Aren't phrases easier to type on mobile devices than letter / number combinations? I always find it annoying to have to switch to different keyboard modes (text / numbers), or having to hold the letter / number key for a few seconds.
Sure, the simple characters make it a bit easier, but the phrases tend to be much longer.
The error rate on a touchscreen keyboard is high enough to really become a problem at 20+ characters when you only see the last typed character (no password review).
Using dictionary words makes it easy for more modern predictive keyboards to keep up, though. Taking the XKCD canonical example, "correct horse battery staple", it's a reasonably secure and lengthy password and includes special characters.
It could also be keyed in via something like Swype or SlideIT in almost as fast as it could be keyed in on a computer keyboard.
Yeah, the iPhone keyboard is what finally got me to stop using r2d2 or c3p0 as a part of my password. And the fact that they are probably in the cracking dictionaries.
Is `rand` a secure random number in ruby? In many programming languages/implementations the default PRNG is only seeded with the current time, which leads to quite low entropy.
“I was extremely disappointed that setting up a clustered VMware instance wouldn’t allow me to create a VM that spanned all the hosts in the cluster. E.g. if i had five VMware ESX hosts with 8 processor cores, I wanted to be able to create a single vm with 40 cores and use all nodes in the cluster,” he wrote.
Not sure why he would have thought this would be possible. This would be an extremely hard problem given the latency involved between different nodes.
Then he came across VCL, or Virtual Open Cluster... “It did just what I wanted, not with an entire OS per se, but with an entire OpenCL application. and that’s good enough for me.”
A similar (but far older) system is MPI[1], which enables parallel computation across many compute nodes for your code by providing message passing. It's kind of a pain to use in my limited experience since you have to adapt your code (it seems like VCL is transparent for OpenCL programs), but it does work. No need for OpenCL, tho of course you could always use OpenCL + MPI. A common thing I see is MPI+OpenMP (for parallel cpu computation).
For an embarrassingly parallel task like this why does there need to be any blazingly fast communication between the nodes at all?
My guess is that they've taken HashCat and not made any changes to it at all and just ran it on this virtual cluster so that it assumes that it's talking directly to each GPU/node.
For brute forcing things there's no need for fast communication between the nodes, you just split the work up into units of n seconds each and then have them poll for work from a central host. Sure it's a bit more work/complex as you're effectively running individual copies of HashCat on each node but that's just a bit of scripting and saves you the cost of Infiniband!
The Virtual Open Cluster and Infiniband solution would be much better for tasks that require lots of intercommunication between the nodes (e.g. block Lanczos of large sparse matrices) but brute forcing passwords/hashes isn't a great example.
I guess the parallelism is why botnets are so good at it. I wonder if anyone's tried getting JavaScript web workers (or possibly, somehow WebGL) to poll a central server to do cracking. A site with just a few thousand visitors a day should be able to crack passwords faster than this machine.
I have attempted this, and I believe others on the wider Internet have as well. Essentially it ended up being slower than if the central servers CPU was used to attack the hashes instead. With only JavaScript available to do the hashing, the maximum per client was disappointingly slow, around 2000 hash/second each if I remember correctly.
It might be better now with faster JavaScript engines, but I wouldn't bet on it.
>That said, I'd be curious to know how long it'd take a device like this to decrypt "secure" AES256 text.
Well, according to the article it tops out at about 340 Gigahashes/second. Let's for the sake of simplicity assume it can do about 1 teraflop (10^12 operations per second, or about 2^40 operations per second). The best known attack for the full 14 round AES encryption reduces it's complexity to 2^96 instructions. So you finish this in 2^56 seconds, or about 2 billion years. I recommend you either wait for an advancement in cryptanalysis or just 30 more doublings of parallel processing power.
Recently I was thinking about alternative ways of implementing authorization security and I had, maybe a silly, idea - wouldn't it be more secure to always log user in and when given a wrong password, "simulate" (generate) account data? In my opinion it would be much harder to write an algorithm detecting if account data is real or not, and isn't the point of cracking to get access to user data?
I haven't seen the discussion that I think is really necessary - when are we going to move beyond passwords, which are obviously growing more and more obsolete? What are we going to use instead of passwords in the future?
And of the 3 What you know (i.e. password) is the most secure when used properly. It's impossible to steal without your knowledge, and it's impossible to misplace.
What you have (eg. physical key) can be stolen from you - or even borrowed, used, and returned without you ever knowing. It can also be copied, and it can be lost - sometimes without being aware of it for a long time.
What you are (eg. fingerprint, iris) is the worst, and the least secure. It's trivial to copy - even from a distance, and it's impossible to change. The entropy available is also low.
So in the future we are still going to use passwords.
Exciting to see the technology behind this field progressing so quickly but troubling considering the passwords my users likely use. Though to be completely realistic their password hashes are very likely already known.
My password is 24 chracters long, and fully random. I don't memorise it. I use Aladdin to type it for me. http://igg.me/aladdin-key
Aladdin is trying to improve the current situation of people using simple or identical passwords everywhere by removing the need to memorise passwords. Aladdin works with Windows, Mac, Linux as well as Android and iPad.
As a matter of fact, I sold 16 GPUs to Jeremi, the security research in question, and yes it was just a fraction of my Bitcoin mining farm. Your statement is true :-)
I wonder how much heat this this generates? How does it stay cool? I have two GTX 670s in SLI and they can get to about 60 degrees with a gap between them... This many cards sandwiched so close must get really really hot. I don't see any water cooling...
Cute. Following Bitcoin hash generation process, this looks like a toy. FPGA and ASIC hashing would be news on par with contemporary hash generation on smaller scale. This is just a better room heater. (i.e. hashing/W ratio is bad).
Roughly speaking, CPUs are highly optimized for sequential execution, with long pipelines, high power consumption, and complex implementations of arithmetic/logic instructions (I'm not an expert, but I _believe_ these are much _better_ than on GPUs, except possibly for certain graphics-related GPU primitives), but relatively few threads. GPUs are optimized for parallel execution, and run many more threads than CPUs, each with higher latency, but nonetheless with higher overall throughput.
The problem with PBKDF2 however is that if you pick a weak password it's useless. It would be better if they included an option for a key as well like other password safes do.
If you are genuinely interested in testing your 1Password keychain, the Jumbo builds of JTR include support for the agilekeychain, and some branches (Magnum Jumbo for example) offer OpenCL support for even faster attacks.
I tried it against mine, and was significantly disappointed in how quickly even my laptop could attack it. I promptly increased the complexity of my master password.
It used to be random alphanumeric, eight characters. JTR tore through that. It's now ~15 random characters, not all ASCII.
Possibly worse, 1Password used to have a mistake in their key generation algorithm that means you could verify a password without the time-consuming key stretching, effectively making it thousands of times faster to crack. JTR doesn't use that method though.
No. Amazon only has Nvidia hardware in their EC2 GPU clusters. Nvidia is not equivalent as it is significantly slower than AMD/ATI hardware for password cracking. Eg. a top-of-the line AMD GPU brute-forces MD5 hashes about 5x faster than a top-of-the-line Nvidia GPU, see: http://golubev.com/gpuest.htm
I don't know any computing provider who rent out AMD GPUs... (This would be a startup opportunity.)
True, but in reality you're probably sending that password over something less secure (like an SSL connection) that doesn't require quite as long (but still a very long time) to crack.
Anything is only as secure as the weakest link in the chain.
If (I'm sure you don't) you allow your browser to save that password so that you don't have to enter it every time then you just need one cleverly designed trojan to be run on your machine (probably easier to do than waiting 4.84E34 years to crack a password) to grab the saved passwords cache from your browser and it's no longer secret.
> Weakness 1: Because it's written down somewhere.
This should be part of your risk assessment. For most people and most passwords the risk is not someone riffling through your wallet to find the card with your 30 character password. The risk is from criminal gangs hacking a system and downloading a huge database of usernames / password hashes, and then performing an offline attack on those hashes.
For most people writing a good password down and keeping the password safely is better than using a weak password.
I fell victim to that once, when I hadn't "upgraded" the re-used throwaway password I'd used to register to see what some random website was. When my throwaway password got exposed (in cleartext facepalm!) by PerlMonks, within a day or so someone had used it to send Acai Berry spam through my Twitter account (which 'd completely forgotten was still using a shared/throwaway password even though it had turned from "some random new website I was curious about" into "somewhere where I actually care about my online reputation").
Just don't re-used passwords _anywhere_ - choose a password generation/storage solution that works across all your devices, and use it to generate unique strong passwords for everything. (1PassWord + DropBox works great for me across my MacOSX, iOS, Android, and Windows devices - I occasionally would like it on Linux too, but rarely enough that I'm satisfied to use my phone and re-type passwords in Linux)
Interesting. It is certainly needed to "upgrade" passwords sometimes.
My beef with 1PW is that it's a single point of failure, not to mention inconvenience/risks. For example, what if I need to check gmail in a trusted, but borrowed device.
The main issue I think is that using only one password for security is insufficient (but not necessarily go for a 2-factor auth)
On the "inconvenient/risks" point - yeah, security is pretty much always a trade-off between convenience and risk. I've already chosen two factor auth for gmail (and Amazon and Dropbox, and I'll add any other important service I can to that list when available), so I pretty much need access to one of my two phones or my iPad to run the TOPT token generator - and if I have any of those devices there's clearly no need to me to trust a borrowed device.
(Though in the complete disaster scenario, I have stored in my wallet, as suggested by Bruce Schenier, the app-password my phones use and the list of backup verification codes - unlabelled so a casual thief _probably_ won't know what to do with them... I've also got irregular exports of everything and the 1Password passphrase and phone PIN printed out and stored in an envelope in the office safe. I _think_ I'm sufficiently paranoid about all that...)
I don't see it as "single point of failure", at least not when your using Dropbox syncing - I've got versions of Dropbox running on two phones, an iPad, two laptops, my iMac, and my home theatre box. I've also got a copy of the data available from Dropbox's servers if I even need. (And there is a risk of a corruption to the synced-everywhere datafile propagating to all those places before it's noticed, but 4 of those copies are backed up with Time Machine (in two different physical locations), and Dropbox stores archived versions for me as well).
FYI, I've learned a little trick that 1Password doesn't seem to share widely. Go into your Dropbox, and in the 1Password.agilekeychain folder there is a file named 1Password.html. It's a read-only instance of your 1Password keychain usable in anything with a browser.
Yeah, for sure - like I said, it's somewhere where I care about my reputation now. Back in '08 or '09 when the Perl Monks password got exposed, not so much (at least not for me...)
Yes, there might be other attacks on the password, but rorr is responding directly to part of the article which claims
> Gosney’s system elevates password cracking to the next level, and effectively renders even the strongest passwords* protected with weaker encryption algorithms, like Microsoft’s LM and NTLM, obsolete.
> The National Institute of Standards and Technology (NIST) has issued a statement that says SSL certificates with a key length of 1,024 bits or fewer will be insufficient for security after December 31, 2010
> It is recommended that the algorithms and key sizes in the "Through 2030" row (e.g., 2048-bit RSA) should be used to provide the cryptographic protection
RSA keys are composite numbers. Bruteforcing them involves factoring, not trying 2^n possibilities. A bruteforce of a 1024-bit RSA key possible to be published this decade and likely by 2030.
I think the suggestion of SSL being less secure was based on it possibly having some vulnerability or other (which, historically, has happened), not necessarily having to brute force it.
Such passwords are certainly secure, but it's a pain to have to carry Keepass/other programs around when using other computers. I think I've found a happy medium by memorizing a simple password-generation function in my scripting language of choice. It produces sufficiently strong passwords, and if you're stranded without Keepass you can still generate them using a local interpreter or a site like codepad.org.
If you can sync your password safe aoftware to your phone, that pretty much solves that problem, at least for me.
(I also rely on having one of my phones or my iPad with me anytime I need secure access to any account of mine, 'cause I use two factor auth using TOTP tokens for places that support it like Google, Amazon, and Dropbox)
This doesn't work because there are conflicting rules out there about what a password should look like. Less than X chars, more than X chars, must contain certain chars, must'n contain certain chars...
I use KeePass, with a copy (via dropbox) on my smartphone for when I'm not at my own computer.
My bank actually limits passwords to a maximum of 10 characters. Drives me bonkers because it prohibits my normal use of the Stanford PwdHash. Many other sites have "helpful" rules that get in the way as well. Frustrating.
Taking SHA-1 (which YOU MUST NOT USE for password hashing blah), it manages 63 billion a second. To try all the passwords for that in the alphanumeric space:
- 10 chars: 35 weeks
- 11 chars: 44 years
- 12 chars: 2,800 years
- 16 chars: 11 times the age of the sun
10 chars for bcrypt: 600,000 years...
http://www.wolframalpha.com/input/?i=%2865**16+%2F+63+billio...