Specification of the scream stream cipher is unclear

I am implementing in C++ the Scream stream cipher. The Scream family is composed of Scream-0, Scream-S and Scream-F. For this question, assume that I'm using Scream-S.

The specifications of the Scream cipher are given in the paper "Scream: a software-efficient stream cipher", but I didn't find a reference sourcecode for this cipher which could have helped me.

Maybe because the specs include many notations, I have some questions about the scream cipher:

1. In section 2 about the two 2X2 matrices : Am I right to say that $x$ and $x+1$ (from the $GaloisField(256)$) are replaced respectively by $2$ and $3$?

2. In section 3, it's possible to implement the function $F$ to optimize it. The author didn't define the multiplication ($u0 = M1(0,0) . S1[x]$). Is it a multiplication following $GF(256)$ with the polynomial $x^8 + x^7 + x^6 + x + 1$ (0x1C3) ?

3. In the algorithm of $F$ in section 3, they write 'byte0'. Does $byte_0$ refer to the MSB or LSB of an integer ?

Since $F$ is the core of the algorithm, it's important for me to know and understand these kind of details.

-

I've just dived into that paper for you, with the following results:

1. You've got that one correct.

2. The eight-byte input is multiplied with matrix M. There is no mention or indication of the polynomial you mention. Simply follow the paper.

The matrices are fixed [[1,2],[2,1]] and [[1,3],[1,3]]. So, 2 and 3 are NOT replaced by x. The multiplication is on GF(256) with the polynomial specified at page 4. Thus, you have to do something like this: GF256_Multiply(2, S1[x], 0x1C3) where 2 = M1(0,1) = M1(1,0) for example. That's why they call T0 and T1 "lookup tables". These are fixed tables which imply M1 and M2 are fixed too.

(Notice: This was corrected thanks to OP's own research and the corrections OP mentioned in the comments to this answer.)

3. I think you got a bit confused there. MSB (= Most Significant Bit) and LSB (= Least Significant Bit) define "bits", while the paper explicitly talks about "bytes" in section 3. Therefore, they did not need to define any MSB or LSB. The paper simply defines $byte_0$ (which is, reading from left to right, the leftmost byte), and $byte_3$ (which is the rightmost byte). So you practically extract the 4 bytes into $byte_0$ up to $byte_3$ from left to right (aka "first in, first out").

Hope that helps.

-
Thanks for the answer. Question 1 and 3 sound good to me. For the second question, the authors mentioned the polynomial at page 4 of the paper. Then, the elements of the 2 matrices belong to GF(256) with the polynomial given. But, S[x] is multiply with 1, x or x+1. Following my logic, should we prefer the multiplication of GF(256) or is it fair to just change x by 2 and x+1 by 3 and multiply normally ? This is confusing me. I'd appreciate clarifications on that point if possible. –  Gabriel L. Oct 9 '13 at 13:21
@GabrielL. Been looking at the wrong page (and the wrong code) in relation to Nr. 2. No, I wouldn't change that. As I understand that part, x and x+1 seems to be influenced in that Feistel ladder. As Figure 2 shows, you'll partition x at a later point too. Following the pictorial description, it's to be expected that x (and therefore x+1) change. Personally, I think it's logic too because if x would always be 2 and x+1 would always be 3, it would not make sense to partition x into two 2x4 matrices later on. In fact, you would be creating a "fixed" A and B and try to mix that all the time... –  e-sushi Oct 9 '13 at 14:48
If I understood well your explanations, the x in the matrices is the same as the input parameter x of the function F. Then, in the multiplication M1(0,1) by S1[xi], the x in matrices are replaced by xi for i=0,...,15 for example. So the multiplication would be normal by replacing x by the correct xi. By the way, these multiplications are necessary to make tables T0 and T1 described in section 3. Sorry if I misunderstood you, but I just want to make sure my logic is right. Thank you very much. –  Gabriel L. Oct 9 '13 at 15:34
@GabrielL. Your logic is right. It seems like you are now on the correct path and understand what's going on in that paper. By the way: no need to thank me. Just remember to "accept" answers if you think they answered your question and if you're satisfied with them. Sometimes, people tend to forget about that. ;) –  e-sushi Oct 9 '13 at 16:19
I successfully implement the Scream cipher with the tests given at the end of the paper. In question 2, matrices are fixed [[1,2],[2,1]] and [[1,3],[1,3]]. So, 2 and 3 are NOT replaced by x. The multiplication is on GF(256) with the polynomial specified at page 4. Thus, you have to do something like this : GF256_Multiply(2, S1[x], 0x1C3) where 2 = M1(0,1) = M1(1,0) for example. Now, I understand why they call T0 and T1 lookup tables. These are fixed tables which imply M1 and M2 are fixed too. Hope my explanations are clears enough. –  Gabriel L. Oct 9 '13 at 19:43