我将插话讨论熵和概率,希望这能帮助你理解。
首先什么是概率?这实际上是统计学家之间的一个悬而未决的问题,但这是频率论者的定义:我们说,如果一个公平的硬币被翻转,它有 0.5 的概率出现正面。但是,如果您掷硬币,您可能会观察到前五个结果都是正面,这看起来不正确。所以,常客说,如果你掷硬币“足够”次,你最终会发现有二分之一的硬币是正面的。
关键是概率并没有说明实际会发生什么。一个高熵密码可以在第一次尝试时通过简单的运气猜到,而不管可能的结果等等。
现在什么是熵?如果您开始说“好吧,这是可能的结果的数量......”您可能在生成一些随机数据的上下文中是正确的,但这是您真正需要了解底层发生了什么的完美示例。
首先,让我们谈谈自我信息。这是一个随机变量(这意味着有许多可能的结果),它随每个结果的概率而变化(然后我们将 -log2(P(X)) 编码为信息的“位”)。所以我们需要为每个结果分配一个概率。
正如其他人所指出的,PIN 选择的一些变化更有可能。所有相同的数字(1111、2222、3333、...)、生日(20XX、19XX)等等。您应该为这些数字分配更高的概率,因为简单地说人们更有可能选择它们并且肯定不会选择随机序列。如何将概率分配给其他数字完全取决于您,并且实际上取决于您对选择引脚的过程了解多少。
现在,熵,或者为了让@codesinchaos 开心,特别是香农熵,是自我信息分布的平均值。给定每个选择的概率,这是自我信息的“最可能”值。这是什么意思?正如当前投票率最高的答案所说,它是衡量选择过程及其好坏的标准,而不是引脚本身。
当您选择 1111、2222、3333 等高概率选项时会发生什么?这些结果给出了非常低的自我信息(-log(P(X)) 对于大概率来说很小,因为我们预计它们会发生),因此删除它们会使分布向右移动,即,将分布的位置移向中心。这将增加其平均值。因此,删除大多数人会以高概率做出的选择实际上会增加熵。
让我们以不同的方式看待熵:如果您要猜测 PIN,您会以什么顺序尝试它们(假设没有锁定)?您肯定会从最有可能的 PIN 开始。熵的意思是,如果你重复这个实验足够多的时间(即试图猜测大量卡片的 PIN,这些卡片的 PIN 是用完全相同的逻辑选择的),那么较低的熵选择会给你,攻击者,更多的成功迅速地。
同样,这仍然是在许多卡片的理论情况下可能发生的问题,而不是因为攻击者运气好而可能发生的问题。
这是您的执行摘要:
- 熵变成什么取决于您如何将概率分配给结果空间。
- 毫无疑问,如果您让人类选择 PIN,他们将选择某些值的概率比其他值高得多。
- 这意味着您不能假设基础分布是均匀的并说“熵==结果数”。
- 如果您取出概率最高的不良选择选项,熵就会上升。
- 熵,就像正确猜测的概率一样,完全没有说明攻击者是否会幸运并正确猜测您的 PIN。它只是说理论上更好的熵会使攻击者更加困难。
现在,为了完善我的答案,让我们看看实际情况。如果我们要与密码、散列函数输出选择或随机数据进行比较,PIN 很糟糕。如果您让攻击者和防御者自由选择 PIN 猜测而没有其他信息,那么 50% 的时间(生日悖论)猜测正确的次数非常低。PIN 会产生糟糕的哈希函数。
然而,人类无法很好地记住 128 位的数据,尤其是在喝醉并试图使用芯片和引脚支付烤肉串时。因此,PIN 是一种务实的妥协,并且以三个猜测为限制,除了攻击者非常幸运之外,您应该是安全的。
TL;DR从您的可能选择中删除更可能的 PIN 选项可以提高您在面对不会随机猜测的攻击者(即大多数攻击者)时的机会。
编辑:我认为这个讨论现在需要一些数学知识。这是我在计算中要假设的:
- 我们使用 4 位 PIN 码
Raesene 链接中的数据是正确的,即:
#1 1234 10.713%
#2 1111 6.016%
#3 0000 1.881%
#4 1212 1.197%
#5 7777 0.745%
#6 1004 0.616%
#7 2000 0.613%
#8 4444 0.526%
#9 2222 0.516%
#10 6969 0.512%
#11 9999 0.451%
#12 3333 0.419%
#13 5555 0.395%
#14 6666 0.391%
#15 1122 0.366%
#16 1313 0.304%
#17 8888 0.303%
#18 4321 0.293%
#19 2001 0.290%
#20 1010 0.285%
- 我还将假设此列表中未提及的任何 PIN 都有相同的机会从剩余的“未分配”概率(上面消耗的总概率为 1)中选择。这几乎肯定是不正确的,但我们只有这么多数据。
为了计算这个,我使用了以下圣人代码:
def shannon_entropy(probabilities):
contributions = [p * (-1*log(p,2)) for p in probabilities]
return sum(contributions)
计算给定概率集的实际香农熵。
import itertools
total_outcomes = 10.0^4
probability_random_outcome = 1 / total_outcomes
probability_random_outcome
maximum_entropy = -log(probability_random_outcome, 2)
maximum_entropy
maximum_entropy_probability_list = list(itertools.repeat(probability_random_outcome, total_outcomes))
maximum_entropy_calculated = shannon_entropy(maximum_entropy_probability_list)
print(maximum_entropy)
print(maximum_entropy_calculated)
演示我的函数通过列出 10^4 个概率(每个概率为 1/10^4)来准确计算最大熵。
然后
probability_list_one = [10.713/100, 6.016/100, 1.881/100, 1.197/100, 0.745/100, 0.616/100, 0.613/100, 0.526/100,0.516/100, 0.512/100, 0.451/100, 0.419/100, 0.395/100, 0.391/100, 0.366/100, 0.304/100, 0.303/100,0.293/100,0.290/100,0.285/100]
outcome_count_one = 10^4 - len(probability_list_one)
print("Outcome count 1:", outcome_count_one)
probability_consumed_one = sum(probability_list_one)
print("Probability consumed by list: ", probability_consumed_one)
probability_ro_one = (1-probability_consumed_one)/outcome_count_one
entropy_probability_list_one = probability_list_one + list(itertools.repeat(probability_ro_one, outcome_count_one))
entropy_one = shannon_entropy(entropy_probability_list_one)
entropy_one
在这里,正如我上面所说的,我采用这 20 个概率并假设其余概率均匀分布在其余结果之间,方法是扩展列表,每个概率设置均匀。执行计算。
probability_list_two = [6.016/100, 1.881/100, 1.197/100, 0.745/100, 0.616/100, 0.613/100, 0.526/100,0.516/100, 0.512/100, 0.451/100, 0.419/100, 0.395/100, 0.391/100, 0.366/100, 0.304/100, 0.303/100,0.293/100,0.290/100,0.285/100]
outcome_count_two = 10^4 - len(probability_list_two)-1
print("Outcome count 2:", outcome_count_two)
probability_consumed_two = sum(probability_list_two)
print("Probability consumed by list: ", probability_consumed_two)
probability_ro_two = (1-probability_consumed_two)/outcome_count_two
entropy_probability_list_two = probability_list_two + (list(itertools.repeat(probability_ro_two, outcome_count_two)))
entropy_two = shannon_entropy(entropy_probability_list_two)
entropy_two
在这种情况下,我删除了最有可能的 PIN 码 1111 并重新计算熵。
从这些结果中,您可以看到随机选择一个 PIN 具有 13.2877 位的熵。重复这个实验,去掉一个 PIN 给我们 13.2876 位
在给定这 20 个 PIN 的选择概率的情况下选择一个 PIN,否则随机选择意味着您在可能的 13.2877 位中选择 11.40 位的熵。在此基础上,阻止 PIN 1111 并以其他方式允许其余 19 个明显的 PIN 和以相同概率选择的所有其他 PIN 具有 12.33 位的熵,在可能的 13.2876 位中。
我希望这可以解释为什么许多答案都说熵正在下降,而不是上升。他们正在考虑最大可能的熵,而不是考虑到选择的可能性的系统的平均熵(香农熵)。更好的衡量标准是香农熵,因为它考虑了每个选择总体上做出的概率以及攻击者可能如何进行攻击。
如您所见,阻止 PIN 1111 显着增加了香农熵,但对整体可能的熵有轻微的损失。如果您想讨论熵,基本上,删除 PIN 1111 会大有帮助。
作为参考,XKCD 漫画计算了大约 28 位的差密码的熵和更高的 44 位密码的熵。同样,这取决于对某些选择的概率所做的假设,但这也应该表明 PIN 在熵方面很糟糕,小 N 的 N 次尝试限制是唯一合理的方法。
公共圣人工作表