November  2019, 13(4): 705-732. doi: 10.3934/amc.2019042

$\textsf{DWCDM+}$: A BBB secure nonce based MAC

1. 

Indian Statistical Institute, Kolkata, India

2. 

NTT Secure Platform Laboratories, NTT Corporation, Japan

* Corresponding author

Received  November 2018 Revised  January 2019 Published  June 2019

Fund Project: This is an extended version of the article accepted in IACR-CRYPTO 2018. Section 3, section 4 and section 5 contains the substantial changes from our article accepted in IACR-CRYPTO 2018. Mridul Nandi is supported by R.C.Bose Centre for Cryptology and Security

In CRYPTO 2016, Cogliati and Seurin have proposed a nonce-based MAC called Encrypted Wegman-Carter with Davies-Meyer (
$\textsf{EWCDM}$
), from an
$n$
-bit block cipher
$\textsf{E}$
and an
$n$
-bit almost xor universal hash function
$\textsf{H}$
as
$\textsf{E}_{K_2}\bigl(\textsf{E}_{K_1}(N)\oplus N\oplus \textsf{H}_{K_h}(M)\bigr),$
for a nonce
$N$
and a message
$M$
that provides roughly
$2n/3$
-bit MAC security. However, obtaining the similar security using a single block cipher key was posed as an open research problem. In this paper, we present Decrypted Wegman-Carter with Davies-Meyer (
$\textsf{DWCDM+}$
) construction based on a single block cipher key that provides
$2n/3$
-bit MAC security from an
$n$
-bit block cipher
$\textsf{E}$
and an
$n$
-bit
$k$
-regular (
$\forall k \leq n$
), almost xor universal hash function
$\textsf{H}$
as
$ \textsf{E}^{-1}_{K}\bigl(\textsf{E}_{K}(N)\oplus N \oplus \textsf{H}_{K_h}(M)\bigr). $
$\textsf{DWCDM+}$
is structurally very similar to its predecessor
$\textsf{EWCDM}$
except that the facts that (i) the number of block cipher keys reduced from
$2$
to
$1$
and (ⅱ) the outer encryption call is replaced by a decryption one. To make the construction truely single-keyed, here we derive the hash key
$K_h$
as the block cipher output of a fixed string
$0^{n-2} \| 10$
as long as the hash key is of
$n$
bits. We show that if the nonce space is restricted to
$(n-1)$
bits,
$\textsf{DWCDM+}$
is secured roughly up to
$2^{2n/3}$
MAC queries (
$2^{n/2}$
MAC queries) and
$2^n$
verification queries against nonce respecting (nonce misuse resp.) adversaries.
Citation: Nilanjan Datta, Avijit Dutta, Mridul Nandi, Kan Yasuda. $\textsf{DWCDM+}$: A BBB secure nonce based MAC. Advances in Mathematics of Communications, 2019, 13 (4) : 705-732. doi: 10.3934/amc.2019042
References:
[1]

M. Bellare and R. Impagliazzo, A tool for obtaining tighter security analyses of pseudorandom function based constructions, with applications to PRP to PRF conversion, preprint, ePrint: 1999/024.ps.Google Scholar

[2]

M. Bellare, O. Goldreich and A. Mityagin, The power of verification queries in message authentication and authenticated encryption, preprint, ePrint: 2004/309.ps.Google Scholar

[3]

S. Chen and J. Steinberger, Tight Security Bounds for Key-Alternating Ciphers, in Advances in Cryptology - EUROCRYPT 2014, Academic Press, 8441 (2014), 327–350.Google Scholar

[4]

S. Chen, R. Lampe, J, Lee, Ya. Seurin and J. Steinberger, Minimizing the two-round even-Mansour cipher, in Advances in Cryptology - CRYPTO 2014, Academic Press, 8616 (2014), 39–56. doi: 10.1007/978-3-662-44371-2_3. Google Scholar

[5]

B. Cogliati and Y. Seurin, Analysis of the single-permutation encrypted Davies-Meyer construction, Des. Codes Cryptography, 86 (2018), 2703-2723. doi: 10.1007/s10623-018-0470-9. Google Scholar

[6]

B. Cogliati and Y. Seurin, EWCDM: An efficient, beyond-birthday secure, nonce-misuse resistant MAC, in Advances in Cryptology - CRYPTO 2016, Academic Press, 9814 (2016), 121–149. doi: 10.1007/978-3-662-53018-4_5. Google Scholar

[7]

