Seeking in AES-CTR-encrypted input

Question

As AES in CTR mode is great for random access, lets say I have a data source created with a CipherOutputStream in AES-CTR mode. The library underneath—which is not mine—uses a RandomAccessFile that allows to seek to a specific byte offset in the file.

My initial thought would be to use a CipherInputStream with a Cipher initialized with the right parameters, but the API for that doesn't do seeking and states to not support mark and reset.

Is there a part of the API that I've missed that can do this for me, should I look into the configuration of CTR's IV/block counter and recreate that with a custom input stream (which sounds like shotgun aimed at self to me) or take some other approach I've missed?

Sharla

Answer 1

I ended up looking up exactly how the IV is updated in CTR mode. This turns out to do a simple +1 for each AES block it processes. I implemented reading along the following lines.

Given a class that implements a read-like method that would read the next byte in a byte sequence that is encrypted and needs to support seeking in that sequence and the following variables:

• BLOCK_SIZE: fixed at 16 (128 bits, AES block size);
• cipher: an instance of javax.crypto.Cipher, initialized to deal with AES;
• delegate: a java.io.InputStream that wraps an encrypted resource that allows random access;
• input: a javax.crypto.CipherInputStream we'll be serving reads from (the stream will take care of the decryption).

The seek method is implemented as such:

void seek(long pos) {
    // calculate the block number that contains the byte we need to seek to
    long block = pos / BLOCK_SIZE;
    // allocate a 16-byte buffer
    ByteBuffer buffer = ByteBuffer.allocate(BLOCK_SIZE);
    // fill the first 12 bytes with the original IV (the iv minus the actual counter value)
    buffer.put(cipher.getIV(), 0, BLOCK_SIZE - 4);
    // set the counter of the IV to the calculated block index + 1 (counter starts at 1)
    buffer.putInt(block + 1);
    IvParameterSpec iv = new IvParameterSpec(buffer.array());
    // re-init the Cipher instance with the new IV
    cipher.init(Cipher.ENCRYPT_MODE, key, iv);
    // seek the delegate wrapper (like seek() in a RandomAccessFile and 
    // recreate the delegate stream to read from the new location)
    // recreate the input stream we're serving reads from
    input = new CipherInputStream(delegate, cipher);
    // next read will be at the block boundary, need to skip some bytes to arrive at pos
    int toSkip = (int) (pos % BLOCK_SIZE);
    byte[] garbage = new byte[toSkip];
    // read bytes into a garbage array for as long as we need (should be max BLOCK_SIZE
    // bytes
    int skipped = input.read(garbage, 0, toSkip);
    while (skipped < toSkip) {
        skipped += input.read(garbage, 0, toSkip - skipped);
    }

    // at this point, the CipherStream is positioned at pos, next read will serve the 
    // plain byte at pos
}

Note that seeking the delegate resource is omitted here, as this depends on what is underneath the delegate InputStream. Also note that the initial IV is required to be started at counter 1 (the last 4 bytes).

Unittests show that this approach works (performance benchmarks will be done at some point in the future :)).

Sharla

The counter in CTR should be initialized to 0, if it ever rolls over there is the possibility that the same key is going to be reused with the same nonce || CTR value which is catastrophic for security. You should be rekeying before that happens. – Outmoded

You're right, I've changed my implementation a bit in the mean time to actually conform to the spec (not sure why I didn't find/go for that in the first place...) – Sharla

Hmm, won't let me edit the comment anymore. A link to the buildup of the IV according to the spec. – Sharla

according to my observation, Oracle JDK takes whole IV byte sequence as a big integer, but not just trailing 32 bit integer. <pre> byte[] ivBytes = new byte[16]; Arrays.fill(ivBytes, (byte)-1); IvParameterSpec iv = new IvParameterSpec(ivBytes); cipher.init(Cipher.ENCRYPT_MODE, key, iv); cipher.update(new byte[16]); byte[] o2 = cipher.update(new byte[16]); Arrays.fill(ivBytes, (byte)0); iv = new IvParameterSpec(ivBytes); cipher.init(Cipher.ENCRYPT_MODE, key, iv); byte[] o3 = cipher.update(new byte[16]); Assert.assertArrayEquals(o2, o3); </pre> – Pout

After months of going round and round, I think I finally grasp what was done here. I really wanted to understand rather than just ask. Anyway, I notice in the code, you said counter starts at 1, but the comment by X-Istence mentions to initialize it to 0. Am I missing something, or the code is right? – Nalley

From a purely functional point of view the difference does not matter, as long as you initialize it in the same way it was encrypted with. I'm unsure what the cryptographic significance is of starting at a specific counter (see also @fishautumn's comment on what the Oracle JDK does). All of this aside, please note that I'm hardly a crypto expert; review and audit everything you do surrounding encryption thoroughly, badly implemented crypto is often more harmful than operating in the plain ;) – Sharla

> // set the counter of the IV to the calculated block index + 1 (counter starts at 1) This is incorrect. The IV is the counter not just it's last four bytes. See example from @Pout > The counter in CTR should be initialized to 0 This is incorrect. Regardless of your starting value in [0 .. 2^128 - 1], you will reuse it exactly after 2^128 steps. – Brettbretz