AES crypto broken by 'groundbreaking' attack

Faster than simply brute-forcing


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.


Other stories you might like

  • India extends deadline for compliance with infosec logging rules by 90 days
    Helpfully announced extension on deadline day

    Updated India's Ministry of Electronics and Information Technology (MeitY) and the local Computer Emergency Response Team (CERT-In) have extended the deadline for compliance with the Cyber Security Directions introduced on April 28, which were due to take effect yesterday.

    The Directions require verbose logging of users' activities on VPNs and clouds, reporting of infosec incidents within six hours of detection - even for trivial things like unusual port scanning - exclusive use of Indian network time protocol servers, and many other burdensome requirements. The Directions were purported to improve the security of local organisations, and to give CERT-In information it could use to assess threats to India. Yet the Directions allowed incident reports to be sent by fax – good ol' fax – to CERT-In, which offered no evidence it operates or would build infrastructure capable of ingesting or analyzing the millions of incident reports it would be sent by compliant organizations.

    The Directions were roundly criticized by tech lobby groups that pointed out requirements such as compelling clouds to store logs of customers' activities was futile, since clouds don't log what goes on inside resources rented by their customers. VPN providers quit India and moved their servers offshore, citing the impossibility of storing user logs when their entire business model rests on not logging user activities. VPN operators going offshore means India's government is therefore less able to influence such outfits.

    Continue reading
  • The App Gap and supply chains: Purism CEO on what's ahead for the Librem 5 USA
    Freedoms eroded, iOS-Android duopoly under fire, chip sources questioned – it's all an opportunity for this phone

    Interview In June, Purism began shipping a privacy-focused smartphone called Librem 5 USA that runs on a version of Linux called PureOS rather than Android or iOS. As the name suggests, it's made in America – all the electronics are assembled in its Carlsbad, California facility, using as many US-fabricated parts as possible.

    While past privacy-focused phones, such as Silent Circle's Android-based Blackphone failed to win much market share, the political situation is different now than it was seven years ago.

    Supply-chain provenance has become more important in recent years, thanks to concerns about the national security implications of foreign-made tech gear. The Librem 5 USA comes at a cost, starting at $1,999, though there are now US government agencies willing to pay that price for homegrown hardware they can trust – and evidently tech enthusiasts, too.

    Continue reading
  • America edges closer to a federal data privacy law, not that anyone can agree on it
    What do we want? Safeguards on information! How do we want it? Er, someone help!

    American lawmakers held a hearing on Tuesday to discuss a proposed federal information privacy bill that many want yet few believe will be approved in its current form.

    The hearing, dubbed "Protecting America's Consumers: Bipartisan Legislation to Strengthen Data Privacy and Security," was overseen by the House Subcommittee on Consumer Protection and Commerce of the Committee on Energy and Commerce.

    Therein, legislators and various concerned parties opined on the American Data Privacy and Protection Act (ADPPA) [PDF], proposed by Senator Roger Wicker (R-MS) and Representatives Frank Pallone (D-NJ) and Cathy McMorris Rodgers (R-WA).

    Continue reading
  • Google battles bots, puts Workspace admins on alert
    No security alert fatigue here

    Google has added API security tools and Workspace (formerly G-Suite) admin alerts about potentially risky configuration changes such as super admin passwords resets.

    The API capabilities – aptly named "Advanced API Security" – are built on top of Apigee, the API management platform that the web giant bought for $625 million six years ago.

    As API data makes up an increasing amount of internet traffic – Cloudflare says more than 50 percent of all of the traffic it processes is API based, and it's growing twice as fast as traditional web traffic – API security becomes more important to enterprises. Malicious actors can use API calls to bypass network security measures and connect directly to backend systems or launch DDoS attacks.

    Continue reading

Biting the hand that feeds IT © 1998–2022