Schneier on Security

A blog covering security and security technology.

« Friday Squid Blogging: Archibald | Main | Torture Bill as C Code »

October 9, 2006

The Doghouse: 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

To receive these entries once a month by e-mail, sign up for the Crypto-Gram Newsletter.

Comments

Chuck • October 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.

Kne • October 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.

Rich • October 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?

Anonymous • October 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 Lodato • October 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.

Rich • October 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?

Alex • October 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.

John • October 9, 2006 12:34 PM

Here's another great one related to wireless:

http://www.merunetworks.com/news/press_releases/...

While no claims of new and improved encryption protocols are made, their claim of "transmission scrambling" sounds like snake oil to me.

Valdis Kletnieks • October 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.

Braid links • October 9, 2006 2:05 PM

Searching on the mathematics behind this is not encouraging, I located this link
http://www.cmis.brighton.ac.uk/staff/agf/...

For instance this is seems unrefuted
"A Practical Attack on the Root Problem in Braid Groups"
http://eprint.iacr.org/2005/459

Or this:
"This work emphasizes an important problem of braid based cryptography: the random generation of good keys. We present a deterministic, polynomial algorithm that reduces the conjugacy search problem in braid group. The algorithm is based on the decomposition of braids into products of canonical factors and gives a partial factorization of the secret: a divisor and a multiple."
http://portal.acm.org/citation.cfm?id=1127520

Alex • October 9, 2006 5:06 PM

@Braind links:

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

Rich2 • October 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 Skala • October 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.

Greg • October 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.

Braid links • October 10, 2006 5:28 AM

@ Alex

I am not certain what to think.

Normally this kind of crypto seems to be considered broken and weak towards heuristic attacks.
www.cs.bris.ac.uk/Research/CryptographySecurity/Workshop/Slides/Vasco.pdf

There is theoretical work trying to make it secure as we clearly would like crypto with less computational requirements.
eprint.iacr.org/2006/079.pdf

Here, some people are trying to make commercial products out of this and seems to have been trying for many years.

They present a magic "algebraic eraser" and continue to claim it is secure - but do they document or refute it is easily breakable by heuristic attacks?

Imagine a deployed passport based on this assumption and suddenly another Jon comes up with a open source program to break any passports in two minutes. The same attack can steal money from your electronic vallet, access secured spaces in your name or even steal your identity through breaking your digital signature.

Worse than a broken technology is one that is assumed secure, but not. Enigma as an example - it kills and the attackers may go very far trying to conceal the fact that it is broken.

But NSA would perhaps love to push a technology, where they hope only their number crunchers can break the keys.

Marketing snake-oil seems to be only the top of the iceberg.

derf • October 10, 2006 10:12 AM

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

Rich2 • October 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 Murray • October 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.

MikeAt1140 • October 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

Braid Links • October 11, 2006 2:04 AM

@ Mike
Sure Anshell & co has for years tried to push this - first papers was in the 90s. All honour to the attempts to save the technology - faster and cheaper crypto is highly needed.

The problem is - as your link also say - that this technology is by its critics in academics considered vulnurable to for instance heuristic attacks. They have proven this to be the case several times.

Simple marketing snake-oil is not the main issue here.

@ Bruce
You are talking about liability of security.

Here you have a nowell problem. A technology with known weaknesses being pushed as failproof for profit.

In US the legal concept of punitive damage apply where a provider is hiding a known problem with their product later causing damage. This is what happened when the tobacco companies.

SecurRF clearly do nothing towards mentioning the track history of a broken crypto only recently amended to claim perfection.

What happens when one of the many highly sensitive security applications, they claim to solve, fail to known weaknesses?

The want to use this for payments, passports, healthcare etc.

Who pays?

When? After the flods of fraud accellerate as spam and virus today?

MikeAt1140 • October 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 Zurnieden • October 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.

Braid links • October 13, 2006 11:38 AM

> please fire your PR-department
> immediately if you haven't done it already.

Not only the PR-department. Also the business people - this technology is clearly not ready for commercialisation. Maybe 10 years from now - hopefully.

Christoph Zurnieden • October 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!

Braid links • October 16, 2006 4:02 PM

> I can't decide that without all of the details or at least the paper promised for december(?).

Of course, but the technology as such seems highly vulnurable and have claims that are so high that for security solutions, there need to be a serious scrutinty and time for attacking this before it can be relied upon - best case.

Compare it with how long it took untill RSA type of cryptography was accepted - and RSA didnt start with several cracks.

Of course it can be used for playground type of applications, where no security is close to being as good as this. But then whats the purpose for the customer?

Sorry, investors have to be very patient to invest in this - and somehow I doubt that impression was given to investors by the business people.

NM • October 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.

BL • October 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.

NM • October 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".

Post a comment

Schneier.com is a personal website. Opinions expressed are not necessarily those of BT.

Subscribe via Kindle

Blog Menu

Search

Powered by DuckDuckGo

Blog Home Page
100 Latest Comments

Archives by Date

2013 J F M A M
2012 J F M A M J J A S O N D
2011 J F M A M J J A S O N D
2010 J F M A M J J A S O N D
2009 J F M A M J J A S O N D
2008 J F M A M J J A S O N D
2007 J F M A M J J A S O N D
2006 J F M A M J J A S O N D
2005 J F M A M J J A S O N D
2004 J F M A M J J A S O N D