By: Gunter Fuchs
Working deep down in the guts (bits and bytes) of a computer, it becomes hard to explain concepts, once the electronic world has taken them over. I wondered about a simple way to explain authentication without referring to the world of computers, so that someone who isn’t savvy with technology can readily understand it. Well, there is an authentication scenario in one’s modern day-to-day affairs that does not involve any computer (except if you consider the human brain to be one). This scenario is plain and simple: putting a signature on a piece of paper.
How can we describe a signing process in system security terms for authentication? Specifically, what has putting one’s signature on a contract or bill to do with “challenge / response authentication”? The analogy is quite simple. The challenge is the request by – say – the cashier to sign the bill. The response is your signature. That way, you prove that you are the person who owns the credit card. The cashier authenticates your signature by comparing it with the one on your credit card. In computer security terms, that means that the host (cashier) compares a stored response (your signature on the credit card) with the actual response (your signature on the bill). If the host (cashier) comes to the conclusion that both signatures are equal, it accepts the generator of the response as being authentic.
This scenario is quite insecure because someone can easily forge a signature. The reason in cryptographic terms is because this system can generate only one challenge / response pair. An adversary knows what the challenge will be, and if she has seen / copied the response (signature) only once, she can, after some practice, reproduce it relatively fast and easily. A way to improve the security in such a system is to increase the number of possible challenge / response pairs. An example in the online world is a list of question / answer pairs. Sometimes when you log in, a question pops up asking the name of your favorite pet, teacher, or band. Only you and the online host know the correct answer. Such a list increases the security of a system, but since this list is usually short, finding out the few answers by eaves-dropping is not a huge obstacle for an adversary. The advantage of such a short list of challenge / response pairs is that a human brain can manage it. But in a system where only computers play with each other, we can introduce much bigger lists. They are nowadays pairs as big as 2^32. In such a system, with a huge number of challenge / response pairs, the host chooses one randomly. An adversary would now have to replicate this huge table, and once it has done that, search through this table for the challenge to find the correct response. Well, you could argue, why not? And how can an authentic client find the correct response in a feasible time? This issue is solved by introducing a cryptographic algorithm and a key into the system. By using a key and an algorithm, tables of challenge / response pairs don’t have to be generated and stored, but a host only has to generate a random number to “choose” a challenge. When the client receives this random number as a challenge, it combines it with a key using a cryptographic algorithm and sends the result back to the host (response). (The cryptographic algorithm “hides” the key so that an adversary cannot extract it from the response.) The host now performs the same calculation using the same key and compares the received response with its calculated one. If the two match—voila!—the host finds the client to be authentic.
With a system that incorporates the process of random challenge / response authentication, an adversary would have to monitor many, many (depending on the biggest number – “number space” – used in this system) authentication sequences between host and client and store them in a table. And after that, it would have to find the challenge in this table to come up with the correct response if it wants to pretend to be the authentic client. Finding it would practically take eternities, “would be infeasible” in cryptographic terms. The quality of the randomness of the random number is important, because the better the quality of the random number generator the less an adversary can predict the next challenge. If an adversary could predict the next challenge, he could search his table in advance.
random challenge response, cryptographic algorithm
Atmel | Bits & Pieces 