Bugs in CTR and Salsa20?

I’ve stumbled on what looks like a bug in the implementation of CTR and Salsa20 in the kernel. I’ve derived salsa20_generic.c from ctr.c so the bugs are essentially similar.

To understand the problem, we need to first understand the following code extract:

blkcipher_walk_init(&walk, dst, src, nbytes);
err = blkcipher_walk_virt_block(desc, &walk, bsize);
while(walk.nbytes) {
    if (walk.src.virt.addr == walk.dst.virt.addr) {
        nbytes = encrypt_inplace(&walk, child, ...);
    else
        nbytes = encrypt_segment(&walk, child, ...);
    err = blkcipher_walk_done(desc, &walk, nbytes);
}

This is the “design pattern” used in various “mode of operations” code, e.g. CBC, CTR, PCBC.

  • The blkcipher_walk_init() call initializes a struct blkcipher_walk with the destination pointer of the ciphertext, the source pointer of the plaintext and the length of data to encrypt.
  • The blkcipher_walk_virt_block() call starts the walking process and also tells the blkcipher APIs the block size of data we are processing. For CBC and PCBC, the block size is simply the blkcipher‘s blocksize so usually blkcipher_walk_virt() is called. For CTR (and Salsa20), the blkcipher‘s blocksize is set to 1 so we need to call blkcipher_walk_virt_block() with the underlying cipher algorithm block size.
  • The encrypt_inplace() and encrypt_segment() are similar code that handles optimally the case where src == dst and src != dst respectively. Their return value is important to the blkcipher_walk_done() call described in the next item.
  • The blkcipher_walk_done() call tells the blkcipher mechanisms how many bytes there are left that the call to encrypt_inplace() or encrypt_segment() did not handle. These are typically the bytes at the end of the block and usually nbytes = walk.nbytes % bsize. The blkcipher API will auto-magically move those bytes into the start of the next loop.

For small buffers of data, the while() loop is seldom executed more than once. However if the buffer size is near the page size, e.g. 4096 bytes, then the blkcipher API will break it up. For example, with AES in CBC mode the while() loop is executed 3 times: first, walk.nbytes = 4008, dst = src; then, walk.nbytes = 16, dst != src; finally, walk.nbytes = 80, dst = src. In the first loop, we see that 4008 % 16 = 8 bytes at the end are not processed. They are only done in the second loop. As the second and third loop has walk.nbytes that is divisble by 16, there are no unprocessed bytes. In total, 4000 + 16 + 80 = 4096 bytes are processed.

In the current implementation of CTR (and Salsa20), the nbytes passed into blkcipher_walk_done() is always zero. This makes sense for small buffers as encrypt_inplace() and encrypt_segment() typically finish the encryption in one loop. However for large buffer that crosses a page (or require at least two loops in the while loop), this may cause the counter to increment unnecessarily.

For example, if 4096 bytes were to be encrypted, the call for CTR (and Salsa20) would be split into 2 parts: first, walk.nbytes = 4008, dst == src; then walk.nbytes = 88, dst == src. This means that the last 8 bytes of the 4008 bytes in the first call will be encrypted with half of the encrypted counter block. It also means that the remaining 8 bytes are discarded as the current APIs do not keep track of how many encrypted bytes were left unused. If we look at the test vectors, we will notice a half-block slip in the output at the end. This is the source of the bug!

My patch to this problem is available here. What it does is to use the encrypt_inplace() and encrypt_segment() code as if they were performing encryption of full blocks all the time, except for the last call in the while loop.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: