git.distorted.org.uk Git - u/mdw/catacomb/blob - README

   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: