SRP and Multifactor Systems

To authenticate a human user, there are three categories of things an authentication system can depend on: In the last few years, there has been much talk of adopting so-called multifactor authentication systems, which use more than one of the above factors to authenticate users. Examples of such systems include SecurID tokens and "smart cards". These are two-factor systems, because they use two of the listed factors, namely a physical token combined with a password, to perform authentication.

How does a strong password protocol fit in with such schemes? Although one might believe at first glance that these devices may make password authentication obsolete, that belief rests on two assumptions. It assumes that smart cards or their equivalent will become ubiquitous in a relatively short time frame, and it assumes that they cannot benefit from strong password authentication. We will demonstrate that neither of these assumptions is valid. In a world where the value of electronic transactions is constantly increasing, the importance for maximal password security only rises with time.

Common Myths

Myth #1: A password-only system is not secure.

This is a common and unfortunate misconception that is held even by some people in the security "expert" community. While it is true that password-based systems have been responsible for many security compromises in the past, this has been a result of the widespread use of weak password authentication.

Strong password authentication removes nearly all of the classic network attack points that might be used against a weaker system. Paradoxically enough, this sometimes results in security that is better than some two-factor methods, because passwords are rather difficult to steal, and the standard passive sniffing and brute-force attacks are rendered useless. Choosing between strong password authentication and a simple two-factor system is really a tradeoff between the physical security offered by a carried token and the mathematical security inherent in a strong password method. As we shall see later, the most secure solution involves a combination of the two technologies.

Myth #2: Everyone will have a smart card in their wallet, and smart card readers will be everywhere next year.

There has been a great deal of hype generated over the last few years about how smart cards will be everywhere, mostly from the manufacturers and marketers of smart cards and smart card readers. They have been quick to capitalize on weaknesses in password authentication technology to push these products. Some bought into the hype because strong password authentication technology either had not been developed or was not widely known or standardized at the time.

Although smart cards are a nice way to improve the portability of stored keys, the concept of hand-carried authenticators has some fundamental problems that will limit their acceptance by the public. Simply stated, users like the convenience of reusable passwords and hate the inconvenience of carrying an object around just to log in to a computer system. Even if an administrator overcomes the resistance of users, the added expense of cards and readers plus the trouble of distributing said tokens makes it extremely difficult to justify a token-based solution except in small groups where strong password mechanisms are unavailable for some reason. As a result, there are many application domains that will probably never go to a smart card system of any kind, much less an externally-imposed standard.

A strong password method takes away most of the reason for wanting a smart card system and gives users the continued convenience of reusable passwords without the security risks once associated with them. As David Jablon once noted, strong password systems are often regarded as "politically-incorrect cryptography" because they threaten the smart-card and hardware-token market, reducing or eliminating the need for such devices in many applications. In our opinion, however, strong password systems are a win for the users, because they offer a more convenient and less expensive alternative to two-factor authentication while providing better security than older password-only systems.

Even though two-factor systems are unlikely to be as widespread as the hype would lead one to believe, there are some applications in which this technology is useful. Rather than thinking of strong password technology as a competitor to smart card systems, the two technologies should be thought of as complementary to each other. Combining the two allows the physical security of a hardware token to leverage the inherent security of strong passwords.

Myth #3: A system designed around smart card technology is automatically safe from brute-force passive and active attacks.

Some people think that having a stored key makes the protocol secure against the usual passive/active attacks over the network. Unfortunately, this assumption ignores the fact that the system is a two-factor system; there is also a user-memorized PIN involved in authentication. Nearly all two-factor systems used in practice do a very poor job of isolating the two authentication factors. A true (some may say ideal) two-factor system requires that the two authentication factors both be compromised before security can be breached. It also requires that the compromise of one factor not help an attacker to compromise the other factor more easily. Otherwise, it would defeat the purpose of using two authentication factors in the first place. While these requirements seem fairly self-evident and obvious, they are seldom met in real-world systems. The following analysis will cover smart card systems that are used for remote system access as well as financial transactions; this is, after all, the nirvana that smart card advocates envision.

Smart card systems use a user-entered PIN to prevent a thief who has stolen or "borrowed" a smart card from being able to use it. This is usually implemented by encrypting the private key on the smartcard with the PIN or a key derived from it. Alternatively, the PIN, combined with the contents of the smartcard, forms the private key. This approach, unfortunately, can be defeated by an adversary who steals the card and has access to custom smart-card-reading equipment. (It is always a conservative but wise assumption that well-equipped and well-funded adversaries exist.) If the card contains an RSA private key, the attack is particularly easy because private keys take a special form, and the attacker can simply try all 10,000 or so PINs to see which one results in a valid private key.

A smarter design might use a discrete-log signature scheme, in which private keys are not constrained to a particular form. Even these are subject to a stolen-card attack. If an attacker eavesdrops on a successful transaction executed by a legitimate user and later steals the card, the information on the card combined with the network traffic can be used to perform an off-line attack on the PIN. Encrypting the transaction with the merchant/host system's public key a la SSL doesn't help, either. The broad outline of such an attack might look like this:

