理想的密码模型是什么？

#1 楼

当密码学家创建算法时，他们通常会提出一些论点，认为算法是安全的。他们需要以一些假设开始争论。例如，在公钥密码学中，它们可能首先假设很难分解大数。

许多算法都使用块密码作为构建块。这些算法安全的论点需要对所讨论的分组密码进行一些（数学）假设，以便开始使用。通常，这种假设是这样的：“如果随机选择加密密钥，那么即使使用选择明文攻击，不知道密钥的攻击者也无法区分分组密码和真正的随机排列。” （这是对伪随机置换[PRP]假设的非正式陈述。）

但是PRP假设并不总是适用。有时，以分组密码不是随机密钥或非秘密密钥的方式使用分组密码（稍后我们将看到一个示例）。在这种情况下，我们需要对分组密码的安全性做出其他一些假设。

什么是理想密码模型？在理想的密码模型中，我们只是假设分组密码是每个密钥的随机排列。此外，我们将这些排列视为独立的。我们假设，如果攻击者想知道使用给定密钥对块进行加密时会发生什么，那么他必须亲自进行计算。他无法通过加密其他块或使用不同密钥的同一块来推断有关输出的任何信息。 （例外：给定一个固定密钥，没有两个输入将产生相同的输出。因此攻击者可以排除这种可能性，仅此而已。）

示例：Davies-Meyer压缩功能。一些哈希函数（例如MD5，SHA-1和SHA-2）是Merkle-Damgard构造的示例。假设我们想找到一个论点，即Merkle-Damgard构造具有抗碰撞性。它们看起来像这样（IV是一个常数，而Hash是输出）：上面的函数$ f $是压缩函数。

现在，可以证明如果$ f $是安全的，则哈希函数也是如此。但是我们可以使用理想的密码模型进行更深入的研究。对于MD5，SHA-1和SHA-2，$ f $是使用所谓的Davies-Meyer构造从块密码$ E $中构建的（这三个哈希函数均使用不同的块密码）： />
$ f（\ mathrm {M}，H）= E_ {M}（H）\ oplus H，$

其中$ M $是消息块，而$ H $是其他输入（链接值）。因此，$ M $被用作密钥，但是如果有人试图为MD5查找冲突，则每个消息块$ M $都在他的控制之下。它既不是随机的也不是秘密的。因此我们不能使用PRP假设。

但是我们可以将$ E $建模为理想密码。使用这种假设，例如，我们可以证明，如果不做大量工作（或者变得非常非常幸运），就找不到MD5或SHA2的冲突。我们可以找到MD5的冲突！那么出了什么问题？好吧，理想的密码模型只是一种启发式方法。分组密码必须使用简单的算法来描述---我们无法生成和存储列出每个密钥下的每个输出的随机表，这些表将非常庞大。这不可避免地在不同的输出和不同的键之间存在某种数学关系。

什么时候使用理想的密码模型？因为理想的密码模型是对分组密码进行建模的一种启发式方法，而不是从技术意义上看似真实的假设，因此应尽可能避免使用。但是有时，尤其是在没有随机密钥的哈希函数中，这是我们唯一的选择。

我如何知道何时可以使用理想密码模型对分组密码进行合理建模？最好询问是否以要求理想密码模型的方式（与PRP假设相反）使用分组密码。接下来，查看如何使用分组密码。例如，在MD5和SHA1，SHA2中，分组密码被埋在压缩功能内部，攻击者无法完全控制对此功能的输入。由于攻击者距离实际的分组密码只有几步之遥，因此使用理想的密码模型变得更加合理，因为攻击者可能很难利用分组密码的弱点。最终，最好的测试是时间的考验。

话虽如此，但事实证明，构造分组密码的某些常见方法会导致与理想密码不可区分的构造...但是这些证明对分组密码的内部进行启发式假设。因此，尽管从学术角度来看这些证明很有趣，但尚不清楚它们对理想密码模型中信任现实世界分组密码有多大贡献。

#2 楼

具有$ k $位密钥和$ b $位块大小的理想密码是由集合$ \ {0索引的集合$ \ {0,1 \} ^ b $的$ 2 ^ k $排列族， 1 \} ^ k $，从所有这些排列族的集合中随机选择。参见例如http://eprint.iacr.org/2005/210.pdf。

