Cryptography-Digest Digest #192, Volume #14 Fri, 20 Apr 01 14:13:00 EDT
Contents:
Re: First cipher (David Wagner)
Re: Basic AES question ("Paul Pires")
Re: Minimal Perfect Hashing (David Wagner)
Re: Distinguisher for RC4 ("Tom St Denis")
Re: Reusing A One Time Pad ("Mark G Wolf")
Good textbooks on information theory (Joe H Acker)
what crypt algo is the smallest to code? ("diediedie")
Re: First cipher ([EMAIL PROTECTED])
Re: what crypt algo is the smallest to code? ("Tom St Denis")
Re: Note on combining PRNGs with the method of Wichmann and Hill ("Douglas A. Gwyn")
Re: First cipher ("Tom St Denis")
Re: First cipher ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: First cipher
Date: 20 Apr 2001 17:00:26 GMT
>How about something a little more
>useful, like pointers on how to cryptanalyze my cipher so I don't bug
>the group with the obvious?
Unfortunately, I don't know of any single good book on cryptanalysis,
but Biham and Shamir's _Differential cryptanalysis of the Data Encryption
Standard_ is a pretty darned good starting point. I've heard that this
book may be out of print; if so, the next-best alternative is to go to
Biham's web page and read his papers on differential and linear cryptanalysis.
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Basic AES question
Date: Fri, 20 Apr 2001 09:57:41 -0700
Tom St Denis <[EMAIL PROTECTED]> wrote in message
news:YIZD6.9551$[EMAIL PROTECTED]...
>
> "Paul Pires" <[EMAIL PROTECTED]> wrote in message
> news:UzZD6.16354$[EMAIL PROTECTED]...
> >
> > Tom St Denis <[EMAIL PROTECTED]> wrote in message
> news:v5ZD6.9193$[EMAIL PROTECTED]...
> > >
> > > "Lou Grinzo" <[EMAIL PROTECTED]> wrote in message
> > > news:[EMAIL PROTECTED]...
> > > > Thanks to Paul and the others for responding.
> > > >
> > > > As best I can tell from the replies, there doesn't seem to
> > > > be a technical reason for limiting keys to those three
> > > > sizes. General crypto theory strongly implies that using
> > > > other key sizes would have the predictable effect on the
> > > > strength of the encryption (longer == stronger), but that
> > > > hasn't been tested and proved to be the case. Correct?
> > >
> > > No whoever tolds you "longer == stronger" is an idiot. Look at designs
> like
> > > LOKI89 and FEAL as compared to DES and come back to the group :-)
> >
> > If you are going to make comparisons, don't you think they should
> > be apples to apples? How can you say anything about the effect
> > of the keysize if you are testing the idea on Algo A versus Algo B??
>
> Because if you followed the argument it was about "does longer keysize
> generally mean stronger". I was trying to show (in a futile attempt to use
> intelligence) that while LOKI used a longer key than DES (LOKI was suppose
> to be a "replacement") it was easier to break...
>
> Anyways.... LALALALALALALALALALALALALALALA
So glad I took the time to craft a reasoned and thoughtfull question and
supplied my thoughts on the subject (snipped and ignored).
If I just zipped off something snide to trivialize your point you might have
just blown me off.
Paul
>
> Tom
>
>
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Minimal Perfect Hashing
Date: 20 Apr 2001 17:01:44 GMT
>At 48 bits, nothing is truly "one way" - with some weeks of
>precomputation, you could use the Hellman time/memory tradeoff to
>build a store that would answer any preimage query in milliseconds. If
>I'm thinking about this right, it should be especially easy to use
>this on a bijective function.
In fact, on a bijective function, it's even easier: the
complexity per query goes down from ~ 2^32 to ~ 2^24.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Distinguisher for RC4
Date: Fri, 20 Apr 2001 17:03:46 GMT
"David Wagner" <[EMAIL PROTECTED]> wrote in message
news:9bppjj$9dq$[EMAIL PROTECTED]...
> David Formosa (aka ? the Platypus) wrote:
> >RC4 is a streem cyper/pydorandom number generator, while 3DES is a
> >block cyper. You can't replace RC4 with 3DES in most situtations.
>
> Nonsense. You can replace RC4 with 3DES-counter mode or 3DES-OFB mode.
I would suggest countermode since at least you're guaranteed a lengthly
period.
Tom
------------------------------
From: "Mark G Wolf" <[EMAIL PROTECTED]>
Subject: Re: Reusing A One Time Pad
Date: Fri, 20 Apr 2001 12:22:59 -0500
> Before patenting CryptoSauce, be sure you are not using Dynamic
> Substitution.
And what is this dynamic substitution of which you speak?
------------------------------
From: [EMAIL PROTECTED] (Joe H Acker)
Subject: Good textbooks on information theory
Date: Fri, 20 Apr 2001 19:26:50 +0200
Hi folks!
I already know a bit about information theory and once read the original
Shannon paper, but I'm looking for a good reference and/or introductory
text to general information theory. One of these excellent textbooks for
teaching that are understandable, aren't clutered with lemmas, but
provide all necessary information for applying the theory.
There are plenty of books about information theory, which one would you
recommend?
Regards,
Erich
------------------------------
From: "diediedie" <[EMAIL PROTECTED]>
Subject: what crypt algo is the smallest to code?
Date: Fri, 20 Apr 2001 17:38:38 GMT
encryption/decryption speed is not of any importance,just the size of the
actual crypt code, what would be suggested (for a public/secret key crypter)
? RSA perhaps?
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: First cipher
Date: Fri, 20 Apr 2001 08:53:52 -0800
"M.S. Bob" wrote:
>
> [EMAIL PROTECTED] wrote:
> >
> > "M.S. Bob" wrote:
> > >
> > > [EMAIL PROTECTED] wrote:
>
> As his says in his self-study course, there is no one good text on
> cryptanalysis of modern ciphers.
This is somewhat sad, given that there are textbooks out
there on some extremely complicated scientific/mathematical analysis
problems.
> The CD he mentions is worth getting BTW.
I'll look into that.
>
> > I found a paper in the Springer-Verlag Lecture Notes in Computer Science
> > Cryptography Proceedings (1982) which analyzed random, reversible
> > S-boxes.
> > Supposedly, if the S-box is reversible and the number of bits per table
> > entry is large, then the probability of a random S-box having one or
> > more bits that are linear functions of the address bits is low.
> >
> > So, for whatever reason, reversible S-boxes seem to be the way to go.
>
> Remember this paper pre-dates the (re-)discovery of differential
> cryptanalysis (by Biham and Shamir) at the Crypto '90 conference.
I'll have to go back and take another look at Schneier's "Self-Study
Course
in Cryptanalysis" which has been sitting on my computer for about a
month now
(heh,heh), but IMHO I think THIS would be the best place to start...to
go
back and dig up the original papers on the most useful cryptanalysis
techniques
being used today and follow that thread. My worry is that my limited
knowledge of pure math will keep me from understanding those types of
papers.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: what crypt algo is the smallest to code?
Date: Fri, 20 Apr 2001 18:07:19 GMT
"diediedie" <[EMAIL PROTECTED]> wrote in message
news:yu_D6.21072$[EMAIL PROTECTED]...
> encryption/decryption speed is not of any importance,just the size of the
> actual crypt code, what would be suggested (for a public/secret key
crypter)
> ? RSA perhaps?
What is your question? You want a small symmetric or asymmetric cipher?
Does it have to be secure? Work on what platforms? Can I make use of my
fake processors DWIM instruction?
Tom
------------------------------
Crossposted-To: sci.crypt.random-numbers
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Note on combining PRNGs with the method of Wichmann and Hill
Date: Fri, 20 Apr 2001 17:27:29 GMT
Mok-Kong Shen wrote:
> "Douglas A. Gwyn" wrote:
> > I recommend presenting the inverse-chi-square (e.g. using the
> > QChiSq function found in my ihat archive). That way the same
> > result can be directly compared to whatever significance level
> > the user chooses.
> Could you say a bit about your 'ihat archive'? (How to
> access that? Are there documents about the inverse-
> chi-square?)
It was included on the disks accompanying Applied Cryptography
under the file name I-HAT.ZIP. For your convenience and possible
general interest I have appended the documentation to this message.
> Sorry, either I misunderstood you or you misunderstood
> the current context. The current discussion is about
> testing the 'uniformity' of the output of PRNGs (or
> post-processed outputs of these), i.e. streams of
> real-valued numbers in [0,1). Do you mean using just
> two categories, i.e. [0,0.5), [0,5,1) in the chi-square
> test to determine whether a stream under study is
> uniform or not? (I suppose certainly not.)
The data that is collected should be analyzed in the best
possible way for testing the specific hypothesis. How to do
that would require much more explanation and experience than
I can convey here. The general point I was trying to make
is that there is no value in multiplying the number of
categories unless that allows a better comparison with the
theoretical expectation. Quite often a simple yes/no test
is all that is needed, and concentrating the information
contained in the observations as much as possible permits a
stronger test than spreading out the information.
NAME
chisq - independence tests for 2-way contingency tables
SYNOPSIS
#include "chisq.h"
/* The following functions are declared in this header file. */
double ChiSqTbl(int r, int c, const long *f, int *df);
double InfoTbl(int r, int c, const long *f, int *df);
DESCRIPTION
ChiSqTbl returns Pearson's Chi^2 statistic for the r-by-c
contingency table of observed frequencies of occurrence for each
combination of row and column categories stored in row-major order
in the vector starting at f. The computed number of degrees of
freedom is stored into the location pointed to by df.
Chi^2 =df Sum for i=0 to r-1 Sum for j=0 to c-1 of
(fij - fi. f.j / N)^2 / (fi. f.j / N) where the row and column sums
are denoted fi. =df Sum for j=0 to c-1 of fij and f.j =df Sum for
i=0 to r-1 of fij and the total number of occurrences is N =df Sum
for i=0 to r-1 Sum for j=0 to c-1 of fij . Terms involving zero
row or column sum are omitted and the returned number of degrees of
freedom are correspondingly reduced from the nominal value
(r-1)(c-1).
InfoTbl returns 2 times Kullback's Ihat(H1:H2) statistic for a
similar contingency table. The number of degrees of freedom
to be used when relating this statistic to the Chi^2 distribution
is stored into the location pointed to by df. (See DISCUSSION
below.)
2 Ihat(H1:H2) =df 2 Sum for i=0 to r-1 Sum for j=0 to c-1 of fij
log (N fij/ (fi. f.j)) where the row and column sums fi. and f.j
and the total number of observations N are the same as for
Pearson's Chi^2.
DISCUSSION
2 Ihat(H1:H2) represents twice the estimated information in favor
of hypothesis H1 over hypothesis H2 contained in the observed
frequencies, where the *null hypothesis* H2 is that the row and
column categorizations are statistically independent and the
*alternative hypothesis* H1 is that they aren't. This statistic
is asymptotically distributed as Chi^2 with (r-1)(c-1) degrees of
freedom; therefore by use of the QChiSq function (see gamma doc) it
can be converted to the probability that the statistic would be as
large as was observed if the categorizations really are
independent. This is of course the traditional use of Pearson's
Chi^2 statistic, which 2 Ihat approaches for large samples when H2
is true. The main difference is that Pearson's Chi^2 is not useful
for small sample sizes, whereas 2 Ihat fully takes into account
all available information for even the smallest samples.
2 Ihat(H1:H2) (along with its corresponding degrees of freedom for
use with QChiSq) is *additive* for independent samples, so that the
information can be accumulated over the course of many independent
experiments in order to improve one's ability to detect a violation
of the null hypothesis.
CAVEATS
Pearson's Chi^2 test is unreliable for low frequencies;
consequently it is usually recommended that categories be chosen to
tally at least 5 occurrences in each bin. However, excessive
combination of bins causes loss of information and consequently
loss of discriminating power. Because 2 Ihat is correct for any
sample size, it does not require combination of bins and is
therefore immune from this problem.
EXAMPLE
/*
Example program to read table dimensions, then frequencies,
and to print both statistics along with significance levels.
*/
#include <stdio.h>
#include <stdlib.h> /* for EXIT_SUCCESS */
#include "chisq.h"
#include "gamma.h" /* for QChiSq() */
#define MAXTBL 1000
static long f[MAXTBL]; /* frequency tallies */
static int r; /* # of rows */
static int c; /* # of columns */
#define x(i,j) f[(i)*c+(j)] /* convenient way to access freqs */
static void Calc(char *name,
double (*func)(int, int, const long *, int *)
)
{
int df; /* degrees of freedom for chi-square */
double stat = (*func)(r, c, f, &df); /* computed statistic */
/* print results */
if ( stat >= 0.0 )
(void)printf("%s = %5.2f\tdf = %2d\tq = %7.4f\n",
name, stat, df, QChiSq(stat, df)
);
else
(void)printf(stat < -3.5 ? "out of memory\n"
: stat < -2.5 ? "table too small\n"
: stat < -1.5 ? "negative frequency\n"
: "too many zeros\n"
);
}
int main(int argc, char *argv[])
{
register int i; /* row index */
register int j; /* column index */
while ( scanf("%d %d\n", &r, &c) == 2 ) /* start new table */
{
/* input tallies */
for ( i = 0; i < r; ++i )
for ( j = 0; j < c; ++j )
(void)scanf(" %ld", &x(i,j));
/* compute statistics and print results */
Calc("chisq", ChiSqTbl);
Calc("2info", InfoTbl);
}
return EXIT_SUCCESS;
}
FILES
chisq.h header file containing definitions
chisq.c source file for functions
REFERENCE
Solomon Kullback, "Information Theory and Statistics" (Dover,
1968).
SEE ALSO
gamma doc.
DIAGNOSTICS
Both these functions a return negative value for the statistic when
it cannot be meaningfully computed, as follows:
-1.0 too many 0 entries in the table (for ChiSqTbl, this means
insufficient degrees of freedom; for InfoTbl, this means
*every* entry in the table was 0)
-2.0 some frequency was specified as less than 0
-3.0 specified number of rows or columns was less than 2
-4.0 unable to dynamically allocate enough working storage
AUTHOR
Douglas A. Gwyn, ARL
NAME
gamma - gamma and related functions
SYNOPSIS
#include "gamma.h"
/* All the following functions are declared in this header file. */
double Gamma(double z);
double LGamma(double z);
double Factorial(int n);
double LFactorial(int n);
double BCoeff(int n, int k);
double Beta(double z, double w);
double PGamma(double a, double x);
double QGamma(double a, double x);
double Erf(double x);
double Erfc(double x);
double CPoisson(double x, int k);
double PChiSq(double chisq, int nu);
double QChiSq(double chisq, int nu);
DESCRIPTION
Gamma returns the real gamma function value Gamma(z) =df Integral
from 0 to infinity of t^(z-1) e^-t dt for z>0.
LGamma returns the value ln Gamma(z) for z>0.
Factorial returns the factorial function value n! =df Gamma(n+1)
for n>=0.
LFactorial returns the value ln n! for n>=0.
BCoeff returns the binomial coefficient value (n over k) =df n! /
(k! (n-k)!) for 0<=k<=n.
Beta returns the real beta function value B(z,w) =df Integral from
0 to 1 of t^(z-1) (1-t)^(w-1) dt for z>0 and w>0.
PGamma returns the incomplete gamma function value P(a,x) =df
(1/Gamma(a)) Integral from 0 to x of e^-t t^(a-1) dt for a>0 and
0<=x<=infinity.
QGamma returns the value 1-P(a,x).
Erf returns the error function value erf(x) =df (2/sqrt(pi))
Integral from 0 to x of e^-(t^2) dt.
Erfc returns the complementary error function value 1-erf(x).
CPoisson returns the cumulative Poisson probability value Px(<k),
which is the probability that the number of Poisson random events
occurring will be between 0 and k-1 inclusive, where the expected
mean is x.
PChiSq returns the value P(Chi^2 | nu), which is the probability
that the observed chi-square for a correct model will be
less than Chi^2, where nu is the number of degrees of freedom.
QChiSq returns the value 1-P(Chi^2 | nu), which is the probability
that the observed chi-square will exceed Chi^2 by chance even for a
correct model, where nu is the number of degrees of freedom.
All these functions return *approximations* to the exact results,
generally accurate to about seven significant digits.
CAVEATS
Overflow can occur.
Invalid parameters cause a diagnostic and termination of the
process.
FILES
gamma.h header file containing definitions
gamma.c source file for functions
AUTHORS
William H. Press, Brian P. Flannery, Saul A. Teukolsky, and William
T. Vetterling ("Numerical Recipes in C", Chapter 6)
Douglas A. Gwyn, ARL
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: First cipher
Date: Fri, 20 Apr 2001 18:08:41 GMT
<[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> "M.S. Bob" wrote:
> >
> > [EMAIL PROTECTED] wrote:
> > >
> > > "M.S. Bob" wrote:
> > > >
> > > > [EMAIL PROTECTED] wrote:
> >
> > As his says in his self-study course, there is no one good text on
> > cryptanalysis of modern ciphers.
>
> This is somewhat sad, given that there are textbooks out
> there on some extremely complicated scientific/mathematical analysis
> problems.
Not really. Analysis is just one of those subjects that never ends. Find
one good text that answers all questions about god? Or about how the human
brain works, or how to factor large integers, or how to remove money from
society or how to make good tv programs?
Answers to these questions will vary over time....
Tom
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: First cipher
Date: Fri, 20 Apr 2001 09:10:05 -0800
Mark Wooding wrote:
>
[snip]
Your last post was helpful. Two more questions:
1.) Would a separate SP network in the key schedule be a good way of
confusing the relationship between the subkeys? (I don't mean
modifying the cipher I posted, I'm asking in a general sense.)
2.) Due to your excellent explanation, I think I understand the
general idea of differential analysis. Are programs generally
used to take care of the plug and chug? Are there cryptanalysis
programs available or is is basically "roll your own"? Does
anyone use MATLAB for cryptanalysis applications?
>
> Crash course intro to differential cryptanalysis. Let E be some block
> cipher. I'll write XOR as + here, because it's easy. Choose some (any)
> input, and a difference d. Now, look at d' = E(x) + E(x + d) as we vary
> x (leaving d constant) -- we'll get any particular d' out with some
> probability (maybe 0 if it never happens). I tend to write this as
> d -> d' [p] for some probability 2^{-p} (so p might be infinite if the
> differential is impossible).
>
> It's obvious that, for any function, we have 0 -> 0 [0] (read: if we
> feed in two things that aren't different to this function, the outputs
> aren't different with probability 2^0 = 1; i.e., it's certain that when
> we put two equal things in, we get two equal things out).
>
> A nonbijective function whose domain isn't strictly larger than its
> range must have a collision: i.e., two inputs x and x' where F(x) =
> F(x'). This means that the differential d -> 0 [p] holds for some
> finite p.
>
> Once you have a collision in Feistel network's F function, something
> interesting happens. Here's a diagram of a Feistel networks with
> XOR-differences labelled on it:
>
> d 0
> | |
> |-d->F-0->+ [ probability 2^{-p} ]
> | |
> d 0
> | |
> +<-0-F<-0-| [ probability 1 ]
> | |
> d 0
>
> So we've manufactured a 2-round iterative characteristic with
> probability 2^{-p}. This is precisely the structure that broke DES.
>
> If I could find a structure like this in your cipher, I could break 12
> rounds with 2^{6p} chosen plaintexts. I suspect that the two rounds at
> the beginning and end can be disposed of fairly easily. (For example,
> given a guess at some key bits in the last round, there are only 2^5
> possible bit patterns for the key in the second round.) So you need to
> ensure that 2^{6p} plaintexts is more than the cipher can produce --
> i.e., that 6 p > 64. (That's where I got the 2^{-10} figure in my last
> article from.)
>
> Now, your F structure is nonbijective as it is. However, making it less
> bijective (e.g., by choosing unbalanced S-boxes) will just increase the
> probabilities of collisions, and make defending against the above attack
> harder.
>
> [Another bit of notation: t_i is a word with just bit i set.]
>
> -- [mdw]
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
