Security/Efficiency Tradeoffs for Permutation-Based Hashing
Security/Efficiency Tradeoffs for Permutation-Based Hashing
复制标题
基于排列的哈希的安全性/效率权衡
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
J. Steinberger
中科院分区：
文献类型：
--
作者：
P. Rogaway;J. Steinberger
我们提供的攻击和分析，捕获的权衡，在理想的排列模型，基于排列的哈希函数的速度和它的潜在安全性之间。我们发现，任何2n位到n位的压缩函数将有不可接受的冲突抵抗它使少于三个n位的置换调用，和任何3 n位到2n位的压缩函数将有不可接受的安全性，如果它使少于五个n位的置换调用。任何从n位排列构建的rate-a哈希函数都可以在大约N1-α次查询中被破坏，其中N = 2n。我们的研究结果提供了指导时，试图设计或分析一个基于置换的哈希函数的限制，什么可能是做。
We provide attacks and analysis that capture a tradeoff, in the ideal-permutation model, between the speed of a permutation-based hash function and its potential security. We show that any 2n-bit to n-bit compression function will have unacceptable collision resistance it makes fewer than three n-bit permutation invocations, and any 3n-bit to 2n-bit compression function will have unacceptable security if it makes fewer than five n-bit permutation invocations. Any rate-a hash function built from n-bit permutations can be broken, in the sense of finding preimages as well as collisions, in about N1-α queries, where N = 2n. Our results provide guidance when trying to design or analyze a permutation-based hash function about the limits of what can possibly be done.