# Why is this Trivium implementation working bytewise instead of bitwise?

I am currently looking into a Trivium implementation available in the FELICS framework.

Parameters of the Trivium stream cipher:

• Key size: 80 bit
• IV size: 80 bit
• State size: 288 bit

The Trivium specification states that the algorithm only shifts the state by one bit per iteration. However, in the FELICS implementation listed below, the author shifts the state by one byte per iteration. Now I am wondering why (or if, as I couldn't find an original test vector by the Trivium authors) this is working as intended?

Encryption algorithm of the Trivium specification:

for i = 1 to N do
t1 ← s66 + s93
t2 ← s162 + s177
t3 ← s243 + s288
zi ← t1 + t2 + t3
t1 ← t1 + s91 · s92 + s171
t2 ← t2 + s175 · s176 + s264
t3 ← t3 + s286 · s287 + s69
(s1, s2, ... , s93) ← (t3 , s1 , ... , s92)
(s94 , s95, ... , s177) ← (t1 , s94 , ... , s176)
(s178, s279, ... , s288) ← (t2 , s178, ... , s287)
end for


As you can see, the state is shifted only by one bit per iteration. All variables only represent one bit. $$N$$ is the number of bits to be encrypted. The last three lines represent the Rotate function of the FELICS implementation.

Encryption algorithm of the FELICS implementation:

void Encrypt(uint8_t *state, uint8_t *stream, uint16_t length) {
uint16_t i;
uint8_t t1, t2, t3;
uint8_t x1, x2, x3, x4, x5;

for (i = 0; i < length; i++) {
x1 = (state << 2) ^ (state >> 6);
x4 = (state << 5) ^ (state >> 3);

t1 = x1 ^ x4;

x1 = (state << 2) ^ (state >> 6);
x4 = (state << 1) ^ (state >> 7);

t2 = x1 ^ x4;

x1 = (state << 3) ^ (state >> 5);
x4 = state;

t3 = x1 ^ x4;

stream[i] ^= t1 ^ t2 ^ t3;

x2 = (state << 3) ^ (state >> 5);
x3 = (state << 4) ^ (state >> 4);
x5 = (state << 3) ^ (state >> 5);

t1 = t1 ^ (x2 & x3) ^ x5;

x2 = (state << 7) ^ (state >> 1);
x3 = state;
x5 = state;

t2 = t2 ^ (x2 & x3) ^ x5;

x2 = (state << 6) ^ (state >> 2);
x3 = (state << 7) ^ (state >> 1);
x5 = (state << 5) ^ (state >> 3);

t3 = t3 ^ (x2 & x3) ^ x5;

Rotate(state, &t1, &t2, &t3);
}
}


The $$x$$ variables represent the $$s$$ variables from the specification. For example, the first appearance of $$x_1$$ is $$s_{66}$$ from the specification. Since $$x_1$$ is the size of one byte, only the last bit of it actually represents the $$66^{th}$$ bit of the state ($$s_{66}$$). The same counts for the $$t$$ variables. In the specification, they are only one bit, but in the implementation they are one byte. Not just the last bit (which actually represents the bit of the specification) is used for encryption, but the entire byte: $$t_1 \oplus t_2 \oplus t_3$$

Rotate algorithm of the FELICS implementation:

void Rotate(uint8_t *state, uint8_t *t1, uint8_t *t2, uint8_t *t3) {
uint8_t i;

/* Rotate register C */
for (i = 35; i > 23 ; i--) {
state[i] = state[i - 1];
}

state = (*t2 << 7) ^ (state & 0x7F);
state = (state & 0x80) ^ (*t2 >> 1);

/* Rotate register B */
for (i = 21; i > 12 ; i--) {
state[i] = state[i - 1];
}

state = (*t1 << 3) ^ (state & 0x07);
state = (state & 0xF8) ^ (*t1 >> 5);

/* Rotate register A */
for (i = 10; i > 0 ; i--) {
state[i] = state[i - 1];
}

state = *t3;
}


This function iterates over the state bytewise ($$36 = 288 / 8$$) and it shows that the function shifts one entire byte per call.

Is the implementation doing what it should? Does it matter anyhow to do it bytewise? I cannot entirely wrap my head around it. Maybe it makes no difference (except for the performance increase), but I am wondering how one is supposed to know this when it is not mentioned anywhere?

On a side note: This is the first stream cipher implementation I am looking into. Also, it is the first time I am working directly with bits and bytes in C, so maybe the answer is quite trivial.

Complete FELICS implementation for reference:

#define STATE_SIZE 36
#define KEY_SIZE 10
#define IV_SIZE 10
#define TEST_STREAM_SIZE 16

void Setup(uint8_t *state, uint8_t *key, uint8_t *iv) {
uint8_t i;
uint8_t t1, t2, t3;
uint8_t x1, x2, x3, x4, x5;

for (i = 0; i < KEY_SIZE; i++) {
state[i] = key[9 - i];
}

state = 0x00;
state = iv >> 5;

for (i = 0; i < IV_SIZE - 1; i++) {
state[i + 12] = (iv[9 - i] << 3) ^ (iv[8 - i] >> 5);
}

state = iv << 3;

for (i = 22; i < 35; i++) {
state[i] = 0x00;
}

state = 0x07;

for (i = 0; i < 144; i++) {
x1 = (state << 2) ^ (state >> 6);
x2 = (state << 3) ^ (state >> 5);
x3 = (state << 4) ^ (state >> 4);
x4 = (state << 5) ^ (state >> 3);
x5 = (state << 3) ^ (state >> 5);

t1 = x1 ^ (x2 & x3) ^ x4 ^ x5;

x1 = (state << 2) ^ (state >> 6);
x2 = (state << 7) ^ (state >> 1);
x3 = state;
x4 = (state << 1) ^ (state >> 7);
x5 = state;

t2 = x1 ^ (x2 & x3) ^ x4 ^ x5;

x1 = (state << 3) ^ (state >> 5);
x2 = (state << 6) ^ (state >> 2);
x3 = (state << 7) ^ (state >> 1);
x4 = state;
x5 = (state << 5) ^ (state >> 3);

t3 = x1 ^ (x2 & x3) ^ x4 ^ x5;

Rotate(state, &t1, &t2, &t3);
}
}

void Encrypt(uint8_t *state, uint8_t *stream, uint16_t length) {
uint16_t i;
uint8_t t1, t2, t3;
uint8_t x1, x2, x3, x4, x5;

for (i = 0; i < length; i++) {
x1 = (state << 2) ^ (state >> 6);
x4 = (state << 5) ^ (state >> 3);

t1 = x1 ^ x4;

x1 = (state << 2) ^ (state >> 6);
x4 = (state << 1) ^ (state >> 7);

t2 = x1 ^ x4;

x1 = (state << 3) ^ (state >> 5);
x4 = state;

t3 = x1 ^ x4;

stream[i] ^= t1 ^ t2 ^ t3;

x2 = (state << 3) ^ (state >> 5);
x3 = (state << 4) ^ (state >> 4);
x5 = (state << 3) ^ (state >> 5);

t1 = t1 ^ (x2 & x3) ^ x5;

x2 = (state << 7) ^ (state >> 1);
x3 = state;
x5 = state;

t2 = t2 ^ (x2 & x3) ^ x5;

x2 = (state << 6) ^ (state >> 2);
x3 = (state << 7) ^ (state >> 1);
x5 = (state << 5) ^ (state >> 3);

t3 = t3 ^ (x2 & x3) ^ x5;

Rotate(state, &t1, &t2, &t3);
}
}

void Rotate(uint8_t *state, uint8_t *t1, uint8_t *t2, uint8_t *t3) {
uint8_t i;

/* Rotate register C */
for (i = 35; i > 23 ; i--) {
state[i] = state[i - 1];
}

state = (*t2 << 7) ^ (state & 0x7F);
state = (state & 0x80) ^ (*t2 >> 1);

/* Rotate register B */
for (i = 21; i > 12 ; i--) {
state[i] = state[i - 1];
}

state = (*t1 << 3) ^ (state & 0x07);
state = (state & 0xF8) ^ (*t1 >> 5);

/* Rotate register A */
for (i = 10; i > 0 ; i--) {
state[i] = state[i - 1];
}

state = *t3;
}

• The unusual bit extractions from word can be faster than byte – kelalaka Nov 8 '18 at 17:26
• Yeah, I presume the byte / bit ops are somehow equivalent. Try a round or two and check. Sometime reference implementations come with a description of the optimizations performed. – Maarten Bodewes Nov 8 '18 at 20:05