W. Dai, V. T. Hoang and S. Tessaro, Information-theoretic indistinguishability via the chi-squared method, in Advances in Cryptology - CRYPTO 2017, Academic Press, 10403 (2017), 497–523. Google Scholar

[8]

N. Datta, A. Dutta, M. Nandi and K. Yasuda, Encrypt or decrypt? To make a single-key beyond birthday secure nonce-based MAC, in Advances in Cryptology - CRYPTO 2018, Academic Press, 10991 (2018), 631–661. Google Scholar

[9]

N. Datta, A. Dutta, M. Nandi, G. Paul and L. Zhang, Single key variant of PMAC_plus, IACR Trans. Symmetric Cryptol., 2017 (2017), 268–305.Google Scholar

[10]

N. Datta, A. Dutta, M. Nandi and G. Paul, Double-block hash-then-sum: A paradigm for constructing BBB secure PRF, IACR Trans. Symmetric Cryptol., 2018 (2018), 36–92.Google Scholar

[11]

A. Dutta, A. Jha and M. Nandi, Tight security analysis of ehtm MAC, IACR Trans. Symmetric Cryptol., 2017 (2017), 130–150.Google Scholar

[12]

B. Gilles, On computationally secure authentication tags requiring short secret shared keys, in Advances in Cryptology - CRYPTO '82, Academic Press, (1983), 79–86. doi: 10.1007/978-1-4757-0602-4_7. Google Scholar

[13]

O. Goldreich, S. Goldwasser and S. Micali, On the cryptographic applications of random functions, in Advances in Cryptology - CRYPTO '84, Academic Press, 196 (1984), 276–288. doi: 10.1007/3-540-39568-7_22. Google Scholar

[14]

P. Jacques, The "Coefficients H" technique, in Selected Areas in Cry. ptography, Academic Press, 5381 (2008), 328–345. doi: 10.1007/978-3-642-04159-4_21. Google Scholar

[15]

P. Jacques, Introduction to mirror theory: Analysis of systems of linear equalities and linear non equalities for cryptography, preprint, https://eprint.iacr.org/2010/287.pdf.Google Scholar

[16]

P. Jacques, Mirror theory and cryptography, Appl. Algebra Engrg. Commun. Comput., 28 (2017), 321-338. doi: 10.1007/s00200-017-0326-y. Google Scholar

[17]

S. Lucks, The sum of PRPs is a secure PRF, in Advances in Cryptology - EUROCRYPT 2000(Bruges), Academic Press, 1807 (2000), 470–484. doi: 10.1007/3-540-45539-6_34. Google Scholar

[18]

B. Mennink and S. Neves, Encrypted davies-meyer and its dual: Towards optimal security using mirror theory, in Advances in cryptology - CRYPTO 2017, Academic Press, 10403 (2017), 556–583. Google Scholar

[19]

B. Mihir, K. Ted and R. Phillip, Luby-Rackoff backwards: Increasing security by making block ciphers non-invertible, in Advances in Cryptology - EUROCRYPT '98, Academic Press, 1403 (1998), 266–280. doi: 10.1007/BFb0054132. Google Scholar

[20]

K. Minematsu and T. Iwata, Building blockcipher from tweakable blockcipher: Extending FSE 2009 proposal, in Cryptography and Coding, Academic Press, 7089 (2011), 391–412. doi: 10.1007/978-3-642-25516-8_24. Google Scholar

[21]

Y. Naito, Blockcipher-based MACs: Beyond the birthday bound without message length, in ASIACRYPT 2017, Academic Press, 10626 (2017), 446–470. Google Scholar

[22]

J. Patarin, A proof of security in O(2n) for the Benes scheme, in Progress in Cryptology - AFRICACRYPY 2008, Academic Press, 5023 (2008), 209–220. doi: 10.1007/978-3-540-68164-9_14. Google Scholar

[23]

J. Patarin, Security in O(2n) for the xor of two random permutations - proof with the standard H technique, preprint, https://eprint.iacr.org/2013/368.pdf.Google Scholar

[24]

B. Srimanta and N. Mridul, Revisiting variable output length xor pseudorandom function, IACR Trans. Symmetric Cryptol., 2018 (2018), 314–335.Google Scholar

[25]

I. Tetsu, M. Bart and V. Damian, CENC is Optimally Secure, preprint, https://eprint.iacr.org/2016/1087.pdf.Google Scholar

[26]

I. Tetsu, New blockcipher modes of operation with beyond the birthday bound security, in Fast Software Encryption, Academic Press, 4047 (2006), 310–327. doi: 10.1007/11799313_20. Google Scholar

[27]

S. Victor, On fast and provably secure message authentication based on universal hashing, in Advances in Cryptology - CRYPTO '96, Academic Press, 1109 (1996), 313–328. doi: 10.1007/3-540-68697-5_24. Google Scholar

[28]

K. Yasuda, A new variant of PMAC: Beyond the birthday bound, in Advances in Cryptology - CRYPTO 2011, Academic Press, 6841 (2011), 596–609. doi: 10.1007/978-3-642-22792-9_34. Google Scholar

[29]

L. Zhang, W. L. Wu, H. Sui and P. Wang, 3kf9: Enhancing 3GPP-MAC beyond the birthday bound, in Advances in Cryptology - ASIACRYPT 2012, Academic Press, 7658 (2012), 296–312. doi: 10.1007/978-3-642-34961-4_19. Google Scholar

show all references

References:
[1]

M. Bellare and R. Impagliazzo, A tool for obtaining tighter security analyses of pseudorandom function based constructions, with applications to PRP to PRF conversion, preprint, ePrint: 1999/024.ps.Google Scholar

[2]

M. Bellare, O. Goldreich and A. Mityagin, The power of verification queries in message authentication and authenticated encryption, preprint, ePrint: 2004/309.ps.Google Scholar

[3]

S. Chen and J. Steinberger, Tight Security Bounds for Key-Alternating Ciphers, in Advances in Cryptology - EUROCRYPT 2014, Academic Press, 8441 (2014), 327–350.Google Scholar

[4]

S. Chen, R. Lampe, J, Lee, Ya. Seurin and J. Steinberger, Minimizing the two-round even-Mansour cipher, in Advances in Cryptology - CRYPTO 2014, Academic Press, 8616 (2014), 39–56. doi: 10.1007/978-3-662-44371-2_3. Google Scholar

[5]

B. Cogliati and Y. Seurin, Analysis of the single-permutation encrypted Davies-Meyer construction, Des. Codes Cryptography, 86 (2018), 2703-2723. doi: 10.1007/s10623-018-0470-9. Google Scholar

[6]

B. Cogliati and Y. Seurin, EWCDM: An efficient, beyond-birthday secure, nonce-misuse resistant MAC, in Advances in Cryptology - CRYPTO 2016, Academic Press, 9814 (2016), 121–149. doi: 10.1007/978-3-662-53018-4_5. Google Scholar

[7]

W. Dai, V. T. Hoang and S. Tessaro, Information-theoretic indistinguishability via the chi-squared method, in Advances in Cryptology - CRYPTO 2017, Academic Press, 10403 (2017), 497–523. Google Scholar

[8]

N. Datta, A. Dutta, M. Nandi and K. Yasuda, Encrypt or decrypt? To make a single-key beyond birthday secure nonce-based MAC, in Advances in Cryptology - CRYPTO 2018, Academic Press, 10991 (2018), 631–661. Google Scholar

[9]

N. Datta, A. Dutta, M. Nandi, G. Paul and L. Zhang, Single key variant of PMAC_plus, IACR Trans. Symmetric Cryptol., 2017 (2017), 268–305.Google Scholar

[10]

N. Datta, A. Dutta, M. Nandi and G. Paul, Double-block hash-then-sum: A paradigm for constructing BBB secure PRF, IACR Trans. Symmetric Cryptol., 2018 (2018), 36–92.Google Scholar

[11]

A. Dutta, A. Jha and M. Nandi, Tight security analysis of ehtm MAC, IACR Trans. Symmetric Cryptol., 2017 (2017), 130–150.Google Scholar

[12]

B. Gilles, On computationally secure authentication tags requiring short secret shared keys, in Advances in Cryptology - CRYPTO '82, Academic Press, (1983), 79–86. doi: 10.1007/978-1-4757-0602-4_7. Google Scholar

[13]

O. Goldreich, S. Goldwasser and S. Micali, On the cryptographic applications of random functions, in Advances in Cryptology - CRYPTO '84, Academic Press, 196 (1984), 276–288. doi: 10.1007/3-540-39568-7_22. Google Scholar

[14]

P. Jacques, The "Coefficients H" technique, in Selected Areas in Cry. ptography, Academic Press, 5381 (2008), 328–345. doi: 10.1007/978-3-642-04159-4_21. Google Scholar

[15]

P. Jacques, Introduction to mirror theory: Analysis of systems of linear equalities and linear non equalities for cryptography, preprint, https://eprint.iacr.org/2010/287.pdf.Google Scholar

