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 key and IV are inserted in the correct order ($k_1, ..., k_{80}$). Contrary to the specification, the Setup function of the FELICS implementation (shown below) inserts the key and IV in reverse order ($k_9, ..., k_0$).

  • First, I have read here that it is more natural to do it in reverse order. Why, though?
  • Second, is it possible to insert the key and IV in the correct order (according to the specification) and still achieve the same result (i.e. the same key stream etc.)? If so, how?
  • Third, since this is done bytewise, could this result in a problem anyhow? For example, if the specification would state to insert the key in reverse order, would it matter to do it bytewise instead of bitwise?

An example for the third question: Suppose we have a key of two bytes.

$b_1 := 11001100$ and $b_2 := 01010101$.

If the key is inserted in...

... the correct order ($b_1$, $b_2$): $11001100 01010101$

... the reverse order bitwise ($b_{16}$, ..., $b_1$): $10101010 00110011$

... the reverse order bytewise ($b_2$, $b_1$): $01010101 11001100$

Depending on whether it is done bitwise or bytewise, the result is not the same.


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;
}
  • This probably comes down to the difference between big and little endian. I presume the processor is little endian while the spec is big endian (at least, that's what I presume since Intel / AMD are little endian) and the order is incorrect (for your version of incorrect). – Maarten Bodewes Nov 8 at 21:14

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.