Re: [Caml-list] Ocaml and cryptography

[Gerd Stolpmann <info@gerd-stolpmann.de>]

Am Donnerstag, den 24.03.2011, 21:17 +0900 schrieb Jehan Pagès:
> Hi,
> 
> I was just having a few thoughts/questions.
> 
> I have developed, in the context of another project, a Sha1
> implementation (also a HMAC implementation and above this all a SASL
> implementation with SCRAM-SHA1 mechanism support). That's not a
> binding to any existent library and is fully native Ocaml. No C in
> particular.

Funnily I did a SCRAM implementation for GSS-API a few weeks ago:
https://godirepo.camlcity.org/svn/lib-ocamlnet2/trunk/code/src/netmech-scram/

It does not implement the crypto primitives in Ocaml, though, but simply
uses XL's cryptokit package - which is a quite complete C
implementation.

> That's all working fine and is fast enough for being comfortable. But
> that's definitely not as fast as a C implementation.
> I made a small benchmark with OpenSSL's SHA1 functions and mine. Both
> tests are loops running 10.000 Sha1 of the same string, then exiting.
> Basically C goes around 6-10 times faster.

This is something I observed already earlier for my cryptgps package
(which implements Blowfish and DES -
https://godirepo.camlcity.org/svn/lib-cryptgps/trunk/). Ocaml is not a
good compiler for this kind of code. I tried it both with int32 and with
normal ints (i.e. a 32 bit word is represented as two ints, where each
int gets 16 bits). Both approaches achieve about the same speed (on 32
bit platforms), and are a small factor slower than C (I think it was
around 4-5 times slower after endless optimizations).

One of the problems seems to be that you cannot enforce to keep the
int32 values in registers all the time (at least in the inner loops). So
there are constantly boxing and unboxing operations. Even worse, this
also causes that memory is allocated all the time, and is of course also
cleaned up all the time.

I haven't checked on a 64 bit platform (at that time - ~10 years ago - I
did not have access to one). 64 bit platforms have more registers, and
there is no need to use int32.

My recommendation would be to avoid Ocaml for this type of code. The
compiler does not recognize that there is a loop it could completely
translate in unboxed mode. As far as I understand, a lot of work would
be required to make the compiler better here, and it would only affect a
few types of code (cryptography, pixel graphics, inner loops of
numerical algos).

Gerd


> Note: my machine is a small notebook which is not powerful enough to
> play most video games, nor even watch videos when they have a little
> too high quality (and I am not talking of HD)! So on common desktop
> machines, the test should go much faster for both version, but I guess
> keep the same speed proportions. You might want to raise the loop to
> 100.000 though in order to see the difference.
> 
> Here are examples of such a run checked with time (there is some
> variance between 2 runs, but the Ocaml version usually computes the
> 10.000 hashes in around 0.4 seconds while the C version computes them
> in about 0.06 seconds):
> 
> ~/SHA1$ time ./obench
> 
> real	0m0.416s
> user	0m0.400s
> sys	0m0.000s
> ~/SHA1$ time ./cbench
> 
> real	0m0.069s
> user	0m0.060s
> sys	0m0.004s
> 
> I checked the standard lib code and the MD5 code has been written in C
> over there. Apparently the cryptokit library as well is writing core
> cryptography in C.
> 
> I still think my code is pretty clean. I have made as much
> optimization as I saw possible and though maybe other may be able to
> still optimize it, I wonder up to which point now.
> 
> I am doing all computations over Int32 because the Sha1 algorithm
> works over 4 octets words. At first, I was doing the "naive" approach
> and was working on strings directly (going back and forth from a
> character code to the character) but that was like extremely slow
> (really). Still it allowed me to get the first working implementation.
> 
> Implementing with int, which is supposed to be much faster than int32,
> would be nice (even though integers can be 64 bits on a 64 bits
> platform, I can just mask the 4 higher octets in such case), but int
> in OCaml is actually 31/63 bits because of the flag bit so I cannot
> represent SHA1 words with int.
> 
> For those interested, you can download the benchmark (which includes
> the code of Sha1) here:
> http://download.tuxfamily.org/ocamlxmpp/sha1_benchmark.tar.gz (just
> 3ko).
> Just run make in the SHA1 directory which will be uncompressed, it
> will create cbench and obench (a SSL library is needed for the C
> benchmark, likely OpenSSL or other with the same API. Nothing external
> is needed for the Ocaml one).
> 
> Maybe anyone has suggestions to improve?
> Or Ocaml simply cannot compete with C here? (I don't mean to do
> better, but getting closer would be already nice)
> 
> Thanks.
> 
> Jehan
> 
> P.S.: don't tell me there are already libraries out there which binds
> to C libraries, so why did I ever bother write this Module. I did
> this:
> 1/ for fun of writing a full SHA1 implementation in Ocaml.
> 2/ because I was wondering how fast it could be.
> 3/ No reason.
> 4/ Because and that's all. ;-)
> 


-- 
------------------------------------------------------------
Gerd Stolpmann, Bad Nauheimer Str.3, 64289 Darmstadt,Germany 
gerd@gerd-stolpmann.de          http://www.gerd-stolpmann.de
Phone: +49-6151-153855                  Fax: +49-6151-997714
------------------------------------------------------------