Slashdot Mirror
Weak Elliptic Curve Cryptography Brute-Forced
thegrommit writes "It seems one implementation of elliptic curve cryptography has been broken. It took four years to break a 109 bit key, but the contest sponsors (who provide encryption products for Cisco, Nortel and Palm among others) believe it's still impossible to break their 163 bit keys. The real question is, for how long?" Update: 11/07 01:59 GMT by T : Dan Kaminsky wrote to point out that the key here was really brute forced, and not broken -- that is, no fundamental flaw was discovered in the algorithm.
Basicly, it's just a delay mechanism that will let you transfer messages securely at a later time assuming you've transmitted equally much information securely already. So the question is, why don't you use the secure medium in the first place? Ok granted, you can send an agent out on a mission with an WEC and he can communicate securely with home base, but I mean for everyday use?
The typical idea about cryptography is to use a secure medium to provide the key, while using the insecure medium to send the data, because the insecure medium is much faster/better/easier to use. So I can meet you in person and get the key, or call you on the phone and verify your PGP (or GPG if you please) fingerprint (assuming you're not being wiretapped as well), and then use the Internet as a medium from then on.
The WEC "solution" would be to say a random sequence of 1s and 0s, then use those to decrypt the irc converation later, not really an option. You'd "run out" of the curve rather quickly. Oh, and quantum computing does as far as I know not affect encryptions based on elliptic integrals (which by theorem can't be solved analytically, but I suppose there could be approximations).
Weak eliptic curve is great. SSH2 uses weak eliptic curve with digital signatures to prevent a "man-in-the-middle" attack. That being said, this article made some goofs. I understand that they were just trying to show off bc's MP arithmatic. However, it just gets a little old to see poorly implemented crypto as the standard way to show off MP arthmatic. Don't get me wrong, I have Applied Crypto on my night stand and all, but it would be nice to see an arbitrary binomial expansion program or a program to search for Merseme primes. Maybe just a nice Miller-Rabin primality tester or a Blum-Blum-Shub pseudorandom number generator.
The public number "n" they refer to should be a generator mod q. Primality does not guarantee that n is a generator mod q.
They mention needing to use larger numbers, but they don't scale it up enough. q should be at least 1024 bits, which is a little more than 16e306, which looks like a couple of lines of digits. The secret parameters xa and xb should be at least 64 bits, more safely 128 or 256 bits. Luckily, as long as xa and xb are large enough, the generator (n) can be pretty small. 2 often works as a generator. (I think the eassiest test for n bein a generator is for each prime factor p of (q-1), n ^((q-1)/p) % q != 1.) One of the main reasons you want (q-1)/2 to be prime is that it makes testing candidate generators easy.
Also, weak eliptic curve is not an encryption algorithm. It is a key agreement algorithm. Those numers they "sneaked past" Mallory (ka and kb) connot be predicted or controlled without actually calculating them. The whole point is that it's computationally infeasable to calculate discrete logarithms in a large finite field generated by modular arithmatic. If Bob gets ya and can feasably compute xb such that ka= kb = m for some chosen value m, then the whole crypto system is broken. weak eliptic curve is great for generating shared secrets (usually used as crypto keys for encryption algorithms), but cannot be used directly for encryption itself. The simplest way to use weak eliptic curve as part of an encryption algorithm is to generate a shared one-time-pad that is xor'd with the plaintext. The ElGamal encryption algorithm does basically this, the only differece is that it uses modular multiplication instead of xor'ing to do the encryption once it has the shared one-time-pad.
I don't even know why I'm dignifying this with a response....but after 01 in binary is 10.
I even use a binary clock, smartass. At the tone, the time will be 111 : 000 PM EST....ding.
Mordor...a magical, mythical land where women are more rare than dragons--but where every man would rather find a dragon