The Side Channel

5:10 AM

Keygen time down to 3ms for 256 bit parameters :3 (Without ciphertext expansion)

...and the assumption is now weaker than it started, and it leads to a more compact ciphertext ($\approx 2\lambda$) expect a whitepaper soon!

Elias

8:26 AM

regarding crypto.stackexchange.com/questions/44157/…

I find it a bit disappointing that we close questions as off-topic that can clearly be answered competently by the people here.

Evinda

10:20 AM

Hey @SEJPM @MickLH
Sorry for my late reply, but I didn't have internet access the last two days.

I wanted to ask if we could also pick some non-linear function F so that the original message cannot be found

MickLH

9

A: Are there any specific requirements for the function $F$ in a Feistel cipher?

Luby and Rackoff published a famous article on that subject (SIAM Journal on Computing, 1988, Vol. 17, No. 2 : pp. 373-386 ). Namely, they showed that if the $F$ functions are pseudorandom, then four rounds are sufficient to achieve security. There are subtle details, though: Each round has it...

Evinda

10:37 AM

Ok. But in the case I am looking at, the number of rounds is 3. What can we say for this case? @MickLH

I got a hint that the function F could contain non-linear parts, say $(x_1, \dots, x_n) \mapsto (x_1 \cdot x_2, x_2, x_3 \cdot x_4, \dots)$. How can we construct such a function in this case, when F is a function of R and k? @MickLH

MickLH

I take it you mean non-linear on $\text{GF}(2)$?

Evinda

Yes

MickLH

Ok that just means use AND gates :P

Evinda

You mean that I should take some product? @MickLH

MickLH

bitwise AND is taking a product in $\text{GF}(2)$

Evinda

10:47 AM

Do we pick for example $F(k,R)=R \cdot k$, i.e. the dot product of R and k? @MickLH

MickLH

What are the domains of those symbols?

Evinda

We have that $k=(k_1,k_2,k_3)$ where $k_i \in \mathbb{F}_2^{4}$ and $L_i=R_{i-1}$ and $R_i=L_{i-1}+F(k_i, R_{i-1})$. You mean the range of $k_i$ and $R_i$ ? @MickLH

Meta Crypto SE

0

Q: Can I ask questions about research journals?

Can I ask for a list of journals that are good enough to publish research work based on the topic related to cryptography? I didn't see journal tag, hence I am thinking that it is not a place to ask about publishing etc., but only related to the research doubts etc.,

discussion

MickLH

@Evinda no I mean the $\mathbb{F}_2^4$, so is that a 4-vector of $\mathbb{Z} / 2\mathbb{Z}$ elements?

I believe someone has exhaustively analysed 4 bit s-boxes, so you should probably find that paper

Evinda

So since each $k_i \in \mathbb{F}_2^{64}$ the domain of $k$ is $\mathbb{F}_2^{64}$ ?

MickLH

10:59 AM

I'd write that as $\mathbf{k} = \{k_1, k_2, \cdots\}$ to make it clear it's a vector

So are there 3 components in $\mathbf{k}$, each component $k_i$ being an element of $\mathbb{Z}/2^4\mathbb{Z}$?

or are you using $\text{GF}\left(2^4\right)$ ?

Evinda

Each component $k_i$ is an element of $\mathbb{Z}/2^2\mathbb{Z}$ since the size of each block is 8 bits. Or am I wrong?

MickLH

the usual 8 bit unsigned words correspond to $\mathbb{Z}/2^8\mathbb{Z}$

Evinda

A ok

MickLH

(the difference is that $\mathbb{Z}/n\mathbb{Z}$ is a ring (unless $n$ is prime), while $GF(2^n)$ is a field)

Evinda

Ah we are working at the field

MickLH

11:10 AM

So you are reducing modulo a polynomial?

Evinda

We are working modulo 2

MickLH

Oh I had meant when you express the $k_i$ components as single symbols, how are they to be interpreted. If you're using the native machine arithmetic then it's the natural ring interpretation

Evinda

What do you mean with native machine arithmetic?

MickLH

+ - * / %

I think I see what you're looking for though

So one important thing to notice about $\text{GF}(2)$ is that $x^2 = x$

$0 \cdot 0 = 0, 1 \cdot 1 = 1$

So for any positive $n$ you have $x^n=x$

So to increase the degree of your polynomials, you'll need to use more terms, since there is no higher exponent

Evinda

So the polynomial have degree at most 1. Right? How can we increase the degree of the polynomials using more terms?

MickLH

11:24 AM

Multivariate polynomials

The degree can be above 1, for example: $y = x_0 x_1$

Evinda

You mean that we pick the following F? @MickLH

$F(k_i,R_i)=a_{1} k_i R_i+a_{2} k_i+a_{3} R_i+a_{4}$ , where all $a_i \in \{0,1\}$

MickLH

What happened to the function? It's taking a single index now

either way, you probably want higher than degree 2, probably more like degree $\geq \frac{n}{2}$ for $n$ bits of input

Evinda

11:46 AM

The degree of $k_i$ is at most 1 and so the degree of $R_{i-1}$, or not?

MickLH

The degree of the polynomial refers specifically to the sum of exponents of each term in the highest degree monomial

So even though the exponents are all limited to 1, you can combine arbitrarily many of them

Evinda

I haven't understood how we can do this, given that there are two terms and the highest degree of each is 1. Could you explain it further to me?

MickLH

In short, use more terms

Evinda

So we consider for example F to be a function of three variables?

