Does this implementation of a function operate in constant time?

Question

Suppose we have a function that takes $n$ parameters, each being one bit in size, and returns a single bit. Internally, this function has a bit string $N \in \{0, 1\}^{2^n}$ and it operates by using the $n$ inputs to form a pointer to bit $i$ in $N$, where $i$ is equal to the input bits being concatenated and treated as an integer.

As an example, imagine we have $F(a, b, c)$ and $N = 01110001_{2}$. If we have $F(1, 0, 1)$, then the output will be found by retrieving bit $101_{2} = 5$, which would be $1$ (or $0$ if you want the left-most bit to be bit $0$).

Would implementing a function this way run in constant time? If it's implemented in hardware? If it's implemented in software?

Update: I thought it was obvious, but selecting the bits from $N$ would be implemented using a bitwise shift followed by a bitwise AND (with the value $1$).

Answer 1

Would implementing a function this way run in constant time?

This is not an implementation, it is an abstract description of the algorithm.

You need an implementation of the function in an actual programming language (or actual hardware) to determine whether or not it executes in constant time. You can't determine this by the description of the abstract algorithm, as there are (usually) many different possible ways to compute it.

An example of an implementation of the function would be some C code. Note how there are no operators or instructions in your description - an implementation would have a difficult time producing results without processing a series of instructions.

Additionally, the actual platform that you execute the algorithm on can influence whether or not the operation takes a constant amount of time. Even the programming language that you use can make implementing constant-time anything challenging.

Note also: Constant time in regards to cryptography means "time taken is independent of any secret data", as opposed to "takes the same amount of time to execute on all possible inputs".

If you branch on data that is supposed to be secret, you will probably leak information about it via how long it takes the operation to be performed.

Answer 2

Your function $F$ is, in an abstract way, a generic $n\rightarrow 1$ function. As I gather, the implementation you suggest is to have some sort of table or register of outputs for all possible inputs (with $n$ input bits, there are $2^n$ possible input combinations) and then somehow "select" the right one.

There are many ways to implement that, both in software and hardware, and not all of them a "constant-time". For instance, in software, you could spread the $2^n$ bits into so many array cells, and use an array access indexed by the inputs (considered as an integer). Since this would constitute a memory access at an address that depends on secret data, this is not constant-time, and may be vulnerable to cache timing attacks.

Now, on a concrete platform like a modern PC, and if $n$ is sufficiently small, then you could store the $2^n$ possible outputs in a register (this obviously works only if $2^n$ is not larger than the register length on the involved machine), and perform a right shift (>> operator in C, shr opcode in x86 assembly) with the inputs ($n$ bits) as shift count. In general, this should be constant-time, but it depends on the exact CPU. Most CPU include a specific piece of hardware called a "barrel shifter" that performs the shift in one clock cycle, regardless of the shift count. Historically, presence of a barrel shifter was not a given; in particular, the Pentium IV famously had not a barrel shifter, and a right shift by a variable count $x$ would take a time more or less proportional to the value of $x$. The "register shift" implementation strategy would not be constant-time in that case.

In hardware, this is a routing problem: you want to route the right bit from the $2^n$ sequence to the output; the circuit will need to "touch" all $2^n$ bits. It so happens that it can be done with a tree of multiplexers. A multiplexer mux(c,a,b) returns a if c is 0, or b if c is 1. You can then do the following:

• Combine all $2^n$ bits in pairs, with $2^{n-1}$ multiplexers, all using the first input bit as control ("c") bit. This yields $2^{n-1}$ output.

• Combine all these $2^{n-1}$ outputs by pairs, with $2^{n-2}$ multiplexers, all using the second input bit as control bit. You now have $2^{n-2}$ values.

• Iterate. At the end, you have a single multiplexer, that uses the last input bit as control, and produces the result you are looking for.

This implementation as a tree of multiplexer is naturally constant-time, and it is the preferred method for making S-boxes in hardware (e.g. for DES implementations).

Answer 3

It depends on hardware and software, but lacking info about that the prudent answer is no, the implementation won't be constant time. The likely answer is yes in hardware (but see below), and no in software unless the hardware is under tight control and the software written with that in mind.

---

Both in hardware and software, it is reasonably easy to assemble the function's input into an integer index $i$ in constant time, and I'll assume this was done (but see the last three bullets). What remains is fetching the appropriate bit in $N$, at index $i$.

In hardware, it is easy to implement indexed access in $N$ in constant time, and the natural implementation does so: a dedicated ROM for $N$ with $i$ the address (except perhaps some bits of $i$), and if the ROM's output if larger than one bit a multiplexer (with selection from the other bits of $i$) to extract the right bit; with perhaps the whole thing followed by a D-latch to hide propagation delays. One way I can think to accidentally introduce a timing dependency is using a serial memory, which access time can be dependent on the address.

In software, the main causes of timing dependency will be

• Data cache, which will tend to make execution time dependent on if the same index, or a close one, was recently fetched; and (in the affirmative) what software has done in-between these events. On CPUs with data caches (that is, all modern ones with speed as a design goal), it is hard to fix this, and almost impossible to do it portably even in compiled languages like (most variants of) C, C++, Go..; much less in languages with an extra level of abstraction like Java, Python, Javascript, PHP, Lua, .Net languages..
• Shift timing variation: if the bit array $N$ is stored compactly (e.g. as a a vector of octets each holding 8 bits of $N$), after the appropriate octet is obtained as x = N[i>>3], there is need to extract the appropriate bit according to j = i&7. A standard programming idiom for that is computed shift, which shifts the octet x to the right j times, then keeps the low-order bit, with (x>>j)&1. Execution time of the later expression has a fair chance to depend on j on CPUs without a barrel shifter (that tends to be low-end CPUs without a data cache). Contrary to the data cache issue, the shift issue it is reasonably easy to fix in software: replace computed shifts with short tables and constant-time operations (yet, see previous and last bullet).
• Code branches according to inputs, index $i$ or the result, as caused by logical operators like ==, <, unary not !.. That must be avoided, which is relatively easy (yet, see last bullet).
• Multiplication timing variation: on quite a few CPUs, computing x*y takes variable time according to the values of one of the arguments, even when the other is a constant like 2. That could creep somewhere, including the computation of $i$. The solution is to use shifts with constant shift value (yet, see last bullet).
• Compiler-induced code: compilers are generally free to make decisions about how to generate the machine code without consideration of data timing dependency, and that's a real danger. For example, on CPUs with a smaller wordsize than used by the programmer, simple code like addition or shift degenerates into many instructions, occasionally with a data-dependent code branch or instruction. A method to avoid that particular issue is to restrict to data types with native hardware support (that's hard in C on 8-bit CPUs, since the result of any arithmetic operation is nominally at least 16-bit). But the general problem requires coding in assembly; or a compiler with awareness of data-dependent timing issues (so far I have seen such options only spottily for a particular construct); or/and checking the compiler-generated object code, especially after a change of compiler option or version.

Note: I leave aside implementation using a Turing machine or other theoretical construction.