2
$\begingroup$

T-Tables and S-Boxes are prone to side-channel attacks, is an implementation without any lookup tables resistant to side-channel ? In this answer, https://crypto.stackexchange.com/a/63520/80926, the author says that secret-dependent if statements, loops and mathematical operations like multiplications may not be constant time, can they make a side-channel attack possible ? ( On an implementation without any llokup tables ).

If they can, what can we do to have a side-channel resistant implemnetation of AES ? Because it seems that it is much slower than a regular implementation.

Is bitsliced the only solution for a device without AES-NI ?

$\endgroup$
4
$\begingroup$

Is an implementation without any lookup tables resistant to side-channel ?

That's only answerable by no unless it is added some limitation to the attack capabilities of adversaries. No implementation of cryptography involving a secret is resistant to sufficiently advanced side channel-attack. What was resistant a decade ago is no longer now, that's been true for the >3 decades I watched that game (I believe before that), and history will repeat itself, I guess.

Specifically, I'm ready to bet that the first applications to cryptanalysis of the advanced technologies currently developed in quantum computing will be sensitive/fast sensors for side channel-attacks then carried with classical computers.

Secret-dependent if statements, loops and mathematical operations like multiplications may not be constant time, can they make a side-channel attack possible ?

Yes, they have the potential to create a side-channel by timing. But for the AES block cipher, once lookup tables are removed or made constant-time, timing side channels are easily avoided (just don't explicitly test a data or key bit). Other side channels (probing, power analysis, electromagnetic emission), and fault attacks (which are not always classified as side channels, but stand in the same league) are the difficult ones.

Is bitsliced the only solution for a device without AES-NI ?

No. There are security-evaluated AES hardware and even software implementations that do not use bitslicing. Their internal design is typically secret (well-guarded from me, at least), and even their API is under NDA. See this marketing material from a company licensing IP in that field.

And if we restrict to side channels by timing, it is possible to remove theses in software-only AES and keep lookup tables. Fast, simple, secure, portable: pick one, perhaps two.

Can an attack (by side-channel) on an (AES software) implementation without any precomputed tables nor any test on key or data but without any additional security like bitslicing be performed over the network in practice with current technology ?

It depends on what's meant by "attack" and "over the network".

  • No, for attacks aimed at recovering the AES key being used based on timing measurements of network packets. The precautions stated have fully deprived the adversary of information thru that side-channel. It is even doubtful that we really need the "without any precomputed tables" part of the statement for anything else than a simple thus strong argument.
  • Yes, otherwise:
    • Software often ends up using the deciphered data in ways that leak information about that data (not the key under use) thru a timing side channel exploitable by remote timing of network packets. Padding oracle attacks are one class of such attacks. They can reveal a key under transfer.
    • Exploitation of bugs (buffer overflow…) and miss-configuration in the software using the AES implementation under attack is a very real threat.
    • When an adversary accessing the machine "over the network" has or gains the ability to run facilitating code on the machine under attack, we can't rule out a side-channel attack: there's a steady flow of new or slightly different architectural CPU side-channels discovered on CPUs which promised process isolation, even recent ones. And there are even more attacks on OSes and virtualization environments with the net effect of breaching process isolation.

The most secure ways to rule out key leak "over the network" involve not manipulating the key with a general-purpose modern computer¹. Like, keeping keys in a dedicated security device (Smart Card, TPM, HSM). That can give strong insurance against key leak, but not key abuse: it remains possible that an adversary remotely deciphers data enciphered with the key.


¹ I nearly wrote a networked general-purpose modern computer, then went back: there are reports of side-channel attacks that could be carried using a nearby compromised networked computer.

| improve this answer | |
$\endgroup$
  • $\begingroup$ You mean that no implementation can be perfect, can an attack on an implementation without any precomputed tables nor any test on key or data but without any addidtional security like bitslicing be performed over the network in practice with curent technology ? with direct access to the device for a short period (for exemple if someone uses their device outside) ? $\endgroup$ – moutonlapin28 Jun 26 at 21:48
  • $\begingroup$ @moutonlapin28 The enemy knows the system. Do not assume anything to be unknown to the attacker except the key. It is a false assumption for any security argument, if you rely on the fact that the attacker has only limited access to the device or cant test it. Security through obscurity alone is bad. $\endgroup$ – tylo Jun 26 at 23:32
  • $\begingroup$ @tylo By access to the device I mean physically. If you go to a cafe, you won't let someone plug an osiloscope to your laptop and analyse it's electromagnetic emissions. $\endgroup$ – moutonlapin28 Jun 27 at 5:02
  • $\begingroup$ I mean as he said it is imposible avoid every side-channel attacks, but is more protection woth it ? $\endgroup$ – moutonlapin28 Jun 27 at 8:24
  • $\begingroup$ @montonlapin28: the electromagnetic emission of a laptop PC can be observed at a distance compatible with a café (that's radio, just as 3G or wifi, only at a lower level), and is enough to carry some side-channel attacks, possibly including timing attacks. That's a mere extension of TEMPEST / RINT / Van_Eck_phreaking. Long ago, french DSSI reportedly used to tour sensitive companies working for defense with a spectacular demo. $\endgroup$ – fgrieu Jun 29 at 13:11

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.