乐高的推理：思考密码学的错误方式

代码很糟糕，密码设计也有缺陷，但像往常一样，我们可以从这个博客中学到一些东西。让我们忽略以下事实：它使用的是MCRYPT_RIJNDAEL_256(Rijndael的256位块版本，而不是AES)，而不是MCRYPT_RIJNDAEL_128(真正的AES)；它不检查substr()的返回值；它将十六进制编码的密钥传递给需要二进制字符串的函数。我以前已经在这个博客上报道过所有这些失败的地方，所以我不会再触及它们了。

相反，让我们关注两个事实。首先，它正在进行“MAC然后加密”(MTA)，这意味着在加密之前将消息认证码(MAC)应用于明文消息-这与现代密码智慧相反。其次，通过非时序安全比较来检查MAC，这意味着如果攻击者能够获得失败解密的真正精确的时序测量，他们就可以找出有多少MAC匹配。在“Encrypt Then MAC”(ETM)设计中，MAC在加密后应用于密文，这种定时泄漏通常会让您伪造消息。但这一次，MAC是在密文中加密的，所以乍一看，利用它似乎更困难。

事实上，这个问题是在该页面的评论部分提出的。代码的作者回应如下：

我曾编写代码对MAC进行恒定时间的文本比较，但后来意识到在使用MAC-Then-Encrypt方法时这不是问题，因为只有在解密之后才会比较MAC，以验证数据是否完整且与加密时相同。因为只有在使用正确的加密密钥时才会暴露正确的MAC，所以文本比较是否以固定时间进行并不重要。更改为Encrypt-Then-MAC方法(需要恒定时间MAC比较)不会向后兼容当前版本。

让我们遵循这句话的逻辑。在广泛的层面上，他们声称时间攻击无关紧要，因为MAC在加密内部。他们提出这一要求的理由是什么？有两种方式来解释所写的内容，这取决于您将“正确的MAC”理解为什么意思。

在一种解释中，“正确的MAC”指的是存储在消息中的MAC，他们说您需要密钥才能访问它，因此即使您可以使用计时通道通过旋转“正确的MAC”来匹配计算出的MAC，您也无法实际了解它是什么。这一推理是有缺陷的，因为要创建伪造，您并不总是需要知道MAC值，您只需要生成一些解密机器可以接受的新密文。或者，它们可能意味着即使您知道计算出的MAC值，也不能在不知道加密密钥的情况下将其放入明文消息中。这假设加密本身提供了某种完整性保护。很可能是这样，但需要更严格的论据来证明它的合理性。

在另一种解释中，“正确的MAC”指的是从解密后的明文消息计算出的MAC。这种解读很难正面解读。确实，它只有在使用正确的密钥解密后才会公开，但是代码中的侧通道在解密之后就会立即泄露有关它的信息！

这两种读物可能都不是作者的真正意思，但我正试图用最好的方式来解释他们的话。

稍后我将告诉您如何攻击此代码，存在攻击的事实表明作者的推理肯定是不可靠的。那么，为什么要花这么多话来分析这个论点呢？因为这是一个非常常见的错误的例子，我称之为乐高推理。

当设计师或开发人员将密码学理解为堆叠在一起的乐高积木时，乐高推理就会发生。蓝色块(MAC)位于红色块(加密)之上，因此蓝色块不会倒下。教科书以电路图的形式展示密码学算法，这些电路图将密码和散列等基元与密钥和明文等数据连接在一起。这导致了一种观点，即密码算法应该被认为是连接在一起的简单组件。

乐高的观点没有错。这是在编写代码时考虑密码算法的一种直观方式。但这是对密码安全性的错误思考。要谈论算法的安全性，您需要将整个系统作为一个整体来考虑。在你的家里，你可以安全地把一个旧的白炽灯泡换成一个更节能的紧凑型荧光灯，而不用担心它会导致你的微波炉爆炸。密码学则不同。对算法的一部分做一个小小的更改就可以完全破坏其他看似无关的部分。仅仅因为电路图中的部件在空间上是分开的，并不意味着它们不会相互影响。你需要着眼于大局。

