The Doghouse: SecureRF

SecureRF:

Claims to offer the first feasible security for RFIDs. Conventional public key cryptography (such as RSA) is far too computationally intensive for an RFID. SecureRF provides a similar technology at far lower footprint by harnessing a relatively obscure area of mathematics: infinite group theory, which comes (of all places) from knot theory, a branch of topology.

Their website claims to have "white papers" on the theory, but you have to give them your personal information to get it. Of course, they reference no actual published cryptography papers. "New mathematics" is my Snake-Oil Warning Sign #2 -- and I strongly suspect their documentation displays several other of the warning signs, too. I'd stay away from this one.

Posted on October 9, 2006 at 7:47 AM • 29 Comments

Comments

ChuckOctober 9, 2006 8:33 AM

You might be a little harsh on these guys. They don't have white papers on their site. But, they list their principals' names. A search on the USPTO web site reveals that they are the inventors of US patent 6,493,449.

See http://patft.uspto.gov/netacgi/nph-Parser?...

They may be selling snake oil but, on a quick read, this patent doesn't smell like snake oil.

Here's the web page for one of the founders.

http://www.math.columbia.edu/~goldfeld/

Columbia is a respected university---even if it tends to have a weak (even for the ivy league) football team.

Here's a web page on their "new" math and crypto.

http://www.adastral.ucl.ac.uk/~helger/crypto/...


Chuck J.

Dvorak (no, not that one)October 9, 2006 8:53 AM

> "The algorithm is fast and scales linearly, whereas RSA and Elliptic Curve Cryptography scale geometrically."

Geometrically? I'm not even sure what's that supposed to mean.

> "One of SecureRF’s first applications is a pharmaceutical tracking device that can [...] determine whether temperature limits have been exceeded. "

o-KAY. Does it also paint my house while I'm away for the weekend, secure our airplanes against OMGterrorists and end world hunger? If not, I'll be very disappointed.

KneOctober 9, 2006 9:00 AM

@Chuck
"Columbia is a respected university".

This is the same University which backed a research on faith-based medicine: "two researchers and a Columbia University fertility expert published a startling finding in a respected medical journal: women undergoing fertility treatment who had been prayed for by Christian groups were twice as likely to have a successful pregnancy as those who had not."
http://www.religionandsocialpolicy.org/news/...

Now, of the three principals on the paper, one has since been arrested for fraud and another disavowed having anything to do with the research. The evidence is scant and unverifiable, and the results are universally disputed by the entire field.

Yet Columbia refuses to retract the paper.

Not what I'd call a University worthy of respect.

RichOctober 9, 2006 9:00 AM

I signed away my first born for the white papers which will be "available soon."

I was surprised to see that they claim that their algorithm works on passive RFIDs. Even with their claimed speedup by a factor of 1000 over other methods that doesn't seem sufficient for passive RFID.

I thought that passive RFID simply delivers a bit string. Does anyone know of the biggest algorithm run on a passive RFID?

AnonymousOctober 9, 2006 9:04 AM

@Dvorak:

"Geometrically? I'm not even sure what's that supposed to mean."

While there might be stuff to snipe about, this isn't really one. It just means that the order is polynomial (e.g. O(n^2) or O(n^3)), rather than linera (O(n)).

Mark LodatoOctober 9, 2006 9:16 AM

@Rich:

Passive RFID just means that the device contains no active power source; instead, it uses power from the received signal to process and transmit the response.

RichOctober 9, 2006 9:31 AM

@Mark

I know that, but let me rephrase my question: how much power is available for computation? Can you execute a hundred instructions? a thousand?

AlexOctober 9, 2006 9:50 AM

Some looking around at braid groups cryptography seems good to my non-braid-groups-math-trained self. They're starting from a generalization of the discrete logarithm problem and the algorithm has been published since 1999 at least (under the name Arithmetica). That's the good part anyway.

The website for SecureRF looks like a marketing person picked up the guide to snake oil and proceeded to use all of it.

Finally, you'll be happy to note they cite you, Bruce, in their patent:
Bruce Schneier, Applied Cryptography 2e, John Wiley pp. 1-3, 513-518, Oct. 1995.

And again:
Schneier, Applied Cryptology, John Wiley, 1995.

Valdis KletnieksOctober 9, 2006 1:07 PM

@chuck:

"two researchers and a Columbia University fertility expert published a startling finding in a respected medical journal: women undergoing fertility treatment who had been prayed for by Christian groups were twice as likely to have a successful pregnancy as those who had not."

