|
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.
|
|
|