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.
RonK • November 30, 2015 7:06 AM
I found one of the promoted comments at Ars quite cogent, and more explicit why proprietary has its disadvantages:
dbostrom
One of the problems with attaching a business plan (SecureRF etc.) to an important decision like this one is that when all is said and done, promoters of a business plan will pretty much always choose their next paycheck over an admission that their business plan is a non-starter. …
Woo • November 30, 2015 7:56 AM
“We do not think this attempt will scale, and we will still claim our system is unbroken.” – of course, the head-into-the-sand method of dealing with an attack is also a classic. Where the best choice would be analysis and improvement, they only offer denial and marketing speak. I can’t wait for the next attack to build on the current research and break their encryption scheme for good.
Oskar Sigvardsson • November 30, 2015 8:01 AM
For parameter
sizes corresponding to claimed 128-bit security, our implementation
recovers the shared key using less than 8 CPU hours, and less than
64MB of memory.
Jesus, they didn’t just figure out an attack, they really destroyed it. Nobody use this algorithm for anything, ever!
Craig • November 30, 2015 8:20 AM
@woo: your head-in-the-sand comment called to mind a favorite adage: “An ostrich can’t put its head in the sand without bending over.” Which reinforces your point, I think.
CallMeLateForSupper • November 30, 2015 9:31 AM
One wonders how this propriatary (choke, gasp) Eraser thing wound up on a fast-track to becoming a standard. I guess some archaeologist unearthed an ancient stone tablet that proclaimed “Algebraic Eraser. Word, dude.”
albert • November 30, 2015 10:13 AM
Using accepted sociological data, I reckon SecureRF might get up to 525600 customers in the first year.
I’m laying odds on when they adopt a catch-phrase like:
“Algebraic Eraser; It’s better than nothing.”
. .. . .. _ _ _ ….
wumpus • November 30, 2015 10:23 AM
Just what “good stuff” public key cryptosystem has never been patented? RSA was famously patented, the elliptical stuff has had multiple levels of patents (even after all the basic things expired, there was still a patent that let you only need half the key length. At the time it was a significant advantage over RSA (RSA key size hadn’t yet exploded). Diffie-Hellman might exist, but it isn’t exactly “public key”.
The thing about patents are that they require making the “invention” public. This makes it harder for snake oil to hide (although I’m sure there exist patented algorithms with secret implementations. There are also million dollar dowsing rods.) As long as the algorithm is public and has a high visibility among cryptographers (such as this thing being shoved into a standard), it might be strong. Obviously, they shoved it into the standard far too fast.
Martin • November 30, 2015 11:16 AM
@wumpus – good comment. You have to understand the good stuff isn’t patented nonsense is part of a larger narrative. Not only is the statement bogus and unsupportable, it infers yet other bogus claims.
Clive Robinson • November 30, 2015 11:26 AM
One reading the introductory pages a couple of things become clear.
Firstly, they did not have all the information from SecureRF, just some test data.
They broke the system within 8 Hours in all cases of the data they had been provided with…
Hmm, if you were SecureRF, and you had to send test data to researchers, would you send “weak” or “strong” test data?
It appears that all they sent was weak data… Which raises the question as to why?
The first question perhaps was “did they know it was all weak data?
If you think about it either they deliberately selected only weak data or by far the majority of keys are weak. That is, if randomly selected you would expect some keys to be strong in roughly the same proportion that the overall strong to weak ratio…
The fact they sent all weak key data raises the question as to why, what did they hope to gain, even the possability they had no clue they were sending weak key data. And if that is true… Then the number of weak keys must be immense and thus significantly outnumber strong keys, perhaps there are no strong keys? In which case it’s game over for this system and it should be dropped faster than a nuke hot “potatoe” (as a VP once demo’d)…
UIUC • November 30, 2015 12:12 PM
Directory of CyberArk patents and/or applications can be found here http://stks.freshpatents.com/Cyber-ark-Software-Ltd-nm1.php
Here’s a page on Kaspersky’s site regarding their recent patents and/or applications http://www.kaspersky.com/about/news/product/2015/New-Technologies-to-Combat-New-Threats-Kaspersky-Labs-Q1-2015-Patents-Digest
Want a few thousand more? Of course now we know that none of these are any “good.”
Clive Robinson • November 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.
Clive Robinson • November 30, 2015 12:58 PM
@ UIUC,
With regards your links you can follow the first down to,
http://www.freshpatents.com/-dt20150423ptan20150113600.php
Which was the first issued this year.
Why it was issued I have no idea because it is all “prior art” there is nothing original in it.
In essence what they are trying to claim is a Password Manager as a front end to a time limited (30min) DB, and an IDS front end that detects uses of accounts under the Password Manager. If use of an account is not matched by an entry in the DB then it’s counted as an unauthorised privilege escalation.
This is by no means a new idea I know of a couple of UK Unis that had in house designed systems exactly like this back in the late 90’s early 00’s.
I’ve talked here about signiture detection systems as part of C-v-P that this idea falls as a tiny subset of…
So I guess it falls within your ‘Of course now we know that none of these are any “good.”‘…
Werner Baumann • November 30, 2015 3:05 PM
The article on ars technica starts with a diagramm they have taken from the White Paper of SecureRF. Please have a look at it (and laugh).
It is not only obviously made up, but simply the kind of nonsense produced by marketing people to impress layman. If you try to take it serious than it shows that Algebraic Eraser needs more resources than any other public key system.
I would never trust a company that tries to fool me in such an incompetent way.
Dr. I. Needtob Athe • November 30, 2015 3:37 PM
SecureRF CEO and President Louis Parks: “Our conclusion is that this attack does not represent a threat to the practical deployment of AEDH in applications with properly chosen parameters…”
So you’re in denial?
Mr. Parks, let me show you my shocked face.
Martin • November 30, 2015 4:18 PM
@Clive Robinson – best I can tell, that’s all you’ve ever done – cut ‘n paste.
Martin • November 30, 2015 4:23 PM
@Clive Robinson, did you invent the Internet as well? After reviewing those patents you really should contact the authorities at once to let them know!
Clive Robinson • November 30, 2015 4:34 PM
@ Martin,
best I can tell, that’s all you’ve ever done – cut ‘n paste.
Oh dear you are a one track pony, making unsupportable devoid of reality based statments.
At the end of the day if everything you do is make assertions you don’t support, then what worth is there in making them?
Ben • November 30, 2015 6:16 PM
OCB is another example of good crypto that’s patented:
http://blog.cryptographyengineering.com/2012/05/how-to-choose-authenticated-encryption.html
And RC4 is good crypto that was a trade secret (it was good crypto for many years, anyway).
not white noise • November 30, 2015 10:08 PM
@Werner Baumann
Re “I would never trust a company that tries to fool me in such an incompetent way.”
Here’s a laugh riot: https://www.youtube.com/watch?v=GwkwgR_78dQ
(Claiming 11 decimal digits is 88 BITS is not the only laugh there; it’s just the most obvious one!)
RonK • December 1, 2015 12:53 AM
@ Ben
OCB is another example of good crypto
Straight-up OCB was broken in 2002, at least for authentication. Try harder?
Z.Lozinski • December 1, 2015 4:08 AM
@Clive,
There are couple of interesting cases I know of cryptosystems being very successful despite being patent or IP encumbered. Both are cases from the telecom world, which may be why they are different.
Both are cases where there is a strong group of organisations developing a technology, with separate agreements on how revenue is shared. (These have to be separate to avoid anti-trust issues, as is explicitly mentioned at the start of every 3GPP meeting!)
There was an unspoken assumption when these technologies were developed that the only companies implementing the technology will be one of the core developers or heavily cross-licensed. In fact in the case of UMTS/LTE, this is written into the patent cross-license terms.
How this will be affected by patent trolls is … interesting.
Clive Robinson • December 1, 2015 6:11 AM
@ Z.Losinski,
Both are cases from the telecom world, which may be why they are different.
A bigger deniable “cartel / monopoly” in bed with the IC it would be harder to find…
And whilst you found NSA under one rock, did you find the rest of the FiveEyes “finessing” at the standards meetings and in the design houses?
There are funny stories told about A5 and the why and how of it’s existance and what the French had to do with it (follow the trail to the IC and likewise with Siemens).
You will also find the work of the NSA behind most of the voice compression algorithms, which may or may not be a cause of concern (I don’t know my maths in that area is no where near good enough to spot subtle flaws for side channels etc, but someone I know who does says there are oddeties that make them cautious).
As for the “Stuff It” phones as a friend used to call the darn things, there have been all sorts of “guesses” as to if they have been either backdoored or have some covert side channel leaking key or other information built into the design incase it gets “coppied” by a “foreign power”.
The ones I saw the guts of used Motorola DSP chips and supposedly an NSA / DoD version of CELP[1]for the codec and DES for encryption.
The more rocks I bumped into when involved with telecommunications the more stories I heard and the more oddities I witnessed. As I’ve said before, it’s difficult to argue against “safety features” even when you can see they are “dual use”. The feeling that you are dangling from a marionettes string does not ever seem to go away…
[1] http://www-mobile.ecs.soton.ac.uk/speech_codecs/standards/dod_celp.html
Z.Lozinski • December 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.
Tom Corwine • December 4, 2015 6:29 PM
@not white noise
Here’s a laugh riot: https://www.youtube.com/watch?v=GwkwgR_78dQ
Only 151 views? I’d think it would get more just for the comedic value.
(Claiming 11 decimal digits is 88 BITS is not the only laugh there; it’s just the most obvious one!)
He actually says 11 characters, so it’s easy to see how he came to the 88 bit conclusion. Sounds more like a con that an error.
Subscribe to comments on this entry
Sidebar photo of Bruce Schneier by Joe MacInnis.
Evan • November 30, 2015 6:58 AM
This is also yet another demonstration of why IoT is a terrible, terrible idea; even if they had used a better crypto suite, having stuff that isn’t susceptible to attacks because it’s too dumb is always a more robust security choice.