Passwords and XKCD

I feel as if I'm walking into a trap. Randall Munroe is sort of a folk hero among geeks, and when I saw his recent comic about password strength, I was, at first, thrilled. Here's someone who knows how to communicate to the masses exactly what they need to know: they choose poor passwords, and could just as easily (or easier) choose strong passwords that they could remember.

I understand where he's coming from, and he's right on some level, but let me explain to you what the layman heard:

If your password is a space-separated list of four English words, no one will ever be able to crack it!

Sadly, there's even solid proof that that's the case. Here's the first example I've seen of a "password" generator based on his approach: XKCD Password Generator.

All I can say is /facepalm.

OK, so those of you who might not get what's going on, here, this is what he's saying:

When you try to make a very strong password, your first inclination is often to try to maximize the complexity of the password from a human perspective. This works very well if you're willing to memorize, say, 13 completely random characters from all over your keyboard. However, most people can't reasonably memorize such a password.

So what most people do is try to come up with something that's difficult to "read" but follows an easy-to-remember pattern. As Randall correctly points out, this is a losing game, and often results in passwords which are relatively easy to guess using simple attacks.

However, his approach is to choose your password from a list of about 17,592,186,044,416 possible passwords made up of four English words. That's a pretty strong password compared to a lot of the kinds of passwords people typically use, but if you're comparing it to the gold standard (randomly selected characters from all of the 95 characters you can type on the typical U.S. keyboard), then you would only need about a 7 character password to make up the same number of possible passwords. 7 character passwords became relatively trivial to crack when I was still new in this industry, and now even 10 character passwords are looking shaky, just in terms of what it takes to crack the perfect password.

So, is Randall right? Well, yes, sort of. However, the best approach would be to combine all of the best strategies for passwords that are easy to remember, not allowing your attacker to know what kinds of passwords to try. Throw in one really odd word to your four. Change up a common saying. Make your password something that's fun to type. Take a simple phrase and censor it out by replacing a word to two with asterisks in a way that makes it sound funny. Combine the first name of a character with part of a quote they're famous for. Draw some ASCII art.

All of these are individually fairly weak strategies, but when you're creative about every password, it's nearly impossible to use any one scheme's weaknesses against you. If you are a target, specifically, this is a strong defense. If a large number of users are being targeted, then there's a larger problem you have to solve, and more attention to detail may be required to solve the problem.

Here are some examples of pass-phrases that you might use. Think of your own clever ways to twist up the keys on your keyboard and be unpredictable. There are still many useful ways to attack your passwords, but it's going to be much harder than if you choose a simple four-common-word password.

• "David had a little ham..."
• "d00dz, it's full of stars!"
• "CaPsLoCkWoNtHeLpYoU"
• "10qpalzm -- qwerty"
• "dayO dayayayO, dayl1te come"
• "<-- I'm with them -->"
• "Are doomed to repeat it who fail to learn from history those"
• "[(@)(@)(@)(@)(@)(@)(@)]"
• "I'm mad as **** and I'm not going to **** it any more!"
• "Q-36 Explosive Space Modulator Marvin"
• "Just one uncommon lexeme"
• "!!1 thousand X yes!!"
• "._-*-_.o0O*!"
• "Star Wars of the Roses vs. Kramer"
• "Sufficiently large values of +/-n"
• ">->O XKCD O<-<"

Are your passwords safe in MD5 or SHA-1 formats?

I've read, over and over again, various questions and seemingly authoritative statements about the security of various hashing algorithms. I've gotten kind of tired of reading misinformation, so here's some detail that you can trust.

• US-CERT of the U. S. Department of Homeland Security said MD5 "should be considered cryptographically broken and unsuitable for further use."
• The document that this was stated in is titled, "Vulnerability Note VU#836068: MD5 vulnerable to collision attacks"
• A collision attack is where an attacker, given access to a hashed password (or other plain text), crafts a password that yields the same result when hashed. Thus to a password authentication system, the crafted "collision" seems to be the correct password.
• If your password hashing scheme does not use a salt, none of this is interesting to you, as you have little or no security to speak of given an attacker (internal or external) who has access to your hashed passwords.

OK, so what does any of this mean to you? Is MD5 secure? Well, not really. It is possible, with moderate hardware investment and access to the hashed password to generate a "skeleton key." No one can "crack" the original password in a reasonable amount of time that I know of or that I've read about, but access to an equivalent password solves many problems for an attacker, even if they can't then take that password and use it against other services (since those services would not be using the same "salt" which prevents the same password hashing the same way on two different sites or services).

The question you have to ask yourself is this: why are you hashing passwords? Is it to protect them, should someone gain access to your systems from the outside? Is it to protect them from those who have access to the data store? In these cases, md5 is at best a weak protection, but it is significantly better than some of the alternatives (DES, etc.) which are breakable in practically no time.

But MD5 is used in many places besides password hashing. Should we stop using it there? Probably not.

For example many backup and data validation tools use MD5 to make sure that data has not been modified (either to initiate a backup/copy or to safeguard against accidental local change). These purposes are still served just as well now as they were when MD5 was introduced, and the fact that MD5 has been proven to have possible collision attacks does not really impact the data integrity aspect of the algorithm. Of course, there are cases where MD5 will identify a block as unchanged when it has, in fact, changed. This is true for all hashing algorithms, but the reason that MD5 was initially considered acceptable for this purpose was that the chance of that happening without malicious intent is astronomically small (that malicious intent was not believed to be as much of a factor then is not interesting to us, now). It would be a bit like dropping a penny down into one of those boxes with water where the goal is to land it on a small platform, and just as you dropped it, an earthquake struck, causing the penny to bounce off the platform, jump back up through the slot and blind you. Just as I don't recommend avoiding such games because of the risk of blindness, I don't think you need to stay away from hashing algorithms (including MD5) in order to avoid missing a data update. If you think someone might be waiting for you to drop the penny so they can set off some dynamite, then you have a different kind of problem, and MD5 might not be the best choice (e.g. if you're performing MD5 checksums in order to verify that a system's software has not been compromised).

