/* All work, ineffciencies, and bugs Copyright 2001 Abhi Shelat & Kevin Fu May be freely reproduced for educational or personal use November 13, 2001 This code implements a toy block cipher we call "Egg" The cipher seems strong except that it trivially falls to a timing attack. 6.857 Network and Computer Security http://web.mit.edu/6.857/www/ */ import java.io.*; import java.util.*; public class eggSmartCard { static final int ITERATIONS = 3; // Sample secret 256-bit key embedded in smart card. // We will use a different key when grading your code. private static final short key[] = { 0x71, 0x69, 0xCA, 0x35, 0xD1, 0x5E, 0xB3, 0x43, 0x9A, 0xCF, 0x15, 0x49, 0x1B, 0xCF, 0x0E, 0x1E, 0x1D, 0x22, 0x24, 0x37, 0xEC, 0x79, 0xC8, 0x24, 0x67, 0xBF, 0xB1, 0xD1, 0xC8, 0x8E, 0x34, 0x64 }; // Invertible 64x64 bit^2 matrix static short M[][] = { { 78, 224, 218, 29, 178, 124, 46, 167}, { 207, 158, 67, 227, 80, 66, 140, 63}, { 92, 220, 148, 228, 65, 217, 70, 72}, { 243, 100, 120, 199, 28, 214, 169, 63}, { 205, 163, 72, 58, 82, 161, 202, 86}, { 248, 147, 74, 33, 121, 87, 181, 47}, { 65, 127, 0, 38, 147, 114, 73, 58}, { 95, 80, 62, 84, 32, 94, 176, 145}, { 178, 139, 116, 109, 180, 73, 254, 196}, { 245, 242, 244, 180, 2, 170, 232, 170}, { 241, 76, 83, 5, 152, 73, 123, 188}, { 154, 150, 119, 153, 225, 33, 10, 21}, { 53, 179, 78, 50, 204, 239, 127, 164}, { 186, 119, 140, 157, 33, 168, 57, 108}, { 51, 220, 169, 253, 234, 149, 37, 230}, { 136, 248, 76, 243, 228, 217, 20, 34}, { 71, 46, 253, 179, 45, 5, 180, 96}, { 190, 113, 78, 69, 216, 15, 88, 221}, { 178, 40, 57, 220, 255, 4, 193, 148}, { 35, 249, 159, 54, 255, 182, 19, 80}, { 102, 161, 160, 62, 237, 54, 144, 21}, { 198, 196, 229, 147, 127, 236, 221, 73}, { 176, 2, 129, 14, 160, 47, 250, 170}, { 75, 41, 227, 16, 187, 152, 21, 103}, { 50, 68, 231, 193, 152, 227, 255, 198}, { 134, 207, 118, 222, 171, 74, 159, 213}, { 75, 132, 197, 104, 176, 18, 118, 80}, { 232, 152, 61, 222, 122, 28, 49, 85}, { 222, 177, 188, 137, 87, 58, 114, 0}, { 70, 135, 232, 0, 217, 59, 196, 2}, { 68, 112, 71, 113, 174, 31, 101, 24}, { 51, 111, 51, 15, 166, 27, 90, 117}, { 255, 159, 226, 87, 99, 87, 15, 199}, { 120, 198, 68, 117, 220, 38, 134, 62}, { 141, 188, 209, 48, 123, 110, 253, 47}, { 81, 210, 54, 229, 4, 184, 35, 59}, { 91, 70, 96, 211, 91, 24, 197, 52}, { 208, 28, 128, 87, 181, 127, 88, 164}, { 110, 166, 42, 1, 5, 77, 22, 120}, { 15, 63, 38, 216, 124, 138, 115, 154}, { 23, 33, 8, 253, 153, 223, 95, 123}, { 101, 182, 74, 220, 121, 161, 62, 152}, { 98, 5, 133, 170, 130, 211, 80, 199}, { 138, 127, 204, 79, 126, 179, 61, 34}, { 216, 16, 83, 182, 131, 201, 115, 249}, { 89, 137, 78, 89, 100, 181, 136, 142}, { 179, 203, 211, 139, 171, 2, 21, 85}, { 26, 198, 227, 149, 137, 53, 163, 70}, { 145, 231, 123, 205, 225, 22, 194, 221}, { 89, 99, 187, 30, 108, 230, 235, 169}, { 144, 71, 61, 20, 196, 191, 109, 138}, { 114, 201, 76, 38, 12, 103, 49, 84}, { 79, 33, 171, 29, 35, 36, 118, 214}, { 7, 234, 44, 190, 166, 182, 115, 180}, { 116, 112, 223, 222, 34, 184, 44, 84}, { 55, 253, 121, 20, 42, 46, 69, 14}, { 96, 222, 84, 5, 173, 121, 61, 21}, { 82, 186, 93, 70, 58, 61, 176, 42}, { 8, 105, 133, 199, 229, 135, 40, 209}, { 68, 212, 139, 111, 176, 96, 130, 175}, { 87, 179, 192, 78, 10, 112, 135, 131}, { 160, 53, 170, 63, 189, 152, 130, 62}, { 207, 191, 232, 75, 248, 168, 113, 56}, { 162, 127, 154, 196, 242, 29, 249, 165} }; // Inverse of M static short N[][] = { { 220, 243, 144, 114, 88, 178, 131, 57}, { 145, 44, 254, 134, 64, 18, 215, 22}, { 216, 27, 0, 187, 191, 17, 16, 10}, { 203, 90, 189, 225, 13, 1, 84, 75}, { 165, 163, 124, 248, 90, 177, 104, 245}, { 148, 26, 64, 51, 238, 122, 216, 125}, { 228, 95, 152, 222, 225, 78, 244, 55}, { 93, 74, 227, 30, 67, 103, 48, 176}, { 178, 176, 63, 168, 124, 12, 51, 211}, { 30, 22, 188, 188, 86, 116, 31, 153}, { 140, 8, 43, 154, 139, 21, 13, 64}, { 10, 245, 244, 213, 154, 32, 78, 23}, { 244, 237, 206, 2, 172, 12, 154, 78}, { 94, 187, 227, 128, 32, 208, 241, 9}, { 43, 119, 118, 128, 28, 49, 102, 124}, { 115, 4, 251, 139, 200, 135, 243, 97}, { 91, 185, 86, 239, 29, 217, 73, 116}, { 4, 177, 113, 62, 110, 26, 114, 180}, { 84, 161, 3, 77, 92, 1, 23, 227}, { 107, 95, 168, 109, 73, 255, 203, 81}, { 70, 134, 154, 129, 188, 5, 45, 143}, { 102, 104, 197, 28, 172, 53, 161, 83}, { 184, 27, 18, 1, 105, 153, 234, 163}, { 37, 49, 14, 148, 58, 111, 171, 195}, { 118, 75, 151, 160, 30, 140, 80, 18}, { 177, 108, 94, 74, 195, 205, 206, 195}, { 95, 233, 181, 167, 227, 157, 35, 242}, { 81, 129, 196, 197, 69, 0, 219, 191}, { 255, 95, 12, 249, 71, 54, 199, 182}, { 206, 186, 91, 237, 91, 119, 92, 152}, { 128, 247, 12, 115, 29, 138, 85, 221}, { 50, 207, 31, 120, 79, 209, 240, 251}, { 165, 132, 11, 27, 64, 119, 209, 124}, { 10, 31, 100, 109, 173, 58, 152, 227}, { 140, 153, 27, 125, 221, 186, 214, 153}, { 45, 152, 161, 134, 60, 31, 254, 254}, { 239, 7, 181, 2, 68, 156, 12, 190}, { 98, 13, 181, 85, 184, 240, 9, 109}, { 15, 196, 206, 64, 151, 220, 45, 197}, { 79, 224, 176, 181, 107, 234, 74, 191}, { 144, 195, 35, 141, 158, 180, 109, 74}, { 52, 176, 149, 169, 41, 172, 179, 49}, { 187, 154, 84, 216, 216, 165, 63, 103}, { 144, 25, 124, 114, 159, 144, 219, 56}, { 122, 165, 171, 155, 245, 221, 135, 186}, { 14, 172, 149, 165, 31, 208, 216, 121}, { 229, 95, 73, 108, 187, 120, 102, 29}, { 189, 35, 236, 147, 99, 112, 55, 229}, { 152, 112, 120, 223, 163, 34, 253, 217}, { 244, 62, 71, 77, 167, 152, 229, 179}, { 166, 222, 185, 255, 161, 89, 55, 168}, { 61, 27, 64, 215, 76, 52, 13, 67}, { 174, 235, 46, 102, 252, 184, 209, 120}, { 239, 230, 250, 173, 188, 111, 48, 111}, { 53, 116, 48, 100, 125, 96, 107, 209}, { 50, 99, 75, 4, 157, 216, 92, 45}, { 153, 137, 229, 104, 132, 189, 195, 102}, { 39, 110, 88, 65, 9, 33, 252, 238}, { 40, 249, 236, 110, 124, 12, 123, 89}, { 143, 222, 134, 232, 97, 72, 158, 95}, { 248, 225, 181, 146, 79, 167, 221, 161}, { 45, 96, 60, 252, 84, 148, 226, 169}, { 176, 40, 225, 231, 120, 154, 70, 79}, { 226, 225, 12, 88, 183, 1, 72, 176} }; /* This 8-bit S-box comes from Rijndael. It's a permutation of 256 values. This table is easily computed, but it is hardcoded here for convenience. See the AES S-Box on http://home.ecn.ab.ca/~jsavard/crypto/co040801.htm */ static final short sbox[] = { 99, 124, 119, 123, 242, 107, 111, 197, 48, 1, 103, 43, 254, 215, 171, 118, 202, 130, 201, 125, 250, 89, 71, 240, 173, 212, 162, 175, 156, 164, 114, 192, 183, 253, 147, 38, 54, 63, 247, 204, 52, 165, 229, 241, 113, 216, 49, 21, 4, 199, 35, 195, 24, 150, 5, 154, 7, 18, 128, 226, 235, 39, 178, 117, 9, 131, 44, 26, 27, 110, 90, 160, 82, 59, 214, 179, 41, 227, 47, 132, 83, 209, 0, 237, 32, 252, 177, 91, 106, 203, 190, 57, 74, 76, 88, 207, 208, 239, 170, 251, 67, 77, 51, 133, 69, 249, 2, 127, 80, 60, 159, 168, 81, 163, 64, 143, 146, 157, 56, 245, 188, 182, 218, 33, 16, 255, 243, 210, 205, 12, 19, 236, 95, 151, 68, 23, 196, 167, 126, 61, 100, 93, 25, 115, 96, 129, 79, 220, 34, 42, 144, 136, 70, 238, 184, 20, 222, 94, 11, 219, 224, 50, 58, 10, 73, 6, 36, 92, 194, 211, 172, 98, 145, 149, 228, 121, 231, 200, 55, 109, 141, 213, 78, 169, 108, 86, 244, 234, 101, 122, 174, 8, 186, 120, 37, 46, 28, 166, 180, 198, 232, 221, 116, 31, 75, 189, 139, 138, 112, 62, 181, 102, 72, 3, 246, 14, 97, 53, 87, 185, 134, 193, 29, 158, 225, 248, 152, 17, 105, 217, 142, 148, 155, 30, 135, 233, 206, 85, 40, 223, 140, 161, 137, 13, 191, 230, 66, 104, 65, 153, 45, 15, 176, 84, 187, 22 }; static final short sboxInv[] = { 82, 9, 106, 213, 48, 54, 165, 56, 191, 64, 163, 158, 129, 243, 215, 251, 124, 227, 57, 130, 155, 47, 255, 135, 52, 142, 67, 68, 196, 222, 233, 203, 84, 123, 148, 50, 166, 194, 35, 61, 238, 76, 149, 11, 66, 250, 195, 78, 8, 46, 161, 102, 40, 217, 36, 178, 118, 91, 162, 73, 109, 139, 209, 37, 114, 248, 246, 100, 134, 104, 152, 22, 212, 164, 92, 204, 93, 101, 182, 146, 108, 112, 72, 80, 253, 237, 185, 218, 94, 21, 70, 87, 167, 141, 157, 132, 144, 216, 171, 0, 140, 188, 211, 10, 247, 228, 88, 5, 184, 179, 69, 6, 208, 44, 30, 143, 202, 63, 15, 2, 193, 175, 189, 3, 1, 19, 138, 107, 58, 145, 17, 65, 79, 103, 220, 234, 151, 242, 207, 206, 240, 180, 230, 115, 150, 172, 116, 34, 231, 173, 53, 133, 226, 249, 55, 232, 28, 117, 223, 110, 71, 241, 26, 113, 29, 41, 197, 137, 111, 183, 98, 14, 170, 24, 190, 27, 252, 86, 62, 75, 198, 210, 121, 32, 154, 219, 192, 254, 120, 205, 90, 244, 31, 221, 168, 51, 136, 7, 199, 49, 177, 18, 16, 89, 39, 128, 236, 95, 96, 81, 127, 169, 25, 181, 74, 13, 45, 229, 122, 159, 147, 201, 156, 239, 160, 224, 59, 77, 174, 42, 245, 176, 200, 235, 187, 60, 131, 83, 153, 97, 23, 43, 4, 126, 186, 119, 214, 38, 225, 105, 20, 99, 85, 33, 12, 125}; /* Alyssa wanted to use the following array to compute parity. Louis decided that space was more expensive than time and implemented this as a function with a running time linear in the number of one bits in the input. We use this code here, but Louis' smart card hardware actually implements this such that our times are indeed linear in the number of one bits. [use your imagination...] Precomputed parity of a byte. Idea borrowed from VRA cipher. If the number of one bits in the byte is odd. zero otherwise. See "Design of practical and provably good random number generators" by Aiello, Rajagopalan, and Venkatesan */ static final short parityPrecomputed[] = { 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0 }; static int onesIn (short ciphertext[]) { int result = 0; for (int i = 0; i < ciphertext.length; i++) for (int j = 0; j < 8; j++) if (((ciphertext[i] >> j) & 0x01) == 0x01) result++; return result; } // XOR of bits static short parity (short vec) throws Exception { if ((vec < 0) || (vec > 255)) throw new Exception("parity: invalid vector " + vec); return parityPrecomputed [vec]; } // Matrix dot product, mat.v static void f (short mat[][], short v[]) throws Exception { if (v.length != 8) throw new Exception("f: invalid vector length " + v.length); short [] out = new short[8]; for (int j = 0; j < 8; j++) out[j] = 0; // each row i*j for (int i = 0; i < 64; i++) { short product = 0; for (int k = 0; k < 8; k++) product ^= parity ((short) (mat[i][k] & v[k])); out[i/8] |= product << (7 - (i%8)); } for(int j=0; j<8; j++) { v[j]=out[j]; } } // Given plaintext and space to store ciphertext // Return execution time and set the ciphertext appropriately float timeScramble (short plaintext[], short ciphertext[], short akey[], int iterations) throws Exception { float time = (float)0.0; if (plaintext.length != 8) throw new Exception("scramble: invalid plaintext length " + plaintext.length); if (ciphertext.length != 8) throw new Exception("scramble: invalid ciphertext length " + ciphertext.length); if (akey.length < (iterations+1) * 8) throw new Exception("scramble: invalid akey length " + akey.length); for (int j = 0; j < 8; j++) ciphertext[j] = plaintext[j]; for (int i = 0; i < iterations; i++) { // XOR for (int j = 0; j < 8; j++) ciphertext[j] ^= akey[i*8 + j]; // Matrix multiplication in GF(2) time += (float) onesIn (ciphertext); f (M, ciphertext); // Byte substitution (S-Box) for (int j = 0; j < 8; j++) ciphertext[j] = sbox[ciphertext[j]]; } // XOR for (int j = 0; j < 8; j++) ciphertext[j] ^= akey[iterations*8 + j]; return time; } float timeScramble (short plaintext[], short ciphertext[]) throws Exception { return timeScramble (plaintext, ciphertext, this.key, ITERATIONS); } // Given cipher and space to store plaintext // Return execution time and set the plaintext appropriately public float timeUnscramble (short plaintext[], short ciphertext[], short akey[], int iterations) throws Exception { float time = (float)0.0; if (plaintext.length != 8) throw new Exception("scramble: invalid plaintext length " + plaintext.length); if (ciphertext.length != 8) throw new Exception("scramble: invalid ciphertext length " + ciphertext.length); if (akey.length < (iterations+1) * 8) throw new Exception("scramble: invalid akey length " + akey.length); // start of decryption algorithm for (int j = 0; j < 8; j++) { plaintext[j] = ciphertext[j]; } // XOR for (int j = 0; j < 8; j++) plaintext[j] ^= akey[iterations*8 + j]; for (int i = iterations-1; i >= 0; i--) { // Byte substitution (S-Box) for (int j = 0; j < 8; j++) plaintext[j] = sboxInv[plaintext[j]]; // Matrix multiplication in GF(2) time += (float) onesIn (plaintext); f (N, plaintext); // XOR for (int j = 0; j < 8; j++) plaintext[j] ^= akey[i*8 + j]; } return time; } public float timeUnscramble (short plaintext[], short ciphertext[]) throws Exception { return timeUnscramble (plaintext, ciphertext, this.key, ITERATIONS); } }