Brute force password cracking

cc by Alexander Edward Genaud
or Poetic License



Standard password requirements are nonsense. You've probably been advised or are even required to generate passwords that are eight characters long, contain numbers, symbols, and mixed case. They may change frequently. And you need unique passwords for each of the hundreds of systems and sites you use. Oh, and you can't write any of them down.

Bu11$hit!

Such advice is neither practical nor sound. It was en vogue before Perestroika, while Elvis was alive, floppy disks were invented, and Roger Moore played James Bond. Computational power has increased millions of times over since the 1970's. Today anyone with modest resources has access to the computational power required to crack any eight character (56-bit) key, and often within minutes due to the miserable quality of human generated passwords.

Since the 1990's encryption has become ubiquitous, from cash machines to just about any web site that requires a password. Equivalent 80-bit symmetric, 160-bit elliptic, and 1024-bit asymmetric are minimal standards today. Whether Google, Facebook, or your bank, whenever you see HTTPS://, you are using at least 1024-bit asymmetric (80-bit symmetric). However, security is only as good as the weakest link. And the weakest link in the chain is most often the human or his password. So, what do 80-bit passwords look like?

F/2vu-yX6k,3W
jkdyebiwqwsdjtrsf
TarZPjWyByhayJ
403649682372061412740739

The first thing you might notice is that they are long; Much longer than eight characters. The second thing you might notice is that they do not all consist of funny characters; You'll notice that some are longer than others, depending on their character diversity. Finally, they may appear to be random; They are not, but there should be no obvious pattern.

Random

Random or pseudo-random is an important characteristic of a password. Perhaps the mix of case, number and symbol suggestion was a failed attempt to encourage random passwords. Unfortunately, when required, most people simply capitalize the first letter and append a number at the end, or something equally uninspired. The most popular are Password1, Password123, Qwerty1, and variations like Pa$$w0rd. With no restrictions, popular passwords are 123456, password, 12345678, qwerty, iloveyou, letmein, dragon, 111111, sunshine, and the like. We know because millions of passwords are cracked and published online each year (recently: Adobe 130 M users, Facebook 6 M users, Schnucks 2 M users, Linkedin 6 M users, Sony 77 M users, RockYou! 32 M, Yahoo 450 K, Hotmail est. 500 K).

Key length

Aside from secrecy and uniqueness, which I hope are obvious, the second most important characteristic of a password is key length. Key length is measured in bits of entropy. It's approximately based on the total number of characters used to make a password. R#jY2%h is better than 9a#J. While extra symbols, numbers and mixed case do improve a password strength substantially, often they make a password more difficult to memorize. You can choose to have longer passwords with few character types, or slightly shorter passwords with more character diversity.

Pen or memory?

Random long passwords are at odds with memorization. If you can memorize a truly random password, it's probably not long enough. If you can memorize a sufficiently long password, then it's probably not truly random.

Paradox? Only because we repeat ancient lore from 1970's spooks. If you must, write your random and unique passwords down, and store them in a safe place. But, I suggest you keep some portion (perhaps not unique) in brain memory that is not vulnerable to discovery. Writing passwords down grants you the luxury of truly random long passwords.

Pseudo-random mnemonics

Alternatively, or for the most important resources, you may consider memorizing pseudo-random passwords. I can't tell you all of my tricks, but one pitfall:

thisisnotagoodpassword

The above is naively calculated as 103 bits. It is not, but you may have read such poor logic elsewhere. A cracking engine will attempt to find patterns before systematically guessing every conceivable combination. The above password is made of words, correctly strung together grammatically. It consists of the 20th, 2nd, 12th, 6th, and 61st most frequent word forms in the English language. The word 'password' is not particularly common in English texts, but it is ironically popular as a password. Its entropy or strength is likely closer to 25 bits than 103.

i,ymwtcaa,satfloewfals,ltoyarn

Instead, you might want to consider an alternative, such as the first letter of each word from a long sentence, like the one you are reading now. Combine short poems from different languages with metro line stops and the prominence of mountains you've climbed. Or the ingredients to your favourite recipe:

3Cf21/2m1/3Cw1TSPNsvo

Paranoia 112

