Nonce reuse/misuse resistance authentication encryption schemes for modern TLS cipher suites and QUIC based web servers

Abstract

Authentication Encryption with Associated Data (AEAD) is a scheme that preserves the integrity of both the cipher text and authenticated data. In AEAD, cipher suites like GCM_SIV and AES_GCM_SIV provides the message integrity through nonce-based authentication encryption technique. The problem of nonce-based authentication encryption is the repetition of nonce in two different messages that violates message integrity property when the number of message blocks is maximized to 2³². This paper verifies the maximum limit of nonce usefulness and proves better security bounds attained in GCM_SIV and AES_GCM_SIV using nonce-reuse/misuse resistance authentication encryption (NRMR-AE) technique. The NRMR-AE resistance property achieves better security bounds and performance even when the nonces are repeated in different messages. But nonce repetition in NRMR-AE property reduces the number of message encryption and message length (in blocks) in GCM_SIV and AES_GCM_SIV AEAD methods used in QUIC(Quick UDP Internet Communications) and TLS Cipher suites which is found to be a greater drawback. This paper increases the number of messages encrypted even with maximum number of nonce repetition ensuring that the message length in AES_GCM_SIV meets the standard NIST bound 2^-32.

1 Introduction

An Authenticated Encryption (AE) technique is a symmetric key method that provides both confidentiality and integrity in TLS communication data exchange between two end systems. In a number of AE schemes [17], the most popular scheme since evolution is Galosis Counter Mode (GCM) operation which achieves privacy and authenticity of a data using GHASH and GCTR functions [5]. The GCM works on parallizable encryption method using AES block cipher. GCM achieves better performance and minimize the time during encryption of bulk data in TLS communications. Among number of Cipher suites, the most famous CIPHERSUITE is AES_GCM [14, 16] which is an Authenticated Encryption with Authenticated Data (AEAD). AEAD provides secrecy and realism in TLS record layer encryption and QUIC protocol function which works on the methodology of nonce-based authentication encryption (nAE). The nonce used in GCM encryption is repeated for two different messages that compromise the security future cipher texts by active adversary attacks.

The main problem of GCM is nonce repetition in two different messages which compromises the security in universal hash function (GHASH) resulting in revealing the secret key of a message. The adversary will then forge the future cipher texts. So the nonce-based authentication cipher suites are not suitable for modern TLS cipher suites and QUIC based web servers [23, 24]. In order to achieve the security in nonce-based authentication encryption scheme random nonces are generated instead of unique pattern of nonces. But due to poor randomness on smarter devices the random nonces are also repeated infrequent and breach the security in cipher suites. So Rogaway and Shrimpton modified the nAE schemes and formulized to nonce-reuse/misuse resistance authentication encryption (NRMR-AE) [17] that provides the confidentiality and authenticity even if the nonces are repeated in two different messages. The adversary is only able to capture the minimal information of the data that does not violate the authenticity.

The base of the NRMR-AE scheme is Synthetic IV (SIV) [5] method that resists the nonce-misuse problem. Based on this SIV method, the new method named GCM_SIV was proposed that rely on nonce-misuse resistance property in TLS cipher suites and QUIC which achieves full security with maximum performance achieved in encrypting the data using pseudo random permutation (PRP) used in block cipher and pseudo random function (PRF) in IV encryption. The GCM_SIV method provides full nonce misuse resistance using the 96-bit nonce value and key derivation method using different (key, nonce) pair. Due to birthday bound attack in GCM_SIV on number of queries, the cipher text could be distinguished after crossing 2⁴⁸ queries. Solving the problems of GCM_SIV, number of different variations was formulized from GCM_SIV as GCM_SIV1, GCM_SIV2 and GCM_SIVr [20]. This achieves a better birthday bound security from 2ⁿ/2 to 2ⁿ called beyond birthday bound security (BBB) [12].

In GCM_SIV encryption method, 2³¹ different messages are encrypted that achieves the NIST standard of IV collision in 2^-32 complexity. So the birthday bound security of GCM_SIV is 2³² with the message length of 2¹⁶.But limited number of messages encrypted is a major problem for QUIC and TLS for handling the large amount of data [23, 24]. So a new standard of NRMR-AE scheme named AES_GCM_SIV [8] is formulized which achieves better security and better performance when encrypting more number of messages with repeated nonces.

With the incidence of the security challenges, the following objectives were contributed.

Verifying and proving security bounds of GCM_SIV, GCM_SIV⁺ and AES_GCM_SIV.

Based on the nonce based authentication scheme, the AES_GCM_SIV achieves better performance against modern TLS Cipher Suites and QUIC web servers.

Finally, the proposed work results in increasing the message length in blocks during the repetition of nonce with maximized performance and better security as per NIST standards.

