Cryptography – Particular algorithmic function encoding – Public key
Reexamination Certificate
1997-03-25
2001-05-01
Cangialosi, Salvatore (Department: 2732)
Cryptography
Particular algorithmic function encoding
Public key
Reexamination Certificate
active
06226383
ABSTRACT:
1. BACKGROUND
1.1. Field of the Invention
This invention relates to cryptographic communication in general, and more specifically, to methods and apparatus for securely proving knowledge of a shared small secret password between two parties using messages exchanged across an open communication channel.
1.2. Description of the Related Art
Passwords are an essential component of secure systems. Although they play a crucial role in authenticating the identity of people to systems, traditional password-based network authentication systems have weaknesses due to improper use of passwords. Such systems often use the password as if it were a cryptographic key, and require the password to be chosen as carefully as one would choose a cryptographic key. One requirement is that the choice be from an effectively large “password-space”. The size of this space is sometimes expressed in terms of a number of bits of “entropy”. For simplicity, we often refer to any low-entropy secret from a space that is vulnerable to dictionary attacks as a “small password”. In practice, due to human limitations, many passwords are small. This is a problem for many systems which can be attacked using a repeated computation using all possible (or likely) guesses for the password. This is known as a brute-force, or dictionary attack.
Dictionary attacks can occur on-line, in an interaction between an attacker and a legitimate user or system. They can also occur off-line, using information gathered by monitoring messages sent between two legitimate parties during an authentication protocol exchange. On-line attacks can often be easily detected and thwarted, by counting bad attempts and denying access. Banking ATM machines thwart attack by retaining the user's card after three bad access attempts. But remote authentication opens the possibility of an off-line attack on the messages transmitted across a network.
As widely available computing power increases, successful off-line dictionary attacks on a small password become easier. Today, ever-increasing computer power has clearly outpaced the (unchanging) ability of people to remember longer passwords. Today, 56-bit symmetric key seem to offer only marginal security. U.S. export regulations have allowed export of 40-bit key systems, presumably because they are breakable. Thus, in many systems, a “safely large password” requires more than 40 bits of entropy, and the number is steadily growing. On the other hand, it seems that many people cannot easily remember and use a password from a space of 32 bits. This is equivalent to a random 10 digit number, about 6 random letters and digits, or a pair of words from an average English dictionary. Several studies over many years have found that a significant percentage of user-chosen passwords can be found with a modest computational effort, having an effective size of less than 30 bits (roughly a billion choices). At one extreme, bank-card PIN numbers have less than 14 bits. Forcing everyone to double or triple the size of their passwords, and expecting them to not write them down, or expecting most people to be comfortable using “pass-phrases”, is denying the inevitable truth. People can't or won't properly handle anything larger than a small password, so systems must protect them from attack. In light of this, most traditional network authentication systems that use passwords are obsolete. Better systems must be designed and deployed that are resistant to off-line dictionary attack, to safely tolerate the use of potentially small passwords.
1.3. Detailed Objective
Our goal is to authenticate one party to the other with a series of messages exchanged across an open network, where interception or modification of the messages by an untrusted third party may be possible. Furthermore, we do not require that either party have access to any additional long-lived keys for either a symmetric or a public-key encryption system—we seek a method based solely on the password. In light of the crucial role of the password, we must protect it as much as possible.
These methods can be used for direct person-to-person authentication, where an appropriate computer or device performs the required protocol computation on behalf of the person. More typically, one of the parties is a host computer. We will refer to the user's computer as “Alice” and the host computer as “Bob”.
We assume that Alice and Bob use a small password as the basis for establishing a secure communication channel between the them, and we assume that an attacker has the computational power to enumerate all possible password values to attempt a dictionary attack. We first desire a method where Alice and Bob prove to each other that they know the same secret. We also desire an extended method where Bob, who only has knowledge of a “hidden-password”, verifies that Alice knows the password. The hidden-password in our extended method will be a specially constructed one-way transformation of the password.
Historically, much attention has focused on the problem of getting Alice to use a large “well-chosen” password. Newer research, such as ours, focuses attention on how to legitimately use a small password for remote authentication across an open insecure network. This must be done without making the password vulnerable to off-line dictionary attack. A related goal of our methods is to provide a zero-knowledge password proof. One party proves knowledge of the password to the another without revealing the password in the process. The importance of the zero-knowledge characteristic is explained further below.
1.4. Traditional methods
Most older methods of remote authentication based on a shared secret do not survive dictionary attacks when the secret is small. In a common example, Alice sends a random number R to Bob, Bob computes a one-way collision-free hash function h of both R and the password S, and sends the result h(R,S) to Alice. Alice also computes h(R,S) and compares it to Bob's result. If they are equal, Bob has proven knowledge of the password to Alice, and because of the hash, the secret password is not directly revealed to a third party who monitors the exchange. The randomness of R prevents replay attacks. However, when the password is small, Eve, an eavesdropper who obtains R and h(R,S), can repeatedly hash each possible password S′ in the dictionary with R, and compare each result h(R,S′) to Bob's response. (The dictionary entries may be either pre-built, or computed as needed.) When a match is found, the attacker knows that S′ is the password.
When tolerance for small passwords is added to all the classic requirements for a secure exchange, most traditional password authentication methods are shown to be obsolete.
Some methods can confirm knowledge of a small shared secret based on the parties' access to other long-lived data. This data may be a large shared secret, or a large public key. There are many general methods for public-key-based authentication. Such schemes pose additional problems such as certifying public-keys, requiring a secure key distribution system, or requiring secure storage for large secret keys. Here we seek methods that are based solely on an easily-memorized secret.
A common approach to protecting the password uses persistent public keys. Typically a client Alice sends a password to a server Bob where he then uses the clear-text password for verification. But before sending it, Alice first seals the password in an encrypted message using Bob's public key. While this approach is intended to provide assurance that only the holder of the corresponding private key, presumably Bob, can unseal the message and discover the password, it creates a new set of security issues.
In many systems, such as the common web browser using Secure Sockets Layer (SSL), there are several ways that an invalid server Barry can be mistaken for Bob such that an unwary user might reveal the password to the wrong party. The security of these systems may depend on:
Bob keeping the private key secret,
Alice knowing
Blodgett & Blodgett, P.C.
Cangialosi Salvatore
Integrity Sciences, Inc.
LandOfFree
Cryptographic methods for remote authentication does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Cryptographic methods for remote authentication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cryptographic methods for remote authentication will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2551870