[mercury-users] Beginner questions
Sandy Harris
sandy.harris at sympatico.ca
Tue Mar 16 12:57:26 AEDT 1999
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.
More information about the users
mailing list