I am designing a user registration protocol for a system where I control both clients and servers. The aim is to establish a symmetric key for subsequent authentication, while minimizing the work load on the server side. The security concerns are less about privacy than about integrity of the system and resistance to DoS attacks. I thought about doing something like this:

  1. Client generates an RSA public-private key pair
  2. Client sends public key to server
  3. Server returns randomly generated key, encrypted in the public key

Is there any risk that malicious clients may choose public keys that cause undue work load on the server? Or, other problems? Is there a better way to minimize load on the server in the face of malicious clients, while still insuring the security of the key exchange for cooperative clients?

  • $\begingroup$ You could use SRP with a good password hashing scheme (time-/ memory intense, like Argon2, Lyra2, Catena, yescrypt, scrypt, bcrypt, PBKDF2). $\endgroup$
    – SEJPM
    Commented Aug 2, 2015 at 16:19
  • $\begingroup$ I fixed an error in what I was suggesting. $\;$ $\endgroup$
    – user991
    Commented Aug 2, 2015 at 22:23

1 Answer 1


Steps 5 and 7 remain very important even when one ignores DoS attacks.

  1. $\;\;\;$ The RSA key-pairs use ​ e = 3
  2. $\;\;\;$ Server signs $\: \langle \hspace{-0.03 in}$ RSA_modulus , RSA_ciphertext $\rangle \:$ and returns that to Client in step 3
  3. $\;\;\;$ If computation is significantly more of a bottleneck than communication,
    $\;\;\;$ then Client computes a sufficiently accurate estimate of its modulus's
    $\;\;\;$ reciprocal in step 1 and sends that estimate to server in step 2
  4. $\;\;\;$ In general, if step 6 is used then its estimate may need to go into what gets signed
    $\;\;\;$ in step 5. $\:$ However, I believe the most straight-forward way to use estimates from
    $\;\;\;$ step 6 would have the property that if an adversary changed it to a bad "estimate",
    $\;\;\;$ then Server will either detect that or get the right result anyway.
    $\;\;\;$ If step 6 is used and the use of its estimates has that property and the key(s)
    $\;\;\;$ is(are) only used as input to a secure MAC scheme and/or a stateless IND-CPA
    $\;\;\;$ encryption scheme and those schemes are only used for authentication
    $\;\;\;$ and/or (possibly-already-authenticated-)encryption respectively, then the
    $\;\;\;$ estimate from step 6 does not need to go into what gets signed in step 5.
    $\;\;\;$ (It's fine if the encryption is used in a way that keeps state, but I only see a proof for the
    $\;\;\;$ cases in which the underlying encryption scheme is IND-CPA despite not keeping state.)

Explanation of what's going on in #7:
By changing the honest client's estimate to a bad one, the adversary might be able to make
the event "server aborts" depend in a useful(-to-the-adversary) way upon what the resulting
key would otherwise have been and the randomness that would've been used to encrypt it.
The assumptions I gave are enough to guarantee that subsequent
communication remains secure despite such any such dependency.

  • $\begingroup$ Thanks for your detailed answer. I had neglected 5. BTW, with e=3, I find encryption is 40 times faster than decryption, versus 20 times faster with e=65537, which is just what I need. However, I have since realized that I need to limit the registration rate for other reasons, so this issue is less important. Still, any time you can prevent strangers from making you do more work than they are doing is a good thing. $\endgroup$ Commented Aug 6, 2015 at 3:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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