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.
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?
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) ======= ============= =========== =============