| |
 |
|
|
Science Forum Index » Cryptography Forum » determining differential characteristics...
Page 1 of 1
|
| Author |
Message |
| Chris Steele... |
 Posted: Wed Jul 23, 2008 1:57 am |
|
|
|
Guest
|
I am currently going through the Schneier self-study course, and have
managed now to break several of the recommended early breaks.
However, I am learning enough to know that there are some big holes in
my basic technique that I should be patching. The biggest of these is
in characteristic determination.
To be sure, one can make some intelligent guesses as to some emergent
characteristics just after reading the algorithm description (ie, the
1-round characteristic with p=1 in DES pops right out at you), but for
the more complicated ones, I'm confident that there is a method better
than a kind of linear cryptanalysis -- examining the relationship
between every possible plaintext under every possible key (in fact, if
you do this once you will never need it, even if it completed, due to
just being able to look up the plaintext/ciphertext combination).
I have been reading some of the papers on differential cryptanalysis,
including Biham and Shamir, but they tend to present cryptanalysis
with the characteristic more as a given and then discuss determining
right pairs to meet said characteristic, which is only helpful if you
are trying to extend or reproduce their attacks, not create new ones.
Any hints out there on how to get started in finding and choosing good
differential characteristics? Obviously, every algorithm is
different, but are there key things to look for in an algorithm
description, or something of that nature? |
|
|
| Back to top |
|
| David Wagner... |
| Posted: Thu Jul 24, 2008 2:27 pm |
|
|
|
Guest
|
Chris Steele wrote:
Quote: Any hints out there on how to get started in finding and choosing good
differential characteristics? Obviously, every algorithm is
different, but are there key things to look for in an algorithm
description, or something of that nature?
It's a bit of an art. It depends upon the structure of the algorithm.
One common structure is a Feistel block cipher, where the round F-function
is built up out of S-boxes. One often starts by identifying the entire
table of all possible differential characteristics for the S-boxes,
then tries to combine high-probability characteristics for the S-boxes
into high-probability characterics for the round F-function. Once one
has some high-probability characteristics for the round F-function,
this provides characteristics for a single round. Then one tries to
combine single-round characteristics into multiple-round characteristics;
iterative characteristics are often prized, for the latter.
This tutorial might be helpful:
http://www.engr.mun.ca/~howard/PAPERS/ldc_tutorial.ps
One useful notion here is counting the number of "active S-boxes", i.e.,
S-boxes where one uses anything other than the trivial characteristic
0 -> 0 (which has probability 1). This is probably most relevant to a
number of modern block ciphers, whose S-boxes were designed according
to the principle of ensuring that every non-trivial characteristic has
probability at most DPmax, for some threshold DPmax that is minimized;
one tries to construct a S-box that makes DPmax as small as possible.
This paper discusses a nifty reduction from finding characteristics with
the minimal number of "active S-boxes" to the network flow problem:
http://lasecwww.epfl.ch/php_code/publications/search.php?ref=Vau99b
Mitsuru Matsui has a paper where he describes a systematic search
procedure for finding many-round differential characteristics for DES
with the maximum possible probability:
Mitsuru Matsui, On correlation between the order
of S-boxes and the strength of DES, EUROCRYPT '94.
http://www.springerlink.com/content/l40u4gg10r1p5kt3/
Basically, he uses a clever branch-and-bound search to explore the
search tree of possible multi-round characteristics, given a list of
single-round characteristics sorted by decreasing probability.
Also, since you seem to be enjoying this, here's a paper I wrote that
discusses a broad class of attacks (at a high level) and how they are
related. At some point in your studies you might enjoy the paper, even
though it doesn't get into many concrete specifics.
http://www.cs.berkeley.edu/~daw/papers/commdiag-fse04.ps
The latter three papers are advanced material, and probably don't
make sense to spend much time on, until you feel reasonably comfortable
with the basics of differential cryptanalysis.
You might find Lars Knudsen's PhD thesis of interest; it discusses many
of these issues. |
|
|
| Back to top |
|
| Chris Steele... |
| Posted: Thu Jul 24, 2008 7:40 pm |
|
|
|
Guest
|
Excellent! Thanks indeed for these great resources. After spending
another day on things after my first post, I was able to determine
single-round characteristics much in the way you described (which
seems obvious now), but now I am working on choosing "better" multi-
round characteristics. I think that some of the papers you pointed
out will be very helpful for that.
BTW, this is not directed at David, but rather at anyone else who is
interested in starting the Schneier self-study. I am putting the
results of my learning experience on these algorithms up on the web.
Please feel free to peruse them if you get stuck or have some
interest; I can't promise that they are the best results possible, but
they all seem to work and have been a lot of fun to write. This
little site contains nothing but these results (currently for the
following), and will continue to be updated:
4-round DES
6-round DES
12-round DES without s-boxes
Generic Closed Cipher
RC5 with no rotations
http://tragoedia.weebly.com |
|
|
| Back to top |
|
| |
|
Page 1 of 1
All times are GMT - 5 Hours
The time now is Tue Oct 07, 2008 3:57 pm
|
|