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.
