5.7 Using a Generic CFB Mode Implementation

5.7.1 Problem

You want a more high-level interface for CFB mode than your library provides. Alternatively, you want a portable CFB interface, or you have only a block cipher implementation and would like to use CFB mode.

5.7.2 Solution

CFB mode generates keystream by encrypting a "state" buffer, which starts out being the nonce and changes after each output, based on the actual outputted value.

Many libraries provide a CFB implementation. If you need code that implements this mode, you will find it in the following Section 5.7.3.

5.7.3 Discussion

You should probably use a higher-level abstraction, such as the one discussed in Recipe 5.16. Use a raw mode only when absolutely necessary, because there is a huge potential for introducing a security vulnerability by accident. If you still want to use CFB, be sure to use a message authentication code with it (see Chapter 6).

CFB is a stream-based mode. Encryption occurs by XOR'ing the keystream bytes with the plaintext bytes, as shown in Figure 5-2. The keystream is generated one block at a time, and it is always dependent on the previous keystream block as well as the plaintext data XOR'd with the previous keystream block.

CFB does this by keeping a "state" buffer, which is initially the nonce. As a block's worth of data gets encrypted, the state buffer has some or all of its bits shifted out and ciphertext bits shifted in. The amount of data shifted in before each encryption operation is the "feedback size," which is often the block size of the cipher, meaning that the state function is always replaced by the ciphertext of the previous block. See Figure 5-2 for a graphical view of CFB mode.

Figure 5-2. CFB mode
figs/spcb_0502.gif

The block size of the cipher is important to CFB mode because keystream is produced in block-sized chunks and therefore requires keeping track of block-sized portions of the ciphertext. CFB is fundamentally a streaming mode, however, because the plaintext is encrypted simply by XOR'ing with the CFB keystream.

In Recipe 5.4, we discuss the advantages and drawbacks of CFB and compare it to other popular modes.

These days, CFB mode is rarely used because CTR and OFB modes (CTR mode in particular) provide more advantages, with no additional drawbacks. Of course, we recommend a higher-level mode over all of these, one that provides stronger security guarantees?for example, CWC or CCM mode.

Many libraries already come with an implementation of CFB mode for any ciphers they support. However, some don't. For example, you may only get an implementation of the raw block cipher when you obtain reference code for a new cipher.

In the following sections we present a reasonably optimized implementation of CFB mode that builds upon the raw block cipher interface presented in Recipe 5.5. It also requires the spc_memset( ) function from Recipe 13.2.

This implementation is only for the case where the feedback size is equal to the cipher block size. This is the most efficient mechanism and is no less secure than other feedback sizes, so we strongly recommend this approach.

5.7.3.1 The high-level API

This implementation has two APIs. The first is a high-level API, which takes a message as input and returns a dynamically allocated result.

unsigned char *spc_cfb_encrypt(unsigned char *key, size_t kl, unsigned char *nonce,
                               unsigned char *in, size_t il);
unsigned char *spc_cfb_decrypt(unsigned char *key, size_t kl, unsigned char *nonce,
                               unsigned char *in, size_t il)

Both of the previous functions output the same number of bytes as were input, unless a memory allocation error occurs, in which case 0 is returned.

These two functions erase the key from memory before exiting. You may want to have them erase the plaintext as well.

Here's the implementation of the interface:

#include <stdlib.h>
#include <string.h>
   
unsigned char *spc_cfb_encrypt(unsigned char *key, size_t kl, unsigned char *nonce,
                               unsigned char *in, size_t il) {
  SPC_CFB_CTX       ctx;
  unsigned char *out;
   
  if (!(out = (unsigned char *)malloc(il))) return 0;
  spc_cfb_init(&ctx, key, kl, nonce);
  spc_cfb_encrypt_update(&ctx, in, il, out);
  spc_cfb_final(&ctx);
  return out;
}
   
unsigned char *spc_cfb_decrypt(unsigned char *key, size_t kl, unsigned char *nonce,
                               unsigned char *in, size_t il) {
  SPC_CFB_CTX       ctx;
  unsigned char *out;
   
  if (!(out = (unsigned char *)malloc(il))) return 0;
  spc_cfb_init(&ctx, key, kl, nonce);
  spc_cfb_decrypt_update(&ctx, in, il, out);
  spc_cfb_final(&ctx);
  return out;
}

Note that this code depends on the SPC_CFB_CTX data type and the incremental CFB interface, both discussed in the following sections.

5.7.3.2 The incremental API

Let's look at the SPC_CFB_CTX data type. It's defined as:

typedef struct {
  SPC_KEY_SCHED ks;
  int           ix;
  unsigned char nonce[SPC_BLOCK_SZ];
} SPC_CFB_CTX;

The ks field is an expanded version of the cipher key (block ciphers generally use a single key to derive multiple keys for internal use). The ix field is used to determine how much keystream we have buffered. The nonce field is really the buffer in which we store the input to the next encryption, and it is the place where intermediate keystream bytes are stored.

To begin encrypting or decrypting, we need to initialize the mode. Initialization is the same operation for both encryption and decryption:

void spc_cfb_init(SPC_CFB_CTX *ctx, unsigned char *key, size_t kl, unsigned char
                  *nonce) {
  SPC_ENCRYPT_INIT(&(ctx->ks), key, kl);
  spc_memset(key,0, kl);
  memcpy(ctx->nonce, nonce, SPC_BLOCK_SZ);
  ctx->ix = 0;
}