Unfortunately, neither the quote, nor the cited article, really do that much to support your cause. Admittedly, there's some fishiness involved with the particular researchers in this case, but the *bigger* question of whether prayer makes a difference is still an open question - it doesn't matter if the *researcher* thinks it works, it matters if the study participants think it works. So it's apparently some variant of the placebo effect - and if we understood *why* it worked, it would lead to a lot of benefits in the field of medicine. (The other possibility, that in fact it's *not* a placebo, but a demonstrable intervention by an unidentified outside force, has equally large implications for theology and philosophy).

Yes, their paper (if it hold up) leaves you saying "Wow, I wouldn't have *expected* it to work twice as well". But the interesting experimental papers are precisely those that end up with "I wasn't expecting *THAT*" results.

AlexOctober 9, 2006 5:06 PM

@Braind links:

The refutation you link to breaks another algorithm, but not the one at stake here (Arithmetica).

Rich2October 9, 2006 10:04 PM

If you did a bit of research before writing you would find that the method was presented to a joint conference of the German, American, and Austrian Mathematicla Societies last summer in Germany, will be published in a juried publication of the American Mathematical Society this winter, and is based on an 90 year old math problem that is recognized around the world. This has nothing to do with what univeristy they come from and little to do with "snake oil". Perhaps you should get the paper and read it first.

Matthew SkalaOctober 10, 2006 1:09 AM

Rich2: If readers have to "do a bit of research" to figure out whether the results are valid, then it's pretty safe to assume that the results are not valid. Legitimate science comes with all the data, proofs, and/or citations needed to verify or replicate it.

GregOctober 10, 2006 2:42 AM

@Anonymous, Dvorak.

Geometrically, in this context would mean much worse that O(n^x) where x is a fixed constant. (aka plynomial). its usally some form of a geometric progression.. ie O(x^n) or worse..(O(n!))

However they are quite wrong. In cryptography n is usally the number of digits of the numbers used which makes both RSA and ECC type systems polynomial IIRC.

If you want to compare to real crypto look at some modern cyphers by others. The full implemetion in a nice pdf and refs, no registration required.

This is snake oil.

derfOctober 10, 2006 10:12 AM

"not theory" definitely sounds like something the US government can sink its teeth into and back 100 percent.

Rich2October 10, 2006 11:30 AM

@Dvorak

I could not find any reference to "geometrically" anywhere on the SecureRF site but see you took it from someone elses writing. I do see that they (SecureRF) claim most other systems (all?) run in quadratic time - which is likely the term the quoted writer was looking to use - which I see later postings here arriving at.

The reference to monitoring temprature is called "Cold Chain Management" and a critical function for temprature sensitive drugs and some areas of the food supply chain. The FDA spends a lot of time and money in this area and you can look at companies like Sensitech to see this in action. Hope this helps with your pending disappointments.

Timm MurrayOctober 10, 2006 5:15 PM

No matter if one of the researchers is a fully-qualified mathematician or not, it should be remembered that many fully-qualified mathematicians have looked at cryptography, said "that's easy", suggested an algorithm, and then promptly had it torn to shreads under public review. Despite the intial looks, cryptography really is a hard problem.

Also, remember that even the best scientists, engineers, and mathematicians are often subject to bad marketing when it comes time to make practical applications of their work.

MikeAt1140October 10, 2006 11:10 PM

Hi Bruce

You once gave the three inventors advice to take their work to the academic community- they did so and have continued to do so. Your readers may find the following reference of interest. See below.

Best

MikeAt1140

http://www.ams.org/bookstore?...

Algebraic Methods in Cryptography
Edited by: Lothar Gerritzen, Ruhr-Universität Bochum, Germany, Dorian Goldfeld, Columbia University, New York, NY, Martin Kreuzer and Gerhard Rosenberger, Universität Dortmund, Germany, and Vladimir Shpilrain, The City College of New York, NY

The book consists of contributions related mostly to public-key cryptography, including the design of new cryptographic primitives as well as cryptanalysis of previously suggested schemes. Most papers are original research papers in the area that can be loosely defined as "non-commutative cryptography"; this means that groups (or other algebraic structures) which are used as platforms are non-commutative.

Readership

Graduate students and research mathematicians interested in algebraic methods in cryptography.

Table of Contents

I. Anshel, M. Anshel, D. Goldfeld, and S. Lemieux -- Key agreement, the Algebraic Eraser$^{TM}$, and lightweight cryptography
G. Baumslag, T. Camps, B. Fine, G. Rosenberger, and X. Xu -- Designing key transport protocols using combinatorial group theory
A. Berenstein and L. Chernyak -- Geometric key establishment
P. Dehornoy -- Using shifted conjugacy in braid-based cryptography
D. Garber, S. Kaplan, M. Teicher, B. Tsaban, and U. Vishne -- Length-based conjugacy search in the braid group
M. I. González Vasco, R. Steinwandt, and J. L. Villar -- Towards provable security for cryptographic constructions arising from combinatorial group theory
D. Grigoriev and I. Ponomarenko -- Constructions in public-key cryptography over matrix groups
A. Groch, D. Hofheinz, and R. Steinwandt -- A practical attack on the root problem in braid groups
D. Hofheinz and D. Unruh -- An attack on a group-based cryptoraphic scheme
N. G. Leander -- Algebraic problems in symmetric cryptography: Two recent results on highly nonlinear functions
E. Lee -- Inverting the Burau and Lawrence-Krammer representations
V. Shpilrain and A. Ushakov -- A new key exchange protocol based on the decomposition problem
V. Shpilrain and G. Zapata -- Using the subgroup

