galois.c 5.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213
  1. /*
  2. * galois.c: arithmetic in Galois Fields
  3. *
  4. * ===================================================================
  5. * The contents of this file are dedicated to the public domain. To
  6. * the extent that dedication to the public domain is not available,
  7. * everyone is granted a worldwide, perpetual, royalty-free,
  8. * non-exclusive license to exercise all rights associated with the
  9. * contents of this file for any purpose whatsoever.
  10. * No rights are reserved.
  11. *
  12. * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  13. * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  14. * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  15. * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
  16. * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
  17. * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  18. * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  19. * SOFTWARE.
  20. * ===================================================================
  21. */
  22. #include "pycrypto_common.h"
  23. FAKE_INIT(galois)
  24. #define ALIGNMENT 32
  25. /**
  26. * A V table is a 4096 bytes table that will contain the expanded
  27. * GHASH key (H). It is used to speed up the GF(128) multiplication Z = X*H.
  28. *
  29. * The table contains 128 entries, one for each bit of X.
  30. * Each entry takes 32 bytes and can fit into the cache line of a modern
  31. * processor. If we assume that access to memory mapped to the same
  32. * cache line is somewhat constant, we can make GHASH robust again
  33. * cache timing attacks.
  34. */
  35. typedef uint64_t t_v_tables[128][2][2];
  36. /**
  37. * To ensure that the V table is aligned to a 32-byte memory boundary,
  38. * we allocate a larger piece of memory and carve the V table from there.
  39. */
  40. typedef struct {
  41. uint8_t buffer[sizeof(t_v_tables)+ALIGNMENT];
  42. int offset;
  43. } t_exp_key;
  44. /**
  45. * Big Endian to word conversions
  46. */
  47. static uint64_t be_to_word(const uint8_t fb[8])
  48. {
  49. uint64_t tmp;
  50. int i;
  51. tmp = 0;
  52. for (i=0; i<8; i++)
  53. tmp = tmp<<8 ^ *fb++;
  54. return tmp;
  55. }
  56. /**
  57. * Word to Big Endian conversions
  58. */
  59. static void word_to_be(uint8_t fb[8], uint64_t w)
  60. {
  61. int i;
  62. for (i=0; i<8; i++) {
  63. fb[7-i] = (uint8_t) w;
  64. w >>= 8;
  65. }
  66. }
  67. /**
  68. * Create a V table. V[i] is the value H*x^i (i=0..127).
  69. * \param h The 16 byte GHASH key
  70. * \param tables A pointer to an allocated V table
  71. */
  72. static void make_v_tables(const uint8_t h[16], t_v_tables *tables)
  73. {
  74. uint64_t (*cur)[2];
  75. int i;
  76. memset(tables, 0, sizeof(t_v_tables));
  77. cur = &((*tables)[0][1]);
  78. (*cur)[0] = be_to_word(&h[0]);
  79. (*cur)[1] = be_to_word(&h[8]);
  80. for (i=1; i<128; i++) {
  81. uint64_t c;
  82. uint64_t (*next)[2];
  83. next = &((*tables)[i][1]);
  84. /** v = (v&1)*0xE1000000000000000000000000000000L ^ (v>>1) **/
  85. c = (*cur)[1]&1 ? 0xE100000000000000 : 0;
  86. (*next)[1] = (*cur)[1]>>1 | (*cur)[0]<<63;
  87. (*next)[0] = (*cur)[0]>>1 ^ c;
  88. cur = next;
  89. }
  90. }
  91. /**
  92. * Multiply two elements of GF(2**128) using the reducing polynomial
  93. * (x^128 + x^7 + x^2 + x + 1).
  94. *
  95. * \param out The 16 byte buffer that will receive the result
  96. * \param key_tables One factor, expanded into a V table
  97. * \param x The other factor (16 bytes)
  98. */
  99. static void gcm_mult2(uint8_t out[16], const t_v_tables *key_tables, const uint8_t x[16])
  100. {
  101. int i, bit_scan_128;
  102. uint64_t z[2];
  103. z[0] = z[1] = 0;
  104. bit_scan_128 = 0;
  105. for (i=0; i<16; i++) {
  106. uint8_t xi;
  107. int j;
  108. xi = x[i];
  109. for (j=0; j<8; j++) {
  110. int bit;
  111. bit = xi>>7 & 1; /** Constant time */
  112. z[0] ^= (*key_tables)[bit_scan_128][bit][0];
  113. z[1] ^= (*key_tables)[bit_scan_128][bit][1];
  114. xi <<= 1;
  115. bit_scan_128++;
  116. }
  117. }
  118. word_to_be(out, z[0]);
  119. word_to_be(out+8, z[1]);
  120. }
  121. /**
  122. * Compute the GHASH of a piece of data given an arbitrary Y_0,
  123. * as specified in NIST SP 800 38D.
  124. *
  125. * \param y_out The resulting GHASH (16 bytes).
  126. * \param block_data Pointer to the data to hash.
  127. * \param len Length of the data to hash (multiple of 16).
  128. * \param y_in The initial Y (Y_0, 16 bytes).
  129. * \param exp_key The expanded hash key (16*256*16 bytes + alignment).
  130. *
  131. * y_out and y_int can point to the same buffer.
  132. */
  133. EXPORT_SYM int ghash(
  134. uint8_t y_out[16],
  135. const uint8_t block_data[],
  136. size_t len,
  137. const uint8_t y_in[16],
  138. const t_exp_key *exp_key
  139. )
  140. {
  141. unsigned int i;
  142. const t_v_tables *v_tables;
  143. if (NULL==y_out || NULL==block_data || NULL==y_in || NULL==exp_key)
  144. return ERR_NULL;
  145. if (len % 16)
  146. return ERR_NOT_ENOUGH_DATA;
  147. v_tables = (const t_v_tables*)(exp_key->buffer + exp_key->offset);
  148. memcpy(y_out, y_in, 16);
  149. for (i=0; i<len; i+=16) {
  150. int j;
  151. uint8_t x[16];
  152. for (j=0; j<16; j++) {
  153. x[j] = y_out[j] ^ block_data[i+j];
  154. }
  155. gcm_mult2(y_out, v_tables, x);
  156. }
  157. return 0;
  158. }
  159. /**
  160. * Expand the AES key into a Python (byte) string object.
  161. */
  162. EXPORT_SYM int ghash_expand(const uint8_t h[16], t_exp_key **ghash_tables)
  163. {
  164. t_exp_key *exp_key;
  165. if (NULL==h || NULL==ghash_tables)
  166. return ERR_NULL;
  167. *ghash_tables = exp_key = calloc(1, sizeof(t_exp_key));
  168. if (NULL == exp_key)
  169. return ERR_MEMORY;
  170. exp_key->offset = ALIGNMENT - ((uintptr_t)exp_key->buffer & (ALIGNMENT-1));
  171. make_v_tables(h, (t_v_tables*)(exp_key->buffer + exp_key->offset));
  172. return 0;
  173. }
  174. EXPORT_SYM int ghash_destroy(t_exp_key *ghash_tables)
  175. {
  176. free(ghash_tables);
  177. return 0;
  178. }