Gecko Architecture

Home page

 

Gecko Architecture

 

Modes: CBC, CTR, ECB, PCBC, CFB, OFB

 

Test Harnesses and Sample programs

 

Downloads

Building the Software

About Gecko

 

Gecko is what is known as a substitution-permutation network.

Gecko operates on a block size of 128 bits, but three different key lengths supported: 128, 192 and 256 bits.

I find the best way to illustrate the Gecko cipher is by comparison.

In this example we will compare the Gecko architecture to the industry standard AES.

 

Gecko Cipher

AES Cipher

 

LOCAL void GKO_Cipher(GKO_state_t* state, uint8_t* bp)

{

†††††† int16_t round;

†††††† const uint8_t* round_key;

†††††† const uint8_t* key_tab = state->expanded_keys.bytes;

††††††

†††††† GKO_XORBytes(state->exchanges.bytes, bp);

†††††† GKO_ShuffleBytes(state->exchanges.bytes, bp);

 

†††††† for (round = 0; round < GKO_NROUNDS - 1; round++)

†††††† {

††††††††††††† round_key = &key_tab[round * GKO_KEY_LEN];

††††††††††††† GKO_SubBytes(bp);††††††††† ††††††††††††††††††††††††††

††††††††††††† GKO_SboxMaskBytes(round_key, bp);†††††††††††††

††††††††††††† GKO_CipherMaskBytes(round_key, bp);†††††††††

††††††††††††† GKO_ShuffleBits(bp);†††††† ††††††††††††††††††††

††††††††††††† GKO_ShuffleBytes(state->exchanges.bytes, bp);††††

††††††††††††† GKO_XORBytes(state->exchanges.bytes, bp);†††††††††††

†††††† }

 

†††††† GKO_ShuffleBytes(state->exchanges.bytes, bp);†††††††††

†††††† GKO_CipherMaskBytes(&key_tab[round * GKO_KEY_LEN], bp);

}

static void Cipher(state_t* state, uint8_t* RoundKey)

{

†††††† uint8_t round = 0;

 

†††††† AddRoundKey(0, state, RoundKey);

 

†††††† for (round = 1; round < Nr; ++round)

†††††† {

††††††††††††† SubBytes(state);

††††††††††††† ShiftRows(state);

††††††††††††† MixColumns(state);

††††††††††††† AddRoundKey(round, state, RoundKey);

†††††† }

 

†††††† SubBytes(state);

†††††† ShiftRows(state);

†††††† AddRoundKey(Nr, state, RoundKey);

}

 

As you can see, Gecko and AES share a similar structure, but the operations are quite different.

I will break it down here, but first I will describe the core philosophy underlying much of Gecko and how it relates to other ciphers.

 

Gecko creates an exchanges table based upon the cipher key. This table is built at initialization time and is used throughout the encryption/decryption process.

The exchange table is 128 bits or 16 bytes, and contains a pseudorandom ordered lookup table.

For instance, a given cipher key might generate the exchange table: [6,8,13,11,5,7,9,0,14,2,4,10,12,3,1,15].

This exchange table is used to both shuffle the bytes in a given round (GKO_ShuffleBytes) as well as the XORís with the plaintext (GKO_XORBytes).

This mechanism ensures that byte/xor ordering canít be anticipated without knowing the cipher key.

 

 

 

 

GKO_SubBytes:

The SubBytes function makes use of the Rijndael S-box to replace input bytes with values from the sbox.

The general form is: input_byte[x] = sbox[input_byte[x]];

This is the substitution mechanism in both Gecko and AES.

AES makes use of the same mechanism for substitution.

 

GKO_SboxMaskBytes:

The general form is: input_byte [N] ^= sbox[round_key[N]];

Here we XOR the input byte[N] with the sbox value of round_key[N].

We double dip on the sbox for this particular use. The sbox is a free source of pseudorandom constants to mask our input (as well as substitute.)

AES has no equivalent function.

 

GKO_CipherMaskBytes:

The general form is: input_byte [N] ^= round_key[N];

It is a typical cryptographic technique, to XOR the input bytes with the round keys.

Similar to the AES AddRoundKey function.

 

GKO_ShuffleBits:

The general form is:
††††††††††† head = PopHead(&input_byte [0x0]);

††††††††††† head = GlueTail(&input_byte [0x1], head);

††††††††††† head = GlueTail(&input_byte [0x2], head);

††††††††††††††††††††††† .

††††††††††††††††††††††† .

††††††††††††††††††††††† .

††††††††††† GlueTail(&input_byte [0x0], head);

Where PopHead and GlueTail simply encapsulates the rather ugly mask and shift operations.

The result is to circularly left-rotate N bits from the head of one byte to the tail of the next byte, until we reach the last byte of the input (128 bits, 16 bytes,) and finally gluing the high N bits of the last byte to the tail of the first byte. Effectively performing a circular, left-rotate of N bits around a 128 bit space.

