Talk:Algebraic Eraser

Suggested page improvements, added references

@Intgr: I'm trying to improve this page in several ways:

1. Add a reference to the refutation of the Ben-Zvi/Blackburn/Tsaban attack
2. Point out that the Blackburn/Robshaw attack is purely against the proposed ISO 29167-20 over-the-air protocol (and not specifically against the AEDH Algorithm)
3. remove some bias in the text about AE being patented by pointing out that both RSA and ECC were (and are) patented, too (and add a reference to the US patent, like was done on the RSA and ECC pages).

Since you clearly didn't like the way I edited it, can please you guide me in appropriately adding these improvements?

PS: AECAP/AEDH *is* a DH protocol in the sense that all key agreement protocols are: you exchange public keys and get out a shared secret. This is no different than ECDH. DerekAtkins (talk) 16:41, 11 February 2016 (UTC)

Hi Derek. Regarding your four points:

1. The refutations only seem to have been published on preprint archives and not (yet) in a peer-review cryptography journal (http://dblp.uni-trier.de/pers/hd/g/Goldfeld:Dorian). The phrasing should thus explicitly mention who refuted the claims (inventors of AE/people affilited with SecureRF) and that this refutation has not (yet) gone through the peer-review process. (The same applies to the papers describing the attacks.)
2. This seems like a worthwhile clarification.
3. The current phrasing regarding the patent situation of AE seems factual and neutral to me. Your proposed reformulation does not.
4. All of the references in this article use the term "Algebraic Eraser", not "Algebraic Eraser Diffie-Hellman". I see no good reason to introduce a change of terminology here. (And I see a good reason not to do so: many people read DH as discrete log.)

—Ruud 17:33, 11 February 2016 (UTC)

Hi Ruud. Thank you for your responses. Are these changes that I can make or will they be reverted again due to CoI?

W.r.t. #1, as far as I know *ALL* of the attacks (and refutations) were published via arXiv or eprint and none of them have gone through a peer-review process. How would you suggest the text be edited?

W.r.t. #3, the existing reference does not seem to be relevant to the statement that the algorithm is patented, whereas referring to the patent would be.

W.r.t. #4, there are more references that can be added that use the term Algebraic Eraser Diffie-Hellman, including several papers/presentations like http://csrc.nist.gov/groups/ST/lwc-workshop2015/papers/session8-atkins-paper.pdf (which doesn't use it in the title, but does refer to "AEDH" on page 3). Also, the reference I had just added ( http://arxiv.org/abs/1601.04780 ) uses AEDH throughout. Moreover, there are additional AE-based protocols that should be differentiated, like AEHash (accepted for publication) and AEDSA (submitted for publication). If nothing else it should be AEKAP.

DerekAtkins (talk) 18:21, 11 February 2016 (UTC)

I applaud Derek for opening this discussion. But I think it's worth being skeptical of anything that Derek Atkins suggests here. It appears to follow the pattern set out in the arstechnica article, with claims that the published attacks don't apply because they use different parameters, that they are are refuted, etc. And that's what one might expect from the CTO of SecureRF.

For example, in the initial version of the article posted by User:DerekAtkins claimed that the Kalka-Teicher-Tsaban attack "was refuted by showing that choosing the matrices in a special form defeats the attack", citing a paper from AE's designers. Please correct me if I'm wrong, but my understanding is that the attack was actually confirmed to apply to "Algebraic Eraser" protocol as initially published in 2006, and a modification was proposed to applications using AE to avoid this attack. I have changed the article to reflect that.

#1 "as far as I know *ALL* of the attacks (and refutations) were published via arXiv or eprint and none of them have gone through a peer-review process" The Kalka-Teicher-Tsaban attack was published in Advances in Applied Mathematics [1]. The rest don't appear to be published in journals or conferences. I think it's fine to keep their coverage in the article, as long as they're neutrally represented and WP:NPOV is strictly followed.

#3 The existing arstechnica reference supports the claim that the AE protocol is patented. Patents in Wikipedia are not considered reliable sources (see WP:PATENTS); even if the patent application claims to apply to Algebraic Eraser, that may turn out to be false, as many patent lawsuits end up dismissed or invalidate the patent. Doing sufficient legal analysis would amount to original research. It's generally best to avoid mentioning/citing patents unless there's a secondary reliable source (WP:PSTS, WP:RS), which is the arstechnica article.

-- intgr [talk] 11:59, 12 February 2016 (UTC)

Oh, I also wanted to address this from #3 "bias in the text about AE being patented by pointing out that both RSA and ECC were (and are) patented, too". I believe using references in this way goes against WP:SYNTHESIS. It's true that there have been patents on RSA, ECC and many other older cryptosystems, those patents have mostly expired (others are being worked around). That's why it's particularly remarkable that AE is patented: we live in a very different world now. New cryptosystems are mostly published without any intent to patent (Curve25519, EdDSA, SIDH, RLWE). Choosing a patented cryptosystem in this age would be very controversial indeed. -- intgr [talk] 13:50, 12 February 2016 (UTC)

intgr, thank you for your reply. You are absolutely right that you should be skeptical of anything I say. You should also be skeptical of anything other people say. Everyone has a bias, be it conscious or unconscious. Me, I'm just trying to make sure all the information that's out there is available, and that the information is factually correct. I'm fine with what I say being filtered through you and others; I just ask that you apply the same filters to everyone equally.

Thank you for making the changes you've made. There are still two more that I feel need to be made:

1. Point out that the Blackburn/Robshaw attack from 10 days ago is purely against the proposed (draft) ISO 29167-20 over-the-air protocol (and not specifically against the AEDH Algorithm).
2. Adding the reference to http://arxiv.org/abs/1601.04780 in response to the Ben-Zv, Blackburn, Tsaban attack.

I'm not going to argue the merits of patenting an algorithm. That choice was made well before I joined the company, by almost a decade. However by your response here you seem to have a clear bias against patented algorithms. I would hope that as an editor here you can step back and see your own (most likely unconscious) bias and try to filter that as well. I just want to point out that the Ars article is not a legal analysis either, so by your own standards should not be treated as such.

Thanks,

-- DerekAtkins (talk) 14:25, 12 February 2016 (UTC)

@DerekAtkins: Sorry that I haven't replied, I couldn't find the time to look into this. Since I'm still figuring this out and I lack formal background in relevant maths and cryptography, I'm asking you to confirm that I have understood things correctly.

So the "ISO 29167-20 over-the-air protocol" is basically a standardization effort of the "Algebraic Eraser OTA Authentication" protocol designed by SecureRF? The Blackburn/Robshaw attack most likely applies to both?

The OTA protocol makes use of AEDH, and you insist that the Blackburn/Robshaw paper applies only to the OTA protocol, but does not highlight any problems in AEDH itself?

The paper states "We side-step the bulk of the mathematical machinery behind the Algebraic Eraser, but observe some curious features of the Algebraic Eraser that cause significant failures in this protocol". This does seem to suggest that at least some blame lies with AEDH itself; maybe it's not outright broken because it leaves lots of details up to the protocol/implementation, but it is just difficult to use securely? It's telling if even the company that designed it cannot build a secure protocol on top of the primitive.

Also, to address your comment: "I would hope that as an editor here you can step back and see your own (most likely unconscious) bias". Yes, I strive for that. And I see now that my argumentation on this point wasn't very good, so let me try agian:

I think factually stating that AE is covered by patents is the least biased way to cover it (such as currently in the article "the company also owns patents covering the protocol").

Introducing comparisons to other cryptosystems would in fact introduce bias, such as your proposed "Like RSA and ECC, the Algebraic Eraser method has been patented". Using the same approach, one could spin it as "the Algebraic Eraser method has been patented, unlike Curve25519, which is free of patents" or even "the Algebraic Eraser method is currently covered by patents, unlike RSA whose patents have expired". This is a pretty clear example of WP:SYNTHESIS. Do you disagree?

"I just want to point out that the Ars article is not a legal analysis either, so by your own standards should not be treated as such.". I agree that the Ars article is not a legal analysis, but it doesn't need to be: it's a reliable source and is appropriate to use to back up statements on Wikipedia. Whereas directly citing the patent and saying it applies to something is arguably original research and not appropriate in Wikipedia. -- intgr [talk] 16:07, 17 February 2016 (UTC)

Hi, some comments. First, as to my background: I am a professional mathematican, working at a research university, doing research in algebra and in particular algorithmic algebra. While I am not published in cryptography, I follow the field quite closely. In particular, group theory, Braid groups, and all the mathematics underlying the Algebraic Eraser, are close to my research field. So despite not being a cryptographer, I feel qualified to comment on this issue. (On the upside, I also have no stakes in this discussion, so perhaps that lends slightly to my credibility)

All in all, I am quite confused and surprised by Derek's claim that the recent arXiv preprint by Blackburn and Robshaw only targets the specific OTA protocol, but not the "core" of the Algebraic Eraser. After reading the paper, I arrived at the exact opposite conclusion: The attack described in section 5, for example, exploits a linearity property of the Algebraic Eraser when queried with multiple different Interrogator public keys. This is by the way a classical mistake in the design of a crypto protocol (or rather: in the design of the threat model), i.e. assuming that active attackers will only vary the messages they feed into the system, but not the keys.

Thus, the linearity property described in Section 3.2 and exploited in Section 5, appears to be an inherent flaw of the Algebraic Eraser. Contrary to Derek's claim, my impression is that if at all, the OTA protocol makes the attack *harder* (but not hard enough to help: the supposedly exponential problem still was turned into a linear one). To quote the end of section 5 of the preview: "The linearity property that facilitates this attack appears intrinsic to the definition of the Algebraic Eraser and thus hard to avoid; increasing the size of parameters will not provide any significant additional security."

All in all, the strong impression this leaves is that the core key establishment protocol is fundamentally broken. Keeping it safe at this point seems to solely rely on "private key validation", which this Wikipedia article currently hints at -- but which, curiously, apparently (?) is not mentioned in official presentations on Algebraic Eraser, like this one: <http://csrc.nist.gov/groups/ST/lwc-workshop2015/presentations/session8-atkins-gunnell.pdf>). The hope would be that this is enough to prevent an attacker from generating sufficiently many private keys to mount a successful attack. Whether this is feasible appears doubtful to me. In particular, how would such a verification be realized without removing the primary advantage AE has over other established KEX protocols, namely its high efficiency?

All that said, if / when the AE team posts a thorough response to the serious issues raised by the Blackburn and Robshaw paper, then of course that can be taken into account, too. Until then, I'd say B&R wrote down clear facts that do not require much of a mathematical level to understand, while Derek has not yet substantiated his claims that the new attack only targets the OTA protocol. BlackFingolfin (talk) 11:41, 18 February 2016 (UTC)

@Intgr: Thank you for the response. I've been wondering about it. I'm happy to help you with any math/crypto questions (it took me several months to wrap my head around the math of AE, and that was with the help of the mathematicians at SecureRF!)  :-)

