TY - GEN
T1 - Constructing rate-1 MACs from related-key unpredictable block ciphers
T2 - 17th International Workshop on Fast Software Encryption, FSE 2010
AU - Zhang, Liting
AU - Wu, Wenling
AU - Wang, Peng
AU - Zhang, Lei
AU - Wu, Shuang
AU - Liang, Bo
PY - 2010
Y1 - 2010
N2 - Almost all current block-cipher-based MACs reduce their security to the pseudorandomness of their underlying block ciphers, except for a few of them to the unpredictability, a strictly weaker security notion than pseudorandomness. However, the latter MACs offer relatively low efficiency. In this paper, we investigate the feasibility of constructing rate-1 MACs from related-key unpredictable block ciphers. First, we show all the existing rate-1 MACs are insecure when instantiated with a special kind of related-key unpredictable block cipher. The attacks on them inspire us to propose an assumption that all the chaining values are available to adversaries for theoretically analyzing such MACs. Under this assumption, we study the security of 64 rate-1 MACs in keyed PGV model, and find that 1) 15 MACs are meaningless; 2) 25 MACs are vulnerable to three kinds of attacks respectively and 3) 24 MACs are provably secure when their underlying block ciphers are related-key unpredictable. Furthermore, we refine these 24 provably secure rate-1 MACs in Compact PGV model by removing a useless parameter away, and find that the resulting 6 provably secure MACs are in fact equivalent to each other. In the aspect of efficiency, however, the low rate of these secure MACs does not necessarily mean they can run faster than none rate-1 one MACs, due to their large number of key schedules.
AB - Almost all current block-cipher-based MACs reduce their security to the pseudorandomness of their underlying block ciphers, except for a few of them to the unpredictability, a strictly weaker security notion than pseudorandomness. However, the latter MACs offer relatively low efficiency. In this paper, we investigate the feasibility of constructing rate-1 MACs from related-key unpredictable block ciphers. First, we show all the existing rate-1 MACs are insecure when instantiated with a special kind of related-key unpredictable block cipher. The attacks on them inspire us to propose an assumption that all the chaining values are available to adversaries for theoretically analyzing such MACs. Under this assumption, we study the security of 64 rate-1 MACs in keyed PGV model, and find that 1) 15 MACs are meaningless; 2) 25 MACs are vulnerable to three kinds of attacks respectively and 3) 24 MACs are provably secure when their underlying block ciphers are related-key unpredictable. Furthermore, we refine these 24 provably secure rate-1 MACs in Compact PGV model by removing a useless parameter away, and find that the resulting 6 provably secure MACs are in fact equivalent to each other. In the aspect of efficiency, however, the low rate of these secure MACs does not necessarily mean they can run faster than none rate-1 one MACs, due to their large number of key schedules.
KW - Block Cipher
KW - Message Authentication Code
KW - Mode of Operation
KW - Provable Security
UR - https://www.scopus.com/pages/publications/77954716362
U2 - 10.1007/978-3-642-13858-4_14
DO - 10.1007/978-3-642-13858-4_14
M3 - Conference contribution
AN - SCOPUS:77954716362
SN - 3642138578
SN - 9783642138577
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 250
EP - 269
BT - Fast Software Encryption - 17th International Workshop, FSE 2010, Revised Selected Papers
PB - Springer Verlag
Y2 - 7 February 2010 through 10 February 2010
ER -