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[7] << 2) ^ (state[8] >> 6);
        x4 = (state[10] << 5) ^ (state[11] >> 3);

        t1 = x1 ^ x4;


        x1 = (state[19] << 2) ^ (state[20] >> 6);
        x4 = (state[21] << 1) ^ (state[22] >> 7);

        t2 = x1 ^ x4;


        x1 = (state[29] << 3) ^ (state[30] >> 5);
        x4 = state[35];

        t3 = x1 ^ x4;


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


        x2 = (state[10] << 3) ^ (state[11] >> 5);
        x3 = (state[10] << 4) ^ (state[11] >> 4);
        x5 = (state[20] << 3) ^ (state[21] >> 5);

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


        x2 = (state[20] << 7) ^ (state[21] >> 1);
        x3 = state[21];
        x5 = state[32];

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


        x2 = (state[34] << 6) ^ (state[35] >> 2);
        x3 = (state[34] << 7) ^ (state[35] >> 1);
        x5 = (state[7] << 5) ^ (state[8] >> 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[23] = (*t2 << 7) ^ (state[22] & 0x7F);
    state[22] = (state[21] & 0x80) ^ (*t2 >> 1);


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

    state[12] = (*t1 << 3) ^ (state[11] & 0x07);
    state[11] = (state[10] & 0xF8) ^ (*t1 >> 5);    


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

    state[0] = *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[10] = 0x00;
    state[11] = iv[9] >> 5;

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

    state[21] = iv[0] << 3;

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

    state[35] = 0x07;


    for (i = 0; i < 144; i++) {
        x1 = (state[7] << 2) ^ (state[8] >> 6);
        x2 = (state[10] << 3) ^ (state[11] >> 5);
        x3 = (state[10] << 4) ^ (state[11] >> 4);
        x4 = (state[10] << 5) ^ (state[11] >> 3);
        x5 = (state[20] << 3) ^ (state[21] >> 5);

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


        x1 = (state[19] << 2) ^ (state[20] >> 6);
        x2 = (state[20] << 7) ^ (state[21] >> 1);
        x3 = state[21];
        x4 = (state[21] << 1) ^ (state[22] >> 7);
        x5 = state[32];

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


        x1 = (state[29] << 3) ^ (state[30] >> 5);
        x2 = (state[34] << 6) ^ (state[35] >> 2);
        x3 = (state[34] << 7) ^ (state[35] >> 1);
        x4 = state[35];
        x5 = (state[7] << 5) ^ (state[8] >> 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[7] << 2) ^ (state[8] >> 6);
        x4 = (state[10] << 5) ^ (state[11] >> 3);

        t1 = x1 ^ x4;


        x1 = (state[19] << 2) ^ (state[20] >> 6);
        x4 = (state[21] << 1) ^ (state[22] >> 7);

        t2 = x1 ^ x4;


        x1 = (state[29] << 3) ^ (state[30] >> 5);
        x4 = state[35];

        t3 = x1 ^ x4;


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


        x2 = (state[10] << 3) ^ (state[11] >> 5);
        x3 = (state[10] << 4) ^ (state[11] >> 4);
        x5 = (state[20] << 3) ^ (state[21] >> 5);

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


        x2 = (state[20] << 7) ^ (state[21] >> 1);
        x3 = state[21];
        x5 = state[32];

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


        x2 = (state[34] << 6) ^ (state[35] >> 2);
        x3 = (state[34] << 7) ^ (state[35] >> 1);
        x5 = (state[7] << 5) ^ (state[8] >> 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[23] = (*t2 << 7) ^ (state[22] & 0x7F);
    state[22] = (state[21] & 0x80) ^ (*t2 >> 1);


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

    state[12] = (*t1 << 3) ^ (state[11] & 0x07);
    state[11] = (state[10] & 0xF8) ^ (*t1 >> 5);    


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

    state[0] = *t3;
}
  • The unusual bit extractions from word can be faster than byte – kelalaka Nov 8 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 at 20:05

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.