Note again that we remove the key from memory during this operation.

Never use the same nonce (often called an IV in this context; see Recipe 4.9) twice with a single key. To implement that recommendation effectively, never reuse a key. Alternatively, pick a random starting IV each time you key, and never output more than about 240 blocks using a single key.

Now we can add data as we get it using the spc_cfb_encrypt_update( ) or spc_cfb_decrypt_update( ) function, as appropriate. These functions are particularly useful when a message may arrive in pieces. You'll get the same results as if it all arrived at once. When you want to finish encrypting or decrypting, call spc_cfb_final( ).

You're responsible for making sure the proper init, update, and final calls are made, and that they do not happen out of order.

The function spc_cfb_encrypt_update( ), which is shown later in this section, has the following signature:

int spc_cfb_encrypt_update(CFB_CTX *ctx, unsigned char *in, size_t il,
                       unsigned char *out);

This function has the following arguments:

ctx

Pointer to the SPC_CFB_CTX object associated with the current message.

in

Pointer to the plaintext data to be encrypted.

il

Number of bytes of plaintext to be encrypted.

out

Pointer to the output buffer, which needs to be exactly as long as the input plaintext data.

Our implementation of this function always returns 1, but a hardware-based implementation might have an unexpected failure, so it's important to check the return value!

This API is in the spirit of PKCS #11, which provides a standard cryptographic interface to hardware. We do this so that the above functions can have the bulk of their implementations replaced with calls to PKCS #11-compliant hardware. PKCS #11 APIs generally pass out data explicitly indicating the length of data outputted, while we ignore that because it will always be zero on failure or the size of the input buffer on success. Also note that PKCS #11-based calls tend to order their arguments differently from the way we do, and they will not generally wipe key material, as we do in our initialization and finalization routines.

Because this API is developed with PKCS #11 in mind, it's somewhat more low-level than it needs to be and therefore is a bit difficult to use properly. First, you need to be sure the output buffer is big enough to hold the input; otherwise, you will have a buffer overflow. Second, you need to make sure the out argument always points to the first unused byte in the output buffer. Otherwise, you will keep overwriting the same data every time spc_cfb_encrypt_update( ) outputs.

Here's our implementation of spc_cfb_encrypt_update( ):

int spc_cfb_encrypt_update(SPC_CFB_CTX *ctx, unsigned char *in, size_t il, 
                           unsigned char *out) {
  int i;
   
  if (ctx->ix) {
    while (ctx->ix) {
      if (!il--) return 1;
      ctx->nonce[ctx->ix] = *out++ = *in++ ^ ctx->nonce[ctx->ix++];
      ctx->ix %= SPC_BLOCK_SZ;
    }
  }
  if (!il) return 1;
  while (il >= SPC_BLOCK_SZ) {
    SPC_DO_ENCRYPT(&(ctx->ks), ctx->nonce, ctx->nonce);
    for (i = 0;  i < SPC_BLOCK_SZ / sizeof(int);  i++) {
      ((int *)ctx->nonce)[i] = ((int *)out)[i] = ((int *)in)[i] ^ 
                                                 ((int *)ctx->nonce)[i];
   
    }
    il  -= SPC_BLOCK_SZ;
    in  += SPC_BLOCK_SZ;
    out += SPC_BLOCK_SZ;
  }
  SPC_DO_ENCRYPT(&(ctx->ks), ctx->nonce, ctx->nonce);
  for (i = 0;  i <il;  i++)
    ctx->nonce[ctx->ix] = *out++ = *in++ ^ ctx->nonce[ctx->ix++];
  return 1;
}

Decryption has a similar API, but a different implementation:

int spc_cfb_decrypt_update(SPC_CFB_CTX *ctx, unsigned char *in, size_t il, 
                           unsigned char *out) {
  int  i, x;
  char c;
   
  if (ctx->ix) {
    while (ctx->ix) {
      if (!il--) return 1;
      c = *in;
      *out++ = *in++ ^ ctx->nonce[ctx->ix];
      ctx->nonce[ctx->ix++] = c;
      ctx->ix %= SPC_BLOCK_SZ;
    }
  }
  if (!il) return 1;
  while (il >= SPC_BLOCK_SZ) {
    SPC_DO_ENCRYPT(&(ctx->ks), ctx->nonce, ctx->nonce);
    for (i = 0;  i < SPC_BLOCK_SZ / sizeof(int);  i++) {
      x = ((int *)in)[i];
      ((int *)out)[i] = x ^ ((int *)ctx->nonce)[i];
      ((int *)ctx->nonce)[i] = x;
    }
    il  -= SPC_BLOCK_SZ;
    in  += SPC_BLOCK_SZ;
    out += SPC_BLOCK_SZ;
  }
  SPC_DO_ENCRYPT(&(ctx->ks), ctx->nonce, ctx->nonce);
  for (i = 0;  i < il;  i++) {
    c = *in;
    *out++ = *in++ ^ ctx->nonce[ctx->ix];
    ctx->nonce[ctx->ix++] = c;
  }
  return 1;
}

To finalize either encryption or decryption, use spc_cfb_final( ), which never needs to output anything, because CFB is a streaming mode:

int spc_cfb_final(SPC_CFB_CTX *ctx) {
  spc_memset(&ctx, 0, sizeof(SPC_CFB_CTX));
  return 1;
}

5.7.4 See Also

Recipe 4.9, Recipe 5.4, Recipe 5.5, Recipe 5.16, Recipe 13.2