16
$\begingroup$

Algebraic Eraser™ is a relatively new asymmetric key agreement protocol (also designated the Colored Burau Key Agreement Protocol), based on a simultaneous conjugacy search problem in a braid group.

An initial exposition is: Iris Anshel, Michael Anshel, Dorian Goldfeld, Stephane Lemieux, Key agreement, the Algebraic Eraser™, and lightweight cryptography, in Contemporary Mathematics 418 (2006) (free slightly later pdf). There has been two early, concurrent attacks:

Here's a recent introductory paper: Derek Atkins, Algebraic Eraser™: A lightweight, efficient asymmetric key agreement protocol for use in no-power, low-power, and IoT devices, accepted paper at Lightweight Cryptography Workshop 2015, with presentation by Paul E. Gunnells.

Algebraic Eraser™ has been proposed for standardization as ISO/IEC 29167-20 (currently an Approved Work Item). The company apparently petitioning for standardization and holding some related patents made available a description worded as a standard proposal (October 2015), and several other technical papers.

There is a recent claimed attack, improving on the Kalka-Teicher-Tsaban attack: Adi Ben-Zvi, Simon R. Blackburn, Boaz Tsaban, A Practical Cryptanalysis of the Algebraic Eraser, in arXiv:1511.03870 and eprint (November 12, 2015); and some controversy about it, according to this Ars Technica article. The aforementioned company made a preliminary analysis of the attack. They acknowledge that it applies to one of two profiles proposed for standardization, and recovers the shared secret key (but not the private key; hence my understanding is that the attack "only" compromises the confidentiality of past recorded sessions, or the integrity of the current session if it can be frozen long enough to carry the attack).

Disclaimer: I have not studied the above references in much depth.

I'm asking the status of the cryptosystem. In particular:

  • What was the claimed security level of the 5 challenges (with $q = 256$ and $n = 16$) solved in the recent attack?
  • Would the attack work for the B10F256 Keyset Parameters in normative Annex C.1 in the October 2015 description ? It supposedly

    provides a security level of 280 using a braid with 10 strands and a field of 256 (28)

  • Is the method by which these Keyset Parameters where generated public? They seem to include the matrix $m\in GL(n,\mathbb F)$ which careful choice was acknowledged critical to defeat the Kalka-Teicher-Tsaban attack, and I read in section 7 of the Atkins introductory paper these are [emphasis mine]

    chosen via a proprietary method

  • How can it be that only the second profile is affected, given that according to the description on section 2, it differs from the other only by having the public key obtained as part of a certificate? [emphasis mine]

    Profile [ii] (Certificate on Tag):
    The Interrogator begins by obtaining the Tag’s certificate (CERT_t). The Tag sends its certificate, which contains its public key (PUB_t), to the Interrogator. The Interrogator obtains PUB_t from CERT_t. The protocol then follows Profile [i]. This protocol allows for tracking the Tag via the Tag’s fixed CERT_t.

  • Are there significant differences between the October 2015 description and what was proposed for standardization, in 2014?
Improve this question
$\endgroup$
15
$\begingroup$

The first part of this partial self-answer uses additional information I received from Professor Simon R. Blackburn, one of the author of the recent attack.

The method used to generate parameters is not public, e.g. for the matrix $m\in GL(n,\mathbb F)$ which careful choice was acknowledged critical to defeat an earlier version of the attack. The authors of the new attack thus asked the company supporting Algebraic Eraser key exchange for standardization to provide "sample parameters that are proposed in practice"; that was before the standard proposal of October 2015 became public, which itself predates publication of the attack.

In the preliminary analysis of the attack, it is stated that the authors of the attack "may have identified a weak set of parameters and keys". This allegedly weak set was supplied by the company making the statement.

