我们可以为ChaCha内核显示碰撞或第二原像吗？ br />
澄清：我使用的是ChaCha核心（伯恩斯坦并未正式定义），它是ChaCha的Salsa20核心（他在此定义）是Salsa20；因此包括使用32位加法来组合多个回合的输入和输出。我不是在问与ChaCha流密码（哪个密钥流生成器使用ChaCha内核）的输出发生冲突。
Salsa20内核具有易于验证的属性，如果我们切换输入的每个32位字的最左位，输出不会更改，因此显示第二原像很简单（因此发生冲突）。在Bernstein提出的Salsa20（或ChaCha）核的使用中，这些冲突或第二原像不是问题，因为核心函数的足够输入固定为任意值，以防止（据我们所知）发生冲突和第二-与这些附加约束匹配的原图像。因此，这个问题更多的是出于好奇。
ChaCha和Salsa20内核还具有其他一些特性，即随机函数不会具有这样的特性，例如固定为零，或者在所有输入的单词是相同的。这些也不是问题，仅是出于故意设计决定的结果，即将无袖子的数字放在核心功能之外，以便于对其进行分析。
更新：也许我的某些好奇心确实来自短暂地造成（在scrypt中使用Salsa20内核的情况下）非常混乱的罪魁祸首Bernstein指出：
我最初将Salsa20核心称为“ Salsa20哈希函数”，但此术语使那些认为“哈希函数”表示“抗冲突压缩功能”的人感到困惑。 Salsa20核心不会压缩并且不具有抗碰撞性。如果要使用抗碰撞压缩功能，请查看Rumba20。 （我想知道同一个人对FNV哈希函数，完美哈希函数，通用哈希函数等的看法。）
这两个都是C99的核心功能；我们正在寻找
in的不同值，以使相应的out相同。#define CHACHA 1 // 1 for ChaCha, 0 for Salsa20
#define ROUNDS 8 // number of rounds, must be even; standard values are 20, 12, 8
#include <stdint.h> // for uint32_t
// 32-bit left rotation of v by n bits, with n in range [1..31]
#define ROTL(v,n) ((uint32_t)(v)<<(n) | (uint32_t)(v)>>(32-n))
// ChaCha or Salsa20 core, parameterized by CHACHA and ROUNDS
void djbcore(uint32_t out[16], const uint32_t in[16]) {
int i;
uint32_t x[16];
for (i = 0; i<16; ++i) x[i] = in[i];
for (i = 0; i<ROUNDS/2; ++i) { // each loop does 2 rounds
uint32_t t;
#if CHACHA // compiled for ChaCha
#define DJBQ(a,b,c,d) /* quarter round for ChaCha */ \
t=(x[a]+=x[b])^x[d]; x[d]=ROTL(t,16); t=(x[c]+=x[d])^x[b]; x[b]=ROTL(t,12); \
t=(x[a]+=x[b])^x[d]; x[d]=ROTL(t, 8); t=(x[c]+=x[d])^x[b]; x[b]=ROTL(t, 7);
DJBQ( 0, 4, 8,12) DJBQ( 1, 5, 9,13) DJBQ( 2, 6,10,14) DJBQ( 3, 7,11,15)
DJBQ( 0, 5,10,15) DJBQ( 1, 6,11,12) DJBQ( 2, 7, 8,13) DJBQ( 3, 4, 9,14)
#else // compiled for Salsa20
#define DJBQ(a,b,c,d) /* quarter round for Salsa20 */ \
t=x[a]+x[d]; x[b]^=ROTL(t, 7); t=x[b]+x[a]; x[c]^=ROTL(t, 9); \
t=x[c]+x[b]; x[d]^=ROTL(t,13); t=x[d]+x[c]; x[a]^=ROTL(t,18);
DJBQ( 0, 4, 8,12) DJBQ( 5, 9,13, 1) DJBQ(10,14, 2, 6) DJBQ(15, 3, 7,11)
DJBQ( 0, 1, 2, 3) DJBQ( 5, 6, 7, 4) DJBQ(10,11, 8, 9) DJBQ(15,12,13,14)
#endif
}
for (i = 0;i < 16;++i) out[i] = x[i] + in[i];
}
#1 楼
我们可以为ChaCha核心展示碰撞或第二原像（暗示前者）吗？
不，可能不会。
Salsa20和ChaCha核心都包含大量的“四分之一回合”，每个回合都是可逆的和双射的。两个核都不是双射的唯一原因（因此可能会发生冲突）是将输入元素最终添加到状态中。
使用Salsa20翻转高位是可行的，因为它不会影响右侧四分之一回合方程式的一面：
b ^= (a+d) <<< 7;
c ^= (b+a) <<< 9;
d ^= (c+b) <<< 13;
a ^= (d+c) <<< 18;
因此，翻转所有高位将它们一路翻转，并通过添加输入来抵消数据。
ChaCha四分之一轮没有那么简单的对称性：
稍微翻转一下，然后开始进行另一种操作，因此，四分之一轮操作不会留下任何简单的变化。寻找碰撞可能很困难。
我意识到这并不是证明，只是一种挥霍自如的理由。
评论
$ \ begingroup $
Nitpick：内核中的最后加法使其不容易反转。我们知道如何在512位域上公开易于计算的功能，这些功能显然是双射的，但是在计算上很难转换为任意输出（诚然，仅使用ARX操作来构建这样的功能需要很多）。
$ \ endgroup $
–fgrieu♦
15年7月24日在6:37
$ \ begingroup $
@fgrieu，我草率地使用“ invertible”作为那里双射的同义词。将修复。
$ \ endgroup $
–otus
15年7月24日在6:37
$ \ begingroup $
如果我们可以证明ChaCha核心不是双射的（除了0回合之外，结果微不足道），那就一定可以了。我猜想这对于几轮来说是可行的（例如2轮），但是对于足够的轮次来达到安全性（例如8轮或更多）则变得不可行。最后的加法破坏了双射的论点，但是缺乏命题的论点并不能证明它不成立（更不用说提供反例了）。
$ \ endgroup $
–fgrieu♦
15年7月24日在12:01
#2 楼
我想我知道您现在要问的内容。ChaCha本质上是一种分组密码，没有关键时间表。这具有一个优势，对于受约束的设备甚至对于台式机，所需的SRAM更少，缓存调用更少（https://stackoverflow.com/questions/10274355/cycles-cost-for-l1-cache-hit-vs-register-on -x86）。 ChaCha之所以能够做到与AES指令集一样快的部分原因。
这确实引起了一个小问题，理论上，关键位会通过滑动攻击而泄漏出去。除了生成幻灯片对之外，基本上需要监视2 ^ 256（生日）ChaCha加密，并且每个加密都有一个已知的明文。
即使ChaCha是假设的理想伪随机函数，其中一个初始状态映射到相同大小的随机最终状态，也存在一个实质性的问题：一小部分最终状态映射到由于生日问题和信鸽问题，导致两个或多个初始状态。
显然，对ChaCha会有明显的攻击。但是由于无法区分计数器模式下的128位分组密码的原因，因此需要观察2 ^ 256个输出以注意任何偏差。
尽管有一些输出对于ChaCha，可能难以估计的大量输出。
我不确定我是否涵盖了所有内容，因此，如果我认为是这样，我将编辑此帖子以包含评论中的任何建议必要。
评论
$ \ begingroup $
抱歉，我的问题不是关于ChaCha（密码）。我现在已经明确指出。我非常同意您对ChaCha（密码）的称赞，这在ChaCha标签的信息中应该很明显。
$ \ endgroup $
–fgrieu♦
15年6月22日在10:03
$ \ begingroup $
@fgrieu IC。在这种情况下，布雷克使用大量的常量表来消除ChaCha的某些属性。没有对哈希进行任何细微修改的情况下，没有人真正使用ChaCha round函数。
$ \ endgroup $
–user3201068
15年6月22日在18:26
#3 楼
回答此问题的最简单，零思考的方法是询问计算机。使用Dylan的加密实现，很容易提出一个问题：两者都相等。密码没有（嗯，没有）隐含的箭头，所以我们对同一问题的措辞略有不同。
我的原始帖子问过省略了双回合的最终32位加法的更容易解决的问题：
m1 != m2 ==> ChaChaCore m1 != ChaChaCore m2
包含该最终加法的实际问题不会很快终止：
ChaCha20> :prove \m1 m2 -> m1 == m2 || ChaChaTwoRounds m1 != ChaChaTwoRounds m2
Q.E.D.
我还在等这个。也许如果我使用SAW并将第一个结果添加为引理，那么解决方案将更快。
评论
$ \ begingroup $
@fgrieu对不起，我准备公开演讲的一部分，以链接到github.com/TomMD/cryptol-slides。在该演示文稿和相关的SAW代码中，我展示了Cryptol / SAW证明了“ On Salsa20 Core Function”论文中的定理。
$ \ endgroup $
– Thomas M. DuBuisson
15年7月24日在1:51
$ \ begingroup $
@fgrieu双循环功能由DJB在规范中定义，并且没有任何冲突。为了理解这些定理，我建议您阅读相关的论文。进一步阅读以了解冲突，尤其是参见“ theorem7”。
$ \ endgroup $
– Thomas M. DuBuisson
15年7月24日在2:57
$ \ begingroup $
如果需要明确说明：ChaChaTwoRounds类似于“ ChaCha2”以获取ChaCha20，我们将运行ChaChaTwoRounds 10次，如您在源代码中所见。这就是我们对ChaCha _ 10所做的工作，ChaCha _ 10的证明尚未终止，但是对于两个回合情况，结果应该是显而易见的推论-没有碰撞。
$ \ endgroup $
– Thomas M. DuBuisson
2015年7月24日3:00
$ \ begingroup $
让我们继续聊天中的讨论。
$ \ endgroup $
– Thomas M. DuBuisson
15年7月24日在4:24
$ \ begingroup $
总结讨论：定理证明者证明ChaCha不能碰撞2轮；这与ChaCha核心发生2轮碰撞没有直接关系。 $ \; $它并没有回答10x2回合的ChaCha核心是否碰撞。实际上，如果自动化工具可以证明或否定仅两轮的ChaCha核心发生碰撞，那将比证明Salsa20核心要大得多。 $ \; $有很强的启发式论点，即ChaCha内核在使用足够多的回合以确保安全性时发生冲突，我们暂时不知道任何冲突。
$ \ endgroup $
–fgrieu♦
15年7月24日在5:43
评论
这是关于ChaCha的事情。这不是哈希函数。嗯，从技术上讲是这样，但是它不会接收消息并将其添加到内部状态以为给定消息分配唯一值。只要发件人和收件人都是受信任的方，原像和冲突的问题就不重要了。 Rumba确实采用了Salsa并将其用作压缩功能，但事实证明，在经过四轮攻击后，它可以抵抗碰撞攻击。问题不是一个真正的问题。 RC4也不是哈希函数。@ user3201068：的确如此。我现在强调了（已存在的）观察结果，即Chacha核的碰撞或第二个原像不会构成缺陷。
……伯恩斯坦的笔记……几个月前，我从伯恩斯坦本人那里读到了一些东西。 “ Bernstein哈希”混淆（至少，我曾经遇到过的-似乎与您的相似）源于Bernstein将“哈希”视为混合/混洗的事实。多年后，他意识到由于“哈希”算法的存在，也引起了混乱。他仍然坚持自己的“散列手段来混合”的口头禅（可能是一个自我的东西），但同时他补充说，他并不是在谈论“哈希”，因为我们（加密社区）知道这些。现在已经不记得标题了，但是如果您觉得合适，我可以尝试将自己阅读的内容进行细化。
那是DJB论文中对“关于Salsa20核心功能”论文的回应。严厉的回应。
@ ThomasM.DuBuisson很可能是一个……（我在移动设备上，现在正享受着德国火车运输的不利影响。我不愿意尝试使用自动柜员机的不稳定连接来检查PDF。）只能说，在阅读伯恩斯坦的出版物时，我倾向于用“混合功能”代替“哈希”，这一切都变得有意义。严厉的回应。真正。至少我们可以断言我们一直都知道伯恩斯坦不是一个所谓的“轻松的角色”。 OTOH，我很喜欢阅读他的旅行经历。