June 04, 2006

CryptoKids, education or propaganda, ECC, speed or agenda capture?

The NSA has a newish site for kids at http://www.nsa.gov/kids/ with a Flash download and a bunch of cartoon characters. It might be fun for kids interested in crypto. Of course it is imbued with current political policies or moralities of the Bush era, and there is a slamming over on Prison Planet.

I think quite mild really. Educating kids is relatively benign as long as they don't cross the line into propaganda. What is of more worry is the continued policy of organised and paid-for propaganda by western governments through all sorts of channels, domestic and foreign. This in my view is unacceptable. In a democratic nation, the people decide such questions and vote. In a dictatorship, the dictator decides and imposes by means of control of the media.

While we are on the subject, Philipp asked me why everyone keeps asking for 16k keys. Well, other than just being perverse in the normal crypto blah blah sense, there turns out to be a reason. I'll leave it to you to decide whether this is a good reason or not.

I discovered this browsing over on Mozo's site in pursuit of something or other. Mozilla are planning to introduce SNI - the trick needed to do SSL virtual hosting - in some near future, as are Microsoft and Opera. But also mentioned was that Mozilla are introducing elliptic curve cryptography, at least into their crypto suite 'NSS'.

ECC is an emerging cryptographic standard which can be used instead of the RSA algorithm. It uses smaller keys than RSA, which means it can be faster than RSA for the same level of cryptographic strength. The US Government is moving away from the RSA cryptosystem, and onto ECC, by the year 2010. See this page from the NSA for more information.

So jumping over to the always engaging NSA's pages on ECC:

... The following table gives the key sizes recommended by the National Institute of Standards and Technology to protect keys used in conventional encryption algorithms like the (DES) and (AES) together with the key sizes for RSA, Diffie-Hellman and elliptic curves that are needed to provide equivalent security.
Symmetric Key Size
RSA and Diffie-Hellman
Key Size (bits)
Elliptic Curve Key Size

Table 1: NIST Recommended Key Sizes

To use RSA or Diffie-Hellman to protect 128-bit AES keys one should use 3072-bit parameters: three times the size in use throughout the Internet today. The equivalent key size for elliptic curves is only 256 bits. One can see that as symmetric key sizes increase the required key sizes for RSA and Diffie-Hellman increase at a much faster rate than the required key sizes for elliptic curve cryptosystems. Hence, elliptic curve systems offer more security per bit increase in key size than either RSA or Diffie-Hellman public key systems.

And, if you wish to use AES 256, then the NIST suggested length for RSA is 15360, or 16k in round numbers. The NSA also points out that the equivalent strengths in that area are computationally more expensive, perhaps 20 times as much.

Does all this matter? Not as much as one would think. Firstly, for financial cryptography, we are not so fussed about the NSA's ability to attack and crack our codes. So the Suite B standard is not so relevant, although it is an interesting sign post to what the NSA thinks is Pareto-secure (or more likely Pareto-complete) according to their calculations.

For protecting both classified and unclassified National Security information, the National Security Agency has decided to move to elliptic curve based public key cryptography. Where appropriate, NSA plans to use the elliptic curves over finite fields with large prime moduli (256, 384, and 521 bits) published by NIST.

And, we'd better not be worried about that, because when the NSA starts cracking the financial codes and sharing that data, all bets in modern democracy are off. The definition of a fascist state is that you are allowed to own stuff, but the government controls that ownership via total control of the financial apparatus. In financial cryptography, we're quite happy to deal with the 128 bit strength of the smaller AES, and 4k RSA keys or less, and rely on warnings about what's reasonable behaviour. It's called risk management.

Further, machines are fast and getting faster. Only at the margin is there an issue, and most big sites offload the crypto to hardware anyway, which perforce limits the crypto sizes to what the hardware can handle (notice how the NSA even agrees that we are still mucking around at 1k keys for the most part).

Literally, if you are worried about key sizes, you are worried about the wrong thing (completely, utterly). So it is important to understand that even though the browsers (IE7 as well, not sure about others) are moving to add ECC, and this involves sexy mathematics and we get to share beers and tall stories with the spooks, this development has nothing to do with us. Society, the Internet, the world at large. It is a strictly USG / NSA issue. In fact:

Despite the many advantages of elliptic curves and despite the adoption of elliptic curves by many users, many vendors and academics view the intellectual property environment surrounding elliptic curves as a major roadblock to their implementation and use. Various aspects of elliptic curve cryptography have been patented by a variety of people and companies around the world. Notably the Canadian company, Certicom Inc. holds over 130 patents related to elliptic curves and public key cryptography in general.

As a way of clearing the way for the implementation of elliptic curves to protect US and allied government information, the National Security Agency purchased from Certicom a license that covers all of their intellectual property in a restricted field of use. The license would be limited to implementations that were for national security uses and certified under FIPS 140-2 or were approved by NSA. ... NSA's license includes a right to sublicense these 26 patents to vendors building products within the restricted field of use. Certicom also retained a right to license vendors both within the field of use and under other terms that they may negotiate with vendors.

