The Side Channel

J.D.

2:30 AM

@EllaRose - I am unclear on the different design you are thinking of. Could you explain further? "4 x 32 bit" doesn't quite make sense to me in the context of MDS matrices and active byte-sized s-boxes.

Ella Rose

sure. Basically, my state consists of 4 fours

each of which is 32 bits long

I have a 4x4 s-box that is applied on each 4 bit tall, 1 bit wide column

(32 times in parallel)

my linear column mixing function mixes each 4 bit tall, 1 bit wide column

then, each of the second, third, and fourth rows are shifted by varying amounts

I apologize for the linked implementation; It is actually computing 4 of those states at once, so is probably not a good reference

hrmm, that first sentence was supposed to say "...state consists of 4 words"

so I don't have byte sized s-boxes

I don't know if MDS matrices are applicable/at use in my design (I'm not such a math buff, I only sort of know what an MDS matrix is)

but basically, in my design, worst case scenario requires 2 applications of the linear mixing layer to cause full diffusion

and I was wondering if it was advantageous to apply the non-linear s-box layer every full diffusion, instead of every half diffusion

J.D.

Wait, are you saying the linear mixing function mixes the same four bits as those that are passed through the 4 x 4 s-box?

Ella Rose

sub bytes -> mix columns -> shift rows -> mix columns -> shift rows -> mix columns -> shift rows

that is one round in my design

(it takes that many shifts to propagate changes to the left of the words)

so the experiment is to do instead:

sub bytes -> mix columns -> shift rows -> mix columns -> shift rows -> mix columns -> shift rows -> mix columns -> shift rows -> mix columns -> shift rows -> mix columns -> shift rows

Instead of putting another sub bytes in the middle there

if that makes any sense at all?

I appreciate your time immensely, by the way

J.D.

To clarify, let's number each bit with 0 to 127, so first row/word is 0, 1, 2, ...31, second row is bits 32 to 63, third row is 64 to 95, then fourth row is bits 96 to 127. Which bits go into a single instance of the s-box? Is it like Serpent - i.e. bits 0, 32, 64 and 96 go together into a single s-box? If so, then which bits go into the mixcolumns function? The same four bits?

Ella Rose

yes, that appears to be accurate

mix columns and the s-box both operate on 4-bit tall, 1-bit wide columns

and they do so in parallel, because it's bitsliced (like Serpent)

J.D.

2:48 AM

Well, first off you don't need that first mix columns, because the s-box mixes those four bits together better than a linear function could hope to do. Second, the concept of MDS doesn't really apply to a 4 x 4 bit matrix. There is a related bitwise concept, and it is possible to have matrices with minimum lower bounds on the number of active bits.

But it's sort of a different animal than the bytewise approach used in AES. There's a cipher that uses a linear matrix based on the bitwise branch number, but for the life of me I can't remember what it is called . . .

Ella Rose

ahh, hrmm I have that variant already actually

one that foregoes the linear column mixer and just utilizes the sub bytes one to do the job

It kind of trips me up that it applies the substitution and branching in the same step though

J.D.

Well, to be clear I was saying just that 1st mix columns step is not necessary. I wasn't saying anything about not needing the other mix columns steps that you describe . .

Ella Rose

basically, the other design renames sub bytes to mix columns

and just throws out the linear mix columns operation entirely

is that bad?

sorry, I guess we're getting into more questions then you bargained for here

I could go on forever, don't mind me

J.D.

By the way, if you are having difficulties with the concept of MDS matrices, I can recommend a paper: On the Need for Multipermutations, by Vaudenay (citeseerx.ist.psu.edu/viewdoc/…) It's an older paper that basically introduced the idea of using MDS matrices for crypto (though it uses the somewhat clearer term "multipermutation" instead of MDS).

Ella Rose

thank you! :)

J.D.

2:55 AM

Reading that paper made MDS so much clearer to me. Maybe it will for you too.

I think that's the paper. Sometimes it's hard to remember which paper was the one that clarified things . . .

Anyway, you can't have a bitwise multipermutation because there is just one bitwise permutation (the identity function), and a square matrix with every bit set to one (which is necessary for every single bit 'submatrix' to be a permutation) is not a permutation. Hopefully this will be clearer once you have read the paper . . .

Ella Rose

hrmm, what do you mean by bitwise permutation? or should I just continue reading

if being multipermutation implies perfect diffusion, does that mean we can't have bitwise functions with perfect diffusion? That sounds like I am interpreting something wrong

J.D.

i.e. if you have a single bit, how many permutations can you apply to it. I actually mispoke - there are two possible permutations - the identity function and the complementation function. i.e. 0,1 becomes 0,1 (identity) and 0,1 becomes 1,0 (the bit is complemented).

Ella Rose

ahhhh

now that makes sense

J.D.

No, the paper is talking about perfect diffusion in the sense that every byte is a function of every other byte. Not every bit is a function of every other bit.

Ella Rose

oh I see

J.D.

3:09 AM

Anyway, I am getting tired. Give the paper a read and if you have questions about MDS matrices you can ask them in the main stackexchange. But I wouldn't feel too bad about having difficulties lower bounding the number of active s-boxes in bitslices Serpent-like designs - that is a nontrivial problem.

Ella Rose

alrighty, thank you for everything. I hope you have pleasant dreams!

J.D.

Night.

CurveEnthusiast

8:16 AM

@Evinda That algorithm looks correct! Note that div_rem(n,2) = n >> 1. So that is actually really cheap. I think you have to be careful with your big-$O$ notation. A multiplication is a single group operation, so it is $O(1)$ if we measure the complexity as the number of group operations. If we measure it with respect to a different metric, it could have different big-$O$ complexity.

Also, I'm not claiming this is the most efficient way to do your computation. I'm saying this way it's easy to directly count the number of group operations you need, since the repeated-squaring algorithm shows you that you need at most $2\log N$.

Transcript for