title: CTR mode in Linux Kernel
body: <p>I am currently experiencing some Kernel development for filesystem purposes that requires AES ciphering and I encounter the following constraints :</p>
  
  <ul>
  <li>I must be able to cipher a plaintext of any length</li>
  <li>Padding (if any) is <em>unnoticeable</em></li>
  <li>The overhead that might result of padding bytes is <em>unacceptable</em></li>
  </ul>
  
  <p>On the paper, there is an easy way to solve this : use the CTR encryption mode !</p>
  
  <p>With that brilliant idea (hum...), I am happily diving into the crypto API sources of the Linux Kernel to learn how to get started.</p>
  
  <p>At this point I notice that the ciphering function involves the use of miscellaneous functions :</p>
  
  <ul>
  <li>The <strong>crypt_inplace</strong> function. Its purpose is to handle the case when the user wants to store the cipher text in the same memory area as the given plaintext. (same as <strong>crypt_segment</strong> but with the memory constraint)</li>
  <li>The <strong>crypt_segment</strong> function. It is the standard ciphering function. It ciphers a whole block of data (that is 16 bytes for AES).</li>
  <li>The <strong>crypt_final</strong> function. When the given plaintext's length <em>L</em> is not a multiple of the underlying block cipher blocksize, this function performs the ciphering on the remaining bytes.</li>
  </ul>
  
  <p>Thus with our <em>L</em> bytes long plaintext and with AES, the first <em>L/16</em> blocks are processed using <strong>crypt_segment</strong> or <strong>crypt_inplace</strong> depending on what is requested. The remaining <em>L mod 16</em> bytes are then ciphered using <strong>crypt_final</strong>.</p>
  
  <p>The inner <strong>crypt_segment</strong> functions is defined as follows : (<strong>crypt_inplace</strong> is very similar)</p>
  
  <pre><code>static int crypto_ctr_crypt_segment(struct blkcipher_walk *walk,
                      struct crypto_cipher *tfm)
  {
      void (*fn)(struct crypto_tfm *, u8 *, const u8 *) =
                     crypto_cipher_alg(tfm)-&gt;cia_encrypt;
      unsigned int bsize = crypto_cipher_blocksize(tfm);
      u8 *ctrblk = walk-&gt;iv;
      u8 *src = walk-&gt;src.virt.addr;
      u8 *dst = walk-&gt;dst.virt.addr;
      unsigned int nbytes = walk-&gt;nbytes;
  
      do {
          /* create keystream */
          fn(crypto_cipher_tfm(tfm), dst, ctrblk);
          crypto_xor(dst, src, bsize);
  
          /* increment counter in counterblock */
          crypto_inc(ctrblk, bsize);
  
          src += bsize;
          dst += bsize;
      } while ((nbytes -= bsize) &gt;= bsize);
  
      return nbytes;
  }
  </code></pre>
  
  <p>As you can see, the counter is incremented on a blocksize basis. On most use cases it will not be an issue but consider this scenario :</p>
  
  <ol>
  <li>Write request at a given place <em>p</em> (this can be a <em>(sector,offset)</em> particular value on a hard drive for instance) : 11-byte long plaintext</li>
  <li>Read request for 8 bytes at <em>p+3</em> : here, we want to get back the 8 last bytes of the initial plaintext from the written ciphertext.</li>
  </ol>
  
  <p>The first step will be done with a single call to <strong>crypt_final</strong> in the ciphering sequence. Then, the 11 ciphered bytes are written at the right place. But when we want to retrieve the last 8 bytes of this chunk of data, due to the "block-wide" ciphering, we need the 3 previous bytes, stored in <em>p</em>, <em>p+1</em> and <em>p+2</em> to perform the deciphering operation.</p>
  
  <p>Obviously, in a filesystem point of view, when a read is requested, there is <em>no way</em> for the kernel to know this kind of things if it does not make some hardware-dependent assumptions.</p>
  
  <p>Hence, here is my question : is there a way to set up the CTR mode to <em>always</em> perform (de)ciphering operations on a byte basis or should I create my own implementation of CTR mode to enforce this ? (I did not find any entry point in ctr source code to do this configuration operation, I might have missed something)</p>
  
  <p>Thanks in advance, I hope I have not stunned you with the big post !</p>
  
  <p><em>PS : The code snippet in this post can be found in the ctr.c file under the crypto directory of a Linux Kernel source tree. The displayed version comes from the 3.8-rc3 Kernel release.</em></p>
  
  <hr>
  
  <h2>EDIT :</h2>
  
  <p>In fact, the CTR mode is designed to handle any length of data. I will recall the description found in the ISO/IEC 10116 specification.</p>
  
  <p>Let assume our plaintext <em>P</em> is divided into chunks <em>( P<sub>i</sub> )<sub>0 &lt; i &lt; n</sub></em> of equal length (<em>j</em> bits).<br>
  Let <em>K</em> be the key supplied for the encryption and <em>IV</em> the initialization vector for the counter.<br>
  The ciphertext <em>C</em> will be divided into chunks <em>( C<sub>i</sub> )<sub>0 &lt; i &lt; n</sub></em> like the plaintext <em>P</em>.<br>
  The CTR mode introduce a counter, which walks at each processed chunk. That said, we will call the counter block used for ciphering (resp. deciphering) the chunk <em>P<sub>i</sub></em> (resp. <em>C<sub>i</sub></em>) <em>CTR<sub>i</sub></em><br>
  Finally, let <em>CTR<sub>1</sub></em> = <em>IV</em><br>
  With these notations, here is what the computation may look like :  </p>
  
  <blockquote>
    <p>FOR i from 1 to n DO</p>
    
    <ol>
    <li>Y = AES_encrypt(<em>CTR<sub>i</sub></em>, <em>K</em>) &lt;- Y is 16-bytes long</li>
    <li>E = Truncate(Y, j) &lt;- Only keep the <em>j</em> leftmost bits of Y</li>
    <li><em>C<sub>i</sub></em> = <em>P<sub>i</sub></em> XOR E</li>
    <li><em>CTR<sub>i+1</sub></em> = ComputeNextCTR(<em>CTR<sub>i</sub></em>) &lt;- Usually <strong>ComputeNextCTR</strong> is a simple incrementation.</li>
    </ol>
    
    <p>DONE</p>
  </blockquote>
  
  <p>In the CTR version found in the Linux Kernel, this behaviour is enforced with <em>j</em> taking the value of the underlying block cipher blocksize (128 bits with AES), except for the last step where a truncation occurs if the given plaintext has not a suitable length.</p>
  
  <p>My question was : is there a way to tell the crypto API to apply the <em>j</em> parameter I want ?
  To me, it seems like the answer is "No.", so I would have to "reinvent" the wheel and make a new implementation of the CTR mode to get this extra feature. Since I may have missed something, I would be grateful to the person who will clearly state this.</p>
  
  <p>Bonus one : If the answer is "No.", a quick overview of how the <em>algapi</em> of the Crypto API works would be very very welcome (I am currently digging into this).</p>
  
  <p>Thanks in advance again.</p>