Computers leak. Even machines running strongly encrypted programs give out information that can be used to infer secrets as electromagnetic signals, the size of packets, or the time it takes to store data in memory can all provide hints to what an application is doing, allowing attackers to deduce information and break cryptographic security.
The vulnerability of such side channels has been known for years, but as more computing moves into the cloud and onto smartphones and tablets, computer scientists are discovering new avenues of attack. And they are working on ways to thwart those attacks.
“One problem we are encountering increasingly is our computations aren’t happening in a safe, secure environment,” says Guy Rothblum, a Microsoft researcher. Many applications run on virtual machines inside servers, ostensibly walled off from neighboring programs. But other applications on the same computer can gain information about the state of that server and use it to infer what the first program is doing. And it is not only encryption keys that are vulnerable to such attacks, which are also known as physical attacks because they measure some physical characteristic of the operation.
“They are particularly devastating for cryptographic algorithms, but I would worry about it for my proprietary algorithm being run on a server or my sensitive data being stored on a server,” Rothblum says.
To combat the problem, Rothblum and Shafi Goldwasser, professor of electrical engineering and computer science at the Massachusetts Institute of Technology and Rothblum’s former advisor, developed a scheme to make computing more leakage resilient. They created a compiler that takes an algorithm and breaks it into a series of modules that perform sub-computations. Although the sub-computations can leak, not all of their bits can be discovered. “The only assumption is that it doesn’t expose everything that’s happening in a sub-computation at once,” Rothblum says.
Each module is a cryptographically secure black box, allowing a hypothetical attacker to see the input and the output, but not the computation occurring inside the box. Data goes into the first module, which performs some computation, then passes the output to the next module, and so on down the line. “Each of them alone isn’t doing anything too sensitive,” explains Rothblum.
Even if the attacker can get some idea of what a particular module is doing, because he can only discover a small number of bits, he cannot learn enough to expose the whole algorithm. That is true even if the adversary can throw as many computing resources as he wants into the problem.
Essentially, the compiler elongates the program, and that can slow down the computation substantially; to protect against k bits of leakage from each sub-computation, the program’s execution time expands by a factor between k-squared and k-cubed. But Rothblum is optimistic that, though it may take years, the computational overhead could be significantly reduced. One approach might be to identify a sensitive core piece of an algorithm and only protect that smaller piece. The significant fact is that the compiler is feasible. “We know it can be done, which we didn’t before,” he says. “Now it’s a matter of making it more efficient.”
Bugging Smartphones
While Rothblum works on safer ways to compile programs, other researchers are discovering vulnerabilities in the growing universe of mobile devices. Suman Jana, a doctoral student at the University of Texas, Austin, won Best Student Paper at the IEEE Symposium on Security and Privacy in San Francisco in May for describing an attack that lets an adversary figure out which Web sites a smartphone user is browsing. The attack takes advantage of the proc filesystem, a virtual file of process information, in Unix, which is the basis of Linux and Android, to uncover how much memory is allocated to a program. Other avenues can reveal similar information in Windows and iOS systems.
“Whenever a browser loads a page, it does a bunch of memory allocations,” Jana explains. “That gives away which pages you are browsing.”
The attacker would first use his own browser to visit Web pages and record how much memory the browser requires to render the page. Jana found that he could distinguish 30%50% of the 100,000 Web sites he visited, depending on which browser he used. The process worked best for pages that did not change very much between visits.
Having disguised his malicious app as an innocuous one and tricked a smartphone user into downloading it, the attacker could watch the phone’s memory allocations and figure out which pages the user was seeing and finding, for instance, what diseases he researches on WebMD. He could deduce even more information. For example, he can tell when someone logs into the dating site OKCupid, because a profile page uses more JavaScript than a log-in page. A free user of the site will see ads, which the attacker can infer by the use of the Flash plug-in.
Combining this process with other side-channel attacks could expose even more information, Jana says. For instance, an adversary can measure the time between keystrokes when a user is typing, and use that to guess which keys are being struck. That information can help distinguish between two pages with similar memory allocations. But if the user is on a login page or a shopping site, it can also help an attacker guess passwords or credit card numbers.
Soundcomber can deduce where in an automated phone system a user is and record the individual’s bank account number or Social Security number.
Hao Chen, associate professor of computer science at the University of California, Davis, developed Touchlogger, a program that can infer keystrokes on a smartphone or tablet by the way the device moves in response to pressure on the touch screen. Although apps require user permission to access sensitive data, such as location readings, the output of spatial sensors, such as the gyroscope or accelerometer, have not been considered sensitive, Chen says. It turns out those sensors can measure shifting and rotation when a user taps the onscreen keyboard, and a machine learning algorithm can predict which keys are pressed. “It gives you enough information that would improve your guessing, much better than a random guess,” Chen says.
A different smartphone app, Soundcomber, also figures out what numbers a user presses, thus inferring phone and credit card numbers. The telephone system uses a combination of two tones to stand for each of the 10 digits on a keypad; capturing those tones and performing a frequency analysis allows the attacker to tease out the digits. The phone’s microphone can also pick up different sounds the phone emits when the user presses a key, gaining another piece of identifying information.
The app also performs “light-weight” speech recognition, focusing only on digits, says Kehuan Zhang, assistant professor at the Chinese University of Hong Kong, who helped develop Soundcomber as a student at Indiana University, Bloomington. The attacker would first call a series of banks and work his way through the various prompts on the automated system, from which language he preferred to different options to check a balance or make a payment, developing a model for each bank. Then, when a user called the bank, Soundcomber would deduce where in the automated system he was and record, say, his account number or Social Security number.
In all these cases, one defense is to add noise to the data being processed, making it more difficult for attackers relying on statistical analysis to tease out the signal they are after. But, like Rothblum’s compiler, that increases the burden on computation, rendering a program less efficient. The memory attack might be thwarted by disabling the proc system, but Jana says that would cause a lot of legitimate programs to malfunction. Likewise, blocking Internet access to the accelerometer might break some desirable apps.
Chen has tried to address the problem with AndroidLeaks, a program that automatically examines smartphone applications and looks for potential information leaks. Users can then decide to restrict the permissions given to apps or not to use them at all. Zhang, along with colleagues from Indiana and Shuo Chen of Microsoft Research, developed another program, Sidebuster, to examine the source code of Web applications. “We try to find out where information could be leaked and try to quantify the leaks,” Zhang says. They have discovered vulnerabilities in popular online tax and investment software.
“It’s very difficult to come up with general defense solutions,” Zhang says. Rothblum’s approach, for instance, would not work with Touchlogger, which records not the internal state of the system but its interaction with the user. Rothblum hopes his compiler can secure many algorithms from different sorts of side-channel attack. But until it is developed into something practical for widespread deployment, the best defense may be looking for potential leaks and plugging them when they are found.
Further Reading
Cai, L., and Chen, H.
TouchLogger: Inferring keystrokes on touch screen from smartphone motion, 6th USENIX Workshop on Hot Topics in Security, San Francisco, CA, Aug. 9, 2011.
Goldwasser, S. and Rothblum, G.N.
How to computer in the presence of leakage, Electronic Colloquium on Computational Complexity 19, 10, Feb. 5, 2012.
Jana, S., and Shmatikov, V.
Memento: Learning secrets from process footprints, IEEE Symposium on Security and Privacy, San Francisco, CA, May 2023 2012.
Schlegel R., Zhang, K., Zhou, X., Intwala, M., Kapadia, A., and Wang, X.
Soundcomber: A stealthy and context-aware sound trojan for smartphones, Proceedings of the 18th Annual Network & Distributed System Security Symposium, San Diego, CA, Feb. 69, 2011.
University of Washington Television
Side Channels and Clouds: New Challenges in Cryptography, http://www.youtube.com/watch?v=6hQ5kvaEFkw, Aug. 30, 2010.
Join the Discussion (0)
Become a Member or Sign In to Post a Comment