From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p2SJDIP6025009 for ; Mon, 28 Mar 2011 21:13:18 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AokCANrckE3U4xEKkWdsb2JhbACERaB+FAEBAQEJCwsHFAMiiGuqOpBfAoElg0t3BIgwiBs X-IronPort-AV: E=Sophos;i="4.63,257,1299452400"; d="scan'208";a="95246608" Received: from moutng.kundenserver.de ([212.227.17.10]) by mail2-smtp-roc.national.inria.fr with ESMTP; 28 Mar 2011 21:13:13 +0200 Received: from office1.lan.sumadev.de (dslb-094-219-208-030.pools.arcor-ip.net [94.219.208.30]) by mrelayeu.kundenserver.de (node=mrbap2) with ESMTP (Nemesis) id 0LfY1R-1Pbpl812FN-00otmX; Mon, 28 Mar 2011 21:13:12 +0200 Received: from [192.168.5.106] (dslb-094-219-208-030.pools.arcor-ip.net [94.219.208.30]) by office1.lan.sumadev.de (Postfix) with ESMTPA id E01935F702; Mon, 28 Mar 2011 21:13:10 +0200 (CEST) From: Gerd Stolpmann To: Jehan =?ISO-8859-1?Q?Pag=E8s?= Cc: caml-list In-Reply-To: References: <1300973216.8429.179.camel@thinkpad> Content-Type: text/plain; charset="UTF-8" Date: Mon, 28 Mar 2011 21:13:09 +0200 Message-ID: <1301339589.8429.564.camel@thinkpad> Mime-Version: 1.0 X-Mailer: Evolution 2.28.1 X-Provags-ID: V02:K0:N7IVAd9frQvzEgklP9/d0p9DrReXpdTfY2vb4tbXdKh PcgkCRgWTj1fxlG14eTN5DfIDXnackrW8J+z+vh6nGq+Gn7mxs q9ZrOHHQsPzp6T0VV7ddrPQF4bu7UcnELWdO9EdQCU+DFc4zHU 4vrlZ0wcnht5LmL4Y+KwMM2Qc4Yrq+kbaP/lPNCr72QOVq9/zK U0bG+a/1tOyUK8+EXRA5g== Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by walapai.inria.fr id p2SJDIP6025009 Subject: Re: [Caml-list] Ocaml and cryptography Am Samstag, den 26.03.2011, 15:44 +0900 schrieb Jehan Pagès: > Hi, > > 2011/3/24 Gerd Stolpmann : > > 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/ > > Nice. What will be the use? (if there is any upper level project > unless adding a feature for the library was the only goal right now?) The motivation is that I currently develop a map/reduce platform (Plasma - plasma.camlcity.org), and I was looking for a way to secure the communication channels between the various components. Plasma uses ONC-RPC, and hence a GSS-API mechanism fits best. I chose SCRAM because of its simplicity - the alternatives would have been Kerberos, or SPNEGO. However, these alternatives would have complicated the deployment of the platform. For GSS-API, SCRAM also supports encryption and integrity, so it is a full-featured solution. > > 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). > > Indeed. About these endless optimization... I had another response > (not made it to the list) with a link to uuidm code (also > implementation a native Ocaml SHA1). I saw it uses Char.unsafe_chr > instead of Char.chr. I didn't know this function, checked the source > of ocaml, saw it is indeed in the interface but hidden behind (**/**) > (so it did not appear in the doc). > > In my benchmark, I think it improves a little, but barely (enough so > that I am not fully sure if the improvement I see is the randomness of > consecutive benchmark tests). Still I keep it (as you say, endless > optimizations: that's mostly when you don't know what else to do) as > my code already makes sure that the code I pass to make a char is > valid. But I wonder if this hidden function is meant to disappear some > day... Is there some official status about this function? I don't think so, but such functions tend not to disappear from the Ocaml runtime (and I'm watching this for more than 10 years). > > 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 see. So that's a limitation of the Ocaml compiler or is it anyway > very difficult to have control on this kind of thing? It's a representation issue. If an int32 value cannot remain in a register, it needs to be "boxed", i.e. it is stored in a small memory block that is specially allocated for this purpose. Although Ocaml is very good at managing short-living memory blocks, there is a measurable slowdown. There is also the analysis complexity in the compiler which has to find out when it is possible to keep a value in a register. The compiler seems not to be written for optimizing small imperative loops as they occur in cryptography. I guess this is just a matter of how much effort you put into this. > > 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. > > Yes I was thinking for quite some time (I mean, some days as this code > is a few days old anyway) to try a int implementation when the > platform is 64 bits (masking over 4 bytes). I just decided to do so > yesterday. And it divides the benchmark time by 2. > > On the small 64 bits machine I have access (slow but slightly faster > than my netbook), my Int32 implementation was running my benchmark in > 0.25 seconds, and the int implementation of the same code otherwise in > 0.12 seconds! This is the price tag for these boxing operations. > So now I make some conditional implementation with > macros so that I use int on 64 bits platform and the generic Int32 on > 32 bits (or if I can't detect for sure I am on 64 bits). > > But the C implementation must have made some crazy optimization in > assembly for 64 bits platform because they run in around 0.008 > seconds! So they are like 15 times faster now from my Ocaml > implementation when it uses int! There are probably some more optimizations you can do. For example, CPUs have a feature called speculative execution - when a conditional jump is found, they cannot easily continue filling their execution pipeline, because they do not know whether the jump is done or not done. So what they do is that they guess (and they are good at guessing, but not perfect), and execute one of the outcomes of the condition speculatively (so that the effects can be undone). Although this is an interesting optimization in the CPU there is still some price to pay. The point is now that it is best to avoid such jumps at all, because the normal execution flow can then continue. If you write the assembly code directly, and know the runtime characteristics of the CPU well, one can greatly speedup the code by avoiding conditional jumps (e.g. by using conditional moves, or by bit shifting tricks). Compilers have a hard time generating such code. Gerd > Oh and to come back to macros (using pa_macro with camlp4o), why is > int validity checked by camlp4?! > I had some tests like this: > > IFNDEF ARCH_64 THEN > 0x8F1BBCDCl > ELSE > 0x8F1BBCDC > ENDIF > > Then when on a 32 bits machine, this stupid camlp4 ends in error > because 0x8F1BBCDC is over max_int! But that's why I do the IFDEF > test! Why does it ever bother checking this? I thought camlp4 was only > about syntax, not about code validation. If camlp4 was to only do its > job and pass the code to the compiler, this one would tell me if I > really made an int error (which was not the case). > Anyway that's not nice, I had to pass these int values as additional > macros instead which is not pretty in my opinion. > > > 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). > > I see. Still I am pretty happy of my code right now. It is not as good > as OpenSSL, but that's still pretty good when you think of it. I am > still doing 10.000 computations now in around 0.1 second on very weak > machines (even my notebook which does not read most videos well, I > have now optimized down to around 0.35 seconds). > > I think I'll stop here for my sha1 implementation (unless someone > points me to some really neat improvement I did not see). I am happy > with it. :-) > > Thanks all! > > Jehan > > > 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 > > ------------------------------------------------------------ > > > > > -- ------------------------------------------------------------ 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 ------------------------------------------------------------