回來吧王女士我最驕傲的信仰😭😭😭 @"n0099"#1

@"n0099"#p36514 您忠誠的四葉tg殘部

tg群是维也纳的地盘里1群是现充人的地盘早已解体的流亡四叶没有容得下我的地方

@"n0099"#p36516 四葉tg殘部是您永遠的家

我局的是您和维也纳的家邀请链接？

@"n0099"#p36518 https://t.me/+TFrGbh04kXRjMzE1

@"n0099"#p36520 已第114514次宣告退葉

@"PeterBarofsky"#p36521 什么时候

回來吧王女士

n0099

yangbowen 您可以让我再转发过去
那为什么不用sha3而是sha2-256
https://github.com/Cyan4973/xxHash/issues/450

yangbowen

n0099 您可以让我再转发过去

不署名（或者以其它方式指向）到我的前提下你要是愿意转发过去我也没意见。比方说以你自己或者“我认识的某个人”的身份。
别无端引流就好

n0099 那为什么不用sha3而是sha2-256

SHA3 的设计使得在没有硬件加速的软件实现上，比 SHA2 慢不少吧。等到 SHA3 硬件加速普及了的话我也推荐 SHA3 。

n0099

yangbowen 以你自己

然后楼主来回复我我不懂装懂？

yangbowen SHA3 硬件加速普及了

blake3有指令集加速？

yangbowen

yangbowen 总之是我我就直接 BLAKE3 了。安全性好，没 Merkle Damgard 的坑，性能也挺快

BLAKE3 采用先进的树状构造（ Merkle Tree ）而不是 Merkle Damgard （MD5、SHA1、SHA2）、 Sponge （SHA3）之类的链式构造，带来一些性能和使用上的好处，比如易于并行计算（每棵子树的计算是独立的）、流式哈希（通过附带上层树节点上的值，可以在接收到完整数据之前就验证已经接收到的部分的哈希）等等。这些优点我是很欣赏的。

n0099

yangbowen 那xxhash3用的什么

yangbowen

n0099 那xxhash3用的什么

没了解过。我看看……

……应该属于带 finalize 的 Merkle Damgard 。因为 finalize 步骤的存在所以并没有长度扩展攻击，不过仍旧是串行的。

yangbowen

n0099 blake3有指令集加速？

BLAKE3 的回合函数是基于 ChaCha 的回合函数。正如 ChaCha 那样属于 ARX ，也就是用 Add Rotate Xor 三种操作组成。这三种操作对于几乎所有 CPU 来说都是本身就有硬件指令的。
顺带一提 xxHash 用了 Add Multiply Rotate Shift Xor Or 。

ARX 当中 Rotate 和 Xor 都是“每个输入位只影响固定的一个输出位”的，不具有对称密码学所需的扩散特性。因此 ARX 类加密算法的扩散是完全基于 Add 操作的——加法进位的时候就会对高位产生影响。
所以用 ARX 造加密算法其实相当于投机取巧，利用 CPU 本来就有的整数加法的硬件加速。

n0099

yangbowen 串行是指不能并行计算？sha3能吗？

yangbowen

n0099 串行是指不能并行计算？

是指对于输入数据不能并行地处理。哈希函数的大部分开销在于对每块输入数据要做的回合函数，一个串行的 construction 意味着必须处理完前一块输入数据才能开始处理下一块。
需要注意的是，同一块数据的回合函数当中本身利用了 SIMD 并行性，跟前面说的“整段输入”层面上的并行与否是两回事。

n0099 sha3能吗？

SHA-3 使用 Sponge Construction ，也是串行的。 SHA-3 的设计团队后来设计的 Kravatte 使用 Farfalle Construction ，是并行的，并且安全属性跟 SHA-3 相当（因为都是基于 keccak-p 置换）。

n0099

yangbowen SIMD 并行性

什么 https://en.wikipedia.org/wiki/Bit-level_parallelism

yangbowen 后来设计的 Kravatte 使用 Farfalle Construction ，是并行的

所以其能并行计算每个chunk？其性能提升有多少？不会还不够上下文交换的吧

yangbowen

n0099 其性能提升有多少

与其说是性能提升，不如说是能不能利用上多线程的问题。也就是所谓“可扩展性”。
对于比较长的输入数据（至少要比单个块长得多，比方说 MiB 级别）才会体现优势。相比之下哈希表使用的非密码学哈希更多是为短输入优化的（显然大部分时候您的哈希表里单个 key 并不会长达 MiB 级别），所以采用简单的 Merkle Damgard 也是合理的。

事实上典型的哈希表会有很多几到几十个字节的短输入（比方说 JSON 键的典型长度），对于这种长度范围来说 SIMD 都不一定有正向提升， AVX512 的话很可能还负优化。“每次哈希”的 initialize/finalize 开销也可能会压过“每块数据”的 compress 开销。
这也是设计 xxHash 这类“快哈希”的时候跟设计密码学哈希的时候要做不同考量的方面。

n0099

yangbowen 有hashtable用xxhash？现在一般用什么？

yangbowen

n0099 有hashtable用xxhash？

我觉得有，但是具体例子我不知道

n0099 现在一般用什么？

libstdc++ 以及 MSVC 用的 FNV1a ， libc++ 用的 Murmur2 （对于 32 位平台）或者 CityHash64 （对于 64 位平台）。
Rust 是 SipHash-1-3 ，用 SipHash 的也挺常见的，主要是防 hashflood 攻击。
别的不清楚。
别用 FNV ，很慢。

n0099

yangbowen 怎么都不用很容易碰撞但实现简单的crc32
甚至pgsql那样自己改了常量表的crc32 https://github.com/n0099/open-tbm/issues/105

https://github.com/postgres/postgres/blob/d81dcc8d6243054e3bde40c6fb2b2a0be4b19da6/contrib/pg_trgm/trgm_op.c#L260-L262 https://github.com/postgres/postgres/blob/9e345415bcd3c4358350b89edfd710469b8bfaf9/src/include/utils/pg_crc.h#L65-L82 https://github.com/postgres/postgres/blob/66e9df9f6ef50719b25ca63b60aad934e14f4a1c/src/backend/utils/hash/pg_crc.c#L27-L35 https://postgrespro.com/list/thread-id/1853644 https://crccalc.com

yangbowen

n0099 怎么都不用很容易碰撞但实现简单的crc32

因为 CRC32 适合硬件实现而不适合软件实现，软件实现性能不高
特别是简单的软件实现性能就更惨不忍睹了
硬件加速要针对每个特定的 CRC 多项式单独设计
CRC 主要还是用于物理层协议编码/解码的 checksum

n0099

yangbowen 那为什么pgsql手写c实现和自己的多项式表

yangbowen

n0099 不知道，别问我

yangbowen

PeterBarofsky

现在还是活群吗

« 上一页