[Discuss] password strength

[tmetro+blu at gmail.com (Tom Metro)]

Kent Borg wrote:
> For example, "8e53-arrow-spell-genetic" is pretty easy to type and
> remember, yet it has 48-bits of entropy in it.  Not enough entropy for
> en encryption key, but plenty for a password.  Entropy doesn't have to
> be hard to type and impossible to remember.

Entropy calculations can be very misleading, as the things that make a
password easy to remember also make it much easier to guess. Password
strength meters, for example, will give you quite misleading answers,
because they usually look at character set and length, and not the
patterns. At most, they look for dictionary words and maybe the presence
of L33t speak.

Ars Technica has a good article on this:

http://arstechnica.com/security/2013/05/how-crackers-make-minced-meat-out-of-your-passwords/

  Anatomy of a hack: How crackers ransack passwords like
  "qeadzcwrsfxv1331"; For Ars, three crackers have at 16,000+ hashed
  passcodes--with 90 percent success.

  The most thorough of the three cracks was carried out by Jeremi
  Gosney, a password expert with Stricture Consulting Group. Using a
  commodity computer with a single AMD Radeon 7970 graphics card, it
  took him 20 hours to crack 14,734 of the hashes, a 90-percent success
  rate. Jens Steube, the lead developer behind oclHashcat-plus, achieved
  impressive results as well. (oclHashcat-plus is the freely available
  password-cracking software both Anderson and all crackers in this
  article used.) Steube unscrambled 13,486 hashes (82 percent) in a
  little more than one hour, using a slightly more powerful machine that
  contained two AMD Radeon 6990 graphics cards. A third cracker who goes
  by the moniker radix deciphered 62 percent of the hashes using a
  computer with a single 7970 card--also in about one hour.
  [...]
  The other variable was the account holders' decision to use memorable
  words. The characteristics that made "momof3g8kids" and "Oscar+emmy2"
  easy to remember are precisely the things that allowed them to be
  cracked. Their basic components--"mom," "kids," "oscar," "emmy," and
  numbers--are a core part of even basic password-cracking lists. The
  increasing power of hardware and specialized software makes it trivial
  for crackers to combine these ingredients in literally billions of
  slightly different permutations. Unless the user takes great care,
  passwords that are easy to remember are sitting ducks in the hands of
  crackers.
  [...]
  ...it was time for stage two, which consisted of a series of hybrid
  attacks. ...a hybrid attack marries a dictionary attack with a
  brute-force attack, a combination that greatly expands the reach of a
  well-honed word list while keeping the keyspace to a manageable
  length.
  [...]
  One of the things Gosney and other crackers have found is that
  passwords for a particular site are remarkably similar, despite being
  generated by users who have never met each other. After cracking such
  a large percentage of hashes from this unknown site, the next step was
  to analyze the plains and mimic the patterns when attempting to guess
  the remaining passwords. The result is a series of statistically
  generated brute-force attacks based on a mathematical system known as
  Markov chains. Hashcat makes it simple to implement this method. By
  looking at the list of passwords that already have been cracked, it
  performs probabilistically ordered, per-position brute-force attacks.
  Gosney thinks of it as an "intelligent brute-force" that uses
  statistics to drastically limit the keyspace.
  [...]
  Early in the process, Steube couldn't help remarking when he noticed
  one of the plains he had recovered was "momof3g8kids." "This was some
  logic that the user had," Steube observed. "But we didn't know about
  the logic. By doing hybrid attacks, I'm getting new ideas about how
  people build new [password] patterns. This is why I'm always watching
  outputs."

  The specific type of hybrid attack that cracked that password is known
  as a combinator attack. It combines each word in a dictionary with
  every other word in the dictionary. ... Steube was able to crack
  "momof3g8kids" because he had "momof3g" in his 111 million dict and
  "8kids" in a smaller dict.
  [...]
  What was remarkable about all three cracking sessions were the types
  of plains that got revealed. They included passcodes such as
  "k1araj0hns0n," "Sh1a-labe0uf," "Apr!l221973," "Qbesancon321,"
  "DG091101%," "@Yourmom69," "ilovetofunot," "windermere2313,"
  "tmdmmj17," and "BandGeek2014." Also included in the list: "all of the
  lights", "i hate hackers," "allineedislove," "ilovemySister31,"
  "iloveyousomuch," "Philippians4:13," "Philippians4:6-7," and
  "qeadzcwrsfxv1331." "gonefishing1125" was another password Steube saw
  appear on his computer screen. Seconds after it was cracked, he noted,
  "You won't ever find it using brute force."


The full article is well worth a read to go on a journey with the author
as he details the approach each of the three crackers took to
successively uncover more and more passwords.

It can be argued that the article used a straw man circumstance -
unsalted MD5 hashes - yet so many sites use techniques that are worse,
or only slightly better. (The article discusses how salting is largely
to defeat rainbow tables (pre-computed hashes), yet they're rarely used
these days, with crackers instead opting to use fast GPUs to compute
hashes on the fly.)

The real problem with most of the hashing algorithms in use today is
that they were designed for computation speed, which is exactly opposite
what you want for protecting passwords. The best performing system used
in the article could compute 8 billion hashes per second. But algorithms
designed to thwart brute force cracking are nothing new. Substitute the
"SHA512crypt function included by default in Mac OS X and most
Unix-based operating systems [that] passes text through 5,000 hashing
iterations..." and that same hardware plummets to "2,000 guesses per
second." Probably even slower for algorithms like bcrypt.

This illustrates that even fairly long passwords are not all that secure
if they rely on dictionary words, L33t speak, and other statistically
predictable use of numbers and punctuation. It's really hard to beat
truly random character sequences.

 -Tom

-- 
Tom Metro
Venture Logic, Newton, MA, USA
"Enterprise solutions through open source."
Professional Profile: http://tmetro.venturelogic.com/