高速SIMD乘法与位移指令的密钥哈希与伪随机函数- HighwayHash

80 浏览量更新于2024-07-14 收藏 314KB PDF 举报

"Fast Keyed Hash and Pseudo-Random Function using SIMD Multiply and Permute - 20 Nov 2016 (1612.06257v2)" 是一篇关于计算机科学的论文，主要探讨了一种基于SIMD（Single Instruction Multiple Data）乘法和位选择指令的快速键控哈希和伪随机函数。该方法被称为HighwayHash，由J. Alakuijala、B. Cox和J. Wassenberg于2017年11月在Google Research发表。 HighwayHash设计的目标是提供一种高效且安全的哈希算法，尤其在处理1KB输入时，其性能比流行的SipHash快3.8倍。该算法利用了现代处理器中的AVX2（Advanced Vector Extensions 2）扩展，这些扩展提供了对大量数据进行并行处理的能力，通过SIMD指令执行多元素乘法和位操作，从而实现快速的哈希计算。论文中，作者讨论了设计选择，并提供了统计分析，包括速度测量和初步的密码学分析。他们假设HighwayHash能经受住进一步的安全分析，其强化版本可能也会对文件校验和及流密码的加速带来显著提升。这表明，HighwayHash不仅关注性能，也重视安全性，以防止潜在的碰撞攻击和其他恶意行为。哈希函数在信息安全领域扮演着重要角色，例如消息认证、高效搜索以及“随机”决策。当攻击者能够找到哈希碰撞（即多个输入产生相同的哈希结果）时，他们可以发起拒绝服务攻击或破坏期望均匀分布输入的应用。键控哈希函数通过使用一个秘密密钥来确保输出的不可预测性，从而防止这种情况发生。这类函数的构建方式使得即使攻击者可以控制输入，也无法轻易预测或篡改输出。这篇论文介绍了HighwayHash作为一种新型的键控哈希和伪随机函数，它利用了现代处理器的高级特性来提高性能，同时保持了必要的安全属性。开放源代码的实现使得这个技术可被广泛采用和评估，对于需要高效哈希运算的领域，如大数据分析、存储系统和网络安全，HighwayHash提供了一个有吸引力的解决方案。

We develop two alternatives that further increase throughput while

retaining the simplicity and thorough mixing of SipHash. We hope that these

algorithms will replace unsafe hash functions and increase the robustness of

applications without incurring excessive CPU cost.

3 SipTreeHash

Maximizing performance on modern CPUs usually requires the use of SIMD

instructions. These apply the same operation (e.g. addition) to multiple

‘lanes’ (elements) of a vector. This works best for data-parallel problems.

However, the SipHash dependency chain oﬀers limited parallelism and cannot

fully utilize the four AVX2 vector lanes. Our SIMD implementation was

actually slower than the scalar version, presumably because of the lack

of bit rotation instructions. We instead compute four independent hash

results by logically partitioning input buﬀers into interleaved 64-bit pieces.

For example, consider a 64 byte input interpreted as eight 64-bit words:

, A

, B

. These can be combined into four hash results

with two updates, one with

and the other with

. We must then fold

the four results into a single hash. XOR reduction is unsuitable because it

cannot distinguish between permutations of the 64-bit words. Instead, we

can just hash the results. This is known as a tree-hash construction and has

been used to accelerate SHA-256 [8].

Our implementation [

] is available as open source software under the

Apache 2 license. Being a straightforward extension of SipHash, this construc-

tion is likely to be secure. However, its hash results are of course diﬀerent, so

this cannot be used as a drop-in replacement. We suggest HighwayHash be

considered instead because it is much faster, especially for smaller inputs.

4 HighwayHash

Tree hash constructions appear to be a good way to utilize SIMD instruc-

tions. However, the SipHash add-rotate-XOR construction is not ideally

suited for current instruction sets. As previously mentioned, bit rotations

must be implemented by ORing together the result of left and right shifts.

Although rotations of multiples of 8 bits can be implemented with very fast

byte permute instructions, this would weaken SipHash to an unacceptable

degree [

]. The individual add and XOR instructions also only achieve a

weak mixing eﬀect. By contrast, AVX2 includes 32

32 bit multiplication

instructions that mix their operands much more thoroughly. Although their

剩余14页未读，继续阅读

weixin_38662122

粉丝: 5
资源: 949

高速SIMD乘法与位移指令的密钥哈希与伪随机函数- HighwayHash

python3.6.5参考手册 chm

Matlab时频分析工具箱及函数应用说明

又报错了<transition-group> children must be keyed: <keep-alive>

freetype-2.8-14.el7.x86_64.rpm

<TransitionGroup> children must be keyed.

<template> cannot be keyed. Place the key on real elements instead.

*** [.pio\build\esp32s3box\src\ChappieBsp\Lvgl\demos\benchmark\assets\img_benchmark_cogwheel_chroma_keyed.c.o] Error 1 ***

vue.esm.js:5105 [Vue warn]: <transition-group> children must be keyed: <ElTag> found in

AttributeError: The vocab attribute was removed from KeyedVector in Gensim 4.0.0. Use KeyedVector's .key_to_index dict, .index_to_key list, and methods .get_vecattr(key, attr) and .set_vecattr(key, attr, new_val) instead.

flink.state.backend.path

最新资源

* [.pio\build\esp32s3box\src\ChappieBsp\Lvgl\demos\benchmark\assets\img_benchmark_cogwheel_chroma_keyed.c.o] Error 1 *