It had been previously claimed that parameters with $q=256$ and $n=16$, as used in the parameter sets provided as challenge (all solved within 8 hours by a single CPU and unoptimized code), were equivalent to 128-bit security (page 13 of the slides presented at NIST's Lightweight Cryptography Workshop 2015).

Professor Simon R. Blackburn did not immediately see a reason why the attack would not work for the B10F256 keyset parameters in the proposed standard (which I understand has claimed 80-bit security level, for $q=256$ and $n=10$). He expects the detailed code in a good implementation would be different to take advantage of smaller parameter sizes.

I have found nothing to support the assertion made in the preliminary analysis of the attack that "only the second profile is subject to (the) attack", for the meaning of profile in the proposed standard .

Right now, I can't trust the security of any profile in the proposed standard, because:

  • The cryptosystem failed in experimental challenges defined by its proponents, at a security level conjectured well above what has been proposed for standardization.
  • That follows a fix for a previous break, and another fix is announced; thus the method is in a break-and-fix cycle, and in the broken state.
  • The parameter generation method is not public; hence it is impossible to rule out that knowledge of that method would allow even better attacks.

PS: Ars Technica quoted a representative of the company supporting Algebraic Eraser key exchange for standardization as having written:

It is apparent that we may have provided 'weak parameters' that were being used for internal testing and sent to the researchers when requested (..) 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.

This statement is academically untenable: in a key exchange protocol, the "shared secret" is "secret material"; and recovering it constitutes a break.

Update following publication of Iris Anshel, Derek Atkins, Dorian Goldfeld and Paul E. Gunnells, Defeating the Ben-Zvi, Blackburn, and Tsaban Attack on the Algebraic Eraser, in Cryptology ePrint Archive (2016-01-18).

In this rebuttal, I found a single argument in support of the assertion that the attack does not apply to the first profile proposed for standardization:

In one of the profiles one party has access to a database that contains public key material for the other parties. Specifically, in this profile an attacker never has access to one of the public keys and, as a result, cannot mount the attack to derive the shared secret.

Come on! Six out of nine letters in public key are devoted to stating that everyone, including the attacker, knows that key; that's the very assumption motivating public-key cryptography. With the opposite assumption, we can use much simpler and lighter secret-key protocols. The proposed standard itself defines public key as: "public data item of an asymmetric pair, that can be made public".

Another argument given is:

the BBT attack is usually thousands of times slower (on a 4 GHz processor) than the running time of the AEDH protocol in a constrained device with limited computing power and memory. The second profile in the ISO 29167-20 draft is an authentication protocol whereby two users in a lightweight cryptographic setting run the AEDH key agreement protocol and obtain a shared secret which is publicly revealed to complete the authentication. If the BBT attack recovers the shared secret after it is revealed and authentication is completed, it is of no consequence. Thus, the attack fails because the information is no longer relevant.

It is even dubious that the duration of the attack adequately protects the second profile (where the certified public key is freely readable from the tag), or the first (otherwise identical), because:

  • A common use of a key establishment protocol is to establish a secret session key used for conventional cryptography, thus the time-frame to be considered for attack extends beyond the authentication time: the secret key remains a target as long as knowing any encrypted data remains desirable to an attacker, and at least for the full duration of an authenticated session.
  • The proposed standard does not describe a time limitation; and in a typical implementation of an RF authentication protocol, it is easy to lengthen the protocol, giving more time to the attack:
    • Typical RF readers implement a communication protocol (e.g. ISO/IEC 14443-4) that allows retry, without stated limitation.
    • Typical RF tags do not measure the time during which they are waiting for data frames, and allow an indefinite pause at such moment. That alone could make the tag vulnerable to unauthorized writing, even if the reader implemented a time limitation.
  • The attack is currently un-optimized, and using parameters much larger than what has been proposed for standardization, thus it is entirely plausible that it can be considerably sped up to become real-time for the parameters proposed for standardization (it is neither acknowledged nor denied that the attack worked in practice for 5 out of 5 of the challenge parameters proposed at a conjectured 128-bit security level with $N=16$, when the standard proposes $N=10$).

Other arguments boil down to: the attack makes an assumption that only holds most of the time; we can choose new parameters that invalidate this assumption, thus make the attack impossible. We're working on the details; the value of parameter $N$ "will necessarily be in a higher range than" $16$ of the attack, "but the method can be computationally viable by applying suitable projection operators associated to singular first private matrices".

Improve this answer
$\endgroup$
1
$\begingroup$

This attempts to outline updates after this other answer, frozen Jan 2016.

Simon R. Blackburn and M.J.B. Robshaw further exposed critics about one of the protocol in the proposed standard with On the Security of the Algebraic Eraser Tag Authentication Protocol; in Cryptology ePrint Archive (2016-02-02, updated 2016-06-02).

D. Atkins and D. Goldfeld wrote Addressing the Algebraic Eraser Diffie-Hellman Over-the-Air Protocol; in Cryptology ePrint Archive (2016-02-25), answering that. They

  • almost acknowledges that the October 2015 draft standard was vulnerable;
  • presents as an excuse that it was rushed out (refer to the paper for the circumstances);
  • compares the attacks to invalid elliptic curves attacks on Diffie-Hellman ECC protocols;
  • notices that theses attack critically rely on recovering a shared secret computed by the authenticated tag when interacting with a rogue device posing as a genuine verifier;
  • propose two possible "straightforward changes to the tag authentication protocol" preventing leak of that shared secret:
    1. hashing it, and using the hash instead;
    2. using it as a key to a MAC for authentication purposes.

These countermeasures make sense, and convincingly block the Blackburn and Robshaw attack, as claimed. But

  • these are important changes,
  • no security reduction is given,
  • no claim is made regarding the attack by Ben-Zvi, Blackburn and Tsaban.

Adi Ben-Zvi, Simon R. Blackburn, Boaz Tsaban's A Practical Cryptanalysis of the Algebraic Eraser; in Cryptology ePrint Archive was updated (2016-06-02), and a version published in proceedings of Crypto 2016.

By late 2016, SecureRF promoted IronwoodKAP (a key agreement protocol described as an outgrowth of the Algebraic Eraser™, that produces the shared secret using a hash as in 1.); WalnutDSA (a digital signature algorithm); and Hickory Hash II (a cryptographic hash function); see Iris Anshel, Derek Atkins, Dorian Goldfeld, Paul E. Gunnells: Post Quantum Group Theoretic Cryptography (2016-12-05), at SecureRF website.

By July 2017, Ironwood has become a Meta key agreement and authentication protocol between one Home Device and multiple Other Devices. The restriction to a single HD (or identical copies thereof) is in order to resist the attack by Ben-Zvi, Blackburn and Tsaban without increasing key size nor compromising performance. The protocol thus has the functionality of symmetric cryptography with persistent HD master key and OD-unique persistent diversified key, used for mutual authentication of HD and OD, and negociation or a per-session shared key; plus claimed quantum resistance, and claimed impossibility to impersonate ODs using what's in a HD. See id.; Ironwood Meta Key Agreement and Authentication Protocol (2017-07).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.