EdDSA and Ed25519
Table of Contents
1. EdDSA 简介
EdDSA 由 Bernstein 等人于 2011 年在论文 High-speed high-security signatures 中提出的,正如原论文标题所写的那样,它是一种非常快的签名算法。EdDSA 可以看作是 Schnorr 签名方案采用 Twisted Edwards Curve 时的变种。
EdDSA 在 RFC8032 中被标准化。目前 EdDSA 有两个方案:Ed25519 和 Ed448。Ed25519 采用的哈希函数为 SHA-512(SHA-2),曲线为 Curve25519;而 Ed448 采用的哈希函数为 SHAKE256(SHA-3),曲线为 Curve448。后文将重点介绍 Ed25519。
1.1. Twisted Edwards Curve
Twisted Edwards Curve 由下式定义:
1.1.1. Curve25519
对于 Curve25519,
如果采用 Montgomery Curve 形式,则 Curve25519 可以表示为:
关于作者是如何选择数字 486662 的?可以参考论文 Curve25519: new Diffie-Hellman speed records :
The smallest positive choices for A are 358990, 464586, and 486662. I rejected A = 358990 because one of its primes is slightly smaller than 2^{252}, raising the question of how standards and implementations should handle the theoretical possibility of a user's secret key matching the prime; discussing this question is more difficult than switching to another A. I rejected 464586 for the same reason. So I ended up with A = 486662.
2. EdDSA, Ed25519
2.1. 11 个参数
EdDSA 一共定义了 11 个参数。对于 Ed25519,这 11 个参数分别为:
+-----------+-------------------------------------------------------+ | Parameter | Value | +-----------+-------------------------------------------------------+ | p | p of edwards25519 in [RFC7748] (i.e., 2^255 - 19) | +-----------+-------------------------------------------------------+ | b | 256 | +-----------+-------------------------------------------------------+ | encoding | 255-bit little-endian encoding of {0, 1, ..., p-1} | | of GF(p) | | +-----------+-------------------------------------------------------+ | H(x) | SHA-512(x) [RFC6234] | +-----------+-------------------------------------------------------+ | c | base 2 logarithm of cofactor of edwards25519 in | | | [RFC7748] (i.e., 3) | +-----------+-------------------------------------------------------+ | n | 254 | +-----------+-------------------------------------------------------+ | d | d of edwards25519 in [RFC7748] (i.e., -121665/121666 | | | = 370957059346694393431380835087545651895421138798432 | | | 19016388785533085940283555) | +-----------+-------------------------------------------------------+ | a | -1 | +-----------+-------------------------------------------------------+ | B | (X(P),Y(P)) of edwards25519 in [RFC7748] (i.e., (1511 | | | 22213495354007725011514095885315114540126930418572060 | | | 46113283949847762202, 4631683569492647816942839400347 | | | 5163141307993866256225615783033603165251855960)) | +-----------+-------------------------------------------------------+ | L | order of edwards25519 in [RFC7748] (i.e., | | | 2^252+27742317777372353535851937790883648493). | +-----------+-------------------------------------------------------+ | PH(x) | x (i.e., the identity function) | +-----------+-------------------------------------------------------+
2.1.1. 点(如公钥)的编码(32 字节)
对于
Ed25519 的参数
总结: Ed25519 的点(如公钥
+--------+--------+--------+-- --+--------+--------+ | p[0] | p[1] | p[2] | ...... | p[30] | p[31] | +--------+--------+--------+-- --+--------+--------+ ^ | | 由于是小端形式,所以最后一字节的最高比特位才表示 x 的正负
当然,也可以使用 255 个比特位编码
参考:
https://datatracker.ietf.org/doc/html/rfc8032#section-5.1.2
https://datatracker.ietf.org/doc/html/rfc8032#section-3.1
2.2. 生成私钥和公钥
为了计算公钥,我们对私钥
特别地,对于 Ed25519(
注 1: Ed25519 公钥从 Ed25519 私钥哈希
注 2:后文我们可以看到私钥哈希
注 3:尽管
2.2.1. 修改 Schnorr 私钥比特位(Bit Clamping)
在由 EdDSA 私钥推导 Schnorr 私钥时(参考节 2.2),为什么不直接使用左边的 256 比特位,而是要做下面修改呢?
- 把第 0,1,2 比特位(最低 3 位)设置为 0;
- 把第 255 比特位设置为 0,把第 254 比特位设置为 1;
这样做的原因分别为:
- 把第 0,1,2 比特位(最低 3 位)设置为 0 的原因是:为了避免 Small-Subgroup Attack(注:当椭圆曲线的 Cofactor 大于 1 时,可能遭受 Small-Subgroup Attack(参考节 5.1),而 Curve25519 的 Cofactor 为 8)。需要说明的是 就算我们不把最低 3 位设置为 0,其实 Ed25519 也不会遭受 Small-Subgroup Attack。因为 Ed25519 中没有 Small-Subgroup Attack 中“自己秘密值和别人提供的数据相乘”的场景出现。而之所以把最低 3 位设置为 0,是为了让 Ed25519 的密钥同时也可以安全地作为 X25519(key-exchange)协议的密钥。
- 而把第 255 比特位设置为 0,把第 254 比特位设置为 1 的原因:让 Curve25519 可以利用 Montgomery ladder 优化手段来加快 Scalar Multiplication 运算。这个设置也不是必要的,因为 Scalar Multiplication 还有其它更快的优化手段。
详情可参考:https://www.jcraige.com/an-explainer-on-ed25519-clamping
2.3. 生成签名
2.4. 验证签名
有了签名数据
特别地,为了防止 Signature Malleability,在验证签名
2.4.1. 证明
EdDSA 的证明:
2.4.2. 验证签名时无法检测 和 是否符合 RFC8032
RFC8032 中规定了:
- Schnorr 私钥
(它由 EdDSA 私钥推导出来),需要把其进行 Clamping 操作(参考节 2.2.1 ,即最低 3 位设置为 0,最高位设置为 0,次高位设置为 1); - 签名时使用的
值由 计算而来。
如果签名者不遵守上面两个要求(比如对
因为验证签名时,从签名数据
2.5. 签名总结
Ed25519 密钥对生成和签名过程可总结为图 1 所示(摘自:https://blog.mozilla.org/warner/2011/11/29/ed25519-keys/ )。
Figure 1: Ed25519 密钥对生成和签名过程(图中 a 是前面介绍的 Schnorr 私钥 s)
3. Ed25519 实现
在 RFC8032 第 6 节中有 Ed25519 的一个 Python 实现。在 https://ed25519.cr.yp.to/software.html 中也有 Ed25519 的一个 Python 实现。
3.1. Ed25519 实现漏洞之“假公钥”
Ed25519 协议本身目前还没有发现有漏洞,不过不恰当的实现可能导致安全漏洞。
出于效率考虑,一些库在实现 Ed25519 时,公钥
攻击者对同一个消息
第一次签名,假设输入的公钥为
第二次签名,假设输入的公钥为
由于
把两次签名得到的
从而有:
我们可以求得
避免这种攻击的办法:不提供签名方法
3.2. Ed25519 实现漏洞之 Signature Malleability
什么是 Signature Malleability?在不知道私钥的情况下,如果通过修改一个已知的合法签名,可以得到另一个合法签名,这就称为 Signature Malleability。Signature Malleability 可能被黑客用于攻击,我们需要避免 Signature Malleability。
假设
下面证明一下,为什么
两个等式的右边是一样的,我们只要证明两个等式的左边相等即可,即证明
循环子群的阶为
根据上面的证明过程可知,当
为了避免 Signature Malleability,在 RFC8032 中规定了在校验签名
不过,在实现时可能忽视了这个检查,如 OpenSSL 以前就忽视过,参见:https://github.com/openssl/openssl/issues/7693
4. BIP32
有人指出在 Hierarchical Deterministic (HD) 场景中如果多次使用 Bit Clamping(参见节 2.2.1)可能不安全,参见:https://moderncrypto.org/mail-archive/curves/2017/000858.html ,有人给出了解决办法,参见:https://moderncrypto.org/mail-archive/curves/2017/000866.html
论文 BIP32-Ed25519: Hierarchical Deterministic Keys over a Non-linear Keyspace 中提出了如何调整 BIP32 来为 Ed25519 曲线推导分层确定性(HD)密钥。不过有人指出,如果 BIP32-Ed25519 中允许很长的 Derivation Path,则可能被恢复出私钥,参考:https://github.com/w3f/hd-ed25519
5. 附录
5.1. Small-Subgroup Attack
当 Cofactor 不为 1 时,可能存在 Small-Subgroup Attack,这里以 Diffie Hellman Key Exchange 协议来介绍下什么是 Small-Subgroup Attack。
The operations are usually implemented in the prime order subgroup of the full Curve. Let’s take the example of Diffie Hellman to understand the small subgroup attack. Let’s say our curve is of order 8p where p is a prime & 8 is the cofactor. The main group of order 8p is a finite cyclic Group. By the fundamental theorem of finite cyclic groups, the 2 subgroups of order 8 & order p are also finite cyclic subgroups. Let G be a generator of the prime order subgroup. Let a & b be Alice’s & Bob’s private key respectively. This is how a typical Diffie Hellman key exchange works.
Alice −−−−−−--−−aG−−−−−−−−−−−→ Bob
Alice ←−−−−−−−--bG−−−−−−−−−−−− Bob
Alice calculates a⋅bG, Bob calculates b⋅aG and the shared secret is derived from abG by both parties.
If Bob is a malicious participant, he can launch a small subgroup attack which can leak some information about Alice’s private key. The protocol depends on operating in the prime order subgroup (i.e. the subgroup of order p). Since G is a generator of the prime order subgroup, abG also falls in the prime order subgroup (because of closure). But the full curve group also contains other subgroups - one of which is of order 8. The points of the subgroup of order 8 are not in the prime order subgroup (other than the identity). Let H be a generator of the subgroup of order 8. Now, if Bob instead of sending bG to Alice sends just H to Alice. So Alice calculates aH (instead of abG) & derives the share secret using that. Alice then encrypts a message using the shared secret & sends it to Bob. Now if Alice’s shared secret had been derived from abG, then number of possible values abG could have is p which is a very large prime - for e.g. for Curve25519,
so brute forcing the encrypted message to recover the shared secret is not possible. However, Bob has tricked Alice into deriving her shared secret from aH. Since H is a generator of subgroup of order 8, aH is a point of the subgroup of order 8 because of closure in the subgroup. So aH can only be one of 8 points instead one of p points. Now brute forcing the secret key is much simpler for Bob. So Bob can recover aH. It’s possible to recover the value of a mod 8 from aH - which is the lower 3 bits of a.
To understand this better, let’s take the example of a simple additive group of order 8p where p=11 and the cofactor is 8. This is the group ℤ/88ℤ. This has the elements {0,1,2,3,4,….87} (I am omitting the coset notation for simplicity)
This has multiple subgroups including
- the prime order subgroup of order 11 - {0,8,16,24,32,40,48,56,64,72,80}
- the cofactor subgroup of order 8 - {0,11,22,33,44,55,66,77}
Let the generator chosen for the DH exchange be 8. So Alice would send a⋅8 & Bob would send b⋅8 & the shared secret would be derived from ab8. A malicious Bob instead of sending b⋅8, sends a generator of the cofactor subgroup - i.e he sends 11. So now Alice computes 11a. Irrespective of what a is chosen by Alice, a⋅11 always is restricted to 8 different elements instead of the bigger group of 11 different elements if Bob was a honest participant. Alice now derives the shared secret from a⋅11 & she encrypts a message with it & sends it to Bob. Because of the attack, Bob now has to only bruteforce by doing an exhaustive search through 8 different elements instead of 11 different elements. In our toy example, reduction from 11 to 8 is not a significant reduction, but in the case of actual cryptographic curves, the reduction in search is huge - from searching through a really large set of size p to searching through just 8 points. So now Bob knows aH. If you iterate through all possible 88 values of a & calculate aH, you will see that aH falls into 8 different values depending on value of a mod 8. So if you know the shared secret, you know a mod 8 which is the lower 3 bits of a.
This is the small subgroup attack.
There are also a couple of other attacks similar to the one we described.
- Instead of sending bG, Bob can send bG+H to Alice. So Alice now calculates abG+aH. Now since Bob knows abG, this again leaks a mod 8.
- Instead of Bob launching the above attack, a man in the middle (Mallory) intercepts bG sent by Bob & replace it with H, then he can brute force the secret key generated by Alice (aH) because it can only be one of 8 points.
In DH, leaking a mod 8 matters only if Alice reuses a. However, above attack is not limited to DH, but also applicable to many other Cryptographic protocols. In some protocols like like PAKE, MQV etc, the attack can have far worse effects.
Mitigation for the small subgroup attack - cofactor clearing
If you have a cyclic group of order np (where p is a prime), then scalar multipliying any element of the group by the cofactor (n) gives you an element of the prime order subgroup irrespective irrespective of which subgroup it was in originally. This can be easily done by both parties - i.e. Alice after choosing a private key a, she multiplies it by 8 & uses 8a as the private key. So when she receives bG from Bob, the shared secret is derived from 8abG instread of from abG. Likewise Bob does the same. Now if Bob is a malicious player, then what is leaked is 8a mod 8 instead of a mod 8. Since 8a mod 8 is always 0, nothing of significance is leaked. Thus, mutliplying the private key by the cofactor mitigates the small subgroup attack.
摘自:https://risencrypto.github.io/CofactorClearing/
简单总结下 Small-Subgroup Attack:在进行 Diffie Hellman Key Exchange 时,Bob 发给 Alice 的数据期望是从大子群中来(bG),但 Bob 如果使坏不发送大子群中的 bG,而是把小子群中元素 H 发给 Alice,那么 Alice 得到的 shared secret 就是 aH,当 Alice 使用 shared secret aH 加密数据发送给 Bob 后,Bob 可以通过暴力搜索破解出 aH(因为 H 所在小子群只有 8 个元素,从而 aH 的可能情况也只有 8 个)。Bob 知道 aH 后,可能从中得到 Alice 的秘密 a 的部分信息(因为大子群中的任意数 a 和小子群 H 相乘后得到的数会在小子群中,也就是只有 8 种可能,这相当于泄露了 a 的最低 3 个比特位)。
之所以会泄露 Alice 的秘密 a 的部分信息,是由于 Alice 把 a 和 Bob 提供的恶意数据相乘后发送给了 Bob。有一种方法可以避免 Small-Subgroup Attack:Alice 在使用 a 前,先把 a 乘以 Cofactor(8),由于这样操作后,其结果的最低 3 位会是 0,这样就不会泄露原先的 a 了。
注:在椭圆曲线中,把自己秘密值和别人提供的公钥相乘是一个危险的操作,比如在 Dangers of using secp256k1 for encryption - Twist Attacks 中提到了一种攻击方式可能会使 secp256k1 的私钥被泄露。