专业的密码学家就是这么做的。而不是自下而上的推理，像这样说：“绿色的乐高积木和红色的乐高积木是这样连接的，所以上面的蓝色乐高积木不会倒下。”他们采取了自上而下的方法，更接近于，“让我们假设这个乐高结构以任何方式破裂。唯一可能的方法(省略了严格的证明细节)是如果绿色的乐高积木一分为二。我们假设个别乐高积木不会破裂，那么整个结构就不会破裂。“。

在密码学术语中，我们首先假设系统容易受到特定类型的对手的攻击。通常，我们会给对手尽可能多的权力。我们让他们加密选定的明文，甚至解密选定的密文。然后，我们证明了这样一种说法：“如果该对手可以破坏整个系统(整个乐高结构)，那么他们就可以在散列函数(不可摧毁的乐高积木块)中找到冲突。”这种推理让我们正式地证明，如果我们使用的密码原语(密码、散列函数、MAC)是安全的，那么整个系统就是安全的。这是对密码学中的安全性进行推理的正确方式。

我个人发现，自上而下的思维模式也是破解糟糕密码的好方法。如果您想破解某些密码，首先根据严格的安全正式定义(IND-CPA、IND-CCA2等)找出表明它不安全的攻击。安全的正式定义是如此严格，以至于您发现的攻击可能根本没有任何实际意义。接下来，抓住这个弱点，想办法把它变成实际相关的攻击。对我来说，这几乎每次都有效。

好的，我之前向您承诺过，我对此PHP加密代码进行了实际攻击，现在是交付的时候了。

我喜欢这次攻击，因为它展示了我到目前为止一直在说的一切。在Lego块视图中，代码中的计时侧通道似乎只与消息完整性相关。我们被诚信搞得心烦意乱，忘了考虑它对保密的影响。事实证明，这会产生很大的影响。我发现的攻击可以让攻击者解密密文中每个块的第一个字节。唯一的前提条件是：(1)攻击者需要一些(小于2000)的已知明文块，以及(2)攻击者需要能够向解密函数提供密文并获得准确的运行时间测量(即，他们可以利用侧信道)。

我不打算在这里解释这次袭击。我觉得这样做会分散人们对这篇帖子所传达的信息的注意力。如果您感兴趣，您可以在这里找到攻击的模拟概念实现证明。代码有很好的注释，所以如果您想知道它是如何工作的，您应该能够通过阅读(并运行)该代码来理解它。

在概念验证中，我删除了Serialize()和UnSerialize()调用，以及对Trim()的调用。我还修改了解密函数，如果第一个字节的MAC比较失败，则返回0；如果MAC比较超过第一个字节，则返回1，模拟具有一个字节粒度的旁路。

我进行了这些更改，以使攻击更容易、更可靠。如果没有这些变化，攻击在理论上仍然是可能的，但要证明起来要困难得多。具体地说，字符串比较计时泄漏实际上并不具有一个字节的粒度。相反，通常逐字比较字符串(一次4或8个字节)，这会增加执行攻击所需的解密查询数。如果读者感兴趣，他们可能会尝试让攻击在现实环境中工作。

当我们用乐高进行推理时，我们为了拯救一棵树而破坏了环境。在这种情况下，我们分心思考Mac和伪造，忘记检查其他安全属性。是的，那块蓝色的乐高积木被红色的积木挡住了，但直到我们后退一步，我们才能看到红色的积木挂在边上，即将倒下，把蓝色的积木也带来了。

把密码学想成乐高积木会让你误入歧途。如果您想要构建安全的密码学，请坚持在具有强大对手的严格模型中提供安全证明。如果您想破解密码学，首先要证明它在严格的模型中是不安全的，然后找到一种方法将这些弱点转化为实际的攻击。

如果你想雇佣我来找出你的密码设计的问题或你代码中的一些错误，你可以在这里找到更多关于我的咨询服务的信息。