Cryptography-Digest Digest #82, Volume #12 Thu, 22 Jun 00 04:13:01 EDT
Contents:
Re: MD5 Expansion (Simon Johnson)
Re: How encryption works (Simon Johnson)
DH - Man In The Middle ("Mark")
Re: MD5 Expansion (jungle)
Re: Length of pseudo random digits (Mok-Kong Shen)
Re: Variability of chaining modes of block ciphers (Mok-Kong Shen)
Re: MD5 Expansion ("Joseph Ashwood")
Re: Length of pseudo random digits ("Douglas A. Gwyn")
Re: obfuscating the RSA private key (Mack)
Re: CRC-64 and 128 - Generator Polynomials? (Mack)
Re: Encryption on missing hard-drives (Mack)
Re: small subgroups in Blum Blum Shub (Mok-Kong Shen)
Re: small subgroups in Blum Blum Shub (Mok-Kong Shen)
Re: Quick Question on Primitive Elements GF(p) (Mack)
Re: Quick Question on Primitive Elements GF(p) (Mok-Kong Shen)
Re: Encryption on missing hard-drives (Guy Macon)
Re: Variability of chaining modes of block ciphers (Guy Macon)
----------------------------------------------------------------------------
Subject: Re: MD5 Expansion
From: Simon Johnson <[EMAIL PROTECTED]>
Date: Wed, 21 Jun 2000 22:10:28 -0700
A much better way is to divide the message in two. Then hash
each part individually and contatenate each hash.
a = 1/2 of M
b = other 1/2 of M
Hash output = H(a) & H(B)
This will have a birthday attack threshold of 2^128, more than
enough.
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
Subject: Re: How encryption works
From: Simon Johnson <[EMAIL PROTECTED]>
Date: Wed, 21 Jun 2000 22:28:16 -0700
no-one <[EMAIL PROTECTED]> wrote:
>On 20 Jun 2000 23:59:13 GMT, [EMAIL PROTECTED] (infamis at
>programmer.net) wrote:
>
>>Ok, I've read this newsgroup's faq, some other texts out
there, and some
>>presentations on cryptography, but I just don't understand it.
Only partially.
>>For example, this is something I read somewhere:
>>--------------------
>>n,e=public key, n = (prime num. p * prime num. q), M=message
>>d=private key
>>encryption: C=M^e mod n
>>decryption: M=C^d mod n
>>[say p=5, q=7, e=3]
>>p*q = 35
>>d=e^(-1) mod ((p-1)(q-1))
>> =16
>>--------------------
>>I understand most of it except....
>>1) is n or e the public key?
>>2) if M=message, is this the checksum of the whole message, of
1 character,
>>blocks of characters, or what?
>>3) the line with "d=....". When I did this out, (3^(-1)) mod
((4)(6)) didn't
>>equal 16... I got 1/3.
Others, in the thread have suggested the euclidean algorithm to
calculate modulo inverses. I'll be different and say you use the
Euler Totient function. to calculate and modulo inverse:
d=e^((p-1)x(q-1)) mod (pxq)
Simplicity itself :)
>>
>>Other questions:
>>I have pgp5.5. They key's properties said Diffie-Hellman/DSS,
with CAST cipher.
>>What in the world does this mean? Isn't DH/DSS the encryption,
so why need CAST
>>[or IDEA which I saw on other keys]?
>>
>>I haven't read about any encryption methods that have broken,
which didn't use
>>a brute force attack. Are there any and how did the decryption
work?
Broken, in the sense you mean, rearly happens. When cipher is
broken, it means a flaw has been found such that the key could
be retrieved by a method other than brute force.
Most of these attacks, are theoretically possible but in
realtity are tremedously difficult to achieve. Some require
massive amounts of data, or require a huge number of operations.
>>I don't plan to make some great encryption method and get
famous or anything, I
>>just want to know how this works because I think it's very
interesting. I'm
>>only 14, so bear with me...
starting at 14? There's a good chance you could get famous :)
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: "Mark" <[EMAIL PROTECTED]>
Subject: DH - Man In The Middle
Date: Thu, 22 Jun 2000 05:47:22 GMT
Im thinking of using a DH exchange to setup my keys (client/server app).
To stop the man in middle attack i need to sign the public values of the DH
exchange.
Im planning on storing my servers public DSS key inside the client EXE. (is
that ok?)
I know i NEED to sign the public values from the server.
what im wondering is if i can skip the signing on the client public values
that get sent to my server.
(this way i wouldnt need to generate any primes on the client (or am i
missing something?))
If i read everything right, only 1 large prime needs to be generated for a
DH exchange (a public value) and 2 primes need to be generated to sign using
DSS. If i can keep this to the server it should speed up initial connection
setup..
Does this comprimise the exchange so a man in the middle attack can still
happen (or any other).
To Sum Up:
If someone can only modify the parameters sent from the client, but not the
server, can they still get in the middle?
Because the middle man would need to onsend the same public value that it
recieved from the server, it would need to use a private key that produced
the same public key as the server...something that is too "hard" to do?
Is my logic correct?
thanks in advance
Mark
------------------------------
From: jungle <[EMAIL PROTECTED]>
Subject: Re: MD5 Expansion
Date: Thu, 22 Jun 2000 01:51:33 -0400
the simples solution is the best ...
Simon Johnson wrote:
> A much better way is to divide the message in two. Then hash
> each part individually and contatenate each hash.
>
> a = 1/2 of M
> b = other 1/2 of M
> Hash output = H(a) & H(B)
>
> This will have a birthday attack threshold of 2^128, more than
> enough.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Length of pseudo random digits
Date: Thu, 22 Jun 2000 08:45:35 +0200
Jacques Th�riault wrote:
> How can I calculate the period of a random digit generator.
>
> Is there any formula to estimate such a period?
Given an 'arbitrary' generator, there is no 'general' recipe for getting
the period except running it. For some number of classes of generators,
one has formulae or else criteria for attaining the maximal periods.
See Knuth, vol. 2.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Variability of chaining modes of block ciphers
Date: Thu, 22 Jun 2000 08:45:51 +0200
Eric Lee Green wrote:
> Mok-Kong Shen wrote:
> >
> > The most popular block chaining mode seems to be CBC.
> > There is also PBC which chains with plaintext blocks.
> > One can also accumulate the previous blocks for doing the
> > chaining and use plaintext as well as ciphertext for
> > chaining. (I used this in one of my own designs.) By
> > combinatorics this gives 8 variants.
>
> Great. You just added 3 bits to the key space. At the expense of adding yet
> more code that could be defective/insecure or slow the operation of the
> program.
If you never use chaining at all, then there is probably no point of mine.
If you use CBC, then switching to PCBC (using both plaintext and
ciphertext) may result in a difference more than what can easily be
quantified by bits.Whether adding code could be defective due to
bugs (or even implanted backdoors) is a software engineering issue
that I have omitted from my considerations. Chaining is in fact very
simple to implement. So neglecting the benefit it offers is not
economically justified in my humble view.
M. K. Shen
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: MD5 Expansion
Date: Wed, 21 Jun 2000 23:30:24 -0700
Except that if you only need to spoof a small portion of the
message with the rest remaining the same the effort is still
2^64 for a birthday paradox attack. What you could do is
also create a hash of the entire message, creating a 3*128
bit hash, with strength that's approaching a 256 bit hash,
although the hash will obviously be larger than 256-bits.
Joe
"Simon Johnson" <[EMAIL PROTECTED]>
wrote in message
news:[EMAIL PROTECTED]...
> A much better way is to divide the message in two. Then
hash
> each part individually and contatenate each hash.
>
> a = 1/2 of M
> b = other 1/2 of M
> Hash output = H(a) & H(B)
>
> This will have a birthday attack threshold of 2^128, more
than
> enough.
>
> Got questions? Get answers over the phone at Keen.com.
> Up to 100 minutes free!
> http://www.keen.com
>
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Length of pseudo random digits
Date: Thu, 22 Jun 2000 06:45:02 GMT
Mok-Kong Shen wrote:
> Jacques Th�riault wrote:
> > How can I calculate the period of a random digit generator.
> Given an 'arbitrary' generator, there is no 'general' recipe for
> getting the period except running it.
Indeed, if it generates digits truly randomly, it has no period.
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: obfuscating the RSA private key
Date: 22 Jun 2000 06:47:42 GMT
[EMAIL PROTECTED] (Dave Ahn) wrote:
[snip]
>Our group has client-server programs that are open sourced for peer review.
>We distribute these programs in source and precompiled binary form. Users
>download the client binary and use it to connect to servers over the
>Internet.
>
>We wish to ensure that the users of the client software are using the
>official precompiled binary as opposed to a custom-compiled version based
>on the public source code. We do not trust the client users. But we do
>trust the server administrator. We also trust the network connection
>between the client and the server (i.e. ignore eavesdropping or man-in-middle
>attacks).
>
[snip]
>Does this clarify my original questions a bit?
>
yes ...
You wish to prevent people from running hacked copies of your
software.
There is no way to do this except with dedicated hardware and
even that is subject to attack. At best you can slow the attacker
down.
With source available for most of the program
except for the authentication portion a determined attack can
rapidly figure out which parts of the code aren't published.
>From there the attacker doesn't even have to figure out
what it does. He just has to duplicate its actions.
Simply disassemble the pertinent part (a good disassembler will
insert its own symbols). Then recompile that section and link
with the new version.
The best way to defeat that is to include
a memory checksum function of some type (CRC,MD5,SHA or
even simply a sum every every first third and seventh byte.
That will force the attacker to figure out what you are doing.
Another way is to include some self-modifying code. ie.
It will crash the program unless the attacker can figure out
what is going on.
Since they have the source code they can also very easily
hack the official version with a patch. There really isn't anyway
to prevent this.
Basically you are stuck with the problem that honest users
are honest and those that aren't ... well ... hackers will hack
>Thanks in advance.
>--
>Dave Ahn | [EMAIL PROTECTED] | Wake Forest University Baptist Medical Center
>
>When you were born, you cried and the world rejoiced. Try to live your life
>so that when you die, you will rejoice and the world will cry. -1/2 jj^2
>
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: CRC-64 and 128 - Generator Polynomials?
Date: 22 Jun 2000 06:55:09 GMT
"Ken Christensen" [EMAIL PROTECTED] wrote:
>Are there "standard" generator polynomials for 64 and 128-bit CRC? I want
>to study how CRC128 compares to MD5 in terms of 1) computation cost in s/w,
>2) gate count in h/w, and 3) probability of collisions (duplicate hashes)
>for hashing of Web URLs. Using remainder methods for computing CRC in s/w
>seems to me would require less CPU cycles than MD5???
>
>Thanks!
>
>Ken Christensen
>--
I am looking for some good CRC polynomials for 64, 128, 192, 256 and
higher bits. Does anyone have a list of primitive polynomials of those degrees
mod 2?
as for using CRC for hashes 1) they are quicker than MD5
2) the gate count should be very low
3) the probability of collision should be the same
however for 3) remember that is for random input
not an active attempt at causing collisions. For most
ASCII text you should be pretty safe. Especially since
web URLs are very specific format. And usually not very long.
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: Encryption on missing hard-drives
Date: 22 Jun 2000 07:11:39 GMT
>Scripsit [EMAIL PROTECTED]:
>
>: On a more sci.crypt note, noone's answered my original question which
>: is if it's possible to encrypt a device such that it's impossible to
>: read the contents without leaving a trail. Something similar to a one
>: time password system, where a series of keys must be used or some
>: other clever algorithm. Just for fun, we'll allow a secure connection
>: to a trusted party.
>
>Since these are disk drives, I'd bet real money that at most
>the contents were encrypted. I suppose it _is_ possible that
>the US gov't has special disk controllers and hard drives,
>such that if you don't do just the right thing when trying
>to read the drive, the data all go away. But it is a real
>stretch of the imagination to come up with that, and it
>would preclude using any off-the-shelf WIN-based OS.
>
I believe (but I could be wrong) that there are encrypting
disk controllers and coresponding drives available.
I can easily imagine such a device pair operating off of
an ATA interface. If I were to build such a device I would
certainly make it erase the data if the correct password
/phrase/timing sequence wasn't applied.
But I can't fathom why you would put such a device on a
WIN based machine where it will just dump content to the
unencrypted swap file where anyone can read it.
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: small subgroups in Blum Blum Shub
Date: Thu, 22 Jun 2000 09:30:24 +0200
"David A. Wagner" wrote:
> Klaus Pommerening <[EMAIL PROTECTED]> wrote:
> > BTW the BBS generator outputs the LSB of its internal state
> > x_i for each step. (x_i = x_{i-1}^2 mod n)
> > Is there any known result that some choice of parameters in BBS
> > guarantees that the LSBs don't give short cycles?
>
> Guarantees? No, not that I know of.
> But, since the LSBs are indistinguishable from random bits
> (assuming factoring is hard), the LSBs have no better chance
> of cycling than random bits would. And, random bits have a
> very low chance of cycling...
Could you please (plausibly) explain why the LSB from BBS are
indistinguishable from random bits, assuming factoring is hard.
Could the LSB assist in factoring? (I thought the numbers in a cycle
of the output from the congruence relation themselves are needed
to effect factoring.)
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: small subgroups in Blum Blum Shub
Date: Thu, 22 Jun 2000 09:29:58 +0200
Tim Tyler wrote:
> Terry Ritter <[EMAIL PROTECTED]> wrote:
> : in sci.crypt [EMAIL PROTECTED] (Klaus Pommerening) wrote:
> :>In <[EMAIL PROTECTED]> Terry Ritter wrote:
>
> :>> * We *can* build a generator which does not use short cycles.
> :>
> :>BTW the BBS generator outputs the LSB of its internal state
> :>x_i for each step. (x_i = x_{i-1}^2 mod n)
> :>Is there any known result that some choice of parameters in BBS
> :>guarantees that the LSBs don't give short cycles?
>
> : Not that I know of. I never even thought of investigating such a
> : thing on my small models. I guess I assumed that sort of thing was
> : exactly what the proofs guaranteed.
>
> Since n = p * q (product of two primes), the /only/ way the lowest bit
> could exhibit a cycle (of length c) smaller than min(p,q) would be if
> it was always 0, or always 1.
This is not valid. If there is cycle of length c, then the period length of
the lowest bit can never be longer than c. A counter-example to your
claim: p=7, q=11, n=77. There is a cycle 4,16,25,9, giving rise to
the period of the lowest bit 0011, i.e. a period length of 4<7.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: Quick Question on Primitive Elements GF(p)
Date: 22 Jun 2000 07:29:01 GMT
Simon Johnson [EMAIL PROTECTED] wrote:
>Is the definition of a number that is a primitve element GF(p),
>if you can mutliply it by itself over and over, and get every
>value 0.....p-1?
>
1..p-1 but who is quibbling.
this is true the multiplicative group mod p
with order p-1
see HAC section 2.6.1 definition 2.214 in particular
>Or is this a side effect of some other definition?
Which came first the chicken or the egg?
>
>Got questions? Get answers over the phone at Keen.com.
>Up to 100 minutes free!
>http://www.keen.com
>
>
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Quick Question on Primitive Elements GF(p)
Date: Thu, 22 Jun 2000 09:57:18 +0200
Simon Johnson wrote:
> Is the definition of a number that is a primitve element GF(p),
> if you can mutliply it by itself over and over, and get every
> value 0.....p-1?
No. You never get 0.
> Or is this a side effect of some other definition?
I suspect that you are very interested in the issue of what is the
most 'optimal' organization of definitions (there are often many
options) in science for pedagogical purposes. Right? Normally
a concept evolves in a certain context. Later one finds another
concept in a different context and sees a connection between
the two. Now it is sometimes the case that, depending on your
personal preference, you can claim the first to be the elementary
concept and the other derived or just the opposite. If you are
interested in primitive elements as such, it seems advisable that
you consult some books about finite fields or coding theory.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Encryption on missing hard-drives
Date: 22 Jun 2000 04:03:16 EDT
[EMAIL PROTECTED] wrote:
>On a more sci.crypt note, noone's answered my original question which
>is if it's possible to encrypt a device such that it's impossible to
>read the contents without leaving a trail. Something similar to a one
>time password system, where a series of keys must be used or some
>other clever algorithm. Just for fun, we'll allow a secure connection
>to a trusted party.
No. The attacker can make a bit-for-bit copy of the drive and apply
whatever terchnique you devise to the copy.
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Variability of chaining modes of block ciphers
Date: 22 Jun 2000 04:07:40 EDT
michael wrote:
>I like the idea that you nassume that your attacker knows
>everything except the plaintext and the key, and has more
>resources and cleverness than you do. Limiting yourself to
>improvements that still improve your security under this
>standard seemms wiser than adding improvements that require
>secrets algorithms, chaining methods, etc (unless the algorithm,
>etc is selected by a part of the key not used elsewhere).
Wow. Exactly what I wrote 2 days ago, right down to the typo!
I guess great minds work alike...
------------------------------
** 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
******************************
