math/mpreduce.h: Missing include files.
[u/mdw/catacomb] / README.cipher
1 Symmetric ciphers
4 Catacomb provides a number of symmetric ciphers, together with a
5 generic cipher interface. More ciphers may be added later.
8 Block cipher interface
10 There are a number of block ciphers implemented, all with
11 extremely similar interfaces. However, block ciphers aren't
12 actually at all pleasant to use directly. They're really
13 intended to be used only by higher-level `modes'.
15 Anyway, I'll take Bruce Schneier's Blowfish as an example.
17 Before doing any encryption or decryption, you need to
18 initialize a `context'. The context data is stored in an object
19 of type `blowfish_ctx'. You initialize the context by calling
20 `blowfish_init' with the address of the context, the address of
21 some key data, and the length of the key.
23 Data is encrypted using `blowfish_eblk' and decrypted by
24 `blowfish_dblk'. Both functions are given data as an array of
25 `uint32' words. (Since Blowfish uses 64-bit blocks, you give it
26 arrays of two words.)
28 A number of constants are defined to describe further properties
29 of the cipher:
31 BLOWFISH_KEYSZ Is 32, to recommend 256-bit keys with Blowfish.
33 BLOWFISH_BLKSZ Is 8, because Blowfish works on 64-bit blocks,
34 which are therefore 8 bytes wide.
36 BLOWFISH_CLASS Is the triple (N, B, 64). This is explained
37 below.
39 The constant byte vector blowfish_keysz (lowercase) contains
40 more detailed descriptions of the key size limits. See
41 `keysz.h' for a description of key size tables.
43 The BLOWFISH_CLASS macro contains information useful to other
44 macros, rather than to direct users of the interface. The three
45 components are:
47 The `type' Simply N if specific macros for handling blocks
48 of the appropriate width have been written, or X
49 if the macros should use a loop instead.
51 The `endianness'
52 Either `B' for big-endian, or `L' for little-
53 endian.
55 The `width' The cipher's block size in bits.
57 This simple interface is thoroughly inconvenient for general
58 use, although it makes writing block ciphers very easy.
61 The peculiarities of the various ciphers are described below.
63 Blowfish Fairly standard, really. Accepts arbitrary-
64 sized keys up to 448 bits. 64-bit blocks. (The
65 original definition only specified keys with a
66 multiple of 32 bits -- the extension I use is
67 due, I think, to Eric Young.) Blowfish is fast
68 and looks very secure.
70 CAST-128 Accepts arbitrary-sized keys up to 128 bits.
71 64-bit blocks. Uses three slightly different
72 types of rounds, based around 8 x 32 S-boxes
73 constructed from bent functions. Faster than
74 RC2. Looks very strong.
76 CAST-256 Accepts arbitrary-sized keys up to 256 bits.
77 128-bit blocks. Submitted to the AES contest,
78 but didn't make it to the final five. Uses the
79 S-boxes and round functions from CAST-128.
80 Looks strong.
82 DES Good old reliable. Been around for donkey's
83 years and still going. Single-DES (implemented
84 here) has a small key, but apart from that is
85 looking remarkably robust. Uses a 56-bit key
86 which may be either 8 bytes with (ignored)
87 parity bits in the bottom bit of each byte, or 7
88 bytes with no parity.
90 DES3 Two- or three-key triple DES. Slow, but strong
91 and almost universally trusted. Accepts 56-,
92 112- and 168-bit keys. (56 bits gives you
93 single DES at a third of the speed.) Again,
94 parity may be included or not, so the full range
95 of key sizes in bytes is: 7, 8, 14, 16, 21 or
96 24.
98 IDEA Requires a 128-bit key. About as fast as DES.
99 No known attacks on the full cipher. Used in
100 PGP2. Patented!
102 RC2 Arbitrary-sized key, up to 128 bytes. Used to
103 be a trade secret of RSA Data Security Inc., but
104 leaked. About as fast as DES. Not convincing
105 in terms of security. Has a bizarre
106 `brain-damage' feature which limits the
107 effective key size.
109 RC5 Arbitrary-sized key, up to 256 bytes. Designed
110 by Ron Rivest. Not completely convincing in
111 security. Almost as fast as Blowfish, but with
112 a quicker key schedule. Patented!
114 Rijndael Accepts keys which are a multiple of 32 bits in
115 size, up to 256 bits. 128-bit block. AES
116 finalist. Fast, may not be strong.
118 Serpent Arbitrary-sized keys up to 256 bits. 128-bit
119 block. AES finalist. About the same speed as
120 DES. Very conservative design. Looks very
121 strong.
123 Twofish Accepts keys which are a multiple of 32 bits in
124 size, up to 256 bits. 128-bit block. AES
125 finalist. Fast, looks strong.
128 Block cipher modes
130 There are four block cipher modes defined, all of which create a
131 useful cipher from block cipher. Modes are implemented
132 separately from ciphers, so it's easy to add either, and easy to
133 apply modes to ciphers.
135 A few definitions will be helpful to explain the modes. Let E
136 denote the encryption function, P be the current plaintext
137 block, C be the current ciphertext, and C' be the previous
138 ciphertext block. Let `XOR' denote the bitwise exclusive or
139 operation.
141 Then the modes Electronic Code Book (ECB), Cipher Block Chaining
142 (CBC) and Ciphertext Feedback (CFB) are defined as:
144 ECB C = E(P)
145 CBC C = E(P XOR C')
146 CFB C = P XOR E(C')
148 Finally, Output Feedback is defined like this: let O be the
149 current output, and O' be the previous output. Then
151 OFB O = E(O'), C = P XOR O
153 The `previous ciphertext' or `previous output' for the first
154 block is provided by an `initialization vector' or IV.
156 The above definitions imply that only data which comes in
157 multiples of the block size can be encrypted. Normally this is
158 the case. However, Catacomb implements all four modes so that
159 almost arbitrary sizes of plaintext can be encrypted (without
160 having to pad out the ciphertext). The details are complicated:
161 read the source, or look up `ciphertext stealing' in your copy
162 of Schneier's `Applied Cryptography'.
164 ECB must have *at least* one entire block to work with, but
165 apart from that can cope with odd-size inputs. Both ECB and CBC
166 insert `boundaries' when you encrypt an odd-size input -- you
167 must decrypt in exactly the same-size chunks as you encrypted,
168 otherwise you'll only get rubbish out.
170 CFB and OFB have no restrictions on input sizes, and do not
171 normally insert boundaries, although it's possible to explicitly
172 request one.
174 Be especially careful with OFB mode. Since it generates an
175 output stream independent of the plaintext, and then XORs the
176 two, if you ever reuse the same key and IV pair, both encrypted
177 messages are compromised. (Take the two ciphertexts, and XOR
178 them together -- then the OFB stream cancels and you have the
179 plaintexts XORed. This is fairly trivial to unravel.)
181 OFB mode makes a good random byte generator. See README.random
182 for details about random number generators in Catacomb.
185 The modes all have similar interfaces. CFB is probably the best
186 example, although CBC is more useful in practice. I'll take
187 Blowfish as my example cipher again.
189 You need to initialize a context block. For Blowfish in CFB
190 mode, this is called `blowfish_cfbctx'. You initialize it by
191 passing the context address, a key, the key length, and pointer
192 to an IV (which must be BLOWFISH_BLKSZ in length) to
193 blowfish_cfbinit. If you pass a null pointer instead of an IV,
194 a zero IV is used. This is usually OK for CBC, but bad for OFB
195 or CFB unless you make sure that the key itself is only used
196 once.
198 Data is encrypted using blowfish_cfbencrypt and
199 blowfish_cfbdecrypt -- both are given: the address of the
200 context, a pointer to the source data, a pointer to the
201 destination (which may overlap the source) and the size of the
202 data to encrypt or decrypt.
204 The IV may be changed by calling blowfish_cfbsetiv. The current
205 IV (really meaning the previous ciphertext) can be obtained with
206 blowfish_cfbgetiv. The key may be changed without altering the
207 IV using blowfish_cfbsetkey. A boundary may be inserted in the
208 ciphertext or plaintext using blowfish_cfbbdry.
210 ECB doesn't use IVs, so there aren't ecbsetiv or ecbgetiv
211 calls. You can't insert boundaries in ECB or CBC mode.
213 OFB encryption and decryption are the same, so there's no
214 separate ofbdecrypt call. However, ofbencrypt has some useful
215 tricks:
217 * If the destination pointer is null, it just churns the output
218 round for a while, without emitting any data.
220 * If the source pointer is null, it simply spits out the
221 output blocks from the feedback process. This is equivalent
222 to giving an input full of zero bytes.
225 Implementing new modes: nasty macros
227 Block cipher modes are implemented as macros which define the
228 appropriate functions. They're given the prefixes (upper- and
229 lowercase) and expected to get on with life.
231 Data can be shunted around fairly efficiently using the BLKC
232 macros. These are fairly ugly, so don't try to work out how
233 they work.
235 In the following notation, `b' denotes a pointer to bytes, and
236 `w' and `wx' denote pointers to words. `PRE' is the uppercase
237 cipher prefix. I'll abuse this notation a little and use the
238 names to refer to the entire arrays, since their lengths are
239 known to be PRE_BLKSZ (in bytes) or PRE_BLKSZ / 4 (in words)
240 long.
242 BLKC_STORE(PRE, b, w) Set b = w
243 BLKC_XSTORE(PRE, b, w, wx) Set b = w XOR wx
244 BLKC_LOAD(PRE, w, b) Set w = b
245 BLKC_XLOAD(PRE, w, b) Set w = w XOR b
246 BLKC_MOVE(PRE, w, wx) Set w = wx
247 BLKC_XMOVE(PRE, w, wx) Set w = w XOR wx
249 These should be enough for most purposes. More can be added,
250 but involves a strong stomach and an ability to do things with C
251 macros which most people wouldn't like to think about over
252 dinner.
255 Other ciphers
257 RC4 was designed by Ron Rivest. It's the second fastest cipher
258 in Catacomb. It looks fairly strong (although see the note
259 about churning the context after keying below). And also note
260 that it works in output feedback -- you just XOR the output from
261 RC4 with the plaintext. Never reuse an RC4 key!
263 RC4 includes an OFB-like interface which should be familiar. It
264 also includes a pair of strange macros RC4_OPEN and RC4_BYTE.
265 These are used to actually get bytes out of the RC4 generator.
267 RC4_OPEN is really a new syntactic form. If `r' is a pointer to
268 an RC4 context, then
270 RC4_OPEN(r, <statements>);
272 executes <statements> within the opened RC4 context. The
273 significance of this is that the expression RC4_BYTE(x) extracts
274 the next byte from the innermost open context, and stores it in
275 x. The standard RC4 encrypt function is written in terms of
276 RC4_OPEN and RC4_BYTE.
278 RC4 makes an excellent and fast random-byte generator.
280 RSA Data Security Inc. claim that RC4 is a trade secret of
281 theirs. It doesn't look very secret to me.
284 SEAL was designed by Phil Rogaway and Don Coppersmith. It's
285 ever-so slightly faster than RC4. It's also patented by IBM.
286 See the header for the interface.
289 Generic cipher interfaces
291 It can be convenient to implement routines where the cipher to
292 use is a parameter. Hence, Catacomb provides a generic
293 interface to (symmetric) ciphers. The generic interface is
294 defined in <catacomb/gcipher.h>.
296 The basic type in the interface is `gcipher', which represents
297 an `instance' of a cipher. You don't see lone cipher objects,
298 only pointers to them, so really everything's in terms of
299 `gcipher *'.
301 A `gcipher' is a structured type with one member, called `ops'
302 which points to a collection of functions and other useful
303 information. If `c' is a cipher...
305 c->ops->b->name Name of the cipher being used
307 c->ops->b->keysz Key size in bytes (or zero for
308 `don't care')
310 c->ops->b->blksz Block size in bytes (or zero for
311 `not a block cipher')
313 c->ops->encrypt(c, s, t, sz) Encrypt the sz bytes stored in
314 s, and store the ciphertext at
315 t.
317 c->ops->decrypt(c, s, t, sz) Like encrypt, only it decrypts.
319 c->ops->destroy(c) Destroys the cipher object `c'.
321 c->ops->setiv(c, iv) Sets the IV to be `iv' -- must
322 be blksz bytes long.
324 c->ops->bdry(c) Inserts a boundary.
326 Note that `setiv' and `bdry' aren't implemented by all ciphers
327 so these may be null pointers. It's best to check first.
329 Generic cipher instances are created from `generic cipher
330 classes' (type `gccipher' -- note the extra `c'). This contains
331 two members:
333 b The `class base' -- this is the object pointed
334 to by `c->ops->b', and contains `name', `keysz'
335 and `blksz' members.
337 init The constructor. You give it a pointer to some
338 key data and the key size, and it returns a
339 generic cipher instance.
341 Note that new generic ciphers always have zero IVs (if they
342 understand the concept), so you may need to call setiv if you
343 want to reuse keys.
345 Always remember to destroy gcipher instances when you're
346 finished with them.
348 The generic cipher class for CBC-mode Blowfish is called
349 `blowfish_cbc' -- the others are named similarly. The RC4
350 generic cipher class is called simply `rc4'.
353 -- [mdw]
355 \f
356 Local variables:
357 mode: text
358 End: