2
$\begingroup$

What is Gimli, and how does XooDoo compare to symmetric ciphers such as AES or ChaCha?

I am looking at this library, called charm.

Interesting paper here.

I also note the paper on XooDoo here.

There were no questions on XooDoo on this site, so I'm really interested to have peoples thoughts.

How do these 'permutation' based ciphers compare with standard symmetric ciphers?

$\endgroup$
  • $\begingroup$ Gimli and XooDoo are unkeyed permutations. AES is a keyed permutation = block cipher. ChaCha is a stream cipher. Every one of these symmetric primitives can be assembled in various constructions to replicate the behavior of the others. The practical differences are things like efficiency (these permutations can be faster than AES), complexity (AES cipher modes are often very complex, strong modes are often slow, but constructions with efficient permutations can offer higher security with better performance), etc. $\endgroup$ – Natanael Aug 2 at 17:27
  • 1
    $\begingroup$ Also, as per the papers on minimalism in cryptography, a construction like XOR - encrypt - XOR (XEX, where encrypt can be an unkeyed permutation) effectively allows you to substitute an unkeyed permutation for a block cipher like AES. If the unkeyed permutation is equally resistant to cryptoanalysis as the keyed permutation, then a XEX mode allows it to be simpler than the typical keyed permutation would be. I can't say much about the actual security of these primitives and their implementations, though. That's for the experts say. $\endgroup$ – Natanael Aug 2 at 17:32
3
$\begingroup$

Gimli is an unkeyed permutation, mapping a 384-bit input to a 384-bit output, $\{0,1\}^{384} \rightarrow \{0,1\}^{384}$. It is not a cipher by itself as you can reverse the output if you have it in its entirety, so it is not sufficient for security by itself. Instead, it is used to create a secure construction, e.g. using the sponge function. This function gets its security by keeping a portion of the permutation's output a secret, making it impossible to reverse without guessing the unknown (too large to brute force) portion of the output.

XooDoo appears to be another unkeyed permutation, with a slightly different design. There's very little we can say about its security right now, however, because it is relatively new. It often takes many years of analysis for the cryptographic community to feel comfortable about a new design. I will say, though, that it was made by reputable cryptographers, including one of the designers of Keccak-f, a heavily-analyzed and secure unkeyed permutation which is used in SHA-3, a NIST-endorsed hash function.

You can't compare an unkeyed permutation to a keyed permutation like AES because they have different purposes. Although you could build a regular block cipher out of it, that's not typically done. A keyed permutation like AES can be thought as a function which selects a permutation at random based on a key. Without knowing the key, you don't know the permutation and cannot reverse the output even if you have it in its entirety. And ChaCha is even harder to compare it with, as it is a stream cipher.


So, is a keyed permutation (block cipher) or an unkeyed permutation better? Typically, a block cipher has been considered a universal cryptographic primitive. Numerous constructions have been built around a block cipher to create things like hashes (for example, using the Davies–Meyer compression function). Recently, unkeyed permutations like Keccak-f and Gimli have gotten significant attention as potentially superior universal primitives because not only are they easier to analyze, but the sponge construction that they are useful to build can be easily adapted for a stream cipher, hash, or authentication function.

Simply put, block ciphers are older and more research has been done into utilizing them, but unkeyed permutations are more flexible and easier to analyze, and are starting to gain serious traction. XooDoo is a result of this trend towards unkeyed permutations. The Gimli paper mentions that there's no reason to doubt the "new conventional wisdom" that a permutation is a better unified primitive than a block cipher.

$\endgroup$
  • 2
    $\begingroup$ FWIW, ChaCha does have an unkeyed permutation, not entirely unlike Gimli, at its core. $\endgroup$ – Ilmari Karonen Aug 3 at 12:30
  • 1
    $\begingroup$ @IlmariKaronen That's true, but it is not a general-purpose secure unkeyed permutation (whereas Gimli is). There's a trivial fixed point and it is vulnerable to attacks if it were used in a sponge construction but which aren't an issue when used the way it is. I would be hesitant to compare the ChaCha core with Gimli. $\endgroup$ – forest Aug 4 at 5:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.