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]

Jianqin Zhou, Wanquan Liu, Xifeng Wang, Guanglu Zhou. On the $ k $-error linear complexity for $ p^n $-periodic binary sequences via hypercube theory. Mathematical Foundations of Computing, 2019, 2 (4) : 279-297. doi: 10.3934/mfc.2019018

[2]

Pak Tung Ho. Prescribing $ Q $-curvature on $ S^n $ in the presence of symmetry. Communications on Pure & Applied Analysis, 2020, 19 (2) : 715-722. doi: 10.3934/cpaa.2020033

[3]

Dean Crnković, Nina Mostarac, Bernardo G. Rodrigues, Leo Storme. $ s $-PD-sets for codes from projective planes $ \mathrm{PG}(2,2^h) $, $ 5 \leq h\leq 9 $. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020075

[4]

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

[5]

Umberto De Maio, Peter I. Kogut, Gabriella Zecca. On optimal $ L^1 $-control in coefficients for quasi-linear Dirichlet boundary value problems with $ BMO $-anisotropic $ p $-Laplacian. Mathematical Control & Related Fields, 2019, 0 (0) : 0-0. doi: 10.3934/mcrf.2020021

[6]

Jennifer D. Key, Bernardo G. Rodrigues. Binary codes from $ m $-ary $ n $-cubes $ Q^m_n $. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020079

[7]

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

[8]

Melvin Faierman. Fredholm theory for an elliptic differential operator defined on $ \mathbb{R}^n $ and acting on generalized Sobolev spaces. Communications on Pure & Applied Analysis, 2020, 19 (3) : 1463-1483. doi: 10.3934/cpaa.2020074

[9]

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, 2020, 13 (4) : 1131-1143. doi: 10.3934/dcdss.2020067

[10]

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

[11]

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

[12]

Lakehal Belarbi. Ricci solitons of the $ \mathbb{H}^{2} \times \mathbb{R} $ Lie group. Electronic Research Archive, 2020, 28 (1) : 157-163. doi: 10.3934/era.2020010

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

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

[20]

Chaoqian Li, Yajun Liu, Yaotang Li. Note on $ Z $-eigenvalue inclusion theorems for tensors. Journal of Industrial & Management Optimization, 2017, 13 (5) : 0-0. doi: 10.3934/jimo.2019129

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (117)
  • HTML views (328)
  • Cited by (0)

[Back to Top]