A Brief Cryptanalysis of Yull

by Erebos (Simmons)

Let me start by saying that I am not a professional cryptographer, so take everything hereafter with a grain of salt.

There was a letter submitted in 32:2 that brought to light a new encryption program: Yull.  What follows is a brief analysis of the cipher it employs named Andromeda.  Before going any further, let's all just agree that rolling your own encryption is a bad idea.

If you do, at least make the source code readily available and with some type of mathematical backing.  There are a series of white papers on the site that describe some design choices, but the source (for the cipher) can be found here: www.yullencryption.com/AndromedaCode

Key Sizes

The author takes issue with the fact that modern ciphers only utilize "small" key sizes, typically in fixed increments.  While it is true that most modern symmetric ciphers max out at 1024-bit keys, this is considered more than adequate.  It would still take a billion computers making a billion guesses a second longer than time itself has existed to brute force a 256-bit key.  Assuming an adversary cannot crack a one kilobyte key, every bit beyond that is just wasted computation.

However, the author objects more so to the fact that an attacker could search your drives for files the same size as a given cipher's key length and thus reveal your keys.

In practice, though, one can use any arbitrary file with established ciphers by first running it through a hash function whose output is the same size as the required key.  This is (very) roughly how key files are already incorporated into existing encryption software (e.g. VeraCrypt¹).

It should also be noted that approved ciphers like AES are meant to fit a wide variety of tasks, not just file encryption on a local machine.  Packet encryption, PRNG, and hardware based encipherment speak to their flexibility.  By tying oneself down to user selected options and files, the use case is pigeon-holed to just local file encryption.  But there is still plenty of need for that.

So how does Andromeda hold up?

Security Through Obscurity

The phrase "security through obscurity" is borderline blasphemy in the world of cryptography.

One should never assume complexity directly correlates to strength.  The irony of Andromeda is that its attempt at security might be its greatest undoing.

As the first white paper states, "For most (or all) other symmetric encryption programs, if you have the key, the encrypted file, and the program itself, you can get the plaintext.  But with Yull, that is not enough, as Yull also requires that all the Options are correct."

These options are chosen by the user per encryption, which means they can also provide a distinguisher.  For example, Andromeda can use a variable number of rounds to encrypt each block, which opens itself up to timing attacks.  The user can also set a read buffer size, but based on modern caching algorithms, this could lead to cache timing attacks.  The encryption itself boasts 60 different functions are used to scramble data, but that falls to power analysis attacks.  Modern ciphers that employ much simpler algorithms succumb to the same types of attacks, even the venerable AES.²

This is the reason we have seen the advent of ARX ciphers, which use only the constant time operations ADD, ROT, and XOR in a defined order (see Threefish³ or Salsa⁴ for a defense of this design).  By giving each encryption so much variability, Andromeda is opened up to a variety of side-channel attacks that can leak information about a user's given options.  But we can assume the user's machine is locked down tight and free from any observation.  So how is the encryption function itself?

60 Encryption Functions

First, I want to clear something up.

The description of Yull frequently refers to data being encrypted millions of times.  What is actually meant here is that the Andromeda cipher uses up to 60 different functions to scramble data a number of times for each input.  I suppose this could be referred to as "encrypting" each input, but some functions (e.g. negate) provide no security in and of themselves (by the author's own admittance).

The biggest issue with the Andromeda cipher is the lack of rationale (or at least the lack of clear presentation thereof).  Each round function is composed of XOR, NOT, and ROT.  Now these are not bad building blocks for a cryptographic structure, e.g. SHA-3 uses the same operations plus AND.⁵

As mentioned earlier, simple is not a problem, but it does require reasoning.  For example, ARX ciphers derive their non-linearity from the ADD operation, which is why they include it.  But why does the 27^th encryption function XOR bytes from the key with the input block?  Is this the only function that does that, or is key material added in elsewhere?  Why just in these functions and not in all?  In fact, it is worth noting that if each function does not add key material, one could design a key/option case where only functions that perform linear operations are used.  Some functions also employ matrix operations.

Again, this is a solid idea, e.g. AES uses matrix multiplication multiplication over Galois fields to provide its security.  Yet with Andromeda, it seems to be a simple matter of setting up a matrix full of values and then pulling specific data out (sort of like a large S-box).  Ultimately, regardless of the number of functions employed, there appears to be no rhyme or reason to the data processing done in each round.  When it comes to cipher design, every function should have a purpose and serve to strengthen the overall cipher.  Andromeda seems to rely on its huge complexity to obfuscate any data it processes, but this does not make it secure.

Closing Remark

I urge someone with more experience than me to do a formal cryptanalysis of the Andromeda cipher.  I would be interested to see how this stands up to linear or differential cryptanalysis methods.  Yull would benefit from a full source code release in an easy to access manner, along with a more formalized white paper.

Unfortunately, the complexity of the encryption process only makes verifying the security harder rather than increasing the security itself.  Although code snippets are provided, the white papers never give a clear picture of why any choices were made other than the large number of combinations they provide.

While this may seem like an utter condemnation of Yull, I hope it is seen more as constructive criticism.  It is only through such criticism that we have the secure cryptoprimitives available today.

And in the end, it is never a bad thing to have more people interested in cryptography.

Sources

1. VeraCrypt Keyfiles
2. Cache-Timing Attacks on AES
3. The Skein Hash Function Family  (specifically §2.2)
4. The Salsa20 Family of Stream Ciphers  (specifically §2.3)
5. SHA-3