| 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213 |
- /*
- * galois.c: arithmetic in Galois Fields
- *
- * ===================================================================
- * The contents of this file are dedicated to the public domain. To
- * the extent that dedication to the public domain is not available,
- * everyone is granted a worldwide, perpetual, royalty-free,
- * non-exclusive license to exercise all rights associated with the
- * contents of this file for any purpose whatsoever.
- * No rights are reserved.
- *
- * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
- * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
- * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
- * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
- * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
- * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
- * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
- * SOFTWARE.
- * ===================================================================
- */
- #include "pycrypto_common.h"
- FAKE_INIT(galois)
- #define ALIGNMENT 32
- /**
- * A V table is a 4096 bytes table that will contain the expanded
- * GHASH key (H). It is used to speed up the GF(128) multiplication Z = X*H.
- *
- * The table contains 128 entries, one for each bit of X.
- * Each entry takes 32 bytes and can fit into the cache line of a modern
- * processor. If we assume that access to memory mapped to the same
- * cache line is somewhat constant, we can make GHASH robust again
- * cache timing attacks.
- */
- typedef uint64_t t_v_tables[128][2][2];
- /**
- * To ensure that the V table is aligned to a 32-byte memory boundary,
- * we allocate a larger piece of memory and carve the V table from there.
- */
- typedef struct {
- uint8_t buffer[sizeof(t_v_tables)+ALIGNMENT];
- int offset;
- } t_exp_key;
- /**
- * Big Endian to word conversions
- */
- static uint64_t be_to_word(const uint8_t fb[8])
- {
- uint64_t tmp;
- int i;
- tmp = 0;
- for (i=0; i<8; i++)
- tmp = tmp<<8 ^ *fb++;
- return tmp;
- }
- /**
- * Word to Big Endian conversions
- */
- static void word_to_be(uint8_t fb[8], uint64_t w)
- {
- int i;
- for (i=0; i<8; i++) {
- fb[7-i] = (uint8_t) w;
- w >>= 8;
- }
- }
- /**
- * Create a V table. V[i] is the value H*x^i (i=0..127).
- * \param h The 16 byte GHASH key
- * \param tables A pointer to an allocated V table
- */
- static void make_v_tables(const uint8_t h[16], t_v_tables *tables)
- {
- uint64_t (*cur)[2];
- int i;
- memset(tables, 0, sizeof(t_v_tables));
- cur = &((*tables)[0][1]);
- (*cur)[0] = be_to_word(&h[0]);
- (*cur)[1] = be_to_word(&h[8]);
- for (i=1; i<128; i++) {
- uint64_t c;
- uint64_t (*next)[2];
- next = &((*tables)[i][1]);
- /** v = (v&1)*0xE1000000000000000000000000000000L ^ (v>>1) **/
- c = (*cur)[1]&1 ? 0xE100000000000000 : 0;
- (*next)[1] = (*cur)[1]>>1 | (*cur)[0]<<63;
- (*next)[0] = (*cur)[0]>>1 ^ c;
- cur = next;
- }
- }
- /**
- * Multiply two elements of GF(2**128) using the reducing polynomial
- * (x^128 + x^7 + x^2 + x + 1).
- *
- * \param out The 16 byte buffer that will receive the result
- * \param key_tables One factor, expanded into a V table
- * \param x The other factor (16 bytes)
- */
- static void gcm_mult2(uint8_t out[16], const t_v_tables *key_tables, const uint8_t x[16])
- {
- int i, bit_scan_128;
- uint64_t z[2];
- z[0] = z[1] = 0;
- bit_scan_128 = 0;
- for (i=0; i<16; i++) {
- uint8_t xi;
- int j;
- xi = x[i];
- for (j=0; j<8; j++) {
- int bit;
- bit = xi>>7 & 1; /** Constant time */
- z[0] ^= (*key_tables)[bit_scan_128][bit][0];
- z[1] ^= (*key_tables)[bit_scan_128][bit][1];
- xi <<= 1;
- bit_scan_128++;
- }
- }
-
- word_to_be(out, z[0]);
- word_to_be(out+8, z[1]);
- }
- /**
- * Compute the GHASH of a piece of data given an arbitrary Y_0,
- * as specified in NIST SP 800 38D.
- *
- * \param y_out The resulting GHASH (16 bytes).
- * \param block_data Pointer to the data to hash.
- * \param len Length of the data to hash (multiple of 16).
- * \param y_in The initial Y (Y_0, 16 bytes).
- * \param exp_key The expanded hash key (16*256*16 bytes + alignment).
- *
- * y_out and y_int can point to the same buffer.
- */
- EXPORT_SYM int ghash(
- uint8_t y_out[16],
- const uint8_t block_data[],
- size_t len,
- const uint8_t y_in[16],
- const t_exp_key *exp_key
- )
- {
- unsigned int i;
- const t_v_tables *v_tables;
- if (NULL==y_out || NULL==block_data || NULL==y_in || NULL==exp_key)
- return ERR_NULL;
- if (len % 16)
- return ERR_NOT_ENOUGH_DATA;
-
- v_tables = (const t_v_tables*)(exp_key->buffer + exp_key->offset);
- memcpy(y_out, y_in, 16);
- for (i=0; i<len; i+=16) {
- int j;
- uint8_t x[16];
- for (j=0; j<16; j++) {
- x[j] = y_out[j] ^ block_data[i+j];
- }
- gcm_mult2(y_out, v_tables, x);
- }
- return 0;
- }
- /**
- * Expand the AES key into a Python (byte) string object.
- */
- EXPORT_SYM int ghash_expand(const uint8_t h[16], t_exp_key **ghash_tables)
- {
- t_exp_key *exp_key;
- if (NULL==h || NULL==ghash_tables)
- return ERR_NULL;
- *ghash_tables = exp_key = calloc(1, sizeof(t_exp_key));
- if (NULL == exp_key)
- return ERR_MEMORY;
-
- exp_key->offset = ALIGNMENT - ((uintptr_t)exp_key->buffer & (ALIGNMENT-1));
- make_v_tables(h, (t_v_tables*)(exp_key->buffer + exp_key->offset));
-
- return 0;
- }
- EXPORT_SYM int ghash_destroy(t_exp_key *ghash_tables)
- {
- free(ghash_tables);
- return 0;
- }
|