Cryptographers discover method to break AES security standard
Aug. 19, 2011
Internet security researchers have discovered a method to break the Advanced Encryption Standard (AES) used to protect everything from top-secret government documents, confidential medical files, social insurance numbers, credit cards and online banking transactions.
The method, which was published in a paper presented Aug. 17 as part of the Crypto 2011 Conference in Santa Barbara, allows potential hackers to recover AES secret keys up to five times faster than previously possible.
This represents a major security issue to many organizations. The method introduces a technique known as 'biclique cryptanalysis' to delete just two bits of data from 128, 192 and 256-bit security encryption keys.
“This research is groundbreaking because it is the first technique discovered of actually breaking single-key AES that is slightly faster than brute force,” said Nate Lawson, a cryptographer and the principal security consultant at Root Labs. “But I must also tell you that it doesn't compromise AES in any practical way.”
Lawson also added that it would still take "trillions of years" to recover strong AES keys using the biclique technique, which is a variant of what's known as a meet-in-the-middle cryptographic attack. This method works both from the inputs and outputs of AES towards the middle, reusing partial computation results to speed up the brute-force key search.
The technique is designed to cut down on the time an attacker needs to fully recover the key.
Lawson added "This technique is a divide-and-conquer attack. To find an unknown key, they partition all the possible keys into a set of groups. This is possible because AES subkeys only have small differences between round numbers. They can then perform a smaller search for the full key since they can reuse partial bits of the key in later phases of the computation."
It's impressive work but there's still no better cipher to use than AES for now. And AES still remains the preferred cryptographic scheme of the U.S. government and a few others. The National Institute of Standards and Technology commissioned AES ten years ago as a replacement for the DES, or Digital Encryption Standard, which wasn't as secure and became obsolete.
The research is the work of Andrey Bogdanov of Katholieke Universiteit in Leuven; Microsoft Research's Dmitry Khovratovich; and Christian Rechberger of Ecole Normale Superieure in Paris.
Both Bogdanov and Rechberger took leave from their positions to work on the project for Microsoft Research that started in October 2010.
In other internet security news
Internet security specialists have developed an Android user application that logs various keystrokes using a smartphone's sensors to measure the locations a user taps on the touch screen. TouchLogger, as their demo app is called, allowed its creators at the University of California to demonstrate a security hole in most smartphones and tablets that has largely gone unnoticed up until today.
While most of these devices lack physical keyboards that have long been known to leak user input, they nonetheless remain very susceptible to outside monitoring through similar side-channel attacks, and that represents a big security risk, according to the researchers.
Whereas eavesdroppers measure sound and electromagnetic radiation to capture input from traditional keyboards, they can also monitor the motion of the mobile device to achieve much the same result from a touch screen-- something that was never given any thought until this latest discovery.
“Motion sensors, such as accelerometers and gyroscopes, may also be used to infer keystrokes as well,” the researchers wrote in a paper presented last week at the HotSec 2011 workshop in San Francisco.
“When the user types on the soft keyboard on a smartphone (especially if the user holds the phone by hand rather than placing it on a fixed surface), the phone vibrates. We discovered that keystroke vibration on touch screens are highly correlated to the keys being typed,” the researcher wrote.
And applications like TouchLogger and others that are similar could be significant since they bypass protections built into both the Android OS and Apple's competing iOS that prevent a program from reading keystrokes unless it's active and receives focus from the screen.
It was designed to work on an HTC Evo 4G smartphone. It had an accuracy rate of more than 70 percent of the input typed into the number-only soft keyboard of the device. The app worked by using the phone's accelerometer to guess estimate the motion of the device each time a soft key was pressed.
With just a few minor adjustments, the security researchers also believe that they can expand the effectiveness of TouchLogger, as well as the devices it will work on-- creating major security concerns for users in the enterprise segment. So far, no significant amount of testing has been done on RIM's BlackBerry system, but it's only a question of time until the researchers begin.
“The tablet has a larger screen, so hopefully we can get a higher accuracy rate on a Qwerty keyboard,” said Liang Cai, a graduate student in U.C. Davis's computer science department who collaborated with his advisor Hao Chen. “We didn't really try it on a large scale of devices, but we will soon.”
Besides targeting devices with larger touch screens, the researchers added that TouchLogger could also be improved by using other sensors built into the targeted device. Prime candidates include gyroscopes to measure the rate of rotation and a camera to further detect motion.
But for now, all they are hoping is to get the word out that the motion detected by a smart device's own sensors could expose highly valuable information, including passwords, social security numbers and credit card information.
“We hope to raise the awareness of motion as a significant side channel that may leak confidential data,” they wrote.
In other internet security news
The well known hacking group Anonymous took credit Monday for an online attack targeting San Francisco's rapid transit system. The group has a reputation for targeting mission-critical and sensitive computer networks across the globe, and this one isn't any different than previous attacks made by the group.
But for now, their motives are still unknown, however. In a news release attributed to the group, and backed up by related Twitter pages, Anonymous said it would take down the website of the Bay Area Rapid Transit System, known as BART, between noon and 6.00 PM Pacific time yesterday.
The move is in response to the organization's management decision to cut off cellphone signals at select subway stations in response to a planned protest last week.
"By cutting off cell phone service, you have not only threatened your citizens' safety, you have also performed an act of censorship," a seemingly computer-generated voice said in a video posted online Sunday afternoon. "And by doing this, you have angered Anonymous."
Yesterday afternoon, a link off BART's website to myBART.org apparently had been hacked as well. It showed a page featuring, among other items, the Anonymous logo -- a smirking mask above two crossed swords, all on a black background.
Additionally, Twitter traffic related to Anonymous also said that the hackers had been able to get into BART's internal network as well. Several related items and documents were posted, including one claiming to be "the User Info Database of MyBart.gov." This had e-mails and, in some cases, phone numbers of hundreds of people.
"We apologize to any citizen that has his information published, but you should go to BART and ask them why your information wasn't secure with them in the first place," the posted item said. "Also-- don't worry-- probably the only information that will be abused from this database is that of BART employees, not you."
Source: The Crypto 2011 Conference.
You can link to the Internet Security web site as much as you like.