Cryptanalysis of Algebraic Eraser

Cryptanalysis of Algebraic Eraser

Algebraic Eraser is a public-key key-agreement protocol that’s patented and being pushed by a company for the Internet of Things, primarily because it is efficient on small low-power devices. There’s a new cryptanalytic attack.

This is yet another demonstration of why you should not choose proprietary encryption over public algorithms and protocols. The good stuff is not patented.

News article.

Comments

Clive RobinsonNovember 30, 2015 12:20 PM

@ Martin,

Not only is the statement bogus and unsupportable, it infers yet other bogus claims.

Hmm is that a self referential statment?

As it happens “patent encumbered” crypto rarely gets wide usage. It is only covered by patent in a few places in the world, but unless there is a “free licence” available to some or all potential users, other methods of achiving the same ends are sort out and used instead.

Hence the old saw “Nobody ever made a living of crypto patents” which is atleast a hundred years old as an observation. A look at the history of what you might know as the “Enigma Cipher Machine” shows it to be true for mechanical ciphers, and PGP for IDEA and RSA will tell the story for software algorithms well enough.

Importantly if a crypto algorithm sees little use, it’s unlikely to attract much analysis unless their is something new or interesting about it.

However the history of FEAL shows that once one or two analysts sink their teeth in and shake, the rest of the community tend to follow “piranha like behavior” as they “sense blood in the water” and all sink their teeth in and rip it apart…

Crypto algorithms only become “good stuff” when many eyes have looked at them. As a rough rule of thumb that happens only when they are likely to be taken up for mass usage. In turn as I’ve already noted the rough rule of thumb on take up is it’s lack of encumbrence, or it’s “first of a kind” nature.

Patent Trolls have made the risk way to high for most engineers which is just one reason I don’t consider encumbered algorithms for anything to be worth the potential legal issues and thus costs. I see the same view point in many engineers, and the only time it changes is when licences or indemnification comes with the specification… Whilst there are those who do use encumbered algorithms, they are usually based well outside of any area where the encumbrence can be enforced, in product that likewise stays well out of reach, and often in a way it is difficult to tell the algoritms are even being used (Patent Trolls being esentialy blackmailers, they tend to only go after those who are both easy targets and have deep pockets).

So if you have any counter examples of encumbered crypto becoming successful outside of the products produced by those who are not encumbered and feel like troting them out, feel free.

Z.LozinskiDecember 1, 2015 12:13 PM

@Clive,

> A bigger deniable “cartel / monopoly” in bed with the IC it would be harder to find…

There’s nothing deniable about it – if you hold a telecom license in any country I have ever worked in, there is usually a license obligation for the operator to provide assistance to the government. Depending on the country, the details may (or may not) be spelled out in statute or regulation. Everyone who works in fixed or mobile telecoms kinda knows this.

And remember, when some of us started working, the PTT (telco) and the IC were just different branches of government: in some cases even under the same department.

Arguably, one of the failings of the IC was in understanding that the same rules didn’t apply to the internet. The standards were not created by ITU-T / ETSI. The vendors were not the 100 year old companies like Ericsson and Siemens that everyone knew. The service providers were different too (and kept changing).

> You will also find the work of the NSA behind most of the voice compression algorithms.

It is a bit more entwingled than that, as it predates the formation of the NSA. The basic research on vocoders was done by Bell Labs in the very early 1930s. Early in WWII (1940) Bell Labs realised the importance of secure speech communications due to the issues involving communications from the UK to the USA, and created two projects. “(1) Short-term mobile privacy systems for low-echelon use and (2) long-term, high-echelon secrecy systems, both suitable for telephone circuits.” The second was named Project-X, and most of the Project-X patents were classified and not released until 1975. The British GPO were involved from 1941, and so was the US Signal Corps. (NSA doesn’t exist, yet). Project-X was the basis of the SIGSALY transatlantic secure voice link from 1943. If money and (electrical) power were no object, you could have secure, compressed, voice 72 years ago. A whole load of interesting people got caught up in this area: Alex Reeves, Harry Nyqvist and Claude Shannon. The technical history of the Bell System has a 700 page volume on “National Service in War and Peace”, which includes some of the fun stuff.

What happens between the end of WW2 and the 1970s is much less clear. But I’m guessing Howard E Rosenblum, who headed the NSA’s Secure Speech Division from 1962, was the prime mover. LPC-10 and the 4.8kbit/s NSA version of CELP you mentioned both show up in the late 1970s about the time microprocessors make implementations of feasible without 19″ racks full of gear.

The interesting part of the “Stuff it” phone is that the early system design had a central key management system. Once more, Howard E Rosenblum’s name is on the black patent which was declassified in 1980.

Photo of Bruce Schneier by Per Ervland.

Schneier on Security is a personal website. Opinions expressed are not necessarily those of Resilient Systems, Inc.