In the authentication world, challenge-response authentication has its own importance. As we all know the password authentication, it is just a simple example of challenge-response authentication. This article helps the readers to grasp the concept and working of challenge-response authentication protocol.
Too often, we see hackers design systems that need security, but they send passwords out as cleartext. Generally, secure authentication is thought to be difficult to do, and often not worth the trouble. However, in our networked world, secure authentication is vital. Automated password sniffers are not only theoretically possible, but doubtlessly already in common use on large, high-bandwidth routers and NAT (Network Address Translation) devices, placed there by hackers or crooked network admins.
Ideally, all network communication should be encrypted, but sometimes this is not necessary, possible, or even legal! In any case, if you do develop some sort of network program that needs authentication devices, and you aren't able to encrypt all traffic, at least use challenge-response authentication.
In simple terms, Challenge-Response Authentication (CRA) is a method for proving your identity over an insecure medium without giving any information out to eavesdroppers that may enable them to identify themselves as you.
About CRA
In computer security terms, challenge-response authentication is a family of protocols in which one party presents a question ("challenge") and another party must provide a valid answer ("response") to be authenticated. The simplest example of a challenge-response protocol is password authentication, where the challenge is asking for the password and the valid response is the correct password.
Clearly an adversary that can eavesdrop on a password authentication can then authenticate itself in the same way. One solution is to issue multiple passwords, each of them marked with an identifier. The verifier can pick any of the identifiers, and the prover must have the correct password for that identifier. Assuming that the passwords are chosen independently, an adversary who intercepts one challenge-response message pair has no more chance of responding correctly to a different challenge than an adversary who has intercepted nothing. It should also be noted that CRA is still secure, even if an attacker can modify your messages to the server, although, if you send plain-text messages to the server, and the attacker can still modify that, the attacker will just wait for you to authenticate, then take over your connection.
For example, when other communications security methods are unavailable, the U.S. military uses the AKAC-1553 DRYAD numeral cipher to authenticate and encrypt some communications. DRYAD includes a list of three-letter challenge codes, which the verifier is supposed to choose randomly from, and random three-letter responses to them. For added security, each set of codes is only valid for a particular time period which is ordinarily 24 hours.
Software in the 1980s and 1990s often used a similar method for copy protection: challenges would be questions like "What is the second word in the third paragraph on page 418 of the manual?". The security assumption was that copying the manual was more difficult than copying the software disk.
Other Applications
Challenge-response protocols are also used to assert things other than knowledge of a secret value. CAPTCHAs ("Completely Automated Public Turing test to tell Computers and Humans Apart."), for example, are a sort of variant on the Turing test, meant to determine whether a viewer of a web application is a real person. The challenge sent to the viewer is a distorted image of some text, and the viewer responds by typing in that text. The distortion is designed to make automated Optical Character Recognition (OCR) difficult and preventing a computer program from passing as a human.
A CAPTCHA or Captcha is a type of challenge-response test used in computing to ensure that the response is not generated by a computer. The process usually involves one computer (a server) asking a user to complete a simple test which the computer is able to generate and grade. Because other computers are unable to solve the CAPTCHA, any user entering a correct solution is presumed to be human. Thus, it is sometimes described as a reverse Turing test, because it is administered by a machine and targeted to a human, in contrast to the standard Turing test that is typically administered by a human and targeted to a machine. A common type of CAPTCHA requires that the user type letters or digits from a distorted image that appears on the screen.
Working of CRA
CRA fundamentally depends on the existence of "one-way hashes". A one-way hash is a function that takes an input, and returns a "hash value". Finding the input of the function from the hash is "computationally infeasible", which, in the case of a decent hash function, means you'll be crunching numbers until the next stone age. Some of the popular one-way hash functions are MD4 (Message-Digest algorithm 4), MD5, SHA (Secure Hash Algorithm), and RIPE-MD (RACE Integrity Primitives Evaluation - Message Digest).
Let's call this one-way function h(). When the client connects to the server, the server makes up a random value, X. The server sends X to the client. The client sends the server h(X+P), where P is the password and + represents concatenation. The servers computes h(X+P) as well, and checks to see if the data from the client matches the computed value. If so, the client must know P.
A practical example:
This example uses the common unix utility "md5sum", which hashes the data on stdin to a 128 bit hash, displayed as 32 hex digits.
Assume the password is "mysecretpass" and both the client and the server know this.
The client connects to the server.
The server makes up some random data, say "sldkfjdslfkjweifj".
The server sends this data to client.
The client concatenates the random data with the password, resulting in
"sldkfjdslfkjweifjmysecretpass"
The client computes the MD5 hash of this value:
5>doug@saturn:/home/doug$ echo sldkfjdslfkjweifjmysecretpass | md5sum 4fab7ebffd7ef35d88494edb647bac37
5>doug@saturn:/home/doug$
The client sends "4fab7ebffd7ef35d88494edb647bac37" to the server.
The server runs the same command, and since the server (hopefully) got the same result, it lets the user in.
One wonders how does this provide security? Well, notice how that the password is never actually sent out in the clear, and how in order for an attacker to determine the password would be to bruteforce the hash function: a daunting task.
Technical Functions
In technical terms, CRAM (Challenge-Response Authentication Mechanism) is the two-level scheme for authenticating network users that is used as part of the web's HyperText Transfer Protocol (HTTP). In CRAM, there are two levels of authentication which are basic authentication and digest authentication.
Using the CRAM, the server (or, alternatively, a proxy server or gateway) issues a challenge to a user in the form of a "401 unauthorized" request for a password. The password is a string of characters known only to the user and the server. When the server receives the user response, it checks to be sure the password is correct. If so, the user is authenticated. If not, or if for any other reason the network does not want to accept the password, a "403 forbidden" message is issued, and access to the site is denied. The CRAM can be used in addition to other security features, such as strong encryption.
The basic form of CRAM can be abused because passwords are comparatively easy to steal. In digest authentication, the more sophisticated of the two forms of CRAM, the password does not appear as plain text sent over the network. This enhances security but does not provide entirely hack-proof protection. Even digest CRAM can be defeated under certain circumstances, giving an unauthorized hacker superuser status. This makes it possible for the hacker to launch a denial-of-service attack, making it difficult or impossible for authorized users to obtain authentication.
Cryptographic Techniques
Non-cryptographic authentication was generally adequate in the days before the internet came into being. Those were the days when the user could be sure that the system asking for the password was really the system they were trying to access, and that nobody was likely to be eavesdropping on the communication channel to observe the password being entered. To address the insecure channel problem, a more sophisticated approach is necessary. Many cryptographic solutions involve two-way authentication, where both the user and the system must each convince the other that they know the shared secret (the password), without this secret ever being transmitted in the clear over the communication channel, where eavesdroppers might be lurking.
One way this is done involves using the password as the encryption key to transmit some randomly-generated information as the challenge, whereupon the other end must return as its response a similarly-encrypted value which is some predetermined function of the originally-offered information, thus proving that it was able to decrypt the challenge. For instance, in Kerberos, the challenge is an encrypted integer N, while the response is the encrypted integer N + 1, proving that the other end was able to decrypt the integer N. In other variations, a hash function operates on a password and a random challenge value to create a response value.
Such encrypted or hashed exchanges do not directly reveal the password to an eavesdropper. However, they may supply enough information to allow an eavesdropper to deduce what the password is, using a dictionary attack or brute-force attack. The use of information which is randomly generated on each exchange (and where the response is different from the challenge) guards against the possibility of a replay attack, where a malicious intermediary simply records the exchanged data and retransmits it at a later time to fool one end into thinking it has authenticated a new connection attempt from the other.
Authentication protocols usually employ a cryptographic nonce as the challenge to ensure that every challenge-response sequence is unique. This protects against a replay attack. If it is impractical to implement a true nonce, a strong cryptographically secure pseudorandom number generator and cryptographic hash function can generate challenges that are highly unlikely to occur more than once. It is important not to use time-based nonces, as these can weaken servers in different time zones and servers with inaccurate clocks.
Mutual authentication is performed using a challenge-response handshake in both directions; the server ensures that the client knows the secret, and the client also ensures that the server knows the secret, which protects against a rogue server impersonating the real server.
Challenge-response authentication can help solve the problem of exchanging session keys for encryption. Using a key derivation function, the challenge value and the secret may be combined to generate an unpredictable encryption key for the session. This is particularly effective against a man-in-the-middle attack, because the attacker will not be able to derive the session key from the challenge without knowing the secret, and therefore will not be able to decrypt the data stream.
Simple Example of Mutual Authentication Sequence
The following is the simple example of mutual authentication sequence depicted by an algorithm
* Server sends a unique challenge value sc to the client
* Client generates unique challenge value cc
* Client computes cr = hash(cc + sc + secret)
* Client sends cr and cc to the server
* Server calculates the expected value of cr and ensures the client responded correctly
* Server computes sr = hash(sc + cc + secret)
* Server sends sr
* Client calculates the expected value of sr and ensures the server responded correctly
where
* sc is the server generated challenge
* cc is the client generated challenge
* cr is the client response
* sr is the server response
Password Storage
To avoid storage of passwords, some Operating Systems (e.g. Unix-type) store a hash of the password rather than storing the password itself. During authentication, the system need only verify that the hash of the password entered matches the hash stored in the password database. This makes it more difficult for an intruder to get the passwords, since the password itself is not stored, and it is very difficult to determine a password that matches a given hash. However, this presents a problem for challenge-response algorithms, which require both the client and the server to have a shared secret. Since the password itself is not stored, a challenge-response algorithm will usually have to use the hash of the password as the secret instead of the password itself. In this case, an intruder can use the actual hash, rather than the password, which makes the stored hashes just as sensitive as the actual passwords. Yet there exist fairly simple challenge-response algorithms that address this shortcoming.
Examples
Examples of more sophisticated challenge-response algorithms are zero-knowledge password proof and key agreement systems (such as Secure Remote Password (SRP)), CRAM-MD5, and ssh's (Secure Shell) challenge-response system based on RSA (Rivest, Shamir, & Adleman - public key encryption technology).
—By: R. Manoj,
The author is an Assistant Editor at Fanatic Media, Bangalore.
He is also an Independent Researcher, specializing in Systems Security. He has an active interest in designing security algorithms for securing mission critical systems. He can reached at infosecurity@fanaticmedia.com |