MikeAt1140October 11, 2006 8:08 AM

The methods of SecureRF go beyond braid group cryptography. The academic
paper is scheduled for publication before the end of the year - reserve judgement
until you've seen the method in print.

As for braid group cryptography Korean,French,Russian and Chinese
cryptographers have developed variations which they claim are
secure against various attacks.


MikeAt1140

Christoph ZurniedenOctober 12, 2006 4:22 PM

After digging through a lot of the relevant papers (using the link http://www.adastral.ucl.ac.uk/~helger/crypto/... posted by Chuck as a starting point) I must admit that I'm not much wiser now. The most conspicuous I got was some headache but that's what the original snake-oil from the traditional chinese medicin is: a remedy for headache.
The theorie behind is more than 80 years old, but it's in cryptographical use about 10 years only and the amount of cryptographic analysis of the proposed implementations is very poor (but atleast all found weaknesses seem to be repairable) and started around 2000.
The theory is very interesting and promising too, and we need alternatives for the algorithms in use now. The probability is very low that the current algorithms may be broken tomorow but displeasingly higher in 10 of years, so it's a good idea to start early. And that's my point: it is way to early for a usable secure product.

So, belongs SecureRF to the doghouse? Definitly. But is the technology behind snake-oil too? Well, I don't know but time will tell.

Dear SecureRF,
please fire your PR-department immediately if you haven't done it already. The text on your webpage doesn't do the cryptographers involved in that area a very big favor.
Thank you in advance.

CZ

Christoph ZurniedenOctober 15, 2006 1:19 PM

> Also the business people - this technology is clearly not ready for commercialisation.

I can't decide that without all of the details or at least the paper promised for december(?).
And there is the usage: RFIDS. You can use that tags for long-time-usage (e.g. passports) or short-term-usage (e.g. the thermometer for transport monitoring). Cost is also involved of course: cost of production, cost of failure, cost of repair in case of failure and so on.
The given example is not so bad: such a RFID-thermometer is cheap to produce, has a short lifetime (a couple of days up to some weeks. Reuse is forbidden here obviously), the cost of failure is low (insurance pays in most cases) and the cost of repair can be kept low (the tags itself are very cheap, so replacement won't lead to immediate bankruptcy).
The last point needs a good PR-department (see Microsoft for how to do it succesfull). Another reason to fire the current occupation. I would even sue them too, because their sheer incompetence led to a blogentry where Bruce Schneier called SecureRF snake-oil!

CZ

NMOctober 19, 2006 11:18 PM

Bruce to quick to condemn???

I just came across this item and the comments. I admit it looks pretty unlikley but I did some research and see the company has a blog at http://rfid-security.blogspot.com/ where it appears they have responded to some of Bruce's comments - and the readers comments. Not sure if everyone should be fired but they should keep putting out data and reviews if they have them.

BLOctober 22, 2006 3:50 PM

Very smart to attack Bruce like this for conservatism and being to fast on the trigger. It might even cheat a few journalists.

But claiming that math is good math if it is new math is against all security principles and experience.

Sure there is (always) a need for new tools, but scrutiny is vital and essential.

The more critical and long term the intended security application, the tougher the scrutiny and test requirements. And they seem to claim that this is the best since oxygene was invented.

Bruce is doing nothing but pointing to the obvious. Naturally they dislike it, but it is their problem to get greed expectance and timing in line with security reality.

And then we are back at the liability issue.

NMOctober 23, 2006 7:20 AM

@ BL

Not sure who is doing the attacking. Their response seemed balanced - with facts - and an attempt at a dialogue.

New Math?? If I read their blog and paper correctly the math comes from the early 19th century - it is only two hundred years old - how old does math have to be for you???

Unfortunately, there is a history of using things before their time - in security and other areas too. We will need to see if the math works - now and in the future - but the stuff we use now is not holding up and cracks are appearing daily - see the front page of the NY Times business section today on how old math is serving the security needs of the payment industry!!!!

We better get a little more aggressive in solving these solutions rather than complaining about everything that "could be wrong".

Leave a comment

Allowed HTML: <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre>

Photo of Bruce Schneier by Per Ervland.

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