Comment by beagle3 | Hacker News Reader

Comment by beagle3 | Hacker News Reader

Parent Full thread

I need a "digital public notary" service, where I send some hash to the notary, they sign it and give me back a signed copy (with the notary's system or public key of choice, e.g. 4096 RSA or 256 bit ECDSA or whatever)

If I want it to be considered reasonable valid proof that I did, indeed, have the data leading to the hash when the notary signed it, and I want stuff I sign today to be acceptable 10 years from now, would you consider HMAC-MD5 viable? How about HMAC-SHA1? I guess plain MD5 and SHA1 are out of the question according to this article.

Speed is not a concern here, so I would be happy with HMAC-SHA3 or anything else... Also, I keep reading that multiple signatures (MD5 + SHA1) are only as strong as the strongest one, but that does not make any sense to me - If you have two differently seeded (initial internal state) MD5 hashes, it should already be much harder to exploit (perhaps not double the number of bits, but surely a large load factor)?

The startup GuardTime offers exactly this service: http://www.guardtime.com/signatures/

You hash your data, and send the hash to them. They embed the hash in a long hash-chain, and publish the current head of the hash chain in Financial Times every month. Once the hash chain head has been published, it is impossible to forge the signed content without destroying all copies of the newspaper in existence.

It seems that the service is free for basic use, only availability SLAs and customer support is paid.

You can hedge your bets with hash combiners: 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).

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

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.

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?)

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.

GuardTime (www.guardtime.com) does keyless signatures. You send the hash, they give you a signature. The beauty of keyless is that there are no secrets involved and even if hacked or goes out of business, signatures will still be valid.

GuardTime seems like what I was looking for.

Thanks!

Have you seen Citizen Media Notary? https://github.com/Miserlou/CitizenMediaNotary

Reply on news.ycombinator.com