NHPoly1305信息汇总
最后更新时间:
NHPoly1305信息汇总
NHPoly1305 - ε-almost-∆-universal hash function for Adiantum^1
这一段听上去很费解。
NH is used for performance since it’s over twice as fast as Poly1305.
什么是NH和Poly1305？
NH和Poly1305与UMAC的关系密切。为此，先关注于什么是MAC^2。
在密码学中，消息认证码（英语：Message authentication code，缩写为MAC），是经过特定算法后产生的一小段信息，检查某段消息的完整性，以及作身份验证。
跟CRC还有些不同：
MAC（消息认证码）和 CRC（循环冗余校验）都是用于检测数据完整性的技术，但它们在目的和实现上有显著的不同。
相同点
- 数据完整性检测：两者都用于检测数据在传输或存储过程中是否发生了变化。
不同点
- 目的：
- MAC：用于验证数据的完整性和真实性。它需要一个密钥来生成和验证，确保数据未被篡改且来源可信。
- CRC：主要用于检测传输或存储中的偶然错误，如噪声引起的比特翻转。它不提供安全性或真实性验证。
- 实现方式：
- MAC：通常基于加密算法，如 HMAC 使用哈希函数，CMAC 使用分组加密。
- CRC：基于多项式除法，使用简单的算法实现，计算效率高。
- 应用场景：
- MAC：用于需要安全性保障的场合，如网络通信、身份验证。
- CRC：用于检测数据传输中的错误，如网络协议（以太网帧）、存储设备。
总结
MAC 适用于需要安全性和真实性验证的场合，而 CRC 适用于快速检测偶然性错误的场合。两者在设计目标和使用场景上有明显的区别。
MAC的其中一种又叫作HMAC^3（Hash-based MAC)，这里已经开始出现了哈希函数。
对于数据中心而言，AWS使用的一种身份认证就是HMAC。
那HMAC之后是什么？就是UMAC^4 (Universal-Hashing^5 MAC)
In cryptography, a universal hashing message authentication code, or UMAC, is a message authentication code (MAC) calculated using universal hashing, which involves choosing a hash function from a class of hash functions according to some secret (random) process and applying it to the message.
根据某种随机处理过程，从一类哈希函数中选取一个进行MAC的处理。个人认为是随机化的HMAC（个人观点不保证准确）
根据RFC 4418^6中所说：
2
3
4
5
be very fast to compute in software on contemporary uniprocessors.
Measured speeds are as low as one cycle per byte. UMAC relies on
addition of 32-bit and 64-bit numbers and multiplication of 32-bit
numbers, operations well-supported by contemporary machines
这样的消息验证码生成在现代设备上运算速度很快。
那么UMAC使用的通用哈希函数又有哪些特征呢？
2
3
4
5
arbitrary length, and produces a 4-, 8-, 12-, or 16-byte output.
UHASH does its work in three stages, or layers. A message is first
hashed by L1-HASH, its output is then hashed by L2-HASH, whose output
is then hashed by L3-HASH.
消息要被三次哈希处理。其中第一层就是使用了NH算法。第二层是Poly算法。
详细实现参见RFC 4418。
回到开头nhpoly1305，那么这俩组合起来又是什么？看crypto/nhpoly1305.c里的注释。
“NHPoly1305” is the main component of Adiantum hashing.
It is an
ε-almost-∆-universal (ε-∆U) hash function for equal-length inputs over Z/(2^{128}Z), where the “∆” operation is addition. It hashes 1024-byte chunks of the input with the NH hash function [2], reducing the input length by 32x. The resulting NH digests are evaluated as a polynomial in GF(2^{130}-5), like in the Poly1305 MAC [3].
首先将1024字节的数据块通过NH哈希函数进行哈希处理。之后，它的产出将用于poly1305中的多项式。
这个ε-∆U是什么？
If we have an upper bound of ϵ<1 on the collision probability, we say that we have ϵ-almost universality.
这是维基百科的定义，然而我感觉还不够。姑且认为是保证了universal hashing的抗碰撞特性。
严格定义见参考文献^7。
回到这个nhpoly1305的注释里，这个算法是用于adiantum，或者换句话说，nhpoly1305.c是adiantum的c语言实现。
那么adiantum^8是什么？
Adiantum is a cipher composition for disk encryption. It uses a new cipher construction called HBSH (hash, block cipher, stream cipher, hash), specifically choosing NH, 256-bit Advanced Encryption Standard (AES-256), ChaCha12/ChaCha20[a], Poly1305 for the four elements.
It was designed in 2018 by Paul Crowley and Eric Biggers at Google specifically for low-powered mobile devices running Android Go. It has been included in the Linux kernel since version 5.0.
用于磁盘加密的算法，其中有NH、AES-256、ChaCha20、Poly1305四个组成部分。
有关于NH与Poly1305的讨论暂时到这里。如何优化是后续的事情。
总结
NH和Poly1305是两个算法，而crypto/nhpoly1305.c是用于Adiantum磁盘加密算法的实现。
另外，NH和Poly算法同时用在了UMAC消息认证码上。MAC家族里的HMAC在aws数据中心里被用于身份认证。
UMAC本身就可以认为是一种可以并行计算、支持SIMD的加速版本MAC。
在优化工作上，因Adiantum被用于低性能移动设备的磁盘加密。故nhpoly1305是一种比较高效的算法，可以同样用于riscv上，无论是提供UMAC计算加速还是其他算法的组件的加速部分都是可行的。