Cryptography-Digest Digest #237, Volume #9 Mon, 15 Mar 99 16:13:04 EST
Contents:
Re: my SHC (Jim Gillogly)
Re: Cipher for chat program (David)
Re: Self-executing encryption program (Mycroft)
Re: pRNG that is "predictable to the left"? (Christoph Haenle)
Re: pRNG that is "predictable to the left"? (Mok-Kong Shen)
Re: Certicom Benchmark (Medical Electronics Lab)
Secure Hash (shc.c) ([EMAIL PROTECTED])
Re: How "safe" is SafeGuard Easy for WinNT by Utimaco? (Terje Mathisen)
Re: DIE HARD and Crypto Grade RNGs. (Patrick Juola)
Re: ElGamal vs RSA (Daniel Bleichenbacher)
Re: Test vectors for RC4 (Jim Gillogly)
Re: DIE HARD and Crypto Grade RNGs. (Mok-Kong Shen)
Re: my SHC ([EMAIL PROTECTED])
Re: Test vectors for RC4 ("Trevor Jackson, III")
Re: Secure Hash (shc.c) (Jim Gillogly)
Re: Factoring large numbers: MPQS algorithm. (Don Leclair - Toggle Software)
----------------------------------------------------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: my SHC
Date: Mon, 15 Mar 1999 09:34:09 -0800
Regarding his proposed new 32-bit hash,
[EMAIL PROTECTED] wrote:
> BTW, it's at
> http://members.tripod.com/~tomstdenis/shc.c
What tests have you run on its output? The first simple test
I tried on it has very suspicious results: I hashed the first
65536 32-bit integers (0x00000000, 0x00000001, ...) and tabulated
the frequencies of the resulting bytes. The expected size of
each of the 256 byte buckets should be 4096. However, the most
frequent output byte was 0x00, at a frequency of 4414, more than
100 ahead of the next most frequent byte. Obviously <something>
has to have the highest output frequency, but when it's 0 (the
most frequent input byte as well as a special case byte), and
by a large margin, it's more than suspicious.
Looks like a loser from here. I think you need to apply more
theory to the hash construction process, and try to figure out
why the authors of other hash algorithms made the design decisions
they did... then run some statistical tests like Maurer and DIEHARD
on the output of your hash with related inputs, as I did here.
Alternatively, you could use one of the widely tested and
presumed-strong hashes and save 32 bits of it.
--
Jim Gillogly
Highday, 23 Rethe S.R. 1999, 17:17
12.19.6.0.8, 3 Lamat 1 Cumku, Eighth Lord of Night
------------------------------
From: [EMAIL PROTECTED] (David)
Subject: Re: Cipher for chat program
Date: Mon, 15 Mar 1999 15:08:00 GMT
On Mon, 15 Mar 1999 09:21:13 -0200, "F. Arndt" <[EMAIL PROTECTED]>
wrote:
>Forgive me for a dumb question: Why must the SERVER encrypt/decrypt?
>It would seem only chat CLIENTS need to share a secret key.
That's not a dumb question at all -- I didn't really explain how this
might work. I was imagining that the clients could connect to chat
directly -- as people would using DCC via IRC. The servers come into
play if someone wants to host a channel or room w/ encrypted messages.
If each room has a different key, and all users of the room share that
key, the clients could encrypt messages, would then be bounced back to
other users. This would be OK, but even in this scenario, the server
will probably have to encrypt topic changes, joins, parts, lists of
channels, and notify messages.
The server will, also, at the very least have to decrypt incoming
messages to see which channel they're for, whether it's a 'command' or
simply text. If the destination channels and packet type
(message/command/etc.) are plaintext it would compromise security, no?
It might make sense, though, to have an option to have different keys
for different users of the same room. What I don't know, from a
cryptographic point of view, is how to do this securely -- would
padding the front of the message w/ random data be enough to protect
the same data encrypted to different keys, etc.? But, this has one
advantage -- a person can't leave the room and then listen in on the
channel w/ a packet snooper, using the key which he/she still has. Of
course, the server could change the group key on every part, but this
could be a lot of work depending on the amount of traffic going in and
out.
I hope this makes sense -- as I said, I'm just beginning to work some
of these issues out.
David
------------------------------
From: Mycroft <[EMAIL PROTECTED]>
Subject: Re: Self-executing encryption program
Date: Mon, 15 Mar 1999 11:30:06 -0600
Sundial Services wrote:
> Mycroft wrote:
> >
> > "Bo Dömstedt" wrote:
> >
> > > [EMAIL PROTECTED] wrote:
> > > >Does anyone know of an encryption program that creates self-executing
> > > >decryption files, so you can send files to anyone who doesn't have the
> > > >program, as long as they have a password?
> >
> > Pkzip has a "scramble" option and you can create self-extracting
> > executables
> > with it.
>
> [Snicker...] Do you know how long it actually takes to dismantle the
> PKZip stream cipher? If you have the slightest idea of what as little
> as 12 bytes of the original plaintext was, at any point in the
> enciphered stream, then you can compute the internal key and recover the
> information remarkably quickly. This fact is all-too-well known.
Hmmmm....I don't recall the original poster asking for a "fool proof"
self-extracting encrypted executable, just an example of ANY self-extracting
ecrypted executable. If you have a better example, then post it. If not...
--
******************************
Remove the "nospam" from my email to reply
------------------------------
From: Christoph Haenle <[EMAIL PROTECTED]>
Subject: Re: pRNG that is "predictable to the left"?
Date: Mon, 15 Mar 1999 17:28:52 +0100
Mok-Kong Shen wrote:
>
> Christoph Haenle wrote:
>
> > Oops, sorry, you're right, should be
> >
> > x_1 = {seed}^d
> > x_2 = {seed}^(d^2)
> > x_3 = {seed}^(d^3)
> > ...
>
> I still don't quite understand. Would you, for example, detail
> how one computes from X_5 the previous values? If the analyst
> gets to X_1, what deters him from computing forwards from there?
>
> M. K. Shen
The issue is that d is the secret exponent in RSA, and e is the
public exponent. When you have x_5, then computing x_4 is easy:
x_4 = {x_5}^e mod n,
since in RSA, {m^d}^e = 1 mod n for all 0<m<n. Likewise, you can
compute x_3, x_2, and x_1, but not x_6 for example.
-Chris.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: pRNG that is "predictable to the left"?
Date: Mon, 15 Mar 1999 18:44:59 +0100
Christoph Haenle wrote:
> The issue is that d is the secret exponent in RSA, and e is the
> public exponent. When you have x_5, then computing x_4 is easy:
>
> x_4 = {x_5}^e mod n,
>
> since in RSA, {m^d}^e = 1 mod n for all 0<m<n. Likewise, you can
> compute x_3, x_2, and x_1, but not x_6 for example.
O.K. But can you give an example where the generator can be useful?
M. K. Shen
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: Certicom Benchmark
Date: Mon, 15 Mar 1999 11:16:31 -0600
Francis Tan wrote:
>
> For GF(2^m), field squaring is very fast , but the field
> multiplication can be quite slow, since it is basically calculated
> using the shift and add method, processing bit by bit. And a field
> inverse is about 3-4 x of a field multplication.
Depends on the field. Multiplication can be fast if you pick the
right fields, for example a trinomial for the prime polynomial.
You can also make inversion fast if you use a normal basis, the
time for an inversion takes as long as a multiply.
> However for GF(p), we are making use of CPU multiply instruction which
> process 1 word at a time. Generally, for larger field size and in CPU
> with word size >=32, the GF(p) performs betters, and the field inverse
> can be eliminated with the use of projective coordinates as well.
Right, this is a hardware speedup. The same thing could be done
with polynomials, but for a general chip it probably will never
happen. If we had an ONB multiply instruction for example, the time
to perform an integer multiply would still be longer.
As a practical case, it may very well be that GF(p) is faster on
generic computers simply because there are several integer units
and you can keep them all filled efficiently. I would hope I could
do the same with GF(2^n) if I write the code correctly, but that
remains to be seen.
I'll be back soon (I hope) with some interesting numbers.
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED]
Subject: Secure Hash (shc.c)
Date: Mon, 15 Mar 1999 18:53:44 GMT
I already got some critism WRT my SHC algorithm. I would really like to
improve it. However I don't know where or what to correct. If I could get
some critism with explanations I would really appreciate it.
My testing so far includes:
- 1 byte files
- sentences
- huge (540KB) text files (with single value changes)
and all have passed. The sums for each of the tests are completely unrelated
for example:
SC of '1' is 242F 043E 903E 021F
SC of '2' is A47A 795C F7C8 2533
SC of 'Tommy' is 7AF4 184A E52A 40D2
SC of 'tommy' is 4DA4 2383 0FF7 5096
You can see some of the nibbles are similar, but the overall hash is
completely different in each case. However I am no expert. I got some of my
ideas from R.Rivests RC5 paper. So I am not a hacker-newbie either. Please
help me! :)
Thanks,
Tom
You can get SHC.C at:
http://members.tripod.com/~tomstdenis/shc.c
(includes pseudo-code)
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: Terje Mathisen <[EMAIL PROTECTED]>
Subject: Re: How "safe" is SafeGuard Easy for WinNT by Utimaco?
Date: Mon, 15 Mar 1999 19:20:24 +0100
Daniel Kinnaer wrote:
>
> I would like to know how 'good' SafeGuard Easy for WinNT by Utimaco
> really is. Is it easy to use, are there any known bugs? Is it really
> that safe as it claims to be? Can hackers 'crack' my system if I
> would install it on my PC?
Assuming it is actually implemented the way they state, i.e. your
password is used (presumably with a salt) to decrypt a header block
which then contains the 128-bit IDEA key used to encrypt the rest of the
hard disk, the security should only be limited by the security of your
password.
We have been using their products on company laptops for several years
now, it is mandatory if you're going to carry any kind of company
internal information on the hard disk.
The two-stage decryption process makes it easy to setup two header
blocks, one encrypted with the user password, plus a backup password
which is kept in a locked safe.
The second password makes it possible to recover the hard disk data if
the user forgets his/her password.
Terje
--
- <[EMAIL PROTECTED]>
Using self-discipline, see http://www.eiffel.com/discipline
"almost all programming can be viewed as an exercise in caching"
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: DIE HARD and Crypto Grade RNGs.
Date: 15 Mar 1999 12:52:37 -0500
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>Patrick Juola wrote:
>>
>
>> So the program I defined above provides an upper bound on the
>> Kolmogorov complexity of a string; more formally, it's a theorem
>> that K(x) <= |x|. There's also a theorem that, for any reasonable
>> definition of randomness, a random string has K-complexity *equal*
>> to its length.
>
>This is well-known. But I am still ignorant of why the definition
>of Kolmogorov, that is void of any connection to computational cost,
>can be a good definition of 'complexity', apart from mathematical
>interests that you indicated.
Well, it's a good measure of the amount of computational machinery
required to obtain a string as long as you don't care how long it
takes.
If you don't regard it as a good definition, then don't use it.
-kitten
------------------------------
From: [EMAIL PROTECTED] (Daniel Bleichenbacher)
Subject: Re: ElGamal vs RSA
Date: 15 Mar 1999 14:51:02 -0500
In article <7cegq4$ktg$[EMAIL PROTECTED]>,
Roger Schlafly <[EMAIL PROTECTED]> wrote:
>
>Michael Sierchio wrote in message <[EMAIL PROTECTED]>...
>>Daniel Bleichenbacher wrote:
>>>
>>> RSA has definitively the advantage over ElGamal encryption/signatures
>>> that good standards for RSA (IEEE, ANSI, PKCS) are available.
>>
>>Bingo.
>
>This is really a silly statement. The standardization work in ANSI and
>IEEE for ElGamal-like signatures predated that for RSA. The most
>popular ElGamal variant is commonly called DSA. As Johnson pointed
>out, there are perfectly good standards for DSA and there have been
>for years.
>
>Bleichenbacher knows this, but argues that DSA and ECDSA are
>"derivated algorithms", while PKCS #1 version 1.5. I am not sure this
>distinction makes any sense, but it is useless even if it does.
>
>
>
Let me try to clarify my previous post here.
As pointed out there are good standards by IEEE, ANSI, etc for
DL based cryptosystems. There is no doubt that DL based
have received similar attention as RSA and that the
standards committees have done a good job creating DL based
standards.
Just, these schemes are not called ElGamal and the
original question was about a comparison of ElGamal
vs. RSA. Now, for RSA encryption we can find standards
using OAEP, whereas (to my knowledge) no such standard
for ElGamal encryption has been proposed. The best, I know,
is the ElGamal encryption included in the openpgp standard.
This one uses a simple 2 byte checksum and hence is at
most marginally secure against chosen ciphertext attacks.
Hence, I still prefer RSA over ElGamal because of the
standards situation.
RSA vs. DLSVDP-DH or DHES is a different question.
--
Daniel Bleichenbacher
Bell Laboratories
600 Mountain Av.
Murray Hill, NJ 07974
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Test vectors for RC4
Date: Mon, 15 Mar 1999 10:37:30 -0800
Dominik Werder wrote:
> I search some test vectors for the RC4 algorithm.
See http://ciphersaber.gurus.com -- if you can make a working
CipherSaber, your implementation works. There are test files
to decrypt there.
--
Jim Gillogly
Highday, 23 Rethe S.R. 1999, 18:35
12.19.6.0.8, 3 Lamat 1 Cumku, Eighth Lord of Night
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: DIE HARD and Crypto Grade RNGs.
Date: Mon, 15 Mar 1999 19:48:11 +0100
Patrick Juola wrote:
>
> Well, it's a good measure of the amount of computational machinery
> required to obtain a string as long as you don't care how long it
> takes.
>
> If you don't regard it as a good definition, then don't use it.
I am afraid that the term 'computational machinery' is fairly vague.
Let me venture to express my personal 'sentiment' to concepts of
Kolmogorov type. We could in analogous way attempt to tackle the
problem of determining the strength of an encryption algorithm:
Define the strength of an algorithm to be the shortest average
time to break that algorithm. This measure could certainly be
useful for comparing algorithms. But there is no way to determine
that 'shortest average time' just as there is no way to determine
the length of the shortest program for a given sequence. Both
are in my opinion useless but merely do a 'transformation' of
a problem without actually solving it at all.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: my SHC
Date: Mon, 15 Mar 1999 16:00:48 GMT
> In fact, since 128 bit hashes fall with 2^64 effort, they are also becoming
> questionable. Most "new" hashes have longer output: SHA and RIPE-MD are 160
> bits, Tiger is 192 bits, and HAVAL has variable outputs up to 256 bits.
(Only
> Tiger is really new, and it's optimized for 64-bit processors.)
However you can extend my algorithm to 128/256 bits if you need. However I
think I may have to modify SHC to use more then one round.
>
> Also, see the MDx specs for how to pad the message. For instance, to prevent
> message extension attacks, include the message length in the hash value.
Thanks,
Tom
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
Date: Mon, 15 Mar 1999 15:23:13 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Test vectors for RC4
Mok-Kong Shen wrote:
>
> Dominik Werder wrote:
> >
> > I search some test vectors for the RC4 algorithm.
> > And I have a question: How strong is RC4 as encryption algorithm?
> > (normal RC4, plainbyte XOR pseudo-random-byte)
> > thanks!
>
> Questions of your type is in general ill-posed. For an algorithm that
> is broken, the question need not be asked; for an algorithm
> that is not yet broken the strength can not be expressed because
> there is no standard unit of strength of encryption algorithms to
> measure that unambiguiously.
For an unbroken cipher, one in which the most efficient attack is brute
force key search, is not the work fact of a brute force search a useful
metric? Consider that DES is not broken, yet it is deprecated as
lacking strength on the basis of just such a work factor analysis.
>
> M. K. Shen
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Secure Hash (shc.c)
Date: Mon, 15 Mar 1999 12:50:35 -0800
[EMAIL PROTECTED] wrote:
> My testing so far includes:
>
> - 1 byte files
> - sentences
> - huge (540KB) text files (with single value changes)
>
> and all have passed. The sums for each of the tests are completely unrelated
The first thing I thought of was to hash a lot of related 4-byte files,
counting from 1 to N; I posted the result of that for N = 2^16, and it
showed a suspiciously high number for 0x00, which was most frequent. I
redid it for N=2^20, counting the output bytes from your hash. They
should be uncorrelated and more or less evenly distributed into 256
bins of about 65536 bytes each. Here are the 10 most frequent bytes:
66481 0.0040 80
66538 0.0040 05
66539 0.0040 02
66601 0.0040 20
66615 0.0040 01
66740 0.0040 40
66864 0.0040 10
67048 0.0040 08
67069 0.0040 04
71501 0.0043 00
The first column is frequency, second is percentage of the file, and
third is the byte value. The highest byte value is the null byte, and
it's very high. All eight of the bytes with Hamming weight 1 are in
the top 10.
You make the call.
Note that passing this test won't demonstrate that the hash is good;
and of course with only 32 bits of output its applications are quite
limited in any case.
--
Jim Gillogly
Highday, 23 Rethe S.R. 1999, 20:39
12.19.6.0.8, 3 Lamat 1 Cumku, Eighth Lord of Night
------------------------------
From: Don Leclair - Toggle Software <[EMAIL PROTECTED]>
Subject: Re: Factoring large numbers: MPQS algorithm.
Date: Mon, 15 Mar 1999 20:35:36 GMT
Hi,
> I am actually doing a study on the factoring algorithms but I still
> have some trouble with the MPQS. I perfectly understand how the basic
> quadratic Sieve works but I don't get the multipolynomial stuff.
Robert Silverman wrote the definitive paper on the subject and "Prime Numbers
and Computer Methods for Factorization" by Hans Riesel has a good overview of
the difference between the QS and the MPQS.
I haven't read the paper by Silverman but the Riesel's explanation is along
these lines:
The MPQS overcomes the problem in the QS that as you sieve over (x^2 mod N)
the quadratic residues it generates quickly grow in size, and therefore are
less likely to be smooth.
Instead of sieving over (x^2 mod N), as in the QS, MPQS sieves over ((a+xb)^2
mod N) where 'b' is a square number itself and 'a' is the first offset such at
((a+x)^2 mod N) is divisible by 'b'. ( 'b' doesn't necessarily have to be a
square number but it is the simplest case )
The resulting residues are all divisible by 'b' and residue/b grows in size at
about the same rate as residues in the QS do. If residue/b is smooth then you
have a residue which can be of use in factoring N in the matrix stage.
Once the size of the resulting residues grows too large, pick a different
values of 'a' and 'b' and start sieving again.
The QS can be thought of as a special case of the MPQS where 'b' is one and
'a' is zero.
Don Leclair
[EMAIL PROTECTED]
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
** 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
******************************
