2
$\begingroup$

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$).

|improve this question
$\endgroup$
  • $\begingroup$ Ella's answer is good but in case you just want to know if this can be implemented in constant time: The answer is Yes! $\endgroup$ – Elias Jan 18 '18 at 22:53
  • 1
    $\begingroup$ Why was this question downvoted? $\endgroup$ – Melab Jan 18 '18 at 23:07
  • $\begingroup$ @EllaRose $2^{3} = 8$, so $N$ is $8$ bits long to cover all possible inputs. $\endgroup$ – Melab Jan 18 '18 at 23:08
  • $\begingroup$ @EllaRose You are correct. $\endgroup$ – Melab Jan 18 '18 at 23:16
  • 1
    $\begingroup$ @Melab because it doesn't describe an actual implementation of anything. Even "using a bitwise shift followed by a bitwise AND (with the value 1)" is still not an implementation. $\endgroup$ – OrangeDog Jan 19 '18 at 15:34
13
$\begingroup$

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.

|improve this answer
$\endgroup$
  • $\begingroup$ It works like the non-linear lookup table in KeeLoq. $\endgroup$ – Melab Jan 18 '18 at 22:53
  • $\begingroup$ If your definition of "constant time" is the commonly used one, then I can still imagine timing attacks being possible on implementations or designs usually described as "constant time". $\endgroup$ – Melab Jan 18 '18 at 22:57
  • $\begingroup$ @Melab Assuming that the time taken is independent of secret data, then what information would your imagined timing attacks recover? $\endgroup$ – Ella Rose♦ Jan 18 '18 at 23:07
  • $\begingroup$ Would a function $F(K, X): \{0, 1\}^{k} \times \{0, 1\}^{x} \rightarrow \{0, 1\}^{y}$, where $K$ is a secret key and $X$ is the data, that takes different amounts of time to execute for different values of $X$ but not for different values of $K$ be said to run in constant time? $\endgroup$ – Melab Jan 18 '18 at 23:15
  • 2
    $\begingroup$ @Melab Since you do not prefix "secret" to the word "data",but you do for the word "key", I assume that "data" is not secret. For example, "data" could be a boolean configuration flag that is named "save_to_disk_or_not", which when true dumps the output to disk, and when false does not do so; In this case, the two possible branches would take drastically different amounts of time, but there is no problem with this from the point of view of cryptography. This is just an example to highlight the point: Branching on non-secret data is not much of an issue. $\endgroup$ – Ella Rose♦ Jan 18 '18 at 23:18
5
$\begingroup$

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).

|improve this answer
$\endgroup$
  • $\begingroup$ Is there a way to implement it in software that is always constant regardless of the platform? $\endgroup$ – Melab Jan 19 '18 at 2:31
  • $\begingroup$ Will you expand on the definition of a generic $n\rightarrow 1$ function? $\endgroup$ – Q-Club Jan 19 '18 at 7:53
  • $\begingroup$ @Melab There is probably no way at all to implement it cross platform in constant time. As soon as you involve some sort of compiler the compiler might screw up your constant time requirements. $\endgroup$ – Elias Jan 19 '18 at 8:17
4
$\begingroup$

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.

|improve this answer
$\endgroup$
  • $\begingroup$ @Q-Club: If that's now good enough, I suggest that you remove your comment; I'll do the same for mine. You could also add a new one asking for further clarification. $\endgroup$ – fgrieu Jan 19 '18 at 11:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.