Break Eskil Steenberg's encryption algorithm!

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

Sizik
Posts: 1243
Joined: Wed Aug 27, 2008 3:48 am UTC

Break Eskil Steenberg's encryption algorithm!

So, Eskil Steenberg (of the stylistic procedural MMO Love) has, as an exercise, created an encryption algorithm, and wants to see if it can be broken. He describes it as "a virtual machine that produces a one time pad, and new instructions for the virtual machine." The full post (with reasoning behind the algorithm) is here, but I'll post the pseudo-C code below.

Code: Select all

`pos_a = key % key_size;pos_b = key % key_size;pos_c = key % key_size;for(i = 0; i < length; i++){old_a = pos_a;pos_a = key[pos_b] % key_size;pos_b = (pos_a + 1 + key[pos_c] % (key_size - 1)) % key_size;pos_c = (pos_a + 1 + key[old_a] % (key_size - 1)) % key_size;decrypted[i] = encrypted[i] ^ key[pos_a] ^ key[pos_b];key[pos_c] = (key[pos_c] << 31) | (key[pos_c] >> 1);key[pos_a] ^= key[pos_c] ^ i ^ decrypted[i]; }`

I would love to see if anyone can break this. If you want to try here are a few assumptions you can make: The key is only used once and is random, but assume that you have access to both the encrypted and a significant part of the plain text message (The encryption should hold up even if an attacker can accurately guess significant parts of the plain text). I’m very curious as to how the key size and amount of plain text data is given can impact the security of the encryption.
gmalivuk wrote:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.

Thesh
Posts: 6568
Joined: Tue Jan 12, 2010 1:55 am UTC

Re: Break Eskil Steenberg's encryption algorithm!

Without going too much into it, and ignoring the obvious like weak keys, I notice one major problem. pos_a, pos_b, and pos_c can (and likely will) be repeated twice in a row. When this happens, it's trivial to recover a part of the state.

For simplicity sake, let's assume the plaintext is all zeros.

If a, b, and c are repeated twice in a row, then
e0 = a ^ b;
let a' = a ^ rotr(c,1) ^ i ^ e0;
e1 = a' ^ b;

e1 = a ^ rotr(c,1) ^ i ^ e0 ^ b
c = rotl(e1 ^ i ^ e0, 1)

Now If it is repeated you have part of the state, it's likely fairly easy to recover the whole state given the simplicity, but I'm not going to spend too much time on this. It's also likely that b and c are equal, and if that is the case, then e0 ^ c will be equal to e1 ^ rotr(c,1), which will be equal to a.
Summum ius, summa iniuria.

Tub
Posts: 465
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Break Eskil Steenberg's encryption algorithm!

To start, the security of a OTP depends on the fact that it's entirely random. Using a PRNG with a low-entropy seed reduces the strength of the algorithm to the strength of the key. There's no OTP here, just key-stretching.

The key is only used once and is random

How would you share the key? If you already have a secure channel to exchange the key, why do you need the cypher? If you can securely share one-time-keys, why don't you share full OTPs?

The strength of OTPs is that they're uncrackable unless the key is compromised. The strength of symmetric cyphers is that you can reuse the shared key without compromising it. His algorithm is combining the worst of both worlds: unproven security while still relying on one-time-keys.

Let's talk about a few properties of good cyphers.

a) The cypher is secure even if the full algorithm is known. Always assume that the algorithm is public, and your only secret is the key. The author argues about obfuscation and secret algorithms, so I'm not sure he's taken that into account.
b) The output is indistinguishable from random numbers. I don't see any proof or even tests.
c) The strength does not depend on the chosen key. In this case, imagine a key entirely filled with zeros, then guess how long the algorithm would take to recover.
(ok, the chosen key will always matter if it allows the attacker to substitute a brute force attack with a simpler dictionary attack, but that's a different matter. He said the key was random, not user-generated.)

so.. probably not a contender against other cyphers with years of research behind them, even if there's no trivial way to crack it.

korona
Posts: 495
Joined: Sun Jul 04, 2010 8:40 pm UTC

Re: Break Eskil Steenberg's encryption algorithm!

I do not really understand how decrypting the encrypted message should work. So this post only talks about retrieving the key. Which of course allows you to decode the message no matter how decryption works.

There are a few points that immediately come to my mind:
• XORing the message with two words from the key does not add any advantage over just XORing with a single word
• The operation (key[pos_c] << 31) | (key[pos_c] >> 1) prefers 1 bits over 0 bits. Ouch.
• XORing with i in the next step also does not produce uniformly distributed numbers
• The algorithm uses a single round per input word which implies. The computational complexity per bit is incredibly small. Which implies:
• Even if it may be difficult to analyze the algorithm by hand it will be easily broken through a mechanical known plaintext attack e.g. by a SAT solver
• Because all operations except for the additions that are used compute pos_a and pos_b can be trivially encoded into SAT such an attack will probably be able to retrieve the key in milliseconds.

EDIT: With some cryptoanalysis SAT is able to completely break MD4 and break 46 round MD5 in less than 15 minutes. A single round key stretching algorithm will be definitely broken in milliseconds, even without further analysis. Runtime increases exponentially in the number of rounds for non-trivial algorithms like MD5.