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: