**Spoiler:**

Here's the breakdown of the components.

Internal state:

Constants:

r1 and r2 are taken from the fractional portion of the square root of two (when represented as binary). I divided it into four bit pieces, eliminated any that were equal to the previous, and appended a 1 to make it a five-bit odd number. These are used for the rotation schedule. These are probably less than ideal, but chosen because I don't want to spend too much time on it.

e1 and e2 are the first and second 32 bits, respectively, of the fractional portion of e.

pi is the fractional portion of pi.

Mixing function:

This is a pretty basic addition, rotation and xor function. It can be considered to have 32 rounds. It's chosen to be simple, but it's far from ideal. In a perfect world, the mixing would make every output bit dependent on every input bit, but this does not accomplish this. It's good enough for my purposes, however. The constant e1 serves two purposes: 1) it makes sure that even if the state is zero, after an iteration it will not be zero (it will be various rotations of e after one call to mix, but it will start looking fairly random after another call) and 2) it makes it so that I alternate between xor and addition, while swapping the order make sure that every word in the state has both an xor and

This is a one pass addition, rotation, and xor function. This can be considered 16 rounds, and does two rotations per round, as opposed to one like the previous function. The goal is simply to make sure the output depends on the entire state in a way that makes it difficult to determine the state.

Initialization:

So, we use the array containing pi to initialize the state, this gets it nice and random looking, makes it harder to find keys or initialization vectors that result in a weak state. The key length is restricted to 1024 bits, the IV length is not restricted. The first thing we do Is mix the IV into the state by xoring it to the first element, and then running the mix function; the IV should never be reused, and this makes it so that the keystream is never repeated.

The next thing we do is initialize a 1024 bit counter from the state using the hash function, with a call to mix for every call to the hash. The counter is there to guarantee that the keystream has a period of at least 1024 bits.

The next step serves two purposes: it stretches the length of the key to 2048 bits, and it makes the state dependent on the key; up until this point, you can assume anyone knows the state. We mix the key in just like we did the IV, and we copy the key to a larger key array. Once the entire key has been mixed in, we use the hash function to append to the key.

This brings us to the final part of the function:

The first thing we do is increment the counter; since this is a known value, we don't have to worry about timing attacks. If the counter was dependent on the key, a timing attack could possibly leak information about the key.

Next, the counter is XORd to the state, and the mix function is called. The next step is to XOR the first half of the key, and mix again. By XORing the key every time, we make it so that even if the attacker knows the state at one point, they cannot compute past or future outputs. We then XOR the second half of the key for further guarantee that the operation cannot be reversed by an attacker (after all, if the key is known, the mix function is bijective). We can now compute the hash and output it as four bytes of our keystream

Internal state:

Code: Select all

`typedef struct sc_state {`

uint32_t pos;

uint32_t keystream;

uint32_t key[64];

uint32_t counter[32];

uint32_t state[32];

} sc_state;

Constants:

Code: Select all

`static const uint32_t r1[] = {`

13, 21, 1, 19, 29, 13, 15, 31,

7, 23, 25, 19, 1, 17, 23, 5,

31, 23, 3, 7, 13, 29, 21, 19,

11, 15, 27, 7, 29, 7, 21, 27

};

static const uint32_t r2[] = {

29, 25, 3, 15, 11, 3, 5, 15,

11, 1, 19, 27, 21, 5, 31, 11,

19, 1, 23, 1, 13, 15, 7, 5,

21, 19, 11, 31, 19, 1, 13, 1

};

static const uint32_t e1 = 0xb7e15162;

static const uint32_t e2 = 0x8aed2a6a;

static const uint32_t pi[] = {

0x243F6A88, 0x85A308D3, 0x13198A2E, 0x03707344,

0xA4093822, 0x299F31D0, 0x082EFA98, 0xEC4E6C89,

0x452821E6, 0x38D01377, 0xBE5466CF, 0x34E90C6C,

0xC0AC29B7, 0xC97C50DD, 0x3F84D5B5, 0xB5470917,

0x9216D5D9, 0x8979FB1B, 0xD1310BA6, 0x98DFB5AC,

0x2FFD72DB, 0xD01ADFB7, 0xB8E1AFED, 0x6A267E96,

0xBA7C9045, 0xF12C7F99, 0x24A19947, 0xB3916CF7,

0x0801F2E2, 0x858EFC16, 0x636920D8, 0x71574E69

};

r1 and r2 are taken from the fractional portion of the square root of two (when represented as binary). I divided it into four bit pieces, eliminated any that were equal to the previous, and appended a 1 to make it a five-bit odd number. These are used for the rotation schedule. These are probably less than ideal, but chosen because I don't want to spend too much time on it.

e1 and e2 are the first and second 32 bits, respectively, of the fractional portion of e.

pi is the fractional portion of pi.

