[Cryptography] Cryptanalyzing a whole-message cipher and a double-tree hash function

[Jon Callas]

> On Dec 26, 2023, at 21:12, Pierre Abbat <phma at bezitopo.org> wrote:
> 
>> 4) Do plan to resist future quantum system attacks.  I would step past
>> and ignore anything new that
>> was not designed for post-quantum cryptography (PQC) (also called
>> quantum-resistant or quantum-safe cryptography).
> 
> It's a symmetric algorithm. How does one make a post-quantum symmetric cipher? 
> The post-quantum algorithms I've heard of are public-key ciphers.

One doesn't. One doesn't need to.

For a symmetric cipher, the best quantum attack is Grover's Algorithm, and that only reduces the security by half the bits. Thus, as an example, AES-128 has 64 bits of quantum strength and AES-256 has 128, so if you're worried about quantum attacks, just use AES-256 and be done with it. Hash functions don't need to worry, because we already consider them to have a strength of half the output size. On top of this, it increasingly looks like Grover's Algorithm is impractical, and even the government recommendations for symmetric cryptography can be summarized as "you don't really need to worry, and if you're still worried, why aren't you just using 256-bit crypto anyway?"

---

In other considerations, I looked at your code and would really like to see a paper that describes what you're doing, what problems you want to solve, what mechanisms you're using to construct things, and so on. When the code is the documentation, then there's no difference between a trivial bug and your thing being broken, for example.

There are a number of questions I have that I know less about for having looked at the code than I did before. As an example, you said in your first message that you want to encrypt a whole message. Yet, what does that mean? Are you building a very-large-block cipher where any one-bit change causes the whole thing to decrypt differently? Or are you doing a chaining mode or something like it? 

I freely admit that I spent probably a whole five minutes (okay, maybe ten) looking at your code and I couldn't really see what the organization of the cipher, its scaffolding and test functions. I'm lazy and really want it all spoon-fed to me. I also think that if you wrote a paper explaining everything, it would force you to think about it in a different way than just the code.

As for cryptanalyzing a hash function as opposed to a cipher -- yeah, that's hard, and there really isn't a lot of detailed work on it. A reason for that is that ciphers and hash functions are completely different creatures. If you'll permit me this metaphor and a horrid oversimplification, a cipher is like a game of cards, where the bits of the key are like the cards. The function of the system relies ultimately that the attacker cannot see the cards in my hand. The game is whether they can figure out what the cards are by watching how the game flow goes. There are different variations on that game, like the known-plaintext game, where the attacker knows what goes in, what comes out, and they have to guess the cards based on that. Easier is a variation where they get to manipulate the plaintext before it goes in. Of course, the hardest version is the ciphertext-only attack.

Hash functions are completely different. They're like a chess game, not a card game. Or perhaps it's still a card game, but they're all face up on the table. There are no secrets. It's a complete information game, and nothing is hidden. Moreover, the sorts of attacks are different, and kinda squishy. Here's an example -- suppose you have a 256-bit hash function. They output is 32 bytes, of course, and if we consider the set of strings at least 33 bytes long, it is obvious that there are collisions (by the Pigeonhole Principle). So the attacker's game is not to *find* a collision, it's about *constructing* them. Again with horrid oversimplifications, there are also flavors of that game, too. The one we see most often is that someone takes a base string S, and modifies that string to produce S_1 and S_2 that hash to the same thing. The hard version is to find a totally different string T that hashes to the same thing as S. Hardest is that T has to have the same length as S. In any event, this is a totally different game from cryptanalyzing a cipher because there are no secrets. 

In any event, this is all part of why it's good to see discussion and not just code.

	Jon