[16]

P. Jacques, Mirror theory and cryptography, Appl. Algebra Engrg. Commun. Comput., 28 (2017), 321-338. doi: 10.1007/s00200-017-0326-y. Google Scholar

[17]

S. Lucks, The sum of PRPs is a secure PRF, in Advances in Cryptology - EUROCRYPT 2000(Bruges), Academic Press, 1807 (2000), 470–484. doi: 10.1007/3-540-45539-6_34. Google Scholar

[18]

B. Mennink and S. Neves, Encrypted davies-meyer and its dual: Towards optimal security using mirror theory, in Advances in cryptology - CRYPTO 2017, Academic Press, 10403 (2017), 556–583. Google Scholar

[19]

B. Mihir, K. Ted and R. Phillip, Luby-Rackoff backwards: Increasing security by making block ciphers non-invertible, in Advances in Cryptology - EUROCRYPT '98, Academic Press, 1403 (1998), 266–280. doi: 10.1007/BFb0054132. Google Scholar

[20]

K. Minematsu and T. Iwata, Building blockcipher from tweakable blockcipher: Extending FSE 2009 proposal, in Cryptography and Coding, Academic Press, 7089 (2011), 391–412. doi: 10.1007/978-3-642-25516-8_24. Google Scholar

[21]

Y. Naito, Blockcipher-based MACs: Beyond the birthday bound without message length, in ASIACRYPT 2017, Academic Press, 10626 (2017), 446–470. Google Scholar

[22]

J. Patarin, A proof of security in O(2n) for the Benes scheme, in Progress in Cryptology - AFRICACRYPY 2008, Academic Press, 5023 (2008), 209–220. doi: 10.1007/978-3-540-68164-9_14. Google Scholar

[23]

J. Patarin, Security in O(2n) for the xor of two random permutations - proof with the standard H technique, preprint, https://eprint.iacr.org/2013/368.pdf.Google Scholar

[24]

B. Srimanta and N. Mridul, Revisiting variable output length xor pseudorandom function, IACR Trans. Symmetric Cryptol., 2018 (2018), 314–335.Google Scholar

[25]

I. Tetsu, M. Bart and V. Damian, CENC is Optimally Secure, preprint, https://eprint.iacr.org/2016/1087.pdf.Google Scholar

[26]

I. Tetsu, New blockcipher modes of operation with beyond the birthday bound security, in Fast Software Encryption, Academic Press, 4047 (2006), 310–327. doi: 10.1007/11799313_20. Google Scholar

[27]

S. Victor, On fast and provably secure message authentication based on universal hashing, in Advances in Cryptology - CRYPTO '96, Academic Press, 1109 (1996), 313–328. doi: 10.1007/3-540-68697-5_24. Google Scholar

[28]

K. Yasuda, A new variant of PMAC: Beyond the birthday bound, in Advances in Cryptology - CRYPTO 2011, Academic Press, 6841 (2011), 596–609. doi: 10.1007/978-3-642-22792-9_34. Google Scholar

[29]

L. Zhang, W. L. Wu, H. Sui and P. Wang, 3kf9: Enhancing 3GPP-MAC beyond the birthday bound, in Advances in Cryptology - ASIACRYPT 2012, Academic Press, 7658 (2012), 296–312. doi: 10.1007/978-3-642-34961-4_19. Google Scholar

Figure 4.1.  $\textsf{DWCDM+}$ construction with an n-bit block cipher EK and n-bit keyed hash function HL where L = EK(0n−2║10).
Figure 4.2.  Birthday bound MAC attack against $\textsf{DWCDM+}$ if full nonce space is used.
[1]

Harbir Antil, Mahamadi Warma. Optimal control of the coefficient for the regional fractional $p$-Laplace equation: Approximation and convergence. Mathematical Control & Related Fields, 2019, 9 (1) : 1-38. doi: 10.3934/mcrf.2019001

[2]

Florin Diacu, Shuqiang Zhu. Almost all 3-body relative equilibria on $ \mathbb S^2 $ and $ \mathbb H^2 $ are inclined. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 1-13. doi: 10.3934/dcdss.2020067

[3]

Ildoo Kim. An $L_p$-Lipschitz theory for parabolic equations with time measurable pseudo-differential operators. Communications on Pure & Applied Analysis, 2018, 17 (6) : 2751-2771. doi: 10.3934/cpaa.2018130

[4]