This attack can easily be expanded and refined to work against specific smart card implementations. Although most people might not be concerned with such stolen-card attacks, it does not seem wise to attempt deployment of a standard with such weaknesses, no matter how minor.

A better way to handle smart card PINs

Here is a proposed sketch of an improved smart card protocol that leverages the strength of a strong password system like SRP-3 to protect both the stored and the memorized authentication factors from attack.

To generate an initial key, a large random number R is generated and the PIN, P, is selected, either by the user or at random. KS = H(R, P) is the private key, and KP = g^KS is the verifier. The value R is burned into the smart card, and KP is given to the host computer/credit card company/bank/etc.

Note that unlike the PIN itself, KP does not need to be transported confidentially; it is enough to ensure its integrity as delivered. This can be done easily by verifying a fingerprint of KP over conventional means like telephone or mail. Since KS has large entropy, a captured value of KP is useless to an offline brute-force attacker. Also note that the verifying institution knows neither R nor the user's PIN; a compromise of the database of KPs would be embarrassing but not necessarily catastrophic.

To authenticate a transaction, the smart card uses SRP-3 as follows.

The securely-exchanged session key K makes both data confidentiality and integrity easy to achieve. If encryption is not available and only integrity is needed, the last message can become <M, H(K, M)>; the hash function becomes a MAC. The value Z neatly stops replay attacks and ensures that K is fresh for each session. Note that the last message implicitly verifies the shared session key, making the explicit session key proofs in SRP-3 unnecessary and simplifying the protocol.

This protocol is significantly more secure than current smart card protocols against card theft. A stolen card is quite useless even to a well-equipped attacker now, because even if R were recovered from the card, it gives no clues about P. In addition, since SRP-3 has been designed to resist both active and passive brute-force attacks, the attacker would not benefit from either previous or future network attacks against the legitimate user. In other words, even if the adversary stole the user's card, captured R, and owned the network over which all authentication took place, he would still be unable to mount a brute-force attack on even a four-digit PIN. He could do nothing better than to go on-line and try out each PIN to see if it worked. An on-line attack, of course, could be easily detected by the bank or merchant.

Another key feature of this system is that the highly secret KS is never stored anywhere, encrypted or otherwise. There is no database of KS values at the vendor side, waiting to be broken into. Even the smart card only generates KS in memory, never keeping it anywhere in non-volatile storage.

The incredible security afforded by this protocol is a direct result of the underlying strength of the SRP-3 protocol. While SRP-3 protects low-entropy passwords well, its security is amplified even more when the password itself is augmented with a strong stored key, making it a high-entropy "password". SRP-3 leverages the security of both factors while keeping them independent of each other. Its forward secrecy characteristics also create an impenetrable barrier between the long-term secrets and the short-term session keys. One result of this is that the encrypted messages can be sent in any form regardless of redundancy and without requiring confounders or special padding. The high-entropy session key K is effectively isolated from the card key and the PIN.

This is the foundation for a true two-factor system, one in which compromise of one factor (a stolen card) does not lead to the compromise of the other (the PIN). SRP-3 has other benefits as well. Since the protocol is truly zero-knowledge, even the card reader cannot obtain any useful information about the private key. The SRP-3 smart card protocol is also not dependent upon any deployed public-key infrastructure, which means that it can be used immediately without having to wait for such an infrastructure to become standardized. When the PKI is finally in place, the SRP-3 smart card protocol can be transparently layered on top of any security layers derived from the PKI. Independent, layered security systems have been shown to be more secure than a system built upon incomplete, interdependent components.

Since SRP-3 is so much stronger than conventional authentication techniques, it allows some additional flexibility in hardware design. For example, since revealing the burned-in value R does not compromise the PIN as it would under a conventional system, the manufacturer would have the option of using a cheaper, lighter non-tamperproof unit to store R. The inherent security offered by the intractibility of breaking SRP-3 can augment or even replace some of the physical-domain security features of smart cards.

Myth: "Our smart cards are secure enough already."

Actually, no. Hacker groups are already having a field day with smart cards, in much the same way that they have been compromising weaker (e.g. challenge-response) password methods in the past. Says one wily hacker, "We've already been ripping apart cards like that at the L0pht for some time." Smart card systems based on weak authentication technologies can never really be made to resist a determined hacker, regardless of how much key material is stuffed onto a card. Once the break is published, there is no way to put the genie back in the bottle.

There are a number of smart card standards in existence, but none of the appear to offer the level of protection against card theft that the SRP-3 smart card protocol can provide. Most of the standards try to deal with the problem using a number of creative, ad-hoc techniques, but ultimately these do not inspire as much confidence as a protocol that has been specifically designed and publicly reviewed as a secure password authentication protocol. Indeed, the security and versatility offered by a smart card system based on SRP-3 may become an important distinction in the inevitable shakeout looming in the smart card industry.