Feeds

AES crypto broken by 'groundbreaking' attack

Faster than simply brute-forcing

Reducing security risks from open source software

Updated Cryptographers have discovered a way to break the Advanced Encryption Standard used to protect everything from top-secret government documents to online banking transactions.

The technique, which was published in a paper (PDF) presented Wednesday as part of the Crypto 2011 cryptology conference in Santa Barbara, California, allows attackers to recover AES secret keys up to five times faster than previously possible. It introduces a technique known as biclique cryptanalysis to remove about two bits from 128-, 192-, and 256-bit keys.

“This research is groundbreaking because it is the first method of breaking single-key AES that is (slightly) faster than brute force,” Nate Lawson, a cryptographer and the principal of security consultancy Root Labs, wrote in an email. “However, it doesn't compromise AES in any practical way.”

He said 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 reduce the time it takes an attacker to recover the key.

Lawson continued:

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 rounds. They can then perform a smaller search for the full key because they can reuse partial bits of the key in later phases of the computation.

It's impressive work but there's no better cipher to use than AES for now.

AES remains the favored cryptographic scheme of the US government. The National Institute of Standards and Technology commissioned AES in 2001 as a replacement for the DES, or Digital Encryption Standard, which was showing signs of its age.

The research is the work of Andrey Bogdanov of Katholieke Universiteit Leuven; Microsoft Research's Dmitry Khovratovich; and Christian Rechberger of Ecole Normale Superieure in Paris. Bogdanov and Rechberger took leave from their positions to work on the project for Microsoft Research. ®

Update

Vulture Central has been deluged with missives from outraged readers complaining about the use of the word “broken” in the headline. "Broken" in cryptography is the result of any attack that is faster than brute force. The biclique technique described here allows attackers to recover keys up to five times faster than brute-force. AES may not be completely broken, but it's broken nonetheless.

What's more, theoretical attacks against widely used crypto algorithms often get better over time. As Root Labs' Lawson has noted, MD5 wasn't compromised in a single 2004 paper. Rather, people successively found better and better attacks against it, starting in the mid 1990's.

Thanks to Reg reader Kevin 3 for bringing the facts to the discussion with this comment.

Mobile application security vulnerability report

More from The Register

next story
LibreSSL RNG bug fix: What's all the forking fuss about, ask devs
Blow to bit-spitter 'tis but a flesh wound, claim team
Microsoft: You NEED bad passwords and should re-use them a lot
Dirty QWERTY a perfect P@ssword1 for garbage websites
Manic malware Mayhem spreads through Linux, FreeBSD web servers
And how Google could cripple infection rate in a second
NUDE SNAPS AGENCY: NSA bods love 'showing off your saucy selfies'
Swapping other people's sexts is a fringe benefit, says Snowden
Own a Cisco modem or wireless gateway? It might be owned by someone else, too
Remote code exec in HTTP server hands kit to bad guys
British data cops: We need greater powers and more money
You want data butt kicking, we need bigger boots - ICO
Crooks fling banking Trojan at Japanese smut site fans
Wait - they're doing online banking with an unpatched Windows PC?
NIST told to grow a pair and kick NSA to the curb
Lrn2crypto, oversight panel tells US govt's algorithm bods
prev story

Whitepapers

Top three mobile application threats
Prevent sensitive data leakage over insecure channels or stolen mobile devices.
The Essential Guide to IT Transformation
ServiceNow discusses three IT transformations that can help CIO's automate IT services to transform IT and the enterprise.
Mobile application security vulnerability report
The alarming realities regarding the sheer number of applications vulnerable to attack, and the most common and easily addressable vulnerability errors.
How modern custom applications can spur business growth
Learn how to create, deploy and manage custom applications without consuming or expanding the need for scarce, expensive IT resources.
Consolidation: the foundation for IT and business transformation
In this whitepaper learn how effective consolidation of IT and business resources can enable multiple, meaningful business benefits.