经过 AES-128 和 HMAC 处理的两个不同输入的输出冲突概率
Output Clash probabilities of two different inputs which undergoes AES-128 and then HMAC
我需要为我的每个输入生成一个唯一的输出字符串，这也是加密安全的。
我目前正在使用 https://github.com/defuse/php-encryption 作为库来首先加密然后散列我的输入。
根据库的readme文件，"Messages are encrypted with AES-128 in CBC mode and are authenticated with HMAC-SHA256 (Encrypt-then-Mac). PKCS7 padding is used to pad the message to a multiple of the block size. HKDF is used to split the user-provided key into two keys: one for encryption, and the other for authentication. It is implemented using the openssl_ and hash_hmac functions."
由于每次我运行算法的输出都不同。据我所知，这是因为加密阶段的 IV 不同。所以我的问题是，两个不同的输入和相同的密钥是否会发生输出冲突。
即HMAC(K2, AES-128(M1, K, IV1)) == HMAC(K2, AES-128(M2, K, IV2)) 可以吗？
由于每次HMAC的输入都不一样，所以抗碰撞能力和底层hash函数是一样的。对于 SHA-256，概率是 2<sup>-n/2</sup> = 2<sup>-128</sup> 其中 n 是输出大小（假设完整输出用作身份验证标记）。这仍然（可能）超出了我们目前的寿命。需要注意的是这里用的是n/2而不是简单的n，因为生日问题可以应用到抗碰撞上。
请务必注意，不应使用 collision resistance, but rather preimage resistance in mind where the probability is actually much much lower. Therefore, with the currently available attacks, it is still safe to use HMAC-MD5, but a better attack can come along which might break that 评估此处预期用途中的 HMAC。 HMAC-SHA256 是目前和（不久的）将来的安全选择。
So my question is, will there ever be an output collision for the two different input and same key.
i.e. can HMAC(K2, AES-128(M1, K, IV1)) == HMAC(K2, AES-128(M2, K, IV2)) be true?
是的，它可能会发生，但概率可以忽略不计（数量级：10^38 分之一），没有任何新发现的 SHA256 弱点。
对于理论上的攻击者来说更有趣的是：对于 128 位 IV，birthday collision 的机会是 2^64 分之一。如果您可以说服攻击者使用此库加密大约 18,000,000,000,000,000,000 个数据块（当今大多数攻击者无法达到的高得离谱的数字），您将获得重复 IV（概率为 50%）。
大多数 AES 密钥只会用于加密少于 2^50 字节的数据，因此对于大多数人来说这并不是一个实际的问题。然而，为了脊椎穿刺安全，我对 Defuse 的加密库版本实施了一个解决方法：
The library already uses HKDF-SHA256 to split the key into two keys:
- An encryption key (for AES)
- An authentication key (for HMAC)
In verison 2, in addition to a 128 bit random nonce for CTR mode, the library will also generate a 256 bit random salt for HKDF. This means that, even in the event that you get a birthday collision in the IV, the AES (and HMAC) keys will not be the same, so no information is leaked.
In order to get a useful collision, you would need the 128-bit nonce and 256-bit HKDF salt to be identical. This gives us 384 bits of breathing room, while the security still depends on a 256-bit "master" key (the one the library user manages).
简而言之，生日冲突的 50% 点发生在 2^192 条消息之后，而不是 2^64 条消息之后。
我需要为我的每个输入生成一个唯一的输出字符串，这也是加密安全的。
我目前正在使用 https://github.com/defuse/php-encryption 作为库来首先加密然后散列我的输入。
根据库的readme文件，"Messages are encrypted with AES-128 in CBC mode and are authenticated with HMAC-SHA256 (Encrypt-then-Mac). PKCS7 padding is used to pad the message to a multiple of the block size. HKDF is used to split the user-provided key into two keys: one for encryption, and the other for authentication. It is implemented using the openssl_ and hash_hmac functions."
由于每次我运行算法的输出都不同。据我所知，这是因为加密阶段的 IV 不同。所以我的问题是，两个不同的输入和相同的密钥是否会发生输出冲突。
即HMAC(K2, AES-128(M1, K, IV1)) == HMAC(K2, AES-128(M2, K, IV2)) 可以吗？
由于每次HMAC的输入都不一样，所以抗碰撞能力和底层hash函数是一样的。对于 SHA-256，概率是 2<sup>-n/2</sup> = 2<sup>-128</sup> 其中 n 是输出大小（假设完整输出用作身份验证标记）。这仍然（可能）超出了我们目前的寿命。需要注意的是这里用的是n/2而不是简单的n，因为生日问题可以应用到抗碰撞上。
请务必注意，不应使用 collision resistance, but rather preimage resistance in mind where the probability is actually much much lower. Therefore, with the currently available attacks, it is still safe to use HMAC-MD5, but a better attack can come along which might break that 评估此处预期用途中的 HMAC。 HMAC-SHA256 是目前和（不久的）将来的安全选择。
So my question is, will there ever be an output collision for the two different input and same key.
i.e. can
HMAC(K2, AES-128(M1, K, IV1)) == HMAC(K2, AES-128(M2, K, IV2))be true?
是的，它可能会发生，但概率可以忽略不计（数量级：10^38 分之一），没有任何新发现的 SHA256 弱点。
对于理论上的攻击者来说更有趣的是：对于 128 位 IV，birthday collision 的机会是 2^64 分之一。如果您可以说服攻击者使用此库加密大约 18,000,000,000,000,000,000 个数据块（当今大多数攻击者无法达到的高得离谱的数字），您将获得重复 IV（概率为 50%）。
大多数 AES 密钥只会用于加密少于 2^50 字节的数据，因此对于大多数人来说这并不是一个实际的问题。然而，为了脊椎穿刺安全，我对 Defuse 的加密库版本实施了一个解决方法：
The library already uses HKDF-SHA256 to split the key into two keys:
- An encryption key (for AES)
- An authentication key (for HMAC)
In verison 2, in addition to a 128 bit random nonce for CTR mode, the library will also generate a 256 bit random salt for HKDF. This means that, even in the event that you get a birthday collision in the IV, the AES (and HMAC) keys will not be the same, so no information is leaked.
In order to get a useful collision, you would need the 128-bit nonce and 256-bit HKDF salt to be identical. This gives us 384 bits of breathing room, while the security still depends on a 256-bit "master" key (the one the library user manages).
简而言之，生日冲突的 50% 点发生在 2^192 条消息之后，而不是 2^64 条消息之后。