5 ms·

You can hedge your bets with hash combiners: http://homepages.cwi.nl/~pietrzak/publications/FLP08.pdf http://homepages.cwi.nl/~pietrzak/publications/FLP08.pdf

by pbsd 14y ago

You can hedge your bets with hash combiners: http://homepages.cwi.nl/~pietrzak/publications/FLP08.pdf http://homepages.cwi.nl/~pietrzak/publications/FLP08.pdf C_{4P}(SHA-2-512, SHA-3-512) should remain solid for a long long time. Your point of failure is, now, the signature scheme. To last for decades, do not use RSA or DSA. Use elliptic curve DSA or similar (EdDSA comes to mind).

AnthonyMouse 14y ago
What's the reasoning for why RSA/DSA with a sufficient key length would be vulnerable sooner than elliptic curve?
- tptacek 14y ago
  Mathematicians are making progress with the multiplicative groups used by RSA and DSA, which indicates that the security margins for RSA and DSA are lower than they are for elliptic curve groups. I can't pretend to be literate here but Daniel Bernstein would point out the numeric field sieve as an example of something that threatens RSA and DSA but not ECC. As I understand it, ECC is also significantly faster.
  - beagle3 14y ago
    Does anyone know of a smart card that implements ECC? Accessible from Linux is a plus. (And in a related issue - does anyone know why smart card deployment in the US is so far behind Europe? Why is it that I need to get a PGPcard from germany and can't find anything comparable in the US?)
- pbsd 14y ago
  A 512-bit hash provides roughly 256 bits of resistance against collision attacks. We (presumably) want to match that level of strength with our signature scheme. RSA and DSA are based on the integer factorization and finite field discrete logarithm problems, respectively. The number field sieve has a complexity (very roughly) proportional to 2^(b^(1/3)), for b-bit keys. This means that keys have to be proportional to 2^(b^3) to achieve b-bit security. For a concrete example, 256-bit security requires ~16384 RSA/DSA keys (this is using a less rough approximation of the NFS complexity). On the other hand, well-chosen elliptic curve groups have (or appear to) much less structure than the above. In generic groups, the best we can do to solve the discrete logarithm are generic attacks, like Rho or BSGS. Those run in time proportional to 2^(b/2). Therefore, we only need keys of size 2^(2b) to achieve b-bit security (512-bit keys for 256-bit security). Bit for bit, elliptic curves are much more efficient to deliver the same level of security. This results in other advantages, like tolerable speed.

by pbsd 14y ago

AnthonyMouse 14y ago

What's the reasoning for why RSA/DSA with a sufficient key length would be vulnerable sooner than elliptic curve?

tptacek 14y ago
Mathematicians are making progress with the multiplicative groups used by RSA and DSA, which indicates that the security margins for RSA and DSA are lower than they are for elliptic curve groups. I can't pretend to be literate here but Daniel Bernstein would point out the numeric field sieve as an example of something that threatens RSA and DSA but not ECC. As I understand it, ECC is also significantly faster.
- beagle3 14y ago
  Does anyone know of a smart card that implements ECC? Accessible from Linux is a plus. (And in a related issue - does anyone know why smart card deployment in the US is so far behind Europe? Why is it that I need to get a PGPcard from germany and can't find anything comparable in the US?)
pbsd 14y ago
A 512-bit hash provides roughly 256 bits of resistance against collision attacks. We (presumably) want to match that level of strength with our signature scheme. RSA and DSA are based on the integer factorization and finite field discrete logarithm problems, respectively. The number field sieve has a complexity (very roughly) proportional to 2^(b^(1/3)), for b-bit keys. This means that keys have to be proportional to 2^(b^3) to achieve b-bit security. For a concrete example, 256-bit security requires ~16384 RSA/DSA keys (this is using a less rough approximation of the NFS complexity). On the other hand, well-chosen elliptic curve groups have (or appear to) much less structure than the above. In generic groups, the best we can do to solve the discrete logarithm are generic attacks, like Rho or BSGS. Those run in time proportional to 2^(b/2). Therefore, we only need keys of size 2^(2b) to achieve b-bit security (512-bit keys for 256-bit security). Bit for bit, elliptic curves are much more efficient to deliver the same level of security. This results in other advantages, like tolerable speed.