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

[Pierre Abbat]

On Tuesday, December 26, 2023 5:41:39 AM EST Jacob Christian Munch-Andersen 
wrote:
> Over all this is a very poor construction stuffed with beginner mistakes and
> plenty cargo cult. It mostly operates on single bytes, making a poor
> utilization of modern CPUs. It utilizes loads of operations that are
> cryptographically simple, yet take a lot of CPU time, like `rot_bitcount`,
> it is just a rotation, but you manage to call modulo with a variable
> divider twice per byte processed. The way `compress` removes 4 bytes per
> iteration means that you end up calling all this slow code a lot of times.
> Yet one can plausibly generate a collision within the first iteration, thus
> bypassing most of the computation.

It has plenty of stack cult too.

Finding a preimage of the compress function is actually trivial; just pick 32 
arbitrary bytes, and run the compress function backward, sticking them in when 
they would be dropped forward. But a collision of the compress function (two 
different preimages of the same image) does not constitute a collision of the 
hash function, unless you have a weak key (all three S-boxes the same). To 
constitute a hash collision, they would have to collide both with sboxalt=0 
and with sboxalt=1. They have to be the last two blocks, where the total 
number of blocks is 6n+1, n>0, not counting the block of exp(4) prepended to 
the message. I searched for pairs of blocks consisting only of bytes which, 
when passed through all three S-boxes, would result in the same number of one-
bits, which collide when compressed with sboxalt both 0 and 1, and found none. 
There's no way those blocks could be the last two blocks of a message, because 
none of the bytes is 0, and the padding always contains a 0. But more 
searching of the key space could turn up a key where 0 is S-boxed to three 
bytes with the same number of bits set.

I could rewrite rotBitcount to use two loops without modulo, instead of one 
loop with modulo, and I think I will do that in Julia, now that you point it 
out. But the Rust and Haskell code are the reference implementation; it's more 
important to be comprehensible than to be fast.

On Tuesday, December 26, 2023 7:15:58 PM EST Tom Mitchell wrote:
> 1) A quick look, the code is copyright and you are asking for a free
> consultation :-(
> I recommend a policy close to other public review submissions.  See
> early editions of TeX.
> Add clarity with an "Intellectual Property Statements / Agreements /
> Disclosures" statement.
> Give attention to code and standards you depend on.

It's BSD3 licensed. GitHub doesn't recognize the license because I put my name 
instead of "Author name here".

> 2) Your key management risks key exposure as the key is exposed on the
> command line.  Many systems and many invasive malware hacks look at
> running programs for the things of interest.

It's a library. The main reasons it has executables are to run test.sh and to 
run cryptanalysis. Rust doesn't have a REPL, so I couldn't test the Rust code 
without making an executable.

> 3) Initialization and runtime library management local and remote is a
> risk.  You risk opening an attack should someone
> notice your reliance on something that they can corrupt in the future.

How would you mitigate the risk? What do you mean by "local and remote"?

> 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.

Pierre
-- 
La sal en el mar es más que en la sangre.
Le sel dans la mer est plus que dans le sang.