AES has no equivalent function.

But the AES MixColumns step combined with the ShiftRows step, is the primary source of AES diffusion.

This is true for Geckoís GKO_ShuffleBits combined with GKO_ShuffleBytes. So I guess some loose analogy could be drawn.

 

GKO_ShuffleBytes:

The general form is:

††††††††††† GKO_SwapBytes(&input_byte [0xf], & input_byte [exchanges[0x0]]);

††††††††††† GKO_SwapBytes(&input_byte [0xe], & input_byte [exchanges[0x1]]);

††††††††††† GKO_SwapBytes(&input_byte [0xd], & input_byte [exchanges[0x2]]);

††††††††††† GKO_SwapBytes(&input_byte [0xc], & input_byte [exchanges[0x3]]);

††††††††††† GKO_SwapBytes(&input_byte [0xb], & input_byte [exchanges[0x4]]);

††††††††††††††††††††††† .

††††††††††††††††††††††† .

††††††††††††††††††††††† .

As discussed earlier, the exchanges table is a table of 8 bit integers 0x0-0xf, in pseudorandom order, the order is defined by the cipher key.

This mechanism (combined with GKO_ShuffleBits) provides Gecko with superior diffusion and confounds linear analysis since the byte ordering in the resulting ciphertext is key dependent.

Somewhat analogous to the AES ShiftRows function.

I say somewhat because while both function mix the bytes across the 16 byte block, Gecko does so with no row constraints, and does so in a pseudorandom order, where the order is defined by the cipher key.

AES does the same row shifts each time and gives linear analysis at least a thread to tug upon.

 

GKO_XORBytes:

The general form is:

††††††††††† input_byte[exchanges[0x0]] ^= input_byte[exchanges[0x1]];

††††††††††† input_byte[exchanges[0x2]] ^= input_byte[exchanges[0x3]];

††††††††††† input_byte[exchanges[0x4]] ^= input_byte[exchanges[0x5]];

††††††††††† input_byte[exchanges[0x6]] ^= input_byte[exchanges[0x7]];

 

††††††††††† input_byte[exchanges[0x1]] ^= input_byte[exchanges[0x2]];

††††††††††† input_byte[exchanges[0x3]] ^= input_byte[exchanges[0x4]];

††††††††††† input_byte[exchanges[0x5]] ^= input_byte[exchanges[0x6]];

††††††††††† input_byte[exchanges[0x7]] ^= input_byte[exchanges[0x0]];

Again, we see the use of the exchanges to randomize the XORs.

The effect here is to propagate changes in one byte in the input plaintext †to neighboring bytes, adding to Geckoís diffusion.

AES has no equivalent function.

 

 

 

 

Gecko Key Expansion

AES Key Expansion

 

LOCAL void GKO_ExpandKeys(GKO_state_t* state, const uint8_t key[])

{

†††††† int ix, ndx = 0, shift = 0;

†††††† uint8_t key_salt=0, salt_ndx=0;

†††††† uint8_t prng_tab[GKO_EXP_KEY_TBL_SIZE];

†††††† for (ix = 0; ix < GKO_EXP_KEY_TBL_SIZE; ix++)

†††††† {

††††††††††††† if (ndx == GKO_KEY_NELTS)

††††††††††††† {††††† // create next round salt

†††††††††††††††††††† key_salt = gko_rsbox[key_salt] ^ key[salt_ndx++];

†††††††††††††††††††† ndx = 0;†††††††††††† // restart the next-key index

†††††††††††††††††††† shift++;†††††††††††† // next rotate value

††††††††††††† }

††††††††††††† // record the new key

††††††††††††† state->expanded_keys.bytes[ix] = _rotl8(key[ndx++],shift) ^ key_salt;

††††††††††††† // create our pseudo-random sorting hat

††††††††††††† prng_tab[ix] = gko_rsbox[ix] ^ state->expanded_keys.bytes[ix];

†††††† }

†††††† // shuffle the expanded keys across the entire key-space

†††††† KeyedShuffle(prng_tab,state->expanded_keys.bytes, GKO_EXP_KEY_TBL_SIZE);

}

static void KeyExpansion(uint8_t* RoundKey, const uint8_t* Key)

