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?
June 26th, 2006
Paul Crowley
When I started on this, I thought I’d be able to dash off a script to keep my CPU fan quiet in a few hours. I’ve just spent far too much of this weekend obsessively hacking on it and testing it, and after creating a tool of great sophistication, I have basically given up in defeat. I’m now using a thermostat-like approach; either the fans are on full or on minimum, nothing in between.
First installment of the saga
Continue Reading June 26th, 2006
Paul Crowley
I had a brief email exchange with the developers of
Dialyzer, the
static analyzer (some might call it a type checker) for
Erlang programs. Currently Dialyzer only
performs analysis on the functional fragment of Erlang and I was
enquiring whether to extend that to handle communication. That would
allow the detection of basic input/output mismatches, e.g. when a
message is sent to a process that does not match any of the patterns
it is willing to receive.
Going further, one might be able to employ the various techniques
developed for process algebras to reason about the concurrent
behaviour of Erlang programs and, for example, detect deadlocks and
enforce information flow security properties. A good example of such a
tool is TyPiCal. It
would be amazing to have something like that for Erlang. After all,
what makes Erlang interesting is not the functional programming aspect
currently checked by Dialyzer, but its support for concurrency,
distribution and fault-tolerance. It is incredibly difficult to
correctly implement systems that involve the latter. If there is any
area of programming in which we want the help of static analysis then
this is it!
Anyway, it turns out that there are no immediate plans to extend
Dialyzer in that direction. However, I was pointed at some related
research that I had hitherto been unaware of: Karol Ostrovský’s PhD
thesis, which in
Part II describes the
sound instantiation of Kobayashi’s generic type system for the
pi-calculus to session types,
extension of session types to multi-session types (which, afaict,
handle sessions that involve asynchronous comms, and servers that
handle multiple sessions without spawning),
application of multi-session types to type check communication of
Erlang processes.
Overall this looks like a promising attempt at constructing a
process-algebra-based type system that is decidable and yet expressive
enough to reason about non-trivial real-world protocols (IMAP4 is used
as an example). The theory behind it seems to be quite involved, but
that could just be due to the presentation format - a thesis rather
than a paper. It will be interesting to see whether this research is
carried any further and eventually materialises in tools for Erlang.
June 26th, 2006
matthias