客戶謎題和 HMAC

我正在學習有關 DoS（拒絕服務）保護的客戶端難題，我遇到了這個問題。

對於每個請求，伺服器向客戶端發送一個新生成的隨機挑戰 r 和一個難度參數 n，客戶端必須生成一個解決方案 s，使得具有密鑰 r 的 HMAC(s) 以 n 個零位結束。”

客戶端計算解決方案和伺服器檢查解決方案的預期 HMAC 計算次數是多少？

我知道伺服器只需要計算 1 個 HMAC，因為它有 s、r 和 n。因此，它只需要客戶端解決方案 s，併計算所需的 HMAC，並查看它最後是否具有所需數量的零位。

我將如何計算客戶的答案？我假設客戶端必須強制使用它，所以他會繼續計算 HMAC，直到最後得到所需的 n 個零位。我該如何做這個計算？

這是一個小方案，它是如何工作的：

Server         Client
  |              |
  |     r,n      |  S: Find s such as HMAC(s,r) = xxxx0000
  |  ==========> |   
  |              |  C: *compute HMAC(0,r) = 123456789*
  |              |  C: *compute HMAC(1,r) = 124687946*
  |              |  C: *compute HMAC(2,r) = 164946518*
  |              |  C: *compute HMAC(3,r) = 165498451*
  |              |  ...
  |              |  C: *compute HMAC(42,r) = 16540000*
  |              |  
  |    s = 42    |  C: Found it ! s is 42
  | <=========== | 
  |              |  S: *compute HMAC(42,r) = 16540000*
  |      OK      |  S: Ok, access granted for you !
  |  ==========> |   
  V              V  

例如，假設您只希望最後一位數字為 0。如果您要計算隨機數的 HMAC 的機會是多少？出色地 $ \frac{1}{10} $ . 所以如果你嘗試 10 個隨機數，你得到至少一個以 0 結尾的 HMAC 的機會是相當不錯的：

$ P = 1 - ((1-\frac{1}{10})^{10}) \approx 65% $ .

然而，你最後問的 0 越多，就越難找到解決方案。例如，如果你在最後要求 4 個零，你會找到的機會 $ s $ 經過 1000 次試驗後：

$ P = 1 - ((1-\frac{1}{10000})^{1000}) \approx 9,5% $ .

經過 10000 次試驗：

$ P = 1 - ((1-\frac{1}{10000})^{10000}) \approx 63% $ .

因此，僅僅通過增加所需的零的數量，您就可以大大增加找到解決方案所需的時間。

為什麼它是“安全的”，因為你改變了 $ r $ 在每一個試探性的。因此，客戶端無法預先計算解決方案。

引用自：https://crypto.stackexchange.com/questions/33580