From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p2ODR63D021074 for ; Thu, 24 Mar 2011 14:27:06 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AhwCAMPjik3U436rkWdsb2JhbACERKEEFAEBAQEJCwsHFAMiiE2oZ5EUAoElg0t3BIgqiBc X-IronPort-AV: E=Sophos;i="4.63,237,1299452400"; d="scan'208";a="78986060" Received: from moutng.kundenserver.de ([212.227.126.171]) by mail3-smtp-sop.national.inria.fr with ESMTP; 24 Mar 2011 14:27:01 +0100 Received: from office1.lan.sumadev.de (dslb-188-097-066-234.pools.arcor-ip.net [188.97.66.234]) by mrelayeu.kundenserver.de (node=mreu1) with ESMTP (Nemesis) id 0LsMfM-1PrrVj1Ou0-011sGP; Thu, 24 Mar 2011 14:26:59 +0100 Received: from [192.168.1.111] (546BE640.cm-12-4d.dynamic.ziggo.nl [84.107.230.64]) by office1.lan.sumadev.de (Postfix) with ESMTPA id CF5DB5F701; Thu, 24 Mar 2011 14:26:58 +0100 (CET) From: Gerd Stolpmann To: Jehan =?ISO-8859-1?Q?Pag=E8s?= Cc: caml-list In-Reply-To: References: Content-Type: text/plain; charset="UTF-8" Date: Thu, 24 Mar 2011 14:26:56 +0100 Message-ID: <1300973216.8429.179.camel@thinkpad> Mime-Version: 1.0 X-Mailer: Evolution 2.28.1 X-Provags-ID: V02:K0:0eyaUEkP1SUXNonxDvp0Ym1ITuBx0nYu7NcXxcvnsRT IuVj6AYRzEyZGYwLSEju+3SOcScYFyi0gzOxRqHGY06uCRfVF9 q6tYZ8h39ZKV0Y4ViNHE/OAL3mabM1xvxygeRmYJSzTHaql38G 2EgCgDnc/ot5ki7+xPqRyNLSvkGmuvZfV2qLoMZRi+yg5KX7tf 372vE/1SkiDhG8WBHihvA== Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by walapai.inria.fr id p2ODR63D021074 Subject: Re: [Caml-list] Ocaml and cryptography 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 ------------------------------------------------------------