API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Apr 11th, 2015
367
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 28.15 KB | None | 0 0
raw download clone embed print report
  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
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!