OLD | NEW |
(Empty) | |
| 1 # Author: Google |
| 2 # See the LICENSE file for legal information regarding use of this file. |
| 3 |
| 4 # GCM derived from Go's implementation in crypto/cipher. |
| 5 # |
| 6 # https://golang.org/src/crypto/cipher/gcm.go |
| 7 |
| 8 # GCM works over elements of the field GF(2^128), each of which is a 128-bit |
| 9 # polynomial. Throughout this implementation, polynomials are represented as |
| 10 # Python integers with the low-order terms at the most significant bits. So a |
| 11 # 128-bit polynomial is an integer from 0 to 2^128-1 with the most significant |
| 12 # bit representing the x^0 term and the least significant bit representing the |
| 13 # x^127 term. This bit reversal also applies to polynomials used as indices in a |
| 14 # look-up table. |
| 15 |
| 16 from .cryptomath import bytesToNumber, numberToByteArray |
| 17 |
| 18 class AESGCM(object): |
| 19 """ |
| 20 AES-GCM implementation. Note: this implementation does not attempt |
| 21 to be side-channel resistant. It's also rather slow. |
| 22 """ |
| 23 |
| 24 def __init__(self, key, implementation, rawAesEncrypt): |
| 25 self.isBlockCipher = False |
| 26 self.isAEAD = True |
| 27 self.nonceLength = 12 |
| 28 self.tagLength = 16 |
| 29 self.implementation = implementation |
| 30 if len(key) == 16: |
| 31 self.name = "aes128gcm" |
| 32 elif len(key) == 32: |
| 33 self.name = "aes256gcm" |
| 34 else: |
| 35 raise AssertionError() |
| 36 |
| 37 self._rawAesEncrypt = rawAesEncrypt |
| 38 |
| 39 # The GCM key is AES(0). |
| 40 h = bytesToNumber(self._rawAesEncrypt(bytearray(16))) |
| 41 |
| 42 # Pre-compute all 4-bit multiples of h. Note that bits are reversed |
| 43 # because our polynomial representation places low-order terms at the |
| 44 # most significant bit. Thus x^0 * h = h is at index 0b1000 = 8 and |
| 45 # x^1 * h is at index 0b0100 = 4. |
| 46 self._productTable = [0] * 16 |
| 47 self._productTable[_reverseBits(1)] = h |
| 48 for i in range(2, 16, 2): |
| 49 self._productTable[_reverseBits(i)] = \ |
| 50 _gcmShift(self._productTable[_reverseBits(i/2)]) |
| 51 self._productTable[_reverseBits(i+1)] = \ |
| 52 _gcmAdd(self._productTable[_reverseBits(i)], h) |
| 53 |
| 54 def _rawAesCtrEncrypt(self, counter, inp): |
| 55 """ |
| 56 Encrypts (or decrypts) plaintext with AES-CTR. counter is modified. |
| 57 """ |
| 58 out = bytearray(len(inp)) |
| 59 for i in range(0, len(out), 16): |
| 60 mask = self._rawAesEncrypt(counter) |
| 61 for j in range(i, min(len(out), i + 16)): |
| 62 out[j] = inp[j] ^ mask[j-i] |
| 63 _inc32(counter) |
| 64 return out |
| 65 |
| 66 def _auth(self, ciphertext, ad, tagMask): |
| 67 y = 0 |
| 68 y = self._update(y, ad) |
| 69 y = self._update(y, ciphertext) |
| 70 y ^= (len(ad) << (3 + 64)) | (len(ciphertext) << 3) |
| 71 y = self._mul(y) |
| 72 y ^= bytesToNumber(tagMask) |
| 73 return numberToByteArray(y, 16) |
| 74 |
| 75 def _update(self, y, data): |
| 76 for i in range(0, len(data) // 16): |
| 77 y ^= bytesToNumber(data[16*i:16*i+16]) |
| 78 y = self._mul(y) |
| 79 extra = len(data) % 16 |
| 80 if extra != 0: |
| 81 block = bytearray(16) |
| 82 block[:extra] = data[-extra:] |
| 83 y ^= bytesToNumber(block) |
| 84 y = self._mul(y) |
| 85 return y |
| 86 |
| 87 def _mul(self, y): |
| 88 """ Returns y*H, where H is the GCM key. """ |
| 89 ret = 0 |
| 90 # Multiply H by y 4 bits at a time, starting with the highest power |
| 91 # terms. |
| 92 for i in range(0, 128, 4): |
| 93 # Multiply by x^4. The reduction for the top four terms is |
| 94 # precomputed. |
| 95 retHigh = ret & 0xf |
| 96 ret >>= 4 |
| 97 ret ^= (_gcmReductionTable[retHigh] << (128-16)) |
| 98 |
| 99 # Add in y' * H where y' are the next four terms of y, shifted down |
| 100 # to the x^0..x^4. This is one of the pre-computed multiples of |
| 101 # H. The multiplication by x^4 shifts them back into place. |
| 102 ret ^= self._productTable[y & 0xf] |
| 103 y >>= 4 |
| 104 assert y == 0 |
| 105 return ret |
| 106 |
| 107 def seal(self, nonce, plaintext, data): |
| 108 """ |
| 109 Encrypts and authenticates plaintext using nonce and data. Returns the |
| 110 ciphertext, consisting of the encrypted plaintext and tag concatenated. |
| 111 """ |
| 112 |
| 113 if len(nonce) != 12: |
| 114 raise ValueError("Bad nonce length") |
| 115 |
| 116 # The initial counter value is the nonce, followed by a 32-bit counter |
| 117 # that starts at 1. It's used to compute the tag mask. |
| 118 counter = bytearray(16) |
| 119 counter[:12] = nonce |
| 120 counter[-1] = 1 |
| 121 tagMask = self._rawAesEncrypt(counter) |
| 122 |
| 123 # The counter starts at 2 for the actual encryption. |
| 124 counter[-1] = 2 |
| 125 ciphertext = self._rawAesCtrEncrypt(counter, plaintext) |
| 126 |
| 127 tag = self._auth(ciphertext, data, tagMask) |
| 128 |
| 129 return ciphertext + tag |
| 130 |
| 131 def open(self, nonce, ciphertext, data): |
| 132 """ |
| 133 Decrypts and authenticates ciphertext using nonce and data. If the |
| 134 tag is valid, the plaintext is returned. If the tag is invalid, |
| 135 returns None. |
| 136 """ |
| 137 |
| 138 if len(nonce) != 12: |
| 139 raise ValueError("Bad nonce length") |
| 140 if len(ciphertext) < 16: |
| 141 return None |
| 142 |
| 143 tag = ciphertext[-16:] |
| 144 ciphertext = ciphertext[:-16] |
| 145 |
| 146 # The initial counter value is the nonce, followed by a 32-bit counter |
| 147 # that starts at 1. It's used to compute the tag mask. |
| 148 counter = bytearray(16) |
| 149 counter[:12] = nonce |
| 150 counter[-1] = 1 |
| 151 tagMask = self._rawAesEncrypt(counter) |
| 152 |
| 153 if tag != self._auth(ciphertext, data, tagMask): |
| 154 return None |
| 155 |
| 156 # The counter starts at 2 for the actual decryption. |
| 157 counter[-1] = 2 |
| 158 return self._rawAesCtrEncrypt(counter, ciphertext) |
| 159 |
| 160 def _reverseBits(i): |
| 161 assert i < 16 |
| 162 i = ((i << 2) & 0xc) | ((i >> 2) & 0x3) |
| 163 i = ((i << 1) & 0xa) | ((i >> 1) & 0x5) |
| 164 return i |
| 165 |
| 166 def _gcmAdd(x, y): |
| 167 return x ^ y |
| 168 |
| 169 def _gcmShift(x): |
| 170 # Multiplying by x is a right shift, due to bit order. |
| 171 highTermSet = x & 1 |
| 172 x >>= 1 |
| 173 if highTermSet: |
| 174 # The x^127 term was shifted up to x^128, so subtract a 1+x+x^2+x^7 |
| 175 # term. This is 0b11100001 or 0xe1 when represented as an 8-bit |
| 176 # polynomial. |
| 177 x ^= 0xe1 << (128-8) |
| 178 return x |
| 179 |
| 180 def _inc32(counter): |
| 181 for i in range(len(counter)-1, len(counter)-5, -1): |
| 182 counter[i] = (counter[i] + 1) % 256 |
| 183 if counter[i] != 0: |
| 184 break |
| 185 return counter |
| 186 |
| 187 # _gcmReductionTable[i] is i * (1+x+x^2+x^7) for all 4-bit polynomials i. The |
| 188 # result is stored as a 16-bit polynomial. This is used in the reduction step to |
| 189 # multiply elements of GF(2^128) by x^4. |
| 190 _gcmReductionTable = [ |
| 191 0x0000, 0x1c20, 0x3840, 0x2460, 0x7080, 0x6ca0, 0x48c0, 0x54e0, |
| 192 0xe100, 0xfd20, 0xd940, 0xc560, 0x9180, 0x8da0, 0xa9c0, 0xb5e0, |
| 193 ] |
OLD | NEW |