Cryptography-Digest Digest #870, Volume #10 Sat, 8 Jan 00 19:13:01 EST
Contents:
Re: simple block ciphers (David Wagner)
Re: simple block ciphers (David Wagner)
Re: Intel 810 chipset Random Number Generator (Scott Nelson)
Re: How to obtain updated SSL certificate for Navigator-3? (Lincoln Yeoh)
Help needed with RSA decrypt ("Keith")
Re: Mispronounce words. (OT Re: How to pronounce "Vigenere"?) (Lincoln Yeoh)
Re: Wagner et Al. ("John E. Kuslich")
Re: Help needed with RSA decrypt ([EMAIL PROTECTED])
Re: REDOC: First use: key dependent S-BOXES (David Wagner)
Re: OLD RLE TO NEW BIJECTIVE RLE (Tom St Denis)
Re: OLD RLE TO NEW BIJECTIVE RLE (Tom St Denis)
Re: simple block ciphers (Tom St Denis)
Re: Intel 810 chipset Random Number Generator (Bradley Yearwood)
Re: Wagner et Al. (Tom St Denis)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: simple block ciphers
Date: 8 Jan 2000 11:24:05 -0800
In article <856979$nlm$[EMAIL PROTECTED]>,
David A Molnar <[EMAIL PROTECTED]> wrote:
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> > Encrypt(x) = x^e mod p
> > Where (d, e, p) is the private key.
> > And if p is private, can a small p be used (say around 128 bits?)
>
> The only "attack" which comes to me right off is noticing how big each of
> the values are. I'm not sure how effective that is.
There's a chosen-plaintext/ciphertext attack that recovers p:
Pick a random z>p. Request the decryption p of z.
Request the encryption c of p. Note that (z mod p) = c,
so p | z-c, and p will fall out.
(If needed, make two queries, and compute gcd(z-c,z'-c').)
Once p is known, a discrete log computation will break the scheme,
so if p is 128 bits, the scheme will be totally insecure.
Better make p be at least 768 bits long. But then this symmetric-key
system is no faster than public-key operations, and moreover, there
doesn't seem to be much point to keeping p secret...
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: simple block ciphers
Date: 8 Jan 2000 11:27:31 -0800
In article <8582sl$72i$[EMAIL PROTECTED]>,
David Wagner <[EMAIL PROTECTED]> wrote:
> > Tom St Denis <[EMAIL PROTECTED]> wrote:
> > > Encrypt(x) = x^e mod p
> > > Where (d, e, p) is the private key.
>
> There's a chosen-plaintext/ciphertext attack that recovers p:
Oh, and there's a chosen-plaintext attack, too:
Pick a small plaintext x so that x < p/2.
Request the encryption y of x, the encryption z of 2, and
the encryption z of 2x. Note that yz = a mod p, so that
p | yz-a. If you can factor yz-a, p will fall out.
More likely, you'll want to make two such queries, and
then use gcd(yz-a,y'z'-a') as your estimate for p.
------------------------------
From: [EMAIL PROTECTED] (Scott Nelson)
Subject: Re: Intel 810 chipset Random Number Generator
Reply-To: [EMAIL PROTECTED]
Date: Sat, 08 Jan 2000 19:32:54 GMT
On 08 Jan 2000 07:36:24 EST, [EMAIL PROTECTED] (Guy Macon) wrote:
>
>http://developer.intel.com/design/chipsets/rng/docs.htm
>
>http://developer.intel.com/design/chipsets/datashts/290658.htm
>
>http://www.intel.com.ec/design/chipsets/rng/faq.htm
>
>http://www.rsasecurity.com/products/bsafe/intel/
>
>http://www.rsasecurity.com/products/bsafe/intel/rsa_rng_nontech.pdf
>
>http://www.rsasecurity.com/products/bsafe/intel/rsa_rng_tech.pdf
Thanks, that's much more helpful.
Personally I liked this one the most:
http://www.intel.com.ec/design/chipsets/rng/CRIwp.htm
After plodding through all this stuff, I still am not sure
whether this is an existing device, or a proposed device,
but a basic summary seems in order;
The noise sources is a highly amplified resistor.
This is processed in several ways;
The output of a another, adjacent resistor is
subtracted from it.
The result is used to skew a low frequency clock.
The low frequency clock samples a higher frequency
clock (about 100:1).
That bit is feed through a Von Neumann rejector
(which is apparently patend-pending :-)
and finally it's stored in a 32 bit register.
I hate to sound negative, but frankly, the overall
design doesn't look very good to me. The addition
of a single gate would have converted the final stage
from a storage register to a mixing accumulator.
The clock skew is questionable, and the choice
of a Von Neumann type rejector is annoying, since
it means variable output rates. This would be
an acceptable tradeoff if it reduced bias to near
0, but apparently, it doesn't. And that failure
is troubling as well. Considering that it's a
hardware device, an average 75Kbps isn't very
impressive performance.
For me, the 810 HRNG is only worth considering
if it's price is low. Anyone know what this
thing is supposed to cost?
Scott Nelson <[EMAIL PROTECTED]>
------------------------------
From: [EMAIL PROTECTED] (Lincoln Yeoh)
Subject: Re: How to obtain updated SSL certificate for Navigator-3?
Date: Sat, 08 Jan 2000 20:34:51 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 05 Jan 2000 11:56:13 -0700, Sundial Services
<[EMAIL PROTECTED]> wrote:
>I happen to like and to prefer Navigator 3, but its site-certificates
>expire on December 31st. How can I obtain new certificates? (I have
>actually downloaded ... ick ... Communicator 4.)
Just delete the certs you don't want.
Link.
****************************
Reply to: @Spam to
lyeoh at @[EMAIL PROTECTED]
pop.jaring.my @
*******************************
------------------------------
From: "Keith" <[EMAIL PROTECTED]>
Subject: Help needed with RSA decrypt
Date: Sat, 8 Jan 2000 20:37:56 -0000
I'm doing an annual Xmas quiz, which has the following question:
This cipher has been constructed by the RSA method with public key (55,27);
the ciphered message is simply I-E-Y-W.
The answer is probably topical for the time of year ( I suspect 2000 if it
is only 4 characters).
I know diddley-squat about encryption - and haven't the time and inclination
to dive in, having just read the RSA FAQ which seems all theory and little
practice. Can anyone please help me witheither the answer, or a tool that
will enable me to decrypt this?
Thanks,
Keith
------------------------------
From: [EMAIL PROTECTED] (Lincoln Yeoh)
Subject: Re: Mispronounce words. (OT Re: How to pronounce "Vigenere"?)
Date: Sat, 08 Jan 2000 20:42:43 GMT
Reply-To: [EMAIL PROTECTED]
On Sat, 08 Jan 2000 02:13:30 GMT, [EMAIL PROTECTED] (Nemo Outis)
wrote:
>Unfortunately if enough people persist long enough in mispronouncing these
>words, they (or their children) will eventually become "right," since what
>constitutes "correct English" is "descriptive rather than prescriptive,"
Let's vote for pronouncing omnipotent as omni-potent. :).
Link.
****************************
Reply to: @Spam to
lyeoh at @[EMAIL PROTECTED]
pop.jaring.my @
*******************************
------------------------------
From: "John E. Kuslich" <[EMAIL PROTECTED]>
Subject: Re: Wagner et Al.
Date: Sat, 08 Jan 2000 13:31:35 -0700
<snip>
>
> >This means that if an attacker somehow gains access to a computer,
>
> Then all bets are off, and all computers and operating systems are
> vulnerable. If you don't have physical security you don't have security.
>
> >There is very little software can do to protect itself from anyone who
> >can gain access to your computer either by physical means
>
> Agreed 100%.
>
> > or by the network through BackOrfice and similar trojans.
>
> A properly secured and administered NT installation is highly
> resistant to having trojans installed.
>
> >Resistance is futile...at least as far as crypto software on the PC is
> >concerned.
>
> Here is where we part company. The argument that imperfections in
> a scheme make the scheme not worth doing is a fallacy. It's like
> saying that a car thief can break into my car with a slimjim and
> hotwire it, so I might as well leave the doors open, the key in the
> ignition, and the engine running. Even easy to defeat security
> measures are often worth doing.
I know some neighborhoods where this is applicable :--))
We seem to have achieved a remarkable degree of agreement, once we had a
chance to spill our beans. The problem is security, like safety, is
never achieved to a 100% level. Nor does it have to be at this level
for all applications.
I will now express pure opinion, based on my own particular observations
and personal experience:
Software protection schemes are not likely to be effective against a
really competent attack - NT or no NT. For anyone attempting to protect
really valuable information, physical security is a must. Also, *most*
modern programmers I have contact with do not have an appreciation for
this fact since they usually only have exposure to the PC at a higher
level of abstraction than necessary to properly understand the risk.
I'm outta here.
JK
--
John E. Kuslich
Password Recovery Software
CRAK Software
http://www.crak.com
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Help needed with RSA decrypt
Date: 8 Jan 2000 16:55:02 -0500
Keith <[EMAIL PROTECTED]> wrote:
> I'm doing an annual Xmas quiz, which has the following question:
> This cipher has been constructed by the RSA method with public key (55,27);
> the ciphered message is simply I-E-Y-W.
> The answer is probably topical for the time of year ( I suspect 2000 if it
> is only 4 characters).
You have an exponent (e=27) and modulus (n=55). The modulus is p*q where p
and q are primes (5,11) (n=pq).
RSA encodes numbers (no larger than the modulus) (number from 1-55 in this
case) (text is converted to numbers ... somehow).
To decode, you must find d so that d*e has remainder 1 when divided by p-1
(4) and q-1 (10) - or, when divided by their least common multiple (20).
So... what times 27 has a remainder of 1 when divided by 20?
d=3 (3*21=81 has remainder 1 when divided by 4 and when divided by 10).
To decode a number x, one then takes the remainder one gets for x^d when
dividing by n (the modulus).
In this case one wants the remainders of dividing x^3 by 55.
How are letters converted to numbers? ASCII? 8 bit? With what parity? In
this case, none of that. Just its position in the alphabet (I=9=ninth
letter, E=5=fifth letter, Y=25=twenty-fifth letter, W=23=twenty-third
letter).
So we have to take x^3 and the remainder when dividing by 55, where x=9,
5, 25 and 23.
So..
x x^3 remainder when x^3 is divided by 55
9 729 14
5 125 15
25 15625 5
23 ? ??
The 14th letter in the alphabet is N
The 15th letter in the alphabet is O
The 5th letter in the alphabet is E
The ?th letter in the alphabet is ?
You should be able to guess the answer :-)
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: REDOC: First use: key dependent S-BOXES
Date: 8 Jan 2000 14:10:30 -0800
In article <[EMAIL PROTECTED]>,
karl malbrain <[EMAIL PROTECTED]> wrote:
> Both REDOC and KHUFU are circa 1990, as far as I know.
Yes, both Khufu and REDOC II were proposed at Crypto'90.
However, while Khufu uses truly key-dependent S-boxes, REDOC II
does not: REDOC II selects from a fixed, public set of 16 possible
substitution tables using key material, and this is (IMHO) very
different from the fully key-dependent S-boxes pioneered in Khufu.
I mistakenly thought your original post was referring to REDOC III,
which does (if I remember correctly) come closer to the ideal of
fully key-dependent S-boxes, but came later than REDOC II and Khufu.
As far as I can tell, the proper credit for fully key-dependent
S-boxes (as used in modern ciphers such as Blowfish and CAST)
goes to Merkle. Correct me if I'm wrong.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: OLD RLE TO NEW BIJECTIVE RLE
Date: Sat, 08 Jan 2000 22:44:18 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (John Savard) wrote:
> On Sat, 08 Jan 2000 04:01:14 GMT, Tom St Denis <[EMAIL PROTECTED]>
> wrote:
>
> >Actually the point of encryption is to eliminate bias. Compression
is
> >suppose to simply remove redundancy. So your point is moot.
>
> >Let me re-iterrate
>
> >COMPRESSION = MAKE SMALLER
> >ENCRYPTION = MAKE RANDOM
>
> Ah, but compression _works_ - it couldn't make things smaller in any
> other way - by making things more random. Thus, modifying a
> compression scheme so that this randomness is more evenly spread, or
> whatever, so as to make ciphertext-only attacks on subsequent
> encryption harder, is a perfectly legitimate endeavor.
If a compression algorithm has bias in the output then failed in it's
goal to remove redundancy. But deflate has less redundancy then
huffman (1-1) for any given english text [for example]. This is an
indirect proof that deflate has less bias then huffman.
In other words. The compression ratio is higher for deflate, which
means there is more bits of info per bit out. This hardly can be in
the form of bias...
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: OLD RLE TO NEW BIJECTIVE RLE
Date: Sat, 08 Jan 2000 22:47:34 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> : [EMAIL PROTECTED] wrote:
> :> John Savard <[EMAIL PROTECTED]> wrote:
>
> :> : (For myself, while I too think removing certain reduncancies from
> :> : compression have their uses, I quarrel with any attempt to
emphasize
> :> : one-to-one purity at the expense of bias. [...]
> :>
> :> Bias in the resulting compressed file is certainly important.
> :>
> :> Which is /more/ important depends partly on the relative sizes of
the
> :> bias caused by lack of elimination of redundancies in the
plaintext, and
> :> the bias introduced by a lack of 1-1 compression.
>
> : Actually the point of encryption is to eliminate bias.
>
> No. The point of encryption is to make recevering the plaintext
difficult
> given the cyphertext. Encryption schemes that produce highly non-
random
> cyphertext certainly exist - and even have concrete applications.
By making the ciphertext random you have successfully removed the bias.
> : Compression is suppose to simply remove redundancy. So your point
is moot.
>
> Removing redundancy has the side effect of reducing bias. So my
point was
> correct.
No it's not. Deflate removes more redundancy then huffman, this means
deflate has less bias in the output.
Think about this. How could deflate have more bias in the output *AND
STILL* compress better then huffman...?
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: simple block ciphers
Date: Sat, 08 Jan 2000 22:53:10 GMT
In article <856979$nlm$[EMAIL PROTECTED]>,
David A Molnar <[EMAIL PROTECTED]> wrote:
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> > [first I did not invent this ...!!!]
>
> Looks kind of like polig-hellman, but with the modulus kept secret,
> too. (unless the modulus is secret in P-H; applied crypto isn't clear
on
> this point)
>
> > p = random prime
> > e = random prime less then p
> > d = chosen such that de = 1 mod (p - 1)
>
> > Encrypt(x) = x^e mod p
> > Decrypt(x) = x^d mod p
>
> > Where (d, e, p) is the private key.
>
> For what it's worth, you have a malleability problem (or
> "feature") : E(x) * E(y) = E(xy), since x^e * y^e = (xy)^e
>
Sorry that must be a typo... cause x^e * y* != xy^e, the bases are not
the same. If they were it would be x^2e ...
> The only "attack" which comes to me right off is noticing how big
each of
> the values are. I'm not sure how effective that is. Here's what I'm
> thinking :
>
> say p is k bits long. Let's also say that it's between 2^{k-1} and 2^
{k}.
> It can't be a perfect power of 2, 'cause then it wouldn't be prime. So
> when we send blocks, we aren't going to get a perfectly uniform
> distribution on numbers between 1 and 2^k, since we will never see a
> number greater than p.
>
> What fraction of numbers are excluded? It seems to me that this
> fraction is :
>
> 2^k - p (number of #s we'll never see)
> -------
> 2^k (total numbers)
>
> well, at best, if 2^k -1 is our prime, this is 1/2^k (really small).
At
> worst, p is really close to 2^{k-1}. So we have approximately
>
> 2^k - 2^{k-1} 2^k * .5
> ------------- = ----------------------- = .5
> 2^k 2^k
>
> or just less than half the numbers we'd expect thrown out.
>
> If you knew exactly what this fraction was, it seems to me that you'd
> determine p. What I don't know is how large a sample you'd need before
> you could get a guess for p, or what your confidence in that guess
might
> be. That may provide part of an answer to your question. I need to
study
> more statistics...
>
> As it is, once you have a guess, you may want some way of checking
it. How
> about this :
>
> We know that x^e * y^e = (xy)^e for any x, y, e. What about if we
> have x^e mod p, x^e mod p, and x^e * y^e mod q ? What happens if q !=
p?
> i.e. q is your guess and you guess wrong? does this identity still
hold?
>
> if the identity doesn't hold, AND you have someone who will tell you
if a
> ciphertext is "correctly formed" or not, it seems you could check your
> guess. and maybe refine your estimate ?
The number of prime moduli eliminitated can be approximated with
n = block size
m = 8+n = size of prime [in sig bits]
a = 2^m / ln 2^m
b = 2^n / ln 2^n
c = a - b
In the case of n=64, c= ~2^66.35, which means there are about
94045974794340509523 prime moduli >2^64 but <2^72...
Obviously simply 'noticing' the modulus is gonna be hard...
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Bradley Yearwood)
Subject: Re: Intel 810 chipset Random Number Generator
Date: 8 Jan 2000 15:01:01 -0800
In article <[EMAIL PROTECTED]>,
Scott Nelson <[EMAIL PROTECTED]> wrote:
>
> <interesting criticisms of Intel RNG design>
>
>For me, the 810 HRNG is only worth considering
>if it's price is low. Anyone know what this
>thing is supposed to cost?
I am not familiar enough with the current state of the motherboard and
chipset market to be definitive, but the 810 chipset appears to be
positioned toward the medium-low segment of the market.
Dell's OptiPlex GX100 and GX110 use the 810 chipset, whereas the more
expensive GX1 and GX1P use the 440BX chipset.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Wagner et Al.
Date: Sat, 08 Jan 2000 22:58:03 GMT
In article <8575rd$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Guy Macon) wrote:
> Nope. That's why I said "often worth doing". Everything in life
> is a series of tradeoffs, and in this case you have to factor in
> the amount of harm to you if your message is read, what kind of
> attacker is likely (Script Kiddy? NSA? Local Police Dept?). and
> how much time and money you have available. "Best possible" is
> usually even stupider than "None".
True enough.
> Agreed, and (in the case of PGP) only if the trojan is customized
> to attack PGP, and has NT administrator rights. The latter is very
> unlikely if your system administrator understands security.
Good so we can stop saying 'attacking PB' since it's OS related. A
good forum on OS security [which this turned into] would be more
usefull for win95/98 owners... :)
[BTW I will entertain any attacks against PB... I am confident i made
it well, but I am a student [for life :)] and still have much to learn].
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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
******************************
