Paper 2016/044

Defeating the Ben-Zvi, Blackburn, and Tsaban Attack on the Algebraic Eraser

Iris Anshel, Derek Atkins, Dorian Goldfeld, and Paul E. Gunnells

Abstract

The \emph{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.