IoT Security Blog

Articles and Posts on IoT Security, Embedded Systems, and the Internet of Things

Cryptanalysis of the Algebraic Eraser Diffie-Hellman key agreement protocol by Ben-Zvi-Blackburn-Tsaban

Analysis of cryptographic methods is a regular event, and it helps to identify areas requiring further research and possible improvement, weak keys or parameters, and in some very rare cases an actual weakness in a method (see SHA-1 research). We encourage reviews and analysis of our methods and make direct requests at conferences we attend throughout the year.

On November 13, 2015, a group of researchers posted an analysis of our Algebraic Eraser cryptosystem. We provided these researchers with a set of parameters and keys for their work. The analysis focused on recovering a computed shared secret. Their work does not make any claims about the security of our method or attempt to recover any secret parameters and keys. Rather, their analysis claims to recover the computed shared secret resulting from a key exchange and, in doing so, may have identified a weak parameter set. This is a regular event in Public-Key systems (look at RSA over the years).

These researchers did not retrieve any private keys or private data. They did not break the Algebraic Eraser system, or reverse the hard problems upon which our method is based.

Within days of receiving this paper, which requires careful analysis itself due to the many conjectures it uses to suggest their analysis is valid, we were able to devise a method to thwart the researchers’ algorithm, and also show that alternate parameter choices would make their attack fail. We will provide a full response, in the form of a published paper, and we are gathering the necessary data at this time. The abstract of our forthcoming paper is posted below.

The researchers may have identified a weak set of parameters and keys, which we appreciate. This type of analysis is part of the ongoing quality assurance process for Public-Key methods, and the outcome will make our solution even stronger.

~Louis Parks, CEO and Derek Atkins, CTO

Abstract and paper link updated January 26, 2016.

Defeating the Ben-Zvi, Blackburn, and Tsaban Attack on the Algebraic Eraser
Iris Anshel, Derek Atkins, Dorian Goldfeld, Paul E. Gunnells

The Algebraic Eraser Diffie Hellman (AEDH) protocol was introduced in 2005 and published in 2006 by I. Anshel, M. Anshel, D. Goldfeld, and S. Lemieux as a protocol suitable for use on platforms with constrained computational resources, such as FPGAs, ASICs, and wireless sensors. It is a group-theoretic cryptographic protocol that allows two users to construct a shared secret via a Diffie Hellman-type scheme over an insecure channel.
Building on the refuted 2012 permutation-based attack of Kalka Teichner Tsaban (KKT), Ben-Zvi, Blackburn, and Tsaban (BBT) present a heuristic attack, published November 13, 2015, that attempts to recover the AEDH shared secret. In their paper BBT reference the AEDH protocol as presented to ISO for certification (ISO 29167-20) by SecureRF. The ISO 29167-20 draft contains two profiles using the Algebraic Eraser. One profile is unaffected by this attack; the second profile is subject to their attack provided the attack runs in real time.This is not the case in most practical deployments.
The BBT attack is simply a targeted attack that does not attempt to break the method, system parameters, or recover any private keys. Rather, its limited focus is to recover the shared secret in a single transaction. In addition, the BBT attack is based on several conjectures that are assumed to hold when parameters are chosen according to standard distributions, which can be mitigated, if not avoided. This paper shows how to choose special distributions so that these conjectures do not hold making the BBT attack ineffective for braid groups with sufficiently many strands. Further, the BBT attack assumes that certain data is available to an attacker, but there are realistic deployment scenarios where this is not the case, making the attack fail completely. In summary, the BBT attack is flawed (with respect to the SecureRF ISO draft) and, at a minimum, over-reaches as to its applicability.

Read the full paper via PDF or at http://arxiv.org/abs/1601.04780.