A Review of the Algebraic Eraser Protocol on Embedded Devices

By Harmon Herring

Background

            Embedded devices exist all around us and become a more integrated part of our lives as each day passes. Whether by interacting with cars, household appliances, or with IOT devices from weird startups, we depend on embedded devices for much more than we realize at first glance. That’s why it’s so incredibly important that these devices are communicating securely – one slip-up and your vehicle could start accepting “security updates” from a malicious third-party.

            Asymmetric (or public key) cryptography lies at the heart of many frequent operations performed by embedded devices. Asymmetric cryptography is integral for providing message integrity, message authenticity, and creating a secure channel through which a private key can be shared. However, asymmetric cryptographic functions are many times more computationally taxing than symmetric cryptographic functions. The reason for this is twofold: it’s more mathematically complex to publish the public key without also revealing the private key, and asymmetric encryption systems avoid a deterministic ciphertext by adding randomness – this increases the size of the ciphertext.


(Kumari)

            How does the increased computational complexity of asymmetric cryptography actually affect embedded devices though? For starters, it’s important to recognize that embedded devices typically have strikingly fewer resources available to them than a personal computer. This means that those asymmetric cryptographic operations are going to take a lot of extra time to complete, slowing down users. Unfortunately, this can also lead to businesses taking security shortcuts in an effort to make a product that’s easier to use.

            What are the current options available to developers? RSA (Rivest-Shamir-Adleman) and ECC (elliptic curve cryptography) schemes are the most commonly used asymmetric cryptosystems. RSA has been around longer and certainly stood through the test of time. ECC schemes are somewhat newer and use fewer key bits to achieve a similar level of security to RSA. ECC schemes are also significantly faster than RSA for private-key operations and key generation (Microchip). Unfortunately, even though ECC schemes are faster and more efficient than RSA, their performance on embedded systems still leaves a lot to be desired.

Algebraic Eraser

            Algebraic Eraser is a proprietary, asymmetric key agreement protocol owned by SecureRF that was born out of a need for more efficient cryptographic functions on embedded devices, particularly on those that make up the Internet of Things. SecureRF claims performance improvements of greater than 60 times that of ECC schemes in terms of speed and power usage at a 128-bit security level (Atkins).


(SecureRF)

            Significant performance improvements aren’t all that Algebraic Eraser has to offer. “E-Multiplication” (the “foundational engine” of Algebraic Eraser, according to SecureRF) can also be used to create hashes, generate pseudo-random numbers, create block or stream ciphers, or create a digital signature algorithm. The benefit of this really shines on embedded devices, allowing manufacturers to save space and resources when implementing Algebraic Eraser at the hardware level.

Flaws

            To begin with, Algebraic Eraser is proprietary, closed source, and patented by SecureRF. Because of this, it will never undergo the same level of scrutiny that open-source material undergoes. If a business situation arises that somehow impacts Algebraic Eraser, you (as a user) will be at the total mercy of SecureRF’s business decisions. When/if vulnerabilities are found, you’ll be at the complete mercy of the patent-holder (SecureRF) to fix the problem and publish any modifications. As unfortunately as it turns out, finding vulnerabilities in this proposed system hasn’t been too uncommon.

            The first notable, published attack on the asymmetric Algebraic Eraser Key-Agreement Protocol revealed that when the E-Multiplication initial matrix is chosen randomly, an attacker is able to determine the shared key, using only the publicly shared parameters (Kalka). The authors of this attack then demonstrated how it could be used against the SecureRF implementation, Colored-Burau Key Agreement Protocol, in a real-world scenario using less than 64 megabytes of memory. Luckily, the authors of Algebraic Eraser responded to this proposed attack and updated their protocol with instruction on how to choose parameters that wouldn’t be vulnerable to the demonstrated attack.

            The latest notable attack on Algebraic Eraser was by Simon Blackburn and Matthew Robshaw, who published a paper called A Practical Cryptanalysis of the Algebraic Eraser in which they demonstrated several possible attacks against Algebraic Eraser and SecureRF implementations of Algebraic Eraser. Ultimately, they were able to compute the generated secret key based on the shared public key when using parameters provided to them directly from SecureRF (ARSTECHNICA). In SecureRF’s response to this paper, they claimed that the parameters used for the attack were abnormally weak and that the described attack wouldn’t be feasible with properly chosen parameters. However, SecureRF has yet to publish a paper disproving Blackburn’s findings and has not supplied what would be considered “properly chosen parameters”.

            Ultimately, it seems that Algebraic Eraser will fall the same way as many other proprietary materials have. The findings of Blackburn and Robshaw were published while SecureRF was attempted to have their protocol included as a part of ISO/IEC 29167. This would have Algebraic Eraser being used as the crypto suite for a large number of devices that perform identification and authentication using radio frequency. However, SecureRF’s proposal was rejected in 2019.

Conclusion

            At this point, it’s clear that there are some serious problems with Algebraic Eraser and specifically with the SecureRF implementations of Algebraic Eraser. Several well-known mathematicians and security experts have warned others to stay away from SecureRF and touted some of their work as “snake-oil”. For example, Bruce Schneier (Schneier) has published a few blog posts on SecureRF, their lack of published cryptography papers, and a few signs that make him believe SecureRF is touting what he calls “snake-oil”. He recommends staying away from them.

            Through my research, it’s been made clear to me that it’s incredibly important to have knowledgeable professionals auditing the tools that are spewed out into the world. Without the work of many who have reviewed Algebraic Eraser, it’d be possible for an insecure tool to put many at risk. I’d like to end with a quote from Simon Blackburn – “IoT is a growth area […] 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 scrutinize the security of systems such as the Algebraic Eraser early in the standardization process, to ensure only secure schemes become ubiquitous.”

References

“RSA vs. ECC Comparison for Embedded Systems.” Https://Www.microchip.com/Content/Dam/Mchp/Documents/SCBU/ProductDocuments/SupportingCollateral/00003442A.Pdf, Microchip, 4 Apr. 2020, www.microchip.com/content/dam/mchp/documents/SCBU/ProductDocuments/SupportingCollateral/00003442A.pdf.

Atkins, Derek. “Algebraic EraserTM: A Lightweight, Efficient Asymmetric Key Agreement Protocol for Use in No-Power, Low-Power, and IoT Devices .” SecureRF, SecureRF, csrc.nist.gov/csrc/media/events/lightweight-cryptography-workshop-2015/documents/papers/session8-atkins-paper.pdf.

Kalka, Arkadius, et al. “Short Expressions of Permutations as Products and Cryptanalysis of the Algebraic Eraser.” Advances in Applied Mathematics, Academic Press, 22 Mar. 2012, www.sciencedirect.com/science/article/pii/S0196885812000267?via%3Dihub.

Schneier, Bruce. Schneier on Security, 9 Oct. 2016, www.schneier.com/blog/archives/2006/10/the_doghouse_se.html.

Kumari, Ranjitha, and B Padmavathi. “A Survey on Performance Analysis of DES, AES and RSA Algorithm along with LSB Substitution Technique.” International Journal of Science and Research, India Online, 4 Apr. 2013, www.ijsr.net/archive/v2i4/IJSRON120134.pdf.

Blackburn, Simon R, et al. “A Practical Cryptanalysis of the Algebraic Eraser.” A Practical Cryptanalysis of the Algebraic Eraser | Proceedings, Part I, of the 36th Annual International Cryptology Conference on Advances in Cryptology — CRYPTO 2016 – Volume 9814, 1 Aug. 2016, dl.acm.org/doi/abs/10.1007/978-3-662-53018-4_7.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s