"So the "ISO 29167-20 over-the-air protocol" is basically a standardization effort of the "Algebraic Eraser OTA Authentication" protocol designed by SecureRF?". Not exactly. The ISO 29167-20 over-the-air protocol was originally proposed by SecureRF but has gone through several revisions with input from several members of the ISO working group (including, by the way, M. Robshaw). The Algebraic Eraser OTA Authentication protocol referenced is an extraction of the protocol content from 29167-20 (stripping away all the ISO-specific content). It is, technically, the work product of the ISO WG and not solely SecureRF.

"The OTA protocol makes use of AEDH, and you insist that the Blackburn/Robshaw paper applies only to the OTA protocol, but does not highlight any problems in AEDH itself?" Correct. The OTA protocol is an authentication protocol that utilizes AEDH as the main cryptographic tool. @BlackFingolfin:, one of several tiny modifications to the OTA protocol completely block the Blackburn/Robshaw attacks, without making any adjustments or changes to AEDH directly (I'll have a reference for that statement shortly).

"This does seem to suggest that at least some blame lies with AEDH itself; maybe it's not outright broken because it leaves lots of details up to the protocol/implementation, but it is just difficult to use securely? It's telling if even the company that designed it cannot build a secure protocol on top of the primitive." By that same argument one could blame ECC for https://www.iacr.org/archive/pkc2003/25670211/25670211.pdf or http://euklid.org/pdf/ECC_Invalid_Curve.pdf -- instead I would just say that there was a bug in the OTA protocol that, instead of being pointed out in the committee, was aired out in the public. It's actually easy to use securely -- just don't expose the computed shared secret. There are several ways to achieve that: using a Hash to obscure it, using a MAC in a challenge/response, or using an encryption challenge/response. (We actually use the MAC method in all the SecureRF products).

"I think factually stating that AE is covered by patents is the least biased way to cover it" I agree, and I'm fine with the wording. However I think there are better references to use than the Ars article (which, by the way, was written without any input from SecureRF). For example, you might consider http://www.eejournal.com/archives/articles/20151019-encryption/ which also clearly says that it's patented.

"I agree that the Ars article is not a legal analysis, but it doesn't need to be: it's a reliable source and is appropriate to use to back up statements on Wikipedia. Whereas directly citing the patent and saying it applies to something is arguably original research and not appropriate in Wikipedia." I would argue whether the Ars article is reliable; I think the EEJournal article I reference above is a more reliable source. W.r.t. [[WP:OR|original research], is it inappropriate to add a link to the patent? Or just inappropriate to use it as a reference to the statement that "it's patented"? It still seems strange to me that a link to a patent isn't a qualified reference to say "a patent exists".

-- DerekAtkins (talk) 15:22, 18 February 2016 (UTC)

@DerekAtkins: wrote: "one of several tiny modifications to the OTA protocol completely block the Blackburn/Robshaw attacks, without making any adjustments or changes to AEDH directly (I'll have a reference for that statement shortly)." -- well then, my curiosity is certainly piqued, I look forward to seeing how you pull off that astonishing feat. BlackFingolfin (talk) 16:41, 18 February 2016 (UTC)

The Ars Technica article does contain input from SecureRF: "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 [...] In an e-mail to Ars, Parks said [...]" I'm getting the impression you are more interested in seeing references to that article removed, rather than improving the citations in this article?

Blackburn and Robshaw's article seems to be, strictly speaking, an attack against the tag authentication protocol built on top of AE, but the Conclusions section has some strong words against the underlying primitive as well. —Ruud 17:25, 18 February 2016 (UTC)

@BlackFingolfin: Ah ye of little faith (but thank you for your patience). Their attacks all depend on getting full access to the computed value, M, which is possible only due to the over-the-air protocol. Changing the over-the-air protocol to produce and send e.g. Hash(M) as a verifier completely defeats their attack. c.f. http://eprint.iacr.org/2016/205 What is astonishing is that they didn't bring this up in the design meetings!

@Ruud Koot: Again, sorry for the delay in responding. I really am trying to improve the article (which also implies improving the citations and references). "Blackburn and Robshaw's article seems to be, strictly speaking, an attack against the tag authentication protocol built on top of AE, but the Conclusions section has some strong words against the underlying primitive as well" -- as you say, the article is an attack against the OTA protocol. Their conclusion does not follow from their paper. There are behind-the-scene political issues going on which don't need to be aired publicly.

So to summarize the outstanding requests:

1. Add a reference to http://www.eejournal.com/archives/articles/20151019-encryption/ in the introduction.
2. Add a reference to http://arxiv.org/abs/1601.04780 in response to Ben-Zvi, Blackburn, Tsaban showing that at least one of their conjectures is false.
3. Add a reference to http://eprint.iacr.org/2016/205 in response to Blackburn/Robshaw and make it clear that their attack is purely against the draft OTA specification.

In addition, I think it would behoove us to separate out the underlying Algebraic Eraser from the key agreement protocol, because there are also other cryptographic constructions that will hopefully deserve pages, too (e.g. AEHash and AEDSA). Mea Culpa for creating a single page at the onset instead of separating out into the individual parts (e.g. the one-way function and then the various constructions built using that one-way function).

--DerekAtkins (talk) 15:48, 15 March 2016 (UTC)

EE Journal source

@Ruud Koot: In what way is EE Journal not an appropriate source? (How is it any less appropriate an Ars Technica?) --DerekAtkins (talk) 15:58, 28 March 2016 (UTC)

This EE Journal, despite its impressive sounding name, seems to be a minor personal blog. The article reads like an advertorial, and doens't say anything that isn't (or shouldn't) be in the Wikipedia article. (Neither are true of Ars Technica or its article). —Ruud 16:07, 28 March 2016 (UTC)

It's not. It's the online face of an actual printed journal (or at least it used to be printed; I've seen copies although I don't actually subscribe). In a quick (30-second) search I've found at least a half-dozen different authors of articles, including under the actual EE Journal "Blog" page. So I would disagree with your characterization of it being a "personal blog". As for the question of content, well, it says in the article "And yes, they have patents" so IMHO it's a valid reference for wikipedia saying that AE has patents (WP:OR). I'd be happy if more of the content of this article were pulled into the wikipedia article, but I can't help it if a third party writes a completely even, balanced, non-inflamatory article about AE! --DerekAtkins (talk) 16:23, 28 March 2016 (UTC)

@DerekAtkins: Two weeks ago, the day before you posted your outstanding request, the person responsible for handling EE Journal's "social media presence" created a Wikipedia article on this publication and explicitly noted that "[i]t is an online only publication and never published a print edition." Perhaps you're confusing it with the EE Times. —Ruud 17:13, 28 March 2016 (UTC)

@Ruud Koot: It still does not imply that it is a personal blog. Indeed, my reading of that page (and the link you forwarded) implies otherwise --DerekAtkins (talk) 17:52, 28 March 2016 (UTC)

It has a negligible Alexa rank of 432,578. It isn't affiliated with any larger publisher. It doesn't seem to have won any notable awards or received external praise. There is no way we can verify if their editorial standards are up to par. This is no Wired or Ars Technica. —Ruud 17:58, 28 March 2016 (UTC)

(edit conflict) @Ruud Koot: Okay, we've established that it's not a print journal, but it doesn't seem to be a "personal blog" either. WP:RS states that online sources qualify as "published" as well. The rest of the RS criteria seems to boil down to "editorial control and a reputation for fact-checking", which is very difficult to assess, but it appears from the articles that there are multiple active writers. The link you posted just above seems to indicate the existence of an editorial team as well. Do you have any better criteria to judge it by? -- intgr [talk] 17:58, 28 March 2016 (UTC)

As per the usual standard: other independent, reliable sources vouching for it in some way. If these existed, I'm sure the creator of EE Journal would have added references to those. This just looks like a blog published by one "Kevin Morris". The usual PR-stuff that gets added as "sources" when people want to get their non-notable stuff desperately included on Wikipedia. —Ruud 18:03, 28 March 2016 (UTC)

Yeah, just browse around a bit starting at http://www.eejournal.com/media-kit. Too much talk about "content marketing". Or http://www.eejournal.com/media-kit/publication/editorial/: "PR Professionals: If your company has an opinion, topic or announcement you feel our editors might want to cover, please contact them directly ..." —Ruud 18:25, 28 March 2016 (UTC)

@Ruud Koot: Did you read the article in question? First, it's not written by "Kevin Morris". Second, it's a survey of several different public key cryptosystems (including RSA and ECC). Third, the referenced content for this article is like 70% down into the article (not that this is important, but just pointing out that the article isn't corporate marketing). --DerekAtkins (talk) 18:42, 28 March 2016 (UTC)

I read it. This is exactly how an advertorial is supposed to look like: first discuss some some uncontroversial well-known stuff, them sneak the advertisement in at the end. Now, do we have any concrete evidence we can point to that could convince us that this EE Journal is a well-respected publication, with an impeccable standard of editorial integrity? —Ruud 18:48, 28 March 2016 (UTC)

Anshel–Anshel–Goldfeld key exchange

How is Algebraic Eraser related to Anshel–Anshel–Goldfeld key exchange? —Ruud 20:25, 18 February 2016 (UTC)