2 Literature survey

Mennink et al. proposed [1] optimal PRFs from Block cipher designs. This paper applies pseudorandom permutation function on GCM, GCM_SIV and AES. This paper also suggests the performance and security improvement of message encryption on various cipher suites is increased. Shoni Gilboa et al. [7] proposes truncated permutation from random function. This paper gives the solution of applying random permutation from a random function on block cipher and their advantages. Ashur et al. [21] proposes boosting authentication encryption robustness with minimal modification. This paper ensures the performance Authentication encryption (AE) algorithms like AES_GCM and CHACHA20_POLY1305. This paper also attains higher performance when using AES_NI instructions set and lower performance without AES_NI instruction set.

Antonie Joux [13] proposes Authentication failures in AE algorithms like NIST version of GCM. This paper analyses and proposes the security violence of GCM under the chosen cipher text attack (CCA). Bock et al. [9] proposes various practical forgery attacks on GCM in TLS. This paper focuses the security violence of AES_GCM that is used most modern cipher suites and QUIC server [21]. This paper also identifies the authenticity problem over 70,000 HTTPS connections. Gueron et al. [5] proposed full nonce misuse-resistant authentication encryption at one cycle per byte. This paper achieves the optimized performance and security using AES_NI and PCLMULQDQ operations with the help of GCM_SIV authentication encryption. But the GCM_SIV authentication encryption method falls the birthday bound security at 2⁴⁷. Gueron [8] proposed Nonce based key derivation on Authentication encryption block cipher modes. This paper analysis chosen plaintext attack, Authentication Encryption, nonce-misuse resistance properties block cipher modes. This paper also increases the performance in hardware using key-derivation function.

The existing works of Authentication encryption algorithms gives the solution of proper nonce usefulness on various TLS cipher suites and various servers. It also discusses the performance of nonce based authentication encryption algorithms that are used in TLS and QUIC. But the existing works does not clearly define the nonce repetition procedure and nonce resistance property on various TLS communications and QUIC based web servers. The existing works also degrades the NIST security level on Authentication encryption algorithms when using repeating nonces. The previous AES_GCM AE algorithm can encrypt only 2³² messages using random nonces. But TLS and QUIC need to encrypt more messages with random nonces. But it also fails once the nonce is repeated two different messages. So the proposed work clearly depicts the nonce repetition and nonce misuse resistance property on modern TLS cipher suites and QUIC based web servers when using Authentication encryption algorithms.

This paper also suggests AES_GCM_SIV authentication encryption algorithm attains the maximum security level when repetition on nonces used and satisfy the NIST security bound with maximum nonce repetition and maximum message encryption on modern TLS cipher suites and QUIC based web servers.

3 Preliminaries

3.1 General notations

For set of all finite bit strings and the length of bit strings being n > 0, take 0, 1 ⁿ, 0, 1^* and 0, 1 ⁺. For, |X| initialize as the length of bit string X and the total length is |X|_n = [|X|/n] denoted by number of blocks. The bit string 0ⁿ represents 0ⁿ ∈ {0, 1} ⁿ and n denotes number of 0’s or number of 1’s. For any message M∈{0,1}^* and an integer l, msb_l(M) denotes most significant l bits of M and lsb_l(M) denotes the least significant l bits of M. The message is split into l blocks which is formulated as (M[i]..........M[j])← M, where M[i]..........M[j] specifies different bit strings that denotes the total message length. For a finite set X, $X \overset{R}{\leftarrow} K$ denotes the uniform random sampling of an element X from K.

3.2 Nonce-based authentication encryption

A nonce based authentication encryption with associated data scheme ∏ performs two different operations, one is encryption algorithm Π_e and decryption algorithm Π_d using set of K_Π ∈ {0, 1} ^*. We Formulate the nAE Π = (K_Π, Π_e, Π_d). In nAE scheme the encryption algorithm consists of key space (K), nonce space(N), associated data space(A) and message space(M) as inputs and produces the cipher text C belongs to {0,1}ⁿ and authentication tag T belongs to {0,1}^τ with constant τ. The decryption algorithm takes K, N, A, C and T as input and produces the valid plain text or special symbol ⊥. The general notation of nAE [14, 15] given by Equation (1) and (2) is,

$(C, T) \leftarrow Π_{e} (K, N, A, M)$ (1)

$M / ⊥ \leftarrow \prod_{d} (K, N, A, C, T)$ (2)

The general security definition of nonce based authentication encryption that provides better security against adversary is modified using nonce misuse resistance authentication encryption like

$\begin{matrix} {Adv}_{\prod}^{MRAE} (A) = Pr [A^{E (., ., .), D (., ., .)} \Rightarrow 1] \\ - Pr [A^{$ (., ., .), ⊥ (., ., .)} \Rightarrow 1] \end{matrix}$ (3)

