Not Great Encryption Standard

Designing a block cipher manually because I think it's fun.

Obviously, don't use this when security is important.

Algorithm Design

We use a Feistel network structure with 80 half-rounds / 40 full rounds. (I chose the number of rounds completely arbitrarily.)

Fiestel network basics

• The block (128 bits for this cipher) is split into the left half and right half.
• Calculate some function F on the right half and the round key. XOR the result with the left half.
• Calculate some function F on the new left half and the round key. XOR the result with the right half.
• Repeat.

For our cipher, also XOR with 2 additional round keys at the beginning and end of the process. (This is because diffusion is somewhat useless in the first and last rounds.)

F function

We want good diffusion (changing one bit affects the entire output) and confusion (obscure relationship between key and plaintext/ciphertext). Importantly, F does not necessarily need to be invertible.

Diffusion

We want good diffusion over the 64-bit half-block. We can achieve this through a Galois matrix multiplication:

• Represent the 64-bit half-block as a vector [high 32 bits, low 32 bits].
• Multiply this vector
  • By the matrix (the first bytes of SHA256(empty string), invertible so we don't lose parts of the output space):

    0xe3b0c442  0x98fc1c14
    0x9afbf4c8  0x996fb924
    

  • Over GF(2^32) with the irreducible polynomial 0x1 04c1 1db7 (this is the same one as CRC32)

Call this output D. A single bit flip in the input now affects all bits in D. Then we'll calculate F with F = D + RoundKey (mod 2^64).

Confusion

We'll apply a nonlinear S-box to each half-block right before it gets fed into F.

Specifically, we map each byte b to its multiplicative inverse in GF(2^8) using the AES irreducible polynomial 0x1 1b. This transformation is "as nonlinear as possible".

Neatly, since inverses come in pairs, inverse substitution is the same as (forward) substitution.

Key Schedule

A total of 84 round keys of 64 bits each are needed (80 half-rounds, 2x 64 bits at the beginning and end).

We support keys of size any multiple of 64 bits. (Sensible choices are 128, 192, or 256 bits.) Call the number of 64-bit words in the key N.

Round keys 0 through N-1 are directly from the input key. Then, we repeat this process to generate another clump of N keys from the previous clump (we can discard some extra keys at the end if N does not divide 84):

• Key (c+1)N + 0 in the new clump is Diffuse[(Diffuse(key (c+1)N-1) >>> 7) xor RoundConstant]
• Key (c+1)N + i for 1 <= i <= N-1 is (Key (c+1)N + i-1 >>> 11) xor (Key cN + i >>> 17) xor RoundConstant

The circular shift constants chosen to be arbitrary primes. This key schedule is somewhat reminiscent of AES's simple key schedule, but with a bit more complexity to hopefully improve security. This key schedule should, in theory, diffuse the key bits well and be decently nonlinear.

The round constant for round i is simply i * 0xa495991b7852b855 (mod 2^64) (number from SHA256 of the empty string).

Usage

cipher.h contains the following functions:

/* Generate the S-box */
void init_s_box();

/*
 * Encrypt a 16-byte block of :plaintext: and write it to :ciphertext:.
 * Requires a pointer to the expanded key.
 * :init_s_box(): must be called before using this function!
 */
void encrypt(void *plaintext, void *ciphertext, void *expanded_key);

/*
 * Decrypt a 16-byte block of :ciphertext: and write it to :plaintext:.
 * Requires a pointer to the expanded key.
 * :init_s_box(): must be called before using this function!
 */
void decrypt(void *ciphertext, void *plaintext, void *expanded_key);

/*
 * Expand the user-supplied key :key: (of length :len: 64-bit words) into :expanded_key:.
 * :expanded_key: must be able to hold 84 round keys of 64 bits each (672 bytes).
 */
void expand_key(void *key, void *expanded_key, int len);

Note that before calling encrypt or decrypt, you must call init_s_box().

You can see an example implementation in main.c.