An oracle attack analyzes each interaction with a system to extract hidden data or implementation details. Defending against oracle attacks is easy—but only if you see vulnerability in the first place
The concept of an oracle attack originates from the study of cryptography. By choosing the plaintext or ciphertext input to an encryptor or a decryptor, respectively, and analyzing the output as it relates to the chosen input, it is often possible to deduce valuable information about the algorithm or a secret item of information, such as one of the keys, that is being used in the algorithm.
Such a vulnerability in a cryptosystem is termed an "oracle" because, like a visit to the ancient Greek Oracle at Delphi, every input, or question, receives an output, or answer, and it is left up to the observer to decide if the answer is meaningful. When the output of an oracle in response to many inputs reveals a hidden truth, the cryptographic oracle attack has succeeded.
According to archaeologist John Hale, the Temple of Apollo at Delphi was constructed at the site of a natural gas vent that would release ethylene from a crack in the earth. The Pythian priestess was said to communicate with Apollo, relaying one's question and returning Apollo's answer. She would become capable of doing so only after inhaling ethylene gas that collected in the Temple's basement. You could think of this as a "high priestess"-in-the-middle vulnerability.
Unfortunately for information security, the high priestess has left the building and is now found throughout the world's information services. It is very common for programmers to write code that exposes software and services to a variety of oracle attacks similar to those that plague cryptographic implementations. In essence, anything that can be learned by an attacker, or anything of value that can be determined conclusively through an attack, that was not intended by the developer of the information system can be viewed as exposing an oracle attack.
A classic oracle attack applied to something other than cryptography is a condition where a password can be deduced by sending many chosen passwords in sequence and carefully monitoring the amount of time required for the system to produce an error response. It is sometimes the case that a partial match of a password will cause the password lookup routine to go through additional rounds of pattern matching or other processing, resulting in a measurably longer response time. Adapting subsequent input based on clues in the output, or the time it takes the oracle to produce the output, may ultimately reveal the entire correct password input. This is known as an adaptive oracle attack, where the oracle will only reveal something of value one small piece at a time and the adversary must adapt in order to achieve an attack objective.
Simpler oracle attacks that are similar to screen scraping are widespread among information systems that dispense data from a database in response to constrained queries. A screen scraping attack is one in which a query will be responded to directly, and the attacker simply captures the output and makes off with it. Preventing an attacker from scraping the entire database is the only defense against screen scraping other than choosing an output data format (e.g., images) that is more difficult for the attacker to parse and store in their own database. Such a scenario becomes an oracle attack when something other than the data itself can be discovered through repeated attacks.
For example, it is very common for web applications to offer a password recovery feature for users. Just type your user name or e-mail address into a form and the web server will deliver your new password to you in e-mail. This is a nice self-service support feature, to be sure, but what happens when you type in an account name that does not exist? In most cases, the server will display an error message. This results in a simple oracle attack that enables anyone to discover the entire range of valid user account names, or worse, to determine the e-mail addresses of every single one of the web site's users.
By purchasing a database of several hundred million e-mail addresses from a spammer, anyone can mount a chosen e-mail address oracle attack against a membership-enabled web site that exposes such a flaw. After enough time passes, the attacker will know which of the e-mail addresses in the source database are also in the web site's membership database.
Defenses against oracle attacks are always easy. What is apparently not easy is seeing that the attack is possible in the first place. More awareness of this attack method is crucial to protect against unintentional disclosure of confidential information and to lock down privacy defenses for publicly accessible information services that accept and respond to queries of all sorts.
One has to wonder whether it would have been possible to ask the oracle of Delphi questions, the answers to which would have revealed that the oracle was under the influence of ethylene gas.
Jason Coombs is Director of Forensic Services for PivX Solutions Inc. (NASDAQ OTCBB: PIVX), a provider of security solutions, computer forensics, and expert witness services. Reach him at [email protected].
