The Cryptokit library OVERVIEW: The Cryptokit library for Objective Caml provides a variety of cryptographic primitives that can be used to implement cryptographic protocols in security-sensitive applications. The primitives provided include: - Symmetric-key ciphers: AES, DES, Triple-DES, ARCfour, in ECB, CBC, CFB and OFB modes. - Public-key cryptography: RSA encryption, Diffie-Hellman key agreement. - Hash functions and MACs: SHA-1, SHA-256, RIPEMD-160, MD5, and MACs based on AES and DES. - Random number generation. - Encodings and compression: base 64, hexadecimal, Zlib compression. Additional ciphers and hashes can easily be used in conjunction with the library. In particular, basic mechanisms such as chaining modes, output buffering, and padding are provided by generic classes that can easily be composed with user-provided ciphers. More generally, the library promotes a "Lego"-like style of constructing and composing transformations over character streams. This library is distributed under the conditions of the GNU Library General Public license version 2, with the special exception on linking described in file LICENSE. REQUIREMENTS: - Objective Caml 3.08 or up. - The Zlib C library, version 1.1.3 or up is recommended. If it is not installed on your system (look for libz.a or libz.so), get it from http://www.gzip.org/, or indicate in the Makefile that you do not have it. If you are running Linux or BSD, chances are that your distribution provides precompiled binaries for this library. - If the operating system does not provide the /dev/random device (for random number generation), consider installing the EGD entropy gathering daemon http://egd.sourceforge.net/ Without /dev/random nor EGD, this library cannot generate random data and RSA keys. The remainder of the library still works, though. INSTALLATION FOR UNIX (including Linux, MacOS X, and Cygwin): - Edit the variables at the beginning of the Makefile to reflect the location where Zlib is installed on your system. The defaults are OK for Linux. - Do "make all". - If the Objective Caml native-code compiler is available on your platform (look for the "ocamlopt" executable), do "make allopt". - (Optional) To test the library, do "make test". You must have either /dev/random or EGD available for the test to succeed. - Become super-user if necessary and do "make install". This installs the library in the standard Objective Caml library directory. INSTALLATION FOR MS WINDOWS: - Edit the variables at the beginning of Makefile.win32 to select either the MSVC or the Mingw port of OCaml. - Start a Cygwin shell and do "make -f Makefile.win all allopt". - (Optional) To test the library, do "make -f Makefile.win test". - Do "make -f Makefile.win install". This installs the library in the standard Objective Caml library directory. DOCUMENTATION: See the HTML documentation in doc/index.html, or the extensive comments in file cryptokit.mli Compilation options: none ocamlc linking options: unix.cma nums.cma cryptokit.cma ocamlopt linking options: unix.cmxa nums.cmxa cryptokit.cmxa WARNINGS AND DISCLAIMERS: Disclaimer 1: the author is not an expert in cryptography. While reasonable care has been taken to select good, widely-used implementations of the ciphers and hashes, and follow recommended practices found in reputable applied cryptography textbooks, you are advised to review thoroughly the implementation of this module before using it in a security-critical application. Disclaimer 2: some knowledge of cryptography is needed to use effectively this library. A recommended reading is the Handbook of Applied Cryptography http://www.cacr.math.uwaterloo.ca/hac/ Building secure applications out of cryptographic primitives also requires a general background in computer security. Disclaimer 3: in some countries, the use, distribution, import and/or export of cryptographic applications is restricted by law. The precise restrictions may depend on the strenght of the cryptography used (e.g. key size), but also on its purpose (e.g. confidentiality vs. authentication). It is up to the users of this library to comply with regulations applicable in their country. DESIGN NOTES AND REFERENCES: The library is organized around the concept of "transforms". A transform is an object that accepts strings, sub-strings, characters and bytes as input, transforms them, and buffers the output. While it is possible to enter all input, then fetch the output, lower memory requirements can be achieved by purging the output periodically during data input. The AES implementation is the public-domain optimized reference implementation by Daemen, Rijmen and Barreto. The DES implementation is based on Outerbridge's popular "d3des" implementation. This is not the fastest DES implementation available, but one of the cleanest. Outerbridge's code is marked as public domain. ARCfour (``alleged RC4'') is implemented from scratch, based on the algorithm described in Schneier's _Applied_Cryptography_ SHA-1 is also implemented from scratch, based on the algorithm described in the _Handbook_of_Applied_Cryptography_. It passes the FIPS test vectors. SHA-256 is implemented from scratch based on FIPS publication 180-2. It passes the FIPS test vectors. RIPEMD-160 is based on the reference implementation by A.Bosselaers. It passes the test vectors listed at http://www.esat.kuleuven.ac.be/~bosselae/ripemd160.html MD5 uses the public-domain implementation by Colin Plumb that is also used in the OCaml runtime system for module Digest. RSA encryption and decryption was implemented from scratch, using OCaml's bignum library for arbitrary-precision arithmetic. Modular exponentiation uses the trivial Russian peasant algorithm, because the bignum library does not support Montgomery modular multiplication. The Chinese remainder theorem is exploited when possible, though. Like all ciphers in this library, the RSA implementation is *not* protected against timing attacks. RSA key generation follows the algorithms used in PGP 2.6.3. Probabilistic primality testing is achieved by Fermat tests using the first 8 prime numbers. While not as good on paper as a Miller-Rabin probabilistic primality test, this seems good enough for PGP, so it should be good enough for us. The seeded PRNG is a combination of AES encryption in CBC mode and a lagged Fibonacci generator with long period. It appears to pass the Diehard statistical tests. Still, better to use the system RNG if high-quality random numbers are needed. PERFORMANCE: Some performance figures measured on a Pentium 4 2Ghz: AES 128: raw encryption 39 Mbyte/s; with CBC and buffering 15 Mbytes/s AES 192: raw encryption 34 Mbyte/s; with CBC and buffering 14 Mbytes/s AES 256: raw encryption 29 Mbyte/s; with CBC and buffering 13 Mbytes/s DES: raw encryption 19 Mbyte/s; with CBC and buffering 8 Mbytes/s 3DES: raw encryption 6.5 Mbyte/s; with CBC and buffering 4.5 Mbytes/s ARC4: raw encryption 57 Mbyte/s; with buffering 47 Mbytes/s SHA1: 31 Mbyte/s SHA256: 21 Mbyte/s RIPEMD160: 21 Mbyte/s MD5: 53 Mbyte/s AES MAC: 20 Mbyte/s RSA 1024: key generation 120 ms public-key operation (public exponent 65537) 0.70 ms private-key operation 29 ms private-key operation with CRT 9 ms