759513d1 |
1 | Symmetric ciphers |
2 | |
3 | |
4 | Catacomb provides a number of symmetric ciphers, together with a |
5 | generic cipher interface. More ciphers may be added later. |
6 | |
7 | |
8 | Block cipher interface |
9 | |
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 |
45c0fd36 |
13 | intended to be used only by higher-level `modes'. |
759513d1 |
14 | |
15 | Anyway, I'll take Bruce Schneier's Blowfish as an example. |
16 | |
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. |
22 | |
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.) |
27 | |
28 | A number of constants are defined to describe further properties |
29 | of the cipher: |
30 | |
60e61068 |
31 | BLOWFISH_KEYSZ Is 32, to recommend 256-bit keys with Blowfish. |
759513d1 |
32 | |
33 | BLOWFISH_BLKSZ Is 8, because Blowfish works on 64-bit blocks, |
34 | which are therefore 8 bytes wide. |
35 | |
36 | BLOWFISH_CLASS Is the triple (N, B, 64). This is explained |
37 | below. |
38 | |
60e61068 |
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. |
42 | |
759513d1 |
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: |
46 | |
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. |
45c0fd36 |
50 | |
759513d1 |
51 | The `endianness' |
60e61068 |
52 | Either `B' for big-endian, or `L' for little- |
759513d1 |
53 | endian. |
45c0fd36 |
54 | |
759513d1 |
55 | The `width' The cipher's block size in bits. |
56 | |
57 | This simple interface is thoroughly inconvenient for general |
58 | use, although it makes writing block ciphers very easy. |
59 | |
60 | |
61 | The peculiarities of the various ciphers are described below. |
62 | |
63 | Blowfish Fairly standard, really. Accepts arbitrary- |
60e61068 |
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. |
69 | |
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. |
75 | |
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. |
759513d1 |
81 | |
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. |
89 | |
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. |
97 | |
60e61068 |
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! |
101 | |
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. |
108 | |
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! |
113 | |
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. |
117 | |
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. |
122 | |
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. |
759513d1 |
126 | |
127 | |
128 | Block cipher modes |
129 | |
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. |
134 | |
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. |
140 | |
141 | Then the modes Electronic Code Book (ECB), Cipher Block Chaining |
142 | (CBC) and Ciphertext Feedback (CFB) are defined as: |
143 | |
144 | ECB C = E(P) |
145 | CBC C = E(P XOR C') |
146 | CFB C = P XOR E(C') |
147 | |
148 | Finally, Output Feedback is defined like this: let O be the |
149 | current output, and O' be the previous output. Then |
150 | |
151 | OFB O = E(O'), C = P XOR O |
152 | |
153 | The `previous ciphertext' or `previous output' for the first |
154 | block is provided by an `initialization vector' or IV. |
155 | |
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'. |
163 | |
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. |
169 | |
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. |
173 | |
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.) |
180 | |
181 | OFB mode makes a good random byte generator. See README.random |
182 | for details about random number generators in Catacomb. |
183 | |
184 | |
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. |
188 | |
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. |
197 | |
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. |
203 | |
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. |
209 | |
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. |
212 | |
213 | OFB encryption and decryption are the same, so there's no |
214 | separate ofbdecrypt call. However, ofbencrypt has some useful |
215 | tricks: |
216 | |
217 | * If the destination pointer is null, it just churns the output |
218 | round for a while, without emitting any data. |
219 | |
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. |
223 | |
224 | |
225 | Implementing new modes: nasty macros |
226 | |
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. |
230 | |
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. |
234 | |
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. |
241 | |
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 |
248 | |
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. |
253 | |
254 | |
255 | Other ciphers |
256 | |
60e61068 |
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! |
759513d1 |
262 | |
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. |
266 | |
267 | RC4_OPEN is really a new syntactic form. If `r' is a pointer to |
268 | an RC4 context, then |
269 | |
270 | RC4_OPEN(r, <statements>); |
271 | |
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. |
277 | |
278 | RC4 makes an excellent and fast random-byte generator. |
279 | |
280 | RSA Data Security Inc. claim that RC4 is a trade secret of |
281 | theirs. It doesn't look very secret to me. |
282 | |
283 | |
60e61068 |
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. |
287 | |
288 | |
759513d1 |
289 | Generic cipher interfaces |
290 | |
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>. |
295 | |
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 *'. |
300 | |
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... |
304 | |
305 | c->ops->b->name Name of the cipher being used |
306 | |
307 | c->ops->b->keysz Key size in bytes (or zero for |
308 | `don't care') |
309 | |
310 | c->ops->b->blksz Block size in bytes (or zero for |
311 | `not a block cipher') |
312 | |
313 | c->ops->encrypt(c, s, t, sz) Encrypt the sz bytes stored in |
314 | s, and store the ciphertext at |
315 | t. |
316 | |
317 | c->ops->decrypt(c, s, t, sz) Like encrypt, only it decrypts. |
318 | |
60e61068 |
319 | c->ops->destroy(c) Destroys the cipher object `c'. |
759513d1 |
320 | |
321 | c->ops->setiv(c, iv) Sets the IV to be `iv' -- must |
322 | be blksz bytes long. |
323 | |
324 | c->ops->bdry(c) Inserts a boundary. |
325 | |
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. |
328 | |
329 | Generic cipher instances are created from `generic cipher |
330 | classes' (type `gccipher' -- note the extra `c'). This contains |
331 | two members: |
332 | |
333 | b The `class base' -- this is the object pointed |
334 | to by `c->ops->b', and contains `name', `keysz' |
335 | and `blksz' members. |
336 | |
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. |
340 | |
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. |
344 | |
345 | Always remember to destroy gcipher instances when you're |
346 | finished with them. |
347 | |
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'. |
351 | |
352 | |
ee62fa16 |
353 | -- [mdw] |
759513d1 |
354 | |
355 | \f |
356 | Local variables: |
357 | mode: text |
358 | End: |