Good and Bad Passwords How-To
Password Cracking Goals, Techniques, Relative
Merits, and Times
Historically, password crackers were most interested in root or
administrative account passwords when they cracked passwords. With
the movement of organizied crime, into the realm of computer and
password cracking, mostly working out of Eastern Europe, and mostly
targeting financial and e-commerce web sites, any accounts and
sensitive customer information would likely be of interest.
The methods used to gain unauthorized access to systems is beyond the
scope of this discussion. The tools and methods for cracking
passwords are the same regardless of who is using them. They are
password cracking programs that use password dictionaries or brute
force. The feature lists of common password cracking programs
are discussed. Also listed are the suggested standard
dictionary transformations for Crack, once the best known tool for
cracking passwords. How long it takes to crack passwords and the
primary factors affecting password cracking times are covered.
Why password dictionary attacks dramatically lower brute force
password cracking times is discussed.
Goals of the Cracker
The goal of crackers has been to obtain the root account password on
UNIX systems and administrator accounts on Windows
systems. These accounts will always be of more value than
ordinary users on these systems. With some UNIX security setups, the passwords for users
in the wheel, security, or root group may have significant value.
Since the cracker presumably already has some degree of access to
the target machine (cracking can only be performed when the attacker
already possess the password hashes which are not available to ordinary
users on modern systems), it's not likely that
unprivileged accounts will be of much value to the intruder, but
the techniques for obtaining passwords are the same regardless of
the target account.
With the movement of organized crime into these activities the
targets are likely to shift. Instead of targeting the employee
administrators and operators of web sites, the customers of financial
and e-commerce web sites have become the real targets.
So far, at least, it seems that
the web servers have been an entry point to the internal networks
of the compromised companies, from which they have then stolen
customer information.
I have found no evidence that these criminals have targeted end
user web accounts at either financial services or ecommerce sites.
That they have not done so only means they have not seen the
opportunity to realize sufficient gains.
It seems clear a significant portion of the U.S. online financial
services industry has been compromised. These criminals clearly
have both the technical skills and necessary financial and
computer resources to crack most web account passwords if they
saw a good reason to do so.
At least for the present financially motivated criminals don't
seem to be interested in consumer web accounts at either financial
services or ecommerce sites. Their is little reason to be relieved
at this. The accounts and password hashes are there for the taking.
Security is poor enough at many sites and it's simply more rewarding
to go directly for the entire customer database as Sony's 77 million
customer's whose credit cards were compromised learned. At those
sites that don't have absurd restrictions on passwords that prevent
strong passwords, I have upgraded my passwords since I heavily
revised this section in 2012, to account for the increases in
computer speed and recent developments in password cracking.
Where customer's passwords are not the target,
intruders are likely to need only one password for an account
with suitable privileges. Additional accounts may be
of some value in preserving access, but are not likely to make much
practical difference in obtaining access to the system at the
desired privilege level. UNIX and Windows systems are normally
quite different in this regard; UNIX systems normally only have
one root account with full system privileges where Windows systems,
especially servers, may have multiple administrator level accounts,
each of which has full system access.
When I wrote this page 13 years ago, 8 character passwords
with mixed case, one or more digits,
a symbol or puncutation mark, and designed so it was not vulnerable
to a dictionary attack were sufficient to be confident your password
was safe. Today, a lot depends on who is cracking a password list
with your password in it. 10 characters may be safe or pretty
marginal. 12 characters appear to be safe against almost anyone
except government agencies such as the NSA. There are so many factors,
some of which are not knowable, that I normally choose 14 characters
for accounts that matter.
While all 8 character passwords would still take years on one fast
desktop or hours on a fast network of computers set up for cracking
passwords, a brute force approach is not likely to be necessary.
Users insist on creating bad passwords. Just over 90% of all known
cracked passwords are in this
top
10,000 password list. All a cracker needs to do is use this
list as their dictionary and in seconds they will get about 70%
to 95% of the passwords on most systems. 93%
of the passwords cracked in the early June 2012 compromise of the
business networking site linkein.com were in this list.
If they do not get the account(s) they want or need on a system with
a large common password list, the crackers will turn first to a small
standard dictionary plus common names, and perhaps less common passwords
and or numeric repeats and sequences, keyboard sequences, and alphabetic
repeats and sequences, along with common rules. A skilled cracker will
work through a progression of dictionaries and rules that have worked
in the past. Only for something very important to them, that has not
fallen with their normal techniques, will a skilled cracker use a brute
force approach, or more unusual dictionaries and rule sets.
Cracking Tool's Feature List
The fundamental flaw in the password system is the tendency of
most people to select passwords that are easy to remember. This
means they choose names and words that have personal meaning to
them as their passwords; these can nearly always be found in
dictionaries or word lists. Often such names or words are modified by
applying predictable changes to them. This may be in response to
system requirements to vary the kinds of characters included in a
password.
The alternative to brute force is a dictionary attack. At its
simplest this means treating each word in a dictionary
(electronic word list) as a password and hashing it, and then
comparing the resulting hashes to the hashes in the password file
being cracked. If the hashes match, the password is known. It's
imperative to understand that this is only the most rudimentary
form of dictionary attack, and that the real power of dictionary
attacks come from understanding the ways in which most people
vary names and dictionary words when attempting to create a
password. By applying all the common transformations to every
word in the electronic list and encrypting each result the number of
tested passwords multiplies rapidly. Every "clever" way of
manipulating words to hide their origin is known to the cracking
tools and those who use them.
To understand what make weak and strong passwords, it's necessary
to understand what cracking tools can and cannot do. When this page
was first written, L0phtCrack was the leading Windows cracking tool.
The easy to use L0phtCrack
with its GUI interface is rather limited compared to Crack and
John the Ripper in its dictionary transformation capabilities.
L0phtCrack can append a user specified number of characters to the
end of the dictionary words. It works through the entire
character set and appends every combination to each dictionary
word; this includes all letter sequences as well as digits
and symbols. L0phtCrack takes less than a second to process the
default dictionary of nearly 30,000 words and about a minute and
a half to process two additional characters in conjunction with
the 30,000 word list (on a PIII 500).
L0phtCrack has been superceded by other tools on Windows. In
particular there are two tools that make use of rainbow tables
to target Windows systems. Rainbow tables are a form of
a sophisticated dictionary attack using precomuted hashes. They
include very sophisticated storage methods that do not require
all the hashes to be stored. They check the ends of "chains" of
hashes. They can determine if a password is part of the chain
without computing every password in the chain. Only after it
is determined that a password is part of a chain is each password
in that chain computed and it's individual hash compared with
the one in the password file. This takes more computation than if all
the computed hashes were stored, but even with today's disks,
all possible passwords up to reasonable lengths to test cannot
be stored on disk. Rainbow tables allow enough passwords to
be stored that they claim a 99% success rate on passwords up
to 13 characters and 96% on 14 character passwords.
Rainbow tables only work against Windows systems because all
Windows systems convert the same plaintext password to the
same hash. This is incredibly stupid. The problem was well
understood before Microsoft developed it's password storage
method. Since Unix has had passwords, all Unix and Unix like
systems have used random "salts" to cause each plaintext password
to be stored with a different hash. Origninally the salts
were only large enough to have 4096 variations. Today the
salts are large enough it is unlikely anyone will ever find
two passwords
stored with the same hash on any Unix like system.
Precomputation attacks cannot work against Unix like systems
or any system, including web sites, that use a proper salting
mechanism.
For 20 years Microsoft has refused to acknowlege there is
anything wrong with their grossly inferior password storage
method. This will be explained in detail on my
Windows Passwords page.
Both John the Ripper and Crack allow the user to define
rule sets that control the transformations that are applied
to the input dictionaries (word lists). Below are most of
the transformations that John the Ripper can perform.
Crack has the same capabilities as do several other
cracking programs.
- Append or prepend defined characters to a word.
- Reverse a word.
- Duplicate a word.
- Mirror a word, i.e. append the reversed word.
- Rotate a word either left or right, i.e. move the first
letter to the end or the last letter to the front.
- Upper case a word.
- Lower case a word.
- Make only the first letter a capital.
- Male all but the first letter a capital.
- Toggle the case of all characters.
- Toggle the case of a character at a set position.
- Minimum and maximum word lengths can be set or long
words can be truncated at a set length.
- Suffixes (s, ed, ing) may be added to words.
- First, last or any specific character may be deleted.
- Characters can be replaced at a set location.
- Characters can be inserted at a set location.
- "Shift" the case, i.e. substitute the other character
on the same key, e.g. 'a' and 'A' or '5' and '%'.
- Shift the characters left or right by keyboard position
(so an 's' becomes an 'a' or 'd').
- Replace all of one character with another.
- Replace all characters of a class (for example vowels,
letters, non letters, digits) with a specific character.
- Remove all occurrences of any character from a word.
- Remove all characters of a class from a word.
- Reject a word if it contains or doesn't contain a character,
or characters from a class.
- Reject a word if the first, last or set character
is or is not a specific character or from a class.
- Reject a word unless it contains at least so many of a
character or characters from a class.
In the forgoing a class might be any of the following: a letter,
a vowel, a consonant, an upper case letter, a lower case letter,
a digit, a symbol or punctuation, a non letter (digits, symbols
and punctuation), alphanumeric or one of several others. The
length limits and reject options don't increase the possibilities,
but allow the cracker to skip "words" where a particular type of
transformation may not make much sense; this should improve the
cracking tool efficiency. For example, the dictionary may already
contain normal words with one or more digits already appended to the
word. By not appending additional digits to such "words", the
cracking tool may save some time by not creating less likely
passwords where three or four digits are appended to a normal word.
Cracking Tool Examples
The words that the transformations operate on can be either from
a standard dictionary (word list, one per line) or from the user
name and words (or names) extracted from the /etc/passwd
GECOS field (Unix like systems, only). Crack appears to be limited to words from
dictionaries. Rules can be combined to perform multiple
transformations on the words. Below is the list of actual
transformations suggested in the Crack 5 documentation:
- Lower case pure alpha words.
- Lower case and pluralize alpha words.
- Append digits and punctuation to all pure alpha words.
- Lower case and reverse pure alpha words.
- Lower case and mirror pure alpha words.
- Capitalize all alphanumeric words, i.e. first letter only.
- Capitalize all alphanumeric words and add a variety of common
punctuation so 'cats' becomes Cats! Cats? Cats. Cats, Cats- etc.
- Upper case all alphanumeric words.
- Remove vowels from pure alpha words.
- Remove white space and punctuation from those words that have
it.
- Duplicate short words.
- Perform most of the similar looking character substitutions
identified in the list of
don'ts.
- Lower case and prepend digits (all words).
- Capitalize then reverse alphanumeric words.
- Reverse then capitalize words.
- Upper case words adding common punctuation and swapping
zero for O.
- Upper case then duplicate, reverse and mirror words.
A number of the preceding transformations had length limitations
which have been omitted for simplicity.
How Long Does It Take to Crack Passwords?
Password Strength
Conceptually the easiest way to crack passwords is to generate
character sequences working through all possible 1 character
passwords, then two characters, then three characters, etc. This
is the brute force attack previously mentioned. It could
start at any specific length password. Each trial password is
hashed the same way as those under attack; if the resulting hash
is identical to the attacked password hash, the test password
that generated the new hash is the password being looked for. Theoretically any
possible password can be found this way, but generally there is
not sufficient computing power available to successfully
accomplish this, once passwords reach a certain length and
character diversity. Generally as computers have gotten faster
passwords have needed to get longer and more character diverse.
A number of factors determine how long brute force
attacks will take. Some may be under a system
administrators control but most are not; others may or may not
be under web site developer's control.
Most of the same factors that affect brute force attacks
also apply to dictionary attacks. The number of passwords to
be tested is simply the size of the dictionary times the number
of transformations to be made per word. There is an immidiate
complication; some transformation rules are not applied if
conditions in the rule are met. In such a case no number
can reasonably be calculated except an upper limit. Once a
number of passwords to be tested is known, it is simply a
a matter of dividing this number by CPS or cracks per second.
Most crackers don't just make one dictionary attempt on
a list of accounts and hashes. They try a small high yield
dictionary first then a larger lower yield dictionary, with
more or different transformations. So with dictionary
attacks there are no simple calculations to perform; it's
more about predicting a cracker's course of action or an
average cracker's course of action. Ultimately every
cracker reaches a decision, when he has enough passwords
from a list, or when fruther resources are not likely
worth the return. That's why cracking times are listed
for brute force attacks only.
Generally the most important factor in brute force cracking of
passwords is how many passwords need to be examined to cover all
possible passwords. Two factors determine this. They are the
length of the password and the number of characters
in the character set from which the passwords are formed. The
number of possible passwords is the number of characters in the
character set raised to the power represented by the password
length. For example, the number of possible three character
passwords formed by 26 lower case letters is 26 cubed.
The character groupings are typically considered to consist of
lower case letters (26), upper case letters (26), digits (10) and
symbols and punctuation (33 if the space is included). Obviously
the strongest passwords include at least one of each from all four
groups or 95 characters. The general formula described above is
often expressed as "characters ^ length" so an 8 character
password using all four sets would be 95^8.
Some people may choose
to consider subsets of characters (vowels and consonants) or
other factors that affect the strength of the password. This depends
on how easily and likey it is that someone attacking passwords can
adjust the search criteria. For example upper case letters, when used, are
almost always used in the first character position and very rarely
any place else, except when all letters are upper case.
Good crackers like to go with the odds and there
are few things easier to do than check the first character
position for upper case letters. Nearly all password cracking tools
have a built in option that will do this. This should get more than 95%
of the passwords with an upper case letter with a fraction the
cost of checking all positions. If all passwords were done this way
first, the cracker can choose to come back and do the other positions
in a separate step, or if there are only a few uncracked passwords
he may choose to move on to a more rewarding project.
This would be even more efficient
if the letters to be uppercased were orderd by the frequency that
letters are used to start words in an unabridged dictionary, or
the frequency that capital letters occur in the local languge,
or the frequency of upper case letters in passwords the cracker
had previously cracked. My Password
Evaluator separates the symbols into common punctuation,
common symbols, and programming symbols; if any 2 from different
groups are used, full credit for 33 is given, otherwise only
the number of characters in the subgroup is counted.
Common punctuation marks are used much more frequently in
general use than symbols from the other groups, and so
punctuation marks should be more common in passwords than the
other symbols.
Cracking tools are designed to provide built in options that
facilitate finding commnon ways in which passwords are created,
and crackers use what is widely known about the formation of
common passwords, plus their own personal experience. People
have shown again and again, despite the overwhelming advice
to the contrary, to be highly predictable in creating passwords
in ways that are easily cracked. Using the cracking tool's
capabilities and what is known about how crackers work, makes
more sense that to use a simple unvarying mathematical
formula which makes no allowance for cracking tool capabilities
and cracker behaviour. Any seriously considered variation that
takes both toool and cracker capabilities into account should
result in more refined estimates, than the simple formula.
Computing Power
One factor is the amount of computing power available to solve
the problem. Computing power increases continually; Moore's law
anticipated a doubling of processing power every 18 months and
this has so far been a close approximation to reality. This
works out to about a 100 times increase each decade. In 2014, a
computer is likely to have approximately a billion times the
computing power available when the first UNIX was developed in
the very late 1960s and early 1970s.
Speed Changes 2001 - 2014
In 2000, in "Password Cracking Using Focused
Dictionaries"1,
Paul Bobby refers to 48000 "password combinations per second"
on a "P2-400MHz computer". In "UNIX Password Security - Ten
Years
Later"2,
Feldmeier and Karn refer to a "top speed of 1092.8 crypts per
second on a Sun SPARCStation." in 1989. Applying
Moore's law we should get between 100,000 and 200,000 crypts per
second on a high end workstations 12 years later. Using
L0phtCrack5,
I've seen about 1.2 million "Tries/sec" using only alphanumeric
characters and about nine hundred thousand "Tries/sec" using the
full 95 character, printable ASCII character set, on a PIII 500.
I believe the L0phtCrack number is at least in part a result of
the weaker encryption used by NT as discussed
on another page. Considering
these in 2001 I used 100,000 CPS for my desktop system.
In early 2007 I wrote the following:
'The best reasonably recent estimates I've seen were presented
in the 2005 Ontario Universities Computing Conference. Johnathan Graham
indicated in a Power Point presentation that "A G5 running at 2.7Ghz
with a highly optimized copy of John The Ripper hits 900,000 cracks per
second.8 This was part of a
presentation that was very knowledgeable and presented in to an
audience of computer professionals. I've seen other much higher
numbers recently but when looked at more closely these may be for
applications, including web sites, and there is no reason to assume
these should be a reliable indicator for cracking operating system
passwords. This number is entirely consistent with the progression
one would expect from other widely cited cracking studies. Though
the figure may be approaching two years in age, the characterization
of "a highly optimized copy of John The Ripper" suggests many
crackers will not make as effective use of the resources available to
them.'
In other words the data that I used in 2007 to estimate cracking times
was likely two and perhaps three years old. Using Moore's law only and
extrapolating from my original calculations, my 2007 numbers should have
been about 25 times faster than my 2001 numbers based on data from 2000,
rather than merely 10 times faster. In late May 2012, I used
Moore's law only and applied it to data from 2000. Allowing for doubling
every 18 months, in 12 years we get 2 ^ 8 or 256 times 100,000 or 25.6
million cracks per second. In mid 2012, 25,000,000 cracks per second seemed a
reasonable number for a fast desktop - one with a fast Intel i7 or top
end AMD 6 core processor. In 2012, I added a table for a fast cracking
network, with 10,000 times the speed of a single desktop.
In January 2014, about 20 months after I last recalulated the password
cracking time tables, for the first
time I have current numbers for specific hardware and identified hashing
algorithms. This is thanks to Hashcat.
On a single CPU PC with an AMD Phenom II X6 1090T, overclocked to 3.8 GHz,
running Hashcat v0.40, 64 bit, on Windows 7, three hash algorithmes were tested.
Phpass ran at 50,000 CPS, NTLM at 71,000,000 CPS and MD5 at 86,000,000 CPS.
This processor is about 4 years old but overclocked to put in in the range of
contemporary medium to high end desktops. I adjusted my single desktop
(in the tables below) to 75,000,000 CPS.
New Developments
Multi Core Computers
Four things have changed that make strong passwords for important accounts
more important than ever. The replacement of single core computers with multi
core computers has quickly increased the computing power available in home and
typical business environments. I don't think Moore's law has changed with
regard the the fastest computers available, but I do think the change to
multi core computers has caused
a short term spike in the total amount of computing power that is generally
available. Though graphics, gaming and other CPU intensive uses will never
have excess CPU power, typical
office and Internet applications rarely push mid to high end desktops to full
capacity except for infrequent, short spikes. In the second decade of the
21st century most home and office computers
are typically doing the automotive equivalent of idling, or maybe rolling
along a city street at 20 to 35 m.p.h nearly all the time.
In the past decade Microsoft has improved its performance
with regard to security and the timely availability of security related
upgrades. Despite this, I'd guess,
is that there are tens, more likely hundreds of millions, of 1 to 4 year old Windows
computers that are not up-to-date with security patches. I believe with
Windows 7, fully automatic updates are the default. Unfortunately, these
and the reboots which normally accompany them often occur at inopportune
times. I expect that many users disable automatic updates.
Even if every Windows computer in the world was fully up-to-date
with all security patches, it would be naive to think this is sufficient to
ensure these computers are immune to network penetration.
In practice, there is little reason to think that most home and small
business computers are much more secure than they were in the past.
I believe the average home computer represents only a modest challenge to a
skilled cracker and that there are many millions of compromised computers in homes
and offices available to non owners for illicit use.
Unless the user actively monitors their CPU use they
will never know anything unexpected is running on their computer.
Once one of these clients is detected and reported to any security organization,
anti-virus and malware scanners should be able to detect such software.
On the other hand there are sophisticated methods to hide viruses and
malware from the scanning tools. Few would have better motivation than
criminals, to ensure
the software they need, was difficult to detect on the compromised
computers on which they were depending. Also, those
with compromised computers are most likely to be those who do not take
the steps to actively defend their computers.
Graphics Processing Units
Second, there is a fairly new development which very much does impact on
Moore's law. This is the development of Graphics Processing Units (GPU),
which can be added to a standard desktop computer as easily as a video
card; you do need an appropriate type video slot in the motherboard.
Some motherboards have two video card slots. One of the tasks that GPUs
are very well suited for is password cracking. When a GPU is being used
for non grapics purposes, it is sometimes
called a GPGPU or general purpose GPU. GPUs are a part of high end video
cards that sell for $80 to $1,400. GPGUPs add massive parallel processing
capabilities to a desktop PC. Some GPU's approach 4000 streaming processors,
which for appropriate tasks, like cracking passwords, is like adding 4000
cores. The performance increase varies depending on the specific hashing
algorithm as well as the specific GPU.
At least two companies are
selling Windows cracking software specifically designed to take advantage of GPUs.
These Windows cracking programs are products I
more or less stumbled on. I did no systematic search. Other well
known and more general products, like John the Ripper are likely
to follow with GPU optimization. Basically
for the price of a high end desktop, plus a few hundred to a couple
thousand dollars for the cracking software which may include rainbow
tables, one can now have a small
super computer to crack passwords. There are even free products with
these cpabilities.
oclHashcat
is free and optimized to use CUDA and Stream enabled video cards.
It runs on both Windows and Linux. Its devlopers tested it with 5 GPU
video cards that are available for around $400 to $700, and a variety
of widely used password hashes. The Windows PC with an Nvidia gtx580 cracked
NTLM hashes at 3.9 billion CPS or 55 times faster than the single CPU
PC listed above; this is one of the slower machines. The fastest used
eight AMD R9 290X cards (or perhaps 4 double R9 290X) and ran at 141
billion CPS or another 36 times faster
than the gtx580, or 1980 times faster than the single CPU PC. For
about $2500 plus a high end PC with sufficient video slots, you can
make a desktop PC almost 2000 times faster than a contemporary high
end multi core desktop without GPU(s), for cracking NTLM hashes.
Network Cracking
Third, password cracking lends itself well to parallel processing on
multiple machines with near linear gains as more machines are
applied to the problem. Computers with a wide
range of speeds may be available and typically this makes no difference
to distributed processing tasks. Work is parcelled out in blocks; the
slave computer may take minutes or hours. When the work is returned
to the controlling computer, an new block is normally sent to the slave.
If no results are returned to the controlling computer after some
extended time period, the work is assigned to another slave. Thus the amount of computing
power available for password cracking continually rises but the
amount available to a single cracker or group of crackers may
vary by several orders of magnitude at any specific point in time.
A variety of cracking tools are now available that take full advantage of
multi core computers and that are also network ready. Both Hashcat programs
and John the Ripper (all free) are network ready. Few tasks are better suited
to distributed network processing than password cracking. It doesn't matter
whether these are computers left on overnight in a business that only works in
the day, or a college computer lab, or a network of dozens to hundreds or more
computers previously compromised by a cracker. Even if someone is working on a
computer that is working on cracking passwords, the chances are good they will
never notice that activity. Three CPU intensive processes can be running on
my six core AMD tower, and I would never notice that anything unusual was
going on, if I did not
routinely check performance monitors that record what each core is doing,
and log CPU levels continuously with custom tools I've developed.
There is an
academic
project working on cracking a 72-bit encrypted key. This project uses
a large network of volunteer computers. It is currently running at more
than 7,500 times the speed of my single fast desktop (75,000,000 CPS).
Twenty months ago they were 30,000 times the speed of a single desktop
(then 25,000,000 CPS). Based on Jan. 14, 2014's number of 574 billion keys per second
versus their overal history of 415 billion keys per second (going back to
2004), I was going to say they are obviously not keeping up with technology
advances, but their keyrate history shows they have actually dropped by
about a third since 20 months ago. While the owners
of the computers in this project have chosen to install client software
that lets their idle CPU cycles be used by this project, there is no
reason anyone who can hack into a home or business computer could not install
comparable software for their cracking projects. These clients are desinged
to be unobtrusive. As soon as the user starts to do something they either
go idle, or scale back so as not to interfere with what the user wants to
do on their computer.
The platform that has contributed by far the most CPU power to the above
academic project are Stream enabled GPUs on Windows systems. The first
Windows computer using a Stream compliant video card joined the project
on July 19, 2009, and in less than 4.5 years, in a decade plus project,
have contributed almost 61% of the work. In five more months, Linux PCs
with Stream compliant video cards have contributed only 6% of the work
done by Stream enabled Windows PCs.
There is no reason to think the Linux PCs should be any slower than a
similar Windows PC. In the oclHashcat comparison, the one Windows PC was
only somewhat faster than 2 Linux PCs and much slower than two other Linux PCs;
most if not all of this difference is likely to be due to the GPU processor
installed on the two very fast PCs. Linux users tend to be more technical
than Windows users, so there is some reason to suspect there might be
more support for a project like this in the Linux community than among
Windows users. The reasonable conclusion is that Windows PCs with Stream
video cards are both fast and not uncommon.
oclHashcat can work with up to 128 GPUs.
We saw a gain of nearly 2000 times with the NTLM hash, so 6 similary
configured computers would give more than the 10,000 times estimate
for my fast cracking network. If 16 such computers (16 x 8 = 128) could
be found (compromised), that works out to 2,786 billion CPS or 3.7 times
the speed of my fast cracking network. It would likely be a challenge to
find and compromise such a perfectly suited collection of computers.
Organized Crime
Fourth, and perhaps most important, hacking or cracking has changed from a
hobby like activity persued for intellecutal satisfaction or reputation in
certain "communities" to a mainstream criminal activity. With the move of much
commerce to the Internet, criminals were bound to follow. Organized crime can
spend as much on targeting a large financial or retail institution as big business can
spend on computer security. Start with a core of several of several GPU
enabled computers and extend that to network hacked systems.
Why not employ several reasonably skilled crackers
to do nothing but break into home and business computers to assemble a network
of slave computers to perform any computational task required? It's a lot cheaper
to steal CPU cycles than to buy the equipment to provide comparable performance.
We can only guess at how
much computing resources a criminal organization may be willing or able to
assemble. One public network working on a similar problem with
a capacity close to my fast cracking network has already been discussed.
There is nothing technological to stop
an organization with large resources from going up another order of
magnitude or more. An article on CNN
Money stated '"If you think about the money that organized crime has,
if they throw out $100,000 to attack you, it's hard for a corporation to
fight against that," said Dave Aitel, president of security firm Immunity
Inc. and a former computer scientist at the National Security Agency.'
What a criminal enterprise may do will depend on their estimate of
costs versus payoff. In doing some reading on organized crime computer
crime, I was almost ready to dismiss the relevance of financial accounts and
passwords, when I read that that on May 10, 2011, "about $2.7 million was
stolen from about 3,400
accounts" as reported by CNN.com. No specifics were given in this
article. To date most attacks on both retail and financial institutions
have gone directly for the customer data containing credit and debit
card information. Most have involved using the stolen data to manufacture
fraudulent credit and debit cards and then hitting thousands of ATM machines
at the same time over wide areas in Eastern Europe. As soon as criminals figure
out a way to make serious money out of direct access to bank and brokerage
accounts, I would expect them to target the password files that are the keys
to accessing these accounts
Cracking Tool
Another factor in cracking speed is the password craking tool itself.
In March of 2012, Martijn Sprengers and Lejla Batina gave a presentation
on "Speeding up GPU-based password cracking." They used a PC with an
Nvidia GTX 295, a GPU that is older and slower than those used by
oclHashcat, but still widely available. One vendor sells 3 variations
ranging from $80 to $275. They provided four speed speed comparisons of
software cracking the widely used MD5 hash. The first was John the Ripper,
arguablely the best known password cracking tool, but is not yet able to
use a GPU. It performs between 2,500 and 5,000 CPS. Sprengers and Batina's
software, labeled as "Our CPU implementation," without a GPU ran at about
25,000 CPS. oclHashcat ran at 720,000 CPS. Their highly optimized version
labeld "Our GPU implementation" ran at 875,000 CPS. In the same PC we
see two hardware configurations with two products running without the
benefit the massively parallel GPU, and two that do use it. The fastest
implementation is between 175 and 350 times faster than the slowest.
Normally the cracking tool recognizes the hashing
algorithm from the resulting hash. For systems that allow the administrator a
choice of encryption methods or various loop counts, the cracking
tool must correctly match these. The first few
characters of many hashes are a code that identifies the hash scheme,
includes the salt when used, and may identify the loop count.
If for any reason the cracking tool uses an algorithm
that does not exactly match that used to create the password hashes, it will
never find any passwords, regardless of the size of the dictionary
and the number of transformations attempted.
Hashing Algorithm
Another factor is the algorithm used to encrypt the password.
Generally this is set by the operating system but some such as
Linux and OpenBSD allow the administrator to select from
different types. Over time as computers have gotten faster
new hashing algorithms have become slower to offset the increase
in computer power. The
standard UNIX encryption method has been changed to make it
slower more than once. On the other hand, some algorithms have
multiple implementations and those cracking passwords have
created variants that produce the same results but run as much as
100 times faster than the version that originally encrypts the
password2. Newer
algorithms attempt to find a logic not likely to have a fast
implementation.
The Hashcat password recovery software project has published cracking
times for a number of different password hashing algorithms in use
in 2014. On roughly comparable hardware, of those algorithms for
which Hashcat has published numbers there is a spread of about 5
million times from the slowest algorithm on the slowest PC to the fastest
algorithm on the fastest PC. Here slow is
better for the password owner and fast is better for the cracker.
On the same PC, the spread is somewhat over 100,000 times from the
slowest to fastest algorithm. Each PC setup interacts differently with
each algorithm. While some PCs are generally faster than others, in one
case PC3 is almost twice as fast as PC4 on one algorithm, but PC4 is about
1.5 times faster than PC3 on a different algoritm.
Hash Iterations
Since the early 2000's there has been a new development, limited
mostly to some Unix variants, and not yet widely used, which
has the potential to shift password security back in favor of those
trying to protect the passwords. This is system administrator control
of the number of hashing iterations performed, often called password
loops, rounds, or cycles control. These are normally available only
with newer and already relatively slow hashing algorithms.
Changing the encryption method
and how many times it is applied, can greatly increase the time
it takes to compute a password hash. Generally, the longer it
takes to compute the hash when the password is created, or
when a user logs onto the system, the
longer it will take when trying to crack the password. Though older
hashing algorithms have had fast implementations used for cracking,
newer hashing algorithms try to make it a design goal to make
alternative, fast implementations difficult to create. Thus the
amount of time it takes to create the original hash when a password
is created or changed, or the authentication time when a user logs
onto a system is an indicator of how long a cracking cycle will take.
Loging into a local text terminal or switching users (su) in text
mode have very little overhead that obscures how long the hashing
process takes. In practice these normally occur too quickly for one
to be aware of the passing time. On many Unix and Unix like systems the
now
obsolete md5crypt hashing algorithms remains the default. Many of
these systems offer newer stronger algorithms. SHA256 and SHA512 are
common; SHA512 should be preferred. It's clearly stronger than SHA256,
and has been available over 5 years with no flaws found. Both normally
offer rounds control as a system adminstrator option.
Based on the performance numbers supplied by
oclHascat
(near page bottom)
SHA512 appears on average about 60 times stronger than MD5.
Hashcat identifies SHA-512, SHA512(Unix), and sha512($salt.$pass)
as different algorithms. All Unix and Unix like systems have used a
($salt.$pass) approach with all algorithms since the 1970s. The
use of a salt does not affect encryption time, but it ensures that
the same password is very unlikely to have the same hash for
different users or on different systems. By not qualifying SHA512
in their performance table, I believe the times are for a single
unsalted cycle as it might be used on a web site or in another
application password and not as SHA512 is used in Unix.
On the Linux distributions with which I'm familiar, 5000 rounds is the
default for SHA512, and this can usually be changed by a system admin.
MD5, as it is used to hash passwords on Unix systems is hard coded to
1000 rounds. Thus by switching to SHA512 you automatically get passwords
300 times stronger. Current passwords are not affected. A password must
be changed for the new hashing scheme to take effect, but on average,
a password of the same length and characater diversity will take 300
times longer to crack.
On a system with an obsolete dual core CPU, the 5000 rounds is imperceptible
when su'ing in a text window. I configured a million rounds and this took
a little over a second to su. Combined, these yield a 60,000 times password
hash strength increase
over the normal Linux default. This is for changing or adding a couple of
lines in a couple configurations files and imposing a minor user inconvenience.
Unfortunately, where these changes need to be made is poorly documented
on the systems I'm familiar with.
With the last couple changes in the cracking time tables, I've started
arguing for 12 character and longer passwords. With system adjustments
like these, I think 9 or 10 characters may be fine. On a contemporary
desktop, I think 10 million rounds might take a little over a second,
though I do not know if password hashing will take full advantage of
multi core CPUs.
The poor documentation, plus searches of multiple Linux fourms and
mailing list archives shows this topic has never been discussed in
these locations before I raised it. The near total lack of response shows
almost no one who has access to this powerful tool knows how to use it
or understands its importatance. SHA256 and SHA512 are available on other
Unix variants besides Linux. From what I've read, it seems that iteration
control is a common part of these hashing algorithms. I very much doubt
the situation is significantly different on non Linux systems.
A second may sound like a lot, and an annoyance to users, as it is
clearly perceptible. In fact though, nearly every day spent on a
computer involves many waits longer than a second, and few if any
of these waits have any beneficial results. Compare this to the time
it takes someone who only uses strong passwords and never reuses
them, but needs to write them down, to retrieve and return a slip of
paper from a purse or wallet, a safe or strong locked file cabinet,
or a good hiding place (if such exists); in this context a second
is minor. With dozens to hundreds of passwords, good 9 or 10
character passwords will still need to be written down. Those
that are used regularly should, however, be learned fairly quickly
and not need to be referrenced.
Salts
There is one other factor that greatly affects cracking speed, or to be more
accurate whether or not there is a need to even bother with cracking some
passwords. This is called a salt. It is a random piece of information that
is added to the password to prevent two passwords that are the same from
having the same hash. In many current Unix and Unix like systems the salt
consitsts of 8 random characters from a 64 character set. Password is one of
the most common passwords. Without salts, every time password is used as a
password on systems that do not use salts, all the hashes are
the same. Using salts is like turning an eight character password into a
16 character password. Some examples will help:
passwordzjJ/GP6v , passwordF2wW.oXU , passwordClq7K25A .
These look just like the passwords on many modern Unix systems would look
just before being passed to the hashing function. They are obviously quite
different and would create very different hashes. But two very similar salts,
1Vk8/ue0   and   2Vk8/ue0   , when combined with an
otherwise identical passwords would also create very different hashes.
Change any one character, passed to hashing function, and you will get a
very different hash. The salt is normally stored as plaintext with the
resulting hash and as available to any cracker as it is to the system.
This is not a problem. The salt must be availble to the system if the
passwords are to be useable. The only purpose of the salt is to ensure
that the same passwords get different hashes. Once when disk space was
expensive and computers slow, salts typically only had 4096 possibilities;
this was good enough to largely ensure that the same password did not have
the same hash on the same computer or even in the same medium size company.
The 8 character salts in wide use today have 218 trillion possibilities.
There is a modest chance that even a really popular password like password
has never gotten the same hash anywhere in the world on systems that use
this method. Even if there are some duplicates, the chance of any one
cracker ever comming across them is remote.
Ensuring that for practical purposes, every password has a unique hash
prevents what are known as precomputation attacks and rainbow table attacks,
which are a very specific and widely used form of precomputation attack.
An excellent example of the problem of not using salts is the October 2013
compromise of Adobe and the theft of a file containing nearly 153 million
user accounts with password hashes. Also, nearly a third had password hints,
entered by the users, to help them remember their password (a very bad idea).
Because of the size of this file, and the tendency of most people to choose
from a relatively small set of passwords, it was a assured that there would
be massive duplication of passwords in this file. Graham Clueley provided
an analysis of the
top 50 passwords in this list.
With few exceptions nearly all were familiar. Because this was one huge list
from a single site, it did show some things that composite lists could not
show. High in a list of site specific lists are likely to be several passwords
that relate to the password list origin: company name, products, school name,
etc. In this list were adobe123, photoshop, adobe1, and macromedia between
4 and 16. This was a client list; in an employee or student list, the number
of passwords related to the institution would likely be higher.
In the Adobe list, because there were no salts, as soon as one password was
figured out, every other matching password was known immediately. Because
there were no salts, the list was huge, and also contained hints, the best
approach to get many passwords quickly is to sort the list on hashes (these are
large random looking strings of ordinary typeable characters). A review of many
related hints together often gave the password away with almost no effort.
The most common password was 123456 . If this was run
through a hashing algorithm, and the hash matched the most common hash,
the password to over 1,900,000 accounts would be known. Number 2 gave up over
446,000 and 3 nearly 346,000. Four and 5 over 200,000 each. Numbers 41
through 50, over 23,000 to over 21,000 each respectivly.
If I were a member of Congress, I'd introduce a law that every company
doing business on the Internet, handling patient, customer, or client
records on systems accessible via the Internet, or selling operating
systems across state lines, be required to use salts (or a newer stronger
technology) when storing passwords to assure hash uniqueness. Generally I do not
think Congress should get directly involved with technology decisions, but
when companies expose patient, customer and client data to attacks accross
state and international boundries, and there is a huge upside with no
practical downside, an exception is warranted.
Microsoft is the biggest company to willfully refuse to use salts where
they are needed, with their Windows system passwords. Since the
introduction of Windows NT in 1993 all subsequent
systems have used the same weak password storage, without salts. As a result,
every Windows system from NT, to 2000, and XP through Windows 8.1, and all
server variants, store the same password, with the same hash. The only
exceptions are systems using Active Directory with Kerberos and domain
controllers. Even on computers that authenticate network services with Active
Directory, the password for the initial local logon is stored with the same
saltless method, used on most other Windows systems. I believe the only
reason for this stunningly bad technical decision, was that Bill Gates,
who was Microsoft's undisputed leader at the time, and involved in many
technical decisions, viewed NT as a "UNIX killer" and made many decisions
because they made NT look less like UNIX. The wide spread use of
rainbow tables, focused mostly on Windows systems, is a development
in response to the fact Windows systems, now spanning more than 20 years,
can all be attacked with the same method, once the password hashes are
obtained.
If a cracker has been attacking windows systems for any length of time
he may have a significant collection of Windows hashes, or simply have
run the 10,000 most common passwords through the Windows hashing
algorithm. If I had Windows password hashes, and wanted the the passwords,
instead of starting with a cracking process, I think I'd simply sort
the Widows password file on the hashes, and use a small custom program
that took this input and compared it to an already sorted list of
previously cracked (or hashed) passwords. Someone should explain to me why
this is less eficient than Rainbow tables, if it is in fact less efficient.
Each match, or in a large password file, group of matches simply gets the
password from the cracked file and is removed from the list that still
needs to be cracked.
Tables of Times to Crack Passwords
The first table below is calculated by assuming 75,000,000 hashing
operations per second. Bassed on numbers provided by
Hashcat this is believed to be a
reasonable figure for a desktop computer, not using a GPU.
The second is calculated at 10,000 times that
rate or 750 billion cracks per second, which I believe to be a
plausible figure for an organized criminal activity, using a cracking network.
Password lengths from 3 to 18 are shown. The numbers
at the top, 26 - 95, indicate the number of characters from which
the passwords are formed. 26 is the number of lower case
letters, 36 is letters and digits, 52 is mixed case letters, 69 is
single case letters with digits, symbols and punctuation, and 95
is all the displayable ASCII characters including mixed case
letters. The 69 and 95 numbers include the space which is not
a legal password character on many systems. But then there are
a number of idiotic systems that do not allow any punctuation or
symbols in their passwords. This includes at least one major bank
which also limits passwords to 8 alphanumeric characters;
a major online brokerage service limits passwords to aplphanumeric.
Why do some of the institutions with the most sensitive data have the
worst password policies?
Please remember the extreme variations
depending on the hashing algorithm, the attacking computer or computers,
and other factors. These are plausible guesses that will fit some
combinaions of many factors. For small files of uncracked passwords
which are NOT salted, such as all Windows systems and many web sites,
these numbers apply to the entire file. The time is likely to go up only
slightly as the the number of passwords to be cracked increases. For
systems which are properly salted, which include nearly all Unix like
systems, these times apply to each password in the file. For example, when processing a
file from a small business with 120 passwords, each second listed below
becomes one minute (on average individual passwords will be cracked in
half the listed times). For a password file of moderate size file with 10,800
records, each second becomes 1.5 hours. For a large file with a million
passwords, each second becomes 5.79 days. In practice most crackers will
start with dictionary attacks. With typical password files, most accounts
will have really bad passwords. If the dictionaries start with ones based
on good common password lists, most passwords will be cracked very
quickly. After dictionary attacks are done, if the crackers proceed to
brute force, times like these will apply to the remaining uncracked
accounts. The first table is based on
a single multi core CPU computer and MD5. With GPU computers the times
will be much less, unless stronger algorithms are used. If faced with
SHA512, bcrypt, or scrypt, these are much slower and highly iterated
and do not optimize well on current GPUs.
If you have a system where you can control hash iterations, you need
to find the algorithm used on your system in the
oclHashcat or other
online cracking benchmarks. This gives you a rough idea of what you
may face. You should assume that anyone who can hack into your system
has multiple GPU systems; it's safest to assume the fast cracking
network or faster. If you are adding iterations, divide the number
you are using by the system default. On at least current Red Hat and Debian
based Linux systems, the default for SHA family algorithms is 5000
rounds. On older bcrypt systems, the defaults were 2^6 or 64 iterations
for ordinary users and 2^8 or 256 iterations for root. If you are
willing to wait a very noticable 1 to 2 seconds each time you login or
su, you will have the most secure passwords your system supports.
The times shown are the times to
process the entire set of passwords thus, the average time to crack
a specific password would be one half the listed times. Some passwords will fall
in the first few minutes or even seconds of a run that takes days or weeks
and others near the end of this same run. A select few will never be cracked.
75 Million CPS - 1 quick desktop
26 36 52
3 0.0002 seconds 0.0006 seconds 0.002 seconds
4 0.006 seconds 0.022 seconds 0.097 seconds
5 0.158 seconds 0.806 seconds 5.07 seconds
6 4.12 seconds 29.0 seconds 4.39 minutes
7 1.78 minutes 17.4 minutes 3.81 hours
8 46.4 minutes 10.4 hours 8.25 days
9 20.1 hours 15.7 days 1.18 years
10 21.8 days 1.55 years 61.1 years
11 1.55 years 55.6 years 3.18 millennia
12 40.3 years 2.00 millennia 165 millennia
13 1.05 millennia 72.1 millennia 8,594 millennia
14 27.3 millennia 2,596 millennia 446,868 millennia
15 709 millennia 93,469 millennia 1.66 universes
16 18,438 millennia 3.36e+6 millennia 86.3 universes
17 479,379 millennia 8.65 universes 4,488 universes
18 1.25e+7 millennia 311 universes 233,380 universes
69 95
3 0.004 seconds 0.011 seconds
4 0.302 seconds 1.09 seconds
5 20.9 seconds 1.72 minutes
6 24.0 minutes 2.72 hours
7 1.15 days 10.8 days
8 2.64 months 2.80 years
9 15.0 years 2.66 centuries
10 1.03 millennia 25.3 millennia
11 71.4 millennia 2,405 millennia
12 4,924 millennia 228,463 millennia
13 339,758 millennia 1.55 universes
14 1.67 universes 147 universes
15 116 universes 13,991 universes
16 7,972 universes 1.33e+6 universes
17 550,096 universes 1.26e+8 universes
18 3.80e+7 universes 1.20e+10 universes
750 Billion CPS - A fast network of computers
26 36 52
3 0.000000 seconds 0.000000 seconds 0.000000 seconds
4 0.000001 seconds 0.000002 seconds 0.000010 seconds
5 0.00002 seconds 0.00008 seconds 0.0005 seconds
6 0.0004 seconds 0.003 seconds 0.026 seconds
7 0.011 seconds 0.104 seconds 1.37 seconds
8 0.278 seconds 3.76 seconds 1.19 minutes
9 7.24 seconds 2.26 minutes 1.03 hours
10 3.14 minutes 1.35 hours 2.23 days
11 1.36 hours 2.03 days 3.87 months
12 1.47 days 2.44 months 16.5 years
13 1.28 months 7.21 years 8.59 centuries
14 2.73 years 2.60 centuries 44.7 millennia
15 70.9 years 9.35 millennia 2,324 millennia
16 1.84 millennia 336 millennia 120,833 millennia
17 47.9 millennia 12,114 millennia 6.28e+6 millennia
18 1,246 millennia 436,091 millennia 23.3 universes
69 95
3 0.000000 seconds 0.000001 seconds
4 0.00003 seconds 0.0001 seconds
5 0.002 seconds 0.010 seconds
6 0.144 seconds 0.980 seconds
7 9.93 seconds 1.55 minutes
8 11.4 minutes 2.46 hours
9 13.1 hours 9.73 days
10 1.26 months 2.53 years
11 7.14 years 2.40 centuries
12 4.92 centuries 22.8 millennia
13 34.0 millennia 2,170 millennia
14 2,344 millennia 206,188 millennia
15 161,759 millennia 1.40 universes
16 1.12e+7 millennia 133 universes
17 55.0 universes 12,627 universes
18 3,796 universes 1.20e+6 universes
I'm using a universe as 14 billion years.
*
If you don't know what 5.88e+7 means
If you think I got the cracks per second wrong, or would like to see the effect of different
computer speeds, password lengths, or character set sizes try the
Crack Time Calculator.
If you use the second table, then 10 character passwords using the
entire character set may appear safe, as it will take about 2.5
years to work through all possible passwords. Remember that is an
average of 1.25 years but even with brute force attacks some
passwords are likely to be found the first day. Remember the
spread for slow computer, slow algorithm to fast computer to fast
algorithm was 5,000,000. There is no way that I'm comfortable with
a couple years for the entire set. Few people have any idea how
their passwords are stored and recent events show even large
software companies continue to make bad choices on password storage.
I haven't used a password shorter than 12 characters in the past
year on any account that matters and most are 14 or longer. The
times in the tables, also assume that you have no weakness in your password that
would allow any kind of dictionary attack to succeed. They are also
based on estimates of something unknowable, what opponents your
passwords may face, and what skills and recources they may posses.
11 characters adds some margin of safety but is another character that much
harder? 12 characters from the full keyboard is almost 10,000 times
stronger than 10. 12 should put your password out of the reach of
almost anyone except a very few who have both great resources and
great determination. You need to be someone special or have something
special to warant an attempt to crack a strong 12 character password.
Of course before it's cracked, anyone attempting to crack it cannot
know it's a 12 character password, and if it is strong (not flawed
by say a reversed rotated dictionary word) the would be cracker probably
will never know what the password is.
In 2001 I suggested 8 character passwords. Today, such passwords
are simply inadequate for anything but throwaway accounts.
I extended the lengths of passwords covered by the tables. This
was primarily to show what happens with all lower case letters.
A well chosen 16.5 character, all lower case password is as
strong as a good 12 character password using mixed case, digits,
symbols and punctuation. That's
a mathematical fact. It may not seem right but it is. Of course you
cannot enter half a charcter and 16 letters is clearly weaker
than a 12 character password from the 95 character set, but probably
fine. I
discuss strong lower case passwords
on another page. This is closely related to the
Words Only option in the Password Generator.
15 to 18 characters covers long passwords and short pass
phrases. Short pass
phrases may include capital letters, numbers or punctuation.
Any of these in arbitrary and unpredictable positions substantially
increases the strength of a long string of lower case letters.
With pass phrases, you need to avoid obvious and common
expressions just as you need to avoid dictionary words in
short passwords.
Depending on the password and the brute force character order, some
passwords might fall quickly. For example if passwords were
generated in the order of ASCII collating sequence, the poor
password !!!111Aa might be found rather quickly, as the exclamation
mark is the first visible typeable character in the ASCII sequence.
On the other hand, the superficially similar !!!!1111AAAAaaaa
could not be cracked by any known method. That's 16 characters.
It violates a number of common do not's regarding passwords.
It uses only 2 keyboard keys, each shifted then unshifted 4 times.
My password evaluator, with its original default settings,
finds 4 distinct error conditions and
would find more if it looked for more character repeats
after finding the first. But the simple fact is, that until
I displayed it publicly as a candidate for a strong password,
no known cracking method could find it.
Cracking is all or nothing proposition; you get
nothing for missing by one character. It would not be hard for a
cracker to program all combinations of 2 to 6 character repeats in
every possible combination between 6 and 20 characters. There are
only 95 typeable characters and 5 different length repeats for each
for 475 specific groupings. Instead of trying to figure out every
possible way to fill each length, there is a much simpler way. I
believe most would agree that 8, two character repeats to make a
16 character password, would not be an easy password to remember
or type. Instead, I suggest a constant four groups, of 2 to 6
character repeats. Then a familiar formula applies. This is the
same as a 475 "character set" for a password 4 characters long,
or 475^4 = about 51 billion, a fairly small number, or about
11 minutes on a fast desktop with no GPU.
I said no known method because it is a well known that crackers
try to avoid any low yield dictionaries.
I doubt anyone has ever programmed a custom cracking dictionary which would
have included this password, because there is no
evidence these are common passwords, except as some lower case letters
and some digits in short passwords (up to 8 characters). Pure brute force is not
feasible at 16 characters and a 95 character set, and odd looking passwords
like I used are very low yield. A few crackers may have taken dictionary
attacks up to 16 characters using common long words and repeated short words
with some common transformations, just to see if anything turns up.
Sequences are actually somewhat more commonly used in passwords than
repeats but there are many more of these, especially
as there are ASCII (alphabet and digits) and keyboard sequences and
forward and reverse. Doing all of these plus the repeats would be a
large dictionary, but not something that today's computers would not
easily handle. At anything over 10 characters the yield is still going
to be too low in 2014. If big websites keep getting hacked, websites
may start forcing longer passwords with varied character sets, and if
so, maybe in several years there will be some evidence of crackers trying
approaches like I just covered.
What I said in the preceeding paragraphs is true of today's cracking
tools, but several of these tools have been designed to accept externally
programmed dictionaries. The tools themselves don't yet do these things
but they can accept custom programmed dictionaries. It's also true that
any password that has a structure that can be described with an algorithm
can be programmed, and such passwords are small subset of all passwords
of similar length and composed of randomly selected characters from the same
character set as the password described by the algorithm, and the longer
the password, the smaller the subset.
There are no dictionary words but 4 ones and 4 lower case a's are
both common in paswords. Four exclamation marks certainly are not
common; this group
has never appeared in any common password list. To the best of my
knowledge no one has ever before seen that exact combinations of
characters. Even rainbow tables (a kind of super sophisticated
dictionary attack) only go to 14 characters. The only problem
with the sample password is that it has NOW been publicly suggested as an example of
a strong password. Why is that a problem? Because when an example
of a way to make a strong password is shown, sooner or later,someone
is likely to copy it and use it exactly as it appeared. There have
probably only been a few thousand examples of strong passwords
in print and on the web. Smart crackers are likely to take each
of these they see, and add them to one of their dictionaries
to be run with no transformations.
Such a list would be very low yield compared to a common password
list, but it should be a LOT better than brute force, even for 8 or
10 character passwords, and especially compared to 16 random characters.
Someone my ask, what about programmed dictionaries, which I discuss
later. For what? To get a more
plausible grouping, we can do all 2 to 6 character sequences and
repeats in groups of 4. The ASCII puctuation and symbol sequences,
that hardly anyone knows, will be omitted as will the digits which
repeat the keyboard, leaving only the upper and lower case alphabets.
The keyboard sequences, which anyone can get, just by looking at the
keyboard, will include forward and reverse as well as wrap from one
line to the next. To get the weak 8 character password I started
with, one set of 95 single characters will be included as both "repeats"
and "sequences". This yields 1802 character groups for 1802^4
or about 10.5 trillion test passwords.
At an average size of 10 characters, plus line terminators, this is over
one hundred terabytes, an awkward number for any but large
organizations. It also turns out that desktops cannot create dictionaries
nearly as fast as as even fast but non GPU enabled PCs can calcualte hashes.
It also seems that both pure dictionary attacks (one word list without
transformations) and rule based attacks (a word list with a series of rules
describing word variations) do not lend themselves well to massively
parallel implementations (GPUs).
In this specific case, there is an answer. It seems that GPU enabled PCs
do not process a single dictionary efficiently but do combine two dictionaries,
in all possible combinations efficiently. So instead of creating the whole
dictionary, the dictionary creating PC creates one side of or one half of the
dictionary. In this case it is 1802^2 = or 3.2 million test passwords, a number
very easilly done on (a few seconds) and stored on (about 33MB) a PC.
Then the same file (or if necessary,
the file and a copy with a different name) is fed as two files to a GPU
enabled PC in a combination attack. Every entry of the "first" dictionary
is combined with every entry of the "second" dictionary. 1802^2 * 1802^2
= 1802^4, the exact result we wanted. This should take about 2 minutes
depending on the algorithm used for hashing and GPU used.
Let's complicate the situation. Here are a couple more long
but "simple" passwords. ertyu789@#$%DFGHJ (17 characters, all
keyboard sequences, and defghz{|}~345IJKL (all ASCII sequences, which
except for the "z{|}~" are pretty obvious). What about
[]\asd;7777777;gHIJK;3456 (25 characters: a keyboard
sequence wrapping from one line to the next, seven 7's, an
alphabetic sequence with odd capitalization, and a numeric
sequence, all separated by semi-colons)
With this last one the repeat and sequence length goes to 7, any
repeat or sequence 2 characters or longer can have a keyboard shift
on either or both ends, and any of 33 symbol separators may appear
in 3 locations; this is
2127^7 * (2032*4) * 33^3 = 5.75e+31.
The square root of this gives us the size of "half" the dictionary or
7.585e+15 test passwords. This would require well over 75,850 terabytes
to store. If it were possible to get the half dictionaries to the fast
cracking network, it would take 173 universes (14 billion years each)
to process the combinations. Not feasible in the foreseeable future.
Length makes what may at first look like bad passwords uncrackeable by
any foreseeable technology, but some systems would reject them because
they contain more than 2 repeat or sequence character groups.
Anyone who might seriously consider trying to get such passwords
would drop the idea as soon as they did the necessary calculations.
After the calculations are done, no one can reasoanbly question the
strength of such passwords. They may not be good passwords despite
their strength; if you use several along such lines, how will you
remember which goes with which account? These are only a little
more memorable than truly random passwords.
Each of these specific passwords is now poor because they have
been publicly displayed. I believe passwords of this type, and those that
contain 3 to 5 relatively short, but unrelated words, especially if some
are only 3 words along the lines of word1.longworD.word3, where longword
is 7 to 10 characters, enormously increasing the potential vocabulary
that needs to be included, represent a viable way to create strong
passwords, for the foreseeable future. I do however recommend using
a password generator, such as the one on this site will soon be, which
can pick pseudo random starts, lengths, and ends to these character
sequences. If you do not use a generator, then at least make a point
of not starting letter sequences with abc, number sequences with
123, and keyboard sequences with qwe. Historically people who have
used these kinds of sequences in passwords have overwhelmingly
started them with these specific characters.
I very much doubt any cracker, in the next decade or so, will try to
cover all possible sequence and repeat patterns going up to 25 characters.
I do however think, that if there is any indication that long passwords
or pass phrases are coming into common use, the crackers will at least
try to cover the most trivial and obvious approaches to long passwords.
This would include all single character passwords from 2 to 30 characters
and abcdefghijklmnopqrstuvwxyz and ABCDEFGHIJKLMNOPQRSTUVWXYZ , and
likely all subsets of these. It might include wraparound versions
of the alphabet such as defghijklmnopqurstuvwxyzabc and maybe all
single keyboard and ASCII sequences up to 15 to 20 characters. It
will not likely include such variations as defgh1.klMnop.rstuvW.yz@bc .
This last, is not likely to be very memorable, at least not if you
have several constructed on similar lines.
Brute Force, Dictionary Comparison
The time to process a cracking dictionary is determined
by the total number of passwords to be tried,
which is a product of the number of words in the dictionary,
times the number of transformations per word, divided by
the rate it takes to hash passwords. Complex rule sets,
may generate thousands
of variations per word in the dictionary. On today's
computers, small dictionaries (less than 100,000 words) with a
few transformations will complete in a few seconds. The
total number of passwords with large dictionaries and many
transformations or huge dictionaries will be huge and the
processing time correspondingly large. The yield per each
word and variation will be very low, but should be high compared
to a brute force attack with the same number of encryptions.
As brute force is the only alternative to dictionary based password
cracking it's worth taking a close look the table above. Look at how
long it should take to crack eight character passwords drawing from
the 95 typeable characters. One simple statement should put this in
perspective. Not including Windows systems, that have a seriously flawed
password storage method
It is highly unlikely that any cracker has ever gotten even a
single password, eight characters or longer, randomly created from
the entire 95 printable ASCII character set.
Wrong!
This was written in 2001 and never changed. Then I listed the cracking time
for all 8 character passwords as just under 2 millennia. Multi core
processors were only in high end servers and network cracking tools were not
available. The academic project mentioned above, using a large network
of volunteer computers, has cracked stronger passwords. Things change
quickly in the computer world and 15 years is a long time. (The data I
used in 2001 was from the previous year.)
If someone is cracking passwords for real, it means they have the hash file
(the file of all passwords) for some computer or institution. While no one
might spend months or a year trying to get your password, if they have the
password file for online access to a major bank or brokerage service they
may have hundreds of thousands or millions of passwords to try to crack.
For a criminal organization, that would easily be worth months of computer time.
All weak passwords would be cracked as well as many that looked like good passwords.
If you use this bank or brokerage service and your password is
not mathematically strong, and entirely free of any
dictionary or related weaknesses, it will be one of those cracked.
Randomness does have it's surprises. If numbers are randomly
selected from a billion number sequence, there is a one in a
billion chance that the first number will be drawn on the first
try. Very unlikely but still possible. To have a 1% chance
of cracking a specific random, 8 character password from the
full character set takes about 20 years of computing, at
100,000 passwords per second. This was reasonable in 2001 when it was
written. Today, with one fast desktop, it would be less than a
month, or perhaps a few seconds on a capable network.
An obscure word in the Afrikaans language, mirrored and all
uppercased except the first letter is more likely to be used as a
password than any single random character sequence of similar
length. Further, where the single random sequence may not be
reliably found (depending on length) by existing technology, the Afrikaans
derived password surely can; it's simply a matter of the cracker
having and choosing to apply sufficient resources. As a practical
matter, it is unlikely that many crackers will bother with
unabridged dictionaries, and foreign language dictionaries,
especially obscure foreign languages, as the rewards will not likely
match the effort. Again, not necessarily true.
One of the well known password crackers today includes a multilingual unabridged
dictionary with 21 languages. Interestingly
Chinese (or Putonghua, a standardised form of the Mandarin), Hindi, Spanish and
Portugese are not included; this leaves out the two most populous countries
in the world and all of Central and South America. Arabic and Farsi are
also missing. Still it's a good
indication where cracking tools are going. Afrikaans is included, as
were nearly all advanced industrialized countries including Japan.
Any word and all the mechanical transformations that can be
described to change that word into something else is a subset of
all possible variations of the same characters. As the length
of the word increases, the standard transformations become an
ever smaller subset of the possible variations. For a word of
meaningful length, say more than 5 characters, the word and its
transformations is an infinitesimal subset of all possible
combinations of the same number of all characters. In other
words, the longer the passwords to be cracked, the larger the
advantage of a dictionary based attack will be compared to a
brute force attack. Here "dictionary based attack" is understood
to include custom programmed dictionaries as described in
a subsequent page
in this section.
I discussed programmed dictionaries in 2001, eleven years before I
ever saw a reference to such a thing in conjunction with a password
cracking tool discussed anywhere else. Now the same tool that has the
multilingual dictionary, has a programed dictionary that creates passwords
matching those created by a popular password generator. The programmed dictionary
feeds the generated passwords directly to the cracking tool so that
they do not need to be stored to disk. It's easy to describe programmed
dictionaries that have so many possible passwords, no institution on Earth
has enough disk space to store them. Huge dictionaries must be fed
directly to the cracking tool without using disk space. I'm beginning
to believe that when disk space for a dictionary really begins to be a
problem, that the processing power to create the dictionary, and
managing the pieces of the dictionary on a network are also likely to
be problematic. The available tools may not have these abilities.
Can conventional computers create dictionaries fast enough to keep up
with the capablities of GPU enabled cracking computers? Probably not.
Can GPU enabled computers create the programmed dictionaries? It seems
likely. One of the attack modes of GPU enabled computers is the
combination of two dictionaries fed to them. Creating programmed
dictionaries is typically no more than assembling sets of components,
words, character repeats and sequences, etc., in all possible combinations.
It seems highly likely that the combination of components of programmed
dictionaries, should be able to take advantage of massively parallel
achitecture, whether these come from discreet disk files or internally
generated arrays and other data structures. It's very possible that
access to the source code would be required to combine and save
preliminary dictionaries, without creating hashes.
In 2007 I could find no evidence that any cracking tools were using
programmed dictionaries, but it is now clear, that every method of
generating plausible passwords, is comming into use with contemporary cracking tools.
Available computing power has increased to the point that these CPU
intensive processes are now becoming practical. Though I cannot predict
how long it will be, it seems possible passwords as we have known them, may have
a finite lifespan, in which they must be replaced by a more secure technology.
In 2012, typically over 90% of the passwords on compromised systems are
cracked. Only a small minority use passwords that are strong enough to
resist today's cracking tools. Length is the easiest way to get strong
passwords. Theoretically length with arbitrary (but not random) patterns
should be able to stay ahead of any technology. Will many publicly
compromised systems get administrators and users to use strong passwords?
If history is any indicator the answer is no.
* Scientific Notation
Scientific notation may look odd to those not familiar with it,
but for very large numbers, it's easier to read than the conventional fixed
notation. For medium size numbers (millions to billions) it may not be
easier to read, as long as a comma is used every three places, but it is
shorter. I chose to use it for all numbers, one million and larger.
It's very appropriate because all the cracking times are estimates based on
assumptions, not the actual time that a specific operating system's
passwords would take to crack on a specific stand alone computer or a
network of known computers.
Like many things, scientific notation, is best explained with some specific
examples. 1.33e+6 is one and a third million. Scientific notation
always starts with a floating
point number between 1.00 and 9.99999... Because there is no need for precision
in my numbers, I limit them to three "significant figures." If 9.99999 stopped
with 6 digits that would be 6 significant figures. Sometimes more significant
figures are used but that is not relevant here. I assume the "e" stands for
exponent. The plus sign means a positive exponent; the decimal point, is
moved as many places to the right as the exponent indicates. Any space not
provided by the available significant digits is zero filled. (Negative
exponents are used for numbers smaller than 1.)
The number after the plus sign tells us how many places to move the decimal
point. If it's 6, it's for a number between one million and one just under
10 million. 7 is for 10 million to just under
a hundred million. 9 is for one billion to just under ten billion, and 11 for 100
billion to just under one trillion, 13 for 10 to just under 100 trillion.
Top of Page -
Site Map
Copyright © 2000 - 2014 by George Shaffer. This material may be
distributed only subject to the terms and conditions set forth in
http://GeodSoft.com/terms.htm
(or http://GeodSoft.com/cgi-bin/terms.pl).
These terms are subject to change. Distribution is subject to
the current terms, or at the choice of the distributor, those
in an earlier, digitally signed electronic copy of
http://GeodSoft.com/terms.htm (or cgi-bin/terms.pl) from the
time of the distribution. Distribution of substantively modified
versions of GeodSoft content is prohibited without the explicit written
permission of George Shaffer. Distribution of the work or derivatives
of the work, in whole or in part, for commercial purposes is prohibited
unless prior written permission is obtained from George Shaffer.
Distribution in accordance with these terms, for unrestricted and
uncompensated public access, non profit, or internal company use is
allowed.
|