就像一个有趣的练习一样，我从头开始设计和实现了一个独立的，经过身份验证的加密工具，包括使用单个加密原语进行密钥派生和拉伸。或更具体地说，是原语的一半。该原语是XXTEA块密码的加密功能。目标是将设计和实现缩减到最低限度，而在实践中不致被破坏-希望-并可能在此过程中学到一些东西。本文是我的设计之旅。这里的一切将几乎与正确答案相反。
该工具本身名为xxtea（小写），并且在所有类似Unix和Windows的系统上均受支持。即使在后者上进行编译也很简单。该代码应易于上下左右跟踪，并附有有关具体决策的注释，尽管我会在此内联引用最重要的内容。
命令行选项遵循通常的约定。两种操作模式是加密（-E）和解密（-D）。默认情况下使用标准输入和标准输出，因此它在管道中很好地工作。提供-o将输出发送到其他地方（如果出了问题会自动删除），并且可选的position参数指示替代输入源。
用法：xxtea＆lt; -E | -D＆gt; [-h] [-o文件] [-p密码] [文件]示例：$ xxtea -E -o file.txt.xxtea file.txt $ xxtea -D -o file.txt file.txt.xxtea
如果未提供密码（-p），则提示输入UTF-8编码的密码。当然，通过命令行参数提供密码通常不是一个好主意，但是对于测试非常有用。
TEA代表Tiny Encryption Algorithm，而XXTEA是第二次尝试修复密码中的弱点-部分成功。对于此特定应用程序，其余问题不应该成为问题。 XXTEA支持可变的块大小，但是我已经将实现硬编码为128位的块大小，同时还进行了一些展开。我也放弃了不需要的解密功能。没有依赖于数据的查询或分支机构，因此不受投机攻击的影响。
XXTEA可对32位字进行操作，并具有128位密钥，这意味着block和key均为四个单词。我的实现大约有十几行。它的原型：
所有加密操作都是从此功能构建的。考虑它的另一种方法是，它接受两个128位输入并返回一个128位结果：
如果我放弃了解密功能，如何解密消息？我敢肯定，我已经猜到了：XXTEA将用于计数器模式或CTR模式。与其直接加密明文，不如加密一个128位的块计数器并将其视为流密码。该消息与加密的计数器值进行异或，以进行加密和解密。
无需填充方案。在其他块模式下，如果消息长度可能不完全是块大小的倍数，则需要某种方案来填充最后一个块。
无效增量（uint32_t ctr [4]）{/ * 128位增量，第一个单词变化最快* / if（！++ ctr [0]）if（！++ ctr [1]）if（！++ ctr [ 2]）++ ctr [3]; }
在xxtea中，单词始终以小尾数字节顺序（最低字节在前）进行编组。将第一个字作为最低有效位，整个128位计数器本身就是小端。
计数器不是从零开始，而是从一些随机选择的128位随机数（称为初始化向量（IV））开始，必要时会回零。消息中将包含IV。此随机数允许将一个密钥（密码）与多封邮件一起使用，因为它们都会使用巨大密钥流的不同，随机选择的区域进行加密。它还提供了语义安全性：对同一文件进行多次加密，密文将始终完全不同。
for（/ * ... * /）{uint32_t cover [4] = {ctr [0]，ctr [1]，ctr [2]，ctr [3]}； xxtea128_encrypt（key，cover）;块[i + 0] ^ =封面[0];块[i + 1] ^ =封面[1];块[i + 2] ^ =封面[2];块[i + 3] ^ =封面[3]；增量（ctr）; }
这是加密的，但是仍然存在身份验证和密钥派生功能（KDF）的问题。为了解决这两个问题，我需要设计一个哈希函数。由于我只使用一个原语，因此我需要以某种方式从块密码构建哈希函数。幸运的是，有一个可以做到这一点的工具：Merkle–Damgård构造。
回想一下xxtea128_encrypt接受两个128位输入并返回一个128位结果。换句话说，它将256位压缩为128位：压缩功能。将两个128位输入加密组合为一个128位结果。我可以重复此操作以将任意数量的128位输入折叠为128位哈希结果。
uint32_t *输入= / * ... * /; uint32_t hash [4] = {0，0，0，0}; xxtea128_encrypt（input + 0，hash）; xxtea128_encrypt（input + 4，hash）; xxtea128_encrypt（input + 8，hash）; xxtea128_encrypt（input + 12，hash）; // ...
注意输入是键，而不是块。哈希状态使用哈希输入作为键重复加密，将哈希状态和输入混合在一起，当输入用尽时，该块即为结果。有点。
在示例中，我使用零作为初始哈希状态，但是如果起始输入是随机的，它将更具挑战性。像河豚一样，在xxtea中，我选择了pi的小数点的前128位：
void xxtea128_hash_init（uint32_t ctx [4]）{/ * pi的前32个十六进制数字* / ctx [0] = 0x243f6a88; ctx [1] = 0x85a308d3; ctx [2] = 0x13198a2e; ctx [3] = 0x03707344; } / *将一个块混合到哈希状态。 * / void xxtea128_hash_update（uint32_t ctx [4]，const uint32_t block [4]）{xxtea128_encrypt（block，ctx）; }
仍然有几个问题。首先，如果输入不是块大小的倍数怎么办？这次，我确实需要一个填充方案来填充最后一个块。在这种情况下，我用字节填充它，其中每个字节是填充字节数。例如，helloworld大致说来就是helloworld666666。
这就产生了一个不同的问题：这将具有与实际以这些字节结尾的输入相同的哈希结果。因此，第二条规则是，即使该填充块是100％填充，也始终存在一个填充块。
另一个问题是Merkle–Damgård的结构容易受到长度延伸攻击。任何人都可以获取我的哈希结果并继续追加其他数据，而无需知道之前发生了什么。例如，如果我使用此哈希对密文进行身份验证，则有人可能会使用此攻击将任意数据附加到邮件末尾。
一些重要的哈希函数（例如SHA-2的最常见形式）容易受到长度扩展攻击。牢记这个问题，我以后可以使用HMAC来解决，但我现在有个想法可以解决。在将填充块混入哈希状态之前，我交换了两个中间词：
/ *将最终的原始字节块追加到哈希状态。 * / void xxtea128_hash_final（uint32_t ctx [4]，const void * buf，int len）{断言（len＆lt; 16）; unsigned char tmp [16]; memset（tmp，16-len，16）; memcpy（tmp，buf，len）; uint32_t k [4] = {loadu32（tmp + 0），loadu32（tmp + 4），loadu32（tmp + 8），loadu32（tmp + 12），}; / *交换中间单词以破坏长度扩展攻击* / uint32_t swap = ctx [1]; ctx [1] = ctx [2]； ctx [2] =交换; xxtea128_encrypt（k，ctx）; }
此操作“绑定”了最后一个块，以使散列无法通过更多输入来扩展。还是我希望。这是我自己的发明，所以soit可能实际上无法正常工作。同样，这是为了娱乐和学习！
首先，XXTEA从未设计用于Merkle–Damgård构造。我假设攻击者可以修改我将解密的文件，因此哈希输入通常且大部分在攻击者的控制之下，这意味着它们可以控制密码密钥。通常在假定密钥不受敌对控制的情况下设计密码。这可能容易受到相关按键攻击的影响。
如下所述，我以两种方式使用此自定义哈希函数：一种是输入不受攻击者控制，因此这是非问题;第二种是，攻击者在控制哈希值之前完全不知道哈希状态输入，我相信可以减轻任何问题。
其次，如今这些128位的哈希状态有点小。对于非常大的输入，通过生日悖论发生碰撞的可能性是一个实际问题。
在xxtea中，即使在加密巨型文件时，摘要一次最多只能计算几兆字节的输入，因此应该是128位状态。
用户将提供一个密码，而我需要以某种方式将其变成一个128位密钥。
如果不直接使用原始密码，则对于密码来说更安全。
前三个可以通过在散列函数中运行密码来解决，并将其用作密钥派生函数。最后一项呢？我将密码（包括nullterminator）重复连接一次，而不是一次哈希密码，直到达到一定数量的字节（硬编码为64 MiB，请参见COST）并将其哈希。这是攻击者在猜测密码时必须重复的计算工作量。
为了避免基于密码长度的定时攻击，我在开始哈希之前预先计算了所有可能的块排列-密码可能会以16字节的块连接在一起。如果有必要使该部分保持恒定的时间，则可以冗余地计算块。散列完全由这些预先计算的块提供。
为了抵御彩虹表等（以及使其更难攻击消息构造的其他部分），将初始化向量用作盐，在密码连接之前将其馈入哈希。
不幸的是，这种KDF并不是很难存储的，攻击者可以利用规模经济来加强其攻击（GPU，自定义硬件）。但是，难于记忆的KDF需要大量内存来计算密钥，这使得内存成为攻击者的昂贵且受限的因素。难以存储的KDF复杂且难以设计，为简化起见，我进行了权衡。
当我说加密是经过身份验证时，我的意思是说，任何人在不知道密钥的情况下，都不能篡改未检测到的密文。通常，这是通过计算带密钥的哈希摘要并将其附加到消息，消息身份验证码（MAC）来完成的。由于使用了密钥，因此只有知道密钥的人才能计算摘要，因此攻击者无法欺骗MAC。
这就是长度扩展攻击的作用：如果MAC的结构不正确，攻击者可能会在不知道密钥的情况下追加输入。幸运的是，我的哈希函数不容易受到长度扩展攻击的攻击！
另一种选择是使用经过身份验证的阻止模式，例如GCM，其核心仍然是CTR模式。不幸的是，这很复杂，而且与普通的点击率不同，我要花很长时间才能说服自己理解正确。因此，我直接使用了CTR模式和哈希函数。
在这一点上，有一个问题是您到底向哈希函数输入了什么。您对纯文本进行哈希处理还是对密文进行哈希处理？由于前者通常无法使用前者，因此它很容易这样做，并且可能会使攻击更加困难。这是个错误。始终在密文上计算MAC，再加密然后进行身份验证。
这就是所谓的厄运原理。在纯文本上计算MAC意味着收件人必须在对不可信密文进行身份验证之前对其进行解密。这很不好，因为消息应在解密之前进行身份验证。这就是xxtea所做的。它碰巧也是最简单的选择。
我们有一个哈希函数，但是要计算MAC，我们需要一个键控哈希函数。再说一次，我做了我认为不会破坏的最简单的事情：将密钥与密文连接起来。或更具体地说：
该计数器是因为xxtea使用具有1兆字节块的分块身份验证。它可以一次对一个块进行身份验证，从而可以通过身份验证在固定数量的内存中解密任意数量的密文。可能发生的最坏情况是块之间的截断-可以接受的折衷方案。计数器确保每个块MAC都是唯一的，并按顺序显示。
同样重要的是要注意，计数器是在密钥后面附加的。计数器处于敌对控制之下-他们可以选择IV-并且首先拥有密钥意味着他们没有关于哈希状态的信息。
除最后一个块（通常更短）以外，所有块均为一兆字节，表示消息结束。它甚至可能只是MAC和零长度密文。这避免了解析可能未经身份验证的长度字段之类的麻烦问题。只要在第一个经过身份验证的短块成功停止即可。
有些人可能会发现它，但潜在的缺点是我在加密和身份验证时使用了相同的密钥。这些通常是两个不同的键。在某些情况下，例如CBC-MAC，这是灾难性的，但我相信在这里还可以。计算单独的MAC密钥很容易，但是我选择了简单的方法。
按照我惯用的样式，加密文件没有明显的头或字段。它们看起来就像是随机数据块。文件以16字节的IV开头，然后是零个或多个1兆字节的块序列，最后是一小段。与/ dev / random没什么区别。
如果用户输入了错误的密码，则在对第一个密码进行身份验证时将被发现（立即阅读：）。这样可以节省文件开头的专用检查，尽管这意味着不可能区分错误密码和修改后的文件。
我知道我的设计由于人为的，自我施加的限制和故意的权衡而存在弱点，但是我很好奇我是否犯了任何明显的错误并带来了实际后果。
对这篇文章有评论吗？ 通过发送电子邮件至~skeeto/[email protected] [邮件列表礼节]，在我的公共收件箱中进行讨论，或查看现有讨论。