Advertisement
Guest User

Untitled

a guest
Apr 11th, 2015
316
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 28.15 KB | None | 0 0
  1. #include <stdint.h>
  2. #include <stdlib.h>
  3. #include <stdio.h>
  4. #include <memory.h>
  5. #include <string.h>
  6. #include <inttypes.h>
  7.  
  8. #define ROUNDS 16
  9.  
  10. //128-bit integers are necessary for full-compliance, but there is not a single
  11. //use-case I know of that needs to support encrypting more than 2^64-1 bytes
  12. #ifdef __GNUC__
  13. typedef unsigned __int128 u128;
  14. #else
  15. typedef uint64_t u128;
  16. #endif
  17.  
  18. typedef uint8_t byte;
  19.  
  20. typedef struct
  21. {
  22.     byte elements[16];
  23. } vector;
  24.  
  25. enum direction
  26. {
  27.     ENCRYPT,
  28.     DECRYPT
  29. };
  30.  
  31. typedef struct state
  32. {
  33.     vector key_schedule[ROUNDS+3][2];
  34.     vector nonce;
  35.     vector mac;
  36.  
  37.     u128 counter;
  38.     u128 length;
  39.  
  40.     vector (*crypt)(vector x, uint8_t block_len, struct state *s);
  41.     enum direction direction;
  42.     char buffer[16];
  43.     uint8_t buffer_len;
  44. } state;
  45.  
  46. /* For internal use only */
  47. static const vector null_vector = {.elements={0}};
  48.  
  49. //The main linear transformation, T, is a 16x16 Matrix modulo 256
  50. //Every square nxn submatrix composed of the columns 0..n-1 and rows 0..n-1 are invertible
  51. //This is a permutation of a circulant matrix composed of the first 16 prime numbers in order
  52. //from least to greatest. The permutation is simply swapping the first and last rows
  53. //which is necessary so that a two is not at position 0,0 since two does not have a
  54. //multiplicative inverse mod 256
  55. static const byte T[16][16] = {
  56.     { 3,  5,  7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,  2},
  57.     {53,  2,  3,  5,  7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47},
  58.     {47, 53,  2,  3,  5,  7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43},
  59.     {43, 47, 53,  2,  3,  5,  7, 11, 13, 17, 19, 23, 29, 31, 37, 41},
  60.     {41, 43, 47, 53,  2,  3,  5,  7, 11, 13, 17, 19, 23, 29, 31, 37},
  61.     {37, 41, 43, 47, 53,  2,  3,  5,  7, 11, 13, 17, 19, 23, 29, 31},
  62.     {31, 37, 41, 43, 47, 53,  2,  3,  5,  7, 11, 13, 17, 19, 23, 29},
  63.     {29, 31, 37, 41, 43, 47, 53,  2,  3,  5,  7, 11, 13, 17, 19, 23},
  64.     {23, 29, 31, 37, 41, 43, 47, 53,  2,  3,  5,  7, 11, 13, 17, 19},
  65.     {19, 23, 29, 31, 37, 41, 43, 47, 53,  2,  3,  5,  7, 11, 13, 17},
  66.     {17, 19, 23, 29, 31, 37, 41, 43, 47, 53,  2,  3,  5,  7, 11, 13},
  67.     {13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,  2,  3,  5,  7, 11},
  68.     {11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,  2,  3,  5,  7},
  69.     { 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,  2,  3,  5},
  70.     { 5,  7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,  2,  3},
  71.     { 2,  3,  5,  7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53}
  72. };
  73.  
  74. //The inverse of T
  75. static const byte T_inv[16][16] = {
  76.     {131, 125,  39,  97,  65, 243, 115, 149,  53, 163, 245, 179,  27, 181, 253, 196},
  77.     {253, 196, 125,  39,  97,  65, 243, 115, 149,  53, 163, 245, 179,  27, 181, 131},
  78.     {181, 131, 196, 125,  39,  97,  65, 243, 115, 149,  53, 163, 245, 179,  27, 253},
  79.     { 27, 253, 131, 196, 125,  39,  97,  65, 243, 115, 149,  53, 163, 245, 179, 181},
  80.     {179, 181, 253, 131, 196, 125,  39,  97,  65, 243, 115, 149,  53, 163, 245,  27},
  81.     {245,  27, 181, 253, 131, 196, 125,  39,  97,  65, 243, 115, 149,  53, 163, 179},
  82.     {163, 179,  27, 181, 253, 131, 196, 125,  39,  97,  65, 243, 115, 149,  53, 245},
  83.     { 53, 245, 179,  27, 181, 253, 131, 196, 125,  39,  97,  65, 243, 115, 149, 163},
  84.     {149, 163, 245, 179,  27, 181, 253, 131, 196, 125,  39,  97,  65, 243, 115,  53},
  85.     {115,  53, 163, 245, 179,  27, 181, 253, 131, 196, 125,  39,  97,  65, 243, 149},
  86.     {243, 149,  53, 163, 245, 179,  27, 181, 253, 131, 196, 125,  39,  97,  65, 115},
  87.     { 65, 115, 149,  53, 163, 245, 179,  27, 181, 253, 131, 196, 125,  39,  97, 243},
  88.     { 97, 243, 115, 149,  53, 163, 245, 179,  27, 181, 253, 131, 196, 125,  39,  65},
  89.     { 39,  65, 243, 115, 149,  53, 163, 245, 179,  27, 181, 253, 131, 196, 125,  97},
  90.     {125,  97,  65, 243, 115, 149,  53, 163, 245, 179,  27, 181, 253, 131, 196,  39},
  91.     {196,  39,  97,  65, 243, 115, 149,  53, 163, 245, 179,  27, 181, 253, 131, 125}
  92. };
  93.  
  94. //S{N}_inv is the inverse of the nxn matrix composed of rows 0..n-1 and columns 0..n-1
  95. static const byte S15_inv[15][15] = {
  96.     { 51, 113, 147,  77,  69, 247, 207, 113, 121, 127, 249, 151, 247, 241, 193},
  97.     {193, 235, 222, 104,  84, 180, 136, 168,  56,  42,  86,  16, 104,  24,  56},
  98.     {241, 220, 227, 188, 180, 110,  44,  62,  80,  32,   2,   8, 192,  54,  24},
  99.     {247, 174, 138, 235,  66, 108,  84, 148, 136,   6, 154,  18, 118, 192, 104},
  100.     {151, 148, 230,  76, 207,   8, 228, 190, 124,  16,  62,   8,  18,   8,  16},
  101.     {249, 178,  38,  78, 166, 103,  98, 172,  52, 134, 214,  62, 154,   2,  86},
  102.     {127, 164, 226, 156,   2,   8, 119, 144, 252, 180, 134,  16,   6,  32,  42},
  103.     {121, 188, 116, 188, 200, 144, 248, 217,  64, 252,  52, 124, 136,  80,  56},
  104.     {113, 212, 124,  90,  96, 122, 112,  86, 217, 144, 172, 190, 148,  62, 168},
  105.     {207,  70,  74, 188,  88,  64, 200, 112, 248, 119,  98, 228,  84,  44, 136},
  106.     {247, 236, 230,  52, 216,  22,  64, 122, 144,   8, 103,   8, 108, 110, 180},
  107.     { 69,  74, 198,  70,   6, 216,  88,  96, 200,   2, 166, 207,  66, 180,  84},
  108.     { 77, 192, 126,  64,  70,  52, 188,  90, 188, 156,  78,  76, 235, 188, 104},
  109.     {147, 174,  94, 126, 198, 230,  74, 124, 116, 226,  38, 230, 138, 227, 222},
  110.     {113, 220, 174, 192,  74, 236,  70, 212, 188, 164, 178, 148, 174, 220, 235}
  111. };
  112. static const byte S14_inv[14][14] = {
  113.     {224, 221, 137,  13, 103,  51, 253, 245,  69, 147, 227, 219, 237,  93},
  114.     {153, 139, 174, 104, 196, 212, 152, 136, 216, 138, 134, 240,  56, 184},
  115.     { 41, 252, 243, 188, 228,  14, 124, 158, 112,   0, 242, 104, 208,  86},
  116.     { 63, 142, 122, 235,  18, 204,   4,  52, 104,  38, 170, 178, 102, 160},
  117.     {103,  84,  70,  76, 239, 200, 196, 254,  60,  80, 222,  72, 114, 200},
  118.     {151, 250, 202, 206,  18, 143, 214,   4, 188,  62, 114,  22,  62,  74},
  119.     { 97,  92,  62,  28, 150, 224,   3,  56, 116, 252, 234,  56,  98, 216},
  120.     { 81,  92,  68, 188,  56, 176,   8, 185, 224,  92, 100,  92,  88, 240},
  121.     {249, 180, 236,  90, 176, 218, 160, 246, 185, 176,  60,  94,   4,  30},
  122.     {183, 166, 250, 188, 104,  32,  56, 144,  88,  23, 178,   4,   4, 140},
  123.     {155, 220, 222,  52, 192,  70, 152,  74,   0,  24, 239, 216, 100,  94},
  124.     {  9, 186, 126,  70,  46, 136, 112, 176, 184, 146, 110,  31, 250,  36},
  125.     {149, 160, 110,  64,  22, 148, 108, 250, 156, 188,  94, 236, 219, 156},
  126.     { 25,  86, 178, 254,  66, 238,  46, 244,  92,  58,  18, 222, 222, 139}
  127. };
  128. static const byte S13_inv[13][13] = {
  129.     {  1,  99,  75, 123,  57,  17,  27, 137, 129,  29,   5,  41,  59},
  130.     {177,  27, 222, 184, 116, 164, 104, 104, 120, 122, 182,  64, 136},
  131.     { 55, 208,  15,  64, 224, 178, 160, 182, 184,  12,  78,  44, 148},
  132.     { 95,  78, 186, 171,  82, 140, 196, 180, 232, 102, 234, 114,  38},
  133.     {207, 196,  22, 252,  63, 248, 244,  30, 156,  96, 174, 248,  34},
  134.     {169, 230, 238,  10,  86, 171, 114, 108, 244, 114,  86,  18,  58},
  135.     { 25, 172, 174,  44, 134, 112, 147, 152, 148,  44,  90,  72, 114},
  136.     {  1, 124, 164,  92, 152,  80, 168, 121,  32,  60, 196, 252, 248},
  137.     {111, 248, 216, 142, 252, 174, 244,  46,  97, 204, 104, 210, 120},
  138.     { 51, 142, 242,   4,  32, 168, 192,  64, 104, 239,  42, 204, 204},
  139.     { 81, 160,  74, 232, 140, 154, 108, 130, 168, 180, 155, 204,  88},
  140.     {253, 114, 102,  30,  86,  32,   8, 192, 232,  26, 214, 119,  82},
  141.     { 97, 104,   6, 232, 110, 124,  84, 234, 108, 180, 118,  20,   3}
  142. };
  143. static const byte S12_inv[12][12] = {
  144.     { 56, 187, 213,  83,  27,  53, 167, 143,  53,  73, 159, 245},
  145.     {217,  91, 206, 248, 164,   4, 136, 248,  88, 154,  38,  96},
  146.     {219, 112, 231, 224,  88,  34, 112, 158, 232,  92, 230, 252},
  147.     { 61, 126, 110, 219,  54,  20, 156,  32, 144, 126, 190, 202},
  148.     {217, 212, 210,  12,  11, 208,  60, 194, 212, 104, 202, 192},
  149.     {171, 182, 122, 218, 178, 163,  26, 192, 204, 218, 194,  58},
  150.     {179,  60, 202, 188,  50,   8,  27, 220, 140, 116, 214,  80},
  151.     { 89,  60, 180,  28, 104, 240, 136, 233,  64,  28,  84, 220},
  152.     { 71, 184, 232,  78, 204,  78, 212, 158, 129, 172, 248, 178},
  153.     {111, 238,  90, 100, 232, 184, 112,  24, 184,  31, 210, 124},
  154.     {137,  96, 154, 168, 156, 186, 204, 178,  72,  20, 107,  44},
  155.     {247,   2, 194, 174,  66,  56,  16, 196,  96, 226, 146, 255}
  156. };
  157. static const byte S11_inv[11][11] = {
  158.     {155, 165, 127, 217,  69, 205, 247,  35,  21, 147,  89},
  159.     {121,  27, 142,  56, 100,   4, 136, 120,  88,  90, 230},
  160.     {255, 104, 223,  40,  80,  66,  48, 142, 104, 212, 158},
  161.     { 35,  18, 130,  39,  74,  68,  60, 200,  80, 210, 242},
  162.     { 25,  84,  82, 140, 139, 208,  60, 194, 212, 232,  74},
  163.     {161,  42, 110,  70, 166,  83, 186,  40, 140,  14, 214},
  164.     {227, 220, 106,  28, 210, 136,  27,  28, 140,  20, 118},
  165.     {157, 244, 108, 164,  32,  16,  72,  89, 192,  84, 204},
  166.     {  5,  28, 204,  74, 176,  62, 244, 230,  65, 208, 124},
  167.     { 19, 230,  82, 172, 224, 216,  48,   8,  56, 151, 138},
  168.     {253, 184, 242, 144, 244,  90, 140,  98, 200, 236, 131}
  169. };
  170. static const byte S10_inv[10][10] = {
  171.     {116, 253, 201,  41, 169,  95,  19,  29,  61, 143},
  172.     { 95, 171, 106,  24, 252,  16, 240, 116, 200,   2},
  173.     {157,  56, 107, 136, 200, 190, 184, 186, 152, 156},
  174.     { 21, 194, 150, 199,  18, 232, 116,  60, 160, 202},
  175.     { 99,  68,  86, 172, 179,  36,  20, 166, 228, 128},
  176.     {119,  58, 170,  38, 254,  63,  98, 132, 124, 246},
  177.     { 89, 236, 230, 252, 170, 180,  67, 184, 124, 124},
  178.     {105,  20,  36, 100,  80,  40,  24,  81, 160, 164},
  179.     {129, 188, 100,  10, 160, 182,   4, 190, 161,  96},
  180.     {157, 214, 214, 204,   8, 172,   8, 108,  72,  47}
  181. };
  182. static const byte S9_inv[9][9] = {
  183.     {183, 103,  51, 221, 161,  51,  11,  49, 245},
  184.     {121, 151,  86,  48,  12, 232,   0, 204,  88},
  185.     {137,  32,  83, 216, 168, 142, 152, 138, 120},
  186.     { 87, 222, 178,  63,  98,  32, 196, 244, 112},
  187.     {227,  68,  86, 172, 179,  36,  20, 166, 228},
  188.     {245, 158,  14, 174, 174,   7,  18, 204, 172},
  189.     {165,  20,  14, 204, 138,   4,  35,   8,  92},
  190.     {189, 172, 188,  20, 112,  88,  56, 129, 192},
  191.     { 97, 252, 164, 138, 160,  54,   4,  62, 161}
  192. };
  193. static const byte S8_inv[8][8] = {
  194.     {  2, 187, 191,  11, 129,  69, 183, 155},
  195.     { 33, 247, 246, 192,  12,  88, 160, 124},
  196.     { 17,   0, 115,  40, 168,  62, 184, 122},
  197.     {231, 158, 242, 223,  98, 128,   4, 212},
  198.     {255, 212,  70, 196,  51,  12, 132, 110},
  199.     { 73,  78, 222, 246,  46, 191,  98,  36},
  200.     { 73, 132,  30,  52,  10, 156, 179, 192},
  201.     {253, 172, 188, 148, 112, 216,  56,   1}
  202. };
  203. static const byte S7_inv[7][7] = {
  204.     {211, 151, 235, 111, 177, 125, 207},
  205.     {149, 167, 230,  16, 204, 184, 128},
  206.     {127,   8, 219, 160,  72,  78,   8},
  207.     { 99,  46,  66,  79, 162, 160, 164},
  208.     { 73, 236, 126,  44,  19,  60, 116},
  209.     {181,  30, 110,  38, 110,  95, 130},
  210.     {137, 132,  30,  52,  10, 156, 179}
  211. };
  212. static const byte S6_inv[6][6] = {
  213.     { 54,  67,  53, 171,  31,  49},
  214.     { 21, 167, 230,  16, 204, 184},
  215.     {231, 168, 139, 192, 216, 174},
  216.     { 55, 254,  90, 223, 170,  80},
  217.     {173, 252, 118, 252, 187, 172},
  218.     {143,  70, 154,  46, 210, 119}
  219. };
  220. static const byte S5_inv[5][5] = {
  221.     {221, 249,  95, 137,  65},
  222.     {157, 119,  22, 160,  60},
  223.     {  9, 156, 215, 228, 180},
  224.     {103, 222, 122,  63,  74},
  225.     { 33, 196,  46, 164,  19}
  226. };
  227. static const byte S4_inv[4][4] = {
  228.     {162,  77,   5,  61},
  229.     {201,  39, 254, 208},
  230.     {141, 172, 143, 116},
  231.     {217,  38, 118,  71}
  232. };
  233. static const byte S3_inv[3][3] = {
  234.     {127, 203,  19},
  235.     {153,   7, 222},
  236.     {129, 164, 199}
  237. };
  238. static const byte S2_inv[2][2] = {
  239.     {170,  87},
  240.     {103, 255}
  241. };
  242. static const byte S1_inv = 171;
  243.  
  244. //Lookup table for multiplicative inverse modulo 257
  245. static const byte mult_inv_mod257[256] = {
  246.       0, 128,  85, 192, 102,  42, 146, 224, 199, 179, 186, 149, 177, 201, 119, 240,
  247.     120,  99, 229,  89,  48, 221, 189,  74,  71,  88, 237, 100, 194,  59, 198, 248,
  248.     147, 188, 234,  49, 131, 114, 144,  44, 162, 152,   5, 110,  39,  94, 174, 165,
  249.      20,  35, 125, 172,  96, 118, 242, 178, 247, 225,  60,  29,  58, 227, 101, 252,
  250.      86,  73, 233, 222, 148, 245, 180,  24, 168,  65,  23, 185, 246, 200, 243, 150,
  251.     164, 209,  95, 204, 126,   2,  64, 183,  25,  19, 208, 175, 151, 215,  45,  82,
  252.      52, 138, 134,  17,  27,  62,   4, 214, 163, 176, 244, 187, 223, 249,  43, 217,
  253.     115, 123,  37, 112, 133, 158,  53,  14,  16, 157, 139, 113, 219,  50,  84, 254,
  254.       1, 171, 205,  36, 142, 116,  98, 239, 241, 202,  97, 122, 143, 218, 132, 140,
  255.      38, 212,   6,  32,  68,  11,  79,  92,  41, 251, 193, 228, 238, 121, 117, 203,
  256.     173, 210,  40, 104,  80,  47, 236, 230,  72, 191, 253, 129,  51, 160,  46,  91,
  257.     105,  12,  55,   9,  70, 232, 190,  87, 231,  75,  10, 107,  33,  22, 182, 169,
  258.       3, 154,  28, 197, 226, 195,  30,   8,  77,  13, 137, 159,  83, 130, 220, 235,
  259.      90,  81, 161, 216, 145, 250, 103,  93, 211, 111, 141, 124, 206,  21,  67, 108,
  260.       7,  57, 196,  61, 155,  18, 167, 184, 181,  66,  34, 207, 166,  26, 156, 135,
  261.      15, 136,  54,  78, 106,  69,  76,  56,  31, 109, 213, 153,  63, 170, 127, 255
  262. };
  263.  
  264. //To perform multiplication modulo 2^257, we convert to 16-bit integers and add 1,
  265. //guaranteeing that we don't perform multiplication by zero. When we are done, we subtract 1
  266. //so that the result is in the range 0..255
  267. static byte multiply_mod257(uint16_t x, uint16_t y)
  268. {
  269.     return ((x + 1) * (y + 1)) % 257 - 1;
  270. }
  271.  
  272. static byte rotl(byte x, byte r)
  273. {
  274.     return (x << r) | (x >> (8-r));
  275. }
  276.  
  277. static byte rotr(byte x, byte r)
  278. {
  279.     return (x >> r) | (x << (8-r));
  280. }
  281.  
  282. static vector u128_to_vector(u128 x)
  283. {
  284.     int i;
  285.     vector t;
  286.     for (i=15; i>=0; i--)
  287.     {
  288.         t.elements[i] = x & 0xFF;
  289.         x >>= 8;
  290.     }
  291.     return t;
  292. }
  293.  
  294. static vector vector_xor(vector x, vector y)
  295. {
  296.     int i;
  297.     for (i=0; i<16; i++)
  298.     {
  299.         x.elements[i] ^= y.elements[i];
  300.     }
  301.     return x;
  302. }
  303.  
  304. static vector vector_multiply(vector x, vector y)
  305. {
  306.     int i;
  307.     for (i=0; i<16; i++)
  308.     {
  309.         x.elements[i] = multiply_mod257(x.elements[i], y.elements[i]);
  310.     }
  311.     return x;
  312. }
  313.  
  314. static vector vector_multiply_inv(vector x, vector y)
  315. {
  316.     int i;
  317.     for (i=0; i<16; i++)
  318.     {
  319.         x.elements[i] = multiply_mod257(x.elements[i], mult_inv_mod257[y.elements[i]]);
  320.     }
  321.     return x;
  322. }
  323.  
  324. //Matrix-multiplication mod 256
  325. static vector matrix_multiply(vector x)
  326. {
  327.     int i,j;
  328.     vector t;
  329.     for (i=0; i<16; i++)
  330.     {
  331.         t.elements[i] = x.elements[0]*T[i][0];
  332.         for (j=1; j<16; j++)
  333.         {
  334.             t.elements[i] += x.elements[j]*T[i][j];
  335.         }
  336.     }
  337.     return t;
  338. }
  339.  
  340. static vector matrix_multiply_inv(vector x, byte block_len)
  341. {
  342.     int i, j;
  343.     vector t;
  344.  
  345.     //If we are decrypting a partial-length block, first remove the contribution
  346.     //from the key before multiplying by the inverse of the submatrix
  347.     for (i=0; i<block_len; i++)
  348.     {
  349.         t.elements[i] = x.elements[i];
  350.         for (j=block_len; j<16; j++)
  351.         {
  352.             t.elements[i] -= x.elements[j]*T[i][j];
  353.         }
  354.     }
  355.    
  356.     //For partial length blocks, perform matrix multiplication using the inverse of the
  357.     //relevant submatrix (S{N}_inv). For full-length blocks, perform matrix multiplication
  358.     //by T_inv
  359.     switch (block_len)
  360.     {
  361.         case 1:
  362.             x.elements[0] = t.elements[0]*S1_inv;
  363.             break;
  364.         case 2:
  365.             for (i=0; i<2; i++)
  366.             {
  367.                 x.elements[i] = t.elements[0]*S2_inv[i][0];
  368.                 for (j=1; j<2; j++)
  369.                 {
  370.                     x.elements[i] += t.elements[j]*S2_inv[i][j];
  371.                 }
  372.             }
  373.             break;
  374.         case 3:
  375.             for (i=0; i<3; i++)
  376.             {
  377.                 x.elements[i] = t.elements[0]*S3_inv[i][0];
  378.                 for (j=1; j<3; j++)
  379.                 {
  380.                     x.elements[i] += t.elements[j]*S3_inv[i][j];
  381.                 }
  382.             }
  383.             break;
  384.         case 4:
  385.             for (i=0; i<4; i++)
  386.             {
  387.                 x.elements[i] = t.elements[0]*S4_inv[i][0];
  388.                 for (j=1; j<4; j++)
  389.                 {
  390.                     x.elements[i] += t.elements[j]*S4_inv[i][j];
  391.                 }
  392.             }
  393.             break;
  394.         case 5:
  395.             for (i=0; i<5; i++)
  396.             {
  397.                 x.elements[i] = t.elements[0]*S5_inv[i][0];
  398.                 for (j=1; j<5; j++)
  399.                 {
  400.                     x.elements[i] += t.elements[j]*S5_inv[i][j];
  401.                 }
  402.             }
  403.             break;
  404.         case 6:
  405.             for (i=0; i<6; i++)
  406.             {
  407.                 x.elements[i] = t.elements[0]*S6_inv[i][0];
  408.                 for (j=1; j<6; j++)
  409.                 {
  410.                     x.elements[i] += t.elements[j]*S6_inv[i][j];
  411.                 }
  412.             }
  413.             break;
  414.         case 7:
  415.             for (i=0; i<7; i++)
  416.             {
  417.                 x.elements[i] = t.elements[0]*S7_inv[i][0];
  418.                 for (j=1; j<7; j++)
  419.                 {
  420.                     x.elements[i] += t.elements[j]*S7_inv[i][j];
  421.                 }
  422.             }
  423.             break;
  424.         case 8:
  425.             for (i=0; i<8; i++)
  426.             {
  427.                 x.elements[i] = t.elements[0]*S8_inv[i][0];
  428.                 for (j=1; j<8; j++)
  429.                 {
  430.                     x.elements[i] += t.elements[j]*S8_inv[i][j];
  431.                 }
  432.             }
  433.             break;
  434.         case 9:
  435.             for (i=0; i<9; i++)
  436.             {
  437.                 x.elements[i] = t.elements[0]*S9_inv[i][0];
  438.                 for (j=1; j<9; j++)
  439.                 {
  440.                     x.elements[i] += t.elements[j]*S9_inv[i][j];
  441.                 }
  442.             }
  443.             break;
  444.         case 10:
  445.             for (i=0; i<10; i++)
  446.             {
  447.                 x.elements[i] = t.elements[0]*S10_inv[i][0];
  448.                 for (j=1; j<10; j++)
  449.                 {
  450.                     x.elements[i] += t.elements[j]*S10_inv[i][j];
  451.                 }
  452.             }
  453.             break;
  454.         case 11:
  455.             for (i=0; i<11; i++)
  456.             {
  457.                 x.elements[i] = t.elements[0]*S11_inv[i][0];
  458.                 for (j=1; j<11; j++)
  459.                 {
  460.                     x.elements[i] += t.elements[j]*S11_inv[i][j];
  461.                 }
  462.             }
  463.             break;
  464.         case 12:
  465.             for (i=0; i<12; i++)
  466.             {
  467.                 x.elements[i] = t.elements[0]*S12_inv[i][0];
  468.                 for (j=1; j<12; j++)
  469.                 {
  470.                     x.elements[i] += t.elements[j]*S12_inv[i][j];
  471.                 }
  472.             }
  473.             break;
  474.         case 13:
  475.             for (i=0; i<13; i++)
  476.             {
  477.                 x.elements[i] = t.elements[0]*S13_inv[i][0];
  478.                 for (j=1; j<13; j++)
  479.                 {
  480.                     x.elements[i] += t.elements[j]*S13_inv[i][j];
  481.                 }
  482.             }
  483.             break;
  484.         case 14:
  485.             for (i=0; i<14; i++)
  486.             {
  487.                 x.elements[i] = t.elements[0]*S14_inv[i][0];
  488.                 for (j=1; j<14; j++)
  489.                 {
  490.                     x.elements[i] += t.elements[j]*S14_inv[i][j];
  491.                 }
  492.             }
  493.             break;
  494.         case 15:
  495.             for (i=0; i<15; i++)
  496.             {
  497.                 x.elements[i] = t.elements[0]*S15_inv[i][0];
  498.                 for (j=1; j<15; j++)
  499.                 {
  500.                     x.elements[i] += t.elements[j]*S15_inv[i][j];
  501.                 }
  502.             }
  503.             break;
  504.         case 16:
  505.             for (i=0; i<16; i++)
  506.             {
  507.                 x.elements[i] = t.elements[0]*T_inv[i][0];
  508.                 for (j=1; j<16; j++)
  509.                 {
  510.                     x.elements[i] += t.elements[j]*T_inv[i][j];
  511.                 }
  512.             }
  513.             break;
  514.     }
  515.     return x;
  516. }
  517. void print_vector(vector x, uint8_t vector_length, int round)
  518. {
  519.     int i;
  520.     fprintf(stderr, "%d: ", round);
  521.     for (i=0; i<vector_length; i++)
  522.     {
  523.         fprintf(stderr,"%02"PRIx8, x.elements[i]);
  524.     }
  525.     fprintf(stderr, "\n");
  526. }
  527.  
  528. static vector encrypt(vector x, uint8_t block_len, state *s)
  529. {
  530.     vector tweak[2];
  531.     int i, j;
  532.    
  533.     //Compute tweak values from the nonce and counter
  534.     //This is an invertible operation to guarantee no two combinations of nonce/counter
  535.     //will result in identical tweak values
  536.    
  537.     tweak[0] = u128_to_vector(s->counter);
  538.     tweak[1] = s->nonce;
  539.     for (i=0; i<2; i++)
  540.     {
  541.         tweak[0] = vector_xor(tweak[0], s->key_schedule[i][0]);
  542.         tweak[1] = vector_xor(tweak[1], s->key_schedule[i][1]);
  543.         tweak[0] = vector_multiply(tweak[0], tweak[1]);
  544.         tweak[0] = matrix_multiply(tweak[0]);
  545.         tweak[1] = vector_multiply(tweak[1], tweak[0]);
  546.         tweak[1] = matrix_multiply(tweak[1]);
  547.     }
  548.     //Make sure trailing bytes of x are all zero
  549.     for (j=block_len; j<16; j++)
  550.     {
  551.         x.elements[j] = 0;
  552.     }
  553.    
  554.     //Perform the actual encryption rounds
  555.     for (i=2; i<ROUNDS+2; i++)
  556.     {
  557.         //Key mixing operations, first XOR by one subkey, then multiply by a second
  558.         //subkey xor'd to a tweek value, modulo 257
  559.         x = vector_multiply(
  560.                 vector_xor(x, s->key_schedule[i][0]),
  561.                 vector_xor(tweak[i%2], s->key_schedule[i][1]));
  562.  
  563.         //Rotate the bytes by between 1 and 7 bits
  564.         //This helps to provide diffusion at a bit level, as multiplication modulo 257 doesn't
  565.         //guarantee that we will achieve that since the coefficients are dependent entirely
  566.         //on the key and tweek; although it is likely that it would be sufficient alone,
  567.         //this provides extra assurance
  568.         for (j=0; j<16; j++)
  569.         {
  570.             x.elements[j] = rotl(x.elements[j],(5*(i-2)+3*j)%7+1);
  571.         }
  572.  
  573.         x = matrix_multiply(x);
  574.        
  575.         //After each matrix multiplication, we need to 0 out the extra bytes otherwise
  576.         //we will not be able to decrypt it
  577.         for (j=block_len; j<16; j++)
  578.         {
  579.             x.elements[j] = 0;
  580.         }
  581.  
  582.         //After half the rounds, xor the partially encrypted block to the MAC
  583.         if (i-2 == ROUNDS/2)
  584.         {
  585.             s->mac = vector_xor(s->mac, x);
  586.         }
  587.     }
  588.  
  589.     //Perform output whitening before returning
  590.     x = vector_multiply(
  591.             vector_xor(x, s->key_schedule[ROUNDS+2][0]),
  592.             vector_xor(tweak[0], s->key_schedule[ROUNDS+2][1]));
  593.     return x;
  594. }
  595.  
  596. static vector decrypt(vector x, uint8_t block_len, state *s)
  597. {
  598.     vector tweak[2];
  599.     vector temp;
  600.     int i, j;
  601.  
  602.     //Compute tweak values from the nonce and counter
  603.     //This is an invertible operation to guarantee no two combinations of nonce/counter
  604.     //will result in identical tweak values
  605.    
  606.     tweak[0] = u128_to_vector(s->counter);
  607.     tweak[1] = s->nonce;
  608.     for (i=0; i<2; i++)
  609.     {
  610.         tweak[0] = vector_xor(tweak[0], s->key_schedule[i][0]);
  611.         tweak[1] = vector_xor(tweak[1], s->key_schedule[i][1]);
  612.         tweak[0] = vector_multiply(tweak[0], tweak[1]);
  613.         tweak[0] = matrix_multiply(tweak[0]);
  614.         tweak[1] = vector_multiply(tweak[1], tweak[0]);
  615.         tweak[1] = matrix_multiply(tweak[1]);
  616.     }
  617.    
  618.     //Remove output whitening
  619.     x = vector_xor(
  620.             vector_multiply_inv(x, vector_xor(tweak[0], s->key_schedule[ROUNDS+2][1])),
  621.             s->key_schedule[ROUNDS+2][0]);
  622.  
  623.     for (i=ROUNDS+1; i>=2; i--)
  624.     {
  625.         //After half the rounds, xor the partially decrypted block to the MAC
  626.         if (i-2 == ROUNDS/2)
  627.         {
  628.             s->mac = vector_xor(s->mac, x);
  629.         }
  630.  
  631.         //We need to perform the key mixing opertation from the encryption on a null vector
  632.         //and then set the trailing bytes of the key to that before we can invert the
  633.         //matrix multiplication
  634.         temp = null_vector;
  635.         temp = vector_multiply(
  636.                 vector_xor(temp, s->key_schedule[i][0]),
  637.                 vector_xor(tweak[i%2], s->key_schedule[i][1]));
  638.  
  639.         for (j=block_len; j<16; j++)
  640.         {
  641.             x.elements[j] = rotl(temp.elements[j],(5*(i-2)+3*j)%7+1);
  642.         }
  643.    
  644.         x = matrix_multiply_inv(x, block_len);
  645.  
  646.         //Rotate the bytes right by between 1 and 7 bits
  647.         for (j=0; j<16; j++)
  648.         {
  649.             x.elements[j] = rotr(x.elements[j], (5*(i-2)+3*j)%7+1);
  650.         }
  651.  
  652.         //Perform the inverse of the key mixing operation
  653.         x = vector_xor(
  654.                 vector_multiply_inv(x, vector_xor(tweak[i%2], s->key_schedule[i][1])),
  655.                 s->key_schedule[i][0]);
  656.  
  657.     }
  658.     return x;
  659. }
  660.  
  661. /* API Functions */
  662.  
  663. void reinit(state *s, vector nonce, enum direction direction)
  664. {
  665.     s->nonce = nonce;
  666.     s->mac = null_vector;
  667.     s->counter = 0;
  668.     s->length = 0;
  669.     s->buffer_len = 0;
  670.     s->direction = direction;
  671.     if (direction == ENCRYPT)
  672.     {
  673.         s->crypt = &encrypt;
  674.     }
  675.     else
  676.     {
  677.         s->crypt = &decrypt;
  678.     }
  679. }
  680.  
  681. state *init(vector *key, size_t key_length, vector nonce, enum direction direction)
  682. {
  683.     unsigned int i, j, k, l;
  684.     vector x = {0};
  685.     state *s = calloc(1, sizeof(state));
  686.     const vector pi = {.elements={
  687.         0x24, 0x3F, 0x6A, 0x88, 0x85, 0xA3, 0x08, 0xD3,
  688.         0x13, 0x19, 0x8A, 0x2E, 0x03, 0x70, 0x73, 0x44
  689.     }};
  690.  
  691.     for(i=0; i<key_length; i++)
  692.     {
  693.         x = vector_multiply(vector_xor(x, key[i]), pi);
  694.        
  695.         for (j=0; j<16; j++)
  696.         {
  697.             x.elements[j] = rotl(x.elements[j],(5*(i-2)+3*j)%7+1);
  698.         }
  699.  
  700.         x = matrix_multiply(x);
  701.     }
  702.  
  703.     for (i=0; i<ROUNDS+3; i++)
  704.     {
  705.         for (j=0; j<2; j++)
  706.         {
  707.             x = vector_xor(x, u128_to_vector(2*i+j));
  708.  
  709.             for(k=0; k<key_length; k++)
  710.             {
  711.                 x = vector_multiply(vector_xor(x, key[k]), pi);
  712.  
  713.                 for (l=0; l<16; l++)
  714.                 {
  715.                     x.elements[l] = rotl(x.elements[l],(3*i+5*j)%7+1);
  716.                 }
  717.  
  718.                 x = matrix_multiply(x);
  719.             }
  720.             s->key_schedule[i][j] = x;
  721.         }
  722.  
  723.     }
  724.     reinit(s, nonce, direction);
  725.  
  726.     return s;
  727. }
  728.  
  729. void dest(state **s)
  730. {
  731.     //You should really zero memory here, but memset will be optimized, GCC does not
  732.     //support memset_s, and I'm lazy
  733.     free(*s);
  734.     *s = NULL;
  735. }
  736.  
  737. size_t append(char *in, size_t in_len, char *out, size_t out_len, state *s,
  738.         size_t *bytes_written)
  739. {
  740.     size_t in_pos = 0;
  741.     size_t out_pos = 0;
  742.     size_t copy_length;
  743.     vector block;
  744.  
  745.     if (s->buffer_len > 0 && s->buffer_len < 16)
  746.     {
  747.         if (in_len+s->buffer_len >= 16)
  748.         {
  749.             copy_length = 16-s->buffer_len;
  750.         }
  751.         else
  752.         {
  753.             copy_length = in_len;
  754.         }
  755.  
  756.         memcpy(s->buffer+s->buffer_len, in, copy_length);
  757.         in_pos += copy_length;
  758.         s->buffer_len += copy_length;
  759.     }
  760.  
  761.     if (s->buffer_len == 16)
  762.     {
  763.         memcpy(block.elements, s->buffer, 16);
  764.         block = s->crypt(block, 16, s);
  765.         s->counter++;
  766.         memcpy(out+out_pos, block.elements, 16);
  767.        
  768.         out_pos += 16;
  769.         s->buffer_len = 0;
  770.     }
  771.  
  772.     while (in_len-in_pos >= 16 && out_len-in_pos >= 16)
  773.     {
  774.         memcpy(block.elements, in+in_pos, 16);
  775.         in_pos += 16;
  776.         block = s->crypt(block, 16, s);
  777.         s->counter++;
  778.         memcpy(out+out_pos, block.elements, 16);
  779.         out_pos += 16;
  780.     }
  781.  
  782.     copy_length = in_len-in_pos;
  783.     if (copy_length > 16)
  784.     {
  785.         copy_length = 16;
  786.     }
  787.  
  788.     if (copy_length > 0)
  789.     {
  790.         memcpy(s->buffer, in+in_pos, copy_length);
  791.         s->buffer_len = copy_length;
  792.         in_pos += copy_length;
  793.     }
  794.     s->length += out_pos;
  795.     *bytes_written = out_pos;
  796.  
  797.     return in_pos;
  798. }
  799.  
  800. //Result is freed on call to dest(state), you
  801. //should not free result or access after calling dest
  802. char * finalize(size_t *out_length, state *s)
  803. {
  804.     //Encrypt remaining data if available
  805.     if (s->buffer_len > 0)
  806.     {
  807.         vector block;
  808.         memcpy(block.elements, s->buffer, s->buffer_len);
  809.         block = s->crypt(block, s->buffer_len, s);
  810.         memcpy(s->buffer, block.elements, s->buffer_len);
  811.     }
  812.     *out_length = s->buffer_len;
  813.     s->length += s->buffer_len;
  814.  
  815.     //Finalize MAC computation by encrypting using the length instead of the counter for the
  816.     //tweak value
  817.     s->counter = s->length;
  818.     s->mac = encrypt(s->mac, 16, s);
  819.  
  820.     //return a reference to the buffer
  821.     return s->buffer;
  822. }
  823.  
  824. char * get_mac(size_t *out_length, state *s)
  825. {
  826.     if (s->length != s->counter) //Not finalized
  827.     {
  828.         *out_length = 0;
  829.         return NULL;
  830.     }
  831.     else
  832.     {
  833.         *out_length = 16;
  834.         return (char *)s->mac.elements;
  835.     }
  836. }
  837.  
  838. int check_mac(char *mac, size_t mac_length, state *s)
  839. {
  840.     int i;
  841.     if (mac_length > 16)
  842.     {
  843.         return 0; //False
  844.     }
  845.     else
  846.     {
  847.         uint8_t check = 0;
  848.         for (i=0; i<mac_length; i++)
  849.         {
  850.             //if any bit differed, check will be non-zero
  851.             check |= s->mac.elements[i] ^ (uint8_t)mac[i];
  852.         }
  853.         return !check;
  854.     }
  855. }
  856.  
  857. //Encrypt or Decrypt all bytes except for the last [trailing_bytes_len] bytes
  858. size_t process_io(FILE *input, FILE *output,
  859.         char *in_buffer, size_t in_buffer_len, size_t trailing_bytes_len,
  860.         char *out_buffer, size_t out_buffer_len,
  861.         state *s)
  862. {
  863.     size_t buffer_len, bytes_read, bytes_written;
  864.     size_t buffer_pos = 0;
  865.     char *tail;
  866.  
  867.     if (trailing_bytes_len > 0)
  868.     {
  869.         buffer_pos = fread(in_buffer, 1, trailing_bytes_len, stdin);
  870.         if (buffer_pos != trailing_bytes_len)
  871.         {
  872.             fprintf(stderr, "Not enough trailing bytes\n");
  873.             exit(1);
  874.         }
  875.     }
  876.     while (trailing_bytes_len < (buffer_len = buffer_pos + fread(in_buffer+buffer_pos, 1,
  877.                     in_buffer_len-buffer_pos, stdin)))
  878.     {
  879.  
  880.         bytes_read = append(in_buffer, buffer_len-trailing_bytes_len, out_buffer,
  881.                 out_buffer_len, s, &bytes_written);
  882.  
  883.         if (bytes_written != fwrite(out_buffer, 1, bytes_written, stdout))
  884.         {
  885.             fprintf(stderr, "Error writing to output\n");
  886.             exit(1);
  887.         }
  888.  
  889.         memmove(in_buffer, in_buffer+bytes_read, buffer_len-bytes_read);
  890.         buffer_pos = buffer_len-bytes_read;
  891.     }
  892.  
  893.     tail = finalize(&bytes_written, s);
  894.  
  895.     if (bytes_written != fwrite(tail, 1, bytes_written, stdout))
  896.     {
  897.         fprintf(stderr, "Error writing to output\n");
  898.         exit(1);
  899.     }
  900.     return buffer_pos;
  901. }
  902.  
  903. int main(int argc, char **argv)
  904. {
  905.     if (argc == 2)
  906.     {
  907.         char direction = argv[1][0];
  908.         vector key = {0};
  909.         vector nonce;
  910.         state *s;
  911.         char *mac;
  912.         size_t bytes_read, bytes_written;
  913.         char out_buffer[8192];
  914.  
  915.         if (direction == 'e')
  916.         {
  917.             char in_buffer[8192];
  918.             FILE *random = fopen("/dev/random", "rb");
  919.             if (random == NULL)
  920.             {
  921.                 fprintf(stderr, "Error reading from /dev/random\n");
  922.                 exit(1);
  923.             }
  924.            
  925.             bytes_read = fread(nonce.elements, 1, sizeof(nonce.elements), random);
  926.  
  927.             fclose(random);
  928.             random = NULL;
  929.             if (bytes_read != 16)
  930.             {
  931.                 fprintf(stderr, "Error reading from /dev/random\n");
  932.                 exit(1);
  933.             }
  934.            
  935.             if (16 != fwrite(nonce.elements, 1, 16, stdout))
  936.             {
  937.                 fprintf(stderr, "Error writing to output\n");
  938.                 exit(1);
  939.             }
  940.            
  941.             s = init(&key, 1, nonce, ENCRYPT);
  942.  
  943.             process_io(stdin, stdout,
  944.                     in_buffer, sizeof(in_buffer), 0, out_buffer, sizeof(out_buffer), s);
  945.  
  946.             mac = get_mac(&bytes_written, s);
  947.  
  948.             if (bytes_written != fwrite(mac, 1, bytes_written, stdout))
  949.             {
  950.                 fprintf(stderr, "Error writing to output\n");
  951.                 exit(1);
  952.             }
  953.             dest(&s);
  954.         }
  955.         else
  956.         {
  957.             char in_buffer[8192+16];
  958.             bytes_read = fread(nonce.elements, 1, sizeof(nonce.elements), stdin);
  959.            
  960.             if (bytes_read != 16)
  961.             {
  962.                 fprintf(stderr, "File did not start with nonce\n");
  963.                 exit(1);
  964.             }
  965.             s = init(&key, 1, nonce, DECRYPT);
  966.  
  967.             bytes_read = process_io(stdin, stdout,
  968.                     in_buffer, sizeof(in_buffer), 16, out_buffer, sizeof(out_buffer), s);
  969.  
  970.             if (!check_mac(in_buffer, bytes_read, s))
  971.             {
  972.                 fprintf(stderr, "MAC check failed\n");
  973.             }
  974.             dest(&s);
  975.         }
  976.     }
  977.     return 0;
  978. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement