Feeds

AES crypto broken by 'groundbreaking' attack

Faster than simply brute-forcing

Choosing a cloud hosting partner with confidence

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.

Beginner's guide to SSL certificates

More from The Register

next story
Russian hackers exploit 'Sandworm' bug 'to spy on NATO, EU PCs'
Fix imminent from Microsoft for Vista, Server 2008, other stuff
FYI: OS X Yosemite's Spotlight tells Apple EVERYTHING you're looking for
It's on by default – didn't you read the small print?
Microsoft pulls another dodgy patch
Redmond makes a hash of hashing add-on
'LulzSec leader Aush0k' found to be naughty boy not worthy of jail
15 months home detention leaves egg on feds' faces as they grab for more power
Forget passwords, let's use SELFIES, says Obama's cyber tsar
Michael Daniel wants to kill passwords dead
Kill off SSL 3.0 NOW: HTTPS savaged by vicious POODLE
Pull it out ASAP, it is SWISS CHEESE
Facebook slurps 'paste sites' for STOLEN passwords, sprinkles on hash and salt
Zuck's ad empire DOESN'T see details in plain text. Phew!
prev story

Whitepapers

Forging a new future with identity relationship management
Learn about ForgeRock's next generation IRM platform and how it is designed to empower CEOS's and enterprises to engage with consumers.
Cloud and hybrid-cloud data protection for VMware
Learn how quick and easy it is to configure backups and perform restores for VMware environments.
Three 1TB solid state scorchers up for grabs
Big SSDs can be expensive but think big and think free because you could be the lucky winner of one of three 1TB Samsung SSD 840 EVO drives that we’re giving away worth over £300 apiece.
Reg Reader Research: SaaS based Email and Office Productivity Tools
Read this Reg reader report which provides advice and guidance for SMBs towards the use of SaaS based email and Office productivity tools.
Security for virtualized datacentres
Legacy security solutions are inefficient due to the architectural differences between physical and virtual environments.