Minor reformatting.

[u/mdw/catacomb] / README.cipher

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 32, to recommend 256-bit keys with Blowfish.

        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 constant byte vector blowfish_keysz (lowercase) contains
        more detailed descriptions of the key size limits.  See
        `keysz.h' for a description of key size tables.

        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.  64-bit blocks.  (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.

        CAST-128        Accepts arbitrary-sized keys up to 128 bits.
                        64-bit blocks.  Uses three slightly different
                        types of rounds, based around 8 x 32 S-boxes
                        constructed from bent functions.  Faster than
                        RC2.  Looks very strong.

        CAST-256        Accepts arbitrary-sized keys up to 256 bits.
                        128-bit blocks.  Submitted to the AES contest,
                        but didn't make it to the final five.  Uses the
                        S-boxes and round functions from CAST-128.
                        Looks strong.

        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.

        IDEA            Requires a 128-bit key.  About as fast as DES.
                        No known attacks on the full cipher.  Used in
                        PGP2.  Patented!

        RC2             Arbitrary-sized key, up to 128 bytes.  Used to
                        be a trade secret of RSA Data Security Inc., but
                        leaked.  About as fast as DES.  Not convincing
                        in terms of security.  Has a bizarre
                        `brain-damage' feature which limits the
                        effective key size.

        RC5             Arbitrary-sized key, up to 256 bytes.  Designed
                        by Ron Rivest.  Not completely convincing in
                        security.  Almost as fast as Blowfish, but with
                        a quicker key schedule.  Patented!

        Rijndael        Accepts keys which are a multiple of 32 bits in
                        size, up to 256 bits.  128-bit block.  AES
                        finalist.  Fast, may not be strong.

        Serpent         Arbitrary-sized keys up to 256 bits.  128-bit
                        block.  AES finalist.  About the same speed as
                        DES.  Very conservative design.  Looks very
                        strong.

        Twofish         Accepts keys which are a multiple of 32 bits in
                        size, up to 256 bits.  128-bit block.  AES
                        finalist.  Fast, looks strong.


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

        RC4 was designed by Ron Rivest.  It's the second 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, <statements>);

        executes <statements> 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.


        SEAL was designed by Phil Rogaway and Don Coppersmith.  It's
        ever-so slightly faster than RC4.  It's also patented by IBM.
        See the header for the interface.


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 <catacomb/gcipher.h>.

        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 `c'.

        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]

\f
Local variables:
mode: text
End: