如何確認我的實施是恆定的時間
我正在按照該算法的比特幣現金 (BCH) 中使用的變體實現 Schnorr 簽名：GitHub - Schnorr Signatures for secp256k1。
一個顯著的區別是 BCH schnorr 算法使用這個變體：IETF - Variant for k 計算。
我在 scala 中使用 Java 的充氣城堡。我通過使用我在這裡呼叫的東西來計算 k，
nonceRFC6979這是我在上面的連結中顯示的實現def sign(unsigned: ByteVector, privkey: PrivateKey): Result[Signature] = { val d = privkey.toBigInteger val N = ecc.domain.getN val G = ecc.domain.getG /** Calculate k*/ val nonceFunction = nonceRFC6979 nonceFunction.init(N, new ECPrivateKeyParameters(d, ecc.domain).getD, unsigned.toArray, additionalData.toArray) val k0 = nonceFunction.nextK.mod(N) if (k0.equals(BigInteger.ZERO)) Failure(Err("Fail to generate signature")) /** R = k * G. Negate nonce if R.y is not a quadratic residue */ val R = G.multiply(k0).normalize val k = if (hasSquareY(R)) k0 else N.subtract(k0) /** e = Hash(R.x || compressed(P) || m) mod n */ val P = G.multiply(d) val pubBytes = P.getEncoded(true).toByteVector val rx = R.getXCoord.toBigInteger.toUnsignedByteVector val e = Sha256.hash(rx ++ pubBytes ++ unsigned).toBigInteger.mod(N) /** s = (k + e * priv) mod n */ val s = e.multiply(d).add(k).mod(N).toUnsignedByteVector /** Signature = (R.x, s) */ val sig = rx ++ s Successful(Signature(sig)) }這是
nonceRFC6979HMacDSAKCalculator與計算相同的實現nextK，如前所述，唯一的區別是我們在此處附加了一些額外的數據，命名為additionalData現在我試圖使這個簽名算法的時間恆定以避免定時攻擊。我的理解是這
multiply可能是一個特別的問題kG。通過查看上面的程式碼，對於那些知道 Bouncy castle 的人，我應該研究什麼來檢查這確實是恆定的？
如何確認我的實施是恆定的時間？我在 scala 中使用 Java 的充氣城堡。
此程式碼不是恆定時間，因為沒有指定平台。以恆定時間或週期執行的計算平台是例外。我不知道目前出售的任何具有網際網路和影片功能的設備。這實際上有助於使攻擊更加困難！
對於加密安全，重要的是數據相關的時序變化：執行時間取決於所操縱的數據¹。該問題的程式碼很可能展示了一些 DDTV，因為它顯然使用了 Java 的 BigInteger 類型，該類型並非旨在避免 DDTV，甚至沒有接近。Bouncy Castle 充斥著使用 BigInteger 的 DDTV，或多或少取決於版本和平台，至少在它的通用 RSA 解密程式碼中（我深入研究的唯一部分）。BC 開發人員通過在容易的情況下降低 DDTV 來解決這個問題，並在不太容易時嘗試用某種程度的噪音來隱藏它。這可能是他們在可移植 Java 加密庫框架中所能做到的最好的了。
除了從頭開始使用面向恆定時間的技術一直到所有加密原語的裸硬體（就像在高安全性設備中的加密加速器和BearSSL中所做的那樣），我認為達到零 DDTV 的希望很小，這是最滿足選項從安全的角度來看，並被實踐。
由於缺乏這一點，唯一的選擇是嘗試使 DDTV 足夠低以使其不會受到攻擊，並嘗試評估這一點。情況很複雜。
在下文中，我將僅討論一些可以添加到現有庫之上的實際增量對策，並且可能會有所幫助。我確信它既不是必要的，也不是充分的，甚至肯定沒有安全缺陷。
一種在理論上有效（甚至完美）的通用對策是在計算開始時啟動一個計時器，考慮到最壞的情況（也許是實驗的最大時間加上幾倍於實驗標準差 $ \sigma $ )，並在計算結束時精確地等待直到計時器結束，然後再釋放結果。但這是便攜性的噩夢。對手（或對平台的控制不佳）可能會增加計算時間（例如通過增加工作量）或減慢 CPU 速度以使其超過計時器；或者，攻擊者可能會設法獲得 CPU 時間的測量值，而不考慮等待計時器過去的時間。
另一種對策增加了隨機延遲。它需要具有精細的粒度。一種簡單的方法是繪製一個均勻隨機整數並等待該週期數（或者如果不可能，則為虛擬循環²），最大整數校準為平均幾個 $ \sigma’ $ ³ 因為缺乏更合理確定的值⁴。雖然攻擊者可以通過關聯不同的實驗，或者重複相同的實驗並平均或保持最小測量時間來減輕這種延遲⁵，但它們通過在對手的輸入中增加不確定性是有用的，這往往會使成功的攻擊需要更多的測量，因此更多的時間。
上述延遲（最終或隨機添加）的問題在於，除了純時序（差分功率分析、電磁和音頻變體、記憶體等硬體功能……）之外，它們對邊通道沒有或幾乎沒有用處。
針對更廣泛的側通道攻擊的一類通用對策是致盲。一般原則是混入一個隨機值，該值會改變計算的方式（因此它的時序和其他側通道洩漏，以與秘密數據無關的方式），但不是其最終結果，這要歸功於數學特性。
一種適用於模計算的致盲對策 $ n $ ，例如 $ s=(k+e\cdot\text{Priv})\bmod n $ , 是
- 添加 $ r_i\cdot n $ 對於隨機 $ r_i $ （說在範圍內 $ [0,2^{64}) $ ）到部分或全部輸入（這裡 $ k $ , $ e $ , $ \text{Priv} $ ) 的公式
- 執行計算模 $ u,n $ 代替 $ n $ ， 對於一些 $ u $ （比如說在一個範圍內 $ [2^{63},2^{64}) $ ，固定或動態隨機選擇），
- 最後減少模 $ n $ .
本著這種精神的另一個對策是，有機會降低橢圓曲線標量乘法中的時間差異的可利用性，同時僅適度增加執行時間（如 30%），即間接生成 $ k $ 併計算 $ R=k\times G $ （在哪裡 $ \times $ 是橢圓曲線上的點乘法）：
- 選擇一些參數 $ m\approx2^{32}\sqrt n $ 和預計算 $ G_m=m\times G $ ( $ m $ 可以是固定的和公開的，包括 2 的冪，或者在性能無關緊要的時候隨機選擇的秘密）。
- 生成隨機 $ k_a $ 和 $ k_b $ 在 $ [0,m’) $ 和 $ m’\approx m $ ，也許是固定的 $ m’=2^{\left\lceil\log_2(m)\right\rceil} $
- 計算 $ R=(k_a\times G_m)+(k_b\times G) $ 在哪裡 $ + $ 是橢圓曲線上的點加法。
- 利用 $ k_a\cdot m+k_b $ 代替 $ k $ 在計算中 $ s=(k+e\cdot\text{Priv})\bmod n $ . 等價物的選擇 $ k $ 不是完全均勻隨機的，但對於 Schnorr 簽名來說仍然很好。減模 $ n $ 可以不同於最終的計算 $ s $ . 考試 $ k=0 $ 可以通過檢查來代替 $ R=\infty $ （實際上，只有在存在一些錯誤或故障時才會發生這種情況，例如在 RNG 中，最好的做法是將私鑰歸零/銷毀，如果這不會造成巨大損失）。
結論：
- 忘記大多數現代計算平台上的恆定時間。
- 零 DDTV 是可取且可實現的，通常在硬體中，甚至在軟體中，但在使用 Java 的標準 BigInteger 類時忘記它。
- 從這個程式碼開始，最容易達到的短期目標是減輕 DDTV 的影響，使其低於在實際條件下可以通過已知方式明顯利用的水平。
- 如何以及如何評估它是廣泛的主題，在這個答案中幾乎沒有涉及。
¹ 我們真的只關心機密數據，但在這段程式碼片段中很多都是。
² 存在可以通過更智能的編譯器或目標平台的 JITC 優化的問題。
³ 與上一個相反 $ \sigma $ ， 這個 $ \sigma’ $ 需要主要考慮 DDTV，而不是與平台相關的可變性。
⁴ 計算需要多少需要實際 DDTV 的模型，以及攻擊者可用時間的假設。
⁵ 如果測量受到增加時間的虛假活動的困擾，那麼（從攻擊者的角度來看）這是一種比平均更強大的策略。隨機延遲的分佈很少是最小的，包括由於沿著計算傳播以阻止重新同步的多個相等延遲而導致的接近高斯分佈，這會給必須依賴此策略的攻擊者帶來比統一延遲更難的時間。
孤注：可以想像，它可能有助於用 CSPRNG 替換隨機延遲和致盲中使用的隨機源，由長期隨機對稱密鑰和計算輸入（這裡是要簽名的消息）作為密鑰。這將使時序具有確定性，阻止使用具有相同輸入的多個測量來消除隨機延遲（顯式延遲或由致盲引起的）的任何嘗試。但這可能不是一個好主意：將時序測量與盡可能多的變化輸入相關聯通常是一種更好的攻擊策略，而不是重複更少的測量以使其更精確；只有在對手不能強制重新播種固定的長期隨機對稱密鑰時，時間才是確定性的；如果對手設法提取該密鑰，那麼確定性很可能會變成一場災難，