Catacomb Catacomb is a cryptographic library. It covers quite a lot of the `standard' cryptographic primitives, although there's plenty of scope for improvement, implementing more block ciphers and hash functions for example. It contains a relatively extensive multiprecision arithmetic library suitable for implementing a wide range of public-key algorithms, although there's little direct support for any particular system. Objectives My objectives in writing Catacomb are: * Security. Of course, in most cases I'm implementing algorithms and protocols invented by other people, so my security is bounded by the security of the algorithms I'm implementing. The important thing is that (a) I document the weaknesses I'm aware of, and (b) I don't add more of my own. * Trust. I want people to be able to trust Catacomb. I'd like to be able to trust that the library (a) implements its various functions correctly, and (b) doesn't leak any other information, or allow malicious input to make the library misbehave in some other way. I have a fairly extensive set of test vectors for various components, and I add more regularly. * Breadth. I want to cover a lot of ground. I'm more interested in covering different sorts of cryptographic primitives and operations than in implementing standard protocols. I'm more likely to add support for elliptic curve-based public-key cryptography and threshold cryptography systems than supporting something like SSL or the PKCS suite of standards. * Portability. Almost all of Catacomb assumes nothing more than plain old ANSI C, and should therefore work on any conforming implementation of C. That's an awful lot of platforms. A few places make `reasonable' assumptions, usually in a fairly localized way, such as ASCII as a character set (in mptext.c). I've made sure I don't assume too much about the properties of integer arithmetic, for example. (Other exceptions include the key-file management code, which uses system-dependent locking primitives, and noise acquisition for the random-number generator.) Notice that efficiency isn't on the list. Catacomb isn't ever-so slow, but it's not particularly quick either. I've mostly used the right algorithms, and made occasional little performance tweaks, but Catacomb will never be the fastest cryptographic library if that means sacrificing other objectives. Licensing, and trust Catacomb is, as is explained at the top of every source file, free software; you may modify and/or redistribute it under the conditions described in the GNU Library General Public License. This is for two reasons, and the second one is more important than the first: * The first reason is that I think that software should be free. All of it. I think that you get better software that way, and that users are better served by free software than by being tied into restrictive licences by vendors of proprietary systems. * The second, and in this case overriding, reason is that I want to encourage trust in Catacomb. I can best do this by showing everyone what I've done and how it works, by being as open as I can about everything I do, and allowing the community at large to either poke holes in it (which I'm sure will happen, and I'll fix any problems as best I can), or fail in the attempt. I've chosen the GNU Library General Public License, rather than the more restrictive (but, to me, ideologically more appealing) plain GPL because I think that the world is better served by having trustworthy software than free software. Under the terms of the LGPL, a program linked against Catacomb must come with the Catacomb source code and be provided in such a form that it can be linked against a recompiled version of the library. Since the cryptographic components are provided in an open form, they can be scrutinized and trusted. In addition, modifications to the library can fix any problems found there, and to a large extend patch up weaknesses in the (proprietary) client program. Consider the case of a program which, among other functions, signs messages on behalf of its user using the Digital Signature Algorithm (DSA). One of the problems with the DSA is that it's the host for a particular nasty `subliminal channel' -- a hostile implementation can, undetectably, leak bits of your private key in each signed message. This works by carefully choosing a supposedly random parameter to the signature function. Once your adversary has acquired a few signed messages, which shouldn't be too hard, he can recover either your entire key, or enough that he can work out the rest in a reasonable amount of time, and then he can forge signatures. If his program can find any other keys, it can leak them too. A small modification to Catacomb can patch this weakness. In particular, the code /* --- Randomize the number @k@ --- * * * Replace `secret string' with some unguessable string * of your own choosing. */ { rmd160_ctx rmd; blowfish_cbcctx bf; octet hash[RMD160_HASHSZ]; static const char phrase[] = "Secret string"; rmd160_init(&rmd); rmd160_hash(&rmd, phrase, sizeof(phrase)); rmd160_hash(&rmd, k->v, MPWS(MP_LEN(k))); rmd160_done(&rmd, hash); blowfish_cbcinit(&bf, hash, sizeof(hash)); blowfish_cbcencrypt(&bf, k->v, k->v, MPWS(MP_LEN(k))); } at the top of the function `dsa_mksig' in `dsa-sign.c' will randomize the parameter @k@, closing the channel. (The code could be tidier -- in particular, it's not completely portable as it stands. A portable implementation would allocate a buffer of `mp_octets(k)' bytes, extract the value `k' to it using `mp_storel', encrypt the buffer, and load back using `mp_loadl'.) The `phrase' ensures that the output of the hash is unpredictable -- without it, at the cost of a squaring in computational effort, our adversary could compute a `k' such that not only `k' but also E_{H(k)}(k) both leak similar information, *and* also whether this transformation had been applied! Of course, the program might not actually use Catacomb for DSA signing. That on its own should be sufficient to cause suspicion -- requiring a cryptographic library and not using it is certainly strange. Documentation There's not a lot at the moment. Sorry. A manual is in progress. Eventually, I want to thoroughly document all functions and macros provided by Catacomb. The manual, which I've already started, will also include commentary on algorithms and techniques used by Catacomb which should help programmers understand and use the library more effectively. The manual is written using LaTeX, because it's quite mathematical in places and using text would probably just confuse matters. There probably won't be manual pages, because keeping everything up-to-date would be too hard. Until that's ready (and progress is fairly good at the moment), you'll have to rely on the comments in the header files. They're mostly good, but rely on a few concepts which haven't been properly explained. In particular, some parts of the multiprecision maths library are quite subtle and require a little mathematical background to understand fully. I've written a collection of README files which cover things in fairly broad brushstrokes, to try and set the header file comments in context. Future directions The following things will likely appear in later versions of Catacomb: * A manual. See above. * Better key management. Particular attention will be paid to management for public-key systems. This needs a lot of thought, however. * Arithmetic in finite fields other than the prime-order fields constructed by integer multiplication with a prime modulus. Interesting variants of Diffie-Hellman and other discrete-log-based systems occur in such fields. * Support for elliptic curve groups. Unfortunately, elliptic curve cryptography is fraught with patent issues. Other stuff not listed here will almost certainly be added. If people have suggestions then I'll consider them fairly, although they shouldn't conflict with my main objectives. -- [mdw] Local variables: mode: text End: