通过密码安全，我的意思是等同于具有密码哈希函数的HMAC的属性：
而又不知道密钥，知道哈希值不会泄漏有关数据的信息，
知道或选择某些数据并不能比蛮力更容易地恢复密钥。
通过滚动哈希，我意味着可以在逐字节滑动的窗口上高效地迭代计算它，即，存在形式为
$ H（c_ {nk-1} ... c_ {n}）的更新操作$ f $ = f \ left [c_n，c_ {nk-2}，H（c_ {nk-1} ... c_ {n-1}）\ right] $，其中$ c_i $是数据字符/字节，并且$ k $是滑动窗口的大小。
为了更具体地说明该应用程序，我们想构建一种安全的分块算法以进行重复数据删除，该算法可以产生可变大小的分块，该分块的大小是通过在内容上拆分数据而构建依赖点，并应避免切割点泄漏信息争夺数据。现有程序正在使用基于常见滚动哈希函数和自定义模糊处理的解决方案，这些函数似乎没有得到很好的分析，例如：
rsyncrypto使用的功能与gzip相同- -rsyncable，它只是字节的总和（显然很弱）。
阁楼正在使用循环多项式（Buzhash），对输入数据字节进行随机秘密替换（从字节到32位整数的替换，当前从a获得将公共表与32位秘密种子进行异或，但由作者计划将其替换为对归零表进行AES-CTR加密；此替换对应于Wikipedia页面中的$ h $函数。
Tarsnap使用的是Rabbin-Karp哈希，它具有输入数据字节的随机秘密替换和随机秘密参数（使用值是索引的HMAC的表从字节替换为32位整数，以及Wikipedia页面还取决于某些固定数据的HMAC；此外，滚动哈希的窗口大小也仅在一定范围内是已知的，并且是可变的。比其他人更安全，尤其是拉比-卡普（Rabbin-Karp）对布扎什（Buzhash）？
注意：分块应用程序具有以下特性：公开的加密数据很少（每次进行剪切决策时仅散列一个哈希值），并且只有部分加密数据已公开（通常，如果哈希的最后一位为空或等于某个值，则将执行剪切决定，因此仅公开这些最后一位）。
性能要求
对于重复数据删除应用程序，我们希望在最坏的情况下，普通计算机上哈希的处理速度至少等于磁盘读取吞吐量（例如约60MB / s），这样它就不会成为瓶颈。理想情况下，它应尽可能快，同时保留足够的安全保证。
[AES]用buzhash和AES-128实现DW的答案表明，在高端现代CPU（英特尔®酷睿™i7-4800MQ CPU @ 2.70GHz）上，安全滚动哈希的运行速度为9MB / s（对应于140MB / s的原始AES）。如果使用openssl的EVP API启用AES-NI，则性能峰值将达到56MB / s（相当于原始AES达到900MB / s），如果在ECB模式下按批次计算，则性能峰值甚至达到150MB / s（计算似乎是并行的）。但是，我们仍不能假设普通计算机具有这样的指令：例如，使用较旧的CPU（英特尔®酷睿™2双核CPU P8400 @ 2.26GHz），性能限制为4.4MB / s，并且性能较低最终的现代CPU（Intel®Atom™CPU N2800 @ 1.86GHz）达到1.5MB / s，这是不可接受的。
[SipHash]根据DW的回答， $ E $是PRF或具有较大域的PRP，因此，如果我没有记错的话，例如声称是PRF的SipHash应该可以。内置的安全滚动散列的运行速度为57MB / s，而无需使用任何特定的指令集，如果专门用于4字节输入，则甚至可以达到97MB / s。但是，这仍然远低于单独使用buzhash所获得的420MB / s，而在之前提到的较旧的CPU上，性能下降至12MB / s。不安全的滚动散列$ R $是$ n $位（例如$ n = 32 $），我们只需要长度为$ m
不幸的是，在进行了更多研究之后，可以在具有CBC-MAC的CPA下，将$ m $位块密码的字典破解为$ O（2 ^ m）$（发现3种特殊冲突）。在我们只显示值为0的冲突的特定上下文中，这是不可能的，并且最佳区分符需要$ O（2 ^ m）$个操作，这等效于$ n $个位的生日边界，因此该方案就像$ n $比特分组密码一样安全。但是$ n = 32 $也太小并且不安全，并且如果增加$ n $，那么最好的区分符仍然只需要$ O（2 ^ m）$运算（基本上是因为如果测试一个$ m $的所有值比特字，此方案将恰好与0产生一个碰撞，而随机函数可能会产生0,1,2 ...），因此具有CBC-MAC的方案不是$ m = 16 $的IND-CPA（与$ m \ geq64 $或$ 128 $）。
#1 楼
一个简单的密码安全滚动哈希函数如下：其中$ R_ {k2}（\ cdot）$是非加密滚动哈希函数（例如Rabin-Karp），而$ E_ {k1} $表示使用分组密码（例如AES）进行加密。通过$ R_ {k2}（\ cdot）$，我的意思是滚动哈希的参数应从$ k2 $派生。另外，我要求您选择$ R_ {k2}（\ cdot）$，以便它是通用哈希函数（$ \ epsilon $-几乎通用也足够）。有了这些选择，这将是加密安全的，并且将是滚动哈希。例如，如果您选择所有参数为秘密，那么Rabin-Karp就是$ \ epsilon $-几乎是通用的。并衍生自$ k2 $，因此这是一个不错的选择。对于循环哈希（Buzhash）也是如此，因此也可以通过这种方式使用。
请注意，当我编写$ E_ {k1}（x）$时，我的意思是对128位块$ x $。没有操作模式；这只是原始的分组密码。 （您可能会以为这是使用ECB模式，因此很成问题，但这是不正确的。这不是加密，并且ECB模式加密的问题不适用于此处。实际上，可以证明我的构造是安全的；请参见下面的证明草图。）
为什么问这为什么是滚动哈希值？好吧，给定$ y = F_k（x）$，如果您知道键$ k $，则可以计算$ z = E_k ^ {-1}（y）$，这是滚动哈希值$ R（\ cdot）$;然后在将输入$ x $更新为$ x'$时，使用与$ R（\ cdot）$一起使用的任何更新算法来更新$ z $，以获取更新的滚动哈希值$ z'$;然后加密$ z'$以获得$ y'= E_k（z'）$。现在$ y'$是$ x'$的安全滚动哈希，即$ y'= F_k（x'）$。因此，这将基于基础滚动哈希的更新功能为$ F_k（\ cdot）$提供更新过程。
为什么这种密码安全？这是从密码学的两个标准定理得出的：（1）如果$ R $是通用的，而$ E $是PRF，则$ E \ circ R $是PRF； （2）如果$ E $是具有较大域的PRP，则$ E $是PRF。当然，分组密码安全性的定义是它应该是PRP。因此，如果$ E $是安全的分组密码，则它是安全的PRF，因此$ F $也是如此。 PRF（伪随机函数）提供所需的安全属性。这是正确形式化密钥哈希的“密码安全性”含义的正确方法。即非常快。
就您询问的其他方案而言：
带有秘密参数的Rabin-Karp是不安全的。给定一些已知的明文，您可以使用线性代数轻松地恢复秘密参数（只需解决一些联立的线性方程式）。我不清楚您所说的“随机随机替换”是什么意思，因此我无法评论Attic或Tarsnap。
如果您是按照Wikipedia中的定义使用Buzhash，即使用表查找（秘密随机替换）将输入的每个字节映射到32位值，然后应用循环哈希，则这在密码上是不安全的。一切都是线性的，并且可以被线性代数打破。引入256个未知数$ T_0，T_1，T_2，\ dots，T_ {255} $表示256个表元素;换句话说，输入中的字节$ b $被映射到$ T_b $。然后，如果知道哈希函数的输入和相应的输出，则可以在$ T $上得到线性方程：例如，如果已知输入为
0x07 0x13，则输出为$ s（T_7）\ oplus T_ {19} $，它是$ T $的线性函数，可为您提供一个线性方程。因此，如果您拥有超过256个已知的输入/输出对，则可以使用线性代数恢复所有$ T $值，学习秘密替换，然后在将来完全破坏/预测哈希函数。因此，如果您需要加密安全性，请不要单独使用Buzhash。评论
$ \ begingroup $
令人信服！但是我现在担心性能。块密码非常快，这是事实，但是此方案加密了一个128位的块以处理输入的每个字节，因此它实际上比基础原始块密码慢16倍。是否存在可与32位块一起使用并在标准密码库中提供的安全块密码，以至少避免主要对填充字节进行加密？
$ \ endgroup $
– cyril42e
2014年5月10日0:28
$ \ begingroup $
@ cyril42e，您是否进行了基准测试？ AES-NI指令出奇地快。因此，您可能想要实施，进行基准测试，并查看其是否满足性能要求。如果没有，我建议编辑您的问题以描述您的性能要求，以及该方案获得多近的性能以及您尝试了什么以提高性能。为您的平台选择最快的分组密码不在此问题的范围内，但是您可以在此处找到许多其他有关此的问题，也可以提出一个新的问题。
$ \ endgroup $
– D.W.
2014年5月10日在1:06
$ \ begingroup $
@ D.W。 $ \; \; \; $具有大型域的“如果$ E $是PRP”，则$ E $是PRF。 $ \：$另外，（几乎）2-大学为此用途比（几乎）大学更有帮助吗？ $ \; \; \; \; \; \; $
$ \ endgroup $
–user991
2014年5月10日17:50
$ \ begingroup $
您应该将“安全”加密理解为具有PRP，并且应该将“大域”理解为对于所有整数$ q $（如果$ \：1 $ \ endgroup $
–user991
2014年5月12日20:45
$ \ begingroup $
@ D.W。，为了清楚起见，您要说的是，为了在您的答案中提出的方案中实现完美的安全性，非安全滚动哈希$ R_k $应该至少为128位？
$ \ endgroup $
– cyril42e
2014年5月16日17:13
评论
另外，如果您想让我们对Tarsnap或Attic的安全性发表评论，请更精确地定义“随机秘密替代”的含义。我编辑了问题以添加所需的信息，谢谢。
感谢更新。对于Attic和Tarsnap的工作方式，我仍然不清楚。替换是应用于输入数据还是Rabin-Karp /循环哈希的输出？我不知道“索引的HMAC”是什么意思。您想尝试用数学表达它吗？
抱歉，我还不清楚Tarsnap的工作方式。替换何时完成？是应用于输入数据还是输出？如果它从字节替换为32位值，是否在散列之前将输入的大小扩展4倍（或在散列之后将输出的大小扩展4倍）？
您获得了50或56 MB / s的速度，而您的目标大约是60 MB / s：听起来好像您已经完成了。英特尔处理器广泛部署在服务器上，现代英特尔处理器确实支持AES-NI。如果在您的应用程序域中，处理器通常不支持AES-NI，则您可能想要测量用户使用的处理器（提示：请确保进行测量），然后对其他有效的分组密码/ PRF进行一些研究（还有其他候选人）。如果SipHash满足您的性能要求，则可能不错，但我尚未对其进行详细研究。 128位密钥已足够。