Based on the above Equation (3) modified security definition, the adversary A does not repeat the same query after getting cipher text from a previous encryption query.

3.3 IV-based encryption

An IV based encryption scheme Π performs an encryption algorithm Π_e and decryption algorithm Π_d with set of keys K_e belongs to 0, 1ⁿ. From this IV encryption is formulated as Π = Π_e, Π_d and notation of IV based encryption and decryption [14, 15] given by Equation (4) and (5) is,

$C \leftarrow K_{e} \times IV \times M$ (4)

$P / ⊥ \leftarrow K_{e} \times IV \times C$ (5)

The advantage of adversary A in IV based encryption is defined as Equation (6) is,

${Adv}_{\prod}^{ivE} (A) = Pr [A^{π_{E} (.)} \Rightarrow 1] - Pr [A^{$ (.)} \Rightarrow 1]$ (6)

Based on the security definition given in Equation (6), the adversary computes Π_e(M) as C ←Π_e (K, M, IV) and $(M) selects random IV and computes C ←Π_e (K, M, IV) that returns C or T which in other case returns IV |C| random bits.

4 Descriptions

4.1 Synthetic IV (SIV)

The SIV [5 , 8] performs an encryption using a block cipher mode of operation. The encryption function of SIV takes inputs such as key (K), plaintext (P) and multiple variable length headers or Zero headers. The main advantage of SIV should authenticate the multiple headers without encrypting when transmitting bulks of data.

The SIV achieves Deterministic authentication encryption (DAE) and nonce based misuse authentication encryption. The SIV works in the method of Encrypt-and-MAC principle that was extracted from the scheme A4. The security of A4 scheme combines the IV based encryption and Vector MAC that achieves the nonce Authentication Encryption (nAE) which gives the nonce-reuse resistance. The security of A4 scheme is explained in the Theorem 1 and is verified using IV of PRF and Tag verification of PRF against adversary attacks

Theorem 1 (security of A4) [3]:

The ivE scheme denotes the function ɛ: K×{0,1}^s×M →{0,1}^*. Consider integers 1 ≤ η, τ ≤ r and let F: L×X^iv → {0,1}^r be a vector MAC from which F^iv: L×X^iv →{0,1}^η and F^tag: L×X^tag →{0,1}^τF^tag are derived. So the resulting nAE scheme denoted as ɛ= A [ɛ, F^IV, F^tag] includes block box reductions. Thus as a compromise of IVE security of ɛ, the PRF security F^IV and the PRF security of F^tag, the adversary could break the nAE security in SIV is specified in Equation (7).

