如果我重新生成密码直到得到我喜欢的密码，那么随机生成的密码的熵会降低多少？

Question

在许多关于众所周知的XKCD #936:短复合密码，还是长字典密码？问题的答案和评论中，强调了随机生成密码的重要性，而不仅仅是编造一个密码。特别是，目前第二高的投票结果在这个问题上说：

随机选择是随机和一致的。这对人类用户来说是很难实现的。你必须说服他们使用一种具有良好随机性的装置(硬币，而不是大脑)，并接受结果。这是我最初回答的要点(转载如下)。如果用户改变选择，如果仅仅通过生成另一个密码，如果他们得到的密码“不讨好他们”，那么他们就偏离了随机均匀性，而熵只能被降低(最大熵是一致的随机性，你不能变得更好，但你可能会变得更糟)。

这让我纳闷:如果我不接受结果，而是生成一个新的随机密码怎么办？这会对最终生成的密码的熵产生多大的影响？

想必，我允许自己拒绝密码的次数越多，最终密码的熵就越有可能降低，例如，我生成了8个密码，并选择了我最喜欢的密码。这能在多大程度上降低我选择的密码的有效熵？(也许log_2(8) = 3 bits是最坏的情况？)

Answer 1

你的假设是合理的。如果我们反复生成真正随机的密码，并选择我们最喜欢的密码，那么一个很好的假设是，在生成的列表中，它是最简单的。为了简单起见，让我们假设密码是介于1和N之间的数字，包括1和N之间的数字，小的数字是“更简单的”，也就是说:攻击者将按1，2，3，……的顺序尝试这些数字。您选择的“最受欢迎的”密码也是生成的密码中最低的。(你可以想象1对应于"1234"，2对应于“密码”，3对应于"summ3r"，.，1000000对应于"zg_uP%bwG"，.)

单个随机数的期望值为N/2，因此攻击者平均需要N/2尝试。但是最小k个随机数的期望值是N/(k+1)，所以现在攻击者平均只需要N/(k+1)尝试。因此，如果k比N不是很小，攻击者就会得到显著的优势。

Answer 2

拒绝/接受真正随机生成的密码，以及在接受之前拒绝多少次，都不会影响熵，因为熵是逐代独立确定的(就像每次掷硬币都不会影响下一个掷硬币的熵一样)。所有的字符串都有相同的熵，只有计算的上下文才能决定‘主观熵’(这是无关的)。

但是，密码的强度与它的随机性没有直接联系--正如你所建议的--如果你要求从字母和数字中随机排列11个字符，那么你就可以得到password123作为你的第一个随机序列。这完全是随机的，只是不是很强。它将具有与下一代相同的熵。

类似地，虽然熵并不是小或多，但如果你一直生成随机字符串直到你“喜欢”一个字符串，你更有可能选择一个较弱的随机字符串(如果你的“喜好”是基于典型的人类考虑因素，比如记忆、抒情质量或可读性等等)。

所以熵和人的喜好是没有联系的，但是喜欢和密码的强度是最肯定的。

Answer 3

为了让用户拒绝特定的随机词选择，对密码的安全性产生有意义的影响，这些拒绝需要是可预测的。否则，攻击者就无法消除特定的单词或单词配对，并在试图猜测密码时节省时间，这是这种做法对他们有利的主要方式。正如所指出的，一个特定的随机词选择的熵并不比另一个少。

如果我们有数据显示，90%的人不会选择随机生成的包含“渐近”这个词的密码(因为这对他们来说没有意义，或者他们担心拼写错误)，那么攻击者就可以消除所有包含这个单词的潜在密码，或者剥夺他们，以便在猜测过程中最后一次尝试。除去这个单词，就可以消除数亿或数十亿的猜测(取决于用于生成密码的单词字典的大小，以及密码的长度)。

因此，正如您可以想象的那样，能够为整个单词字典收集关于典型用户单词拒绝的数据对于攻击者来说是非常有价值的，因为这可能会使攻击者能够消除通常需要的大量工作来强制执行密码。我不知道任何关于用户接受特定随机词用于密码使用的可预见性的公开研究。

但是有一些关于人们所知道和常用的词汇的数据，这些数据可能与他们在密码中使用这些词的偏好有关。类似的研究也存在于通常出现在密码中的单词上。我也不会感到惊讶的是，有一个或多个情报机构正在保密的关于密码词偏好的未发表的研究。

因此，为了最安全起见，您应该抵制拒绝特定密码的诱惑，因为您可能会陷入攻击者已知的可预测模式。然而，很难量化拒绝偶然的随机密码(而不是其他密码)是否会影响您的安全性，从而超过潜在的可用性好处。