Now, that changes as your risk profile changes. There are times, I believe, where it makes sense to take extra precautions. For example, if you're making constant backups of large amounts of rapidly changing data whose integrity in original and backup form has a high risk associated (e.g. medical data), then I might use two hashing algorithms to perform the verification. MD5 might be a fine choice for one of them, but I'd use SHA-1 or something similar on top of it. It's still astoundingly unlikely to be an issue, but there's a time an place for being stupidly extra-certain and if you can afford the extra CPU cycles, why not compute two hashes while you're looking at the data?

What about SHA-1? Hasn't that been broken too? No, SHA-1 has known weaknesses which will likely yield security-impacting attacks in the future, but as of now, these weaknesses have yet to be translated into actual attack vectors. It's certainly worth staying on top of, and keeping a flexible hashing scheme (ala the OpenBSD/LDAP schema) in your application in order to upgrade to SHA-3 when it becomes available and has been thoroughly tested, but for now SHA-1 is an excellent choice for anything short of military/state-secret sorts of crypto-hashing needs.

Bruce Schneier, who is recognized around the world as an authority on cryptographic security, had this to say about the news regarding SHA-1:

They can find collisions in SHA-1 in 2⁶⁹ calculations, about 2,000 times faster than brute force. Right now, that is just on the far edge of feasibility with current technology.
Jon Callas, PGP's CTO, put it best: "It's time to walk, but not run, to the fire exits. You don't see smoke, but the fire alarms have gone off." That's basically what I said last August.

It's time for us all to migrate away from SHA-1.
Most of the hash functions we have, and all the ones in widespread use, are based on the general principles of MD4. Clearly we've learned a lot about hash functions in the past decade, and I think we can start applying that knowledge to create something even more secure.

Hash functions are the least-well-understood cryptographic primitive, and hashing techniques are much less developed than encryption techniques. Regularly there are surprising cryptographic results in hashing ... we still have a lot to learn about hashing.

Perl 6: Why So Long?

Over the years, many people have asked me when Perl 6 is going to happen. Now, I've only been peripherally involved, and I don't think I can speak for any of the current developers, but here's my take. First off, comparing development times of Perl 6 to, say, Python 3 (ne Python 3000) is entirely spurious. Python and Perl 5 relate to Perl 6 in roughly the way that classic Lisp 1.5 relates to Common Lisp. That is to say, Python and Python 3 are essentially the same language and exist at essentially the same order of complexity. In fact, they exist at about the same order of complexity as Perl 5, Ruby, PHP and many other high level languages.

Perl 6, meanwhile, is a massively ambitious effort that aims to meld the best features of nearly every style of language design into a single language. This means that the language must be able to represent programs as data (in order to implement true macros); it must provide a meta-object protocol (in order to support Ruby-style mixins and Smalltalk-style traits); it must implement function overloading (C++-style calling) and multi-method dispatch (CLOS-style methods) while also providing interface contracts (like Java) and generics (C++ at the low-level, Haskell at the high level); and it should provide native threading and parallel execution (ala Fortress). Now, take a language that has all of these features, and yet still manages to be familiar to a C-derived language programmer and also allow programs full access to the definition of the language at run-time in order to support multiple Common Lisp style domain-specific languages within a single program. To my knowledge no other language has ever taken on all of these goals and managed to get very far.

OK, so that's the excuse. What's the reality? Hmm... I'd say that Perl 6 is probably closing in on its .0 release within the next 2-3 years. Realistically, it probably would have taken a team of dedicated programmers who knew the finer points of self-hosted language design a couple of years to accomplish the Perl 6 design and implementation, given a clear idea of what they wanted from the onset. Perhaps a bit longer, but not much. As it was, many of the Perl developers have other things to do and Larry had some time that he wasn't able to do much for personal reasons in the middle of the whole thing. All of that combined with the fact that the Perl community was never entirely sure what the end-goal would be, and much of the design process has been a journey of discovery and... well, 10-12 years isn't a surprising number.

These days, there's an STD that describes the grammar and a fairly solid set of specs. That's a big improvement. There's also a virtual machine for running the language that's reached 1.0 status and deployed what can arguably be called the most advanced compiler-writing toolkit ever written. Again, a huge leg up.

That in turn has enabled the creation of a new prototype of the language that uses said virtual machine, taking a large portion of the burden of implementation off of the Perl 6 team, and the result has been a flood of development on the prototype, which has overtaken that of previous efforts in only a little over a year.

In the end, if you thought that Perl 6 was going to be Perl 5 with a few changes, you're in for a shock. If you thought that Perl 6 was basically a dead project because it has taken almost 10 years so far, then you're not aware of the history of such language design (the Common Lisp design and implementation process took nearly as long with DARPA and many commercial Lisp organizations backing it).

As we enter the final stretch and Perl 6 begins to become a platform upon which real work can be done, I just wanted to remind everyone that, while simpler languages (and I mean that in a non-pejorative way) rise and fall, there are some things that are worth waiting for.