Sugata Gangopadhyay, Goutam Paul, Nishant Sinha, Pantelimon Stǎnicǎ. Generalized nonlinearity of $ S$-boxes. Advances in Mathematics of Communications, 2018, 12 (1) : 115-122. doi: 10.3934/amc.2018007

[5]

Gyula Csató. On the isoperimetric problem with perimeter density $r^p$. Communications on Pure & Applied Analysis, 2018, 17 (6) : 2729-2749. doi: 10.3934/cpaa.2018129

[6]

Haisheng Tan, Liuyan Liu, Hongyu Liang. Total $\{k\}$-domination in special graphs. Mathematical Foundations of Computing, 2018, 1 (3) : 255-263. doi: 10.3934/mfc.2018011

[7]

Pak Tung Ho. Prescribing the $ Q' $-curvature in three dimension. Discrete & Continuous Dynamical Systems - A, 2019, 39 (4) : 2285-2294. doi: 10.3934/dcds.2019096

[8]

Ekta Mittal, Sunil Joshi. Note on a $ k $-generalised fractional derivative. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 797-804. doi: 10.3934/dcdss.2020045

[9]

Eun-Kyung Cho, Cunsheng Ding, Jong Yoon Hyun. A spectral characterisation of $ t $-designs and its applications. Advances in Mathematics of Communications, 2019, 13 (3) : 477-503. doi: 10.3934/amc.2019030

[10]

Gang Wang, Yuan Zhang. $ Z $-eigenvalue exclusion theorems for tensors. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-12. doi: 10.3934/jimo.2019039

[11]

Caili Sang, Zhen Chen. $ E $-eigenvalue localization sets for tensors. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-19. doi: 10.3934/jimo.2019042

[12]

Annalisa Cesaroni, Serena Dipierro, Matteo Novaga, Enrico Valdinoci. Minimizers of the $ p $-oscillation functional. Discrete & Continuous Dynamical Systems - A, 2019, 0 (0) : 1-15. doi: 10.3934/dcds.2019231

[13]

Zalman Balanov, Yakov Krasnov. On good deformations of $ A_m $-singularities. Discrete & Continuous Dynamical Systems - S, 2019, 12 (7) : 1851-1866. doi: 10.3934/dcdss.2019122

[14]

Lin Du, Yun Zhang. $\mathcal{H}_∞$ filtering for switched nonlinear systems: A state projection method. Journal of Industrial & Management Optimization, 2018, 14 (1) : 19-33. doi: 10.3934/jimo.2017035

[15]

Shengbing Deng. Construction solutions for Neumann problem with Hénon term in $ \mathbb{R}^2 $. Discrete & Continuous Dynamical Systems - A, 2019, 39 (4) : 2233-2253. doi: 10.3934/dcds.2019094

[16]

Teresa Alberico, Costantino Capozzoli, Luigi D'Onofrio, Roberta Schiattarella. $G$-convergence for non-divergence elliptic operators with VMO coefficients in $\mathbb R^3$. Discrete & Continuous Dynamical Systems - S, 2019, 12 (2) : 129-137. doi: 10.3934/dcdss.2019009

[17]

Mohan Mallick, R. Shivaji, Byungjae Son, S. Sundar. Bifurcation and multiplicity results for a class of $n\times n$ $p$-Laplacian system. Communications on Pure & Applied Analysis, 2018, 17 (3) : 1295-1304. doi: 10.3934/cpaa.2018062

[18]

Daniel Heinlein, Michael Kiermaier, Sascha Kurz, Alfred Wassermann. A subspace code of size $ \bf{333} $ in the setting of a binary $ \bf{q} $-analog of the Fano plane. Advances in Mathematics of Communications, 2019, 13 (3) : 457-475. doi: 10.3934/amc.2019029

[19]

Guoyuan Chen, Yong Liu, Juncheng Wei. Nondegeneracy of harmonic maps from $ {{\mathbb{R}}^{2}} $ to $ {{\mathbb{S}}^{2}} $. Discrete & Continuous Dynamical Systems - A, 2019, 0 (0) : 1-19. doi: 10.3934/dcds.2019228

[20]

Joackim Bernier. Bounds on the growth of high discrete Sobolev norms for the cubic discrete nonlinear Schrödinger equations on $ h\mathbb{Z} $. Discrete & Continuous Dynamical Systems - A, 2019, 39 (6) : 3179-3195. doi: 10.3934/dcds.2019131

2018 Impact Factor: 0.879

Article outline

Figures and Tables

[Back to Top]