[mercury-users] Beginner questions

[Sandy Harris]

Fergus Henderson wrote:

> > 3):
> > My main application for Mercury would be as a tool for trying
> > to break ciphers. Write a program that takes a set of known
> > plaintext/ciphertext pairs encrypted under the same key, and
> > outputs the key.
> >
> > This is clearly possible in principle, but the cipher designers
> > work hard to make it difficult in practice. The general form of
> > the problem is the NP-complete Boolean satisfaction problem,
> > but I'll be dealing only with specific finite-sized instances.
> 
> Hmm... what kind of algorithm are you thinking of using?

My concern is trading off compile-time effort against run time.
For this application, a compile time measured in months would be
fine if it allowed optimisations that made the final program fast.

Essentially, what I want to do is code it with a carefully chosen
representation, so that the compiler's optimisations can in effect
solve the problem symbolically. Then at run time, drop in the data
& out pops a key.

It is clear that the solution I want can be written as a Boolean
eq'n with 256 inputs and a unique 56-bit output. Also that with
a clumsy representation and no optimisation, you need several
thousand intermediate variables and ridiculous amounts of
computation.

Am I looking for a non-existent silver bullet here?

>From a piece of my email to a crypto list:

<quote>
For any cipher, take some convenient small number of rounds
and write equations over boolean vectors of the form:

	c = e(p,k)
	p = d(c,k)

where e() & d() are encrypt & decrypt functions, c ciphertext,
p plaintext & k the round key. This is always possible, though
not necessarily simple.

Now for double that number of rounds, we can write:

	m = e(p,k0)
	m = d(c,k1)

where m is the middle text value & we immediately have:

	e(c,k0) = d(p,k1)

Now try to solve this to get a new set of equations,
covering twice as many rounds as the equations you
started with:

	c = E(p,k0,k1)
	p = D(c,k0,k1)

</quote>

The idea is to do this recursively for 1, 2, 4 ... all rounds
and solve the final eqn's for the key.

In the particular cipher I'm attacking, DES, there's a handy
additional constraint. All the round keys are formed by just
permuting bits of the primary key. With a 56-bit primary key
and 48-bit round keys, k0 and k1 above must have >= 40 bits
in common.