## Tuesday, 8 September 2015

A lot of fuss has been made recently about the hackers who released all of the private information held by the company Ashley Madison, which provides a supposed intermediary service for would-be adulterers.  Private information pertaining to millions upon millions of users has been released into the public domain.

What does that mean, though?  If you are one of Ashley Madison’s customers you may be desperately wondering who knows what your name is, where you live, your credit card information - even, perhaps, intimate details of your sexual preferences - what are the prospects for that information also making its way into the public eye?  I thought I would talk a little bit about encryption, how it works … and how to crack it.

Password-based encryption systems work broadly on the basis of either encryptions or hashes.  The difference between the two is that encryption systems are two way functions, whereas hash systems are one-way functions.  With an encryption-based system for every output value there is only one possible input value that could give rise to it, whereas with a hash system every output value has an unmanageably large number of possible input values that could give rise to it.  A trivial, but quite inadequate, example of a hash system might be a function which returns 1 if the input is odd and 0 if it is even.  Clearly, given an output value of 1 or 0 there is no way to determine what the input value was, beyond narrowing it down to an odd or even number.

With an encryption system the designer is basically asserting that there is no known way to reverse the encryption.  The risk is that if such a reversal algorithm is ever discovered it instantly unlocks every password ever encrypted using that system.  By contrast, with a hash system the designer is asserting that reversal is fundamentally not possible.  But in this case the risk is that you can unlock the password by stumbling upon one of a colossal number of possible input values (of which the true password is just one).  Both methods have their advantages, and are widely used.  But note that, in most common parlance, the output of a password security algorithm - whether an encryption or a hashing function - is usually referred to as a ‘hash’.

Typically, in a security application, the input value is a password.  What we have in principle is a system where I can publish both the encryption/hash algorithm and the hash value itself, and nobody can use that information to work out what the password was which created that hash value.  Anybody can make a guess at the password and pass it through the hash algorithm, but unless the guess is correct the result will not match the hash value.  The key advantage is that the open-text password itself is never stored anywhere.  Just about every password-based authentication system today is based upon these principles.

So how do hackers set about cracking those passwords?  The reality is that there is only one way of doing it.  What you do is make a guess at the password, pass it through the hash algorithm, and compare the result to the open-text hash value.  If you guessed right, you’ve cracked it.  If not, you try again with a different guess at the password.  Simple, really.  How long do you think it would take before they guessed right?

What serious ‘professional’ hackers do is to compile lists of ‘known’ passwords.  These are combinations of known names, known places, common numbers (such as dates) and other common candidates.  Also, every time a hacker cracks or otherwise obtains a password, they will add it to a list of known passwords, where it can be used to crack similar passwords the owner may be using elsewhere.  Such lists are maintained in various dark corners of the internet.  The list might, for example, contain the word
FRED’.  People accessing these lists will use that to automatically derive variants such as fred, “fReD”, “FR3D”, “fred69”, and “DERF”.  Hackers using specially-configured computers will burn through these lists, passing each and every possible password through the hash algorithm until they find a match, at which point all of your personal information protected by that password is immediately at their fingertips.  However, such lists usually contain over 10 million passwords.

While this analysis may or may not give you pause for thought, it is based on a simple inconvenient truth.  How quickly it takes the attack to crack your password depends on how ‘secure’ your password is.  An ‘unsecure’ password will appear near the top of the list as one of the best guesses available.  It will be cracked pretty quickly.  A less secure password won’t get tried until later in the process and will take a lot longer to crack.  But a highly secure password is one that won’t actually get tried at all for the simple reason that it won’t even be on the list.  It won’t be cracked at all.

The fact is, the vast majority of password choices used by ordinary people today are not secure enough to avoid appearing on one of those nefarious lists.  If your password doesn’t appear on a list, or cannot be derived from a root that appears on a list, then it is never going to be cracked no matter whose computer is doing the cracking.  Bear this in mind next time you enter a password somewhere!  The problem is that people don’t like properly secure passwords because they are almost impossible to remember.  But there’s no simple way around that.  Here is an example of a highly secure 48-character password (the degree of security increases exponentially with the number and variety of characters used):

2ys5Ts46\Edtwe(Ddpbk8/!6taa3Zs<UdEAZmPtMe"nkrrRF

If this is what you had to type in to access your Ashley Madison account, you can console yourself that it was never going to be cracked.  Mind you, it might take you all day, and several frustrating attempts, just to enter it successfully each time you log in!  Such is the price to be paid for a comfortable level of security.

One of the most commonly used hash algorithms is SHA-2, designed by the NSA.  Less secure is MD5 which is often used to verify the accuracy of a CD rip (which is not a security application).  More secure would be something seriously potent like bcrypt, scrypt, or PBKDF2.  As a reasonable approximation, what makes an algorithm more ‘secure’ is largely down to the amount of computer time taken to calculate the hash value, as this also increases the time taken by a hacker to churn through a list of passwords.  Additionally, algorithms like scrypt work by requiring the computer to have a very substantial amount of RAM, making the required hardware much more expensive, while at the same time compromising a hacker’s ability to configure an attacking computer to perform multiple operations in parallel.  Despite this, the scrypt algorithm, for example, is deceptively simple, amounting to only a few tens of lines of code.

Many experts in computer and internet security are suspicious of NSA-designed algorithms such as SHA-1 and SHA-2, due to concerns that NSA may potentially only approve encryption systems that they are reasonably confident they can crack.  Such considerations are highly speculative.  However, a more recent development, SHA-3, was approved following a competition among non-NSA designers.

Even though what I have described sounds virtually uncrackable you would be surprised at how clever people are when it comes to mathematically analyzing encryption systems and devising increasingly more efficient ways of attacking them.  One such attack is known as a “rainbow table”.  It uses the formidable data storage capacity of modern computer and network technology to store vast lists of what you might term ‘intermediate results’.  By referring to those rainbow tables, hackers can seriously short-circuit the time taken to crack a password.  To get around that, most encryption and hash algorithms using a technique called “salting”, which adds various random characters to the user’s password before encrypting it.  These random characters, called the “salt”, can be stored in plaintext alongside the hash result without compromising the integrity of the encryption.  Salting has the effect of disrupting a rainbow table and rendering it useless.