Suggestion: incrementTimingSafe(final byte[] bytes, final int offset, final int length)

[Andrew-Cottrell]

I recently wrote the following methods and thought they could be added to the bytes-java library if it is believed that they might be useful to other people.

    /**
     * Increments a big-endian integer embedded in a byte array.
     * @param bytes The byte array embedding an integer.
     * @param offset The offset of the integer in bytes.
     * @param length The length of the integer in bytes.
     * @throws IndexOutOfBoundsException If the offset and/or length are invalid.
     */
    static void incrementTimingSafe(final byte[] bytes, final int offset, final int length) {

        /* The `carry` starts at 1 and may transition to 0. */
        int carry = 1;

        /* Always loop through every value in range without a break or early return. */
        for (int index = offset + length - 1; index >= offset; index--) {
            /* Increment every value in range by either 1 or 0. */
            final byte value = bytes[index];
            final int unsigned = value & 0xFF;
            final int sum = unsigned + carry;
            bytes[index] = (byte) sum;
            /* Set `carry` to 1 if `sum` overflowed, otherwise set to 0. */
            carry = sum >> 8;
        }
    }

    /**
     * Increments a big-endian integer represented by a byte array.
     * @param bytes The byte array representing a integer.
     */
    static void incrementTimingSafe(final byte[] bytes) {
        incrementTimingSafe(bytes, 0, bytes.length);
    }

This implementation is intended to be timing-safe to mitigate timing attacks. It is impossible to accurately predict how the JVM may compile the code or how the CPU's branch predictor may change timings. However, OpenJDK 11.0.6_10 compiles this method to machine code that is branch-free within the for-loop body.

For example, once compiled using OpenJDK 11.0.6_10, the for-loop body disassembles to the following assembly:

movsx   edi,byte ptr [rdx+rdi+10h] ; final byte value = bytes[index];
and     edi,0ffh                   ; final int unsigned = value & 0xFF;
add     edi,esi                    ; final int sum = unsigned + carry;
mov     rsi,rdi                    ; move sum to rsi
movsxd  rbx,r9d                    ; rbx = index
mov     byte ptr [rdx+rbx+10h],sil ; bytes[index] = (byte) sum;
sar     edi,8h                     ; carry = sum >> 8;
dec     r9d                        ; index = index - 1
mov     rsi,rdi                    ; move carry to rsi

My use case involves incrementing an 11-byte integer embedded within a 12-byte initialization vector source buffer, but I expect these methods may be useful for other use cases. They could be exposed like Bytes.equalsConstantTime(byte[]), which is backed by Util.Byte.constantTimeEquals(byte[], byte[]).

In cryptography, "constant-time" often means "timing-safe" rather than referring to constant time complexity. I prefer the term "timing-safe", rather than "constant-time", because the algorithm has linear time complexity with respect to the length of the embedded number. However, the methods could be named incrementConstantTime for consistency with equalsConstantTime.

Please close this issue if the suggested methods are not thought to be appropriate for the bytes-java library.