From 3579e03594083dc852c4dc08de80aecfe53401c6 Mon Sep 17 00:00:00 2001 From: Matthew Endsley Date: Fri, 18 Dec 2020 18:10:32 -0800 Subject: [PATCH] Add AES_GCM primitive --- Hazel.UnitTests/Crypto/AesGcmTest.cs | 255 +++++++++++++++++ Hazel.UnitTests/Hazel.UnitTests.csproj | 2 + Hazel.UnitTests/Utils.cs | 62 ++++ Hazel/Crypto/AesGcm.cs | 379 +++++++++++++++++++++++++ Hazel/Hazel.csproj | 1 + 5 files changed, 699 insertions(+) create mode 100644 Hazel.UnitTests/Crypto/AesGcmTest.cs create mode 100644 Hazel.UnitTests/Utils.cs create mode 100644 Hazel/Crypto/AesGcm.cs diff --git a/Hazel.UnitTests/Crypto/AesGcmTest.cs b/Hazel.UnitTests/Crypto/AesGcmTest.cs new file mode 100644 index 0000000..9620973 --- /dev/null +++ b/Hazel.UnitTests/Crypto/AesGcmTest.cs @@ -0,0 +1,255 @@ +using Hazel.Crypto; +using Microsoft.VisualStudio.TestTools.UnitTesting; +using System.Text; + +namespace Hazel.UnitTests.Crypto +{ + [TestClass] + public class AesGcmTest + { + [TestMethod] + public void Example1() + { + byte[] key = Utils.HexToBytes("FEFFE992 8665731C 6D6A8F94 67308308"); + byte[] nonce = Utils.HexToBytes("CAFEBABE FACEDBAD DECAF888"); + byte[] associatedData = Utils.HexToBytes(""); + + using (Aes128Gcm aes = new Aes128Gcm(key)) + { + byte[] plaintext = Utils.HexToBytes(""); + byte[] ciphertextBytes = new byte[plaintext.Length + Aes128Gcm.CiphertextOverhead]; + aes.Seal(ciphertextBytes, nonce, plaintext, associatedData); + + CollectionAssert.AreEqual(Utils.HexToBytes("3247184B 3C4F69A4 4DBCD228 87BBB418"), ciphertextBytes); + } + + using (Aes128Gcm aes = new Aes128Gcm(key)) + { + byte[] ciphertext = Utils.HexToBytes("3247184B 3C4F69A4 4DBCD228 87BBB418"); + byte[] plaintext = new byte[ciphertext.Length - Aes128Gcm.CiphertextOverhead]; + bool result = aes.Open(plaintext, nonce, ciphertext, associatedData); + Assert.IsTrue(result); + CollectionAssert.AreEqual(Utils.HexToBytes(""), plaintext); + } + } + + [TestMethod] + public void Example2() + { + byte[] key = Utils.HexToBytes("FEFFE992 8665731C 6D6A8F94 67308308"); + byte[] nonce = Utils.HexToBytes("CAFEBABE FACEDBAD DECAF888"); + byte[] associatedData = Utils.HexToBytes(""); + + using (Aes128Gcm aes = new Aes128Gcm(key)) + { + byte[] plaintext = Utils.HexToBytes(@" + D9313225 F88406E5 A55909C5 AFF5269A + 86A7A953 1534F7DA 2E4C303D 8A318A72 + 1C3C0C95 95680953 2FCF0E24 49A6B525 + B16AEDF5 AA0DE657 BA637B39 1AAFD255 + "); + byte[] ciphertextBytes = new byte[plaintext.Length + Aes128Gcm.CiphertextOverhead]; + aes.Seal(ciphertextBytes, nonce, plaintext, associatedData); + + CollectionAssert.AreEqual(Utils.HexToBytes(@" + 42831EC2 21777424 4B7221B7 84D0D49C + E3AA212F 2C02A4E0 35C17E23 29ACA12E + 21D514B2 5466931C 7D8F6A5A AC84AA05 + 1BA30B39 6A0AAC97 3D58E091 473F5985 + + 4D5C2AF3 27CD64A6 2CF35ABD 2BA6FAB4 + "), ciphertextBytes); + } + + using (Aes128Gcm aes = new Aes128Gcm(key)) + { + byte[] ciphertext = Utils.HexToBytes(@" + 42831EC2 21777424 4B7221B7 84D0D49C + E3AA212F 2C02A4E0 35C17E23 29ACA12E + 21D514B2 5466931C 7D8F6A5A AC84AA05 + 1BA30B39 6A0AAC97 3D58E091 473F5985 + + 4D5C2AF3 27CD64A6 2CF35ABD 2BA6FAB4 + "); + byte[] plaintext = new byte[ciphertext.Length - Aes128Gcm.CiphertextOverhead]; + bool result = aes.Open(plaintext, nonce, ciphertext, associatedData); + Assert.IsTrue(result); + + CollectionAssert.AreEqual(Utils.HexToBytes(@" + D9313225 F88406E5 A55909C5 AFF5269A + 86A7A953 1534F7DA 2E4C303D 8A318A72 + 1C3C0C95 95680953 2FCF0E24 49A6B525 + B16AEDF5 AA0DE657 BA637B39 1AAFD255 + "), plaintext); + } + } + + [TestMethod] + public void Example3() + { + byte[] key = Utils.HexToBytes("FEFFE992 8665731C 6D6A8F94 67308308"); + byte[] nonce = Utils.HexToBytes("CAFEBABE FACEDBAD DECAF888"); + byte[] associatedData = Utils.HexToBytes(@" + 3AD77BB4 0D7A3660 A89ECAF3 2466EF97 + F5D3D585 03B9699D E785895A 96FDBAAF + 43B1CD7F 598ECE23 881B00E3 ED030688 + 7B0C785E 27E8AD3F 82232071 04725DD4 + "); + + using (Aes128Gcm aes = new Aes128Gcm(key)) + { + byte[] plaintext = Utils.HexToBytes(""); + byte[] ciphertextBytes = new byte[plaintext.Length + Aes128Gcm.CiphertextOverhead]; + aes.Seal(ciphertextBytes, nonce, plaintext, associatedData); + + CollectionAssert.AreEqual(Utils.HexToBytes(@" + 5F91D771 23EF5EB9 99791384 9B8DC1E9 + "), ciphertextBytes); + } + + using (Aes128Gcm aes = new Aes128Gcm(key)) + { + byte[] ciphertext = Utils.HexToBytes(@" + 5F91D771 23EF5EB9 99791384 9B8DC1E9 + "); + byte[] plaintext = new byte[ciphertext.Length - Aes128Gcm.CiphertextOverhead]; + bool result = aes.Open(plaintext, nonce, ciphertext, associatedData); + Assert.IsTrue(result); + + CollectionAssert.AreEqual(Utils.HexToBytes(""), plaintext); + } + } + + [TestMethod] + public void Example4() + { + byte[] key = Utils.HexToBytes("FEFFE992 8665731C 6D6A8F94 67308308"); + byte[] nonce = Utils.HexToBytes("CAFEBABE FACEDBAD DECAF888"); + byte[] associatedData = Utils.HexToBytes(@" + 3AD77BB4 0D7A3660 A89ECAF3 2466EF97 + F5D3D585 03B9699D E785895A 96FDBAAF + 43B1CD7F 598ECE23 881B00E3 ED030688 + 7B0C785E 27E8AD3F 82232071 04725DD4 + "); + + using (Aes128Gcm aes = new Aes128Gcm(key)) + { + byte[] plaintext = Utils.HexToBytes(@" + D9313225 F88406E5 A55909C5 AFF5269A + 86A7A953 1534F7DA 2E4C303D 8A318A72 + 1C3C0C95 95680953 2FCF0E24 49A6B525 + B16AEDF5 AA0DE657 BA637B39 1AAFD255 + "); + byte[] ciphertextBytes = new byte[plaintext.Length + Aes128Gcm.CiphertextOverhead]; + aes.Seal(ciphertextBytes, nonce, plaintext, associatedData); + + CollectionAssert.AreEqual(Utils.HexToBytes(@" + 42831EC2 21777424 4B7221B7 84D0D49C + E3AA212F 2C02A4E0 35C17E23 29ACA12E + 21D514B2 5466931C 7D8F6A5A AC84AA05 + 1BA30B39 6A0AAC97 3D58E091 473F5985 + + 64C02329 04AF398A 5B67C10B 53A5024D + "), ciphertextBytes); + } + + using (Aes128Gcm aes = new Aes128Gcm(key)) + { + byte[] ciphertext = Utils.HexToBytes(@" + 42831EC2 21777424 4B7221B7 84D0D49C + E3AA212F 2C02A4E0 35C17E23 29ACA12E + 21D514B2 5466931C 7D8F6A5A AC84AA05 + 1BA30B39 6A0AAC97 3D58E091 473F5985 + + 64C02329 04AF398A 5B67C10B 53A5024D + "); + byte[] plaintext = new byte[ciphertext.Length - Aes128Gcm.CiphertextOverhead]; + bool result = aes.Open(plaintext, nonce, ciphertext, associatedData); + Assert.IsTrue(result); + + CollectionAssert.AreEqual(Utils.HexToBytes(@" + D9313225 F88406E5 A55909C5 AFF5269A + 86A7A953 1534F7DA 2E4C303D 8A318A72 + 1C3C0C95 95680953 2FCF0E24 49A6B525 + B16AEDF5 AA0DE657 BA637B39 1AAFD255 + "), plaintext); + } + } + + [TestMethod] + public void TestReuseToDecrypt() + { + byte[] key = Utils.HexToBytes("FEFFE992 8665731C 6D6A8F94 67308308"); + byte[] nonce = Utils.HexToBytes("CAFEBABE FACEDBAD DECAF888"); + byte[] associatedData = Utils.HexToBytes(@" + 3AD77BB4 0D7A3660 A89ECAF3 2466EF97 + F5D3D585 03B9699D E785895A 96FDBAAF + 43B1CD7F 598ECE23 881B00E3 ED030688 + 7B0C785E 27E8AD3F 82232071 04725DD4 + "); + + using (Aes128Gcm aes = new Aes128Gcm(key)) + { + byte[] plaintext = Utils.HexToBytes(""); + byte[] ciphertextBytes = new byte[plaintext.Length + Aes128Gcm.CiphertextOverhead]; + aes.Seal(ciphertextBytes, nonce, plaintext, associatedData); + + CollectionAssert.AreEqual(Utils.HexToBytes(@" + 5F91D771 23EF5EB9 99791384 9B8DC1E9 + "), ciphertextBytes); + + byte[] ciphertext = Utils.HexToBytes(@" + 5F91D771 23EF5EB9 99791384 9B8DC1E9 + "); + plaintext = new byte[ciphertext.Length - Aes128Gcm.CiphertextOverhead]; + bool result = aes.Open(plaintext, nonce, ciphertext, associatedData); + Assert.IsTrue(result); + + CollectionAssert.AreEqual(Utils.HexToBytes(""), plaintext); + } + } + + [TestMethod] + public void TestPlaintextSmallerThanBlock() + { + byte[] key = Utils.HexToBytes("FEFFE992 8665731C 6D6A8F94 67308308"); + byte[] nonce = Utils.HexToBytes("CAFEBABE FACEDBAD DECAF888"); + byte[] originalPlaintext = Encoding.UTF8.GetBytes("Lorem ipsum"); + Assert.IsTrue(originalPlaintext.Length < 16); + + using (Aes128Gcm aes = new Aes128Gcm(key)) + { + byte[] ciphertext = new byte[originalPlaintext.Length + Aes128Gcm.CiphertextOverhead]; + aes.Seal(ciphertext, nonce, originalPlaintext, ByteSpan.Empty); + + byte[] plaintext = new byte[originalPlaintext.Length]; + bool result = aes.Open(plaintext, nonce, ciphertext, ByteSpan.Empty); + Assert.IsTrue(result); + + CollectionAssert.AreEqual(originalPlaintext, plaintext); + } + } + + [TestMethod] + public void TestPlaintextLargerThanBlockMultiple() + { + byte[] key = Utils.HexToBytes("FEFFE992 8665731C 6D6A8F94 67308308"); + byte[] nonce = Utils.HexToBytes("CAFEBABE FACEDBAD DECAF888"); + byte[] originalPlaintext = Encoding.UTF8.GetBytes("Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua."); + Assert.IsTrue(originalPlaintext.Length > 16); + Assert.IsTrue((originalPlaintext.Length % 16) != 0); + + using (Aes128Gcm aes = new Aes128Gcm(key)) + { + byte[] ciphertext = new byte[originalPlaintext.Length + Aes128Gcm.CiphertextOverhead]; + aes.Seal(ciphertext, nonce, originalPlaintext, ByteSpan.Empty); + + byte[] plaintext = new byte[originalPlaintext.Length]; + bool result = aes.Open(plaintext, nonce, ciphertext, ByteSpan.Empty); + Assert.IsTrue(result); + + CollectionAssert.AreEqual(originalPlaintext, plaintext); + } + } + } +} diff --git a/Hazel.UnitTests/Hazel.UnitTests.csproj b/Hazel.UnitTests/Hazel.UnitTests.csproj index 89e20cf..0a97afc 100644 --- a/Hazel.UnitTests/Hazel.UnitTests.csproj +++ b/Hazel.UnitTests/Hazel.UnitTests.csproj @@ -57,6 +57,7 @@ + @@ -70,6 +71,7 @@ + diff --git a/Hazel.UnitTests/Utils.cs b/Hazel.UnitTests/Utils.cs new file mode 100644 index 0000000..c0ca08f --- /dev/null +++ b/Hazel.UnitTests/Utils.cs @@ -0,0 +1,62 @@ +using System.Linq; +using System.Text; + +namespace Hazel.UnitTests +{ + static class Utils + { + /// + /// Hex encode a byte array (lower case) + /// + public static string BytesToHex(byte[] data) + { + string chars = "0123456789abcdef"; + + StringBuilder sb = new StringBuilder(data.Length * 2); + for (int ii = 0, nn = data.Length; ii != nn; ++ii) + { + sb.Append(chars[data[ii] >> 4]); + sb.Append(chars[data[ii] & 0xF]); + } + + return sb.ToString().ToLower(); + } + + /// + /// Decode a hex string to a byte array (lowercase) + /// + public static byte[] HexToBytes(string hex) + { + hex = hex.ToLower(); + hex = hex = string.Concat(hex.Where(c => !char.IsWhiteSpace(c))); + + byte[] output = new byte[hex.Length / 2]; + + for (int ii = 0; ii != hex.Length; ++ii) + { + byte nibble; + + char c = hex[ii]; + if (c >= 'a') + { + nibble = (byte)(0x0A + c - 'a'); + } + else + { + nibble = (byte)(c - '0'); + } + + if ((ii & 1) == 0) + { + output[ii / 2] = (byte)(nibble << 4); + } + else + { + output[ii / 2] |= nibble; + } + } + + return output; + } + } +} diff --git a/Hazel/Crypto/AesGcm.cs b/Hazel/Crypto/AesGcm.cs new file mode 100644 index 0000000..51ec281 --- /dev/null +++ b/Hazel/Crypto/AesGcm.cs @@ -0,0 +1,379 @@ +using System; +using System.Diagnostics; +using System.Security.Cryptography; + +namespace Hazel.Crypto +{ + /// + /// Implementation of AEAD_AES128_GCM based on: + /// * RFC 5116 [1] + /// * NIST SP 800-38d [2] + /// + /// [1] https://tools.ietf.org/html/rfc5116 + /// [2] https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-38d.pdf + /// + /// Adapted from: https://gist.github.com/mendsley/777e6bd9ae7eddcb2b0c0fe18247dc60 + /// + public class Aes128Gcm : IDisposable + { + public const int KeySize = 16; + public const int NonceSize = 12; + public const int CiphertextOverhead = TagSize; + + private const int TagSize = 16; + + private readonly ICryptoTransform encryptor_; + + private readonly ByteSpan hashSubkey_; + private readonly ByteSpan blockJ_; + private readonly ByteSpan blockS_; + private readonly ByteSpan blockZ_; + private readonly ByteSpan blockV_; + private readonly ByteSpan blockScratch_; + + /// + /// Creates a new instance of an AEAD_AES128_GCM cipher + /// + /// Symmetric key + public Aes128Gcm(ByteSpan key) + { + if (key.Length != KeySize) + { + throw new ArgumentException("Invalid key length", nameof(key)); + } + + // Create the AES block cipher + using (Aes aes = Aes.Create()) + { + aes.KeySize = 128; + aes.KeySize = 128; + aes.BlockSize = 128; + aes.Mode = CipherMode.ECB; + aes.Padding = PaddingMode.Zeros; + aes.Key = key.ToArray(); + + this.encryptor_ = aes.CreateEncryptor(); + } + + // Allocate scratch space + ByteSpan scratchSpace = new byte[96]; + this.hashSubkey_ = scratchSpace.Slice(0, 16); + this.blockJ_ = scratchSpace.Slice(16, 16); + this.blockS_ = scratchSpace.Slice(32, 16); + this.blockZ_ = scratchSpace.Slice(48, 16); + this.blockV_ = scratchSpace.Slice(64, 16); + this.blockScratch_ = scratchSpace.Slice(80, 16); + + // Create the GHASH subkey by encrypting the 0-block + this.encryptor_.TransformBlock(this.hashSubkey_.GetUnderlyingArray(), this.hashSubkey_.Offset, this.hashSubkey_.Length, this.hashSubkey_.GetUnderlyingArray(), this.hashSubkey_.Offset); + } + + /// + /// Encryptes the specified plaintext and generates an authentication + /// tag for the provided additional data. Returns the byte array + /// containg both the ciphertext and authentication tag. + /// + /// + /// Array in which to encode the encrypted ciphertext and + /// authentication tag. This array must be large enough to hold + /// `plaintext.Lengh + CiphertextOverhead` bytes. + /// + /// Unique value for this message + /// Plaintext data to encrypt + /// + /// Additional data used to authenticate the message + /// + public void Seal(ByteSpan output, ByteSpan nonce, ByteSpan plaintext, ByteSpan associatedData) + { + if (nonce.Length != NonceSize) + { + throw new ArgumentException("Invalid nonce size", nameof(nonce)); + } + if (output.Length < plaintext.Length + CiphertextOverhead) + { + throw new ArgumentException("Invalid output size", nameof(output)); + } + + // Create the initial counter block + nonce.CopyTo(this.blockJ_); + + // Encrypt the plaintext to output + GCTR(output, this.blockJ_, 2, plaintext); + + // Generate and append the authentication tag + int tagOffset = plaintext.Length; + GenerateAuthenticationTag(output.Slice(tagOffset), output.Slice(0, tagOffset), associatedData); + } + + /// + /// Validates the authentication tag against the provided additional + /// data, then decrypts the cipher text returning the original + /// plaintext. + /// + /// + /// The unique value used to seal this message + /// + /// + /// Combined ciphertext and authentication tag + /// + /// + /// Additional data used to authenticate the message + /// + /// + /// On successful validation and decryprion, Open writes the original + /// plaintext to output. Must contain enough space to hold + /// `ciphertext.Length - CiphertextOverhead` bytes. + /// + /// + /// True if the data was validated and successfully decrypted. + /// Otherwise, false. + /// + public bool Open(ByteSpan output, ByteSpan nonce, ByteSpan ciphertext, ByteSpan associatedData) + { + if (nonce.Length != NonceSize) + { + throw new ArgumentException("Invalid nonce size", nameof(nonce)); + } + if (ciphertext.Length < CiphertextOverhead) + { + throw new ArgumentException("Invalid ciphertext size", nameof(ciphertext)); + } + else if (output.Length < ciphertext.Length - CiphertextOverhead) + { + throw new ArgumentException("Invalid output size", nameof(output)); + } + + // Split ciphertext into actual ciphertext and authentication + // tag components. + ByteSpan authenticationTag = ciphertext.Slice(ciphertext.Length - TagSize); + ciphertext = ciphertext.Slice(0, ciphertext.Length - TagSize); + + // Create the initial counter block + nonce.CopyTo(this.blockJ_); + + // Verify the tags match + GenerateAuthenticationTag(this.blockScratch_, ciphertext, associatedData); + if (0 == Const.ConstantCompareSpans(this.blockScratch_, authenticationTag)) + { + return false; + } + + // Decrypt the cipher text to output + GCTR(output, this.blockJ_, 2, ciphertext); + return true; + } + + /// + /// Release resources acquired by the cipher + /// + public void Dispose() + { + this.encryptor_.Dispose(); + } + + // Generate the authentication tag for a ciphertext+associated data + void GenerateAuthenticationTag(ByteSpan output, ByteSpan ciphertext, ByteSpan associatedData) + { + Debug.Assert(output.Length >= 16); + + // Hash `Associated data || Ciphertext || len(AssociatedD data) || len(Ciphertext)` + // into `blockS` + { + // Clear hash output block + SetSpanToZeros(this.blockS_); + + // Write associated data blocks to hash + int fullBlocks = associatedData.Length / 16; + GHASH(this.blockS_, associatedData, fullBlocks); + if (fullBlocks * 16 < associatedData.Length) + { + SetSpanToZeros(this.blockScratch_); + associatedData.Slice(fullBlocks * 16).CopyTo(this.blockScratch_); + GHASH(this.blockS_, this.blockScratch_, 1); + } + + // Write ciphertext blocks to hash + fullBlocks = ciphertext.Length / 16; + GHASH(this.blockS_, ciphertext, fullBlocks); + if (fullBlocks * 16 < ciphertext.Length) + { + SetSpanToZeros(this.blockScratch_); + ciphertext.Slice(fullBlocks * 16).CopyTo(this.blockScratch_); + GHASH(this.blockS_, this.blockScratch_, 1); + } + + // Write bit sizes to hash + ulong associatedDataLengthInBits = (ulong)(8 * associatedData.Length); + ulong ciphertextDataLengthInBits = (ulong)(8 * ciphertext.Length); + this.blockScratch_.WriteBigEndian64(associatedDataLengthInBits); + this.blockScratch_.WriteBigEndian64(ciphertextDataLengthInBits, 8); + + GHASH(this.blockS_, this.blockScratch_, 1); + } + + // Encrypt the tag. GCM requires this because `GASH` is not + // cryptographically secure. An attacker could derive our hash + // subkey `hashSubkey_` from an unencrypted tag. + GCTR(output, this.blockJ_, 1, this.blockS_); + } + + // Run the GCTR cipher + void GCTR(ByteSpan output, ByteSpan counterBlock, uint counter, ByteSpan data) + { + Debug.Assert(counterBlock.Length == 16); + Debug.Assert(output.Length >= data.Length); + + // Loop through plaintext blocks + int writeIndex = 0; + int numBlocks = (data.Length + 15) / 16; + for (int ii = 0; ii != numBlocks; ++ii) + { + // Encode counter into block + // CB[1] = J0 + // CB[i] = inc[32](CB[i-1]) + counterBlock.WriteBigEndian32(counter, 12); + ++counter; + + // CIPH[k](CB[i]) + this.encryptor_.TransformBlock(counterBlock.GetUnderlyingArray(), counterBlock.Offset, 16, this.blockScratch_.GetUnderlyingArray(), this.blockScratch_.Offset); + + // Y[i] = X[i] xor CIPH[k](CB[i]) + for (int jj = 0; jj != 16 && writeIndex < data.Length; ++jj, ++writeIndex) + { + output[writeIndex] = (byte)(data[writeIndex] ^ this.blockScratch_[jj]); + } + } + } + + // Run the GHASH function + void GHASH(ByteSpan output, ByteSpan data, int numBlocks) + { + ///TODO(mendsley): See Ref[6] for opitmizations of GHASH on both hardware and software + /// + ///[6] D. McGrew, J. Viega, The Galois/Counter Mode of Operation (GCM), Natl. Inst. Stand. + ///Technol. [Web page], http://www.csrc.nist.gov/groups/ST/toolkit/BCM/documents/ + ///proposedmodes / gcm / gcm - revised - spec.pdf, May 31, 2005. + + Debug.Assert(output.Length == 16); + Debug.Assert(data.Length >= numBlocks * 16); + + int readIndex = 0; + for (int ii = 0; ii != numBlocks; ++ii) + { + for (int jj = 0; jj != 16; ++jj, ++readIndex) + { + // Y[ii-1] xor X[ii] + output[jj] ^= data[readIndex]; + } + + // Y[ii] = (Y[ii-1] xor X[ii]) · H + MultiplyGF128Elements(output, this.hashSubkey_, this.blockZ_, this.blockV_); + } + } + + // Multiply two Galois field elements `X` and `Y` together and store + // the result in `X` such that at the end of the function: + // X = X·Y + static void MultiplyGF128Elements(ByteSpan X, ByteSpan Y, ByteSpan scratchZ, ByteSpan scratchV) + { + Debug.Assert(X.Length == 16); + Debug.Assert(Y.Length == 16); + Debug.Assert(scratchZ.Length == 16); + Debug.Assert(scratchV.Length == 16); + + // Galois (finite) fields represented by GF(p) define a set of + // closed algebraic operations. For AES128_GCM we'll be dealing + // with the GF(2^128) field. + // + // We treat each incoming 16 byte block as a polynomial in field + // and define multiplication between two polynomials as the + // polynomial product reduced by (mod) the field polynomial: + // 1 + x + x^2 + x^7 + x^128 + // + // Field polynomials are represented by a 128 bit string. Bit n is + // the coefficient of the x^n term. We use little-endian bit + // ordering (not to be confused with byte ordering) for these + // coefficients. E.g. X[0] & 0x00000001 represents the 7th bit in + // the bit string defined by X, _not_ the 0th bit. + // + + // What follows is a modified version of the "peasant's algorithm" + // to multiply two numbers: + // + // Z contains the accumulated product + // V is a copy of Y (so we can modify it via shifting). + // + // We calculate Z = X·V as follows + // We loop through each of the 128 bits in X maintaining the + // following loop invariant: X·V + Z = the final product + // + // On each iteration `ii`: + // + // If the `ii`th bit of `X` is set, add the add the polynomial + // in `V` to `X`: `X[n] = X[n] ^ V[n]` + // + // Double V (Shift one bit right since we're storing little + // endian bit). This has the effect of multiplying V by the + // polynomial `x`. We track the unrepresentable coefficient + // of `x^128` by storing the most significant bit before the + // shift `V[15] >> 7` as `carry` + // + // Check if we've overflowed our multiplication. If overflow + // occurred, there will be a non-zero coefficient for the + // `x^128` term in the step above `carry` + // + // If we have overflowed, our polynomial is exactly of degree + // 129 (since we're only multiplying by `x`). We reduce the + // polynomial back into degree 128 by adding our field's + // irreducible polynomial: 1 + x + x^2 + x^7 + x^128. This + // reduction cancels out the x^128 term (x^128 + x^128 in GF(2) + // is zero). Therefore this modulo can be achieved by simply + // adding the irreducible polynomial to the new value of `V`. The + // irreducible polynomial is represented by the bit string: + // `11100001` followed by 120 `0`s. We can add this value to `V` + // by: `V[0] = V[0] ^ 0xE1`. + SetSpanToZeros(scratchZ); + X.CopyTo(scratchV); + + for (int ii = 0; ii != 128; ++ii) + { + int bitIndex = 7 - (ii % 8); + if ((Y[ii / 8] & (1 << bitIndex)) != 0) + { + for (int jj = 0; jj != 16; ++jj) + { + scratchZ[jj] ^= scratchV[jj]; + } + } + + bool carry = false; + for (int jj = 0; jj != 16; ++jj) + { + bool newCarry = (scratchV[jj] & 0x01) != 0; + scratchV[jj] >>= 1; + if (carry) + { + scratchV[jj] |= 0x80; + } + carry = newCarry; + } + + if (carry) + { + scratchV[0] ^= 0xE1; + } + } + + scratchZ.CopyTo(X); + } + + // Set the contents of a span to all zero + static void SetSpanToZeros(ByteSpan span) + { + for (int ii = 0, nn = span.Length; ii != nn; ++ii) + { + span[ii] = 0; + } + } + } +} diff --git a/Hazel/Hazel.csproj b/Hazel/Hazel.csproj index a1d4c0c..f938a8d 100644 --- a/Hazel/Hazel.csproj +++ b/Hazel/Hazel.csproj @@ -73,6 +73,7 @@ + -- 2.39.5