From 759513d1c2f79d94abe726682f43a28f363229cc Mon Sep 17 00:00:00 2001 From: mdw Date: Mon, 13 Dec 1999 15:35:40 +0000 Subject: [PATCH] Some documentation so users aren't completely lost. --- README | 211 +++++++++++++++++++++++++++++++++ README.cipher | 320 ++++++++++++++++++++++++++++++++++++++++++++++++++ README.hash | 134 +++++++++++++++++++++ README.mp | 368 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ README.random | 213 +++++++++++++++++++++++++++++++++ 5 files changed, 1246 insertions(+) create mode 100644 README create mode 100644 README.cipher create mode 100644 README.hash create mode 100644 README.mp create mode 100644 README.random diff --git a/README b/README new file mode 100644 index 0000000..ccc4987 --- /dev/null +++ b/README @@ -0,0 +1,211 @@ +Catacomb + + + Catacomb is a cryptographic library. It covers quite a lot of + the `standard' cryptgraphic primitives, although there's plenty + of scope for improvement, implementing more block ciphers and + hash functions for example. It contains a relatively extensive + multiprecision arithmetic library suitable for implementing a + wide range of public-key algorithms, although there's little + direct support for any particular system. + + +Objectives + + My objectives in writing Catacomb are: + + * Security. Of course, in most cases I'm implementing + algorithms and protocols invented by other people, so my + security is bounded by the security of the algorithms I'm + implementing. The important thing is that (a) I document + the weaknesses I'm aware of, and (b) I don't add more of my + own. + + * Trust. I want people to be able to trust Catacomb. I'd + like to be able to trust that the library (a) implements its + various functions correctly, and (b) doesn't leak any other + information, or allow malicious input to make the library + misbehave in some other way. I have a fairly extensive set + of test vectors for various components, and I add more + regularly. + + * Breadth. I want to cover a lot of ground. I'm more + interested in covering different sorts of cryptographic + primitives and operations than in implementing standard + protocols. I'm more likely to add support for elliptic + curve-based public-key cryptography and secret-sharing + systems than supporting something like SSL or the PKCS suite + of standards. + + * Portability. Almost all of Catacomb assumes nothing more + than plain old ANSI C, and should therefore work on any + conforming implementation of C. That's an awful lot of + platforms. A few places make `reasonable' assumptions, + usually in a fairly localized way, such as ASCII as a + character set (in mptext.c). I've made sure I don't assume + too much about the properties of integer arithmetic, for + example. (Other exceptions include the key-file management + code, which uses system-dependent locking primitives, and + noise acquisition for the random-number generator.) + + Notice that efficiency isn't on the list. Catacomb isn't + ever-so slow, but it's not particularly quick either. I've + mostly used the right algorithms, and made occasional little + performance tweaks, but Catacomb will never be the fastest + cryptographic library if that means sacrificing other + objectives. + + +Licensing, and trust + + Catacomb is, as is explained at the top of every source file, + free software; you may modify and/or redistribute it under the + conditions described in the GNU Library General Public License. + This is for two reasons, and the second one is more important + than the first: + + * The first reason is that I think that software should be + free. All of it. I think that you get better software that + way, and that users are better served by free software than + by being tied into restrictive licences by vendors of + proprietary systems. + + * The second, and in this case overriding, reason is that I + want to encourage trust in Catacomb. I can best do this by + showing everyone what I've done and how it works, by being + as open as I can about everything I do, and allowing the + community at large to either poke holes in it (which I'm + sure will happen, and I'll fix any problems as best I can), + or fail in the attempt. + + I've chosen the GNU Library General Public License, rather than + the more restrictive (but, to me, ideologically more appealing) + plain GPL because I think that the world is better served by + having trustworthy software than free software. Under the terms + of the LGPL, a program linked against Catacomb must come with + the Catacomb source code and be provided in such a form that it + can be linked against a recompiled version of the library. + Since the cryptographic components are provided in an open form, + they can be scrutinized and trusted. In addition, modifications + to the library can fix any problems found there, and to a large + extend patch up weaknesses in the (proprietary) client program. + + Consider the case of a program which, among other functions, + signs messages on behalf of its user using the Digital Signature + Algorithm (DSA). One of the problems with the DSA is that it's + the host for a particular nasty `subliminal channel' -- a + hostile implementation can, undetectably, leak bits of your + private key in each signed message. This works by carefully + choosing a supposedly random parameter to the signature + function. + + Once your adversary has acquired a few signed messages, which + shouldn't be too hard, he can recover either your entire key, or + enough that he can work out the rest in a reasonable amount of + time, and then he can forge signatures. If his program can find + any other keys, it can leak them too. + + A small modification to Catacomb can patch this weakness. In + particular, the code + + /* --- Randomize the number @k@ --- * + * + * Replace `secret string' with some unguessable string + * of your own choosing. + */ + + { + rmd160_ctx rmd; + blowfish_cbcctx bf; + octet hash[RMD160_HASHSZ]; + static const char phrase[] = "Secret string"; + + rmd160_init(&rmd); + rmd160_hash(&rmd, phrase, sizeof(phrase)); + rmd160_hash(&rmd, k->v, MPWS(MP_LEN(k))); + rmd160_done(&rmd, hash); + blowfish_cbcinit(&bf, hash, sizeof(hash)); + blowfish_cbcencrypt(&bf, k->v, k->v, MPWS(MP_LEN(k))); + } + + at the top of the function `dsa_mksig' in `dsa-sign.c' will + randomize the parameter @k@, closing the channel. (The code + could be tidier -- in particular, it's not completely portable + as it stands. A portable implementation would allocate a buffer + of `mp_octets(k)' bytes, extract the value `k' to it using + `mp_storel', encrypt the buffer, and load back using + `mp_loadl'.) + + The `phrase' ensures that the output of the hash is + unpredictable -- without it, at the cost of a squaring in + computational effort, our adversary could compute a `k' such + that not only `k' but also E_{H(k)}(k) both leak similar + information, *and* also whether this transformation had been + applied! + + Of course, the program might not actually use Catacomb for DSA + signing. That on its own should be sufficient to cause + suspicion -- requiring a cryptographic library and not using it + is certainly strange. + + +Documentation + + There's not a lot at the moment. Sorry. A manual is in + progress. + + Eventually, I want to thoroughly document all functions and + macros provided by Catacomb. The manual, which I've already + started, will also include commentary on algorithms and + techniques used by Catacomb which should help programmers + understand and use the library more effectively. The manual is + written using LaTeX, because it's quite mathematical in places + and using text would probably just confuse matters. There + probably won't be manual pages, because keeping everything + up-to-date would be too hard. + + Until that's ready (and progress is fairly good at the moment), + you'll have to rely on the comments in the header files. + They're mostly good, but rely on a few concepts which haven't + been properly explained. In particular, some parts of the + multiprecision maths library are quite subtle and require a + little mathematical background to understand fully. + + I've written a collection of README files which cover things in + fairly broad brushstrokes, to try and set the header file + comments in context. + +Future directions + + The following things will likely appear in later versions of + Catacomb: + + * A manual. See above. + + * Better key management. Particular attention will be paid to + management for public-key systems. This needs a lot of + thought, however. + + * Secret-sharing systems. Take a secret, and give n people a + `share' in it, so that any k <= n of them can recover the + secret, but fewer than k have no hope. + + * Arithmetic in finite fields other than the prime-order + fields constructed by integer multiplication with a prime + modulus. Interesting variants of Diffie-Hellman and other + discrete-log-based systems occur in such fields. + + * Support for elliptic curve groups. Unfortunately, elliptic + curve cryptography is fraught with patent issues. + + Other stuff not listed here will almost certainly be added. If + people have suggestions then I'll consider them fairly, although + they shouldn't conflict with my main objectives. + +-- +[mdw] + + +Local variables: +mode: text +End: diff --git a/README.cipher b/README.cipher new file mode 100644 index 0000000..f9d08b9 --- /dev/null +++ b/README.cipher @@ -0,0 +1,320 @@ +Symmetric ciphers + + + Catacomb provides a number of symmetric ciphers, together with a + generic cipher interface. More ciphers may be added later. + + +Block cipher interface + + There are a number of block ciphers implemented, all with + extremely similar interfaces. However, block ciphers aren't + actually at all pleasant to use directly. They're really + intended to be used only by higher-level `modes'. + + Anyway, I'll take Bruce Schneier's Blowfish as an example. + + Before doing any encryption or decryption, you need to + initialize a `context'. The context data is stored in an object + of type `blowfish_ctx'. You initialize the context by calling + `blowfish_init' with the address of the context, the address of + some key data, and the length of the key. + + Data is encrypted using `blowfish_eblk' and decrypted by + `blowfish_dblk'. Both functions are given data as an array of + `uint32' words. (Since Blowfish uses 64-bit blocks, you give it + arrays of two words.) + + A number of constants are defined to describe further properties + of the cipher: + + BLOWFISH_KEYSZ Is zero, to indicate that Blowfish doesn't care + much about the size of key you give it. + + BLOWFISH_BLKSZ Is 8, because Blowfish works on 64-bit blocks, + which are therefore 8 bytes wide. + + BLOWFISH_CLASS Is the triple (N, B, 64). This is explained + below. + + The BLOWFISH_CLASS macro contains information useful to other + macros, rather than to direct users of the interface. The three + components are: + + The `type' Simply N if specific macros for handling blocks + of the appropriate width have been written, or X + if the macros should use a loop instead. + + The `endianness' + Either `B' for big-endian, or L for little- + endian. + + The `width' The cipher's block size in bits. + + This simple interface is thoroughly inconvenient for general + use, although it makes writing block ciphers very easy. + + + The peculiarities of the various ciphers are described below. + + Blowfish Fairly standard, really. Accepts arbitrary- + sized keys up to 448 bits. (The original + definition only specified keys with a multiple + of 32 bits -- the extension I use is due, I + think, to Eric Young.) Blowfish is fast and + looks very secure. + + IDEA Requires a 128-bit key. Not very fast. No + known attacks on the full cipher. Used in + PGP2. Patented! + + DES Good old reliable. Been around for donkey's + years and still going. Single-DES (implemented + here) has a small key, but apart from that is + looking remarkably robust. Uses a 56-bit key + which may be either 8 bytes with (ignored) + parity bits in the bottom bit of each byte, or 7 + bytes with no parity. + + DES3 Two- or three-key triple DES. Slow, but strong + and almost universally trusted. Accepts 56-, + 112- and 168-bit keys. (56 bits gives you + single DES at a third of the speed.) Again, + parity may be included or not, so the full range + of key sizes in bytes is: 7, 8, 14, 16, 21 or + 24. + + RC5 Arbitrary-sized key. Designed by Ron Rivest. + Not completely convincing in security. About as + fast as Blowfish, but with a quicker key + schedule. Patented, I think. + + +Block cipher modes + + There are four block cipher modes defined, all of which create a + useful cipher from block cipher. Modes are implemented + separately from ciphers, so it's easy to add either, and easy to + apply modes to ciphers. + + A few definitions will be helpful to explain the modes. Let E + denote the encryption function, P be the current plaintext + block, C be the current ciphertext, and C' be the previous + ciphertext block. Let `XOR' denote the bitwise exclusive or + operation. + + Then the modes Electronic Code Book (ECB), Cipher Block Chaining + (CBC) and Ciphertext Feedback (CFB) are defined as: + + ECB C = E(P) + CBC C = E(P XOR C') + CFB C = P XOR E(C') + + Finally, Output Feedback is defined like this: let O be the + current output, and O' be the previous output. Then + + OFB O = E(O'), C = P XOR O + + The `previous ciphertext' or `previous output' for the first + block is provided by an `initialization vector' or IV. + + The above definitions imply that only data which comes in + multiples of the block size can be encrypted. Normally this is + the case. However, Catacomb implements all four modes so that + almost arbitrary sizes of plaintext can be encrypted (without + having to pad out the ciphertext). The details are complicated: + read the source, or look up `ciphertext stealing' in your copy + of Schneier's `Applied Cryptography'. + + ECB must have *at least* one entire block to work with, but + apart from that can cope with odd-size inputs. Both ECB and CBC + insert `boundaries' when you encrypt an odd-size input -- you + must decrypt in exactly the same-size chunks as you encrypted, + otherwise you'll only get rubbish out. + + CFB and OFB have no restrictions on input sizes, and do not + normally insert boundaries, although it's possible to explicitly + request one. + + Be especially careful with OFB mode. Since it generates an + output stream independent of the plaintext, and then XORs the + two, if you ever reuse the same key and IV pair, both encrypted + messages are compromised. (Take the two ciphertexts, and XOR + them together -- then the OFB stream cancels and you have the + plaintexts XORed. This is fairly trivial to unravel.) + + OFB mode makes a good random byte generator. See README.random + for details about random number generators in Catacomb. + + + The modes all have similar interfaces. CFB is probably the best + example, although CBC is more useful in practice. I'll take + Blowfish as my example cipher again. + + You need to initialize a context block. For Blowfish in CFB + mode, this is called `blowfish_cfbctx'. You initialize it by + passing the context address, a key, the key length, and pointer + to an IV (which must be BLOWFISH_BLKSZ in length) to + blowfish_cfbinit. If you pass a null pointer instead of an IV, + a zero IV is used. This is usually OK for CBC, but bad for OFB + or CFB unless you make sure that the key itself is only used + once. + + Data is encrypted using blowfish_cfbencrypt and + blowfish_cfbdecrypt -- both are given: the address of the + context, a pointer to the source data, a pointer to the + destination (which may overlap the source) and the size of the + data to encrypt or decrypt. + + The IV may be changed by calling blowfish_cfbsetiv. The current + IV (really meaning the previous ciphertext) can be obtained with + blowfish_cfbgetiv. The key may be changed without altering the + IV using blowfish_cfbsetkey. A boundary may be inserted in the + ciphertext or plaintext using blowfish_cfbbdry. + + ECB doesn't use IVs, so there aren't ecbsetiv or ecbgetiv + calls. You can't insert boundaries in ECB or CBC mode. + + OFB encryption and decryption are the same, so there's no + separate ofbdecrypt call. However, ofbencrypt has some useful + tricks: + + * If the destination pointer is null, it just churns the output + round for a while, without emitting any data. + + * If the source pointer is null, it simply spits out the + output blocks from the feedback process. This is equivalent + to giving an input full of zero bytes. + + +Implementing new modes: nasty macros + + Block cipher modes are implemented as macros which define the + appropriate functions. They're given the prefixes (upper- and + lowercase) and expected to get on with life. + + Data can be shunted around fairly efficiently using the BLKC + macros. These are fairly ugly, so don't try to work out how + they work. + + In the following notation, `b' denotes a pointer to bytes, and + `w' and `wx' denote pointers to words. `PRE' is the uppercase + cipher prefix. I'll abuse this notation a little and use the + names to refer to the entire arrays, since their lengths are + known to be PRE_BLKSZ (in bytes) or PRE_BLKSZ / 4 (in words) + long. + + BLKC_STORE(PRE, b, w) Set b = w + BLKC_XSTORE(PRE, b, w, wx) Set b = w XOR wx + BLKC_LOAD(PRE, w, b) Set w = b + BLKC_XLOAD(PRE, w, b) Set w = w XOR b + BLKC_MOVE(PRE, w, wx) Set w = wx + BLKC_XMOVE(PRE, w, wx) Set w = w XOR wx + + These should be enough for most purposes. More can be added, + but involves a strong stomach and an ability to do things with C + macros which most people wouldn't like to think about over + dinner. + + +Other ciphers + + There's only one stream cipher implemented at the moment, and + that's RC4. It was designed by Ron Rivest. It's the fastest + cipher in Catacomb. It looks fairly strong (although see the + note about churning the context after keying below). And also + note that it works in output feedback -- you just XOR the output + from RC4 with the plaintext. Never reuse an RC4 key! + + RC4 includes an OFB-like interface which should be familiar. It + also includes a pair of strange macros RC4_OPEN and RC4_BYTE. + These are used to actually get bytes out of the RC4 generator. + + RC4_OPEN is really a new syntactic form. If `r' is a pointer to + an RC4 context, then + + RC4_OPEN(r, ); + + executes within the opened RC4 context. The + significance of this is that the expression RC4_BYTE(x) extracts + the next byte from the innermost open context, and stores it in + x. The standard RC4 encrypt function is written in terms of + RC4_OPEN and RC4_BYTE. + + RC4 makes an excellent and fast random-byte generator. + + RSA Data Security Inc. claim that RC4 is a trade secret of + theirs. It doesn't look very secret to me. + + +Generic cipher interfaces + + It can be convenient to implement routines where the cipher to + use is a parameter. Hence, Catacomb provides a generic + interface to (symmetric) ciphers. The generic interface is + defined in . + + The basic type in the interface is `gcipher', which represents + an `instance' of a cipher. You don't see lone cipher objects, + only pointers to them, so really everything's in terms of + `gcipher *'. + + A `gcipher' is a structured type with one member, called `ops' + which points to a collection of functions and other useful + information. If `c' is a cipher... + + c->ops->b->name Name of the cipher being used + + c->ops->b->keysz Key size in bytes (or zero for + `don't care') + + c->ops->b->blksz Block size in bytes (or zero for + `not a block cipher') + + c->ops->encrypt(c, s, t, sz) Encrypt the sz bytes stored in + s, and store the ciphertext at + t. + + c->ops->decrypt(c, s, t, sz) Like encrypt, only it decrypts. + + c->ops->destroy(c) Destroys the cipher object `r'. + + c->ops->setiv(c, iv) Sets the IV to be `iv' -- must + be blksz bytes long. + + c->ops->bdry(c) Inserts a boundary. + + Note that `setiv' and `bdry' aren't implemented by all ciphers + so these may be null pointers. It's best to check first. + + Generic cipher instances are created from `generic cipher + classes' (type `gccipher' -- note the extra `c'). This contains + two members: + + b The `class base' -- this is the object pointed + to by `c->ops->b', and contains `name', `keysz' + and `blksz' members. + + init The constructor. You give it a pointer to some + key data and the key size, and it returns a + generic cipher instance. + + Note that new generic ciphers always have zero IVs (if they + understand the concept), so you may need to call setiv if you + want to reuse keys. + + Always remember to destroy gcipher instances when you're + finished with them. + + The generic cipher class for CBC-mode Blowfish is called + `blowfish_cbc' -- the others are named similarly. The RC4 + generic cipher class is called simply `rc4'. + + +-- +[mdw] + + +Local variables: +mode: text +End: diff --git a/README.hash b/README.hash new file mode 100644 index 0000000..6b0988f --- /dev/null +++ b/README.hash @@ -0,0 +1,134 @@ +Cryptographic hash functions + + + Hash functions are very useful cryptographic primitives. + Catacomb provides a few of the best-known cryptographic hashes. + + +Hash function interface + + Hash functions share a regular interface. I'll take Ron + Rivest's MD5 as an example. + + Using a hash function is a three-stage process. You initialize + a context, you hash some data, and you get the result out of the + end. The data to be hashed need not be contiguous, and you + don't have to have it all before you start. Hash function + contexts don't use up lots of memory. + + An MD5 context is called `md5_ctx'. You initialize it with + `md5_init'. You hash a block of data using `md5_hash' giving it + the context, the pointer to the data and its length. Finally, + you extract the data using `md5_done', giving it the address of + a buffer of MD5_HASHSZ bytes for it to write the result. + + There are some other standard operations as well, but they're + not often used: see the header files for details. + + The hash functions supported are: + + MD4 By Ron Rivest -- returns a 128-bit hash. MD4 is + not collision-resistant, and may not even be + second-preimage-resistant. Don't depend on its + security. On the other hand, MD4 is *very* + fast. + + MD5 Also by Rivest, also returns a 128-bit hash. + MD5 is slower than MD4, and more conservative, + but there are still grave doubts about its + security. + + SHA1 Designed by the US National Security Agency. + Returns a 160-bit hash. Slower than MD5. Looks + strong. Fixes a problem in the earlier SHA. + + RIPEMD-160 Designed by the people who broke MD4 and MD5. + Returns a 160-bit hash. Slower than SHA1. My + personal preference. + + +HMAC interface + + It's possible to construct a `keyed hash' or `message + authentication code' from a hash function. Most methods for + doing this are insecure. HMAC is a good method, with rigorously + proven security properties. + + Each hash function above has an HMAC mode defined for it. This + works much the same way as block cipher modes. + + Using HMAC is a two-step process. First, you initialize a MAC + key block `mackey' to contain the key you'll use, and then you + initialize MAC contexts `macctx' which to actually hash the + data. Hashing works just the same as the basic hash function, + except that you use `macinit', `machash' and `macdone' functions + rather than the plain `init', `hash' and `done'. + + +Generic interfaces + + Generic interfaces to hash functions and MACs are provided. See + README.cipher to get an idea for how a similar generic interface + works -- I'll only explain the differences here. + + The generic hash object, `ghash' contains an `ops' member + referring to: + + h->ops->b->name The name of the hash function. + + h->ops->b->hashsz The output size of the hash function. + + h->ops->hash(h, p, sz) Hash sz bytes of data starting at + address p. + + h->ops->done(h, b) Stop hashing, write the result to buffer + b with size `hashsz'. + + h->ops->destroy(h) Destroy the generic hash object. + + The generic hash class, `gchash', contains a base which has the + same members as `ops->b' above, and an `init' function which + takes no arguments and returns a pointer to a `ghash'. + + There's a generic MAC interface too. A MAC class, `gcmac' + contains a hash base (exactly the same, but with a different + name), and a function `key' which takes a pointer to some key + data and the key size, and returns a pointer to a `generic mac' + object, `gmac'. + + A `gmac' contains an `ops' member: + + m->ops->b->name, m->ops->b->hashsz + As above. + + m->ops->init(m) Returns a generic *hash* object to + actually compute a MAC over some data. + + m->ops->destroy(m) Destroys the generic MAC block. + + + That was quite complex. Here's an example of using a generic + MAC. + + void compute_mac(gcmac *gcm, const void *k, size_t ksz, + const void *p, size_t sz, + void *hash) + { + gmac *m = gcm->init(k, ksz); + ghash *h = m->ops->init(m); + m->ops->destroy(m); + h->ops->hash(h, p, sz); + h->ops->done(h, hash); + h->ops->destroy(h); + } + + Note that the hash doesn't depend on the MAC object continuing + to exist. + +-- +[mdw] + + +Local variables: +mode: text +End: diff --git a/README.mp b/README.mp new file mode 100644 index 0000000..a7909f2 --- /dev/null +++ b/README.mp @@ -0,0 +1,368 @@ +Multiprecision maths library + + + Catacomb comes with a fairly reasonable multiprecision maths + library. It's not stunningly fast, and doesn't do everything, + but it seems good for the sorts of things needed in + cryptographic algorithms (which, for example, GMP isn't[1]). + + There are basically three layers to the system: + + * The low-level `mpx' layer, which implements some basic + arithmetic but is fairly unpleasant to actually use. + + * A high-level `mp' layer, which provides a useful `mp' + multiprecision type and implements useful arithmetic on + them. + + * Everything else. A collection of miscellaneous routines for + performing particular operations efficiently or simply. + + [1] In particular, GMP is truly rotten at converting numbers + into well-defined binary formats. It has its own format, + but it's not defined in the manual, has changed once before, + probably doesn't conform to any standards in the + cryptographic community, and can only be written to or read + from a file stream, so you can't use it in memory (for + example to encrypt it). Basically, it's a right pain. + + +The low-level interface + + The low level is described in `mpx.h'. It includes everything + else it needs. + + An integer is represented in an array of words. Each word has + type `mpw' (multi precision word). The least significant word + comes first. An array is described by its `base' -- the address + of the first element -- and its `limit' -- the address *just + after* the last element. Thus, the length of the array is + `limit - base'. This representation is particularly convenient + for many things. An old version used base and length, which was + a nuisance. + + The largest value which can be represented in a word is + MPW_MAX. The number of bits used in the representation of a + word is MPW_BITS. Actually, you might be able to use more bits + and store larger numbers, but everything will go wrong if you + try. + + The macro call MPW(x) returns the low MPW_BITS bits of x. It's + very useful in low-level arithmetic. + + The call MPWS(n) tells you the `sizeof' an array of n words. + It's also very useful. Try not to get MPW and MPWS confused + because they mean very different things. + + The actual low-level macros and functions are documented + relatively well. They are given source and destination arrays + for things to be read and written to. Usually the sources + mustn't overlap the destinations, and destinations certainly + mustn't overlap other destinations; sometimes this restriction + is lifted, where it would be both convenient and easy to do so. + Sources can overlap each other without problems, because they're + not written to. + + The difficult parts are the Karatsuba functions. Karatsuba + and Ofman discovered a neat recursive way to multiply large + numbers. It requires quite a bit of workspace, and adds some + overhead, but has lower asymptotic complexity than the standard + multiply algorithm. Usually, Karatsuba functions get used + automatically by the rest of the library when appropriate and + you don't have to care. + + +The high-level interface + + The high-level invents a type, `mp'. It's a structured type, + with the following members: + + mpw *v, *vl Base and limit of the word array. + size_t sz Number of words actually allocated to the array. + unsigned f Various flags. + unsigned ref Number of references to the integer. + + The flags are interesting. Here's what they mean: + + MP_NEG The number is negative + MP_BURN Burn the number after using it + MP_CONST The number mustn't be modified or freed + MP_UNDEF The number contains no interesting value + MP_DESTROYED The number has been freed once already + + The last one is handy for catching bugs. MP_NEG is obvious -- + Catacomb uses a signed-magnitude representation because things + are usually easier that way. MP_CONST is set on various + constants provided for general convenience so they don't get + destroyed by accident. MP_UNDEF is used to avoid copying + useless data. + + MP_BURN marks a `secret' number. Secret numbers are overwritten + with zeroes (`burnt') when they're freed. Secrecy is a viral + concept: anything calculated from a secret number is also + secret, so they get burnt too. + + Most of the time, you refer to numbers by their addresses. Lots + of `mp *' pointers get used. You hardly ever see a real `mp', + just pointers to them. + + There are a collection of utility functions for keeping the + system running -- for creating new numbers without interesting + values, for throwing old ones away, for extending the amount of + memory they use, and so on. + + Throwing numbers away is simple. You pass the pointer to the + number to `mp_drop'. If someone else still has a reference to + the number, it stays where it is, but remembers that you're not + interested in it any more. If nobody's interested then the + number is disposed of. + + You can add a reference using MP_COPY. It returns the new + reference. The new reference is the same as the old one, but + it's a useful fiction to pretend that it's different. + + Real arithmetic happens in a fairly uniform way. There's an + important point to make about `destinations', though. Just + about all of the arithmetic functions take `destination' + arguments (one for each result), with the idea that, at least + conceptually, they store the results there. What actually + happens is that a reference is lost to whatever the destination + used to refer to, and a reference to the new result is gained. + The address might be different, and then again it might not. + Destinations acn be the same as sources -- that works fine. + Finally, there's the magic value `MP_NEW'. MP_NEW is a special + constant which, as a destination, means `create a new place and + put the answer there'. + + The idea is that, sometimes it helps that memory is already + allocated for a destination, so it doesn't have to be obtained + specially, and, even more often, you want to throw away old + intermediate results while you're calculating new ones. + + Here are some examples of how to do it right: + + x = mp_add(MP_NEW, y, z); + Assumes x didn't have a useful value before. + Afterwards it refers to the sum of y and z. y and z + themselves are unchanged. + + y = mp_add(y, y, z); + Add z to y. Now y is the sum of z and the old y. z is + unchanged. + + q = MP_NEW; + mp_div(&q, &x, x, y); + Sets q (a new value) equal to x / y, and puts the + remainder back in x. y is unchanged. + + z = mp_sub(z, y, z); + Subtract z from y, putting the result back in z. y is + unchanged. + + x = mp_mul(y, y, z); + Multiply y by z, putting the result in x, but making y + no longer useful. + + Here's some examples of how to do it wrong: + + mp_mul(y, y, z); + mp_mul might choose somewhere other than b's storage to + write its result. (In fact, the current version + certainly will.) So y is trashed because there are no + references to it any more, and the result of the + multiplication is lost. + + x = mp_mul(y, y, z); + x = mp_add(x, x, y); + Whoops. We stored the result in x, but y still got + trashed and might contain anything. Adding it to x is a + bad move. + + It's not hard once you get the hang of it, although it might + feel a bit weird to start with. + + +Modular multiplication and exponentiation + + Lots of public-key crypto uses modular multiplication and + exponentation operations. Doing them efficiently is very + important. Multiplication on its own is easy, and Catacomb's + multiplication algorithms are fairly good (though not up with + the very best). Doing the modular reduction afterwards is the + tricky bit. + + There are three approaches to modular reduction in Catacomb. + All of them have their good and bad points. + + 1. Use mp_div + + For a one-off calculation, this is a good idea. Division is a + slow operation -- that's a shame, but life's like that. But + when you're doing a one-shot operation, that's the best you can + manage. + + 2. Use Barrett reduction + + Barrett reduction is a system whereby you do a little + precomputation up-front (one division, in fact) and are then + able to perform modular reductions without resorting to + expensive division operations. To use it, you initialize a + `context' with the modulus, reduce some numbers, and then + destroy the context when you've finished. + + Conceptually, Barrett reduction is simple. You give it x and it + gives you back x mod m. The mathematics behind it is fairly + clever, though -- the real manual has a page of explanation for + how it works. + + Barrett reduction works on any positive modulus m. It will do a + modular reduction on any integer x which is at most twice as + long as m (in words). x can be larger than m^2, but it mustn't + be more than twice as long. + + 3. Use Montgomery reduction + + Montgomery reduction is a little more clever. It does a little + more work up-front than Barrett reduction, and understanding the + benefits is a little harder. However, it's actually slightly + more efficient for general use. There's also a disadvantage + that Montgomery reduction only works when the modulus is *odd*. + It all goes horribly wrong with an even modulus. Don't try it. + + I'm not going to explain how Montgomery reduction actually + works. But I am going to explain how to use it. + + The precomputation for Montgomery reduction, performed when you + initialize a context, computes a value called R, and also R^2 + (both mod m). (It also computes some other stuff, but that's + not important for this discussion.) Note that R is dependent on + the modulus m. + + A Montgomery reduction takes a number x, which should be less + than m^2 (it can actually be a bit larger) and computes the + value x R^{-1} mod m. That doesn't sound very useful, does it? + + Things start looking more hopeful when you multiply your inputs + by R. (There's a clever way of doing that: see below.) To + compute xy mod m, you can first calculate xR and yR, multiply + them together to get xyR^2, and do a Montgomery reduction to get + xyR^2 R^{-1} mod m. Then the R^{-1} cancels one of the Rs and + you end up with xyR mod m. Essentially, you do your entire + calculation with an extra factor of R all the way through it. + + Removing the factor of R at the end is easy. You just run the + Montgomery reduction algorithm again -- the R^{-1} cancels the R + and the answer pops out the end. Getting the factor of R in the + first place is easy -- you multiply by R^2 and do a reduction. + + The multiply-and-reduce thing is so common that there's a + dedicated function which does them both in one go. + + Here's a simple example of multiplying two numbers mod m: + + mpmont mm; + mp *ar, *br, *p; + mpmont_create(&mm, m); + ar = mp_mul(MP_NEW, a, m.r2); /* aR mod m */ + br = mp_mul(MP_NEW, b, m.r2); /* bR mod m */ + p = mpmont_mul(&mm, MP_NEW, ar, br); /* abR mod m */ + p = mpmont_reduce(&mm, p, p); /* ab mod m */ + mpmont_destroy(&mm); + mp_drop(ar); + mp_drop(br); + + Actually, it's not a very clever example. Here's a better way, + for such a simple calculation: + + mpmont mm; + mp *p; + mpmont_create(&mm, m); + p = mpmont_mul(&mm, MP_NEW, a, b); /* abR^{-1} mod m */ + p = mpmont_mul(&mm, p, p, mm.r2); /* ab mod m */ + mpmont_destroy(&mm); + + Of course, for a single multiply-and-reduce, you're better off + just using + + mp *p = mp_mul(MP_NEW, a, b); + mp_div(0, &p, p, m); + + the traditional division method. + + Both Barrett and Montgomery reduction methods have modular + exponentiation functions. If m is a message, n is an RSA + modulus, and e is the public exponent, I can do an RSA + encryption simply by doing + + mpmont mm; + mpmont_create(&mm, n); /* RSA modulus is odd */ + c = mpmont_exp(&mm, MP_NEW, m, e); + mpmont_destroy(&mm); + + (Yes, it's well worth creating a Montgomery context for a + full-blown exponentiation, unless someone's deliberately gone + out of their way to make it easy for you by choosing a very + small public exponent.) + + +Finding prime numbers + + Prime numbers are important too. Finding them is not ever-so + easy. + + Catacomb has two useful facilities. There's a fast sequential- + search filtering system called `pgen', and a good (but + probabilistic) primality tester which implements the Rabin- + Miller test. + + The idea is that you initialize a pgen object with a starting + place. It spends a short time initializing itself, and then + tells you whether the number you gave it is (a) definitely + composite, (b) definitely prime (only for small numbers), or (c) + it doesn't know. The advantage of the pgen system is that it's + good at stepping regularly. You can advance it by 2 or 4 very + rapidly, and it will give you the same sort of answer for the + next number. + + When you find a number which pgen says it doesn't know about, + you must test it more thoroughly. This is time-consuming, but + pgen has weeded out many no-hopers so it's not so bad. + + The Rabin-Miller test takes a number to test, and stores it in a + context. You then give it some random numbers, and it gives you + results. When you've finished, you destroy the context. + + The Rabin-Miller test has two possible responses: (a) definitely + not prime, and (b) probably prime. Answer (a) is certain. + Answer (b) you may get with a composite number at most one time + in four. If you try n times, the probability of a composite + number going unnoticed is at most one in 4^n. In fact, the real + probability is *much* lower than this. + + It's also important to bear in mind that this is examining the + probability that a number passes n Rabin-Miller tests given + that it's composite. What's actually interesting the the + probability that a number is composite given that it passed n + tests. This probability is lower still. For 1024-bit numbers, + which are about the right size by current standards of security, + you need only five tests to ensure a probability of less than 1 + in 2^80 of a composite number slipping through. + + There are specialized functions for finding various sorts of + prime numbers with particular properties. Read the header files + to find out what they do. + + +Conclusion + + This basically concludes the tour of Catacomb's multiprecision + maths library. I hope it's provided enough background that the + comments start making sense. + +-- +[mdw] + + +Local variables: +mode: text +End: diff --git a/README.random b/README.random new file mode 100644 index 0000000..6fd95eb --- /dev/null +++ b/README.random @@ -0,0 +1,213 @@ +Catacomb's random number generators + + + Catacomb contains a large number of pseudorandom number + generators. Some are dedicated to generating pseudorandom + numbers; others are ciphers in output-feedback mode. Some are + cryptographically strong, others are fast or simple. All have + been statistically tested and come out OK. + + +The `rand' generator + + Cryptographic applications need a source of true random data. + The `rand' generator is Catacomb's true-random-data source. + + The design is my own. I wasn't happy with any existing designs, + and I'm still not -- even Counterpane's Yarrow gives me an + uneasy feeling[1]. I'm not aware of any cryptanalytic attack + against my generator, and I'd very much like to hear if anyone + else knows differently. + + The generator's state is held in an object of type `rand_pool'. + Data can be added into the pool using the `rand_add' function. + Random numbers can be extracted by calling `rand_get'. + + It's possible to attach a `noise acquisition' function to a + rand_pool. The function `rand_getgood' extracts a number of + bytes from the generator, calling the noise acquisition function + if it thinks it's low on randomness. This shouldn't actually be + necessary once the generator has been topped up once. It makes + the generator very slow. + + It's also possible to key the generator. The output + transformation then depends on the key, making it even harder + for an adversary to work out anything useful about the + generator. + + The underlying transformation used by the generator is + + x' = E_{H(x)}(x) + + i.e., hash, use the hash as a key, and encrypt. + + + [1] The Yarrow paper states that it offers 160 bits-worth of + security, and that an adversary can't distinguish its output + from real random bits. I have an attack which takes about + 2^64 64-bit outputs and tells the difference between + Yarrow-160 and real random data, by analysing the frequency + of adjacent 64-bit blocks being equal. + + +Noncryptographic generators + + Two pseudorandom-number generators are supplied which have no + cryptographic strength whatever. They are, respectively, a + traditional linear-congruential generator (lcrand) and a + Fibonacci generator (fibrand). + + The linear-congruential generator has three (fixed) parameters, + a, c and p, and calculates + + x[i] = (a x[i - 1] + c) mod p + + The prime p is fairly large (2^32 - 5, in fact), and a and c are + carefully chosen. The generator has a period of p - 1. There + is one fixed point (i.e., it transforms to itself rather than + being in the cycle) which must be avoided. + + The Fibonacci generator works by adding together old results: + + x[i] = (x[i - 24] + x[i - 55]) mod 2^32 + + It has a very long period, and is the fastest pseudorandom + number generator in Catacomb. + + These two generators are very useful when the cryptographic + strength of the output isn't important, for example when + choosing random numbers for primality testing. + + +The Blum-Blum-Shub generator + + This is by far the strongest and by even further the slowest + pseudorandom-number generator in Catacomb. Its output has been + proven to be indistinguishable from random data by *any* + polynomial-time test, assuming that factoring large numbers is + difficult. + + Use the BBS generator when you're feeling really paranoid, and + you've got a few hours with nothing to do. + + +Output-feedback ciphers + + Ciphers in output-feedback mode simply emit a pseudorandom + stream. To construct a cipher, you XOR the stream with the + plaintext. It's even easier just to use the output as random + numbers. + + +Generic interface + + There's a fairly comprehensive generic interface for Catacomb's + various generators. + + Each generator provides a function which returns a pointer to a + `generic pseudorandom-number generator', of type `grand'. + + A `grand' is a structured type containing one member, `ops', + which is a pointer to various useful things. Let `r' be a + pointer to a generic pseudorandom-number generator; then, + + r->ops->name The name of the generator. + + r->ops->max One greater than the maximum output of + the `raw' function, or zero if it just + emits words. + + r->ops->misc(r, op, ...) + Performs a miscellaneous operation. The + various standard `op' values are + described below. + + r->ops->destroy(r) Destroy the generic generator. + + r->ops->raw(r) Return a raw output from the generator. + For `lcrand', this is an integer in the + range [0, p); for other generators, it's + the same as `word'. + + r->ops->byte(r) Return an octet. The result is + uniformly distributed over the integers + in the interval [0, 256). + + r->ops->word(r) Returns a word. The result is uniformly + distributed over the integers in the + interval [0, 2^32). + + r->ops->range(r, l) Returns an integer unformly distributed + in the interval [0, l), l < 2^32. + + r->ops->fill(r, p, sz) Fill the sz bytes at address p with + uniformly distributed bytes (i.e., + integers in the interval [0, 256). + + All of these operations are supported by all generators. Some + may be inefficient, however, since they're synthesized using + operations more suited to the particular generator. For + example, `word' is not efficient on the linear-congruential + generator, but is for the Fibonacci generator. + + The misc-ops are as follows: + + misc(r, GRAND_CHECK, op) Return nonzero if `op' is a + recognized misc-op for this + generator. + + misc(r, GRAND_SEEDINT, s) Seed the generator using the + integer s. + + misc(r, GRAND_SEEDUINT32, s) Seed the generator using the + 32-bit word s. + + misc(r, GRAND_SEEDBLOCK, p, sz) Seed the generator using the + block of sz bytes starting at + address p. + + misc(r, GRAND_SEEDMP, m) Seed the generator using the + multiprecision integer m. + + misc(r, GRAND_SEEDRAND, r') Seed the generator using some + output from the generic pseudo- + random number generator r'. + + +Statistical testing + + I generated 10M of data with each of Catacomb's random number + generators, and tested them with George Marsaglia's DIEHARD + suite. While the random data is not included here, the + following trivial Bourne shell script will generate the exact + output streams I used, assuming that the supplied `rspit' + program is in the current PATH: + + for i in des 3des idea blowfish rc5 rc4; do + rspit $i -kseed -z10m -o$i.rand + done + for i in lcrand fibrand; do + rspit $i -p -s0 -z10m -o$i.rand + done + rspit rand -p -z10m -orand.rand + nice rspit bbs -p -s2 -z10m -obbs.rand + + (Note that generating the BBS output data can take over an + hour. Make sure you have a good book to read.) + + Looking at the results, I think that they all passed the tests + relatively convincingly. + + I've not actually included the DIEHARD output files in the + distribution, because they're quite large, and anyone can + reproduce my results exactly using the publically available + DIEHARD distribution and the code supplied. If you do actually + want them, send me some mail and I'll send you a 60K tar.gz + file by (approximate) return. +-- +[mdw] + + +Local variables: +mode: text +End: -- 2.11.0