Mixing function:

Code: Select all

`static void sc_mix(sc_state *state) {`

uint32_t i, prev;

prev = state->state[31];

for (i=0; i<31; i+=2) {

state->state[i] ^= prev;

state->state[i+1] += state->state[i];

prev = state->state[i+1] = rotl(state->state[i+1],r1[i+1]);

}

prev ^= e1;

for (i=0; i<31; i+=2) {

state->state[i] += prev;

state->state[i] = rotl(state->state[i],r1[i]);

prev = state->state[i+1] ^= state->state[i];

}

}

This is a pretty basic addition, rotation and xor function. It can be considered to have 32 rounds. It's chosen to be simple, but it's far from ideal. In a perfect world, the mixing would make every output bit dependent on every input bit, but this does not accomplish this. It's good enough for my purposes, however. The constant e1 serves two purposes: 1) it makes sure that even if the state is zero, after an iteration it will not be zero (it will be various rotations of e after one call to mix, but it will start looking fairly random after another call) and 2) it makes it so that I alternate between xor and addition, while swapping the order make sure that every word in the state has both an xor and

Code: Select all

`static uint32_t sc_hash_state(sc_state *state) {`

uint32_t i, x = e2;

for (i=0; i<31; i+=2) {

x += state->state[i];

x = rotl(x,r2[i]);

x ^= state->state[i+1];

x = rotl(x,r2[i+1]);

}

return x;

}

This is a one pass addition, rotation, and xor function. This can be considered 16 rounds, and does two rotations per round, as opposed to one like the previous function. The goal is simply to make sure the output depends on the entire state in a way that makes it difficult to determine the state.

Initialization:

Code: Select all

`extern sc_state * sc_init(const uint32_t *key, size_t key_length, const uint32_t *iv, size_t iv_length) {`

size_t i;

sc_state *state = (sc_state*)malloc(sizeof(sc_state));

memcpy(state->state, pi, sizeof(pi));

if (key_length > 32) key_length = 32;

for (i=0; i<iv_length; i++) {

state->state[0] ^= iv[i];

sc_mix(state);

}

for (i=0; i<32; i++) {

state->counter[i] = sc_hash_state(state);

sc_mix(state);

}

for (i=0; i<key_length; i++) {

state->key[i] = key[i];

state->state[0] ^= key[i];

sc_mix(state);

}

for (i = key_length; i<64; i++) {

state->key[i] = sc_hash_state(state);

sc_mix(state);

}

state->pos = 4;

return state;

}

So, we use the array containing pi to initialize the state, this gets it nice and random looking, makes it harder to find keys or initialization vectors that result in a weak state. The key length is restricted to 1024 bits, the IV length is not restricted. The first thing we do Is mix the IV into the state by xoring it to the first element, and then running the mix function; the IV should never be reused, and this makes it so that the keystream is never repeated.

The next thing we do is initialize a 1024 bit counter from the state using the hash function, with a call to mix for every call to the hash. The counter is there to guarantee that the keystream has a period of at least 1024 bits.

The next step serves two purposes: it stretches the length of the key to 2048 bits, and it makes the state dependent on the key; up until this point, you can assume anyone knows the state. We mix the key in just like we did the IV, and we copy the key to a larger key array. Once the entire key has been mixed in, we use the hash function to append to the key.

This brings us to the final part of the function:

Code: Select all

`static uint32_t sc_keystream_get(sc_state *state) {`

uint32_t i = 0;

while((state->counter[i] += 1) == 0) i++;

for (i=0; i<32; i++) {

state->state[i] ^= state->counter[i];

}

sc_mix(state);

for (i=0; i<32; i++) {

state->state[i] ^= state->key[i];

}

sc_mix(state);

for (i=0; i<32; i++) {

state->state[i] ^= state->key[i+32];

}

return sc_hash_state(state);

}

The first thing we do is increment the counter; since this is a known value, we don't have to worry about timing attacks. If the counter was dependent on the key, a timing attack could possibly leak information about the key.

Next, the counter is XORd to the state, and the mix function is called. The next step is to XOR the first half of the key, and mix again. By XORing the key every time, we make it so that even if the attacker knows the state at one point, they cannot compute past or future outputs. We then XOR the second half of the key for further guarantee that the operation cannot be reversed by an attacker (after all, if the key is known, the mix function is bijective). We can now compute the hash and output it as four bytes of our keystream

I did some tests for randomness using ent and it appears as random as /dev/urandom, so that's a good sign. I provide no guarantees on the security of this algorithm, in fact I am not even happy with the mix function and rotation constants, but it was just a fun project to show how you can make a simple, efficient stream cipher that can evade anyone who hasn't spent a good deal of time studying cryptanalysis.

Source, if you are interested.

- sc.tar.gz
- (1.4 KiB) Downloaded 291 times