{

†††††† unsigned i, j, k;

†††††† uint8_t tempa[4]; // Used for the column/row operations

 

†††††† // The first round key is the key itself.

†††††† for (i = 0; i < Nk; ++i)

†††††† {

††††††††††††† RoundKey[(i * 4) + 0] = Key[(i * 4) + 0];

††††††††††††† RoundKey[(i * 4) + 1] = Key[(i * 4) + 1];

††††††††††††† RoundKey[(i * 4) + 2] = Key[(i * 4) + 2];

††††††††††††† RoundKey[(i * 4) + 3] = Key[(i * 4) + 3];

†††††† }

 

†††††† // All other round keys are found from the previous round keys.

†††††† for (i = Nk; i < Nb * (Nr + 1); ++i)

†††††† {

††††††††††††† {

†††††††††††††††††††† k = (i - 1) * 4;

†††††††††††††††††††† tempa[0] = RoundKey[k + 0];

†††††††††††††††††††† tempa[1] = RoundKey[k + 1];

†††††††††††††††††††† tempa[2] = RoundKey[k + 2];

†††††††††††††††††††† tempa[3] = RoundKey[k + 3];

 

††††††††††††† }

 

††††††††††††† if (i % Nk == 0)

††††††††††††† {

†††††††††††††††††††† // Function RotWord()

†††††††††††††††††††† {

†††††††††††††††††††††††††† const uint8_t u8tmp = tempa[0];

†††††††††††††††††††† †††††† tempa[0] = tempa[1];

†††††††††††††††††††† †††††† tempa[1] = tempa[2];

†††††††††††††††††††† †††††† tempa[2] = tempa[3];

†††††††††††††††††††† †††††† tempa[3] = u8tmp;

†††††††††††††††††††† }

 

†††††††††††††††††††† // Function Subword()

†††††††††††††††††††† {

†††††††††††††††††††† †††††† tempa[0] = getSBoxValue(tempa[0]);

†††††††††††††††††††† †††††† tempa[1] = getSBoxValue(tempa[1]);

†††††††††††††††††††† †††††† tempa[2] = getSBoxValue(tempa[2]);

†††††††††††††††††††† †††††† tempa[3] = getSBoxValue(tempa[3]);

†††††††††††††††††††† }

 

†††††††††††††††††††† tempa[0] = tempa[0] ^ Rcon[i / Nk];

††††††††††††† }

#if defined(AES256) && (AES256 == 1)

††††††††††††† if (i % Nk == 4)

††††††††††††† {

†††††††††††††††††††† // Function Subword()

†††††††††††††††††††† {

†††††††††††††††††††† †††††† tempa[0] = getSBoxValue(tempa[0]);

†††††††††††††††††††† †††††† tempa[1] = getSBoxValue(tempa[1]);

†††††††††††††††††††† †††††† tempa[2] = getSBoxValue(tempa[2]);

†††††††††††††††††††† †††††† tempa[3] = getSBoxValue(tempa[3]);

†††††††††††††††††††† }

††††††††††††† }

#endif

††††††††††††† j = i * 4; k = (i - Nk) * 4;

††††††††††††† RoundKey[j + 0] = RoundKey[k + 0] ^ tempa[0];

††††††††††††† RoundKey[j + 1] = RoundKey[k + 1] ^ tempa[1];

††††††††††††† RoundKey[j + 2] = RoundKey[k + 2] ^ tempa[2];

††††††††††††† RoundKey[j + 3] = RoundKey[k + 3] ^ tempa[3];

†††††† }

}

 

Gecko Key Expansion Explained as it relates to AES

 

Gecko starts out by adding the cipher key as the first N round keys to the table of expanded keys. So for instance, for a 128 bit cipher key, those 16 bytes are added as the first 16 bytes of a 176 byte expanded key table.

All subsequent Gecko round-keys are derived from the original cipher key, rotated left (N) XOR key_salt.

The left rotate is 1 for the next block of keys, 2 for the next and so on until the table is filled.

The key_salt is generated from the rsbox[N] XOR cipher key [N].

In the first pass, where the original cipher key is added, key_salt is zero, so key_salt has no effect on the first block of keys. In the next pass, when the second block of keys are added (16 bytes in the case of 129 bit cipher key,) the key_salt = rsbox[0] XOR cipher key [0]. By definition rsbox[0] = 0x52. If the first cipher key byte was say 0x38, then would have a key_salt value of 0x52 XOR 0x38, or 0x6A.

This key_salt will be use for all keys within a block, and is incremented rsbox[N++] XOR cipher key [N++] for each subsequent block.

 

Shuffling the expanded key table:

In order to diffuse relationships between keys, Gecko finishes by shuffling the keys across the entire key table (unlike AES that only shuffles within a 16 byte block.)

 

To accomplish this, Gecko builds and auxiliary and temporary table for the sole purpose of acting as a pseudorandom seed table for a Fisher-Yates shuffle.

The way this table is built is as follows:
prng_tab[ix] = gko_rsbox[ix] ^ state->expanded_keys.bytes[ix];

 

The prng_tab is this is pseudorandom seed table, and is built from rsbox[N] XOR expanded_key[N]. Where N is the expanded key table index we are currently processing.

 

We then hand these two tables to the Fisher-Yates shuffle. Fisher-Yates uses the prng_tab as a table of pseudorandom values to shuffle the expanded key table.

 

The result is an expanded key table which is pseudo randomly ordered. This includes the cipher key that originally appeared as the first N bytes of the expanded key table.

 

By performing this operation, it cannot be conjectured that key[n] relates to key[j] in any meaningful way.