Cryptography-Digest Digest #735, Volume #11 Mon, 8 May 00 20:13:01 EDT
Contents:
Re: An argument for multiple AES winners (Mok-Kong Shen)
Re: Compression as decryption (Mok-Kong Shen)
Re: An argument for multiple AES winners (Anton Stiglic)
Generator for ElGamal? ([EMAIL PROTECTED])
Analysis of LETSIEF2 (David A. Wagner)
Re: Generator for ElGamal? (David A. Wagner)
Re: Why no civilian GPS anti-spoofing? / proposal (Dave Ashley)
Analysis of MMBOOZE (David A. Wagner)
Re: Analysis of LETSIEF2 ("Adam Durana")
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: An argument for multiple AES winners
Date: Mon, 08 May 2000 23:19:04 +0200
Anton Stiglic write:
> You are calculating the probability in the wrong way.
> It's not an *and*, but an *or*. If you have 3 algos,
> with probability of p1 that the first will have a component
> that is patented, p2 for the second and p3 for the last,
> the probability that the whole has a component that is
> patented is p1 + p2 + p3, which is >= to any single pi.
>
> This comes from the fact that you are reliable for what
> you have done in the past (if you used a patented
> algorithm in the past, they can sue you).
>
> The more algos you use, the greater the risk of having
> a patent attack.
I am not sure that, if I use an algorithm that incorporates a hidden
patent, I would have to pay anything to the patent holder for
usage of the algorithm BEFORE his notice, as long as the general public
also doesn't have any knowledge of the involvement of the hidden
patent. (I am absolutely unconscious of my guilt.) On the other hand,
if my application has been tightly geered to that algorithm and (for
whatever reasons -- there could be many) I have no appropriate
algorithm to substitute the algorithm now known to have patent claims,
then I am really caught.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Compression as decryption
Date: Mon, 08 May 2000 23:18:54 +0200
"Pred." wrote:
> > Do you intend to hide your 'new algorithm' from the opponent?
>
> No. It would be public. But the compression codec would be new in the
> sense that it would be carefully designed with respect to encryption.
> As an example, any frequency tables would be encrypted and the
> placement of it would depend on the key.
>
> What I think, is that adding a compressor - when correctly designed -
> would make it very difficult to attack it with differential analysis.
>
> (Correctly designed meaning something like what David is talking about
> on http://members.xoom.com/ecil/compress.htm)
>
> No easy answers I guess, but can we say *something* about this?
Risking to be flamed by experts, I like to express my view that a
compressor without giving the opponent easy means to find the
frequency table or the equivalent is doing a substitution and in that
sense is performing a non-trivial encryption step in combination
with the proper encryption algorithm that follows it. Thus the
compressor contributes positively. On the other hand, it is a
well-known fact in practical cryptology that one can't rigorously
quantify the strength of encryption algorithms and that in almost all
cases subjectivity cannot be eliminated from evaluations. Thus that
'something' that you demanded must by necessity be quite fuzzy,
even though experiences might help in building one's judgement in
concrete situations, like old fishermen can often predict the weather
of the following day with fair accuracy. (But one is of course
entirely free to accept or reject stuffs of such nature.)
M. K. Shen
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: An argument for multiple AES winners
Date: Mon, 08 May 2000 17:21:35 -0400
Mok-Kong Shen wrote:
> Anton Stiglic write:
>
> > You are calculating the probability in the wrong way.
> > It's not an *and*, but an *or*. If you have 3 algos,
> > with probability of p1 that the first will have a component
> > that is patented, p2 for the second and p3 for the last,
> > the probability that the whole has a component that is
> > patented is p1 + p2 + p3, which is >= to any single pi.
> >
> > This comes from the fact that you are reliable for what
> > you have done in the past (if you used a patented
> > algorithm in the past, they can sue you).
> >
> > The more algos you use, the greater the risk of having
> > a patent attack.
>
> I am not sure that, if I use an algorithm that incorporates a hidden
> patent, I would have to pay anything to the patent holder for
> usage of the algorithm BEFORE his notice, as long as the general public
> also doesn't have any knowledge of the involvement of the hidden
> patent. (I am absolutely unconscious of my guilt.) On the other hand,
> if my application has been tightly geered to that algorithm and (for
> whatever reasons -- there could be many) I have no appropriate
> algorithm to substitute the algorithm now known to have patent claims,
> then I am really caught.
The thing is that you will be sued for what you used in the past. If
your system ever used the algorithm in the past, then you can get sued.
That's the bottom line.
If you are talking about hiding the truth, or the fact that you used such
or such algorithm, that is something else.
This was discussed by some at AES3, people have misconceptions about
this fact.
Anton
------------------------------
From: [EMAIL PROTECTED]
Subject: Generator for ElGamal?
Date: 8 May 2000 22:12:58 GMT
I was just looking at a piece of code that purported to implement
ElGamal, and noticed they weren't making any checks to make sure that
the "g" was really a generator. I knew that they used Schneier's
Applied Cryptography as a reference, so looked in there and he says to
just use a random g (which they have faithfully implemented)!
Surely this is a mistake, right? The public key must include a pair
<g,p>, where g is a generator for p.
I checked the errata for Schneier's book, and it didn't say anything
about this. Am I missing something really obvious here?
--
Steve Tate --- srt[At]cs.unt.edu | Gratuitously stolen quote:
Dept. of Computer Sciences | "The box said 'Requires Windows 95, NT,
University of North Texas | or better,' so I installed Linux."
Denton, TX 76201 |
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Analysis of LETSIEF2
Date: 8 May 2000 14:54:41 -0700
LETSIEF2 was proposed for the sci.crypt cipher contest, and has
some interesting features. But, after a short look at it, I'm
thinking there might be an attack here that works with something
like O(2^32) chosen texts and comparable complexity.
If there are no mistakes, it looks like this should be enough to
recommend that LETSIEF2 not be deployed in production systems.
But maybe I made some mistake or overlooked something.
What do you think -- does the following work?
We have two useful truncated differentials for one round of LETSIEF
that take the following form:
(0,x) -> (y,0) with probability 1, and
(y,0) -> (0,y) with probability 1/256,
where x,y represent arbitrary non-zero 32-bit values. Consequently,
if we concatenate them, we get the following truncated differential for
12 rounds (i.e., the entire LETSIEF2 cipher):
(0,x) -> (0,y) with probability 1/2^48.
This useful observation is due to Matthew Fisher.
I suggest the following attack. Obtain 2^32 chosen plaintexts whose left
half is fixed and whose right half varies over all 32-bit possibilities.
This gives us 2^63 pairs of texts, and count the number of pairs
of ciphertexts that agree in their left half. We expect 2^63/2^48 =
2^15 of the pairs to follow the truncated differential in all 12 rounds.
For each of the remaining 2^63 - 2^15 pairs, we expect the ciphertexts to
behave approximately randomly, so the left halves of their ciphertexts
should be equal with probability 1/2^32. This gives us an additional
(2^63 - 2^15)/2^32 ~=~ 2^31 pairs of matching ciphertexts.
In total, for LETSIEF2, we expect to see about 2^31 + 2^15 matching
ciphertexts. In comparison, for a random permutation (i.e., an ideal
cipher), the expected number of matching ciphertexts is 2^63/2^32 =
2^31, with standard deviation approximately 2^15.5. Thus, the number of
matching ciphertexts for LETSIEF2 will be about 2^-0.5 ~=~ 0.71 standard
deviations above what we'd expect for an ideal cipher, so this the
signal is just barely above the noise, and this should let us distinguish
LETSIEF2 from an ideal cipher and be correct about 72% of the time.
The distinguishing probability can be improved by repeating the attack
for several values of the left half. In this way, with something like
2^38 chosen texts we can probably distinguish LETSIEF2 from an ideal
cipher with a nearly-negligible probability of error.
It may also be possible to turn this into a slightly better attack
(fewer texts & ability to recover key mterial, but possibly larger
workfactor) by using an 11-round truncated differential (with prob.
1/2^40) combined with a 1-R analysis. However, this would take more
work to carefully analyze the complexity of the resulting attack and
check whether it can be made to work.
Anyway, if the above is correct, it is pretty good evidence that LETSIEF2
does not seem to exhibit the level of security we've come to expect from
modern ciphers, and perhaps the design should be re-considered.
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Generator for ElGamal?
Date: 8 May 2000 15:04:01 -0700
In article <8f7e5a$9uf$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
> I was just looking at a piece of code that purported to implement
> ElGamal, and noticed they weren't making any checks to make sure that
> the "g" was really a generator. I knew that they used Schneier's
> Applied Cryptography as a reference, so looked in there and he says to
> just use a random g (which they have faithfully implemented)!
>
> Surely this is a mistake, right? The public key must include a pair
> <g,p>, where g is a generator for p.
Hmm. If the adversary gets to choose g, then this is clearly a bad
idea, since there is no way to verify that g was indeed chosen randomly
("oops, you got g=1 this time, you must have just been unlucky!").
Perhaps what Schneier meant is the following: It is typically easy to
find a generator by just choosing random values and testing them until
you find one which is a generator; in practice, you won't have to try
too many times.
To check whether g is a generator, check that g^{(p-1)/q} != 1 mod p
for all prime factors q dividing p-1. This check is particularly easy
when p is a safe prime, i.e., (p-1)/2 is prime.
Actually, my personal belief is that in practice it is better to choose
to be a generator of a subgroup of (Z/pZ)^* of prime order q, where q is
sufficiently large. If q=(p-1)/2 is prime, this is easy: pick a random
element, square it mod p, and as long as the result isn't 0,1,-1 mod p,
the result generates a subgroup of order q. For DSA-subroups, where q
is 160 bits long, the corresponding algorithm isn't too much harder.
Then, check that everything you receive is a member of this subgroup.
In real-world implementation, it is also important to ensure that all
elements of (Z/pZ)^* are indeed in the range 2..p-2. (The special values
0,1,-1 mod p are bad, and the integers < 0 or > p are also bad, for if
you allow these inputs, there may be attacks. See, e.g., Bleichenbacher's
paper on El Gamal signatures.)
------------------------------
From: Dave Ashley <[EMAIL PROTECTED]>
Subject: Re: Why no civilian GPS anti-spoofing? / proposal
Date: Mon, 08 May 2000 22:48:26 GMT
It actually takes a lot to cause two commercial airliners to run into
each other. It happens very routinely that a pilot will wave off a
landing because he sees something he does not like, such as another
plane on the ground moving towards the runway. It would also be hard to
get one to smack into the ground at a place besides the runway. The
pilots are very aggressive about staying alive.
I agree that the "out of fuel" scenario seems most plausible. But,
still, this is difficult to engineer. The pilots have other
instruments, as well, and they might notice that they are going W when
they should be going E. And there would certainly be radio traffic when
the plane did not make an air traffic control handoff.
And, of course, for reliability, the B-word seems a better investment
than tampering with GPS.
Tampering with GPS signals just doesn't seem to be a reliable way to
down an airplane.
In article <lOsR4.7372$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> > Nobody said that. A few state-backed terrorists steering a
> > few jumbo commercial airliners way off course would certainly
> > be sufficient to terrorize the public.
>
> I think my problem with the whole scenario is two-fold. First, I'm
> basically as anti-gps as you can get. Having firsthand experience
> using it, I find it of very limited use as an _aid to
> navigation_. That's not to say it's a bad idea, or a waste of money,
> just that it's primarily useful for doublechecking your current
> location.
>
> Second, it just seems obvious to me that a state sponsored terrorist
> would have many cheaper/easier ways to terrorise air traffic than
> this.
>
> When you talk about sending planes off course though, the thought
> occours to me that while causing planes to collide is farfetched, it
> may be somewhat easier to keep one lost over the ocean long enough to
> run out of fuel, or some other navigational shenanegin.
>
> > The fact is, our technological infrastructure is exceedingly
> > fragile, a fact that has many people concerned (and occasionally
> > somebody actually working on the problem). The more one puts
> > his eggs all in one basket, especially a fragile one, the more
> > likely a catastrophe will occur.
>
> Well, as I said above, you should _not_ be putting your eggs all in
> the gps basket. Given that the navigator should still be navigating by
> hand, large deviations from the GPS fix will be obvious. The challenge
> then is to figure out which location is correct. Anywhere inside most
> nations air space this should be trivial, over blue water it's
> probably slightly more problematical.
>
> > The sad thing is that GPS is a nearly ideal application for
> > public-key cryptography (everybody could decode, but only the
> > system itself could encode), which would have solved the
> > spoofing problem.
>
> I don't know, my experience with gps is limited to little black boxes
> that I plugged into other little boxes. ;) I would think though, that
> there would always be at least an impractical spoofing
> attack. Assuming somehow the system sent a signal that everyone could
> decode, which only it could generate. Then, if I wanted you to think
> you were at point B rather than point A, why couldn't I go to B and
> transmit the signal to you? Assuming the points were close enough that
> you didn't notice the time difference, your equipment would assume it
> was at B.
>
> --
> Matt Gauthier <[EMAIL PROTECTED]>
>
--
=================================================
Dave Ashley, [EMAIL PROTECTED]
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Analysis of MMBOOZE
Date: 8 May 2000 15:50:48 -0700
I looked at MMBOOZE, a variation on MMB but with some interesting
new ideas, as proposed for the sci.crypt cipher contest. However,
I think there is a differential attack against it.
If I am right (and maybe I made some stupid mistakes), it looks
like the cipher may fall to attacks using O(2^25) chosen ciphertexts,
and this should be enough to re-consider the design of the cipher.
The problem is that avalanche is quite a bit worse in the reverse
(decryption) direction than in the forward (encryption) direction.
We have a truncated differential
00...000000ab000000..00
--decrypt-->
00...00000000cdef00..00
with probability 1/2^16 for decryption through one round of MMBOOZE,
where a,b,c,d,e,f represent arbitrary 8-bit differences.
As a slight variation, when a=b, the same 8-bit multiplier is used
in the first multiplication to encounter the ciphertext difference,
and in this case we have a separate truncated differential where e=f=0
that holds with the same probability. These two can be concatenated.
Finally, for the final decryption round, we can use this truncated
differential of probability 1:
00...000000cdef000000..00
--decrypt-->
??...??????????????00..00
where the question marks (?) represent arbitrary 8-bit differences
which aren't important enough to name with a letter.
If we start with the ciphertext difference 00aa00..00, I think that
after three rounds of decryption (i.e., MMBOOZE decryption) we get a
plaintext difference of the form ??????????????00..00 with probability
about 1/2^32. Thus, I suggest to obtain about 2^32 pairs of ciphertexts
with the required difference, and look for right pairs that follow the
truncated differential.
Note that we can obtain 2^15 pairs from 2^8 chosen ciphertexts using
the technique of structure. Thus, 2^17 * 2^8 = 2^25 chosen ciphertexts
should suffice to obtain the first right pair.
Each right pair suggests some subkey material, and this can probably be
fashioned into a key-recovery attack with the standard techniques of
differential cryptanalysis. This would need to be verified, of course,
but I think it should probably all work out.
There also seem to be other truncated differentials which have similar
probability but allow for more use of structures. I did not search very
hard for better truncated differentials, so it may be possible to greatly
improve the attack.
In any case, this does not look very good for the MMBOOZE cipher....
What do you think?
------------------------------
From: "Adam Durana" <[EMAIL PROTECTED]>
Subject: Re: Analysis of LETSIEF2
Date: Mon, 8 May 2000 19:30:34 -0400
I follow what you are saying here, but I do not fully understand
differential analysis yet. So I will have to rely on others to decide if
this is correct. With LETSIEF1, Boris emailed and confirmed that the attack
was real, and then I removed it. Obviously as more people participate in
the contest I can't expect everyone to be as honest as Boris. So if Boris
emails me or posts that this attack does work I will remove LETSIEF2 from
the listing. Or if no one proves that this attack does not work I will
remove LETSIEF2 from the listing.
And thanks for taking part in the contest!
If anyone needs the URL with the listing it is
http://www.wizard.net/~echo/crypto-contest.html
- Adam
"David A. Wagner" <[EMAIL PROTECTED]> wrote in message
news:8f7d31$k73$[EMAIL PROTECTED]...
> LETSIEF2 was proposed for the sci.crypt cipher contest, and has
> some interesting features. But, after a short look at it, I'm
> thinking there might be an attack here that works with something
> like O(2^32) chosen texts and comparable complexity.
>
> If there are no mistakes, it looks like this should be enough to
> recommend that LETSIEF2 not be deployed in production systems.
> But maybe I made some mistake or overlooked something.
> What do you think -- does the following work?
>
> We have two useful truncated differentials for one round of LETSIEF
> that take the following form:
> (0,x) -> (y,0) with probability 1, and
> (y,0) -> (0,y) with probability 1/256,
> where x,y represent arbitrary non-zero 32-bit values. Consequently,
> if we concatenate them, we get the following truncated differential for
> 12 rounds (i.e., the entire LETSIEF2 cipher):
> (0,x) -> (0,y) with probability 1/2^48.
> This useful observation is due to Matthew Fisher.
>
> I suggest the following attack. Obtain 2^32 chosen plaintexts whose left
> half is fixed and whose right half varies over all 32-bit possibilities.
> This gives us 2^63 pairs of texts, and count the number of pairs
> of ciphertexts that agree in their left half. We expect 2^63/2^48 =
> 2^15 of the pairs to follow the truncated differential in all 12 rounds.
> For each of the remaining 2^63 - 2^15 pairs, we expect the ciphertexts to
> behave approximately randomly, so the left halves of their ciphertexts
> should be equal with probability 1/2^32. This gives us an additional
> (2^63 - 2^15)/2^32 ~=~ 2^31 pairs of matching ciphertexts.
>
> In total, for LETSIEF2, we expect to see about 2^31 + 2^15 matching
> ciphertexts. In comparison, for a random permutation (i.e., an ideal
> cipher), the expected number of matching ciphertexts is 2^63/2^32 =
> 2^31, with standard deviation approximately 2^15.5. Thus, the number of
> matching ciphertexts for LETSIEF2 will be about 2^-0.5 ~=~ 0.71 standard
> deviations above what we'd expect for an ideal cipher, so this the
> signal is just barely above the noise, and this should let us distinguish
> LETSIEF2 from an ideal cipher and be correct about 72% of the time.
>
> The distinguishing probability can be improved by repeating the attack
> for several values of the left half. In this way, with something like
> 2^38 chosen texts we can probably distinguish LETSIEF2 from an ideal
> cipher with a nearly-negligible probability of error.
>
> It may also be possible to turn this into a slightly better attack
> (fewer texts & ability to recover key mterial, but possibly larger
> workfactor) by using an 11-round truncated differential (with prob.
> 1/2^40) combined with a 1-R analysis. However, this would take more
> work to carefully analyze the complexity of the resulting attack and
> check whether it can be made to work.
>
> Anyway, if the above is correct, it is pretty good evidence that LETSIEF2
> does not seem to exhibit the level of security we've come to expect from
> modern ciphers, and perhaps the design should be re-considered.
------------------------------
** 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 (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
