Eaglesong: On Novelty as a Design Requirement

[keks]

Novelty as a design requirement makes sense to prevent existing hardware miners from being used for mining on the Nervos network. However, so little is known about the security of Eaglesong, that it is not clear that there is no faster way to find a target than brute force. Two of the four steps of the permutation function are trivially invertible, and no rigorous cryptanalysis of the algorithm has been performed.

One approach to combine the security of existing hash functions (like SHA3) and the novelty of Eaglesong is to compose/chain them. SHA3 can be computed in hardware within a few cycles, so the overhead is not significant. Alternatively, don't use SHA3 but a different, more lightweight Keccak instance as additional hash. Make sure to rigorously motivate your choice of parameters in this scenario.

[janx]

Thanks for the suggestions.

We considered to mix Eaglesong with other hash functions but chose not to because 1. we're quite confident about Eaglesong after cryptoanalysis, 2. as Eaglesong is only used in proof-of-work hashing, if a weakness is found & published all miners could leverage it, and 3. we want to avoid extra complexity as much as possible.

The eaglesong paper is accepted by RCD2019 recently and the organizer will publish it on website soon, as it hasn't been uploaded I'll send it through email. Here is Alan explaining Eaglesong (start from 24:10) which may also help.

[keks]

Thank you for your response. I am happy to see there that you published an analysis of the algorithm. I am aware that Alan works and has worked with some highly respected people in the field. However, a single publication is rarely the end of the possible analysis (or rather, if it is, that's bad news because it means there is not more work to be done because the cipher/hash is broken - though I see that this is not the case here). However, it also means that I am still not remotely as confident that Eaglesong is secure as I am about Keccak being secure. Regarding your second point, yes, everyone can leverage published results, but there is a clear incentive not to publish the results and mine faster than others. Finally, Keccak is an off-the-shelf algorithm, with off-the-shelf implementations both in hardware and software. I don't think this increases the complexity to a point that it hurts.

Still, I want to correct my recommendation from before and suggest that instead of chaining the hashes you either concatenate or XOR them.

[janx]

Copy & paste from Alan: "The point that a single paper is not the end of all cryptanalysis is true; the future may hold more and improved analyses and might expose weaknesses that we overlooked. However the purpose of our present analysis is not to try and break it and see how far we get -- rather, it was to lower-bound the attack complexity using linear and differential cryptanalysis. If our argument is correct (and we do use heuristics that could turn out to be false) then any future linear, differential, and rotational cryptanalysis cannot perform better than our bounds."

I think those points are based on the confidence level to Eaglesong and are valid if there're undiscovered exploits. We acknowledge the possibility of undiscovered risks in Eaglesong, it's the simplicity and our own cryptoanalysis convinced us the probability is very small.

Still, I want to correct my recommendation from before and suggest that instead of chaining the hashes you either concatenate or XOR them.

Why do you suggest against chaining?

[keks]

Why do you suggest against chaining?

What you need here is a hash combiner. This is a construction that composes one hash functions from two, and is secure as long as either of them is secure. The simplest one, and the one that has undergone most analysis by cryptographers, is concatenating the two hashes. Intuitively, this means that the adversary has to find a collision in both hashes to find a collision in the combination. There are combiners that aim to achieve stronger security than the sum of the securities. These are more complex, but I don't think this use case requires such a combiner. One of them makes much use of XOR, but does not apply it to the output of the hashes in a straightforward manner. I have not been able to find papers on chaining hash functions (i.e. H(M) = (H_1(H_2(M))). My hunch is that the security of this construction is either strongly dependent on the inner hash functions, or has been understood to be insecure from very early on so nobody talks about it anymore.

My recommendation is to use any combiner that preserves collision resistance. I suggest a variant of the low-complexity concatenation approach. Instead of just concatenating the two hashes, interleave them such that

H_1(M) = a_0 || a_1 || ... || a_n
H_2(M) = b_0 || b_1 || ... || b_n
H(M) = a_0 || b_0 || a_1 || b_1 || ... || a_n || b_n

This is, from a informational and computational point of view, equivalent to concatenation, but whether or not the hash is below the threshold will depend on both hashes.

Some literature:

• https://www.esat.kuleuven.be/cosic/publications/article-2461.pdf
• https://tuprints.ulb.tu-darmstadt.de/2094/1/thesis.lehmann.pdf
• https://www.iacr.org/archive/eurocrypt2015/90560190/90560190.pdf

[aszepieniec]

Security of a new hash function compared to well-established SHA3 candidates

It is true that Eaglesong has not received as much cryptanalytic attention as Keccak has. There is a nonzero probability that someone will find a weakness in Eaglesong. However, there is also a small but nonzero probability that someone will find a weakness in Keccak or BLAKE.

I note that the discussion is independent of any particular design choice. It is difficult to answer such a highly generic concern without the specific design choices becoming relevant.

(And no, the fact that two steps of the round function are trivially invertible, does not indicate a potential weakness. The other steps are trivially invertible too. (I don't even know which two steps were being referenced.) All steps have to be invertible; otherwise it's not a permutation. All steps of the Keccak round function are also trivially invertible.)

Security of Eaglesong

By design, Eaglesong relies on sound design principles that also underlie widely deployed ciphers such as AES, Keccak, and ChaCha/BLAKE. A new attack would indicate:

1. at least one of these design strategies is much less robust than previously believed; or
2. the three design principles are not enough and are in need of another, complementary, design principle in order to provide adequate security.

Either event would with very high probability spill over to other published ciphers.

Combining Eaglesong with another hash function to defend against events 1 or 2, only makes sense if that second hash function has a completely different design strategy. From that perspective, I would recommend selecting SHA2 as the second hash function rather than Keccak or BLAKE2.

Also note that in our analysis, differential cryptanalysis and linear cryptanalysis are the best performers. (They usually are.) We set the number of rounds in accordance with a very optimistic (from the attacker's point of view) bound on the success probability of a linear cryptanalysis attack. However, we expect that with a more refined analysis, for instance involving a wide trail argument spanning 3 rounds as opposed to 2, the number of required rounds can be pushed down by quite a lot. We did not do this more refined analysis because it is rather involved, requires a large computation, and reporting on it does not make the paper any easier to read. (Nor should it make anyone more convinced about the security of Eaglesong.)

In simple terms, follow-up works (if any) are more likely (imho) to reduce -- rather than increase -- the number rounds required for the same level of security.

Combining Eaglesong with another hash function

I advise against this course of action, on account of the design goal of simplicity and beauty, as well as my own confidence that a weakness in Eaglesong is not likely to be found.

It is also worth noting (as it has been earlier in this discussion) that a weakness in the proof-of-work function is not as fatal as a cryptographic weakness elsewhere, for instance in the signature scheme. In fact, for the proof-of-work function, a weakness is indistinguishable from an optimization; both allow miners exploiting it to mine x% more efficiently than miners not exploiting it. What likely values for x are, is a cryptographic question but frankly the science has not developed yet to the point where we can answer. It is possible that by combining Eaglesong with another hash function, you end up increasing x rather than decreasing it.

If you are going to combine Eaglesong with another hash function (and let me repeat that I advise against this), then I would recommend: a) to use SHA2 rather than Keccak or BLAKE2; b) to use function composition rather than concatenation.

Recommendation (a) has to do with the recycled design principles of Keccak and BLAKE. As a result, the event "Eaglesong is broken" is much less independent of "Keccak or BLAKE2 is broken" than it is of "SHA2 is broken".

Recommendation (b) has to do with the fact that the proof-of-work puzzle is preimage-finding and not collision-finding. Specifically, the security game is multi-target one-wayness. A collision oracle does not help you win this game.

Suppose you have two hash functions, H0(x) and H1(x) from bitstrings of any length to bitstrings of length 2^n, and they let you find collisions after querying P and Q times, respectively, with P, Q < sqrt(2^n). Then the number of queries you need to make to find a collision for H0(H1(x)) is on the order of min(P, Q), and in fact, slightly less than that. The intuition is that your inputs will collide if they collide in H0 or if they collide in H1. In other words, against collisions, hash function composition gives you the security level of the weakest of the two components.

The situation is the opposite for preimage-finding. Suppose you can find a preimage for H0(x) with P work, and for H1(x) in Q work (work being either number of queries or time steps), and P, Q < 2^-n. Then inverting first H1 and then H0 is done in P+Q work -- and that's ignoring the possibility that your inverter for H0 might only work if you have a sufficiently large set of targets. In simple words, against preimage finding, hash function composition gives you the security level of the strongest of the two components. Of course, this analysis considers H0 and H1 to be independent and generic; meaning that this analysis does not capture the possibility of an inverter for H0(H1(x)) that can work in less work than P or Q by exploiting a particular structure in H0 and H1 that happens to make the composition easier to attack.