NSA Watch

Three things.

U.S. Patent #6,947,978:

Method for geolocating logical network addresses

Abstract: Method for geolocating logical network addresses on electronically switched dynamic communications networks, such as the Internet, using the time latency of communications to and from the logical network address to determine its location. Minimum round-trip communications latency is measured between numerous stations on the network and known network addressed equipment to form a network latency topology map. Minimum round-trip communications latency is also measured between the stations and the logical network address to be geolocated. The resulting set of minimum round-trip communications latencies is then correlated with the network latency topology map to determine the location of the network address to be geolocated.

"Fact Sheet NSA Suite B Cryptography":

The entire suite of cryptographic algorithms is intended to protect both classified and unclassified national security systems and information. Because Suite B is a also subset of the cryptographic algorithms approved by the National Institute of Standards, Suite B is also suitable for use throughout government. NSA's goal in presenting Suite B is to provide industry with a common set of cryptographic algorithms that they can use to create products that meet the needs of the widest range of US Government (USG) needs.

"The Case for Elliptic Curve Cryptography":

Elliptic Curve Cryptography provides greater security and more efficient performance than the first generation public key techniques (RSA and Diffie-Hellman) now in use. As vendors look to upgrade their systems they should seriously consider the elliptic curve alternative for the computational and bandwidth advantages they offer at comparable security.

Posted on September 30, 2005 at 7:31 AM • 20 Comments

Comments

Gustavo BittencourtSeptember 30, 2005 8:38 AM

"Elliptic Curve Cryptography provides greater security and more efficient performance than the first generation public key techniques"

But ECC was less researched than the others algorithms!

ZSeptember 30, 2005 8:46 AM

"As vendors look to upgrade their systems they should seriously consider the elliptic curve alternative for the computational and bandwidth advantages they offer at comparable security"

and the advantages for the NSA.....

WooSeptember 30, 2005 9:01 AM

@2: which would be? As far as I know, even NSA has no useful attack against EC systems yet. Or are you referring to the fact that shorter keys are faster to bruteforce?

Gustavo BittencourtSeptember 30, 2005 9:24 AM

@Woo

I am saying that primes properties (used in RSA) have being studying for centuries, but the Elliptic Curve studies has only few decades. So, it is reasonable to presume that with more research, ECC will must increase the key size to maintain the same strength that the older algorithms.

DarkFireSeptember 30, 2005 9:35 AM

As far as the watches are concerned - it's worth noting that every single *suicide* attack, without exception, has featured a hand-operated detonator.

More movie-plot security? Seems like it...

wiredogSeptember 30, 2005 10:08 AM

"time latency of communication" etc. Hmmm. Isn't that the method Cliff Stoll describes in "The Cuckoo's Egg?"

Bruce SchneierSeptember 30, 2005 11:39 AM

"'Elliptic Curve Cryptography provides greater security and more efficient performance than the first generation public key techniques'

"But ECC was less researched than the others algorithms!"

I agree with you, not the NSA.

ProhiasSeptember 30, 2005 11:46 AM

> "The patent link doesn't find the patent."

> It does when I try.

It is flaky. Works 5 times out of 10 :)

Josh O.September 30, 2005 12:00 PM

> It is flaky. Works 5 times out of 10 :)

I'm doing way better than you. It works every other time for me!

Jonathan LutzSeptember 30, 2005 12:10 PM

@ Gustavo and Woo

But thats not what Certicom says ;)

You guys have a point when it comes to EC-based protocols. They just haven't been around that long. On the other hand, the generic study of elliptic curves and the elliptic curve discrete log problem (ECDLP) is not new. I believe its centuries old.

I'll leave it to the mathematical historians to verify/correct me on this... just thought I'd throw it out there.

CypherpunkSeptember 30, 2005 1:19 PM

