# Adding a number congruent to $0$ to ensure that the mod operation takes a constant number of instruction cycles

I've been looking at the s2n implementation of HMAC, and in the update' function (line 175), it says

/* Keep track of how much of the current hash block is full
*
* Why the 4294949760 constant in this code? 4294949760 is the highest 32-bit
* value that is congruent to 0 modulo all of our HMAC block sizes, that is also
* at least 16k smaller than 2^32. It therefore has no effect on the mathematical
* result, and no valid record size can cause it to overflow.
*
* The value was found with the following python code;
*
* x = (2 ** 32) - (2 ** 14)
* while True:
*   if x % 40 | x % 48 | x % 64 | x % 128 == 0:
*     break
*   x -= 1
* print x
*
* What it does do however is ensure that the mod operation takes a
* constant number of instruction cycles, regardless of the size of the
* input. On some platforms, including Intel, the operation can take a
* smaller number of cycles if the input is "small".
*/


It then goes on to do

state->currently_in_hash_block += (4294949760 + size) % state->hash_block_size;
state->currently_in_hash_block %= state->block_size;


I don't understand why you would want to add a number that's congruent to zero modulo state->hash_block_size - what does it achieve? How does it guarantee a constant number of instruction cycles?

• While I have to appreciate the neat hack, it's pretty ridiculous. There is no guarantee of a constant number of cycles afterwards in general (some architecture can still do something crazy). And there does not seem to be any reason to hide the number considering it is the data length that will likely leak due to the data being copied over anyway.
– otus
Aug 30 '16 at 15:11
• @otus: well, if we're talking about the time taken to integrity-check a padded TLS record, there is a potential side channel attack based on the amount of data HMAC'ed (which would indicate the amount of padding); the entire record is encrypted, and so the attacker can't find that directly. That said, this implementation doesn't appear to hide the number of times the hash compression function was evaluated, and so there's a much bigger gap left open. Aug 30 '16 at 18:43

As the comment you quote notes:

On some platforms, including Intel, the [modulo] operation can take a smaller number of cycles if the input is "small".

Is that really true, and what does that mean? A bit of Googling led me to the Intel® 64 and IA-32 Architectures Optimization Reference Manual, which in table C-16 lists the throughput of the DIV instruction (which is used to compute both division and modulo) as "~20-26" cycles per instruction (~19-25 cycles on Ivy Bridge), with the following footnote:

1. The throughput of “DIV/IDIV r32” varies with the number of significant digits in the input EDX:EAX and/or of the quotient of the division for a given size of significant bits in the divisor r32. The throughput decreases (increasing numerical value in cycles) with increasing number of significant bits in the input EDX:EAX or the output quotient. The latency of “DIV/IDIV r32” also varies with the significant bits of the input values. For a given set of input values, the latency is about the same as the throughput in cycles.

So what does that mean in plain English?

• Integer division and modular reduction are not constant-time operations on Intel x86 CPUs.
• The time taken to divide or reduce a number depends (mainly?) on the bit length of the number being divided or reduced.

Thus, the time needed to calculate x % y can leak information about the size of x. However, we can minimize this leakage by instead calculating (x + c) % y, where c is a large constant multiple of y. In particular, the constant c should be chosen so that:

1. the bit length of x + c is the same for all possible values of x,
2. the calculation of x + c cannot overflow for any possible value of x, and
3. of course, c needs to be divisible by the modulus y.

Depending on the range of possible x values, of course, it may not always be possible to find a constant c that would satisfy these requirements.

In the code you quote above, however, the constant 4294949760 appears to have been chosen as the largest value c that will not overflow a 32-bit unsigned register when added to any number 0 ≤ x < 214, and which is also an integer multiple of the possible moduli 40, 48, 64 and 128. Given that 4294949760 ≥ 231, this also ensures that it satisfies the first condition: bitlength(4294949760 + x) = 32 for all 0 ≤ x < 214.

• Much more precise answer than mine. Aug 31 '16 at 8:59

I assume that this is because the mod operation must now always be performed. If the input $x$ to the modulus operator can be shown to always be smaller than $n$ in specific situations then the modulus calculation can be skipped because in that case $x \bmod n = x$. The time difference between skipping and non-skipping could be abused for a timing based side channel attack.

I am quite sure that this would not guarantee a number of cycles. Firstly, it is in python. Secondly, they elude to Intel, and that architecture is particularly poor at this specific operation and there are a lot of flavors that all behave a little differently. Here's an assembly example:

mov dx, 0
mov ax, 1234
mov bx, 10
div bx       ; Divides 1234 by 10. DX = 4 and AX = 123
`

The div instruction on x86 takes between 4 and 181 cycles; however, the issue I see is that you have instruction execution times based on the width of both registers, so even if you have a small value on one side, that 4294949760 value will most likely make it take 40 cycles. This means that wether you use the small value or the large value, it takes 40 cycles.

The answer seems to be: it takes 40 cycles, but not for the reason that the author thought. If the author actually kept of an 8 bit division, it'd take 24 or less.

• The calculation to get the number 4294949760 is in python, not the protected calculation itself, if I understood correctly. Aug 30 '16 at 11:36
• still, there's no way to make a general statement on cycle time on 1) x86 and 2) an interpreted language, without hardware and software information. it could be correct but I its more likely not. someone with a python debugger could answer for sure, but the x86 target is more important. Aug 30 '16 at 11:43
• s2n itself points to a c language implementation. Aug 30 '16 at 11:48
• even in C, I cannot guarantee how many cycles div as an assembly instruction will take in a general case because it is completely dependent on the CPU core. It's a shame that SPARC/POWER didn't take over the world because between the flavors of Intel and AMD, you really cannot count on anything taking the same amount of time. Here's an overview: agner.org/optimize/instruction_tables.pdf Aug 30 '16 at 12:17
• I think your answer is technically correct in itself, but currently it it isn't synchronized with the question. Instead of commenting, you're probably better off amending the answer... Aug 30 '16 at 12:52