Revisiting structure graphs: Applications to CBC-MAC and EMAC
In [2], Bellare, Pietrzak and Rogaway proved an O(ℓq2/2n)${O(\ell q^{2}/2^{n})}$ bound for the PRF (pseudorandom function) security of the CBC-MAC based on an n-bit random permutation Π, provided ℓ<2n/3${\ell<2^{n/3}}$. Here an adversary can make at most q prefix-free queries each having at...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
De Gruyter
2016-12-01
|
| Series: | Journal of Mathematical Cryptology |
| Subjects: | |
| Online Access: | https://doi.org/10.1515/jmc-2016-0030 |
| _version_ | 1797999521434697728 |
|---|---|
| author | Jha Ashwin Nandi Mridul |
| author_facet | Jha Ashwin Nandi Mridul |
| author_sort | Jha Ashwin |
| collection | DOAJ |
| description | In [2], Bellare, Pietrzak and Rogaway proved an O(ℓq2/2n)${O(\ell q^{2}/2^{n})}$ bound for the PRF (pseudorandom function) security of the CBC-MAC based on an n-bit random permutation Π, provided ℓ<2n/3${\ell<2^{n/3}}$. Here an adversary can make at most q prefix-free queries each having at most ℓ${\ell}$ many “blocks” (elements of {0,1}n${\{0,1\}^{n}}$). In the same paper an O(ℓo(1)q2/2n)${O(\ell^{o(1)}q^{2}/2^{n})}$ bound for EMAC (or encrypted CBC-MAC) was proved, provided ℓ<2n/4${\ell<2^{n/4}}$. Both proofs are based on structure graphs representing all collisions among “intermediate inputs” to Π during the computation of CBC. The problem of bounding PRF-advantage is shown to be reduced to bounding the number of structure graphs satisfying certain collision patterns. In the present paper, we show that [2, Lemma 10], stating an important result on structure graphs, is incorrect. This is due to the fact that the authors overlooked certain structure graphs. This invalidates the proofs of the PRF bounds. In [31], Pietrzak improved the bound for EMAC by showing a tight bound O(q2/2n)${O(q^{2}/2^{n})}$ under the restriction that ℓ<2n/8${\ell<2^{n/8}}$. As he used the same flawed lemma, this proof also becomes invalid. In this paper, we have revised and sometimes simplified these proofs. We revisit structure graphs in a slightly different mathematical language and provide a complete characterization of certain types of structure graphs. Using this characterization, we show that PRF security of CBC-MAC is about σq/2n${\sigma q/2^{n}}$ provided ℓ<2n/3${\ell<2^{n/3}}$ where σ is the total number of blocks in all queries. We also recover tight bound for PRF security of EMAC with a much relaxed constraint (ℓ<2n/4${\ell<2^{n/4}}$) than the original (ℓ<2n/8${\ell<2^{n/8}}$). |
| first_indexed | 2024-04-11T11:05:59Z |
| format | Article |
| id | doaj.art-1c4d20fa0a0643ff840ed415441bb2f8 |
| institution | Directory Open Access Journal |
| issn | 1862-2976 1862-2984 |
| language | English |
| last_indexed | 2024-04-11T11:05:59Z |
| publishDate | 2016-12-01 |
| publisher | De Gruyter |
| record_format | Article |
| series | Journal of Mathematical Cryptology |
| spelling | doaj.art-1c4d20fa0a0643ff840ed415441bb2f82022-12-22T04:28:21ZengDe GruyterJournal of Mathematical Cryptology1862-29761862-29842016-12-01103-415718010.1515/jmc-2016-0030Revisiting structure graphs: Applications to CBC-MAC and EMACJha Ashwin0Nandi Mridul1Indian Statistical Institute, Kolkata, IndiaIndian Statistical Institute, Kolkata, IndiaIn [2], Bellare, Pietrzak and Rogaway proved an O(ℓq2/2n)${O(\ell q^{2}/2^{n})}$ bound for the PRF (pseudorandom function) security of the CBC-MAC based on an n-bit random permutation Π, provided ℓ<2n/3${\ell<2^{n/3}}$. Here an adversary can make at most q prefix-free queries each having at most ℓ${\ell}$ many “blocks” (elements of {0,1}n${\{0,1\}^{n}}$). In the same paper an O(ℓo(1)q2/2n)${O(\ell^{o(1)}q^{2}/2^{n})}$ bound for EMAC (or encrypted CBC-MAC) was proved, provided ℓ<2n/4${\ell<2^{n/4}}$. Both proofs are based on structure graphs representing all collisions among “intermediate inputs” to Π during the computation of CBC. The problem of bounding PRF-advantage is shown to be reduced to bounding the number of structure graphs satisfying certain collision patterns. In the present paper, we show that [2, Lemma 10], stating an important result on structure graphs, is incorrect. This is due to the fact that the authors overlooked certain structure graphs. This invalidates the proofs of the PRF bounds. In [31], Pietrzak improved the bound for EMAC by showing a tight bound O(q2/2n)${O(q^{2}/2^{n})}$ under the restriction that ℓ<2n/8${\ell<2^{n/8}}$. As he used the same flawed lemma, this proof also becomes invalid. In this paper, we have revised and sometimes simplified these proofs. We revisit structure graphs in a slightly different mathematical language and provide a complete characterization of certain types of structure graphs. Using this characterization, we show that PRF security of CBC-MAC is about σq/2n${\sigma q/2^{n}}$ provided ℓ<2n/3${\ell<2^{n/3}}$ where σ is the total number of blocks in all queries. We also recover tight bound for PRF security of EMAC with a much relaxed constraint (ℓ<2n/4${\ell<2^{n/4}}$) than the original (ℓ<2n/8${\ell<2^{n/8}}$).https://doi.org/10.1515/jmc-2016-0030cbcemacstructure graphrandom permutationpseudorandom function94a60 68r05 68r10 68q87 |
| spellingShingle | Jha Ashwin Nandi Mridul Revisiting structure graphs: Applications to CBC-MAC and EMAC Journal of Mathematical Cryptology cbc emac structure graph random permutation pseudorandom function 94a60 68r05 68r10 68q87 |
| title | Revisiting structure graphs: Applications to CBC-MAC and EMAC |
| title_full | Revisiting structure graphs: Applications to CBC-MAC and EMAC |
| title_fullStr | Revisiting structure graphs: Applications to CBC-MAC and EMAC |
| title_full_unstemmed | Revisiting structure graphs: Applications to CBC-MAC and EMAC |
| title_short | Revisiting structure graphs: Applications to CBC-MAC and EMAC |
| title_sort | revisiting structure graphs applications to cbc mac and emac |
| topic | cbc emac structure graph random permutation pseudorandom function 94a60 68r05 68r10 68q87 |
| url | https://doi.org/10.1515/jmc-2016-0030 |
| work_keys_str_mv | AT jhaashwin revisitingstructuregraphsapplicationstocbcmacandemac AT nandimridul revisitingstructuregraphsapplicationstocbcmacandemac |