A potential standard for securing network-connected pacemakers, automobiles, and other lightweight devices has suffered a potentially game-over setback after researchers developed a practical attack that obtains its secret cryptographic key.
Known as Algebraic Eraser, the scheme is a patented way to establish public encryption keys without overtaxing the limited amounts of memory and computational resources that often constrain so-called Internet of Things (IoT) devices. Developed by scientists from Shelton, Connecticut-based SecureRF, it’s similar to the Diffie-Hellman key exchange in that it allows two parties who have never met to securely establish a key over an insecure channel.
The big advantage Algebraic Eraser has had is its ability to work using only a tiny fraction of the power and computing resources required by more traditional key exchanges. Algebraic Eraser has looked so promising that it’s an underlying technology in ISO/IEC AWI 29167-20, a proposed International Organization for Standardization specification for securing radio frequency identification-enabled technologies, wireless sensors, embedded systems, and other devices where security is paramount and computing resources are minimal.
Now, academic researchers say the Algebraic Eraser suffers a weakness that’s so severe it compromises the entire security of the proposed ISO standard when the Algebraic Eraser is used. To underscore their assessment, the researchers developed an attack that requires just eight hours to recover a shared 128-bit key negotiated using the Algebraic Eraser. (The shared key acts as the shared secret key that encrypts and decrypts data stored on a device.) With enhancements, they said, the attack can probably be carried out much more quickly. The underlying weakness means there could be potentially disastrous consequences if it’s widely used.
“A key exchange might be used to secure the long-term key for an implanted medical device, say, or a networked vehicle,” Simon Blackburn, a mathematics professor at Royal Holloway University of London and co-author of a paper titled A Practical Cryptanalysis of the Algebraic Eraser, wrote in an e-mail to Ars. “Compromising the key might allow malicious code to be inserted into the device or might allow the device to be remotely controlled by an adversary. I would not want a hacker to take control of my car or my pacemaker.”
“Serious doubt”
In the paper, Blackburn—along with Bar-Ilan University mathematicians Adi Ben-Zvi and Boaz Tsaban—said they chose to examine Algebraic Eraser and a SecureRF-developed implementation of it called Colored Burau Key Agreement Protocol (CBKAP) because of its potential to become ubiquitous in the IoT landscape, where cars, medical devices, and many other traditional devices are connected to the Internet or similar types of networks.
“IoT is a growth area, where current widely accepted public key techniques struggle to operate due to tight efficiency constraints,” they wrote. “It is likely that solutions which are efficient enough for these applications will become widely deployed, and the nature of these applications make system changes after deployment difficult. Thus, it is vital to scrutinise the security of systems such as the Algebraic Eraser early in the standardisation process, to ensure only secure schemes become ubiquitous.”
The researchers went on to say that “because our attack efficiently recovered the shared key of the CBKAP for recommended parameter sizes, using parameters provided by SecureRF, we believe the results presented here cast serious doubt on the suitability of the Algebraic Eraser for the applications proposed.”
In contrast to previous attacks on the Algebraic Eraser, Blackburn said the latest attack recovers the shared secret key directly from the public key of one user (usually referred to as “Alice” by cryptographers) and the messages exchanged between Alice and a second user (usually referred to as “Bob”) rather than attempting to reconstruct the random information that Alice or Bob generated.
“The approach avoids the problems with a previous attack, which got stuck when trying to find part of this random information,” Blackburn told Ars. “This new twist allows us to reduce the problem of breaking the scheme to linear algebra and a problem in small permutation groups.”
No threat
SecureRF CEO and President Louis Parks told Ars he doesn’t believe the attack is as practical as the recent paper reports, for several reasons. For one, he said the shared secret extraction technique doesn’t scale. For another, he said, the attack won’t work when different parameters are used for the cryptosystem, which he referred to as Algebraic Eraser Diffie-Hellman, or AEDH.
“Our conclusion is that this attack does not represent a threat to the practical deployment of AEDH in applications with properly chosen parameters,” he wrote in an abstract to a research paper he said he plans to publish in response to the attack.
In an e-mail to Ars, Parks said his company has no plans to revise claims that the Algebraic Eraser has been “In public domain for 10 years with no successful attacks.”.
“It is apparent that we may have provided ‘weak parameters’ that were being used for internal testing and sent to the researchers when requested,” Parks wrote. “We are addressing both this area of parameters and our process for approving secure parameters. But his attack does not claim to have ‘broken’ our method or recover any secret material. It claims to be able to recover a computed shared secret. If true, then like RSA and others, we will need to identify these weak parameters to our partners and ensure they are not used.”
For his part, Blackburn said he was surprised to learn that Parks said the attack doesn’t scale and doesn’t work as well as reported in the paper. Blackburn said he also doesn’t understand why SecureRF scientists would have provided parameters they didn’t believe would withstand the new attack, and he’s eager to see the final paper Parks has discussed. Several prominent mathematicians have taken to social media in recent days to echo Blackburn’s claim that the new attack essentially breaks the Algebraic Eraser and renders it all but dead.
Until SecureRF has had time to present its final paper, such pronouncements are preliminary. But based on the new attack, it’s clear that the drafters of ISO/IEC AWI 29167-20 should take a long, hard look at the Algebraic Eraser now. If that attack works the way Blackburn and his peers say it does, the time to address this crippling weakness is now—not when the underlying Algebraic Eraser is embedded in millions of devices.
Source:https://arstechnica.com/
Working as a cyber security solutions architect, Alisa focuses on application and network security. Before joining us she held a cyber security researcher positions within a variety of cyber security start-ups. She also experience in different industry domains like finance, healthcare and consumer products.
