SEA
The Simple Encryption Algorithm (SEA) is a very very simple symmetrical block cipher designed by me. It has a key and data size of 128-bits, or 16 bytes. It uses some elements from AES, such as a key schedule and the sbox.
Basic concepts
Round IV
Each round has a IV “block”, which is 128 - bits in size. This adds the random factor to this and makes it much harder to decrypt. Unfortunately, this means that in order to decrypt, you need to know two pieces of information: the key, and the round IV for each round.
Key Schedule
The key schedule is a group of keys, one for each round. The key is derived from the previous key by XORing the round IV with the previous key. If the result of the XOR operation is 00, then it is set to 01, because multiplying by 0 in a finite field equals 0 and is irreversible using multiplication, which is not what we want.
Basic operations
SubBytes
SubBytes (substitute bytes) operates on the same idea as AES. In fact, it uses the same sbox table as AES, since the sbox for AES was designed for security.
When encrypting, replace each byte with the corresponding byte in the sbox.
When decrypting, replace each byte with the corresponding byte in the inverse sbox.
MixCells
Here, we rearrange cells within a columns.
The first row remains constant. The second column is shifted by one. The third is shifted by two, and the fourth column is shifted by two. The direction it is shifted depends on whether you are encrypting or decrypting. For encrypting, you shift up. When decrypting, you shift down.
XORBytes
In this step, we XOR the data output from the previous step with the round key. The operations for this step are the same for both encrypting and decrypting.
GaloisMult
In this step, we multiply the output from the previous data by the round key, but not using matrix multiplication. I was unable to calculate the inverse of Galois Field in a spreadsheet due to the limited functions, so this is a compromise.
When encrypting, we multiply by the round key. When decrypting, we multiply by the multiplicative inverse of the round key.
Implementation in Google Sheets
As with the AES post, I will not explain every little detail. Here, I will go over the special things I had to do
GMUL
If you read the AES post first, you might remember that I had a lookup table for multiplication in a Galois Field. However, the table only covered multiplication by 02, 03, 09, 0B, 0D, and 0E. SEA multiplies by any value from 00 to FF, and thus would a require a lookup table of 256^2, which would have 65,536 entries, way too big for a simple lookup.
Unfortunately, this means that we have to use a script. This function takes two hexadecimal strings and multiplies it in a Galois Field of size 2^8, and returns a hexadecimal answer.
The script is below:
function GMUL(a, b) {
// Convert hex strings into decimal numbers
var a = parseInt(a, 16);
var b = parseInt(b, 16);
var v = new Number;
v = 0;
while (b != 0){
if (b & 1)
v ^= a;
b >>= 1;
if (a & (1 << (8 - 1))){
a <<= 1;
a ^= 0x11B;
} else {
a <<= 1;
}
}
// Convert number back to hex, uppercase, and pad with zeros
return pad(v.toString(16).toUpperCase(), 2);
}
For the GaloisMult step, we use this function to calculate the new data. Unfortunately, we pay a heavy price in performance. Recalculating everything takes roughly 10 seconds, compared to nearly instant for the much more complicated AES sheet.
Random IV values
Part of SEA’s strength relies on a random round IV for each round. The spreadsheet provides a button that generates random IV values. When pressed, it calls the following function:
/*
* Generates new random values for the round IV table
*/
function generateIV() {
// Update when IV location in spreadsheet is updated
var ivrange = "Z15:AC30";
var ui = SpreadsheetApp.getUi();
var ss = SpreadsheetApp.getActiveSpreadsheet();
var se = ss.getSheetByName("SEA Encrypt");
var response = ui.alert('Warning! This may take a while! Your spreadsheet WILL need to reload all the values, which can further increase runtime. Continue?', ui.ButtonSet.YES_NO);
// Process the user's response.
if (response == ui.Button.YES) {
var buffer = generateRandomMatrix(0, 255, 16, 4);
var range = se.getRange(ivrange);
var values = range.getValues();
for (var row in values) {
for (var col in values[row]) {
values[row][col] = buffer[row][col];
}
}
range.setValues(values);
ui.alert('IV updated! Make sure to update the input for the decrypting sheet!', ui.ButtonSet.OK);
}
}
Most of it is setup for reading and writing to a spreadsheet. The interesting parts are var buffer = generateRandomMatrix(0, 255, 16, 4); and values[row][col] = buffer[row][col];
generateRandomMatrix is the one that actually matters.
/*
* Generates a matrix with random hex values
* @param {Number} min - Minimum random value (inclusive)
* @param {Number} max - Maximum random value (inclusive)
* @param {Number} rows - Number of rows in the matrix
* @param {Number} columns - Number of columns in the matrix
* @returns {Matrix} - A two dimensional matrix of size row x columns with random values
*/
function generateRandomMatrix(min, max, rows, columns) {
var buffer = [];
for (var i = 0; i < rows; i++) {
buffer[i] = [];
for (var r = 0; r < columns; r++) {
buffer[i][r] = 0;
}
}
for (var row in buffer) {
for (var col in buffer[row]) {
buffer[row][col] = pad((Math.floor(Math.random() * (max - min + 1)) + min).toString(16).toUpperCase(), 2);
Logger.log(buffer[row][col]);
}
}
return buffer;
}
This function generates a matrix filled with random hex values, which is then inserted back into the spreadsheet.
Multiplicative Inverse
There are several approaches to calculating the multiplicative inverse in a Galois Field (from Wikipedia):
- By multiplying a by every number in the field until the product is one. This is a Brute-force search.
- Since the nonzero elements of GF(pn) form a finite group with respect to multiplication, a pn−1 = 1 (for a ≠ 0), thus the inverse of a is a pn−2.
- By using the extended Euclidean algorithm.
- By making a logarithm table of the finite field, and performing subtraction in the table. Subtraction of logarithms is the same as division.
All of those operations are way too slow for Sheets, and most likely impossible. Since there are only 256 values, from 00 to FF, we can do a lookup table.
Here is the Java code to calculate the multiplicative inverse of all numbers from 00 to FF:
public class Tables {
public Tables() {
loadE();
loadL();
loadInv();
loadS();
loadInvS();
loadPowX();
}
public byte[] E = new byte[256]; // "exp" table (base 0x03)
public byte[] L = new byte[256]; // "Log" table (base 0x03)
public byte[] S = new byte[256]; // SubBytes table
public byte[] invS = new byte[256]; // inverse of SubBytes table
public byte[] inv = new byte[256]; // multiplicative inverse table
public byte[] powX = new byte[15]; // powers of x = 0x02
private String[] dig = {"0","1","2","3","4","5","6","7",
"8","9","a","b","c","d","e","f"};
// FFMulFast: fast multiply using table lookup
public byte FFMulFast(byte a, byte b){
int t = 0;;
if (a == 0 || b == 0) return 0;
t = (L[(a & 0xff)] & 0xff) + (L[(b & 0xff)] & 0xff);
if (t > 255) t = t - 255;
return E[(t & 0xff)];
}
// FFMul: slow multiply, using shifting
public byte FFMul(byte a, byte b) {
byte aa = a, bb = b, r = 0, t;
while (aa != 0) {
if ((aa & 1) != 0)
r = (byte)(r ^ bb);
t = (byte)(bb & 0x80);
bb = (byte)(bb << 1);
if (t != 0)
bb = (byte)(bb ^ 0x1b);
aa = (byte)((aa & 0xff) >> 1);
}
return r;
}
// hex: print a byte as two hex digits
public String hex(byte a) {
return dig[(a & 0xff) >> 4] + dig[a & 0x0f];
}
// hex: print a single digit (for tables)
public String hex(int a) {
return dig[a];
}
// loadE: create and load the E table
public void loadE() {
byte x = (byte)0x01;
int index = 0;
E[index++] = (byte)0x01;
for (int i = 0; i < 255; i++) {
byte y = FFMul(x, (byte)0x03);
E[index++] = y;
x = y;
}
}
// loadL: load the L table using the E table
public void loadL() { // careful: had 254 below several places
int index;
for (int i = 0; i < 255; i++) {
L[E[i] & 0xff] = (byte)i;
}
}
// loadS: load in the table S
public void loadS() {
int index;
for (int i = 0; i < 256; i++)
S[i] = (byte)(subBytes((byte)(i & 0xff)) & 0xff);
}
// loadInv: load in the table inv
public void loadInv() {
int index;
for (int i = 0; i < 256; i++)
inv[i] = (byte)(FFInv((byte)(i & 0xff)) & 0xff);
}
// loadInvS: load the invS table using the S table
public void loadInvS() {
int index;
for (int i = 0; i < 256; i++) {
invS[S[i] & 0xff] = (byte)i;
}
}
// loadPowX: load the powX table using multiplication
public void loadPowX() {
int index;
byte x = (byte)0x02;
byte xp = x;
powX[0] = 1; powX[1] = x;
for (int i = 2; i < 15; i++) {
xp = FFMulFast(xp, x);
powX[i] = xp;
}
}
// FFInv: the multiplicative inverse of a byte value
public byte FFInv(byte b) {
byte e = L[b & 0xff];
return E[0xff - (e & 0xff)];
}
// ithBIt: return the ith bit of a byte
public int ithBit(byte b, int i) {
int m[] = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80};
return (b & m[i]) >> i;
}
// subBytes: the subBytes function
public int subBytes(byte b) {
byte inB = b;
int res = 0;
if (b != 0) // if b == 0, leave it alone
b = (byte)(FFInv(b) & 0xff);
byte c = (byte)0x63;
for (int i = 0; i < 8; i++) {
int temp = 0;
temp = ithBit(b, i) ^ ithBit(b, (i+4)%8) ^ ithBit(b, (i+5)%8) ^
ithBit(b, (i+6)%8) ^ ithBit(b, (i+7)%8) ^ ithBit(c, i);
res = res | (temp << i);
}
return res;
}
// printTable: print a 256-byte table
public void printTable(byte[] S, String name) {
for (int i = 0; i < 256; i++) {
System.out.println(i + "," + hex(S[i]));
}
}
// printL: print the L table
public void printL() {
printTable(L, "L");
}
// printE: print the E table
public void printE() {
printTable(E, "E");
}
// printS: print the S table
public void printS() {
printTable(S, "S");
}
// printInv: print the inv table
public void printInv() {
printTable(inv, "inv");
}
// printInvS: print the invS table
public void printInvS() {
printTable(invS, "iS");
}
public static void main(String[] args) {
Tables sB = new Tables();
// sB.printL();
// sB.printE();
// sB.printS();
// sB.printInvS();
sB.printInv();
// sB.printPowX();
}
}