Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:13:58
Mike Rosing (eresrch@msn.fullfeed.com)
Tue, 1 Sep 1998 09:16:12 -0500 (CDT)
On Mon, 31 Aug 1998, Sandy Harris wrote:
> I've thought up a method of cryptanalysis which I don't recall
> reading of anywhere, probably for several of the following reasons:
>
> it's pretty obvious
> it's hopelessly inefficient
> my memory's not all that good
> I haven't read all that much
>
> But it looks to me like it isn't entirely hopeless, & even if it
> is, then proving it hopeless for a given cipher might be useful.
I've been thinking about it for a long time. Glad to know I'm
not the only insane person around :-)
>
> Consider a cipher that operates on 64-bit blocks & uses a 128-bit
> key. Can we write equations in any useful algebra for the output
> in terms of the key & input? Given enough matched input/output
> (plaintext/ciphertext) pairs known to use the same key, can we
> just solve for the key?
Or better, given the cipher and s-boxes, can we find a set
of equations which will allow us to find any key given a
plaintext/ciphertext pair? Probably not, but neat to think about.
> Against any decent real cipher, it certainly won't be at all
> straightforward. My questions are whether it is possible at
> all, if so, whether it's pratical and whether the answers
> to those questions can be proved.
Proof is very difficult. Analysis is practical for each cipher.
At least, we can come up with a set of nonlinear equations and
stare at them until we go nuts.
> Choosing an algebra:
>
> The attacker can choose whatever algebra gives the best attack.
> For most ciphers, you would choose an algebra that coped well
> with some of the cipher's operations and then spend some effort
> expressing the other cipher operations in that algebra.
[....]
I'd write out all the equations first, then see if there are
large scale patterns. Higher level algebra may help you see
cracks, but you still need to manipulate individual terms to
completely solve the system.
> What to attack:
>
> For some ciphers, you'd solve for the primary key. For others,
> you might solve for the round keys. Choose whichever is easier,
> since both break the cipher.
[....]
But what if I can come up with a set of equations that ignores
the key(?!? bad cipher!). In other words, suppose I get a system
of equations which includes the key bits, cipher text bits and
plain text bits. Using the system, I eliminate the key bits
and leave only cipher text and plain text bits. The cipher text
is input, the plain text is output and we don't need a key.
That's a seriously broken cipher.
> Example:
>
> I know that Boolean problems can be thoroughly intractable,
> in particular that SAT is NP-complete, and that the equations
> for a good cipher will not be linear. But are there any proofs
> that the problem is intractable for real ciphers?
How would you prove that? You can show it as a list of non-linear
equations, but someone might find a polynomial time solution.
[....]
> Now I rather strongly suspect that if I extended this to 16-round
> CAST, got a big collection of such assertions, handed them to an
> equation-solver & asked it for the key, I'd have a spectacularly
> long wait.
symbolic equation solvers need hand holding. Our brains see
patterns, computers don't. While we don't know what thinking is,
combined with computer tools we can do a lot. You can't just
hand over a set of equations and wait, you have to help guide the
solver. Along the way, you get good at being a guide :-)
> But can we prove the project is doomed from the start because I'd
> need more than 2^64 different plaintexts & that's not possible?
> This would prove this CAST immune to this attack in just the way
> various ciphers are shown to be immune to differential or linear
> cryptanalysis.
>
> Or, given that CAST uses bent functions as s-box columns and that
> overall s-box non-linearity is high, can we prove some interesting
> lower bound on the work required to solve that system of equations?
>
> Is there perhaps even an obvious bound because equation-solvers use
> a form of search?
I don't think anything is obvious. This is a *very* difficult problem,
otherwise it would have been done already. The NSA probably has a few
people working on it, but they can't tell us what they know.
I think a good place to start would be Terry Ritter's 4 and 8 bit ciphers.
He's trying to create systems which can be analyzed and scaled up to
128 bits or more and have provable security. With 8 bits, you can write
out all the equations and have a chance at solving them.
Finding solutions to nonlinear functions is also difficult. But it could
be exceptionally useful in helping to find optimal functions for ciphers.
Some work has been done on nonlinear functions, check out Eurocrypt and
crypto conference proceedings.
Nice idea, keep pounding on it!
Patience, persistence, truth,
Dr. mike
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:13:58