${Adv}_{ɛ^{\land}}^{prf} (A) \leq {Adv}_{F}^{prf} (β (A) + {Adv}_{ɛ}^{ivE} (D (A)) + q_{d} / 2^{n}$ (7)

4.2 GCM_SIV

GCM-SIV [5] is a nonce based authentication encryption scheme that achieves full security using the components of GHASH and CTR. The GCM-SIV performs the encryption function using input Nonce (N), Authentication Data (A) and Message (M) and produces the cipher text with authentication using GHASH and CTR functions. The GCM_SIV encryption algorithm is detailed in Table 1.

Table 1
GCM_SIV encryption algorithm

Input: (N), (A), (M) GHASH_L (A, M) CTR_K (IV, m)

Deriver Key: K, K₁ len ← str_n/2 (|A|) ||str_n/2 (|M|) if m = 0 then S←∈

Ver ← GHASH_L(N,A,M) X ← A ∥ 0^n|A|_n-|A| ∥ M ∥ 0^n|M|_n-|M| ∥ len else

Tag ← E_{K
¹} (Ver) Y ← 0 ⁿ I ← IV

IV ← msb_n-k (Tag) ∥ 0^k for j ← 1 to x do S[1] ← E_K(I[1])

m ← |M|_n Y ← L.(Y ⊕ X[j]) for i ← 2 to m do

N ← CTR_K (IV, m) return Y I[i] ← inc(I[i–1])

C ← M ⊕ msb_|M| (N) N[i] ← E_K(I[i])

Return (C, T) N ← N [1] ∥ . . … ∥ N [m]

Return

Input: (N), (A), (M)	GHASH_L (A, M)	CTR_K (IV, m)
Deriver Key: K, K₁	len ← str_n/2 (\|A\|) \|\|str_n/2 (\|M\|)	if m = 0 then S←∈
Ver ← GHASH_L(N,A,M)	X ← A ∥ 0^n\|A\|_n-\|A\| ∥ M ∥ 0^n\|M\|_n-\|M\| ∥ len	else
Tag ← E_{K ¹} (Ver)	Y ← 0 ⁿ	I ← IV
IV ← msb_n-k (Tag) ∥ 0^k	for j ← 1 to x do	S[1] ← E_K(I[1])
m ← \|M\|_n	Y ← L.(Y ⊕ X[j])	for i ← 2 to m do
N ← CTR_K (IV, m)	return Y	I[i] ← inc(I[i–1])
C ← M ⊕ msb_\|M\| (N)		N[i] ← E_K(I[i])
Return (C, T)		N ← N [1] ∥ . . … ∥ N [m]
Return

Figure 1 depicts the GCM_SIV encryptin algorithm using the master keys of K1 and K2.

Fig. 1

GCM_SIV Encryption.

So the security of GCM-SIV [26] includes a PRF function of CTR and GHASH function that achieves the nonce authentication encryption Equation (8). ${Adv}_{GCN - SIV}^{MRAE} (A) < 2 . {Adv}_{F}^{prf} (A^{\land}) + (\frac{M}{n}) + \frac{{(q_{E} (A) + q_{D} (A))}^{2} + q_{D} (A)}{2^{n}} + \frac{q_{E} {(A)}^{2}}{2^{n - k}}$ (8)

4.3 AES_GCM_SIV

The AES-GCM-SIV [6, 8] is one of the most important AEAD schemes which achieve better security and better performance in the use of nonce repetition compared to other GCM-SIV methods. The AES-GCM-SIV is an AEAD cipher which combines the GCM-SIV constructions. This combined construction differs from two important functions from GCM-SIV that includes POLYVAL hash function instead of GHASH and varied key derivation function. The main construction of AES-GCM-SIV consists of GCM-SIV⁺ and key derivation based on nonce and master key.

Figure 2 explains the AES_GCM_SIV encryption and decryption algorithm using the nonce and secret key values. The algorithm explains the GCTR and GHash functions.

Fig. 2

AES_GCM_SIV Encryption.

The implementation of AES_GCM_SIV encryption algorithm is summarized in Table 2 involving key generation and PolyVal creation.

Table 2

AES_GCM_SIV Encryption Algorithm

Key: K (Master Key]
Key length = 128 or 256
If k = 128, Apply AES128 else AES256
Input: K, N, A, M
Encryption:
(k1,k2)=key Der (K,N)
T_i = Trunc₆₄ (AES_K (N\|\| [i] ₃₂)) then,
K₁ = T₁\|\| T₀ and K₂ = T₃\|\| T₂ if key = 128
Else
K₂ = T₅\|\| T₄ \|\| T3\|\| T₂ if key = 256
TAG=Hash-then-Encrypt [H, E] _K1,K2 (N, A, M)
E_k2 (H_k1 (A, M)+N), then
H_k1 (A, M)=0\|\| Trunc_n - 1(POLYVAL (k1, Encode (A, M))
Cipher Text = CTR [AES] _K2 (Trunc_n - 1(T), M)

Theorem 2 (The security of AES_GCM_SIV) [13, 25]

The AES_GCM_SIV mode of operation is a nonce misuse resistant authenticated encryption scheme. Considering for all Q, R, q_D, L, K $\in ℕ$ with k < 32 and $Q < \frac{3}{24} . 2^{128}$ , and every (Q, R, q_D, L, K)-bounded adversary A attacking AES_GCM_SIV, there exists an adversary A” for distinguishing AES from a random permutation and making 6Q AES queries, along with an adversary A‘ for distinguishing AES from a random function as shown in Equation (9) ${Adv}_{\prod}^{MRAE} (A) \leq {Adv}_{AES}^{prp} (A^{II}) + min (\frac{36 Q^{2}}{2^{129}}, \frac{6 Q}{2^{96}}, 1) + Q [2 {Adv}_{E}^{prf} (A^{I}) + \frac{R^{2}}{2^{126 - k}} + \frac{R^{2} + 2 q_{D}}{2^{127}}]$ (9)

Where t(A^I)≤Q.6.t(A) and q_f (A^I) ≤ Q . (2R + 2q_D + L/128)

5 Implementation

In the implementation phase we have verified the security bounds of AES_GCM, GCM_SIV and AES_GCM_SIV authentication encryption algorithms while using different nonces and maximum nonce repletion. This phase also verifies the NIST security bound on all the above authentication encryption algorithms.

5.1 Verification and proving security bounds

The security bounds of GCM-SIV (Two key methods) analysis is based on number of encryptions made by an adversary within the NIST time bound of 2^-32. The Equation (8) of GCM-SIV describes the adversary against GCM-SIV who performs the encryption/ decryption queries and takes twice the advantage of any adversary performing block cipher (AES) outputs with differentiated random function and the number of encryption queries as N_E²/2^{n - k - 2}. In GCM-SIV the standard message length is 2³²-1 blocks, so the value of encryption queries N_E is defined N_E²/2⁹⁴. Based on the above encryption queries, the security bound is fixed to 2⁴⁷. After encrypting 2⁴⁷ messages there is a collision in the 95th-bit of pseudo random value T used in CTR block encryption. So the result of CTR encryption in GCM-SIV provides the same stream of messages. Based on the security problems of GCM-SIV encryption of messages, the number of encryptions can be minimized the NIST standard of IV collision that does not exceed 2^-32 can be followed. So the number of message encryptions is restricted to 2³¹ that is formulated from (2³¹)²/2⁹⁴ = 2^-32. Suppose if the encryption limit is increased, then the secret key for achieving the better security in GCM-SIV must be changed. But the standard of large servers encrypting short messages at very high frequency using GCM-SIV method are not suitable for achieving the security.

Hence, a new standard of nonce reuse misuse resistance scheme AES-GCM-SIV which combines the existing GCM-SIV components has been adopted in this paper. This differs in the function of key derivation and full randomness of counter block (127-bit) used in counter encryption. In addition to the above modifications in AES-GCM-SIV, universal hash function for generation of the tag is performed. The AES-GCM-SIV using POLYVAL hash function that is similar to GHASH used in GCM-SIV avoids byte swapping in POLYVAL and increase better performance. In AES-GCM-SIV the security bounds are constructed by key derivation and counter mode encryption.

The key derivation functions provides the better security bounds against the adversary and truncating the output blocks of a pseudorandom permutation which is used in AES block cipher that derive keys from nonce and master key. The key derivation function produces the output of 64 bits key with the input of each 128-bit. So the key derivation of 128-bit key needs 2 AES operations and 256-bit key needs 4 AES operations. So the advantage of key derivation is to reduce the distinguishing probabilities of a block cipher from a pseudo random function or pseudo random permutation.

The following Equation (10) gives distinguishable truncation of the keys from randomly chosen permutation from a random function

$Ad v_{n, m} \tilde{(q)} \leq min (\frac{\tilde{q}}{2^{n + 1}}, \frac{\tilde{q}}{2^{\frac{m + n}{2}}}, 1)$ (10) where $\tilde{q} \leq \frac{3}{4} . 2^{n}$ is the number of queries.

The derived key advantage of adversary A makes $Q \leq \frac{3}{24} . 2^{128}$ and getting (K1, K2) pairs of keys with length 128 bits and 256 bits in AES-GCM-SIV is specified in Equation (11)

$\begin{matrix} {AdvKDF}_{DeriveKey}^{prf} (A) \leq {Adv}_{AES}^{prp} (t, 6 Q) + min \\ (\frac{36 Q^{2}}{2^{129}}, \frac{6 Q}{2^{96}}, 1) [n = 128, m = 64] \end{matrix}$ (11)

Based on the derived key advantage 2⁶⁴ different key pairs can be derived without affecting birthday bound Q ap; 2⁶⁴ for distinguishing AES from pseudorandom function, because the distinguishing advantage is only $\frac{6}{2^{32}}$ in improved key derivation function.

The AES-GCM-SIV is a nonce-reuse misuse resistance authentication encryption and the adversary A against the NRMR-AE security of AES-GCM-SIV is described as in Equation (12), ${Adv}_{\prod}^{NRMR - AE} (A) \leq {Adv}_{AES}^{prp} (A^{| |}) + min (\frac{36 Q^{2}}{2^{129}}, \frac{6 Q}{2^{96}}, 1) + Q [2 {Adv}_{E}^{prf} (A^{|}) + \frac{R^{2}}{2^{126 - k}} + \frac{R^{2} + 2 q_{D}}{2^{127}}]$ (12)

Based on the above Equation (12), the existing adversary A^||| against PRF of block cipher AES perform Q(2R + 2q_D + L/128) and existing adversary A^|| against PRP of 6Q oracle queries. On verifying the security bounds, the AES-GCM-SIV contains both PRP and PRF functions. But performing PRF on block cipher is not good computation for providing better security in nonce-misuse resistance authentication schemes. In the above equation the key derivation is used to derive keys for each nonce using a uniformly random function Π^| in AES-GCM-SIV. So the difference between ${Adv}_{\prod}^{MRAE}$ and ${Adv}_{\prod^{|}}^{MRAE}$ can be converted to a distinguishing advantage of key derivation method from a random function as in Equation (13). ${Adv}_{\prod}^{MRAE} (A) < {Adv}_{AES}^{prp} (A^{II}) + min (\frac{36 Q^{2}}{2^{129}}, \frac{6 Q}{2^{96}}, 1) + {Adv}_{\prod^{I}}^{MRAE} (A)$ (13)

Based on the above equation Q different nonces and Q different key derivation is used by the adversary. So Q Different keys for different queries is used and the security bound in GCM-SIV⁺ is achieved as in Equation (14) ${Adv}_{\prod}^{MRAE} (A) < 2 . {Adv}_{AES}^{prf} (A^{I}) + \frac{R^{2}}{2^{126 - k}} + \frac{R^{2} + q_{D} (A)}{2^{127}}$ (14)

Here Q act as a hybrid argument of multiuser setting in GCM-SIV⁺ security bound and Equation (15) shows the security bound of GCM-SIV⁺, $\begin{matrix} {Adv}_{\prod}^{MRAE} (A) < Q (2 . {Adv}_{AES}^{prf}) (A^{I}) \\ + \frac{R^{2}}{2^{12 - k}} + \frac{R^{2} + q_{D} (A)}{2^{127}} \end{matrix}$ (15)

Based on the hybrid argument of multiuser setting, the encryption and decryption queries used in derived keys from different nonce are different. Hence the decryption queries are different, the hybrid argument of Q is changed to Q + q_D because the value of Q = 0 when there is no encryption. Thus the adversary simply forge future cipher texts and it also affects the key derivation of the term min 36Q²/2¹²⁹, 6Q/2⁹⁶ in GCM-SIV+.

Based on the notable problems the security bound of AES-GCM-SIV is modified and provides a better security bound against adversary A using nonce-misuse resistance authentication method. So the newly constructed security bound of AES-GCM-SIV is as in Equation (16), ${Adv}_{\prod}^{NRMR - AE} (A) \leq {Adv}_{AES}^{prp} (A^{II}) + min (\frac{36 Q^{2}}{2^{129}}, \frac{6 Q}{2^{96}}) + Q [2 {Adv}_{E}^{prf} (A^{I}) + \frac{R^{2}}{2^{126 - k}} + \frac{R^{2} l_{a}}{2^{128}}]$ (16)

Though the block cipher works better in PRP the second integral part of the above equation specifies the block cipher AES in PRF rather in PRP. So the PRF advantage of security bound in above equation should be replaced by PRP-advantage using PRP-PRF switching lemma [2] is made as in Equation (17),

${QAdv}_{AES}^{prf} (A^{I}) \leq {QAdv}_{AES}^{prp} (A^{I}) + \frac{Q R^{2}}{2^{129 - 2 k}}$ (17)

Based on PRP-PRF switching lemma the final security bound of AES-GCM-SIV is given in Equation (18),

$\begin{matrix} {Adv}_{\prod}^{NRMR - AE} (AE) \leq {Adv}_{AES}^{prp} (A^{II}) + min (\frac{36 Q^{2}}{2^{129}}, \frac{6 Q}{2^{96}}) \\ + [{Qadv}_{E}^{prp} (A^{I}) + \frac{Q R^{2}}{2^{129 - 2 k}} + \frac{Q R^{2}}{2^{126 - k}}] \end{matrix}$ (18)

So the finalizing equation of nonce reuse/misuse resistance authentication encryption achieved in AES-GCM-SIV is specified in Equation (19),

${Adv}_{AES - GCM - SIV}^{NRMR - AE} \leq \frac{6 Q}{2^{96}} + \frac{Q R^{2}}{2^{129 - 2 k}} + \frac{Q R^{2}}{2^{126 - k}}$ (19)

Based on the nonce-misuse resistance properly achieved in AES_GCM_SIV, it can use more than 2³² random nonces compared to AES_GCM and GCM_SIV authentication encryption schemes. So the new scheme AES_GCM_SIV encrypts maximum number of messages with suitable nonce repetition bounds will be useful for modern TLS cipher suites and QUIC based web servers.

6 Results of security bounds comparison

The comparison of security bounds in varied AES-GCM-SIV evolved is based on the number of messages encrypted per nonce (Q), nonce repetition (R) and message length 2^m. Based on the Equations (19) and (12), the security bounds of AES-GCM-SIV are verified against the maximum number of message encryptions and maximum number of nonce repetition within the NIST bound 2^-32. The comparison of security bounds is detailed and justified in Table 3.

Table 3
Security bounds comparison

Table 3 analyses the maximum message encryptions with considering the values of Q, R, and K and satisfying the bound 2^-32. For considering the better security bounds the values beyond 2^-32 (red colored) will results in active adversary attacks. So the above table gives better security bounds, considering the values of number of different nonces(Q), maximum nonce repetition (R) and message length for encrypting bulk data (K). This table also gives the detailed analysis of number of nonces and nonce repetition that can be used to achieve the maximum message length blocks of a message.

The message length also depends on the nonces and nonce repetition where the message length decreases when number on nonces and nonce repetition are higher.So the number of nonces and nonce repetition can be restricted when achieving the better message length in TLS cipher suites and QUIC.

Based on the above analysis the number of encrypted messages with maximum nonce repetition using AES-GCM-SIV scheme is higher when compared to existing AES-GCM and GCM_SIV that results in achieving better security and performance. So the newly constructed AEAD scheme which is best suitable for modern TLS cipher suites and QUIC for encrypting more messages with maximum message length without changing the secret key. According to the birthday bound security analysis the new AES-GCM-SIV achieves the 2⁶⁴ derivations that maximize the security bounds to a greater extent.

Figures 3 and 4 shows that as expected in the message transmission rate, the number of bytes is increasing for the various schemes when using nonce repetition of 2¹⁵. Then the AES_GCM_SIV proves better message transmission rate and secure the NIST bound 2^-33 and 2^-31.

Fig. 3

Nonce Repetition bounds.

The proposed scheme AES_GCM_SIV depicted in Figs. 3 and 4 shows maximum achieved message transmission rate in TLC and QUIC on varied message length(say 2⁸³ and 2⁶⁷) respectively.

In Fig. 5 display the results of maximum message length in blocks. The new AES_GCM_SIV scheme applies various nonce repetition(R) 2¹⁰, 2⁶ and 2³ with different number of nonces(Q). The comparison also achieves the better NIST security bounds against adversary is 2^-32.

Fig. 4

Nonce Repetition Bounds.

Fig. 5

Message Length Performance.

Figures 6 and 7 shows that the results of encryption upon different message length. The scheme AES_GCM_SIV results that on applying different Q and R values with constant message length 2¹⁰ and 2¹⁶.

Fig. 6

Message encryption.

Fig. 7

Message Encryption.

Figure 8 explains the performance in varying the message lengths along the x axis and nonce repetition along y axis. The figure insights that if the message length is increased there is a gradual drop in number of messages during maximum nonce repetition. Owing to the drop in message count, the proposed work defends the security of 2^-32 which proves to be a better security.

Fig. 8

Message Length Performance.

Figures 9 and 10 describes the performance of encryption and decryption. The performance was measured with constant message length 2¹⁰ and 2¹⁶ and varying different Q and R which satisfies the NIST security bound greater than 2^-32. The performance was justified in computing with the capacity of Intel ^® Core TM i7-7660 4 GHz and 8GB RAM.

Fig. 9

Encryption and Decryption Performance.

Fig. 10

Encryption and Decryption Performance.

7 Conclusion

This paper makes proper investigation on nonce misuse problem in TLS cipher suites and QUIC based web servers when performing number of maximum number of message encryption and nonce repetition. The nonce misuse problem is avoided by adopting nonce reuse/misuse resistance authentication schemes like GCM_SIV and AES_GCM_SIV. Based on the better security bounds derived in this paper, the AES_GCM_SIV is concluded to be the best scheme for achieving better security bounds performing large messages in TLS cipher suites and QUIC based web servers which also meets the NIST security bound 2^-32. So the modern TLS cipher suites and QUIC using AES_GCM_SIV scheme will achieve better bounds even on repeating nonces in their message communication. But some schemes like AES_GCM and CHACHA20-POLY1305 also provides better bounds using unique nonce for different message encryption. The NRMR-AE scheme also increases the message encryption up to 2⁵⁰ when minimizing the number of nonces used and nonce repetition in AES_GCM_SIV.

References

Mennink

Bart

and Neves

Samuel

, Optimal PRFs from Blockcipher Designs. IACR Transactions on Symmetric Cryptology, ISSN 2519-173X 2017(3), 228–252.

Bellare

and Impagliazzo

, A tool for obtaining tighter security analyses of pseudorandom function based constructions, with applications to PRP to PRF conversion. Cryptology ePrint Archive, Report 1999/024, 1999. http://eprint.iacr.org/1999/024.

Chanathip Namprempre, Phillip Rogaway, and Thomas Shrimpton. Reconsidering Generic Composition. In Phong Q. Nguyen and Elisabeth Oswald, editors, Advances in Cryptology – EUROCRYPT 2014, volume 8441 of LNCS, pages 257–274. Springer, 2014.

Dworkin

, Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC, Nov. 2007. http://csrc.nist.gov/publications/nistpubs/800-38D/SP-800-38D.pdf

Gueron

and Lindell

, GCM-SIV: Full nonce misuse-resistantauthenticated encryption at under one cycle per byte. https://eprint.iacr.org/2015/102.pdf.

Gueron

, Langley

and Lindell.

, AES-GCM-SIV: Special citation and Analysis, Cryptology ePrint Archive, Report 2 017/168, 2017. http://eprint.iacr.org/2017/168.

Gilboa

and Gueron

, Distinguishing a truncated random permutation from a random function. Cryptology ePrint Archive, Report 2015/773, 2015. http://eprint.iacr.org/2015/773.

Gueron

, Langley

and Lindell

, AES-GCM-SIV: Specification and analysis. Cryptology ePrint Archive, Report 2017/168, 2017. http://eprint.iacr.org/2017/168.

Böck

Hanno

, Zauner

Aaron

, Devlin

Sean

, Somorovsky

Juraj

and Jovanovic

Philipp

, Nonce-Disrespecting Adversaries: PracticalForgery Attacks on GCM in TLS, https://eprint.iacr.org/2016/475.pdf.

10.

Harkins

, Synthetic Initialization Vector (SIV) Authenticated En-cryption Using the Advanced Encryption Standard (AES). RFC 5297(Informational), Oct. 2008. https://tools.ietf.org/html/rfc5297.

11.

Iwata

and Seurin

, Reconsidering the security bound of AES-GCM-SIV.IACR Trans, Symm. Cryptol2017(4) (2017), 240–267.

12.

Iwata

, New blockcipher modes of operation with beyond the birthday bound security. In M. J. B. Robshaw, editor, FSE 2006, volume 4047 of LNCS, pages 310–327. Springer, Heidelberg, Mar. 2006.

13.

Joux.:Authentication Failures in NIST version of GCM. 2006. http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/comments/800-38Series-Drafts/GCM/Jouxcomments.pdf.

14.

Salowey

Joseph

, Choudhury

Abhijit

and McGrew

David A.

, AES Galois Counter Mode (GCM) Cipher Suites for TLS. IETF RFC 5288, 2008.

15.

McGrew

D.A.

and Viega

, The Security and Performance of the Galois/Counter Mode (GCM) of Operation. In INDOCRYPT 2004, Springer (LNCS 3348), pages 343–355, 2004.

16.

McGrew

and Bailey

, “AES-CCM Cipher Suites for Transport Layer Security (TLS)”, RFC 6655, DOI 10.17487/RFC6655, July 2012. https://www.rfc-editor.org/info/rfc6655.

17.

Rogaway

and Shrimpton

, The SIV Mode of Operation for Deterministic Authenticated-Encryption (Key Wrap) and MisuseResistant Nonce-Based Authenticated-Encryption. Availablefrom http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/siv/siv.pdf (2007).

18.

Gilboa

Shoni

, Gueron

Shay

and Morris

Ben

, How many queries are needed to distinguish atruncated random permutation from a random function?Journal of Cryptology31(1) (2018), 162–171.

19.

Krovetz

Ted

, Philip Rogaway. The Software Performance of Authenticated-Encryption Modes. Pages 306–327, Springer-Verlag, 2011.

20.

Iwata

Tetsu

and Minematsu

Kazuhiko

, Stronger Security Variants of GCM-SIV. IACR Trans, Symmetric Cryptol2016(1) (2016), 134–157.

21.

Ashur

Tomer

, Dunkelman

Orr

and Luykx

Atul

, Boosting Authenticated Encryption Robustness With Minimal Modifications,Annual International Cryptology Conference, Advances in Cryptology – CRYPTO 2017 pp. 3–33.

22.

QUIC, a multiplexed stream transport over UDP. https://www.chromium.org/quic.

23.

Roskind

Jim

, Quick UDP internet connections: Multiplexed stream transport over UDP, 2012. https://docs.google.com/document/d/1RNHkx_VvKWyWg6Lr8SZ-saqsQx7rFVev2jRFUoVD34/edit.

24.

Roskind

Jim

, Experimenting with QUIC. The Chromium Blog, 2013. http://blog.chromium.org/2013/06/experimenting-with-quic.html.

25.

Gilboa

and Gueron

, The Advantage of Truncated Permutations. Manuscript, 2016. https://arxiv.org/abs/1610.02518.

26.

Iwata

, Ohashi

and Minematsu

, Breaking and repairing GCM security proofs. In R. Safavi- Naini and R. Canetti, editors, CRYPTO 2012, volume 7417 of LNCS, pages 31–49. Springer, Heidelberg, Aug. 2012.

Nonce reuse/misuse resistance authentication encryption schemes for modern TLS cipher suites and QUIC based web servers

Abstract

1 Introduction

2 Literature survey

3 Preliminaries

3.1 General notations

3.2 Nonce-based authentication encryption

4.1 Synthetic IV (SIV)

5.1 Verification and proving security bounds

Table 3 Security bounds comparison

References

Table 3
Security bounds comparison