Feeds

AES crypto broken by 'groundbreaking' attack

Faster than simply brute-forcing

Beginner's guide to SSL certificates

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.

Internet Security Threat Report 2014

More from The Register

next story
'Regin': The 'New Stuxnet' spook-grade SOFTWARE WEAPON described
'A degree of technical competence rarely seen'
You really need to do some tech support for Aunty Agnes
Free anti-virus software, expires, stops updating and p0wns the world
You stupid BRICK! PCs running Avast AV can't handle Windows fixes
Fix issued, fingers pointed, forums in flames
Privacy bods offer GOV SPY VICTIMS a FREE SPYWARE SNIFFER
Looks for gov malware that evades most antivirus
Patch NOW! Microsoft slings emergency bug fix at Windows admins
Vulnerability promotes lusers to domain overlords ... oops
HACKERS can DELETE SURVEILLANCE DVRS remotely – report
Hikvision devices wide open to hacking, claim securobods
prev story

Whitepapers

Why cloud backup?
Combining the latest advancements in disk-based backup with secure, integrated, cloud technologies offer organizations fast and assured recovery of their critical enterprise data.
A strategic approach to identity relationship management
ForgeRock commissioned Forrester to evaluate companies’ IAM practices and requirements when it comes to customer-facing scenarios versus employee-facing ones.
How to determine if cloud backup is right for your servers
Two key factors, technical feasibility and TCO economics, that backup and IT operations managers should consider when assessing cloud backup.
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.
Choosing a cloud hosting partner with confidence
Download Choosing a Cloud Hosting Provider with Confidence to learn more about cloud computing - the new opportunities and new security challenges.