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-&gt;currently_in_hash_block += (4294949760 + size) % state-&gt;hash_block_size;
state-&gt;currently_in_hash_block %= state-&gt;block_size;


I don't understand why you would want to add a number that's congruent to zero modulo state-&gt;hash_block_size - what does it achieve? How does it guarantee a constant number of instruction cycles?
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:


  
  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:


the bit length of x + c is the same for all possible values of x,
the calculation of x + c cannot overflow for any possible value of x, and
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 &le; x &lt; 214, and which is also an integer multiple of the possible moduli 40, 48, 64 and 128.  Given that 4294949760 &ge; 231, this also ensures that it satisfies the first condition: bitlength(4294949760 + x) = 32 for all 0 &le; x &lt; 214.