9
$\begingroup$

This could be a question for CodeReview.SE, but I thought it might require non-trivial cryptographic knowledge to merit it on-topic here.

The C language is chosen as it's a common language for implementing cryptographic algorithms. Also, as we're choosing C, the primary platforms under consideration are PCs, smart devices such as cellphones, tablets, and TVs, and servers.

Arbitrary s-box may be required when designing products for sale in jurisdictions that mandates local cryptography standards such as SM4, Camellia, SEED in China, Japan, and South Korea.

Here's my attempt at reducing side-channel when implementing arbitrary s-box. To the best of my knowledge, it's now constant-time, but

Q: how should other side-channel attacks such as fault attack and electromagnetic detector in proximity etc. be prevented?

#include <stdint.h>

const extern uint8_t sbox_table[256];

uint8_t sbox(uint8_t x)
{
    int i;
    uint8_t ret = 0;
    uint16_t mask = 0;

    for(i=0; i<256; i++)
    {
        mask = i ^ x;
        mask = (mask - 1) >> 8;
        ret |= sbox_table[i] & mask;
    }

    return ret;
}

uint8_t invsbox(uint8_t x)
{
    int i;
    uint8_t ret = 0;
    uint16_t mask = 0;

    for(i=0; i<256; i++)
    {
        mask = sbox_table[i] ^ x;
        mask = (mask - 1) >> 8;
        ret |= i & mask;
    }

    return ret;
}
$\endgroup$
11
  • 2
    $\begingroup$ Also yes, this question is on-topic thanks to our "side channels and their countermeasures" exception for code-related tasks. $\endgroup$
    – SEJPM
    Commented Jul 20, 2020 at 13:13
  • 2
    $\begingroup$ @bdegnan: actually, all memory accesses here are independent of the value $x$, hence whether a memory access is a hit or miss does not leak any information about $x$. $\endgroup$
    – poncho
    Commented Jul 20, 2020 at 18:02
  • 1
    $\begingroup$ Regarding "arbitrary S-box", note that both SM4 and Camellia have S-boxes that can be calculated in terms of AES's S-boxes if you have hardware capable of AES (x86 AES-NI, ARMv8). $\endgroup$
    – Myria
    Commented Jul 20, 2020 at 18:32
  • 5
    $\begingroup$ Note that C does not guarantee the above code will be constant time: execution time is not considered an observable effect by the C standard, so NO code can be guaranteed to be constant time if written in C. It almost certainly is in practice, but compilers don't make any attempt to enforce this (or any other side-channel resistance). $\endgroup$ Commented Jul 20, 2020 at 19:23
  • 1
    $\begingroup$ Note that to achieve constant timing BearSSL uses BitSlicing $\endgroup$
    – kelalaka
    Commented Jul 20, 2020 at 19:37

2 Answers 2

1
$\begingroup$

I've seen that a C-compiler for an 8-bit platform translated x++ for an uint16_t x to (1) incrementing the low byte of x, (2) branch skipping the next command if the result of incrementing is non-zero, and then (3) incrementing the high byte of x (unless we branched).

If your "(mask - 1)" is compiled in the same glorious way by that C-compiler, your loops will be in total constant time, but the round where x=i will take longer than the other rounds on that platform.

So the way to go is bit-slicing, as already suggested by kelalaka in the comments.

$\endgroup$
1
$\begingroup$

This question has already been answered in the comments.

First of all, from my experience there isn't such thing as creating a side-channel attack free implementation because this is the concept of side channel attacks, e.g. using unordinary information that are generated by an implementation that was previously considered useless.

Jumping to your code, which is at least secure against cache timing attacks, the comment from SAI Peregrinus holds :

Note that C does not guarantee the above code will be constant time: execution time is not considered an observable effect by the C standard, so NO code can be guaranteed to be constant time if written in C. It almost certainly is in practice, but compilers don't make any attempt to enforce this (or any other side-channel resistance).

As mentioned by poncho, in your code the memory accesses are independent from the value to look up, x. This doesn't guarantee constant time execution since the sbox_table will be stored in memory and cache misses will also probably take place. The BitSlicing technique used in BearSSL mentioned by kelalaka offers constant time execution. This technique is just a software implementation of a Boolean circuit that calculates the sbox. Even in its plain form of BitSlicing used in BearSSL I suspect it will be faster than your technique, check this post to see why. Also if implemented appropriately using xmm registers it may also multiple simultaneous sbox lookups and offer extra speedup according to this paper. In terms of security, both techniques offer no information about the x value with respect to the time of execution.

Now, speaking more generally about side channel attacks. This short paper, in my opinion provides a brief overview of common side channel attacks and their mitigations. There are many more side channel attacks than fault and electromagnetic attack where I don't think all of them can be mitigated using only software.

A few last words referring to your question, I don't think one can claim that your implementation is fully secure against EM based solely on the software since it is really depends on if hardware implements any optimization techniques that will reveal information or if it implements any mitigation techniques. Now, for the fault attack, I don't see any blatant flaws (e.g a branch depending on a single bit or something). But again fault attacks cover a really broad range of attacks and I think it is impossible to say that an implementation mitigates a large part of them.

$\endgroup$
3
  • $\begingroup$ "This technique is just a software implementation of a Boolean circuit that calculates the sbox."; DannyNiu asked for something that would allow the computation of an arbitrary sbox; unless you give a process to convert an arbitrary sbox into a boolean circuit, your response doesn't answer the question. $\endgroup$
    – poncho
    Commented Dec 1, 2022 at 21:29
  • $\begingroup$ @poncho BitSlicing is referenced nowhere in the question. In my opinion his code is correct in mitigating cache timing attacks. BitSlicing is just another way of mitigating cache timing attacks by achieving constant time by executing the whole boolean circuit every time. Now, the problem you mention is solved in the same way that all the MPC and HE boolean circuits are generated. RTL description of the circuit is done in an HDL and it is converted using a synthesis tool to a gate-level netlist. It takes around 5 minutes. The only thing you have to do next is write the appropriate C expressions $\endgroup$
    – tur11ng
    Commented Dec 1, 2022 at 21:46
  • $\begingroup$ @poncho The sbox is actually a lookup table and can be represented by something similar to a switch statement in software. $\endgroup$
    – tur11ng
    Commented Dec 1, 2022 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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