3 ms·

Something is nagging me for quite some time. DJB invented curve25519, which is advertised to offer 128 bits security. On the other hand, DJB also said 128 bit

Something is nagging me for quite some time. DJB invented curve25519, which is advertised to offer 128 bits security. On the other hand, DJB also said 128 bits are not enough for symmetric crypto. https://cr.yp.to/snuffle/bruteforce-20050425.pdf https://cr.yp.to/snuffle/bruteforce-20050425.pdf This makes me a bit uneasy: would a parallel brute force search would be much more difficult for elliptic curves than it would for symmetric cyphers? Why? By the way, a similar problem arises with poly1305. I'm missing something.

mSparks 10y ago
I think what you are missing is the huge investment the "bad guys" have put into getting people to believe insecure communications are in fact secure.
dtech 10y ago
Afaik breaking a 128-bit ECC key does not require brute-forcing 2^128 keys but rather computing 1 difficult problem on a 128-bit input. Breaking e.g. AES key of n bits requires you to try 2^n combinations, but the actual computation per key is very fast. [1] https://crypto.stackexchange.com/questions/13249/why-can-ecc-key-sizes-be-smaller-than-rsa-keys-for-similar-security https://crypto.stackexchange.com/questions/13249/why-can-ecc...
cesarb 10y ago
Well, curve25519 uses 256-bit keys (actually, a few bits less than 256). The parallel brute force search should take time similar to that of a 256-bit symmetric cipher. The reason curve25519 has a security level of only 128 bits is that ECDLP takes time proportional to the square root, so half the number of bits (https://en.wikipedia.org/wiki/Elliptic_curve_cryptography#Key_sizes https://en.wikipedia.org/wiki/Elliptic_curve_cryptography#Ke...). As for poly1305, it actually uses not one, but two separate 128-bit keys. The authentication tag computed using the first key is encrypted with the second key. For a brute force search, it should be as hard as breaking something with a single key of around 256 bits.
Natanael_L 10y ago
A batch attack on 128 bit symmetric lowers the total cost to below 2^128 computations to successfully decrypt messages. The cost approximately follows the birthday paradox math, and thus becomes cheaper at a slightly faster than linear rate given a higher volume of ciphertexts. A batch attack on asymmetric ECDSA like curve25519 costs MORE than 2^128, it just grows logarithmicly instead of linearly. That's why.

mSparks 10y ago

I think what you are missing is the huge investment the "bad guys" have put into getting people to believe insecure communications are in fact secure.

dtech 10y ago

Afaik breaking a 128-bit ECC key does not require brute-forcing 2^128 keys but rather computing 1 difficult problem on a 128-bit input. Breaking e.g. AES key of n bits requires you to try 2^n combinations, but the actual computation per key is very fast. [1] https://crypto.stackexchange.com/questions/13249/why-can-ecc-key-sizes-be-smaller-than-rsa-keys-for-similar-security https://crypto.stackexchange.com/questions/13249/why-can-ecc...

cesarb 10y ago

Well, curve25519 uses 256-bit keys (actually, a few bits less than 256). The parallel brute force search should take time similar to that of a 256-bit symmetric cipher. The reason curve25519 has a security level of only 128 bits is that ECDLP takes time proportional to the square root, so half the number of bits (https://en.wikipedia.org/wiki/Elliptic_curve_cryptography#Key_sizes https://en.wikipedia.org/wiki/Elliptic_curve_cryptography#Ke...). As for poly1305, it actually uses not one, but two separate 128-bit keys. The authentication tag computed using the first key is encrypted with the second key. For a brute force search, it should be as hard as breaking something with a single key of around 256 bits.

Natanael_L 10y ago

A batch attack on 128 bit symmetric lowers the total cost to below 2^128 computations to successfully decrypt messages. The cost approximately follows the birthday paradox math, and thus becomes cheaper at a slightly faster than linear rate given a higher volume of ciphertexts. A batch attack on asymmetric ECDSA like curve25519 costs MORE than 2^128, it just grows logarithmicly instead of linearly. That's why.