确保对未来事件的预测

信息安全 加密 密码学 哈希
2021-09-05 12:41:11

我想对未来事件做出预测,但只在事件发生后揭示预测,以免我的预测知识影响结果。

例如,假设 Alice 预测 Bob 将在 4 月 24 日上午 9:17 喝掉他那杯溢出的牛奶。她写入一个文本文件:

Bob spills his glass of milk on April 24th at 9:17 AM.

Alice 不希望 Bob在事件发生之前知道预测的细节,否则 Bob 可能会在当天避免牛奶,以防止 Alice 预测的结果。但是,如果只翘揭示了预测之后该事件已经发生,Bob可以声称爱丽丝制造的预测后,已经发生的事件。

当然,Alice 应该在事件发生前向 Bob 提供一些关于她的预测真实性的验证——这种验证在事件发生之前不会透露预测的细节,但可以确认预测是在事件发生之前做出的。

我想出了两种可能的验证方法:

  1. 加密
    • Alice 对文本文件应用对称密钥加密算法(例如 AES)
    • 爱丽丝向鲍勃提供加密文件
    • 事件发生后,Alice 向 Bob 提供秘密密码
    • Bob 解密加密文件并读取预测
  2. 散列
    • Alice 对文本文件应用散列算法(例如 SHA-256)
    • Alice 向 Bob 提供计算的哈希值
    • 事件发生后,Alice 向 Bob 提供原始文本文件
    • Bob 对文本文件应用相同的散列算法并验证散列

哪种验证方法最安全(即理论上 Bob 更难克服并因此在事件发生之前发现预测)?

哪种验证方法最实用(例如,哈希占用的空间比加密文件小得多)?

1个回答

加密不提供您需要的功能;至少不是直接的。作为一个极端情况,考虑一次性密文:密钥与要加密的数据一样长,并且加密是通过逐位异或完成的:给定密钥K和明文P,密文是C = P XOR K假设您使用 OTP 进行加密;您预测了P并发布了加密版本C后来,预测结果是错误的;Bob 不会洒牛奶而是洒(早上 9 点 17 分,真可惜!)。你现在想表现得好像你一直都在正确地预测它;因此,你想要密文C解密为P',而不是P(注意P'与P具有相同的长度)。这很简单:计算密钥K' = C XOR P'并将K'发布为您使用的密钥。您可以验证C确实是P'K'加密的结果。

因此,使用 OTP,您可以在事后伪造初始消息。正是这一特性使 OTP 成为理论上牢不可破的加密系统:对于给定的密文,每个可能的明文都是可能的(具有相同的概率)。

因此,如果您使用另一个加密系统(例如,一些 AES),那么这可能会提供您正在寻找的那种承诺,只是因为加密系统不完善。这看起来不像是一个良好的安全基础:它必须是好的,但不能太好。

散列是一个更好的选择。将预测P散列为H = SHA-256( P ),然后发布散列值。稍后,揭示P:每个人都可以对揭示的P进行哈希处理,并查看它是否与之前发布的哈希值H匹配。只要散列函数是抗冲突的,这是安全的,即只要您不能创建两个散列到相同值的预测PP'(因为否则您可以选择揭示发生的那个)。

作为旁注,该出版物可以采用多种形式。考虑可信时间戳:这是一种公共的承诺方法。Time Stamping Authority (TSA) 接收一个散列值,将其封装在一个结构中,该结构还包含当前日期和时间(如 TSA 所知),并对该结构进行签名。实际上,TSA 通过其签名(以可验证的方式)说:“哈希值H是在日期T或更早发布的,因为我在日期T看到了它”。在非计算机世界中,这样的工作是使用Soleau 信封完成的

哈希值有一个缺点:它可能允许某人尝试暴力预测。给定哈希值H,可以尝试可能的预测P并将它们全部哈希,直到找到匹配项,从而在预测出现之前重建预测。例如,可以知道您预测某天某天会溢出一些饮料,并尝试所有饮料和日期的组合。由于散列可以以每秒数十亿条消息的速度进行(使用良好的 GPU),一些结构化预测可能会被提前泄露。为了防止这种攻击,请在末尾添加随机填充:

Bob spills his glass of milk on April 24th at 9:17 AM, and
here is random padding:sef9yb94bo3qr7yqwnc67sb32

确保每次进行预测时都使用新的随机字符(不要重复使用它们!)。请注意,可以构建一个人为的散列函数示例,该示例是“安全的”,因为它不允许计算冲突,但仍然无法隐藏预测值;然而,这将是一个人为的例子。使用 SHA-256,只要添加足够多的随机填充(随机字符将添加 5 或 6 位熵;在 80 位时,敌人完全被击败,因此 16 个字符就足够了),随机填充就可以完成工作。该方法的一个缺点是您必须将完整的输入字符串(即填充预测)与随机字符一起保存。如果您打算将其保留在脑海中,这可能会很麻烦。