Cryptography-Digest Digest #66, Volume #10 Tue, 17 Aug 99 18:13:03 EDT
Contents:
Re: Digital simulation (David Kessner)
Re: New encryption algorithm ([EMAIL PROTECTED])
Re: Q. a hash of a hash ... ("Brian McKeever")
Re: Q. a hash of a hash ... ("Brian McKeever")
Re: Triple DES (168bit) -- Triple DES (112bit) (Anton Stiglic)
Re: Cracking the Scott cryptosystems?
Re: How good is this quadratic sieve variation? (Bob Silverman)
Re: Triple DES (168bit) -- Triple DES (112bit) (Anton Stiglic)
Re: Triple DES (168bit) -- Triple DES (112bit) (Anton Stiglic)
Re: Q. a hash of a hash ... (Anton Stiglic)
VEA - Video Encryption Algorithm ([EMAIL PROTECTED])
Re: I HOPE AM WRONG (Guenther Brunthaler)
Re: frequency of prime numbers? (Guenther Brunthaler)
encyrption (greg pruitt)
Re: Q. a hash of a hash ... (John Myre)
Re: NIST AES FInalists are.... (wtshaw)
----------------------------------------------------------------------------
From: David Kessner <[EMAIL PROTECTED]>
Subject: Re: Digital simulation
Date: Tue, 17 Aug 1999 11:46:10 -0600
Reply-To: [EMAIL PROTECTED]
Wim Lewis wrote:
> Yah... first you design a CPU using logic gates, then you program it
> to execute your algorithm ... ;-)
>
> DES shouldn't be too hard to implement in hardware, especially if
> EWB lets has a ROM component (for the S-boxes). ARC4 might not be too
> hard either if you can build an 8-bit adder and an 8x256 bit memory.
I've designed both a CPU and DES into an FPGA. They are available
at http://www.free-ip.com. DES runs at 369 megabytes/second in a
commonly available FPGA!
David Kessner
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: New encryption algorithm
Date: Tue, 17 Aug 1999 17:58:16 GMT
[EMAIL PROTECTED] wrote:
>> [EMAIL PROTECTED] wrote:
>> But lets theoretically assume that this algorithm really is
>> revolutionary and that its author would be able to make money on
>> its patent. In this case how can he insure his idea from being
>> stolen by somebody else who could simply patent it first and become
>> the inventor of the algorithm in terms of law?
>
> You are right, this is difficult. (Actually, there is an easy answer:
> he should go and patent it, then reveal it.)
>
> In general, little consideration is given to this by people saying
> that a secret algorithm is not good, because:
>
> 1) there is no need of a "revolutionary algorithm". Triple-DES with
> whitening (...) should do just nicely for about any purpose
Does that mean that you find cryptography a dead science
with no need for developement and no room for new
algorithms?
I suppose you would have said the same (>1) about single DES
just a few years ago...
Bartosz Zoltak
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: "Brian McKeever" <[EMAIL PROTECTED]>
Subject: Re: Q. a hash of a hash ...
Date: Tue, 17 Aug 1999 12:11:16 -0700
Brian McKeever <[EMAIL PROTECTED]> wrote in message
news:7pahfe$a1h$[EMAIL PROTECTED]...
>
> I can't say anything for the specific case H=SHA1, but it seems to me that
> in general, we lose a lot of collision resistance. If we take H to be a
> random permutation of some set S (eg {0.. n -1}, for some n), then the
> probability of H(a) = H(b) a != b is 1/n. But consider p( H(H(a)) =
H(H(B))
> | a != b). I calculate this as 1/n + (n-1)/n * 1/n or about 2/n. We've
> about doubled the probability of a collision (which makes sense, since
there
> are 2 opportunities for collision).
>
> Brian
>
I of course meant to let H be a random function S -> S, rather than a random
permutation.
Brian
------------------------------
From: "Brian McKeever" <[EMAIL PROTECTED]>
Subject: Re: Q. a hash of a hash ...
Date: Tue, 17 Aug 1999 12:13:48 -0700
Anton Stiglic <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Helger Lipmaa wrote:
>
> > Let H be a hash function. If an adversary finds a collision to H (say
x!=y,
> > H(x)=H(y)) it has also a collision for H^2: x!=y but H(H(x))=H(H(y)).
> > If an adversary finds a collision to H^2 (say x!=y, H(H(x))=H(H(y))) it
may be
> > the case that H(x)!=H(y) but H(H(x))=H(H(y)) (in which case she has a
pair
> > z=H(x), w=H(y), z!=w, H(z)=H(y)) or H(x)=H(y) (in which case she has a
pair
> > x!=y, but H(x)!=H(y)). It is trivial establish which case holds.
> >
> > So in theory, double hashing does not help at all.
> >
> > Helger Lipmaa
> > http://home.cyber.ee/helger
>
> Ahh, thanks alot, this is exactly what I was looking for. You prooved
that
> we found a collision for H iff we found a collision for H^2, so H and
H^2
> are equaly collision resistant.
>
> Thanks..
>
>
> Anton
>
H and H^2 are *not* equally collision resistant. Helger said "If an
adversary finds a collision to H^2 (say x!=y, H(H(x))=H(H(y))) it may be the
case that H(x)!=H(y) but H(H(x))=H(H(y))". Also, reread the post of mine
that he was responding to.
Brian
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Triple DES (168bit) -- Triple DES (112bit)
Date: Tue, 17 Aug 1999 15:07:42 -0400
[EMAIL PROTECTED] wrote:
> Frank Piepiorra wrote:
>
> According to AC2 there is an attack against 3DES with two keys that
> allows
> to break the cipher with an effort of 2^120/p encryptions with p known
> plaintexts. For more than 256 known plaintexts this attack is faster
> than
> brute force. (P.C van Oorschot and M.J.Wiener 'A Known-Plaintext Attack
> on
> Two-Key Triple Encryption' Advances in Cryptology,
> EUROCRYPT '90 Proceedings, Springer 1991m pp. 318-325)
>
> 3DES with three different keys can be attacked with a meet-in-the-middle
> attack. It needs 2^112 encryptions (R.C Merkle and M. Hellman 'On the
> Security of Multiple Encryption'; Communications of the ACM, v.24, n.7,
> 1981, pp 465-467).
>
Isn't that paper, from Merkle and Hellman 1981, a discussion about an attack
against
3DES with 2 keys, using a meet-in-the-middle attack.
Also, Oorchot, Wiener, have a _known-Plaintext_ attack, see Eurocrypt '90.
I have not hurd of an attack on 3DES with 3 keys. Someone give me a ref if
------------------------------
From: <[EMAIL PROTECTED]>
Subject: Re: Cracking the Scott cryptosystems?
Date: Mon, 16 Aug 1999 22:44:31 +0200
On Sun, 15 Aug 1999, SCOTT19U.ZIP_GUY wrote:
> In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>
> >
> >> But I prefer the features that should be found
> >> on future ciphers for files. Namely a one bit change in input cahnges
> >> the whole file out.
> >
> >What's the use of it?
> The main reason for this is so that the whole file would
> have to be used for an attacker to break making it harder to
> break. Also if one use small common pharses the data is
> not spread out so it ie easyer to attack if it has the so called
> error recovery feature.
The benefit of this method depends on the size of the message but it isn't
very important in most cases.
Your wrapped PCBC mode doesn't add more than some bits of strength against
brute-force-attacks and it isn't even clear if it is able to add any
strength against other attacks - it reminds me on the reflector of an
enigma: It looks like a good idear but as long as no cryptanalysis is done
on this method we don't know whether it helps the cryptographer or the
attacker.
> >
> >It should be enough to add a checksum to find the error.
> No this just gives the attaker more infomation
If the cipher is strong it doesn't help to attack the cipher - think about
CBCC mode.
For a weak cipher it doesn't help too much not to use a checksum: If it is
neccessary to be able to check the integrity of the file wrapped PCBC
doesn't help and there has to be some additional check. In the other case
the attacker will be able to see whether he produced garbage or not.
> >
> >> One where the entropy of message is spread
> >> a lot better than the AES small black cipher with tiny keys.
> >
> >Why?
> same anwser as above.
> >
> >> ...
> >> Actually I prefer using pass pharse that are easy to rember too
> >
> >But what is the use of a huge key that contains only a small amount of
> >entropy?
> The huge key is just a consequence of the message. It is easier to
> change to a different keyenc.key file once in a while than having some
> fixed scheme to expand the key to fit the S-Box far better to let the
> users have a choice of any single cycle S-Box.
>
?
>
> >
> >> ...
> >> The design methods of the AES
> >> candidates means they can't be good for file or serious message
> >> protection.
> >
> >Why do you think so?
> >
> >All AES candidates were developed to withstand all known attacks.
> >
> >All of them are using more rounds than neccessary and the developers
> >tried to add as much security as possible against unknown attacks (the
> >unkeyed rounds in MARS, for example).
>
> They were not developed to minimize the possible recovery based on
> information theory.
> They where developed by people years behind what
> the NSA is most likely using. A smart person serious about encryption
> would assume in the design that some one could be more clever than he is.
This is why the AES candidates use more rounds than neccessary, why MARS
uses unkeyed rounds and so on.
Do you really think your cipher could be strong only because you are using
an unusual design?
Why do you think, NSA wouldn't be able to break a cipher that was
developed without any cryptanalytic knowledge?
> So the design should use the most amount of computer resourses for the
> job that can be talerated while minimizing the possiblity of solutions.
So you think your algorithm is secure because it is slow?
3DES is better than blowfish because it needs more time to do it's job?
Enterrottacher Andreas
[EMAIL PROTECTED]
[EMAIL PROTECTED]
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: How good is this quadratic sieve variation?
Date: Tue, 17 Aug 1999 17:13:28 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> Bob Silverman wrote:
> >
>
> > The basic problem is that one hopes that values of Q(x) are smooth
> > over an interval (say) [-M,M]. The best one can hope for is that
> > these values are going to be equal to about M sqrt(N)/sqrt(8) for
> > well chosen polynomials Q(x).
>
> For f(x) = x^2 mod N, is there any empirical estimate (rough values
> based on actual runs) of the probability of having f(x) smooth
> for x, say, in [h, 2h] (h = sqrt(N)) ?
>
> M. K. Shen
Yes. The actual probabilities follow theoretical estimates quite
well. The theoretical estimates can be taken from Dickman's function
[see Knuth vol 2 or my paper with Sam Wagstaff "A Practical
Analysis of the ELliptic Curve Factoring Algorithm, Math. Comp. 1993]
or from the theorem of Canfield, Erdos, & Pomerance. Basically,
the probability that a large integer y has all its prime factors less
than x is about u^-u where u = log y/log x.
A reason to prefer Dickman's function is that the large prime variation
allows one or two factors outside of the factor base. Dickman's
function can handle this. I can send code which will compute
Dickman's function, if you like. Send me private email.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Triple DES (168bit) -- Triple DES (112bit)
Date: Tue, 17 Aug 1999 15:13:43 -0400
The point of having a 168 bit key scheme is that, if in fact there are no
loop-holes
(no possible attacks other then brute force), the best way to attack is
by trying
each key, with 168 bits, it will take you a hell of alot more time than
with 56 bits.
Anton
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Triple DES (168bit) -- Triple DES (112bit)
Date: Tue, 17 Aug 1999 15:18:03 -0400
Good point. Of cours, if we only had a 64-bit block to encrypt, one would
use a 64 bit
key and the one-time pad scheme. The thing is that we have many more bits to
encrypt.
We can never get unconditional security. We just want to prevent an easy
brute force attack,
we don't want a scheme where we are using 128 bits, but an attacker only
needs 2^56 tries,
we want the attacker to need to search the entire 2^128 keys key space.
Attacks on 2 key 3DES have reduced the numbers of key tries needed.
Anton
John Savard wrote:
> "karl malbrain" <[EMAIL PROTECTED]> wrote, in part:
>
> >The key size never materially exceeds 64 bits with a 64 bit block cipher.
> >Triple DES materially extends the original 56 bit key size to 64 bits.
>
> Capturing 2^64 blocks of known plaintext may not be possible, even
> while performing 2^64 key trials is.
>
> Hence, while one may speak of the theoretical complexity of an attack
> as not being increased, in practice, there can be as many as (2^64)!
> keys for a 64-bit block cipher, and increasing the key size up to that
> limit can, under appropriate circumstances, genuinely add to the
> problem facing a cryptanalyst.
>
> John Savard ( teneerf<- )
> http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Q. a hash of a hash ...
Date: Tue, 17 Aug 1999 15:25:49 -0400
You should read his proof as follows:
1. First I proove that if I found a collision for H, I have one for H^2:
(this is easy): if I have x!= y and H(x) = H(y), then
of cours H(H(x)) = H(H(y)), and I have found
a colision for H^2.
2. Then I proove that if I found a collision for H^2, I have one for H:
if I have x!=y such that H(H(x)) = H(H(y)), then I have one
of two cases:
a: H(x) = H(y): in wich case I have a collison for H.
b: H(x) != H(y): in wich case I denote x' = H(x) and
y' = H(y). I can now say that y' != x' and H(x') = H(y').
So, to conclude, if I have a collison for H, I have one for H^2 (1),
and, the other way around, if I have a collison for H^2 I have one
for H (2).
It is a simple and nice proof, it prooves that H and H^2 are equaly
collision resistant.
Anton
------------------------------
From: [EMAIL PROTECTED]
Subject: VEA - Video Encryption Algorithm
Date: Tue, 17 Aug 1999 19:28:09 GMT
Here's a link to a description of VEA, an encryption algorithm designed
to work within the MPEG compression/decompression process. It is noted
in the text that it is not very secure against real cryptographers,
however it can be useful for privacy and securing pay-per-view.
http://www.acm.org/sigmm/MM98/electronic_proceedings/shi/
Anyway, just posting this for those who are curious.
Casey
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (Guenther Brunthaler)
Subject: Re: I HOPE AM WRONG
Date: Tue, 17 Aug 1999 20:20:29 GMT
On Sat, 14 Aug 1999 20:28:07 -0400, <[EMAIL PROTECTED]> wrote:
>I'm sure CNN is praying for an invasion too!
...with neutron bombs; for this will double the viewing quotes!
Greetings,
Guenther
--
Note: the 'From'-address shown in the header is an Anti-Spam
fake-address. Please remove 'nospam.' from the address in order
to get my real email address.
In order to get my public RSA PGP-key, send mail with blank body
to: [EMAIL PROTECTED]
Subject: get 0x2D2F0683
Key ID: 2D2F0683, 1024 bit, created 1993/02/05
Fingerprint: 11 71 47 2F AF 2F CD F4 E6 78 D5 E5 3E DD 07 B5
------------------------------
From: [EMAIL PROTECTED] (Guenther Brunthaler)
Subject: Re: frequency of prime numbers?
Date: Tue, 17 Aug 1999 20:30:32 GMT
On Tue, 10 Aug 1999 17:50:00 -0700, "karl malbrain" <[EMAIL PROTECTED]>
wrote:
>As Bob S has illustrated, you have to take BOTH sides of this contradiction
>at ONCE: P is also provably COMPOSITE (because it's not in the list), hence
>a contradiction with your proof that P is PRIME. Karl M
No, it means that P cannot be prime, but it must. This contradiction
cannot be resolved if N exists.
Therefore N cannot exist, and so there must be an infinite number of
prime numbers.
BTW, I found Don's simple proof beautiful!
Greetings,
Guenther
--
Note: the 'From'-address shown in the header is an Anti-Spam
fake-address. Please remove 'nospam.' from the address in order
to get my real email address.
In order to get my public RSA PGP-key, send mail with blank body
to: [EMAIL PROTECTED]
Subject: get 0x2D2F0683
Key ID: 2D2F0683, 1024 bit, created 1993/02/05
Fingerprint: 11 71 47 2F AF 2F CD F4 E6 78 D5 E5 3E DD 07 B5
------------------------------
From: greg pruitt <[EMAIL PROTECTED]>
Subject: encyrption
Date: Tue, 17 Aug 1999 20:17:57 GMT
i've never heard of cast encryption before. is that stronger than
triple des & idea has any of them been broken yet?
--
greg pruitt
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Q. a hash of a hash ...
Date: Tue, 17 Aug 1999 15:25:10 -0600
The proof below is not valid (reasoning follows):
Anton Stiglic wrote:
>
> You should read his proof as follows:
>
> 1. First I proove that if I found a collision for H, I have one for H^2:
> (this is easy): if I have x!= y and H(x) = H(y), then
> of cours H(H(x)) = H(H(y)), and I have found
> a colision for H^2.
>
> 2. Then I proove that if I found a collision for H^2, I have one for H:
> if I have x!=y such that H(H(x)) = H(H(y)), then I have one
> of two cases:
> a: H(x) = H(y): in wich case I have a collison for H.
> b: H(x) != H(y): in wich case I denote x' = H(x) and
> y' = H(y). I can now say that y' != x' and H(x') = H(y').
>
> So, to conclude, if I have a collison for H, I have one for H^2 (1),
> and, the other way around, if I have a collison for H^2 I have one
> for H (2).
>
> It is a simple and nice proof, it prooves that H and H^2 are equaly
> collision resistant.
>
> Anton
Consider, for example, H(x) defined as, say, shifting right by one bit
(and so discarding the low order bit). Now H(x) = H(y) means that x
and y are the same except (perhaps) for their low order bit. But
H(H(x)) = H(H(y)) even when x and y differ in *two* bits. In other
words, H^2 plainly has *more* collisions than H.
The problem with the proof is that although H^2 only has collisions
due to H, it does not necessarily have the same number of them. In
fact, you can see that each collision of H can potentially give rise
to two collisions of H^2.
Now obviously the H I defined above is not exactly a cryptographically
secure hash function. But it does mean that H and H^2 will not be
equally collision resistant unless H has some other properties, more
than assumed in the above proof (which assumed nothing, really, except
that H is a function).
Indeed, if H^2 has exactly as many collisions as H, I think this
implies that H must be a permutation on those inputs that are the
same size as its output. That is, we would require that there be
zero collisions between such inputs. Otherwise H^2 has all of the
collisions of H, plus others.
John M.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: NIST AES FInalists are....
Date: Tue, 17 Aug 1999 16:19:16 -0600
In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn"
<[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] wrote:
> > Do they send you a memo or what?
>
> If you want to discuss security issues, there are appropriate
> channels for that, and Usenet is definitely *not* one of them.
In crypto, generally it is accepted that knowing all about an algorithm is
not going to compromise its use if it is good enough. Much the same is
apt to be appropriate for large areas of security issues. Surely Usenet
is the best way to openly discuss such things with those most concerned.
I find that one on one discussions elsewhere are apt to be matches that
turn out to have little to do with real issues at all, just whether one
side or the other can bully through a point of view. I appeal to you
continue related discussions in public. I also make it well known again
here that I personally have no wish to argue differences in private on
these matters myself; sunlight remains the best disinfectant.
--
All's fair in love, war, and crypto. ERACE
------------------------------
** 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
******************************
