diff --git a/crypto/cipher_extra/aead_test.cc b/crypto/cipher_extra/aead_test.cc
index 02e0d99..d0c266a 100644
--- a/crypto/cipher_extra/aead_test.cc
+++ b/crypto/cipher_extra/aead_test.cc
@@ -40,6 +40,10 @@
 constexpr uint32_t kCanTruncateTags = 1 << 1;
 // kVariableNonce indicates that the AEAD supports a variable-length nonce.
 constexpr uint32_t kVariableNonce = 1 << 2;
+// kNondeterministic indicates that the AEAD performs randomised encryption thus
+// one cannot assume that encrypting the same data will result in the same
+// ciphertext.
+constexpr uint32_t kNondeterministic = 1 << 7;
 
 // RequiresADLength encodes an AD length requirement into flags.
 constexpr uint32_t RequiresADLength(size_t length) {
@@ -58,6 +62,16 @@
   return (flags >> 3) & 0xf;
 }
 
+constexpr uint32_t RequiresMinimumTagLength(size_t length) {
+  // See above for statically checking the size at compile time with future C++
+  // versions.
+  return (length & 0xf) << 8;
+}
+
+constexpr size_t MinimumTagLength(uint32_t flags) {
+  return ((flags >> 8) & 0xf) == 0 ? 1 : ((flags >> 8) & 0xf);
+}
+
 struct KnownAEAD {
   const char name[40];
   const EVP_AEAD *(*func)(void);
@@ -87,6 +101,14 @@
     {"AES_256_GCM_SIV", EVP_aead_aes_256_gcm_siv, "aes_256_gcm_siv_tests.txt",
      0},
 
+    {"AES_128_GCM_RandomNonce", EVP_aead_aes_128_gcm_randnonce,
+     "aes_128_gcm_randnonce_tests.txt",
+     kNondeterministic | kCanTruncateTags | RequiresMinimumTagLength(13)},
+
+    {"AES_256_GCM_RandomNonce", EVP_aead_aes_256_gcm_randnonce,
+     "aes_256_gcm_randnonce_tests.txt",
+     kNondeterministic | kCanTruncateTags | RequiresMinimumTagLength(13)},
+
     {"ChaCha20Poly1305", EVP_aead_chacha20_poly1305,
      "chacha20_poly1305_tests.txt", kCanTruncateTags},
 
@@ -189,7 +211,8 @@
         ctx.get(), aead(), key.data(), key.size(), tag_len, evp_aead_seal));
 
     std::vector<uint8_t> out(in.size() + EVP_AEAD_max_overhead(aead()));
