給定熵的密碼認證的邊界安全性
對手 Craig 試圖以 Alice 的身份登錄系統，該系統只接受正確的密碼，（僅）在嘗試成功時洩漏，並允許多次嘗試。
愛麗絲的密碼選擇被建模為有限集合中的隨機選擇 $ m $ 可能的密碼 $ P_i $ 每個都有機率 $ p_i $ ， 和 $ 0\le i<j<m\implies p_i\ge p_j>0 $ ， 和 $ 1=\displaystyle\sum_{0\le i<k}p_i $ .
假設克雷格有一個愛麗絲密碼選擇的完美模型，並嘗試 $ n $ 密碼 $ P_i $ 通過增加 $ i $ （和 $ 0\le n\le m $ )，如果他登錄就停止。克雷格的成功是有可能的 $ q_n=\displaystyle\sum_{0\le i<n}p_i $ .
我們知道 $ n $ , $ m $ ，以及密碼分佈的香農熵 $ H=\displaystyle-\sum_{0\le i<m}p_i\cdot\log_2(p_i) $ . 為了均勻分佈 $ p_i $ ，我們會有 $ q_n=n/m=n/2^H $ . 但是我們不知道說分佈。
我們怎樣才能嚴格、嚴密地約束克雷格的成功機率 $ q_n $ ?
澄清：是問上下界 $ q_n $ 作為一個函式 $ (n,m,H) $ .
如果我們另外有最小熵怎麼辦 $ H_\text{min}=-\log_2(p_0) $ 或其他一些有趣的機率分佈度量？
現在有 $ u $ 使用者 Alice、Bob ..（我們假設）彼此獨立地選擇了他們的密碼，但分佈相同。克雷格知道使用者登錄，並嘗試 $ P_i $ 在移動到之前為每個使用者 $ P_{i+1} $ . 當他登錄任何使用者的帳戶時，他停止了，或者已經 $ n $ 嘗試，與 $ 0\le n\le (m-1)\cdot u+1 $ .
界限會變成什麼？
建議數值說明：for $ n=1000 $ 在……之外 $ m=2^{48} $ , $ H=20 $ -位熵，我們可以得到什麼界限 $ q_n $ ? 如果我們另外假設 $ H_\text{min}=12 $ ? 或與 $ u=2^{10} $ ?
密碼選擇的實際分佈是否傾向於讓我們收緊界限？
優化攻擊者的成功機率受約束 $ H $ 和密碼數量
讓我們稍微調整一下符號以使其不那麼麻煩：對手嘗試的密碼具有機率 $ p_i $ 為了 $ 0 \leq i < n $ ，並且對手沒有嘗試的密碼有機率 $ q_j $ 為了 $ 0 \leq j < m $ . 對手以機率成功 $ \sum_i p_i $ .
我們尋求一個極點 $ f = \sum_i p_i $ 在零點之間 $ g $ 和 $ h $ 在哪裡 $$ \begin{align*} g &= H + \sum_i p_i \log p_i + \sum_j q_j \log q_j, &&\text{entropy constraint;} \ h &= 1 - \sum_i p_i - \sum_j q_j, &&\text{total probability constraint.} \end{align*} $$ 這些極值點是$$ d(f - \lambda g - \mu h) = df - g,d\lambda - \lambda,dg - h,d\mu - \mu,dh $$對於拉格朗日乘數 $ \lambda $ 和 $ \mu $ . 自從$$ d(x\log x) = \log x,dx + x\cdot(1/x),dx = (1 + \log x),dx, $$我們有 $$ \begin{align*} df &= \sum_i dp_i, \ \lambda,dg &= \lambda,dH + \sum_i \lambda (1 + \log p_i),dp_i + \sum_j \lambda (1 + \log q_j),dq_j, \ \mu,dh &= -\sum_i \mu,dp_i - \sum_j \mu,dq_j. \end{align*} $$ 因此，如果 $ dH = 0 $ 儘管 $ dp_i $ 和 $ dq_j $ 非零（我們持有 $ H $ 固定但允許機率變化），我們從 $ 0 = d(f - \lambda g - \mu h) $ 方程組 $$ \begin{align*} 0 &= 1 - \lambda (1 + \log p_i) + \mu, \ 0 &= -\lambda (1 + \log q_j) + \mu, \end{align*} $$ 並從 $ g,d\lambda = 0 $ 和 $ h,d\mu = 0 $ 我們像以前一樣得到熵和總機率約束。自從 $ \log $ 是單射的，這個系統意味著 $ p_i $ 都是平等的，並且 $ q_j $ 都是平等的；呼叫共同價值觀 $ p/n $ 和 $ q/m $ ， 分別。從總機率約束，我們有 $ p = 1 - q $ . 熵約束減少到$$ H = -p \log (p/n) - (1 - p) \log [(1 - p)/m]. $$ 對手的成功機率 $ p $ 必須通過分佈到第一個的最小/最大均勻機率質量來優化 $ n $ 與此熵約束一致的密碼。 有兩種解決方案，因為 $ H $ 正在增加 $ p < n/(n + m) $ 並減少 $ p > n/(n + m) $ ，對應於攻擊者的最小和最大成功機率。
反相 $ H $ 很棘手，但我們可以在這種情況下近似它而不會太麻煩。讓 $ n = 1000 $ 和 $ m = 2^{48} - 1000 $ 就像問題一樣。對於最小值 $ p < n/(n + m) = 1000/2^{48} $ ，我們可以使用近似 $ \log (1 - p) \approx 0 $ ， 以便 $$ \begin{align*} H &= -p \log (p/n) - (1 - p) \log [(1 - p)/m] \ &\approx -p \log (p/n) + (1 - p) \log m \ &= \log m - p \log (p/n) - p \log m \ &= \log m - p \log (p m/n). \end{align*} $$ 為了解決這個問題，讓 $ W(x e^x) = x $ 是蘭伯特的 W 函式。認為 $ y = x \log (a x) $ ; 然後 $ e^y = e^{x \log (a x)} = a x e^x $ ， 以便 $ e^y/a = x e^x $ ， 從中 $ x = W(x e^x) = W(e^y/a) $ . 因此，由於 $ \log m - H \approx p \log (p m/n) $ , 我們可以恢復 $ p \approx W(e^{\log m - H}/(m/n)) = W(e^{-H} n) $ . 為了 $ H = 20 \log 2 $ 以便 $ e^{-H} = 2^{-20} $ ，我們得到$$ p \approx W(2^{-20} \cdot 1000) \approx 0.000952766 > 2^{-11}. $$ 對於最大值 $ p > n/(n + m) $ ，我們可以對減函式使用二分法 $ H $ （在更適合簡單數值計算的範圍內）找到$$ p \approx 0.757204 < 4/5. $$ 因此，$$ 2^{-11} < p < 4/5. $$
多使用者設置
假設 Alice、Bob等都使用相同的密碼分佈。如果有 $ u $ 使用者，攻擊者成功破壞至少一個的機率 $ u $ 使用者與 $ i^{\mathit{th}} $ 密碼由 $ \hat p_i = 1 - (1 - p_i)^u $ . 這是每個使用者選擇除密碼以外的密碼的機率的補充 $ P_i $ . 對手嘗試第一次後的成功機率 $ n $ 密碼是 $ \hat p = 1 - (1 - \sum_i p_i)^u $ . 為了優化這一點，我們只需替換目標 $ f $ 在上述程序中 $ f’ = 1 - (1 - \sum_i p_i)^u $ . 我們得到修改後的方程組 $$ \begin{align*} 0 &= u \bigl(1 - \sum\nolimits_\iota p_\iota\bigr)^{u-1} - \lambda (1 + \log p_i) + \mu, \ 0 &= -\lambda (1 + \log q_j) + \mu, \end{align*} $$ 據我所知，這不會改變極值點，只會改變對手在這些點上的成功機率值。認為 $ u = 2^{10} $ ; 然後因為 $ 2^{-11} < p < 4/5 $ , $$ \begin{gather*} 1 - (1 - 1/2^{11})^{2^{11}} \approx 1 - e^{-1} \approx 0.63212 \ 1 - (1 - 4/5)^u = 1 - (1/5)^{2^{10}} \approx 1, \end{gather*} $$ 所以我們有$$ 1/2 < \hat p < 1. $$ 也就是說，對手在多目標攻擊中猜測一千個密碼的成功機率 $ 2^{48} $ 對於一千個使用者中的任何一個，使用 20 位熵的可能性保證比公平的拋硬幣正面朝上要好，並且可能基本上是 1。 請注意，這種多目標攻擊仍然需要花費 $ n\cdot u $ 查詢，就像單目標攻擊成本一樣 $ n $ 查詢（除非密碼數據庫設計得非常糟糕）。在這種情況下，它的成本 $ 2^{20} \approx 10^6 $ 查詢。
附錄：如果密碼的數量是無限的，那麼熵對於任何成功機率都是無限的，無論多麼接近 1
使固定 $ 0 < \varepsilon < 1 $ . 讓 $ p_0 = 1 - \varepsilon $ 和 $ p_i = \varepsilon/m $ 為了 $ i = 1, 2, \ldots, m $ . 該分佈的香農熵為 $$ \begin{align*} H &= -(1 - \varepsilon)\log(1 - \varepsilon) - \sum_{i=1}^m (\varepsilon/m) \log(\varepsilon/m) \ &= -(1 - \varepsilon)\log(1 - \varepsilon) - \varepsilon \log (\varepsilon/m) \ &= -(1 - \varepsilon)\log(1 - \varepsilon) - \varepsilon \log \varepsilon + \varepsilon \log m. \end{align*} $$ 如果 $ \log m $ 上面是無限的，所以是 $ H $ .
對手一次猜測成功的機會，嘗試第一個密碼的機率 $ p_0 $ ， 是 $ 1 - \varepsilon $ ，可以任意接近1，而整個分佈的香農熵任意高，通過添加除第一個以外的更多等機率密碼。
這個反例表明，對於任何香農熵，第一次嘗試後的成功機率可以任意接近 1。另一方面，該分佈的最小熵為 $ -\log (1 - \varepsilon) $ ，無論有多少其他選擇。
一般來說，如果密碼分佈的最小熵是 $ H_\infty $ ，那麼單次猜測成功的最佳機會是 $ e^{-H_\infty} $ . 如果假設它不是第一個密碼分佈的最小熵是 $ H’\infty $ ，在第一次猜測之後，一次猜測成功的最佳機會是 $ e^{-H’\infty} $ ，所以兩次試驗後成功的最佳機率是$$ \Pr[T_0] + \Pr[T_1 \mathrel| \neg T_0] \Pr[\neg T_0] = e^{-H_\infty} + e^{-H’\infty} (1 - e^{H\infty}) $$等等，在哪裡 $ T_0 $ 意味著第一次嘗試後成功， $ T_1 $ 意味著第二次之後的成功，等等。 在統一的情況下，這會減少為人們可能期望的超幾何分佈。