| 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 |
| 13 | intended to be used only by higher-level `modes'. |
| 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 | |
| 31 | BLOWFISH_KEYSZ Is 32, to recommend 256-bit keys with Blowfish. |
| 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 | |
| 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 | |
| 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. |
| 50 | |
| 51 | The `endianness' |
| 52 | Either `B' for big-endian, or `L' for little- |
| 53 | endian. |
| 54 | |
| 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- |
| 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. |
| 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 | |
| 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. |
| 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 | |
| 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! |
| 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 | |
| 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 | |
| 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 | |
| 319 | c->ops->destroy(c) Destroys the cipher object `c'. |
| 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 | |
| 353 | -- [mdw] |
| 354 | |
| 355 | \f |
| 356 | Local variables: |
| 357 | mode: text |
| 358 | End: |