5
$\begingroup$

In recent crypto there has been a trend to design ciphers using only the ARX set of instructions - i.e. additions (modulo $2^{32}$ or $2^{64}$), rotations (by a fixed constant) and XORs, examples include Threefish, Salsa20 and ChaCha20.

One of the nicer, claimed properties of such ciphers is that they are supposedly easier to implement in a side-channel resistant fashion.

Assuming one would want to implement Threefish (on a multitude of architectures such as ARM, x86 and x64), which precautions does one need to take to avoid side-channel attacks for such implementations? And are there any precautions which would be applicable to ARX designs specifically? If, which precautions against side-channel attacks can/should be taken?

What I don't count here: attacks that would work by exploiting unproperly erased/freed memory. I'm looking for the standard cryptographical side channels: cache-timing, "normal" timing and maybe (differential) power (/EM) analysis.

What I would consider "pre-cautions": any code solely intended to defeat side channel attacks while not being documented in the original specification (which usually gives only a mathematical approach).

$\endgroup$
  • 6
    $\begingroup$ Hardware side channels (e.g. power analysis) are possible. $\endgroup$ – CodesInChaos Nov 13 '15 at 21:07
  • $\begingroup$ Without any "pre-cautions", it is highly likely that your implementation is vulnerable to (various) side-channel attacks. The pre-cautions that would be required also depend on the capabilities of your attacker, of course. $\endgroup$ – Aleph Nov 13 '15 at 21:46
  • 1
    $\begingroup$ @Aleph, which pre-cautions and which side-channel attacks? What if I just use my standard x64/x86 assembly / C++ to implement the cipher using adds, minuses, rotates, shifts and XORs while storing all the intermediate variables (except the raw key, tweak and plaintext) in registers (exclusively)? $\endgroup$ – SEJPM Nov 14 '15 at 20:37
  • 2
    $\begingroup$ maybe useful ressource $\endgroup$ – SEJPM Nov 14 '15 at 20:40
  • 1
    $\begingroup$ One example of a possible timing side channel is that addition can take variable time depending on carries. For example, with a very simple CPU carries between words could be implemented with branches or in a high-level language numbers that overflow the word size can get reallocated. $\endgroup$ – otus Nov 15 '15 at 16:39
2
$\begingroup$

Side channels

Essentially, side channels tell something about the secret data by using properties (e.g. timing, power consumption) of the algorithm itself. If an algorithm executes in a different way for different messages/keys, the attacker can deduce information about the message/key from the properties of the execution.

Even if the attacker only gains a little information about the key in one execution, they can do statistical analysis on arbitrary many measurements and thus still get a lot of information.

Where I come from I have learnt that you must assume that the attacker:

  1. Can query the device an arbitrary amount of times with their own chosen messages/ciphertexts.
  2. Knows every instruction (and branch) as they are executed (by using timing attacks/power traces).
  3. Knows the execution time of every instruction (by using timing attacks/power traces).
  4. Knows every address that is looked up during the execution of the algorithm (by using cache timing attacks).

Solution: All crypto algorithms must run deterministically. In other words:

ARX ciphers

ARX ciphers limit themselves to only three basic operations which all run in constant time on pretty much all platforms. Because of their design, there are not really that many precautions to be taken, as long as you adhere to the rules above.

But know that, while you will be ok most of the time, it just really depends on the implementation and on the platform. As Squeamish notes: hardware implementations of ARX ciphers can just as easily be vulnerable against DPA/EM attacks, even if you follow all the rules above.

$\endgroup$
  • 2
    $\begingroup$ This addresses timing side channels in software implementations on general-purpose CPUs, but doesn't address DPA side channels in hardware. ARX ciphers are just as vulnerable to that as anything else, unless you, e.g., compute the complement in parallel. I suggest you refrain from advising ‘you'll be okay’ when the OP specifically mentioned power analysis as a possible threat. $\endgroup$ – Squeamish Ossifrage Aug 13 '17 at 4:32
  • $\begingroup$ Yea. That's a good point. I'll update the answer. $\endgroup$ – dsprenkels Aug 13 '17 at 4:38

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.