Commercial vendors may receive a license from NSA provided their products fit within the field of use of NSA's license. Alternatively, commercial vendors may contact Certicom for a license for the same 26 patents. Certicom is planning on developing and selling software toolkits that implement elliptic curve cryptography in the field of use. With the toolkit a vendor will also receive a license from Certicom to sell the technology licensed by NSA in the general commercial marketplace. Vendors wishing to implement elliptic curves outside the scope of the NSA license will need to work with Certicom if they wish to be licensed.

The NSA is being quite proper and is disclosing it in full. If you didn't follow here it is: You can't use this stuff without a licence. The NSA has one for USG stuff. You don't.

The RSA algorithm and the related DH family now go head-to-head with a patented and licensed alternative. As a curious twist in fate, this time RSA and friends are on the other side. We fought this battle in the 90s, as the RSA patent was used as a lever to extract rents - that's the point of the patent - but also to roll out agendas and architectures that ultimately failed and ultimately cost society a huge amount of money. (Latest estimate for America is $2.7 bn per year and the UK is up to UKP800 mn. Thanks guys!)

The way I see it, there is no point in anyone using elliptic curve crypto. It could even be dangerous to you to do this - if it results in agendas being slipped in via licensing clauses that weaken your operations (as happened last time). I can't even see the point of the NSA doing it - they are going to have to pay through the nose to get people to touch this stuff - but one supposes they want this for on-the-margin hardware devices that have no bearing on the commercial hard reality of economics.

Indeed, somewhere it said that the Mozo code was donated by Sun. One hopes that these guys aren't trying too hard to foister another agenda nightmare on the net, as we still haven't unwound the last one.

Posted by iang at June 4, 2006 12:54 PM | TrackBack

>> What is of more worry is the continued policy of organised
>> and paid-for propaganda by western governments through all
>> sorts of channels, domestic and foreign. This in my view
>> is unacceptable. In a democratic nation, the people decide
>> such questions and vote. In a dictatorship, the dictator
>> decides and imposes by means of control of the media.

In the US the following is quite common. Local government bureaucrats and politicians want to do something for which voter approval (eg for a bond issue) is required. The voters obstinantly and repeatedly vote it down. The government then hires a political science research firm (paid for with tax revenue) to conduct surveys etc. to figure out what lies need to be told to get the voters to vote "yes" and then hire a PR firm (paid with tax revenue) to roll out the recommended campaign.

It is futile to call it unacceptable. They do it and get away with it. Furthermore, this (thru whatever pretense necessary) will always happen in any democracy.


Posted by: CCS at June 5, 2006 02:22 AM

Increasing crypto key size is to security what turning lights off is to energy conservation. It's a very simple and visible act, and thus signals that you care about security (or energy conservation, respectively), but doesn't actually contribute much directly to the goal.

Posted by: nick at June 5, 2006 02:29 PM

I do not agree with the assertion that ECC is much faster than RSA. It is actually not.

The modern way of doing RSA is using multiprime RSA, where the equivalent strength of 168-bit ECC keys would be a modulus with 6 192-bit prime factors. For encryption, since you only need to encrypt 80-bit symmetric keys, you can use the "RSA for paranoids" approach and pad it to a value smaller than the smallest prime factor (let's say to 184 bits). Then you can do encryption by taking four squares in 1152-bit modulus and decryption by doing a single exponentiation in a 192 bit modulus. Quite competitive with 160-bit ECC.

For digital signatures, it is true that ECC generally beats multiprime RSA on speed and signature size, but it has a covert channel just like traditional ElGamal-based signature schemes, which is fine with automatic applications but can be a problem when digital signatures are used for legal purposes.

The big problem with RSA is the excessive cost of key generation. On a regular, cheap cellphone, it takes about an hour to generate a secure RSA key (maybe we can speed it up by a factor of 10, but even that seems quite a challenge on one hand and not even nearly enough for user convenience on the other hand). Even if it has to be done only once in a lifetime of the mobile device, making sign-up time an hour will drive many users away.

DH key generation takes about a minute, ECC key generation would take about 10 seconds. DSS signatures are of the same size as EC-DSS signatures and take the same amount of time to compute (provided that the expensive exponentiation is pre-computed). Verification takes about the same time as key generation.

On general purpose computers (notebooks and workstations) none of this matters. Everything (except for RSA key generation, which takes about 10 seconds) happens faster than one can say "elliptic curve".

Posted by: Daniel Nagy at June 8, 2006 02:30 PM

Afterthoughts. On-the-margin hardware does matter. Far more people have cellphones than computers and they are not getting any faster over time (you can always trade speed for battery life and batterly life is valued higher by the market). Cellphones, as the experimental data from my previous post shows, are not quite well equipped for public key crypto.
In other bad news, multiprime RSA is also patent-encumbered: it's a Compaq patent, AFAIK. It expires soon, and it is probably safe to ignore even at this point, but still...
I am increasingly confident that my partially PGP-compatible cellular project will stick to traditional D-H in a Schnorr group for encryption and DSA for signatures. All public key operations are doable within a minute and most can be done in the background while the user is typing the message. Signature verification will be done upon request, not automagically; once signatures are verifiable, there is no need to actually verify all of them.

Posted by: Daniel Nagy at June 8, 2006 04:33 PM
Post a comment

Remember personal info?

Hit preview to see your comment as it would be displayed.