math/mpreduce.h: Missing include files.
[u/mdw/catacomb] / README
1 Catacomb
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.
13 Objectives
15 My objectives in writing Catacomb are:
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.
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.
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.
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.)
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.
59 Licensing, and trust
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:
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.
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.
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.
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.
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.
108 A small modification to Catacomb can patch this weakness. In
109 particular, the code
111 /* --- Randomize the number @k@ --- *
112 *
113 * Replace `secret string' with some unguessable string
114 * of your own choosing.
115 */
117 {
118 rmd160_ctx rmd;
119 blowfish_cbcctx bf;
120 octet hash[RMD160_HASHSZ];
121 static const char phrase[] = "Secret string";
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 }
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'.)
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!
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.
152 Documentation
154 There's not a lot at the moment. Sorry. A manual is in
155 progress.
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.
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.
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.
178 Future directions
180 The following things will likely appear in later versions of
181 Catacomb:
183 * A manual. See above.
185 * Better key management. Particular attention will be paid to
186 management for public-key systems. This needs a lot of
187 thought, however.
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.
194 * Support for elliptic curve groups. Unfortunately, elliptic
195 curve cryptography is fraught with patent issues.
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.
201 -- [mdw]
203 \f
204 Local variables:
205 mode: text
206 End: