Cryptography-Digest Digest #364, Volume #13 Tue, 19 Dec 00 11:13:01 EST
Contents:
Re: Nonlinearity question ([EMAIL PROTECTED])
Re: does CA need the proof of acceptance of key binding ? (Timothy M. Metzinger)
Re: Homebrew Block Cipher: Moonshine (Tim Tyler)
Re: Software PRNG.. (Tim Tyler)
Re: Software PRNG.. (Tim Tyler)
Christmas cipher message ("Keith Searing")
Re: Result of an old thread? (Benjamin Goldberg)
Re: Result of an old thread? ("Jakob Jonsson")
Re: Why primes? (digiboy | marcus)
Re: Result of an old thread? ("Jakob Jonsson")
Re: Nonlinearity question ("Jakob Jonsson")
Re: Result of an old thread? (Mok-Kong Shen)
In today´s paper I read how Cuban intelligence bosses are using shortwaves and the
Morse code to communicate with their intelligence agents in Miami .... interesting ..
when I was in California (I think) I got some strange messages to my head .. (Markku
J. Saarelainen)
Re: In =?iso-8859-1?Q?today=B4s?= paper I read how Cuban intelligence (Volker
Hetzer)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Nonlinearity question
Date: Tue, 19 Dec 2000 10:54:24 GMT
In article <[EMAIL PROTECTED]>,
Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> Hmm, I just discovered that Tom Denis's TC3 implements this very idea.
>
> I suppose for analysis I'll just wait for his paper :)
The idea is bad, if you are relying on just this. If you combine the
invert with some unrelated operation it might be ok.
The invert has excellent resistence to differential and linear attacks.
Unfortunately it has no resistence to algebraic attacks such as the
interpolation attack.
In the case of TC3 the whole thing of N rounds is the same as
( a * x + b ) / ( c * x + d )
where x is the plaintext and a, b, c, d are key dependent constants.
Provided b is not zero (and it hardly ever is zero) you can normalise it
to have b=1. Then you have three unknowns to find (a, c, d). Three known
plaintext/cyphertext pairs will give you three linear equations and
provided they are linearly independant you can solve them.
Note that the model above fails if the input to any of the inversions is
zero. But, with a 128 bit block, that hardly ever happens.
Conclusion: TC3 is broken. Very badly broken.
Exercise for the student: can this be applied to Rijndael?
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (Timothy M. Metzinger)
Date: 19 Dec 2000 11:37:35 GMT
Subject: Re: does CA need the proof of acceptance of key binding ?
In article <[EMAIL PROTECTED]>, Mok-Kong Shen
<[EMAIL PROTECTED]> writes:
>My poor knowledge does not allow me to answer your question
>in concrete terms. But I believe that it is indispensable
>for the CA to be able to well bind the a key to the physical
>person once and with that to later verify communications from
>him and for that there is apparently no other secure means
>than the convential ones of proving identity. Of course one
>CA could rely on another CA, but at least one CA must do the
>work. One problem that is in my view not resolved (resolvable)
>is that the CA must be trusted and that is a subjective matter.
Typically in PKIs designed for high assurance, the binding between the key
pair(s) and the individual is accomplished by a Registration Authority (RA).
The RA performs a face-to-face validation of identity, and then the individual
generates the key pair(s) in the presence of the RA, and gives the public
portion to the RA. The RA sends the public key with a request for a digital
certificate to the CA in a signed message. The CA trusts the RA and thus
generates the certificate and signs it.
There are variations on this, but in all cases there is a face-to-face
verification of identity.
The CA is the root of trust for all the certificates it issues - there's no way
around the fact that the CA must be trusted. Relying parties have to look at
the policies and procedures for the operation of the CA and decide how much
trust to place in it.
Timothy Metzinger
Commercial Pilot - ASMEL - IA AOPA Project Pilot Mentor
'98 M20J - N1067W
Pipers, Cessnas, Tampicos, Tobagos, and Trinidads at FDK
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Homebrew Block Cipher: Moonshine
Reply-To: [EMAIL PROTECTED]
Date: Tue, 19 Dec 2000 11:58:59 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: Why do you feel that a Feistel is bad?
Here's my (simplistic) perspective of what's wrong with Feistel networks:
Feistel networks keep half the round effectively unchanged. This
means that half the round's output is a trivial linear function of
that round's inputs.
Feistel networks are used with balanced s-boxes. Balanced s-boxes
alone are sufficient to produce permutations. The Feistel network is
another method of generating permutations. As such it is unnecessary -
all you need are a collection of balanced s-boxes.
Keeping half the round unchanged is wasteful in terms of getting maximum
confision in hardware implementations. One half of the round is being fed
through s-boxes - this takes time. The other half of the round is just
sitting around doing nothing while this happens. Instead it could
usefully be subject to confusion. [This objection is only true if there's
some sort of diffusion applied between rounds, which means that the
outputs from the previous round are all needed before processing of the
next section can start].
If hardware speed is a significant factor, ISTM that use of a Feistel
network is not going to give you the greatest bangs for your buck.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Free gift.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Software PRNG..
Reply-To: [EMAIL PROTECTED]
Date: Tue, 19 Dec 2000 12:07:45 GMT
Jorgen Hedlund <[EMAIL PROTECTED]> wrote:
:
: And these "algorithms" (?) are implementable in software? It sounds like
: true hardware stuff. [...]
Such algorithms do work rather nicely in hardware - but you can do them in
software.
: It seems also that if one should be able to create something truly
: random, one needs to "connect" with the analogue world in some way. []
: For instance when they (Sun? Sgi?) took a lavalamp and filmed it (?)
http://lavarand.sgi.com/
: and then used the information to create some random series.
You stared the thread asking for a software *P*RNG.
It now sounds like what you /really/ want is a hardware RNG.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Software PRNG..
Reply-To: [EMAIL PROTECTED]
Date: Tue, 19 Dec 2000 12:11:13 GMT
kimpert <[EMAIL PROTECTED]> wrote:
: [EMAIL PROTECTED] says...
:> Are there any (good) software PRNG's on the net, that is also free?
: Here's one place to start. Actually, it was recommended to me in this
: ng a few years ago for a simulation program I have. I wanted some
: PRNG code that was fast and likely to be "more random" the the rand()
: function in the MSVC++ library.
: http://www.math.keio.ac.jp/%7Ematumoto/emt.html
: It's called the Mersenne Twister. [...]
*Don't* use this for the OP's "simple stream cipher driven from
a long-period pseudo-random number generator (PRNG)", though -
since it wasn't designed with that application in mind.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: "Keith Searing" <[EMAIL PROTECTED]>
Subject: Christmas cipher message
Date: Tue, 19 Dec 2000 13:40:46 -0000
Once again I'm seeking help to decipher a seasoonal message in a deviuos
christmas quiz. I'm no cryptographer, so I haven't a chance with this. All
assistance welcomed (and it is legit - teams can be of any size!)
Thanks, Keith
An easy cipher this year, though the following plaintext is not easy at all.
THE HOLIDAY SEASON IS KEPT FOR THE PIANISTS, BUT THEY PRAY THAT ANY MUSICAL
PIECE (HARMONIOUS OR OTHERWISE) IS LESS THAN AN HOUR LONG. THE TIME MUSIC
PLEASANTLY OCCUPIES IS TIME THAT PEOPLE AND ANGELS CAN RELAX.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Result of an old thread?
Date: Tue, 19 Dec 2000 13:42:23 GMT
Mok-Kong Shen wrote:
>
> Jakob Jonsson wrote:
> >
> [snip]
> > To find a nonsingular matrix you will have to guess, but in GF(q)
> > the probability that a random nxn matrix is nonsingular is quite
> > high, at least 0.28 for q=2, higher for larger q, and close to 1 for
> > very large q (*), so if you simply choose parameters at random, you
> > will find a nonsingular matrix pretty soon.
> >
> > (*) The number of nonsingular nxn matrices in GF(q) is
> > (q^n-1)*(q^n-q)*(q^n-q^2)*...*(q^n-q^{n-1}). To get the fraction P
> > of nonsingular matrices, divide each factor with q^n and compute the
> > log of the result. You obtain
> >
> > log(P) = log(1-1/q) + log(1-1/q^2) + log(1-1/q^3) + ...
> >
> > Now approximate.
>
> But we don't have a 'random' matrix in the full sense,
> i.e. the elements are partly related to one another
> due to the Gaussion method ('the parameters') isn't it?
The formulae above are for the *generation* of A, B, and S. What Jakob
Jonsson is saying is that we can create A and B very easily, by
producing a completely random matrix, again and again, until we find one
that is nonsingular (and thus invertable). This will work because the
probability of a random matrix being nonsingular is very high. The
reason why this is important to know, is that randomly filling a matrix
is much faster and easier than computing one to be singular in some
byzantine manner.
--
There are three methods for writing code in which no bug can be found:
1) Make the code so straightforward that there are obviously no bugs.
2) Make the code so complicated that there are no obvious bugs.
3) Insist that any apparent bugs were really intentional features.
------------------------------
From: "Jakob Jonsson" <[EMAIL PROTECTED]>
Subject: Re: Result of an old thread?
Date: Tue, 19 Dec 2000 15:09:18 +0100
"Benjamin Goldberg" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Jakob Jonsson wrote:
> >
...
> > > > X = AS,
> > > > Y = SB,
> > > > Z = ASB.
...
> > All solutions can be found efficiently via Gaussian elimination in the
> > usual manner. We won't get stuck. Instead we will get a bunch of zero
> > rows in the matrix X, and since there are solutions to the equation
> > X*W = Z, the corresponding rows in Z will be zero as well. Just drop
> > these rows and solve the remaining system. You will obtain some
> > parameters (one parameter in each column of W for each zero row in X
> > after Gaussian elimination) in your solution. For example, with two
> > zero rows in a 4x4 matrix system, the solution in one column of W will
> > be something like
> >
> > w_1 = a s + b t + c
> > w_2 = d s + e t + f
> > w_3 = s
> > w_4 = t,
> >
> > where s and t are parameters and a,b,c,d,e,f are known constants. Any
> > values on s and t will give a solution.
>
> But does this allow you to find the original matrix S?
>
> Especially considering that if the implementor is smart, he'll choose it
> in some way OTHER than simply putting in an all zeros row or column.
>
> It's relatively easy to find singular matrices that have all elements
> nonzero, all it takes is a careful choice of values along the diagonal.
I was referring to the matrix obtained from X after Gaussian elimination.
The original matrix X does not have to be of this simple form. I am sorry if
I wasn't very clear on that point. What I want to find via this procedure is
W; S is obtained by multiplying SB with the inverse of W.
> > To find a nonsingular matrix you will have to guess, but in GF(q) the
> > probability that a random nxn matrix is nonsingular is quite high, at
> > least 0.28 for q=2, higher for larger q, and close to 1 for very large
> > q (*), so if you simply choose parameters at random, you will find a
> > nonsingular matrix pretty soon.
>
> Hmm, does this work for GF(2^N) as well as GF(p) ?
Yes, you have q^n-1 choices for the first row in the matrix (any row except
the zero row), q^n-q choices for the second row (any row except multiples of
the first row), q^n-q^2 for the third row (any row except linear
combinations of the first two rows), and so on. This is true for any prime
or prime power q.
> BWT this forumula indicates that for q=2, P=0.288788095 for 30 terms.
> Rounding to 2 significant digits results in P=.29 (where earlier you
> said .28)
Of course you are right; I felt that 0.288... is not "at least" 0.29 since
it is less than 0.29.
Jakob
------------------------------
From: digiboy | marcus <[EMAIL PROTECTED]>
Subject: Re: Why primes?
Date: Tue, 19 Dec 2000 13:55:47 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> The replies has given me something with
> substance to work with. I will have to
> use a pen and paper for a while, trying
> to see, for myself, what you're explaining.
My response is somewhat pointless, but if anyone sifting through didn't
understand the rest :
In simple terms, factoring a number made up of primes is harder.
With QBNs there are likely to be many factors that can be used as
shortcuts.
> I do own a crypto book (or two if one
> counts the Code Book),
Hehe the Code Book is fun.
--
[ marcus ] [ http://www.cybergoth.cjb.net ]
[ ---- http://www.ninjakitten.net/digiboy ]
[ prime numbers are the crypto gods ----- ]
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "Jakob Jonsson" <[EMAIL PROTECTED]>
Subject: Re: Result of an old thread?
Date: Tue, 19 Dec 2000 15:30:59 +0100
> But we don't have a 'random' matrix in the full sense,
> i.e. the elements are partly related to one another
> due to the Gaussion method ('the parameters') isn't it?
You are right in that the set of all possible solutions W to the equation
XW= Z is not necessarily distributed in the same manner as the set of all
matrices, so this will need some further analysis. Intuitively, I feel that
the fraction of nonsingular matrices should increase with the rank of X and
Z (which is the same as the rank of S), but I don't know.
Jakob
------------------------------
From: "Jakob Jonsson" <[EMAIL PROTECTED]>
Subject: Re: Nonlinearity question
Date: Tue, 19 Dec 2000 15:44:56 +0100
See http://www.ii.uib.no/~larsr/papers/interpol.ps.Z for further details on
interpolation attacks (cited in the Rijndael spec, section 8.5)...
Jakob
<[EMAIL PROTECTED]> skrev i meddelandet
news:91neou$hs0$[EMAIL PROTECTED]...
> In article <[EMAIL PROTECTED]>,
> Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> > Hmm, I just discovered that Tom Denis's TC3 implements this very idea.
> >
> > I suppose for analysis I'll just wait for his paper :)
>
> The idea is bad, if you are relying on just this. If you combine the
> invert with some unrelated operation it might be ok.
>
> The invert has excellent resistence to differential and linear attacks.
> Unfortunately it has no resistence to algebraic attacks such as the
> interpolation attack.
>
> In the case of TC3 the whole thing of N rounds is the same as
>
> ( a * x + b ) / ( c * x + d )
>
> where x is the plaintext and a, b, c, d are key dependent constants.
> Provided b is not zero (and it hardly ever is zero) you can normalise it
> to have b=1. Then you have three unknowns to find (a, c, d). Three known
> plaintext/cyphertext pairs will give you three linear equations and
> provided they are linearly independant you can solve them.
>
> Note that the model above fails if the input to any of the inversions is
> zero. But, with a 128 bit block, that hardly ever happens.
>
> Conclusion: TC3 is broken. Very badly broken.
>
> Exercise for the student: can this be applied to Rijndael?
>
>
> Sent via Deja.com
> http://www.deja.com/
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Result of an old thread?
Date: Tue, 19 Dec 2000 15:46:31 +0100
Benjamin Goldberg wrote:
>
> Mok-Kong Shen wrote:
> >
> > Jakob Jonsson wrote:
> > >
> > [snip]
> > > To find a nonsingular matrix you will have to guess, but in GF(q)
> > > the probability that a random nxn matrix is nonsingular is quite
> > > high, at least 0.28 for q=2, higher for larger q, and close to 1 for
> > > very large q (*), so if you simply choose parameters at random, you
> > > will find a nonsingular matrix pretty soon.
> > >
> > > (*) The number of nonsingular nxn matrices in GF(q) is
> > > (q^n-1)*(q^n-q)*(q^n-q^2)*...*(q^n-q^{n-1}). To get the fraction P
> > > of nonsingular matrices, divide each factor with q^n and compute the
> > > log of the result. You obtain
> > >
> > > log(P) = log(1-1/q) + log(1-1/q^2) + log(1-1/q^3) + ...
> > >
> > > Now approximate.
> >
> > But we don't have a 'random' matrix in the full sense,
> > i.e. the elements are partly related to one another
> > due to the Gaussion method ('the parameters') isn't it?
>
> The formulae above are for the *generation* of A, B, and S. What Jakob
> Jonsson is saying is that we can create A and B very easily, by
> producing a completely random matrix, again and again, until we find one
> that is nonsingular (and thus invertable). This will work because the
> probability of a random matrix being nonsingular is very high. The
> reason why this is important to know, is that randomly filling a matrix
> is much faster and easier than computing one to be singular in some
> byzantine manner.
Probably I haven't understood. But if a n*n matrix A is
of rank n-1, then Ax=v has solution that has only one
degree of freedom, although x has n elements. Thus
the n elements of x is equivalent to only one random
variable (the n values are related). In the analogous
situation of AY=U, we therefore can't say that Y has n*n
random variables.
M. K. Shen
------------------------------
From: Markku J. Saarelainen <[EMAIL PROTECTED]>
Crossposted-To: alt.2600,alt.security,comp.security
Subject: In today´s paper I read how Cuban intelligence bosses are using shortwaves
and the Morse code to communicate with their intelligence agents in Miami ....
interesting .. when I was in California (I think) I got some strange messages to my
head ..
Date: Tue, 19 Dec 2000 14:51:34 GMT
It was the Morse code for "SOS" ... and I understood it, but did not
really know what was going on, but it was very very strange, because I
had not had similar experiences before .. but in the next news that I
read, I read about the accident of the nuclear submarine Kursk. So I
realized something ...
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Crossposted-To: alt.2600,alt.security,comp.security
Subject: Re: In =?iso-8859-1?Q?today=B4s?= paper I read how Cuban intelligence
Date: Tue, 19 Dec 2000 16:51:44 +0100
"Markku J. Saarelainen" wrote:
>
> It was the Morse code for "SOS" ... and I understood it, but did not
> really know what was going on, but it was very very strange, because I
> had not had similar experiences before
Y'know, many cellphones emit the morsecode for SMS when a sms is received.
Those two messages are rather familiar. It couldn't just be a mobile you've
heard?
Greetings!
Volker
--
Windows has detected that your mouse pointer has moved.
Your computer will have to restart for this change to take effect.
Do you wish to restart now (Y/N)?
------------------------------
** 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
******************************