IC模型主要用于证明，您需要假设对手仅凭以下知识而无法获得显着优势-甚至选择-$ k $位字符串$ K $。或者换句话说，当您需要一个可以随机且不可预测地运行的组件时，即使对手知道/控制了所有输入，该组件也很有用。为了说明这一点，请考虑DES（绝对不理想的密码），它具有互补性质，其中$ E_ {K}（P）= E_ {K ^ C}（P ^ C）$的概率为1（$ X ^ C $是$ X $的补数）。将其与理想密码进行对比，其中$ E_ {K}（P）$和$ E_ {K ^ C}（P ^ C）$都是独立且一致的随机值，它们仅以概率$ \ frac { 1} {2 ^ b} $。

当试图证明实际的分组密码或密码系统的机密性时，IC模型并不是特别有用（假设没有真实的密码曾经希望满足），IC模型太强了。但这（据称）对于建模块密码的其他属性（如抗碰撞性或图像前抗性）很有用。

#3 楼

点1到3的部分答案...

理想密码模型描述了一个近似于随机预言但具有固定输入大小的键置换。
具有块大小的理想密码$ B $位和密钥大小$ N $位应显示以下属性：给定任何单个密钥$ K $，所有$ 2 ^ B $纯文本的密文分布在统计上是随机的
给定任何单个密钥$ K $，所有$ 2 ^ B $纯文本都会有$ 2 ^ N $个唯一密文
给定任何单个明文$ P $，可能出现密文的可能性对于所有$ 2 ^ N $密钥，其值应为$ 1 / {2 ^ N} $，从而使密码的行为类似于具有固定$ P $的随机函数。对于不知道密钥的人而言，从给定的密文中获取密码至少应像穷举密钥搜索器一样困难。
从给定的明文/密文组合中查找匹配密钥的工作量对于不知道密钥的人来说，离子至少应该像穷举密钥搜索一样困难。

给定任何单个纯文本$ P $，所有密钥都有$ 2 ^ N $密文，并且如果$ N = B $，所有密文都不应区分。密文的选择应模拟随机函数。这可能没有道理，但是如果它们是不同的，则密码将不会近似为随机预言。这可以使用$ B $很小的示例来显示：

具有2位块和2位密钥，以下2个表由所有可能的输入$ P $和输出$构成所有密钥的C $：

    P0 P1 P2 P3
K0  2  0  3  1 
K1  3  0  1  2
K2  1  2  3  0
K3  2  3  0  1

    P0 P1 P2 P3
K0  2  3  1  0
K1  3  1  0  2
K2  0  2  3  1
K3  1  0  2  3

    P0 P1 P2 P3
K0  2  0  3  1
K1  3  0  1  2
K2  1  2  3  0
K3  0  3  2  1

表1展示了其中的明文不会在任何键下对其自身进行加密的属性。
表2展示了其中的明文纯文本将对每个密钥具有唯一的密文。
表3既不显示表1的属性，也不显示表2的属性。
在所有表中，没有等效的密钥，对于$ P $的所有值，在$ C = P $的情况下也没有密钥。在第一个表中，1的概率为任何具有$ P1 $的键都是0.0。
在第二张表中，如果$ K2 $和$ K3 $的值尚未为1，则$ P0 $和$ K3 $的密文的概率为0.5。确定，而不是预期的0.25。
因此，无法满足属性3，因为具有固定$ P $的密码不再像随机函数那样工作。实际上，出于显而易见的原因，表1示例可能不是一件坏事。

前三个属性使理想密码成为伪随机排列。
所有分组密码都必须表现出属性2以便使密文可逆转换为纯文本

我不认为我有足够的能力回答点4或5，但是理想的密文模型用于围绕分组密文构建密码结构被认为是安全的，然后使用密码的密钥和块大小从模型中推断出结构的安全性。
唯一的方法来判断密码是否表现出理想的行为是蛮力，对于
这是除了密码本身被证明可以抵抗所有已知攻击之外，其工作负载至少与穷举密钥搜索一样困难。
即使对于小型密码， ，例如12位和24位密钥，则保存所有输出需要96 GiB数据ts，然后需要测试分布的理想随机性。 24位块和48位密钥将需要12 ZiB的数据进行分析，据我所知，这是目前地球上任何一个高密度存储集群所不能容纳的。位是$ B * 2 ^ {N + B} $，对于现代密码（例如AES）的密钥和块大小，最小值为$ 2 ^ {263} $，最大值则远远超过宇宙中的原子数。