Feeds

AES crypto broken by 'groundbreaking' attack

Faster than simply brute-forcing

Boost IT visibility and business value

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.

Gartner critical capabilities for enterprise endpoint backup

More from The Register

next story
Microsoft: We plan to CLEAN UP this here Windows Store town
Paid-for apps that provide free downloads? Really
Snowden on NSA's MonsterMind TERROR: It may trigger cyberwar
Plus: Syria's internet going down? That was a US cock-up
Who needs hackers? 'Password1' opens a third of all biz doors
GPU-powered pen test yields more bad news about defences and passwords
e-Borders fiasco: Brits stung for £224m after US IT giant sues UK govt
Defeat to Raytheon branded 'catastrophic result'
Hear ye, young cyber warriors of the realm: GCHQ wants you
Get involved, get a job and then never discuss work ever again
Chinese hackers spied on investigators of Flight MH370 - report
Classified data on flight's disappearance pinched
Microsoft cries UNINSTALL in the wake of Blue Screens of Death™
Cache crash causes contained choloric calamity
prev story

Whitepapers

Implementing global e-invoicing with guaranteed legal certainty
Explaining the role local tax compliance plays in successful supply chain management and e-business and how leading global brands are addressing this.
7 Elements of Radically Simple OS Migration
Avoid the typical headaches of OS migration during your next project by learning about 7 elements of radically simple OS migration.
BYOD's dark side: Data protection
An endpoint data protection solution that adds value to the user and the organization so it can protect itself from data loss as well as leverage corporate data.
Consolidation: The Foundation for IT Business Transformation
In this whitepaper learn how effective consolidation of IT and business resources can enable multiple, meaningful business benefits.
High Performance for All
While HPC is not new, it has traditionally been seen as a specialist area – is it now geared up to meet more mainstream requirements?