Is it possible to decipher at random position with nodejs crypto?

Question

My understanding is that an AES block cipher in CTR mode allows, in theory, to decipher any location of a large file, without needing to read the whole file.

However, I don't see how to do this with nodejs crypto module. I could feed the Decipher.update method with dummy blocks until I get to the part I'm interested in, at which point I would feed actual data read from the file, but that would be an awful hack, inefficient, and fragile, since I need to be aware of the block size.

Is there a way to do it with the crypto module, and if not, what module can I use?

Answer 1

Original Increment Function

NodeJS uses OpenSSL under the hood and the code for CTR mode can be found here: ctr128.c implementation An equivalent function in Node.js might look like this:

function ctr128Inc(counter) {
    let c = 1;
    let n = 16;

    do {
        n -= 1;
        c += counter[n];
        counter[n] = c & 0xFF;
        c = c >> 8;
    } while (n);
}

This function increments the counter by one block. To increment by multiple blocks, you might wrap it as follows:

function incrementIVOpenSSL(iv, increment) {
    for (let i = 0; i < increment; i++)
        ctr128Inc(iv)
}

However, this method is inefficient for large increments due to its linear time complexity and is practically unusable in real-world applications.

Readable and Efficient Version Using BigInt

Node.js introduces the BigInt type, which can handle arbitrarily large integers efficiently. We can utilize it to increment the IV by converting the IV buffer to a BigInt, performing the increment, and converting it back to a Buffer:

const IV_MAX = 0xffffffffffffffffffffffffffffffffn;
const IV_OVERFLOW_MODULO = IV_MAX + 1n;

function incrementIvByFullBlocks(originalIv: Buffer, fullBlocksToIncrement: bigint): Buffer {
    let ivBigInt = bufferToBigInt(originalIv);

    ivBigInt += fullBlocksToIncrement;

    if (ivBigInt > IV_MAX)
        ivBigInt %= IV_OVERFLOW_MODULO;

    return bigIntToBuffer(ivBigInt);
}

function bufferToBigInt(buffer: Buffer): bigint {
    const hexedBuffer = buffer.toString(`hex`);
    return BigInt(`0x${hexedBuffer}`);
}

function bigIntToBuffer(bigInt: bigint): Buffer {
    const hexedBigInt = bigInt.toString(16).padStart(32, `0`);
    return Buffer.from(hexedBigInt, `hex`);
}

Only this method isn't as fast as the one proposed by @youen. On my PC, for 100k iterations, @youn's method finishes in 15ms and BigInt version in 90ms. It is not a big difference though and BigInt version is by far more obvious for a reader.

Alternative Implementations and Performance Comparison

Another implementation can be found in the crypto-aes-ctr library. It performs the increment operation more quickly (~7ms for 100,000 iterations) but sacrifices readability. It also supports more edge cases, mostly connected with incrementing IV by very big numbers. Something that probably won't be the case in real-life scenarios for a very long time (until we switch to Petabytes drives). For a detailed comparison refer to my GitHub gist. The BigInt method and the OpenSSL-inspired function are the only ones passing all edge case tests, with the BigInt approach offering a good balance between performance and readability.

Introducing aes-ctr-concurrent

To simplify the process and enhance performance in concurrent environments, I've developed the aes-ctr-concurrent library, available on NPM. This library:

• Wraps Node.js's crypto module.
• Adjust the IV to start encryption/decryption at any byte position, not just on block boundaries.
• Supports efficient encryption and decryption of data streams in concurrent applications.

Answer 2

I've found different approaches to solve this problem:

Method 1 : CTR mode

This answer is based on @ArtjomB. and @gusto2 comments and answer, which really gave me the solution. However, here is a new answer with a working code sample, which also shows implementation details (for example the IV must be incremented as a Big Endian number).

The idea is simple: to decrypt starting at an offset of n blocks, you just increment the IV by n. Each block is 16 bytes.

import crypto = require('crypto');
let key = crypto.randomBytes(16);
let iv = crypto.randomBytes(16);

let message = 'Hello world! This is test message, designed to be encrypted and then decrypted';
let messageBytes = Buffer.from(message, 'utf8');
console.log('       clear text: ' + message);

let cipher = crypto.createCipheriv('aes-128-ctr', key, iv);
let cipherText = cipher.update(messageBytes);
cipherText = Buffer.concat([cipherText, cipher.final()]);

// this is the interesting part: we just increment the IV, as if it was a big 128bits unsigned integer. The IV is now valid for decrypting block n°2, which corresponds to byte offset 32
incrementIV(iv, 2); // set counter to 2

let decipher = crypto.createDecipheriv('aes-128-ctr', key, iv);
let decrypted = decipher.update(cipherText.slice(32)); // we slice the cipherText to start at byte 32
decrypted = Buffer.concat([decrypted, decipher.final()]);
let decryptedMessage = decrypted.toString('utf8');
console.log('decrypted message: ' + decryptedMessage);

This program will print:

       clear text: Hello world! This is test message, designed to be encrypted and then decrypted
decrypted message: e, designed to be encrypted and then decrypted

As expected, the decrypted message is shifted by 32 bytes.

And finally, here is the incrementIV implementation:

function incrementIV(iv: Buffer, increment: number) {
    if(iv.length !== 16) throw new Error('Only implemented for 16 bytes IV');

    const MAX_UINT32 = 0xFFFFFFFF;
    let incrementBig = ~~(increment / MAX_UINT32);
    let incrementLittle = (increment % MAX_UINT32) - incrementBig;

    // split the 128bits IV in 4 numbers, 32bits each
    let overflow = 0;
    for(let idx = 0; idx < 4; ++idx) {
        let num = iv.readUInt32BE(12 - idx*4);

        let inc = overflow;
        if(idx == 0) inc += incrementLittle;
        if(idx == 1) inc += incrementBig;

        num += inc;

        let numBig = ~~(num / MAX_UINT32);
        let numLittle = (num % MAX_UINT32) - numBig;
        overflow = numBig;

        iv.writeUInt32BE(numLittle, 12 - idx*4);
    }
}

Method 2 : CBC mode

Since CBC uses the previous cipher text block as IV, and that all cipher text blocks are known during the decryption stage, you don't have anything particular to do, you can decrypt at any point of the stream. The only thing is that the first block you decrypt will be garbage, but the next ones will be fine. So you just need to start one block before the part you actually want to decrypt.

Answer 3

I could feed the Decipher.update method with dummy blocks until I get to the part I'm interested in

As @Artjom already commented, assuming using CTR mode, you don't need to feed start of the file or any dummy blocks. You can directly feed ciphertext you are interested in. (starting the blocksize of 128 bit using AES)

see the CTR mode of operation, you just need to set the IV counter to the starting block of the ciphertext, feed only part of the encrypted file you want to decipher (you may need to feed dummy bytes of the starting block if needed)

Example:

you need to decrypt a file from position 1048577, using AES it's block 65536 (1048577/16) plus 1 byte. So you set the IV to nonce|65536, decrypt dummy 1 byte (to move to position to 16*65536+1) and then you can just feed your ciphertext from the part of the file you are interested in