1

I'm designing a server which accepts anonymous messages using ECIES: as in, anonymous users send the server an ephemeral EC public key, and the server uses ECDH to derive a shared secret, and some KDF to obtain a shared symmetric key to decrypt the actual message. The problem is ECDH, which is among the fastest key exchange available, is really slow. From some quick tests, my computer can only handle about 3000 key exchanges per second.

An attacker could be constantly computing key exchanges and sending them to the server. I'm not too worried about this if the attacker has actually done the key exchanges. At least that way, the attacker will be doing as much work (slightly more with ECDH) as the server. The problem is an attacker can send a garbage key and make the server do a lot of work doing the key exchange on garbage. My first question is, in a reasonable implementation like OpenSSL, will the key exchange quickly return with an error, or take a long time doing useless computation?

Assuming the above is fixed, there are two more problems: an attacker could use the same ephemeral key over and over, keeping the shared secret but making the server do the key exchange repeatedly; and an attacker could precompute a lot of ephemeral keys beforehand and send them all at once.

One attempt at a solution to both problems is for the server to keep its own ephemeral keypair which changes every ~10 minutes. It can publish its ephemeral public key signed with its permanent private key. Then it would not be unreasonable for the server to remember the keys and corresponding secrets received during this period. However, this doesn't really solve the precomputation attack because correctly generated EC keys will still work with a key exchange, they just would produce garbage data. Is there any fast way for a server to know that a given key will actually decrypt the message?

Sorry for the long post, and thanks in advance to any comments.

1

Your benchmark is possibly incomplete. I have a server which features a CPU reported as: "Intel(R) Xeon(R) CPU E3-1220 V2 @ 3.10GHz". It has four cores. On that machine, OpenSSL 1.0.1f reports (with openssl speed ecdhp224) that it can perform 9096 ECDH instances per second, using the NIST P-224 curve (a fine curve, of security rated at "112 bits", comparable to RSA-2048). This is on a single core: the machine has four cores, so it can do 36000 ECDH per second, 12 times as much as the numbers you report.

Actually receiving 36000 individual messages per second can be challenging. A usual Unix-like server may run into I/O trouble much before accepting 36000 TCP connections per second. Even with UDP, it is quite possible that I/O costs will dominate, not the cryptography. This calls for benchmarks.

One may note that these figures imply an elementary cost of about 340000 cycles per EC point multiplication. Other curves with optimized implementations can do better. This article reports computation speeds down to 55000 clock cycles for curve K-233 (which offers security similar to P-224), which would translate to more than 225000 ECDH per second on my server (I think I saw a more recent article which optimized it further, down to about 40000 clock cycles, but I don't find it at the moment). What these figures show is that you should be able to achieve much better performance while sticking to standard ECIES (with standard curves).

Therefore I recommend investing the "optimized implementation" road further, rather than resorting to protocol modifications: it seems likely that you could bring the cryptography-related cost much below the I/O costs.

1

It will take a long time doing useless computation.
One could conceivably use a designated-verifier non-interactive computationally
zero-knowledge argument that the rest of the message is well-formed.

More usefully, use proofs of work and PKE with fast decryption.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.