Why not join the 21st century and admit that your earlier skepticism about elliptic curve cryptography (http://www.schneier.com/crypto-gram-9911.html#EllipticCurvePublic-KeyCryptography) was unfounded? If it's good enough for the NSA, shouldn't that be good enough for ordinary users?

And what about bilinear pairing based cryptography, which is built on elliptic curves? Half the papers at crypto conferences these days are pairing based. That's because this new technology allows for capabilities far beyond what can be achieved with old techniques.

Further, the kinds of issues you have raised with elliptic curves apply with at least equal force to cryptosystems built on factoring and discrete logs, like RSA and DH.

Pairing is wired, elliptic curves are tired, and RSA is expired. You need to get with the program and stop living in the 1990s.

ramananSeptember 30, 2005 1:21 PM

ECC is relatively new, but the study of Algebraic Curves is not new by any stretch. Also, both points raised in the article on key size and speed are valid. I wouldn't be so fast to dismiss ECC simply because it has been endorsed by the NSA. There are plenty of smart people researching ECC.

On preview, what Cypherpunk said.

involved partySeptember 30, 2005 5:17 PM

About the first patent. I'm pretty sure my non-disclosure agreement from a previous employer is expired.

We worked on this around late 2003/early 2004. Some guy from the NSA had a one hour-ish presentation about the technology.

We never licensed the technology, but at the base it works like this:

1. Multiple servers all ping the target IP multiple times (I think they figured optimal was about 8 times).
2. You discard all but the lowest latency (the closest to the wire latency).
3. You drop the constant part of all the latency involved, this amounts to say you substract the fastest from all the others.
4. You use the remaining latencies as keys to lookup up a table of known location for the closest match.

It requires a database of known locations. In tests, they had 50 miles accuracy in the bay area, I think. And they estimated that 6000 wll chosen locations could give metropolitan area precision over the continental us.

My memory is sketchy (we never ended up doing anything with this, I believe they never finalized the exclusivity contract they were trying to negociate. Might have something to do with the fact the company was knee deep in online gaming.) so I might be wrong on some details.

Ian EiloartOctober 4, 2005 7:01 AM

In the ECC article, it says: "To attack an algorithm with a k-bit key it will generally require roughly 2k-1 operations." Some mistake, surely?

Alexandre CARMEL-VEILLEUXOctober 4, 2005 8:22 AM

@Ian:

Probably a font issue, it should be 2^(k-1) or half the keyspace. I'm guessing the exponentiation got dropped from the formatting.

Pat CahalanOctober 4, 2005 5:27 PM

From the paper:

> Hence, elliptic curve systems offer more security per bit increase in key
> size than either RSA or Diffie-Hellman public key systems.

This statement is not equivalent to this statement:

> Elliptic Curve Cryptography provides greater security and more efficient
> performance than the first generation public key techniques (RSA and
> Diffie-Hellman) now in use.

If there is a practical limit to the necessary key size. Only the second part of the statement is true (it's more efficient)

(in other words, if a 128 bit symmentric or 3072 bit D-H key is unattackable, increasing the key size past 3072 provides no "extra" security).

I'm not saying that it's not more efficient.

There is another sort of shaky logical conclusion:

> However, unlike the RSA and Diffie-Hellman cryptosystems
> that slowly succumbed to increasingly strong attack algorithms,
> elliptic curve cryptography has remained at its full strength since
> it was first presented in 1985.

Taken together with this:

> In the public domain, more general theoretic attacks on the fundamental
> problems of factoring and discrete logs made steady progress until the
> early 1990's. Since that time, no dramatic improvements in these
> attack algorithms have been published.

10 years of no progress against a widely deployed technology seems to be a pretty good indicator that it's fairly secure. Sure, no progress against elliptic curve encryption is also an indicator that it's fairly secure, but I don't follow academic journals enough to know who's been attacking what, and for how long.

I don't find greater efficiency to be a compelling trade-off when comparing a widely deployed technology that has been relatively unscathed for 10 years vs a less widely deployed technology.

Unless I'm selling e-c cryptographic products.

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..