Making the client do all the work

By: on June 26, 2006

This paper proposes to reduce the workload of SSL servers by making the clients carry as much of the crypto-related load as possible. I think it’s possible to do even better.

Key agreement: In the above, the server only has to do an RSA public key operation, which is cheap if the exponent is low (eg three). However, we can do even better (and have a stronger security bound too) by using the Rabin operation – modular squaring – instead. This is more than twice as fast as the RSA operation with exponent three. Normally, Rabin encryption is slowed down by certain steps that are needed to handle the fact that modulo a large semi-prime, most numbers that have square roots have four of them, and the recipient has to know which one you mean. However, modern KEM schemes greatly reduce this cost, and Rabin-KEM encryption is just about the fastest public key operation I know of, with the exception of certain probabalistic signature checking schemes.

Signatures: a trick has been missed here. Modern “one-time” signature schemes (eg “Better than BiBa“) can actually sign many messages before the private key must be discarded for security, which in an online/offline signature scheme greatly reduces the number of documents to be signed. For even greater efficiency, a hash tree can be used to sign many one-time keys simultaneously. At the cost of imposing a small latency on all clients, we can even discard the one-time signatures, avoiding a patent, and directly use hash trees; as many clients try to connect, the server can place the documents to be signed in a hash tree and sign them all with one operation. This scheme scales very nicely: the server performs its public key operation at a constant rate of, say, ten per second, and no matter how many clients are trying to connect these signatures will serve to authenticate the server to them all. The clients may have to wait an extra tenth of a second for the connection to complete, but this cost will be small in the cost of connecting to a busy server.

Client puzzles I’m not sure I understand why mixing up the client puzzle step and the public key generation step is beneficial.

With this scheme, the server only has to do one modular squaring per client – and even that only when the client has proven its worth by solving a client puzzle. I wonder if it’s possible to do even better?

FacebookTwitterGoogle+

2 Comments

  1. Kemal Bicakci says:

    Thanks for the comments.

    For the key aggrement part, yes it is true that Rabin public key operation has a better performance. But we have a goal to keep public key crypto primitive as it is in the paper.

    For the signatures, one has to be very careful to balance between the time for signing and the length of the signature. A rule of thumb is that once you improve the signing time or the number of signatures per public key, it is very likely that you increase the size of signatures.

    For the client puzzle, reverse SSL without client authentication requires the client to generate a public key – private key pair. This part explores the possibility to use this for something extra (for protection against DoS attack).

  2. Paul Crowley says:

    we have a goal to keep public key crypto primitive as it is in the paper

    To what end? If you’re changing the protocol to make the server more efficient, why not make the most efficient choice? It might make sense to use RSA where the client already has an RSA encryption key which is signed with some certificate, but otherwise I don’t see what you gain.

    For the signatures, one has to be very careful to balance between the time for signing and the length of the signature. A rule of thumb is that once you improve the signing time or the number of signatures per public key, it is very likely that you increase the size of signatures.

    You don’t specify the “k” value that you use for Lamport’s scheme in your paper, except to say that it is the same as the length of the message. I assume this means that the “message” is the 160 bit hash of what is being signed. So you have to send the one-time public key, the signature of the one-time public key, and the signature of the message: that’s 160x2x160 + 320 + 160×160 = 77120 bits = 9640 bytes. “Better than BiBa” requires (for k=20, t=8) 256×160 + 320 + 20×160 = 44480 bits = 5560 bytes.

    Hash trees add hardly anything to the signature size: if you put 1024 one-time public keys in a tree and sign that, it only adds 10×160 bytes to your output. Given that, it’s probably worth trading off multi-shot use for signature size as you say, especially since you have leisure in the early hours of the morning to generate lots of one-time keys. But there are efficient schemes with smaller signatures/public keys than either “Better than BiBa” or the Lamport scheme you outline.

    Of course, my batching scheme does away with the need for one-time signatures altogether, reducing the signature overhead to more like 320 + 10×160 = 1920 bits = 240 bytes for 1024 signatures per signing operation.

    For the client puzzle, reverse SSL without client authentication requires the client to generate a public key – private key pair. This part explores the possibility to use this for something extra (for protection against DoS attack).

    If you don’t tie the two together, a client can use a single public-private key pair for lots of servers, greatly reducing the cost of connection. In practice generating such a key pair is probably too costly a client puzzle for most circumstances.

Post a comment

Your email address will not be published.

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>