Cryptography-Digest Digest #85, Volume #12 Thu, 22 Jun 00 11:13:00 EDT
Contents:
Re: DH - Man In The Middle (Mark Wooding)
Re: Quick Question on Primitive Elements GF(p) (Mark Wooding)
Re: How encryption works (Mark Wooding)
Re: How encryption works (infamis.at.programmer.net)
Re: How encryption works (Mark Wooding)
libdes: des_SPtrans ([EMAIL PROTECTED])
Re: Encryption on missing hard-drives (Guy Macon)
Re: How encryption works ([EMAIL PROTECTED])
Re: How encryption works ([EMAIL PROTECTED])
Re: libdes: des_SPtrans (Mark Wooding)
Re: Encryption on missing hard-drives ("Tony T. Warnock")
Re: Variability of chaining modes of block ciphers (Mok-Kong Shen)
Re: Length of pseudo random digits (Mok-Kong Shen)
Re: Variability of chaining modes of block ciphers (Mok-Kong Shen)
Re: Variability of chaining modes of block ciphers (Mark Wooding)
Re: Variability of chaining modes of block ciphers (Mark Wooding)
Re: Try it. (John)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: DH - Man In The Middle
Date: 22 Jun 2000 10:35:57 GMT
Mark <[EMAIL PROTECTED]> wrote:
> 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.
Yes.
> Im planning on storing my servers public DSS key inside the client
> EXE. (is that ok?)
Should be OK, assuming that you don't have any worries about users
themselves modifying the executable. (If you do, then all bets are off:
give up and go home now.)
> 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 is OK, if you don't mind authenticating the client later. As long
as you do it carefully.
> (this way i wouldnt need to generate any primes on the client (or am i
> missing something?))
You're missing something. You can reuse DSA parameters, and share them
among many users. All the client needs to do is find a copy of the
shared parameters, pick a random secret key x, 0 < x < q, and somehow
transmit g^x (mod p) to the server.
> If i read everything right, only 1 large prime needs to be generated
> for a DH exchange (a public value)
No. If you've agreed on the Diffie-Hellman parameters (the prime and
generator) beforehand, you only need to generate arbitrary random
numbers to do the exchange, not find primes.
> and 2 primes need to be generated to sign using DSS.
Again, false. You need to generate a random number, and do some
arithmetic.
> Does this comprimise the exchange so a man in the middle attack can still
> happen (or any other).
Do it carefully.
Here's a suggestion for the other sci.crypt readers to analyse.
Choose a security parameter t, such that 2^t effort is more than your
adversary will expend in breaking the system. You'll also need to
decide on the length of primes to make the Discrete Log problem
sufficiently hard -- see references elsewhere to the RSA and CryptoSavvy
papers about choosing numbers of the right size.
The system uses two sets of parameters:
p_S, q_S, g_S -- DSA parameters for the server. (q_S is 2t-bit prime;
p_S is a larger prime such that q_S divides p_S - 1, and the
Discrete Log Problem mod p_S is hard; g_S generates the
order-q_S subgroup mod p_S.)
p, q, g -- DH parameters for key exchange. (p = 2 q + 1; both p and q
are prime, and p is large enough for the Discrete Log Problem
mod p to be hard; g = 4.)
The server creates a private DSA key x_S, 0 < x_S < q_S, and publishes
its corresponding public key y_S = g_S^{x_S} mod p_S. The server knows
all of the values above; the clients know the parameters and the
server's public key.
Let S(*) be the server's signature on a piece of data (i.e., the data
together with a signature).
The protocol works like this:
1. client -> server: g^\alpha mod p
2. server -> client: S(g^\alpha mod p, g^\beta mod p)
In detail:
1. The client chooses a random Diffie-Hellman exponent \alpha,
0 < \alpha < q, and sends its public Diffie-Hellman value g^\alpha
mod p.
2. The server generates its own random Diffie-Hellman exponent \beta,
0 < \beta < q, and sends back, in a signed message, both its own
public value g^\beta mod p and the client's public value.
Both then compute the secret K = g^{\alpha \beta} mod p, from which they
can set up a secret and valid connection using a symmetric cipher and a
MAC, keyed from the shared secret K. The client is certain that it is
communicating with the server: the server has no such assurance, but may
require some authentication later.
Analysis: Consider an adversary who controls the network between the
client and server. He can change the client's initial public value, but
cannot forge the server's signature on the response, so the client will
detect the modification. He cannot change the server's public value
either, for the same reason. The adversary could replay old responses
from the server, although they would not contain the correct client
public Diffie-Hellman value. Hence, the client can be sure that it has
a valid and fresh response from the correct server, and that the server
received the value it sent.
The server doesn't know who the client is. It could be anyone at all.
This may be OK. If it isn't, you probably want to add another message
3. client -> server: S_C(g^\beta mod p)
to confirm the freshness of the client's response, and its authenticity
(where S_C(*) denotes a message signed by the client).
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Quick Question on Primitive Elements GF(p)
Date: 22 Jun 2000 10:53:19 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?
>
> Or is this a side effect of some other definition?
Sort of. This is the way I've seen this stuff defined:
Let q = p^f for some prime p and positive integer f. Let x be an
element of GF(q), x != 0. We call a positive integer i an `exponent of
x' if x^i = 1. The `order of x' is the least exponent of x. An element
g of GF(q) is called `primitive' if the order of g is q - 1.
It is an immediate consequence of this definition that, if g <- GF(q) is
primitive, then for each x in the multiplicative group of GF(q) there
exists an integer i such that g^i = x. This could be used as an
alternative definition.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: How encryption works
Date: 22 Jun 2000 10:55:05 GMT
Simon Johnson <[EMAIL PROTECTED]> wrote:
> 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 :)
Very simple. Wrong, but simple.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (infamis.at.programmer.net)
Subject: Re: How encryption works
Date: 22 Jun 2000 11:26:11 GMT
So let me get this straight:
for a dh/dss key 2048/1024 bit with cast-128 cipher, the cast key encrypts the
message, then dh encrypts the cast-128 key and the ciphertext produced from the
cast cipher? Where does dss come into play?
for the same key, does this mean the dh key is 2048bit and the dss key is
1024bit? If not, what key(s) do the numbers 2048 and 1024 correspond to?
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: How encryption works
Date: 22 Jun 2000 11:35:34 GMT
infamis.at.programmer.net <[EMAIL PROTECTED]> wrote:
> So let me get this straight:
> for a dh/dss key 2048/1024 bit with cast-128 cipher, the cast key
> encrypts the message, then dh encrypts the cast-128 key and the
> ciphertext produced from the cast cipher?
No, just the CAST128 key.
> Where does dss come into play?
It's used to sign the message, if you decided that you wanted to do
that.
> for the same key, does this mean the dh key is 2048bit and the dss key
> is 1024bit?
Yes. The DSA spec says that DSA parameters p and q must be limited in
size (p to 1024 bits, q to 160). Both restrictions seem bizarre to me.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED]
Subject: libdes: des_SPtrans
Date: Thu, 22 Jun 2000 11:37:13 GMT
hi all,
i'm porting a portion of libdes to a handheld terminal with very little
code memory (32K). if i can get to calculate des_SPtrans table
in "spr.h" i can save 4K, that makes 12.5%. does anyone know the
algorithm to calculate the table? i ananlysed it for some time but
could not get to an answer. thanks in advance.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Encryption on missing hard-drives
Date: 22 Jun 2000 07:57:37 EDT
Mok-Kong Shen wrote:
>
>[EMAIL PROTECTED] wrote:
>
>> ABC news reported today that "[Bill] Richardson said he has changed
>> the procedure which now requires information such as the data on the
>> hard drives to be encrypted" which strongly implies that it
>> wasn't. Really though, no amount of encryption is going to help in the
>> face of abysmal physical security. Twenty six people were allowed
>> unescorted access to the vault, and could remove items without signing
>> for them. On top of that, the last inventory was for the y2k
>> inspection.
>
>Judged with commonsense, one can conclude that the materials involved
>(despite the official claims) could not be very critical. I base my
>conjecture
>on a case I know: In the seventies a friend developed a program for a
>certain hightech firm. The program was on a magnetic tape and kept in a
>vault. Each time when the program got run, the tape was taken from the
>vault to the computing centre and put back after the run, always under
>the supervision/protection of an armed guard. Even years after leaving
>the firm, he was requested to provide informations about the names of
>countries he visited during vacations. So it seems unbelievable that the
>present hard-drive could contain materials that are really any precious.
>
>M. K. Shen
>
You are missing the cultural differences. These aren't employees of a
high tech firm. Thjese are scientists with a core belief that keeping
secrets is silly, futile, moronic, and a big game that they win whenever
they circumvent the military security procedures.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: How encryption works
Date: 22 Jun 2000 08:02:39 -0400
> 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?
n is part of the public and private key. To encrypt, one needs to know e and
n. The public key is made up of the two numbers (e,n).
The private key is the pair (d,n).
NOTE that the above is NO GOOD. e MUST BE RELATIVELY PRIME TO p-1 AND q-1. You
have e=3 and q-1=6! NO GOOD! If you must use p=5, q=7, then p-1=4,
q-1=6. Unfortunately, there are only (1/2)(2/3)*24 numbers relatively prime to
and smaller than 24 (8 of them: 1, 5, 7, 11, 13, 17, 19 and 23: The number of
solutions to x^2=1 mod 24 is also 8. For this example, n=35, you have chosen
an n so small, that for any private key you pick, (e,35), the public key is
the SAME!). BAD EXAMPLE!
Let me take p=5, q=11: n=55: (p-1)*(q-1)=4*10=40=8*5. Now let me take e=3 (now
it IS relatively prime to (p-1)(q-1)) and d=27.
>>2) if M=message, is this the checksum of the whole message, of 1 character,
>>blocks of characters, or what?
You can only encrypt messages of size M<n. n is chosen to be large. M can be
broken up into pieces of that size. For example, the word "this" can be
encoded in ascii as (in hex): 0x74686973 (0x74=t, 0x68=h, etc.) which is the
decimal number 1,952,999,795. If you want to encde "this" in one step (intead
of breaking down into smaller number, 0x7468, 0x6973, say for "th" and
"is") you need an n of at least this size. However, usually one does not
actually encode text with RSA (it is too slow) but encodes a random number
(large and a larger n). That random number is used as the key for a different
method of encoding (e.g. IDEA - a faster method) in which the actual text is
encrypted.
>>3) the line with "d=....". When I did this out, (3^(-1)) mod ((4)(6)) didn't
>>equal 16... I got 1/3.
What is 1/3? It is the number which when multiplied by 3 gives 1.
In my corrected example (p=5, q=11, e=3, n=55, (p-1)(q-1)=40) we DO want
1/3. The "thing" which multiplied by 3 gives 1. BUT we are not doing regular
rational number arithmetic. We want e*d=1 mod (p-1)(q-1) - we are doing mod_40
arithmetic (we only have integers from 0 to 39). What IS (1/3)_mod_40? It is
the number which multiplied by 3 gives us 1 (mod_40). Well,
3*27=81=1+2*40=1 mod_40.
So ... 1/3 = 27 (in mod 40 arithmetic).
>>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]?
See above. One often does not use RSA to encrypt, but some other method
(e.g. IDEA) (since it is faster). But those faster methods do not use public
keys. To use a public key with them, one uses RSA (or Diffie-Hellman, another,
related method) not to encrypt the message, but to encrypt the random number
that is used for IDEA to encrypt the actual text message.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: How encryption works
Date: 22 Jun 2000 08:09:42 -0400
Simon Johnson <[EMAIL PROTECTED]> wrote:
> 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)
Ooops!
Well ... what is d*e mod pq?
What is de mod (p-1)(q-1)?
If you want the inverse of e mod pq, you can use d=e^[(p-1)(q-1)-1] but that
is the inverse mod pq. So ... finding the inverse mod n involves factoring n
into its prime factors (finding phi(n)). To find the inverse of e mod
(p-1)(q-1) would involve finding all the prime factors of the numbers p-1 and
q-1 if you wanted to use the Totient function. If you can do THAT, can factor
numbers of that size, then you could crack RSA!
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: libdes: des_SPtrans
Date: 22 Jun 2000 13:31:19 GMT
[EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
> i'm porting a portion of libdes to a handheld terminal with very
> little code memory (32K). if i can get to calculate des_SPtrans table
> in "spr.h" i can save 4K, that makes 12.5%. does anyone know the
> algorithm to calculate the table? i ananlysed it for some time but
> could not get to an answer. thanks in advance.
It's a combination of a bunch of small substitution tables and a bit
permutation. My version of DES, in Catacomb, provides a program which
generates such tables from the original tables provided in the
definition of DES. Interstingly, libdes's table isn't actually the same
as mine.
If interested, see http://www.excessus.demon.co.uk/misc-hacks/#catacomb.
-- [mdw]
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: Encryption on missing hard-drives
Date: Thu, 22 Jun 2000 07:44:21 -0600
Reply-To: [EMAIL PROTECTED]
Guy Macon wrote:
> Mok-Kong Shen wrote:
> >
> >[EMAIL PROTECTED] wrote:
> >
> >> ABC news reported today that "[Bill] Richardson said he has changed
> >> the procedure which now requires information such as the data on the
> >> hard drives to be encrypted" which strongly implies that it
> >> wasn't. Really though, no amount of encryption is going to help in the
> >> face of abysmal physical security. Twenty six people were allowed
> >> unescorted access to the vault, and could remove items without signing
> >> for them. On top of that, the last inventory was for the y2k
> >> inspection.
> >
> >Judged with commonsense, one can conclude that the materials involved
> >(despite the official claims) could not be very critical. I base my
> >conjecture
> >on a case I know: In the seventies a friend developed a program for a
> >certain hightech firm. The program was on a magnetic tape and kept in a
> >vault. Each time when the program got run, the tape was taken from the
> >vault to the computing centre and put back after the run, always under
> >the supervision/protection of an armed guard. Even years after leaving
> >the firm, he was requested to provide informations about the names of
> >countries he visited during vacations. So it seems unbelievable that the
> >present hard-drive could contain materials that are really any precious.
> >
> >M. K. Shen
> >
>
> You are missing the cultural differences. These aren't employees of a
> high tech firm. Thjese are scientists with a core belief that keeping
> secrets is silly, futile, moronic, and a big game that they win whenever
> they circumvent the military security procedures.
That's rather insulting to those who disarm nuclear weapons in the field.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Variability of chaining modes of block ciphers
Date: Thu, 22 Jun 2000 16:28:08 +0200
Mark Wooding wrote:
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> > It is not seldom the case that one's favourite good cipher has a fixed
> > key size and hence that slight longer-ness isn't available,
> > unfortunately. Variability of key size is a design virtue in my
> > humble view but appears to be rather difficult to realize well in
> > certain types of encryption algorithms.
>
> How strange. I've seen very few recent ciphers which have fixed-length
> key sizes. I suppose that the CAST ciphers are a case in point, but I
> also suspect that CAST-128 is `good enough' without playing silly games
> with chaining modes. All of the AES entries support keys at least as
> large as 256 bits, which is `more than enough'; MARS and RC6 are notable
> in allowing much longer keys. Blowfish, RC4, and RC5 all support
> `sufficiently[1] large keys'. Bolting the Rijndael key schedule into
> Square would increase key size to `more than enough' (but I suspect that
> the Counterpane team's analysis of Rijndael has demolished Square along
> the way, so it wouldn't be worth it). SEAL's key is fixed at 160 bits,
> which is a bit of a shame, although a variant based on (say) Tiger
> rather than SHA1 would easily increase this.
>
> Finally, if your `favourite' cipher doesn't have a large enough
> keyspace, that's a good reason for picking a different `favourite'.
> May I recommend Blowfish? ;-)
>
> [1] In the Rolls-Royce sense.
It is indeed strange that you have seen very few recent ciphers which
hav fixed-length key sizes. The most recent ciphers of significance are
certainly the AES candidates. How many of these allow you to vary the
key size from 128 by steps of, say, 8 all the way to 256? (Note we
were discussing about 'slightly larger keys', not giant jumps.)
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Length of pseudo random digits
Date: Thu, 22 Jun 2000 16:28:23 +0200
Tim Tyler wrote:
> Jacques Th�riault <[EMAIL PROTECTED]> wrote:
>
> : How can I calculate the period of a random digit generator.
>
> : Is there any formula to estimate such a period?
>
> Here are a couple of approaches:
>
> 1) Test the output to see if it is periodic. Depending on your
> application, you may need to do this with more than one possible seed.
>
> Typically this only lets you conclude with certainty that a cycle
> doesn't exist. You can't conclude with certainty that there's
> definitely a cycle from any finite volume of output - since (e.g.)
> "...10101010101..." may be part of a genuinely random sequence.
For a PRNG, the period may depend on the seed. So testing with
one seed may not be useful. I am not clear how one can determine
that a cycle doesn't exist in case it indeed doesn't exist.
> 2) Examine the algorithm and its documentation in an attempt to
> demonstrate using mathematical proofs that cycles no shorter than a
> given length exist.
>
> If your random digit generator is deterministic - i.e it's a PRNG, rather
> than an attempt at an RNG - you can place an upper bound on the possible
> period by examining the size of the generator's internal state.
>
> There are a couple of common cases worth mentioning:
>
> If your generator is reversible, and each state has a random but unique
> precursor, there a formula to give the expected period.
>
> If your generator simulates a random map between states, there's another
> formula to give the expected period.
But one may not be able, or at least not easily, to find the formulae.
(Compare finding the integrals of certain functions.)
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Variability of chaining modes of block ciphers
Date: Thu, 22 Jun 2000 16:31:15 +0200
Mark Wooding wrote:
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> > If you believe that your cipher is really strong enough, then you of
> > course don't need to consider anything extra. ECB is then presumably
> > already o.k.
>
> No. ECB has weaknesses (block rearrangement and copying) which apply
> even with an ideal block cipher.
That's why I favour use of chaining.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Variability of chaining modes of block ciphers
Date: 22 Jun 2000 14:35:05 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> That's why I favour use of chaining.
So do I. It's just that varying your method seems silly. Pick one, say
CBC with ciphertext stealing, and use a good cipher.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Variability of chaining modes of block ciphers
Date: 22 Jun 2000 14:42:14 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> It is indeed strange that you have seen very few recent ciphers which
> hav fixed-length key sizes. The most recent ciphers of significance
> are certainly the AES candidates. How many of these allow you to vary
> the key size from 128 by steps of, say, 8 all the way to 256? (Note we
> were discussing about 'slightly larger keys', not giant jumps.)
Off the top, RC6, Twofish, Serpent, and CAST256. I think (but don't
quote me) that MARS and HPC also qualify here, and possibly other things
like DFC and Frog. Rijndael's key can be increased in steps of 32 bits.
I'm not actually sure what a `slightly larger key' buys you anyway. If
you think that n bits isn't enough, n + 3 bits isn't likely to make you
much happier. Use 4 n instead.
-- [mdw]
------------------------------
Subject: Re: Try it.
From: John <[EMAIL PROTECTED]>
Date: Thu, 22 Jun 2000 08:04:22 -0700
Hmmm...I wonder, though, should they just have put the source
code on this group? :-) HOw can they make money if they can't
protect there source? Oh well, this is sure a strange business.
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
** 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
******************************