I briefly mentioned TLS/SSL keys above (HTTPS://). As of 2014, the mandatory minimum key will double from 1024 to 2048-bit asymmetric (80 to 112-bit symmetric equivalent). If you are an executive with valuable information, a whistleblower, political dissident, freedom fighter, journalist undercover, responsible for network security, or just clinically paranoid, 112-bits should be your password strength target. If you need more security than that, then skip 128, because only a 144-bit password can match your trendy 4096-bit RSA or elliptic key, on a computer air gapped from the network. What do 112-bit passwords look like? They are big!

8g3xi5mjd9sd28shd0lpa5
z9H6mWhC8ndfT9H5G8h
4036496823720614127407899233257870
jkdyebiwqwsdjtrsfjsdosdv
F/2vu-yX6k,3WrT7%/

Examples

Based on the Von Neumann-Landauer Limit, which represents the absolute minimum energy required by the laws of physics to change one bit state, a brute force attack on 122-bits would consume about 4 TWh, roughly the amount of energy consumed by Google each year.

However, closer to reality, based on documented distributed attacks on SHA-256 hashed targets, a 77-bit password could be cracked in a year after consuming 370 GWh, with 69-bit passwords cracked in a day and 64-bit passwords cracked in the first hour.

A modest but determined attack using commercially available specialized ASIC hardware could crack 66-bit passwords within a year consuming average American household consumption of 11 MWh. 57-bit keys would be cracked in the first day. With more of the same hardware and Google's energy supply, we could crack 84-bit passwords within a year.

The chart below groups password examples by similar strength, within 5 bits of each other. There are examples of mix case, numbers, and symbols; examples of only lower case numbers; mix case and numbers; etc. They are indented to highlight their character length. Each group has two estimates of the amount of time required on average to complete a brute force attack, from realistic GWh/year distributed attack on the left, and a GWh/year attack at the limit of the laws of physics on the right.


=======   =============                             =============
Shannon   distributed                                 theoretical
Entropy   rate (1 GWh)                              limit (1 GWh)
=======   =============                             =============
115|......................................................decades
114|                    TarZPjWyByhayJRasjjs
113|                      8g3xi5mjd9sd28shd0lpa5
113|                   z9H6mWhC8ndfT9H5G8h
112|                        jkdyebiwqwsdjtrsfjsdosdv
112|                  F/2vu-yX6k,3WrT7%/
111|
110|........................................................years
109|
108|                     8g3xi5mjd9sd28shd0lpa
108|                   TarZPjWyByhayJRasjj
108|                       jkdyebiwqwsdjtrsfjsdosd
107|                  z9H6mWhC8ndfT9H5G8
106|
105|                 F/2vu-yX6k,3WrT7%
105|.......................................................months
104|
103|                      jkdyebiwqwsdjtrsfjsdos
103|                    8g3xi5mjd9sd28shd0lp
102|                  TarZPjWyByhayJRasj
101|                 z9H6mWhC8ndfT9H5G
100|.........................................................days
099|                F/2vu-yX6k,3WrT7
098|                     jkdyebiwqwsdjtrsfjsdo
098|                   8g3xi5mjd9sd28shd0l
097|
096|                 TarZPjWyByhayJRas
095|                z9H6mWhC8ndfT9H5
095|........................................................hours
094|                    jkdyebiwqwsdjtrsfjsd
093|               F/2vu-yX6k,3WrT
093|                  8g3xi5mjd9sd28shd0
092|
091|                TarZPjWyByhayJRa
090|......................................................minutes
089|               z9H6mWhC8ndfT9H
089|                   jkdyebiwqwsdjtrsfjs
088|                 8g3xi5mjd9sd28shd
087|              F/2vu-yX6k,3Wr
086|
085|               TarZPjWyByhayJR
085|..decades.............................................seconds
084|                  jkdyebiwqwsdjtrsfj
083|              z9H6mWhC8ndfT9
082|                8g3xi5mjd9sd28sh
081|
080|             F/2vu-yX6k,3W
080|..years......................................................
079|                 jkdyebiwqwsdjtrsf
079|              TarZPWjyByhaxJ
079|                        403649682372061412740789    Yottahash
078|
077|               8g3xi5mjd9sd28s
077|             z9H6mWhC8ndfT
076|                       40364968237206141274078
075|                jkdyebiwqwsdjtrs
075|..months.........................................milliseconds
074|            F/2vu-yX6k,3
074|             TarZPWjyByhax
073|                      4036496823720614127407
072|              8g3xi5mjd9sd28
071|            z9H6mWhC8ndf
070|               jkdyebiwqwsdjtr
070|..days.......................................................
069|                     403649682372061412740          Zettahash
068|           F/2vu-yX6k,
068|            TarZPWjyByha
067|             8g3xi5mjd9sd2
066|                    40364968237206141274
065|              jkdyebiwqwsdjt
065|           z9H6mWhC8nd
065|..hours..........................................microseconds
064|
063|                   4036496823720614127
062|           TarZPWjyByh
062|          F/2vu-yX6k
062|            8g3xi5mjd9sd
061|             jkdyebiwqwsdj
060|..minutes....................................................
059|                  403649682372061412                  Exahash
059|          z9H6mWhC8n
058|
057|          TarZPWjyBy
056|           8g3xi5mjd9s
056|                 40364968237206141
056|            jkdyebiwqwsd
056|         F/2vu-yX6
055|..seconds.........................................nanoseconds
054|
053|         z9H6mWhC8
053|                4036496823720614
052|
051|           jkdyebiwqws
051|          8g3xi5mjd9
050|         TarZPWjyB
049|        F/2vu-yX
049|               403649682372061                       Petahash
048|
047|        z9H6mWhC
047|          jkdyebiwqw
046|         8g3xi5mjd
046|              40364968237206
045|        TarZPWjy
045|..milliseconds....................................picoseconds
044|
043|       F/2vu-y
043|             4036496823720
042|         jkdyebiwq
041|       z9H6mWh
041|        8g3xi5mj
040|
039|       TarZPWj
039|            403649682372                             Terahash
038|
037|        jkdyebiw
037|      F/2vu-
036|           40364968237
036|       8g3xi5m
035|      z9H6mW
035|..microseconds...................................femtoseconds
034|      TarZPW
033|          4036496823
032|       jkdyebi
031|     F/2vu
031|      8g3xi5
030|
029|         403649682                                   Gigahash
029|     z9H6m
028|     TarZP
028|      jkdyeb
027|
026|        40364968
025|     8g3xi
025|..nanoseconds.....................................attoseconds
024|    F/2v
023|    z9H6
023|     jkdye
023|       4036496
022|    TarZ
021|
020|    8g3x
019|      403649                                         Megahash
018|    jkdy
018|   F/2
017|   z9H
017|   Tar
016|     40364
015|   8g3
015|..picoseconds....................................zeptoseconds
014|   jkd
013|    4036
012|
011|
010|
009|   403                                               Kilohash
=======   =============       ===========           =============
Shannon   moderate hash       distributed             theoretical
Entropy   rate (1 KWh)        doc (1 GWh)           limit (1 GWh)
=======   =============       ===========           =============

cc by Alexander Edward Genaud or Poetic License

Moral rights < PTS CC BY-NC < [ Password Cracking, ] > Erin > Latest