C[omp]ute

From: andrew cooke <andrew@...>

Date: Tue, 24 Dec 2013 00:23:19 -0300

A couple of nights ago I finally finished the break of ONE round of RC5 with
no rotation using the idea I mentioned near the start of
http://acooke.org/cute/BreakingRC0.html (ie carefully chosen plaintext plus
some simple arithmetic, then targetting individual bits in the xor, then a bit
more arithmetic).  It works nicely, but there's no way to extend it to
multiple rounds that I can see.


So now I'm thinking about the second idea I mentioned there, which was to
express everything as additions modulo 2.  That seems like it might work
because XOR is addition modulo 2, and addition is, well, something similar to
addition modulo 2...

But when I look at the details, it's not so easy.  Addition has a carry.  And
carry is not a modulo 2 kind of thing.

If I take the basic operation in RC5, which is (a^b)+c, and think about that
in terms of bits, and extend it to include the carry bit, k, from the bit
below, then I have something like (a^b)+c+k.

Now that is just a+b+c+k for the bit's value, modulo 2.  But the carry bit to
chain up to the next level is not so easy.  It's something like 

  abck + abc(1-k) + ab(1-c)k + (1-ab)ck

which contains multiplications!  So it isn't linear.  So it seems like the
maths is going to get messy...


So I shelved that approach and looked round for something else.  I started to
think about statistical methods and / or approximations.  I wondered if there
was some kind of iterative approach - if you have a guessed state, how can you
improve it?  And that led to the idea of using a genetic algorithm to improve
the state.

The critical part of genetic algorithms is representing and merging state.
The state itself seems pretty obvious - it's the RC5 internal state.  A bunch
of integers.  But how would you merge two individuals to generate a child?

At first I thought of what you might call "vertical" merging.  Take some
integers from one parent, and some from another.  But then there's an obvious
alternative, which you might call "horizontal" - take the lower bits of the
integers from one parent, and the higher bits from the other.

Which is better?  If you tihnk about RC5 without rotation then the horizontal
approach seems better.  Because it seems like there could be a lot of
redundancy "horizontally" (in fact, I saw redundancy in my single round
solution), while "vertically" the only effect is carry (the same carry that
was such a nuisance above).

At this point I had a kind of side-track.  Maybe I could just ignore carry to
a first approximation?  I don't think that goes anywhere, but I am noting it
just in case it's useful later.


Then suddenly, from those thoughts about the horizontal and vertical, and
carry being a vertical operation, I had a surprising insight.  Something that
in retrospect seems very obvious.  So obvious that I am worried I am doing
something stupid.  But I will write it down here and see how it looks in the
morning:

Without rotation, the least significant bits are unaffected by any other
bits.  RC5 breaks a block into two parts, a and b.  These go through repeated
(u^v)+w operations to get a' and b'.  But nothing in the (u^v)+w operation
mixes in any new, variable information in the lowest bits.  Higher bits get
the carry.  And rotation would cause chaos.  But without rotation the lowest
bits are pretty much unchanging.

In other words, the lowest bit of a' and b' is completely determined (for a
given state / key) by the lowest bit of a and b.  There are 4 possible
combinations and so with 4 plaintext blocks we can write down the truth table
for the lowest bit!

This extends to higher bits, but, because of the carry, they also depend on
lower bits.  So you can construct a truth table for the lowest two bits of
each part with 8 blocks.  And so on.

Now a block is typically 32bits (although it can vary, and my lovely Julia
code is parameterised by this).  So constructing a full table is not
feasible.  But the lowest 16 bits are easy meat.


So I need to test that.  And then, if I don't have any more ideas, look at
genetic programming.  Can the two approaches be merged?  The truth table
approach shows that there is a lot of duplicate state in the lowest bits.  But
how can I represent that in a genetic model in a way that preserves all the
flexibility?

Interesting / fun problems, even if no-one else cares about block ciphers any
more.

Andrew