Stream slicing operation in block cipher and side-channel attack

Question

My symmetric block cipher works kind of like a stream cipher, but it works on $128$-bit blocks. It generates a $128$-bit block in every round. And at the end of the round, I have to slice it into two blocks and add them together. I mean after each round we take first $a$ bits and second $b$ bits of $128$-bit block and then compute $b+a$. $a$ is equal to $0$ to $127$, it is computed from the key schedule and should be indistinguishable from random. But such slicing can be attacked by the side-channel attack. Attacker can find $a_{0}$, $a_{1}$, $a_{2}$ and so on for every round.

But my cipher works like a stream cipher. That means it computes bit by bit in steps and then combines them into a block. Normally I'm making $128$-bit block with this, for $i$ in the range $0-127$:

$ct=0$

$ct=ct+bitv$

$bitv$ is a bit value $0$ or $1$ and it comes from cipher function. We are just making some binary string/block here. My idea is to not slicing block in the end but first compute first $a$ bits like a string for $i$ in the range $0-a$, where $a$ is some indistinguishable from a random number from the key schedule:

1. $a=a+btiv$

and then compute the rest of the string for $i$ in range $a+1-127$ as:

2. $ct = ct + bitv + a$

Anyway, we still have to make for example two loops "for". First for $i$ in range $0-a$ and second in range $a+1-127$ inside the round. Is it possible to attack it by the side-channel attack? Can the attacker detect when the first loop will end and the second will start and then find $a$?

Answer 1

The key schedule should be considered secret. Your side channel reveals the key schedule. Even if your key schedule is indistinguishable from random an attacker can usually still derive the key. Since your key schedule is the same as your encryption algorithm it would be inherently vulnerable to the same attacks as your encryption. Even if it isn't, your key schedule probably still isn't a secure hashing algorithm and therefore the original key can even be obtained.

Most (all) modes of operation are broken even if only the key schedule is revealed but not the key. Some are (slightly) less broken than others.

Side-channels are enabled by any data-dependent memory accesses. Even if the total number of memory accesses is constant, this cannot be assumed to provide security. If I perform some computation on bits $1,...,a$ and I perform another (possibly the same) computation on bits $a+1,...,128$ I've just performed a different pattern of memory accesses, and revealed the value of $a$ (which is nearly impossible to fix in implementation). Nevermind the fact that for loops require an if statement to tell when to break (the compiler adds it implicitly). That means that you've allowed cache-timing, branch-prediction, and branch-timing attacks.

On the impact of various side-channels

• Cache-timing is fixable in hardware that doesn't cache memory. Memory caching exists in all major architectures, and can't really by bypassed or disabled.
• Branch-prediction (also known as speculative execution) only exists in hardware that tries to predict branching. This behavior exists in all major architectures, and can't be bypassed.
• Branch-timing attacks, however, are hardware-agnostic and will affect every system identically... For this reason these are among the worst of all side-channels.

All side-channel attacks, even if hardware-dependent, are considered crippling to a secure cryptographic implementation.