We authenticate ourselves multiple times every day. Every time we open a door with a key we are authenticating ourselves to the building we are entering, simply by demonstrating possession of the key. When we buy something with a bankcard we authenticate ourselves via possession of the card and knowledge of the associated PIN. This is known as two factor authentication. We use passports to authenticate ourselves when we travel. Sometimes we authenticate by simply recognising each other, although this is not a very scalable method. Failure to authenticate quickly or accurately can have fatal consequences – in the American Civil War the famous confederate General Stonewall Jackson was killed by his own troops for failing to authenticate himself.
With the advent of the computer, the issue of authentication became more important. It has fallen to cryptographers to come up with suitable mechanisms. Here we will use the terminology of a “client” who is authenticating to a “server”, as this is most often the context in which authentication arises on the Internet.
Keeping Secrets
Keeping secrets is fundamental to authentication. We clients need to have an authentication secret that will uniquely identify us and cannot be taken from us. But keeping secrets is hard. We can remember small ones and we can write down or store bigger ones. But if we write it down or store it, we need to keep it safe somewhere. A good idea is to actually keep it in a safe! This can be protected by a combination lock, rather like those ubiquitous safes found in hotel rooms. Typically a small easily remembered 4-digit PIN is the combination that opens the vault.
Computers have similar problems. They can be quite good at keeping small secrets – like us they can hold them in memory. But large files are much harder to protect. Computer based systems can also benefit from access to the equivalent of a hardware vault. A common scenario then is where the authentication secret is hidden inside of a hardware vault which can only be unlocked by entry of the correct PIN. Even better if the entire authentication protocol can be carried out from within the confines of the vault. Such a vault typically comes in the form factor of a smart-card. A mobile phone SIM card would be a classic example.
One alternative (and under exploited) idea is to split a secret into multiple parts, as a way of keeping it secure. Ideally the splitting should be done in such a way that having all the parts except one is as useful (in fact useless) as having none of the parts.
Multi-factor Authentication
This is increasingly seen as a good idea, as it is intuitively much more secure. Here we will only consider two-factor authentication as we typically authenticate via a combination of what-we-know and what-we-have. Now the what-we-have part can be the hardware vault itself, and the what-we-know part is a PIN.
Why you might ask do we have to deploy extra hardware? Why is a software solution not possible? Can we not have a software vault? And surely a software vault is exactly what encryption should give us?
Well yes we can have a software vault. But the problem is the dreaded “off-line dictionary attack”. Here an attacker who wants to determine the combination of the software vault (the PIN) can quickly try every possible combination (at full computer speed) until the safe pops open. And how do they know when they have hit on the right combination? Because they know what a genuine authentication secret looks like. So if you want a software vault, you will need a large unguessable (and hard to remember) password, not a simple PIN. Basically the number of combinations needs to be so large that even a fast computer cannot exhaustively try all of them in a reasonable time. And you would be surprised at just how good computers are carrying out this kind of search.
Of course this is not a problem for a hardware vault – after three wrong attempts it will simply not allow any more, and it might alert the appropriate authorities. Or it might self-destruct and destroy its own contents!
Hash-based Methods
Cryptographers have many useful tools. One is the humble hash function. This takes an input of any length and provides an output which is of a fixed length, typically a 70-digit number. It can only be implemented by a computer. No two distinct inputs ever produce identical outputs. Or put it this way – if anyone ever discovers two such inputs which do produce identical outputs then that would represent a “collision” and the finder would automatically enter the cryptographer’s hall-of-fame. But take it from me – it’s not going to happen. The hash function is also “one-way”. That is given the input, the output can be calculated very quickly. However, given the output, it is impossible to determine the input.
Username/Password
This is by far the most common method of authentication in the world of computers. The client chooses a memorable password and registers with the server. The server stores the client username, and next to it a hash of their chosen password. The list of clients and their hashed passwords is known as the password file. More generally we might call it a credentials database. When a client wants to authenticate they supply their username and password. The server looks up the username, hashes the supplied password, and compares this with the stored value. If they match, authentication succeeds.
Using the hash function has advantages and provides a certain level of security. Anyone who accesses the credentials database cannot easily determine the associated passwords – recall that the hash function is one-way. However, they can guess passwords, hash them, and look for matches in the file. For this reason, we are encouraged to use large unguessable passwords.
If the credentials database could be guaranteed to be protected, then this would not be an issue. But the sad reality is that over and over again computers have shown an inability to protect large password files, especially those required to be available at the front line of the server authentication process.
Challenge/Response
This is the next most popular idea. Each client is issued with their own private hash function. The server has a copy of the same hash function. To authenticate the server issues a challenge to the client. This forms the input to the hash function and the output is transmitted back to the server. The server then passes the same challenge through its copy of the hash function, and compares it with what it has received. If they are the same, you are authenticated. This method is surprisingly widespread – it is used for example in all chip-and-pin bank cards, mobile phone SIM cards and pay-per-view TV smart cards. Another common form is the security token. Your bank may force you to carry around one of these tokens, to use when you need to do some high-value ebanking operations.
To protect the secret hash function, it is typically implemented inside of a hardware vault. The hash function can only be accessed when the correct PIN is entered. So we get two factor authentication. The process can only be activated by the client if they have both the vault and the PIN.
On the server side there is a credentials database containing usernames and hash function parameters. So again this represents a major vulnerability (and a famous security token vendor was famously hacked when such a file was exposed, instantly rendering 40 million hardware tokens obsolete. Ouch!)
Public Key methods
Another more powerful cryptographic primitive is the Public/Private key pair. Public key cryptography was invented in the 1970s. My public key is, well, public. You could use it to send me a secret message, or to verify my digital signature. I alone can use the associated private key to decrypt your secret message, or to apply a unique digital signature. An infrastructure – the Public Key Infrastructure – is in place which binds public keys to actual identities.
Public Key Cryptography
First I register with the server by giving it my public key. The server maintains a database associating my username with my public key. To authenticate the server sends me a random message. I digitally sign it with my private key and send it back to the server. The server looks up my public key and uses it to verify my signature. If it verifies, I am authenticated.
This is better, as the servers credential file only contains public keys. So on the face of it we don’t need to worry so much if it is stolen. On the client side it makes sense to again lock the private key inside of a PIN-protected hardware vault, to obtain two factor authentication. It makes even more sense to place the entire client side of the authentication protocol inside of the vault so that the private key is not even momentarily exposed to the outside world.
One downside is that public-key operations are orders of magnitude more time-consuming than simple hash functions. Only the more expensive hardware vaults would have the capability to implement them.
Zero-Knowledge proofs
This is a more elegant idea. In general, using cryptography, it is possible to prove possession of a certain secret, while revealing nothing whatsoever about that secret. Sounds unsettlingly counter-intuitive but such proofs are indeed possible. This leads us to a different approach to the authentication problem. Let us separate out the server function from the registration process. Up until now it is assumed that clients register directly with the server. But what if a third party is introduced – a Trusted Authority or TA – whose role it is to hand out authentication secrets to clients that register successfully. This third party is largely off-line, and it is certainly not required to be on-line for day-to-day authentication of clients.
So now assume that this TA has a Public/Private key pair. To create a client secret it digitally signs an identity string associated with the client. To authenticate the client uses a zero-knowledge proof, to convince the server that that they are in possession of a valid signature of their claimed identity.
The beauty of this idea is that the server does not need to maintain a credentials database for its clients. Indeed, neither does the TA. So there is no large and easily stolen credentials database! As before to obtain 2-factor authentication the client might keep their signed identity inside of a PIN-protected hardware vault. The TA also might use a vault to protect its private key – in fact the TA private key is the lynch-pin of the whole system. Doing it this way there is only one public key involved, the public key of the TA which is known to all parties. Learn more about the benefits of authentication powered by zero-knowledge proof.
Software Vault re-visited
One annoying aspect of all these solutions is the apparent requirement for an expensive hardware vault. In most PCs and laptops such a vault does not exist. And where it does – like as the SIM card in a mobile phone – it doesn’t belong to us and isn’t available for us to use. If such a vault is not available, must we fall back on Username/Password?
Let us look again at some of these solutions and see can we get away with a software vault, and an easily remembered PIN.
What if the method of section 5.1 was implemented in such a way that the private keys had no identifiable structure, and if the public keys were not made public? In fact, there are public key methods in which the private key is just a random number. And there is no actual requirement to make client public keys “public”. In this case light-weight encryption with a PIN would be adequate, as a brute-force searcher would have no way of knowing when they had hit on the right PIN just by looking at what it decrypted. They would have to test the result of each guess by attempting to log-in to a server, which is now implementing a 3-strikes-and-you-are out policy. Unfortunately, there is still a big problem. If (or rather when) the credential database is hacked and the public keys revealed, all clients without exception fall back to just one-factor authentication.
What about the method of section 5.2? The problem here is that a brute force searcher always has access to the TA public key. So as they try each PIN they can attempt to verify the signed identity. When the verification succeeds, they have found the authentication secret. So that won’t work.
Happy Ending
At this stage the features of an ideal solution are beginning to become clear. We would like a scheme which (a) does not require a credentials database (like the Zero-Knowledge proof method), (b) does not require a hardware vault (like Username/Password), and (c) which is easily made 2-factor and can use a short PIN (as expected of most modern systems).
Today’s application, security and operations owners must deal with the ever increasing and unpredictable demand to securely authenticate more internal, external and mobile users and devices and do so at the scale and speed of today’s Mobile Internet.
In response to this, they continue to attempt to ratchet up their password-based security with incremental investments in new and higher levels of two-factor and two-step authentication, doing nothing to defuse the ticking time bomb of a breach of their password database or to make life easier for users, who are increasingly frustrated with concocting, remembering and using complex passwords, technologies and processes.
MIRACL Trust®, the world’s first and only Zero Password Strong Authentication Platform, enables cost-effective and agile strong authentication at mobile Internet scale. MIRACL Trust® MFA eliminates passwords and password database breaches altogether while dramatically increasing user safety, convenience and satisfaction. MIRACL Trust® MFA lowers the administrative costs and complexity of rolling out strong authentication at mobile Internet scale.