-    if (!t->HasAttribute("NO_SEAL")) {
+    if (!t->HasAttribute("NO_SEAL") &&
+        !(GetParam().flags & kNondeterministic)) {
       size_t out_len;
       ASSERT_TRUE(EVP_AEAD_CTX_seal(ctx.get(), out.data(), &out_len, out.size(),
                                     nonce.data(), nonce.size(), in.data(),
@@ -269,7 +292,8 @@
       "crypto/cipher_extra/test/" + std::string(aead_config.test_vectors);
   FileTestGTest(test_vectors.c_str(), [&](FileTest *t) {
     if (t->HasAttribute("NO_SEAL") ||
-        t->HasAttribute("FAILS")) {
+        t->HasAttribute("FAILS") ||
+        (aead_config.flags & kNondeterministic)) {
       t->SkipCurrent();
       return;
     }
@@ -337,7 +361,8 @@
 
     std::vector<uint8_t> out(in.size());
     std::vector<uint8_t> out_tag(EVP_AEAD_max_overhead(aead()));
-    if (!t->HasAttribute("NO_SEAL")) {
+    if (!t->HasAttribute("NO_SEAL") &&
+        !(aead_config.flags & kNondeterministic)) {
       size_t out_tag_len;
       ASSERT_TRUE(EVP_AEAD_CTX_seal_scatter(
           ctx.get(), out.data(), out_tag.data(), &out_tag_len, out_tag.size(),
@@ -469,9 +494,10 @@
   const size_t nonce_len = EVP_AEAD_nonce_length(aead());
   ASSERT_GE(sizeof(nonce), nonce_len);
 
+  const size_t tag_len = MinimumTagLength(GetParam().flags);
   bssl::ScopedEVP_AEAD_CTX ctx;
   ASSERT_TRUE(EVP_AEAD_CTX_init(ctx.get(), aead(), key, key_len,
-                                1 /* one byte tag */, NULL /* ENGINE */));
+                                tag_len, NULL /* ENGINE */));
 
   const uint8_t plaintext[1] = {'A'};
 
@@ -492,7 +518,7 @@
 
   const size_t overhead_used = ciphertext_len - sizeof(plaintext);
   const size_t expected_overhead =
-      1 + EVP_AEAD_max_overhead(aead()) - EVP_AEAD_max_tag_len(aead());
+      tag_len + EVP_AEAD_max_overhead(aead()) - EVP_AEAD_max_tag_len(aead());
   EXPECT_EQ(overhead_used, expected_overhead)
       << "AEAD is probably ignoring request to truncate tags.";
 
@@ -578,8 +604,11 @@
   ASSERT_TRUE(EVP_AEAD_CTX_seal(ctx.get(), in, &out_len,
                                 sizeof(kPlaintext) + max_overhead, nonce.data(),
                                 nonce_len, in, sizeof(kPlaintext), nullptr, 0));
-  EXPECT_EQ(Bytes(valid_encryption.data(), valid_encryption_len),
-            Bytes(in, out_len));
+
+  if (!(GetParam().flags & kNondeterministic)) {
+    EXPECT_EQ(Bytes(valid_encryption.data(), valid_encryption_len),
+              Bytes(in, out_len));
+  }
 
   OPENSSL_memcpy(in, valid_encryption.data(), valid_encryption_len);
   ASSERT_TRUE(EVP_AEAD_CTX_open(ctx.get(), in, &out_len, valid_encryption_len,
diff --git a/crypto/cipher_extra/test/aes_128_gcm_randnonce_tests.txt b/crypto/cipher_extra/test/aes_128_gcm_randnonce_tests.txt
new file mode 100644
index 0000000..e28fdb6
--- /dev/null
+++ b/crypto/cipher_extra/test/aes_128_gcm_randnonce_tests.txt
@@ -0,0 +1,30 @@
+# These tests are versions of the tests from the corresponding AES-GCM test
+# file, but with the nonce appended to the tag.
+
+KEY: d480429666d48b400633921c5407d1d1
+NONCE:
+IN:
+AD:
+CT:
+TAG: 7d7daf44850921a34e636b01adeb104f3388c676dc754acfa66e172a
+
+KEY: 3881e7be1bb3bbcaff20bdb78e5d1b67
+NONCE:
+IN: 0a2714aa7d
+AD: c60c64bbf7
+CT: 5626f96ecb
+TAG: ff4c4f1d92b0abb1d0820833d9eb83c7dcf5b7ae2d7552e2297fcfa9
+
+KEY: ea4f6f3c2fed2b9dd9708c2e721ae00f
+NONCE:
+IN: 8d6c08446cb10d9a2075
+AD: 5c65d4f261d2c54ffe6a
+CT: 0f51f7a83c5b5aa796b9
+TAG: 70259cddfe8f9a15a5c5eb485af578fbf975809ddb5172382745634f
+
+KEY: 31d93fd51c2d6450cf35d9edd71413f4
+NONCE:
+IN: e78eba6c58f93cc2374932fc21e54f695f2daeda3bd1e0121a77d178e3bf5c0e824a99042e8f2522df829d014e4d35a756780e8c07f53ca8fb78db6fb76754ad461665051c4572b2514804d0a9cbae1a1a013b796565eee13a7832ab8834b8406b1185332552d38754dde2344ff4f6e4823390964ba2dc43de136f2235b1d919e0f4ad60813d30f0ac1dad35abe3bee9479337c7b430841d2c722f12aeaf931cedd8a82053f697fff8d07f0af6013da7da58a5dfcf45561943e7ccdfd8d11fbe96a68a5a27982e47346500c0284caf8e6b63c6621e80503a7365d6693dc9a249093dc45221cfd88562e25910034c2c123e44e3b09d8a8a15547285d2596b98c7a0ee9d10b2cdb032d08a6caee1212420b6854181a583c15e046aa202dd
+AD: a4fdd42aad5475ffc1b122170024486406033c8640233cd9b23c286fdd40c5b69eee39cfbf965f7a10c73663f9804e6821c4f62980f8362a580bab446325b009a004b60b1dbd12566b55b42e58d8037d86c1050cd6ecaaac2fb0ef616a15bc5bcd8252fd459165795c500bbb2fb1476e5cfef9549db733be65bde391c810d099e3745a2cc7a94debe1f4ff6653b338123ef7d2f9a602bc9a4bbe757a63f932a802014f2f06c6688faf14332a355b1025f33687124399f55b6a5adb4864727ec6c5334c41d78d1463400925f6c29c0f611f35c9640045a740dad5b4f0dcb632e7f9a3478b526aa9f97cd9f8d3ad094b7922890e7b6d9c67fcc4f747d04ddcd115fba0a8f0433c6fb1bf6011a9cd153f866c76b26d427a25aebc60d10540
+CT: 8d668fb50efda82552aeb5d075ff3977c37929d73f6639289e7c6da8c89c664df80b2387e788d12398d62d3c0ed2f9f918010d41021c464d54f016c4e10e85e29ba3a45793df2ebd6cdf30045363434387bb0d20439f4986e6eb7ae9fd85fe776f7b8035025624c2413ca8491cc6e79fe901b9c40ff3a0e37a7c7e88b56de4fee65861865162821e046846d253982e4ecd17bd26214b0923a4297d4ed9423395d856940829ca5ee74488c3b4d8aa3c5ceade17d8a3f2e45d3ba91360ac1c76d6a29f8243bf49c1d75aa41ba239fa6f3b123e198ba799e3b70c674607c5371894800954eda0264b3b82606433f71371dabc5f1fb3d703232533662920a241f613c38d16b0bad24f4aa3b336af89cdcd2f371e1bed7aaa47c56d17100a01
+TAG: 594ee5c93636cfb5fde940e3d561440a28f6f0c288c9f92e80252e1e
diff --git a/crypto/cipher_extra/test/aes_256_gcm_randnonce_tests.txt b/crypto/cipher_extra/test/aes_256_gcm_randnonce_tests.txt
new file mode 100644
index 0000000..caabc42
--- /dev/null
+++ b/crypto/cipher_extra/test/aes_256_gcm_randnonce_tests.txt
@@ -0,0 +1,30 @@
+# These tests are versions of the tests from the corresponding AES-GCM test
+# file, but with the nonce appended to the tag.
+
+KEY: e5ac4a32c67e425ac4b143c83c6f161312a97d88d634afdf9f4da5bd35223f01
+NONCE:
+IN:
+AD:
+CT:
+TAG: d7cba289d6d19a5af45dc13857016bac5bf11a0951f0bfc7ea5c9e58
+
+KEY: 73ad7bbbbc640c845a150f67d058b279849370cd2c1f3c67c4dd6c869213e13a
+NONCE:
+IN: f0535fe211
+AD: e91428be04
+CT: e9b8a896da
+TAG: 9115ed79f26a030c14947b3e454db9e7a330a184fc245812f4820caa
+
+KEY: 80e2e561886eb2a953cf923aaac1653ed2db0111ee62e09cb20d9e2652bd3476
+NONCE:
+IN: 96669d2d3542a4d49c7c
+AD: e51e5bce7cbceb660399
+CT: 4521953e7d39497e4563
+TAG: 2083e3c0d84d663066bbe2961b08dcf75daf201589654da8884c3c68
+
+KEY: 31dbefe589b661af00a6fbad426e013f30f448c763f957bbcbaf9c09764f4a95
+NONCE:
+IN: 908bd801b70d85085dd480e1207a4a4b7ef179dac495a9befb16afe5adf7cb6f6d734882e6e96f587d38bfc080341dc8d5428a5fe3498b9d5faa497f60646bcb1155d2342f6b26381795daeb261d4ab1415f35c6c8ac9c8e90ea34823122df25c6ddae365cc66d92fc2fe2941f60895e00233b2e5968b01e2811c8c6f7a0a229f1c301a72715bd5c35234c1be81ef7d5cc2779e146314d3783a7aa72d87a8f107654b93cb66e3648c26fc9e4a2f0378fa178c586d096092f6a80e2e03708da72d6e4d7316c2384a522459a4ad369c82d192f6f695b0d90fcc47c6f86b8bbc6f2f4ea303aa64f5ce8b8710da62482147bcc29c8238116549256a7a011fd9c78bbb8c40e278740dc156c2cc99c3591fec2918cdeb5240fb428
+AD: 5a32d7044f003b2ffefffe5896933f4d8d64909fa03e321a1bdf063099b9f89752d72e877291d8da12340c5dd570d7d42984ffab5177824fc5483b4faf488504e6822e371dca9af541c6a97312b9cbf341b4198b0902cd2985ac10a8b5b5fe9691bb29a88344f863c980e4e871a72a8b74f92eef68c176e9d2ef037898ff567298e186af52ec62eb7429a8004ac46b945678b82859396d36d388ec3d67653aec35cf1da2684bbc6c78a5f9e3ce1b355af3b207f64e0fa73501c5d48a14638d0906c87eaa876debcf1a532c1475d80ed3d4b96458d2236eb9f67988863bc6d5c16b96b93d898683d248d7bc601b5035fc365481b89465e37a8f7dd64635e19a0282639cecde72c6b1638e0aa6e56f9c00d031cdadc59ce37e
+CT: aeab9db30a579ca54195e54a9e6c787f40100c6d12ceee35643f36ae45f618cc9bb66aa4c0fae0ec2686cb4101a5b23a46877460c7e020b38b0d8d1f533ecfa99df03d346bc854a578276d7d5685ad1fb03655683a64aae4159c9efa6781f053057e0811226c7c533967a94587f4025353b28cc3a2ce5763783b4c31e7818b8ad9195bc03be8f294f9f6ceac578f9d30b22b1f5a68d647d46cf6db4a9c3a8a5c06fa97c9efb4578f501ea96db1f40942e3f24c44a7e4070a6b931c39947d9692930b67767357015de51a39e46fff94b6019e4bc1ad9d216a571ba0dc88859c49d2c487ca657384e49b4d382d86a60c8d5195320909c4e82fc077a3b22bd4eccf0f067e66ec78eed642b2d16f0f304f60f1d9ba69e205c982
+TAG: 17ca09e3084504fc22e914ee28312c8e147fe99bba0f606c57242314
diff --git a/crypto/fipsmodule/cipher/e_aes.c b/crypto/fipsmodule/cipher/e_aes.c
index 6d9b40d..6df2b7b 100644
--- a/crypto/fipsmodule/cipher/e_aes.c
+++ b/crypto/fipsmodule/cipher/e_aes.c
@@ -933,21 +933,19 @@
 
 static void aead_aes_gcm_cleanup(EVP_AEAD_CTX *ctx) {}
 
-static int aead_aes_gcm_seal_scatter(const EVP_AEAD_CTX *ctx, uint8_t *out,
-                                     uint8_t *out_tag, size_t *out_tag_len,
-                                     size_t max_out_tag_len,
-                                     const uint8_t *nonce, size_t nonce_len,
-                                     const uint8_t *in, size_t in_len,
-                                     const uint8_t *extra_in,
-                                     size_t extra_in_len,
-                                     const uint8_t *ad, size_t ad_len) {
-  struct aead_aes_gcm_ctx *gcm_ctx = (struct aead_aes_gcm_ctx *) &ctx->state;
-
-  if (extra_in_len + ctx->tag_len < ctx->tag_len) {
+static int aead_aes_gcm_seal_scatter_impl(
+    const struct aead_aes_gcm_ctx *gcm_ctx,
+    uint8_t *out, uint8_t *out_tag, size_t *out_tag_len, size_t max_out_tag_len,
+    const uint8_t *nonce, size_t nonce_len,
+    const uint8_t *in, size_t in_len,
+    const uint8_t *extra_in, size_t extra_in_len,
+    const uint8_t *ad, size_t ad_len,
+    size_t tag_len) {
+  if (extra_in_len + tag_len < tag_len) {
     OPENSSL_PUT_ERROR(CIPHER, CIPHER_R_TOO_LARGE);
     return 0;
   }
-  if (max_out_tag_len < extra_in_len + ctx->tag_len) {
+  if (max_out_tag_len < extra_in_len + tag_len) {
     OPENSSL_PUT_ERROR(CIPHER, CIPHER_R_BUFFER_TOO_SMALL);
     return 0;
   }
@@ -991,18 +989,35 @@
     }
   }
 
-  CRYPTO_gcm128_tag(&gcm, out_tag + extra_in_len, ctx->tag_len);
-  *out_tag_len = ctx->tag_len + extra_in_len;
+  CRYPTO_gcm128_tag(&gcm, out_tag + extra_in_len, tag_len);
+  *out_tag_len = tag_len + extra_in_len;
 
   return 1;
 }
 
-static int aead_aes_gcm_open_gather(const EVP_AEAD_CTX *ctx, uint8_t *out,
-                                    const uint8_t *nonce, size_t nonce_len,
-                                    const uint8_t *in, size_t in_len,
-                                    const uint8_t *in_tag, size_t in_tag_len,
-                                    const uint8_t *ad, size_t ad_len) {
-  struct aead_aes_gcm_ctx *gcm_ctx = (struct aead_aes_gcm_ctx *) &ctx->state;
+static int aead_aes_gcm_seal_scatter(const EVP_AEAD_CTX *ctx, uint8_t *out,
+                                     uint8_t *out_tag, size_t *out_tag_len,
+                                     size_t max_out_tag_len,
+                                     const uint8_t *nonce, size_t nonce_len,
+                                     const uint8_t *in, size_t in_len,
+                                     const uint8_t *extra_in,
+                                     size_t extra_in_len,
+                                     const uint8_t *ad, size_t ad_len) {
+  const struct aead_aes_gcm_ctx *gcm_ctx =
+      (const struct aead_aes_gcm_ctx *)&ctx->state;
+  return aead_aes_gcm_seal_scatter_impl(
+      gcm_ctx, out, out_tag, out_tag_len, max_out_tag_len, nonce, nonce_len, in,
+      in_len, extra_in, extra_in_len, ad, ad_len, ctx->tag_len);
+}
+
+static int aead_aes_gcm_open_gather_impl(const struct aead_aes_gcm_ctx *gcm_ctx,
+                                         uint8_t *out,
+                                         const uint8_t *nonce, size_t nonce_len,
+                                         const uint8_t *in, size_t in_len,
+                                         const uint8_t *in_tag,
+                                         size_t in_tag_len,
+                                         const uint8_t *ad, size_t ad_len,
+                                         size_t tag_len) {
   uint8_t tag[EVP_AEAD_AES_GCM_TAG_LEN];
 
   if (nonce_len == 0) {
@@ -1010,7 +1025,7 @@
     return 0;
   }
 
-  if (in_tag_len != ctx->tag_len) {
+  if (in_tag_len != tag_len) {
     OPENSSL_PUT_ERROR(CIPHER, CIPHER_R_BAD_DECRYPT);
     return 0;
   }
@@ -1037,8 +1052,8 @@
     }
   }
 
-  CRYPTO_gcm128_tag(&gcm, tag, ctx->tag_len);
-  if (CRYPTO_memcmp(tag, in_tag, ctx->tag_len) != 0) {
+  CRYPTO_gcm128_tag(&gcm, tag, tag_len);
+  if (CRYPTO_memcmp(tag, in_tag, tag_len) != 0) {
     OPENSSL_PUT_ERROR(CIPHER, CIPHER_R_BAD_DECRYPT);
     return 0;
   }
@@ -1046,6 +1061,17 @@
   return 1;
 }
 
+static int aead_aes_gcm_open_gather(const EVP_AEAD_CTX *ctx, uint8_t *out,
+                                    const uint8_t *nonce, size_t nonce_len,
+                                    const uint8_t *in, size_t in_len,
+                                    const uint8_t *in_tag, size_t in_tag_len,
+                                    const uint8_t *ad, size_t ad_len) {
+  struct aead_aes_gcm_ctx *gcm_ctx = (struct aead_aes_gcm_ctx *)&ctx->state;
+  return aead_aes_gcm_open_gather_impl(gcm_ctx, out, nonce, nonce_len, in,
+                                       in_len, in_tag, in_tag_len, ad, ad_len,
+                                       ctx->tag_len);
+}
+
 DEFINE_METHOD_FUNCTION(EVP_AEAD, EVP_aead_aes_128_gcm) {
   memset(out, 0, sizeof(EVP_AEAD));
 
@@ -1091,6 +1117,116 @@
   out->open_gather = aead_aes_gcm_open_gather;
 }
 
+static int aead_aes_gcm_init_randnonce(EVP_AEAD_CTX *ctx, const uint8_t *key,
+                                       size_t key_len,
+                                       size_t requested_tag_len) {
+  if (requested_tag_len != EVP_AEAD_DEFAULT_TAG_LENGTH) {
+    if (requested_tag_len < AES_GCM_NONCE_LENGTH) {
+      OPENSSL_PUT_ERROR(CIPHER, CIPHER_R_BUFFER_TOO_SMALL);
+      return 0;
+    }
+    requested_tag_len -= AES_GCM_NONCE_LENGTH;
+  }
+
+  if (!aead_aes_gcm_init(ctx, key, key_len, requested_tag_len)) {
+    return 0;
+  }
+
+  ctx->tag_len += AES_GCM_NONCE_LENGTH;
+  return 1;
+}
+
+static int aead_aes_gcm_seal_scatter_randnonce(
+    const EVP_AEAD_CTX *ctx,
+    uint8_t *out, uint8_t *out_tag, size_t *out_tag_len, size_t max_out_tag_len,
+    const uint8_t *external_nonce, size_t external_nonce_len,
+    const uint8_t *in, size_t in_len,
+    const uint8_t *extra_in, size_t extra_in_len,
+    const uint8_t *ad, size_t ad_len) {
+  if (external_nonce_len != 0) {
+    OPENSSL_PUT_ERROR(CIPHER, CIPHER_R_INVALID_NONCE_SIZE);
+    return 0;
+  }
+
+  uint8_t nonce[AES_GCM_NONCE_LENGTH];
+  if (max_out_tag_len < sizeof(nonce)) {
+    OPENSSL_PUT_ERROR(CIPHER, CIPHER_R_BUFFER_TOO_SMALL);
+    return 0;
+  }
+
+  RAND_bytes(nonce, sizeof(nonce));
+  const struct aead_aes_gcm_ctx *gcm_ctx =
+      (const struct aead_aes_gcm_ctx *)&ctx->state;
+  if (!aead_aes_gcm_seal_scatter_impl(gcm_ctx, out, out_tag, out_tag_len,
+                                      max_out_tag_len - AES_GCM_NONCE_LENGTH,
+                                      nonce, sizeof(nonce), in, in_len,
+                                      extra_in, extra_in_len, ad, ad_len,
+                                      ctx->tag_len - AES_GCM_NONCE_LENGTH)) {
+    return 0;
+  }
+
+  assert(*out_tag_len + sizeof(nonce) <= max_out_tag_len);
+  memcpy(out_tag + *out_tag_len, nonce, sizeof(nonce));
+  *out_tag_len += sizeof(nonce);
+
+  return 1;
+}
+
+static int aead_aes_gcm_open_gather_randnonce(
+    const EVP_AEAD_CTX *ctx, uint8_t *out,
+    const uint8_t *external_nonce, size_t external_nonce_len,
+    const uint8_t *in, size_t in_len,
+    const uint8_t *in_tag, size_t in_tag_len,
+    const uint8_t *ad, size_t ad_len) {
+  if (external_nonce_len != 0) {
+    OPENSSL_PUT_ERROR(CIPHER, CIPHER_R_INVALID_NONCE_SIZE);
+    return 0;
+  }
+
+  if (in_tag_len < AES_GCM_NONCE_LENGTH) {
+    OPENSSL_PUT_ERROR(CIPHER, CIPHER_R_BAD_DECRYPT);
+    return 0;
+  }
+  const uint8_t *nonce = in_tag + in_tag_len - AES_GCM_NONCE_LENGTH;
+
+  const struct aead_aes_gcm_ctx *gcm_ctx =
+      (const struct aead_aes_gcm_ctx *)&ctx->state;
+  return aead_aes_gcm_open_gather_impl(
+      gcm_ctx, out, nonce, AES_GCM_NONCE_LENGTH, in, in_len, in_tag,
+      in_tag_len - AES_GCM_NONCE_LENGTH, ad, ad_len,
+      ctx->tag_len - AES_GCM_NONCE_LENGTH);
+}
+
+DEFINE_METHOD_FUNCTION(EVP_AEAD, EVP_aead_aes_128_gcm_randnonce) {
+  memset(out, 0, sizeof(EVP_AEAD));
+
+  out->key_len = 16;
+  out->nonce_len = 0;
+  out->overhead = EVP_AEAD_AES_GCM_TAG_LEN + AES_GCM_NONCE_LENGTH;
+  out->max_tag_len = EVP_AEAD_AES_GCM_TAG_LEN + AES_GCM_NONCE_LENGTH;
+  out->seal_scatter_supports_extra_in = 1;
+
+  out->init = aead_aes_gcm_init_randnonce;
+  out->cleanup = aead_aes_gcm_cleanup;
+  out->seal_scatter = aead_aes_gcm_seal_scatter_randnonce;
+  out->open_gather = aead_aes_gcm_open_gather_randnonce;
+}
+
+DEFINE_METHOD_FUNCTION(EVP_AEAD, EVP_aead_aes_256_gcm_randnonce) {
+  memset(out, 0, sizeof(EVP_AEAD));
+
+  out->key_len = 32;
+  out->nonce_len = 0;
+  out->overhead = EVP_AEAD_AES_GCM_TAG_LEN + AES_GCM_NONCE_LENGTH;
+  out->max_tag_len = EVP_AEAD_AES_GCM_TAG_LEN + AES_GCM_NONCE_LENGTH;
+  out->seal_scatter_supports_extra_in = 1;
+
+  out->init = aead_aes_gcm_init_randnonce;
+  out->cleanup = aead_aes_gcm_cleanup;
+  out->seal_scatter = aead_aes_gcm_seal_scatter_randnonce;
+  out->open_gather = aead_aes_gcm_open_gather_randnonce;
+}
+
 struct aead_aes_gcm_tls12_ctx {
   struct aead_aes_gcm_ctx gcm_ctx;
   uint64_t min_next_nonce;
diff --git a/include/openssl/aead.h b/include/openssl/aead.h
index 6d78db2..3bc74e7 100644
--- a/include/openssl/aead.h
+++ b/include/openssl/aead.h
@@ -146,6 +146,30 @@
 // https://tools.ietf.org/html/draft-irtf-cfrg-gcmsiv-02
 OPENSSL_EXPORT const EVP_AEAD *EVP_aead_aes_256_gcm_siv(void);
 
+// EVP_aead_aes_128_gcm_randnonce is AES-128 in Galois Counter Mode with
+// internal nonce generation. The 12-byte nonce is appended to the tag
+// and is generated internally. The "tag", for the purpurses of the API, is thus
+// 12 bytes larger. The nonce parameter when using this AEAD must be
+// zero-length. Since the nonce is random, a single key should not be used for
+// more than 2^32 seal operations.
+//
+// Warning: this is for use for FIPS compliance only. It is probably not
+// suitable for other uses. Using standard AES-GCM AEADs allows one to achieve
+// the same effect, but gives more control over nonce storage.
+OPENSSL_EXPORT const EVP_AEAD *EVP_aead_aes_128_gcm_randnonce(void);
+
+// EVP_aead_aes_256_gcm_randnonce is AES-256 in Galois Counter Mode with
+// internal nonce generation. The 12-byte nonce is appended to the tag
+// and is generated internally. The "tag", for the purpurses of the API, is thus
+// 12 bytes larger. The nonce parameter when using this AEAD must be
+// zero-length. Since the nonce is random, a single key should not be used for
+// more than 2^32 seal operations.
+//
+// Warning: this is for use for FIPS compliance only. It is probably not
+// suitable for other uses. Using standard AES-GCM AEADs allows one to achieve
+// the same effect, but gives more control over nonce storage.
+OPENSSL_EXPORT const EVP_AEAD *EVP_aead_aes_256_gcm_randnonce(void);
+
 // EVP_aead_aes_128_ccm_bluetooth is AES-128-CCM with M=4 and L=2 (4-byte tags
 // and 13-byte nonces), as decribed in the Bluetooth Core Specification v5.0,
 // Volume 6, Part E, Section 1.
diff --git a/sources.cmake b/sources.cmake
index 7daa7e2..d7b527b 100644
--- a/sources.cmake
+++ b/sources.cmake
@@ -12,6 +12,7 @@
   crypto/cipher_extra/test/aes_128_ccm_bluetooth_tests.txt
   crypto/cipher_extra/test/aes_128_ccm_bluetooth_8_tests.txt
   crypto/cipher_extra/test/aes_128_ctr_hmac_sha256.txt
+  crypto/cipher_extra/test/aes_128_gcm_randnonce_tests.txt
   crypto/cipher_extra/test/aes_128_gcm_siv_tests.txt
   crypto/cipher_extra/test/aes_128_gcm_tests.txt
   crypto/cipher_extra/test/aes_192_gcm_tests.txt
@@ -20,6 +21,7 @@
   crypto/cipher_extra/test/aes_256_cbc_sha256_tls_tests.txt
   crypto/cipher_extra/test/aes_256_cbc_sha384_tls_tests.txt
   crypto/cipher_extra/test/aes_256_ctr_hmac_sha256.txt
+  crypto/cipher_extra/test/aes_256_gcm_randnonce_tests.txt
   crypto/cipher_extra/test/aes_256_gcm_siv_tests.txt
   crypto/cipher_extra/test/aes_256_gcm_tests.txt
   crypto/cipher_extra/test/chacha20_poly1305_tests.txt