Signature

Lamport簽名:偽造一個簽名需要多少個簽名?

  • December 5, 2014

Lamport signature :對消息進行簽名請注意,現在 Alice 的私鑰已被使用,並且不應再次使用。其他 256 個未用於簽名的隨機數,她絕不能發布或使用。最好她應該刪除它們;否則,其他獲得訪問權限的人稍後將能夠創建虛假簽名。

如果 Lamport 的簽名方案被錯誤地使用,就說你會多次使用它。您需要多少個不同消息的簽名才能偽造簽名?

我在想如果你有一個簽名,然後是“相反”消息(不是真正的消息,而是消息的雜湊和),所以第一條消息中的每個 0 都是 1,1 是 0。如果你有這兩個簽名,你會有愛麗絲私鑰所需的一切。

但是,認為你得到這兩條消息可能是不現實的。對於您需要多少個簽名,是否有一些通用公式?

謝謝!

如果消息是隨機的,則每個附加簽名都會使安全級別減半。如果攻擊者選擇了消息,則兩個簽名(每個位不同的消息)足以完全中斷。

大約 64 位的安全級別可以被堅定的攻擊者破解,而 32 位的安全級別可以在一台家用電腦上輕鬆破解。

所以如果你使用 256 對,這是一個合理的水平,因為它提供了 256 位的安全性來防止第二原像攻擊,而 128 位來防止衝突,一旦你使用相同的密鑰 3 次就可以進行實際攻擊,而且查找消息很簡單-簽名配對一次使用四次。

注意此時攻擊者並不能完全確定他要簽名的消息,他需要嘗試 $ 2^{64} $ (三個簽名後)或 $ 2^{32} $ (四次簽名後)不同的消息,以找到他可以簽名的消息。這對攻擊者來說通常不是問題,因為他可能想要簽署的許多東西都有攻擊者可以自由選擇的部分。

為什麼每次簽名後減半?

當您觀察單個簽名時,您會知道每一對中的一個雜湊值。因此,要創建簽名,您需要有一個與簽名的每一位匹配的消息雜湊。

當您觀察兩個簽名時,您會知道一半對的兩個散列,而另一半只知道一個散列。所以消息雜湊只需要匹配你只知道一個的那一半。

當您觀察三個簽名時,您會知道 3/4 對中的兩個雜湊值,並且僅知道剩餘 1/4 中的一個雜湊值。現在您只需要匹配原始位的 1/4。

等等

引用自:https://crypto.stackexchange.com/questions/2640