759513d1 |
1 | Catacomb |
2 | |
3 | |
4 | Catacomb is a cryptographic library. It covers quite a lot of |
6540d069 |
5 | the `standard' cryptographic primitives, although there's plenty |
759513d1 |
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 secret-sharing |
37 | systems than supporting something like SSL or the PKCS suite |
38 | 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 | * Secret-sharing systems. Take a secret, and give n people a |
190 | `share' in it, so that any k <= n of them can recover the |
191 | secret, but fewer than k have no hope. |
192 | |
193 | * Arithmetic in finite fields other than the prime-order |
194 | fields constructed by integer multiplication with a prime |
195 | modulus. Interesting variants of Diffie-Hellman and other |
196 | discrete-log-based systems occur in such fields. |
197 | |
198 | * Support for elliptic curve groups. Unfortunately, elliptic |
199 | curve cryptography is fraught with patent issues. |
200 | |
201 | Other stuff not listed here will almost certainly be added. If |
202 | people have suggestions then I'll consider them fairly, although |
203 | they shouldn't conflict with my main objectives. |
204 | |
205 | -- |
206 | [mdw] |
207 | |
208 | \f |
209 | Local variables: |
210 | mode: text |
211 | End: |