MickLH

I think it's natural to just take the entire bit vector at once, like: $F_n(\mathbf{k}, \mathbf{R}) = \prod_{i \in S_n^k} k_i \prod_{i \in S_n^R} R_i$

where $S_n^x$ is a subset of indices into $x$ chosen for the $n$-th round

Beware though, a product of random bits will quickly tend towards zero, so you'll want to accumulate several such products additively until you reach an acceptable bias

Sorry if I disappear, getting a bit tired, it's about 4am

Evinda

12:05 PM

Ok, I haven't understood it yet, but I will think about it in the meanwhile

SEJPM

3:14 PM

@Elias we don't normally close answers asking for official test vectors. But you asked us to compute test vectors ourselves which is indeed border-line off-topic to a programming question

so you have two options:

1) live with the NIST test vectors I commented and forget about this Q
2) Edit your question to ask for official test vectors for CCM because you couldn't find any and wait for somebody to post the ones from the NIST doc or some other standard doc

If you chose to go for 2) I'd of course support the re-open (at least with my vote and probably by also bugging our mods)

Elias

3:54 PM

@SEJPM I didn't even ask the question I just thought your comment makes a really good answer. :)

And given that bad implementations can break cryptography and that lots of side-channel stuff is implementation dependent but still considered crypto I don't quite agree with considering implementations as off-topic. :)

SEJPM

@Elias we have a very fine line indeed on this point...

SEJPM

4:10 PM

@Elias I've edited the Q and voted to re-open

even though I'm suspecting now by the looks of it that the OP actually wants AES and not AES-CCM test vectors (because he doesn't ask for a tag, didn't specify AAD and didn't provide a nonce)

Meta Crypto SE

5:23 PM

1

Q: Do we want to allow questions asking for random test vectors?

I recently stumbled upon a question asking for the calculation of a random test vector: An example of CCM - AES Mode need to test if my AES CCM mode works correctly, but I don't find any example to test that please? AES-128 Plaintext = 00112233445566778899AABBCCDDEEFF Key = 0001020304...

discussion featured allowed-questions

Evinda

6:29 PM

@MickLH What do you mean to accumulate several such products additively?

MickLH

XOR is addition on $\text{GF}(2)$

int F(int a, int b, int c, int d) {
    return (a & b) ^ (c & d);
}

this function $F : \mathbb{F}_n^4 \mapsto \mathbb{F}_n$ actually can be seen as a vector function over $n$ elements from $\text{GF}(2)$, where it returns $\mathbf{x} = \{a_i b_i + c_i d_i\}^n$

(and the XOR of two independent bits is less biased than either of the two inputs)

but the AND of two independent bits gets more biased, because 3/4th of the input space leads to the output 0

so, I mean that you'll want to make sure not only that the degree is high enough for your non-linearity to be useful, but also that there's enough terms so that the bias is canceled out as well

Evinda

8:46 PM

What exactly do you mean with bias? @MickLH

MickLH

By "bias" I mean the deviation away from 50%, of the bit's probability of being set.

Evinda

When is a bit set?

MickLH

When it takes the value $1$

(alternatively you could define it opposite, but that just feels weird)

Evinda

9:12 PM

So, we define $F(\mathbf{k}, \mathbf{R}) = \prod_{i \in S_k} k_i c_{k, i} \prod_{i \in S_R} R_i c_{R, i}$ but from the code:

int F(int a, int b, int c, int d) {
return (a & b) ^ (c & d);
}

we get that $\prod_{i \in S_k} k_i c_{k, i}$ is the addition modulo 2 of the vectors $k_i$'s and $\prod_{i \in S_R} R_i c_{R, i}$ is the addition modulo 2 of the vectors $R_i$'s and then the result is the AND operation between the above two results, or not? But why is this the addition modulo 2 when we have a product? @MickLH

MickLH

It's the other way around, those products are the non-linearity, and that version of the expression was screwed up, cut the $c$ terms.

That C++ function there is "bit sliced", meaning that if you run it on 8 bits, it's treating them as 8 separate $i$ indices and evaluating $F_i \mapsto a_i b_i + c_i d_i \mod 2$ for each one.

Evinda

So we don't take the products, just the addition modulo 2?

MickLH

Addition modulo 2 is the XOR in the middle

Evinda

So, first we multiply the vectors k_i's and the we multiply the vectors R_i's and the we add these two results modulo 2?

MickLH

You'll want to mix between the indices to achieve higher degree polynomials, and diffusion

int F(int a, int b, int c, int d) {
    int out = 0;
    for(int i=0;i<16;i++) {
        a = (a << 3) | (a >> 29);
        b = (b << 5) | (b >> 27);
        c = (c << 7) | (c >> 25);
        d = (d << 11) | (d >> 21);
        out ^= a & b & c & d;
    }
    return out;
}

Here's something that's probably horribly broken but generates degree 4 polynomials with 16 terms for every output bit

Here's a formula for one of the 32 output bits: $$F_{0} = a_{11} b_{29} c_{15} d_{19} + a_{14} b_{2} c_{22} d_{30} + a_{16} b_{16} c_{16} d_{16} + a_{17} b_{7} c_{29} d_{9} + a_{19} b_{21} c_{23} d_{27} + a_{20} b_{12} c_{4} d_{20} + a_{22} b_{26} c_{30} d_{6} + \cdots$$

It has 16 terms of degree 4, corresponding to the 16 iterations where a products of degree 4 is accumulated into the sum

Transcript for