| 1 | Catacomb |
| 2 | |
| 3 | |
| 4 | Catacomb is a cryptographic library. It covers quite a lot of |
| 5 | the `standard' cryptographic primitives, although there's plenty |
| 6 | of scope for improvement, implementing more block ciphers and |
| 7 | hash functions for example. It contains a relatively extensive |
| 8 | multiprecision arithmetic library suitable for implementing a |
| 9 | wide range of public-key algorithms, although there's little |
| 10 | direct support for any particular system. |
| 11 | |
| 12 | |
| 13 | Objectives |
| 14 | |
| 15 | My objectives in writing Catacomb are: |
| 16 | |
| 17 | * Security. Of course, in most cases I'm implementing |
| 18 | algorithms and protocols invented by other people, so my |
| 19 | security is bounded by the security of the algorithms I'm |
| 20 | implementing. The important thing is that (a) I document |
| 21 | the weaknesses I'm aware of, and (b) I don't add more of my |
| 22 | own. |
| 23 | |
| 24 | * Trust. I want people to be able to trust Catacomb. I'd |
| 25 | like to be able to trust that the library (a) implements its |
| 26 | various functions correctly, and (b) doesn't leak any other |
| 27 | information, or allow malicious input to make the library |
| 28 | misbehave in some other way. I have a fairly extensive set |
| 29 | of test vectors for various components, and I add more |
| 30 | regularly. |
| 31 | |
| 32 | * Breadth. I want to cover a lot of ground. I'm more |
| 33 | interested in covering different sorts of cryptographic |
| 34 | primitives and operations than in implementing standard |
| 35 | protocols. I'm more likely to add support for elliptic |
| 36 | curve-based public-key cryptography and threshold |
| 37 | cryptography systems than supporting something like SSL or |
| 38 | the PKCS suite of standards. |
| 39 | |
| 40 | * Portability. Almost all of Catacomb assumes nothing more |
| 41 | than plain old ANSI C, and should therefore work on any |
| 42 | conforming implementation of C. That's an awful lot of |
| 43 | platforms. A few places make `reasonable' assumptions, |
| 44 | usually in a fairly localized way, such as ASCII as a |
| 45 | character set (in mptext.c). I've made sure I don't assume |
| 46 | too much about the properties of integer arithmetic, for |
| 47 | example. (Other exceptions include the key-file management |
| 48 | code, which uses system-dependent locking primitives, and |
| 49 | noise acquisition for the random-number generator.) |
| 50 | |
| 51 | Notice that efficiency isn't on the list. Catacomb isn't |
| 52 | ever-so slow, but it's not particularly quick either. I've |
| 53 | mostly used the right algorithms, and made occasional little |
| 54 | performance tweaks, but Catacomb will never be the fastest |
| 55 | cryptographic library if that means sacrificing other |
| 56 | objectives. |
| 57 | |
| 58 | |
| 59 | Licensing, and trust |
| 60 | |
| 61 | Catacomb is, as is explained at the top of every source file, |
| 62 | free software; you may modify and/or redistribute it under the |
| 63 | conditions described in the GNU Library General Public License. |
| 64 | This is for two reasons, and the second one is more important |
| 65 | than the first: |
| 66 | |
| 67 | * The first reason is that I think that software should be |
| 68 | free. All of it. I think that you get better software that |
| 69 | way, and that users are better served by free software than |
| 70 | by being tied into restrictive licences by vendors of |
| 71 | proprietary systems. |
| 72 | |
| 73 | * The second, and in this case overriding, reason is that I |
| 74 | want to encourage trust in Catacomb. I can best do this by |
| 75 | showing everyone what I've done and how it works, by being |
| 76 | as open as I can about everything I do, and allowing the |
| 77 | community at large to either poke holes in it (which I'm |
| 78 | sure will happen, and I'll fix any problems as best I can), |
| 79 | or fail in the attempt. |
| 80 | |
| 81 | I've chosen the GNU Library General Public License, rather than |
| 82 | the more restrictive (but, to me, ideologically more appealing) |
| 83 | plain GPL because I think that the world is better served by |
| 84 | having trustworthy software than free software. Under the terms |
| 85 | of the LGPL, a program linked against Catacomb must come with |
| 86 | the Catacomb source code and be provided in such a form that it |
| 87 | can be linked against a recompiled version of the library. |
| 88 | Since the cryptographic components are provided in an open form, |
| 89 | they can be scrutinized and trusted. In addition, modifications |
| 90 | to the library can fix any problems found there, and to a large |
| 91 | extend patch up weaknesses in the (proprietary) client program. |
| 92 | |
| 93 | Consider the case of a program which, among other functions, |
| 94 | signs messages on behalf of its user using the Digital Signature |
| 95 | Algorithm (DSA). One of the problems with the DSA is that it's |
| 96 | the host for a particular nasty `subliminal channel' -- a |
| 97 | hostile implementation can, undetectably, leak bits of your |
| 98 | private key in each signed message. This works by carefully |
| 99 | choosing a supposedly random parameter to the signature |
| 100 | function. |
| 101 | |
| 102 | Once your adversary has acquired a few signed messages, which |
| 103 | shouldn't be too hard, he can recover either your entire key, or |
| 104 | enough that he can work out the rest in a reasonable amount of |
| 105 | time, and then he can forge signatures. If his program can find |
| 106 | any other keys, it can leak them too. |
| 107 | |
| 108 | A small modification to Catacomb can patch this weakness. In |
| 109 | particular, the code |
| 110 | |
| 111 | /* --- Randomize the number @k@ --- * |
| 112 | * |
| 113 | * Replace `secret string' with some unguessable string |
| 114 | * of your own choosing. |
| 115 | */ |
| 116 | |
| 117 | { |
| 118 | rmd160_ctx rmd; |
| 119 | blowfish_cbcctx bf; |
| 120 | octet hash[RMD160_HASHSZ]; |
| 121 | static const char phrase[] = "Secret string"; |
| 122 | |
| 123 | rmd160_init(&rmd); |
| 124 | rmd160_hash(&rmd, phrase, sizeof(phrase)); |
| 125 | rmd160_hash(&rmd, k->v, MPWS(MP_LEN(k))); |
| 126 | rmd160_done(&rmd, hash); |
| 127 | blowfish_cbcinit(&bf, hash, sizeof(hash)); |
| 128 | blowfish_cbcencrypt(&bf, k->v, k->v, MPWS(MP_LEN(k))); |
| 129 | } |
| 130 | |
| 131 | at the top of the function `dsa_mksig' in `dsa-sign.c' will |
| 132 | randomize the parameter @k@, closing the channel. (The code |
| 133 | could be tidier -- in particular, it's not completely portable |
| 134 | as it stands. A portable implementation would allocate a buffer |
| 135 | of `mp_octets(k)' bytes, extract the value `k' to it using |
| 136 | `mp_storel', encrypt the buffer, and load back using |
| 137 | `mp_loadl'.) |
| 138 | |
| 139 | The `phrase' ensures that the output of the hash is |
| 140 | unpredictable -- without it, at the cost of a squaring in |
| 141 | computational effort, our adversary could compute a `k' such |
| 142 | that not only `k' but also E_{H(k)}(k) both leak similar |
| 143 | information, *and* also whether this transformation had been |
| 144 | applied! |
| 145 | |
| 146 | Of course, the program might not actually use Catacomb for DSA |
| 147 | signing. That on its own should be sufficient to cause |
| 148 | suspicion -- requiring a cryptographic library and not using it |
| 149 | is certainly strange. |
| 150 | |
| 151 | |
| 152 | Documentation |
| 153 | |
| 154 | There's not a lot at the moment. Sorry. A manual is in |
| 155 | progress. |
| 156 | |
| 157 | Eventually, I want to thoroughly document all functions and |
| 158 | macros provided by Catacomb. The manual, which I've already |
| 159 | started, will also include commentary on algorithms and |
| 160 | techniques used by Catacomb which should help programmers |
| 161 | understand and use the library more effectively. The manual is |
| 162 | written using LaTeX, because it's quite mathematical in places |
| 163 | and using text would probably just confuse matters. There |
| 164 | probably won't be manual pages, because keeping everything |
| 165 | up-to-date would be too hard. |
| 166 | |
| 167 | Until that's ready (and progress is fairly good at the moment), |
| 168 | you'll have to rely on the comments in the header files. |
| 169 | They're mostly good, but rely on a few concepts which haven't |
| 170 | been properly explained. In particular, some parts of the |
| 171 | multiprecision maths library are quite subtle and require a |
| 172 | little mathematical background to understand fully. |
| 173 | |
| 174 | I've written a collection of README files which cover things in |
| 175 | fairly broad brushstrokes, to try and set the header file |
| 176 | comments in context. |
| 177 | |
| 178 | Future directions |
| 179 | |
| 180 | The following things will likely appear in later versions of |
| 181 | Catacomb: |
| 182 | |
| 183 | * A manual. See above. |
| 184 | |
| 185 | * Better key management. Particular attention will be paid to |
| 186 | management for public-key systems. This needs a lot of |
| 187 | thought, however. |
| 188 | |
| 189 | * Arithmetic in finite fields other than the prime-order |
| 190 | fields constructed by integer multiplication with a prime |
| 191 | modulus. Interesting variants of Diffie-Hellman and other |
| 192 | discrete-log-based systems occur in such fields. |
| 193 | |
| 194 | * Support for elliptic curve groups. Unfortunately, elliptic |
| 195 | curve cryptography is fraught with patent issues. |
| 196 | |
| 197 | Other stuff not listed here will almost certainly be added. If |
| 198 | people have suggestions then I'll consider them fairly, although |
| 199 | they shouldn't conflict with my main objectives. |
| 200 | |
| 201 | -- [mdw] |
| 202 | |
| 203 | \f |
| 204 | Local variables: |
| 205 | mode: text |
| 206 | End: |