Cryptography-Digest Digest #803, Volume #9 Tue, 29 Jun 99 20:13:04 EDT
Contents:
Re: trapdoor one way functions (Jonathan Katz)
Re: DES-NULL attack (John Curtis)
Re: MP3 Piracy Prevention is Impossible ([EMAIL PROTECTED])
Re: The One-Time Pad Paradox (Jim Gillogly)
Re: Windows9x Crypt Function ([EMAIL PROTECTED])
eliptical curve cryptosystems ([EMAIL PROTECTED])
Re: The One-Time Pad Paradox ("Dr.Gunter Abend")
Re: Why mirrors invert left-to-right (was: Kryptos article) ("Douglas A. Gwyn")
Re: one time pad (Don Dodson)
Re: Why mirrors invert left-to-right (was: Kryptos article) ("Douglas A. Gwyn")
Re: Question on LIBDES (Paul Koning)
Re: eliptical curve cryptosystems (DJohn37050)
Re: two questions (William Tanksley)
Re: PIII Random Number Generator? (Anonymous)
Re: How do you make RSA symmetrical? (Gilad Maayan)
Re: How do you make RSA symmetrical? (Gilad Maayan)
Re: Hamming Weight ("ziggy")
Re: Secure link over Inet if ISP is compromized. (Paul Koning)
Re: Secure link over Inet if ISP is compromized. (Paul Koning)
Re: Hamming Weight (Jim Gillogly)
Re: PIII Random Number Generator? (William Tanksley)
Re: trapdoor one way functions (Nicol So)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Jonathan Katz)
Subject: Re: trapdoor one way functions
Date: 28 Jun 1999 21:58:41 -0400
In article <7l3m7b$9a8$[EMAIL PROTECTED]>, [EMAIL PROTECTED] writes:
|> I was wondering if there are any other trapdoor one way functions in
|> academia that don't use either the discrete logarithm problem or the
|> integer factoring problem.
|>
|> Basically I would like to research puzzles which are not 'large' number
|> oriented (which would dismiss ECC as well).
|>
|> If anyone has any hints, links or ideas please let me know.
|>
|> Tom
|> --
|> PGP key is at:
|> 'http://mypage.goplay.com/tomstdenis/key.pgp'.
|>
|>
|> Sent via Deja.com http://www.deja.com/
|> Share what you know. Learn what you don't.
I suggest you check out recent reviews of available public key cryptosystems.
Underlying any public key cryptosystem is a trapdoor one-way function (in some
guise or another). There have been PKCs based on error correcting codes, shortest-
vector lattice problems, and the knapsack problem (as well as a few others).
--
======================
Jonathan Katz
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (John Curtis)
Subject: Re: DES-NULL attack
Date: 29 Jun 1999 20:03:49 GMT
In article <[EMAIL PROTECTED]> Horst Ossifrage <[EMAIL PROTECTED]> writes:
>Thomas Pornin wrote:
>
>> Agreed. But Moore's law (*) will keep on getting it less secure every
>> year. This explains the 128-bit keys for the AES.
>
>
>My job is designing next generation microprocessors at a major
>company. You should expect the rate of improvement to slow down
>starting today. 18 years ago the prediction was that 0.1 micron
>transistor lengths would be near the smallest sizes practical
>for mass production, and that is one limitation for speed. Today
>one company is preparing 0.07 micron transistors. At work, we face
>the limits of scaling in 2 years for mass produced ICs. After 2001
>I expect a doubling of speed to take, not 18 months, but 36 months.
>After then, speed will increase more slowly. Heat, noise,
>and the speed of light are already very real constraints on
>improvements.
>of light
I take your estimates as being a reasonable estimate of
when limits will be reached. Never say never, but
there are some pretty daunting technical challenges out
there.
a. current densities go higher, which hits a pretty
fundamental limit in that electron collisions with
atoms in the metal layers cause migration which will
take small imperfections in the metal traces and
narrow them. Well known limit, Copper makes it better,
but it is still there. Electrons bumping into atoms is
pretty darn fundamental.
b. gate thickness is ~one order of magnitude away from
quantum limits that will grossly affect MOS transistors.
minor nits:
c. noise isn't a fundamental limit at this point, as the
impedences are too low to make inherent noise a problem.
d. heat isn't as difficult a limit as it appears. I offer
as evidence the absence of liquid cooled designs in mass
production.
Yeah, you're right, the speed of light is pretty fundamental %^).
ciao,
jcurtis
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: MP3 Piracy Prevention is Impossible
Date: 29 Jun 1999 16:30:34 -0400
Else <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] wrote in message <7lapgp$ok4$[EMAIL PROTECTED]>...
>>It's completely impossible to make sure that somebody can't share
>>the plaintext of a document with somebody else. Why try?
> It does not have to be "completely impossible". "Too expensive" would do
> just fine.
Yes ... I am registered on a site that has some proprietary documents. The
only access is (besides viewing it on screen) a print command for hard
copy (no file ... so one cannot share files). Very expensive and difficult
to get files. I had to install the plain text printer driver and
configure that to print to file.
(for graphics, I have installed a postscript driver set to print to file
and use GhostView/GhostScript to convert to BMP).
On some web sites there is real audio only available for streaming. Very
difficult to save copies of the file. I had to choose LOOPBACK as my
recording source and start up a sound recorder to record it while playing
(one conversion to/from analog to get a digital file).
It's not "impossible" nor even "expensive" nor even hard. However, it does
require a little bit of knowledge of how to get things done besides the
ability to turn on the computer and point and click one's way around the
WWW.
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: The One-Time Pad Paradox
Date: Tue, 29 Jun 1999 13:39:06 -0700
"Dr.Gunter Abend" wrote:
> It may happen (in real life) that you guess the truth from an
> accidental message, even if this message is pure nonsense.
"Psychic attacks" are outside the scope of academic cryptanalysis,
despite the fact that major governments have spent a fair amount of
resources trying to develop them. To see how bogus an attempted
defense is against the non-problem you describe above, consider that
the ciphertext is not necessary: the opponent can simply guess the
truth of what you might have sent, whether or not there was a message.
There is no defense against this, unless your psychic transmitters
are better than their psychic eavesdroppers.
> I would prefer such encryption techniques that *never* produce
> intelligible ciphertexts. If a ciphertext contains some letter
> combinations that resemble words, it should be rejected, i.e. the
> encryption should simply be repeated.
Since they have a far better chance of randomly guessing the wrong
plaintext than they do the right one, you're addressing a non-problem.
> In the case of a OTP one simply could use the same keystring as
> before, but starting with a little offset. This offset could be
> mentioned in the ciphertext, or you simply pad the plaintext with
> some meaningless bits (zeroes) at the beginning.
>
> Do you see any weakness in this modified OTP method? It merely
Sure -- it normally won't eliminate the problems you envision.
If the message is long enough, you can expect to find likely-looking
words in it easily. I just ran /dev/urandom for a while and got
a <lot> of likely fragments in the output of "strings". The chance
of finding a likely-string-free ciphertext of any appreciable length
is negligible.
> This trick does not resolve the problem of OTP keystrings of all
> 0's or the like. Excluding these exceptional (but random!) strings
> might weaken the cipher, however: how much? I suggest to skip
Again, it leaks information, which a true OTP will not. See the
previous messages in the thread to see how this happens to you.
--
Jim Gillogly
Highday, 6 Afterlithe S.R. 1999, 19:55
12.19.6.5.14, 5 Ix 2 Tzec, Sixth Lord of Night
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Windows9x Crypt Function
Date: Tue, 29 Jun 1999 20:42:46 GMT
This is just a guess, of course, but since Windows NT uses MD5 to hash
their passwords, I don't see why Win98 wouldn't. I could be mistaken,
of course.
In article <7lamio$fph$[EMAIL PROTECTED]>,
"Andrew Whalan" <[EMAIL PROTECTED]> wrote:
> I am looking to doing some research on some distributed networking and
it
> has come up that it would be an ideal situation to implement a brute
force
> cryptanalysis engine. Other ideas include proving/disproving various
> mathematical theories via exhaustion, but I am primarly interested in
> cryptography and data security.
>
> If anyone could provide me with some information about the windows 9x
crypt
> function or provide me with some resources as where I could find some
info
> it would be great.
>
> Thankyou in advance,
> Andrew Whalan
>
>
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: eliptical curve cryptosystems
Date: Tue, 29 Jun 1999 20:37:34 GMT
Does anybody know where I can get information about ECC's? I'm looking
for a site that preferably has information on all 4 implementations of
ECC's (encryption, signatures, two others I can't think of right now...)
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: "Dr.Gunter Abend" <[EMAIL PROTECTED]>
Subject: Re: The One-Time Pad Paradox
Date: Tue, 29 Jun 1999 22:45:21 +0200
Patrick Juola wrote:
>G.A.> I would prefer such encryption techniques that *never* produce
> >intelligible ciphertexts. If a ciphertext contains some letter
> >combinations that resemble words, it should be rejected, i.e. the
> >encryption should simply be repeated.
> >
> >In the case of a OTP one simply could use the same keystring as
> >before, but starting with a little offset. This offset could be
> >mentioned in the ciphertext, or you simply pad the plaintext with
> >some meaningless bits (zeroes) at the beginning.
> >
> >Do you see any weakness in this modified OTP method? It merely
> >excludes such ciphertexts that could give the adversary a hint,
> >even a misleading one. The actual keystring is still truely
> >random.
>
> I don't see any weaknesses -- but neither do I see any strength
> added. If the key is actually random (and more formally,
> independent), then the key-with-offset is no different than
> the key without offset.
That was my opinion, too.
> On what basis are you assuming that the first N bits are less random
> than the rest -- and why are you using a generator with an assumed
> flaw?
No, there is no flaw, and the first bits are not bad, but if you
skip them, the ciphertext changes completely. Hopefully, letter
clusters disappear due to the shifting.
Intelligible ciphertexts *may* give the Adversary a *hint*.
This is beyond mathematics, may be psychology.
Even the *existence* of a message from a specific sender may
give him valuable information.
The question simply was: do we get a *mathematical* weakness
when we try to solve the psychological problem (the "paradox").
> >This trick does not resolve the problem of OTP keystrings of all
> >0's or the like. Excluding these exceptional (but random!) strings
> >might weaken the cipher, however: how much? I suggest to skip
> >a portion of the random keystring in case the offset trick doesn't
> >work, i.e. several offset values produce letter combinations.
> >
> >Do you see any weakness in skipping a part of the preselected
> >random keystring? This "skipping" could simply be done by
> >sending a meaningless message that consumes this "bad" part of
> >the keystring.
>
> Yes. The weakness is well-documented in Shannon's mathematics; the
> key no longer obtains complete entropy and the system entropy is
> no longer sufficient to obtain perfect secrecy. Whether or not
> near-perfect secrecy suffices for your purpose is up to you --
> but you're going to a lot of extra trouble to obtain secrecy
> comparable to a good block cypher.
Why? If I *intended* to send this useless extra message, then
everything is correct, the keystring *is* random, and there is
no security flaw. However, if I send the extra message *only*
in order to modify the keystring, then obviously it is no more
truely random. Can you *quantify* this lack of randomness?
If this very little loss of mathematical security is compared
with the gain of psychological safety, one could make a rational
decision.
> You can probably see this most intuitively if you assume that
> what you are filtering out are English-looking strings, but
> what is actually encrypted is a different language; the proportion
> of (for example) long ``words'' appearing in the cyphertext will
> be different and biased.
I didn't imagine English words -- I had a simpler algorithm in
mind: check for letter tripletts with at least one vowel.
This would still be a rather rare condition!
But the question is: Does this kind of offset into the random
keystring cause any weakness at all?
There are several reasons, why one would prefer OTP encryption.
It is extremely safe - no possible backdoor, it does not depend
on specific hardware - except for the storage of the keystring,
the unnoticed theft of the key is unlikely, and it is denyable.
Ciao, Gunter
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Why mirrors invert left-to-right (was: Kryptos article)
Date: Tue, 29 Jun 1999 21:51:23 GMT
[EMAIL PROTECTED] wrote:
> The mapping is controlled by the frame of reference. Since the normal
> one is not inertial, the vertical axis is special. In one word the
> reason is "gravity".
That's why we think most easily of rotating ourselves around the
vertical axis for comparison purposes, but it isn't a "frame of
reference" issue in the relativistic sense.
------------------------------
From: [EMAIL PROTECTED] (Don Dodson)
Subject: Re: one time pad
Date: 29 Jun 1999 15:08:41 -0700
In article <7l90dl$vp8$[EMAIL PROTECTED]>,
Greg Ofiesh <[EMAIL PROTECTED]> wrote:
>Again, in theory. Now if you want to take this to the practicle, let
>me ask you, are you 100% certain (ready to bet your life on it) that
>the NSA does not yet have a working quantum computer or other highly
>advanced device that would make even a 1k bit keyspace very reasonable?
I am 100% certain that they do not have such a device. Such a machine
cannot be built in this universe, regardless of the technology.
Don
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Why mirrors invert left-to-right (was: Kryptos article)
Date: Tue, 29 Jun 1999 21:53:20 GMT
"S.T.L." wrote:
> The certain preferred orientation that YOU are using is simply thus:
> you and your mirror image (in this imaginary observation) have both
> your feet on the same floor and have your front-sides in the same
> direction. Therefore left-right is inverted.
That begs the question. You both have your right hand on the same
wall (perhaps), too.
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: Question on LIBDES
Date: Tue, 29 Jun 1999 11:38:44 -0400
Marc Hoeppner wrote:
>
> Hi,
>
> I am trying to understand the libdes version 4.01 of Eric Young, but there
> is something that I must have overlooked in the des_enc.c. The final inner
> function des_enc doesn't seem to use the key schedule at all which is
> abviously nonsense. Could someone please enlighten me?
Read the definition of the D_ENCRYPT macro.
paul
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: eliptical curve cryptosystems
Date: 29 Jun 1999 22:21:25 GMT
Check out IEEE P1363 for info on ways to do ECC signatures and key agreement.
ECC encryption is scheduled for P1363a. See www.certicom.com for a positive
slant on ECC. Check out the white papers and PKS ECC papers.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (William Tanksley)
Subject: Re: two questions
Reply-To: [EMAIL PROTECTED]
Date: Tue, 29 Jun 1999 22:52:57 GMT
On Tue, 29 Jun 1999 22:13:17 GMT, Douglas A. Gwyn wrote:
>[EMAIL PROTECTED] wrote:
>> 1. Block ciphers are actually more versitile than stream ciphers. A
>> block cipher can be used as a stream cipher, ...
>That's exactly backward. A block cipher *cannot* be used as a stream
>cipher, since nothing can be emitted until an entire block is ready.
DES-OFB uses a block cipher to generate a keystream, which is XORed into
the plaintext. Obviously, any block cipher could be used in OFB mode.
The stream is generated a block at a time, but it's trivial to break a
block into characters. As with most stream ciphers, the keystream is not
dependant on the data.
>This question seems to come up every few months, always with the
>same (mostly wrong) answers.
Naturally :).
--
-William "Billy" Tanksley
------------------------------
Date: Wed, 30 Jun 1999 00:20:27 +0200 (CEST)
From: Anonymous <[EMAIL PROTECTED]>
Subject: Re: PIII Random Number Generator?
See http://www.cryptography.com/intelRNG.pdf for an analysis by
Cryptography Research, Paul Kocher's consulting company. Kocher is
very well respected in the field and he indicates that the RNG is sound.
Note that Intel passes the RNG output through a SHA-1 whitener in the PC
library, so that any irregularities in the output should be well hidden
by this step. But even without this the data looks very good.
The RNG works on the principle of sampling a high speed clock by a low
speed one whose period is randomized by thermal noise. In effect there
is a high speed clock oscillating between 0 and 1, and you measure it
at a random point to get a random bit. More details are available in
the paper.
------------------------------
From: [EMAIL PROTECTED] (Gilad Maayan)
Subject: Re: How do you make RSA symmetrical?
Date: Tue, 29 Jun 1999 22:20:10 GMT
>No, this is not possible. is M^e < N, then M is trivially recovered.
Okay, I agree with you. But what about e? Assuming e was not known
(and yes, I do know that in conventional RSA e is assumed known),
would you be able to extrapolate e from the plaintext and cyphertext?
>Further, if M is 64 bits then M^e mod N won't be 64 bits as well.
Fine, but is there anything you can add to "M^e mod N" to get a 64 bit
cyphertext? Enlarging N, reducing the exponent, or something like
that?
>"You can lead a horse's ass to knowledge, but you can't make him think"
Yeah, well I'm trying. :)
------------------------------
From: [EMAIL PROTECTED] (Gilad Maayan)
Subject: Re: How do you make RSA symmetrical?
Date: Tue, 29 Jun 1999 22:05:35 GMT
>No offense but that was a really stupid post.
>I am not trying to be mean but you seem to not understand what PKC is
>for...
Did you even read my message, Tom? I want to use two different keys,
one for encryption, another for decryption. I'm just trying to figure
out how to make the RSA system symmetrical.
------------------------------
From: "ziggy" <[EMAIL PROTECTED]>
Subject: Re: Hamming Weight
Date: Tue, 29 Jun 1999 16:08:52 -0700
Anybody know where I can get a really fast B = A XOR 0? ROF4LOL!
Jim Gillogly <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> [EMAIL PROTECTED] wrote:
> >
> > What is a Hamming Weight and how does one calculate it?
>
> It's the number of 1-bits in your data. If your machine has a
> "population count" instruction, that's the easiest way; a table
> lookup or a shifting strategy may be the next best, depending on
> your architecture.
>
> One use is to determine how close your attempted plaintext is
> to some actual known plaintext.
>
> --
> Jim Gillogly
> Hevensday, 4 Afterlithe S.R. 1999, 23:55
> 12.19.6.5.12, 3 Eb 20 Zotz, Fourth Lord of Night
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: Secure link over Inet if ISP is compromized.
Date: Tue, 29 Jun 1999 15:59:59 -0400
Keith A Monahan wrote:
> ... And keep in mind that the current version of IP does not allow
> for any sort of authentication of packets.
Not true.
IPSec does that. It is optional for IPv4, mandatory for IPv6.
There are plenty of implementations of it, including at least
one free one (for Linux).
paul
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: Secure link over Inet if ISP is compromized.
Date: Tue, 29 Jun 1999 11:45:07 -0400
Gene Sokolov wrote:
>
> Let's assume that Alice and Bob both have dial-up Internet accounts. They
> want to establish a secure channel.
>
> Alice <--> ISP-A <--> Internet <--> ISP-B <--> Bob
>
> Do I understand this correctly, assuming that *all* their data is passed
> through ISP-A and ISP-B, there is absolutely no way to ensure secure
> communication between them if either of the ISP is controlled by the
> adversary? Alice and Bob would need another trusted channel to exchange data
> before secure Internet link can be established.
Right.
All security requires some sort of previously established trusted value
to get the process going. For example, Alice and Bob could use public
key based authentication algorithms, but only if Alice has a way to
verify
that the public key that supposedly belongs to Bob *really* belongs to
Bob.
That may be easy or not so easy. If Alice knows Bob's voice, she can
call him on the phone and have him read the MD5 hash of the public key
(PGP key fingerprint). Or Alice and Bob may both have a trusted copy
of the public key of a certification authority which will issue
certificates
for their public keys.
Sometimes you may get the impression that you don't need to have this
out
of band step, for example when using security services in web browsers.
But you still do: what happened is that you (perhaps without realizing
it) put your trust in a public key (root certificate) stored in the
browser itself. If you have reason to believe the browser's
distribution
media are clean, that may be good enough, but you do need to realize
you're depending on that assumption!
As Tony Lauck put it at Digital some years ago: "autoconfiguration
of security is a contradiction in terms".
paul
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Hamming Weight
Date: Tue, 29 Jun 1999 16:49:37 -0700
ziggy wrote:
>
> Anybody know where I can get a really fast B = A XOR 0? ROF4LOL!
I don't see the humor. Are you saying I should know how to count
1-bits in my data quickly independent of architecture, that csybrandy
should have looked up Hamming Weight instead of asking, or something
else entirely?
> Jim Gillogly <[EMAIL PROTECTED]> wrote ...
> > [EMAIL PROTECTED] wrote:
> > >
> > > What is a Hamming Weight and how does one calculate it?
> >
> > It's the number of 1-bits in your data. If your machine has a
> > "population count" instruction, that's the easiest way; a table
> > lookup or a shifting strategy may be the next best, depending on
> > your architecture.
> >
> > One use is to determine how close your attempted plaintext is
> > to some actual known plaintext.
--
Jim Gillogly
Highday, 6 Afterlithe S.R. 1999, 23:47
12.19.6.5.14, 5 Ix 2 Tzec, Sixth Lord of Night
------------------------------
From: [EMAIL PROTECTED] (William Tanksley)
Subject: Re: PIII Random Number Generator?
Reply-To: [EMAIL PROTECTED]
Date: Tue, 29 Jun 1999 22:54:55 GMT
On Wed, 30 Jun 1999 00:20:27 +0200 (CEST), Anonymous wrote:
>See http://www.cryptography.com/intelRNG.pdf for an analysis by
>Cryptography Research, Paul Kocher's consulting company. Kocher is
>very well respected in the field and he indicates that the RNG is sound.
>Note that Intel passes the RNG output through a SHA-1 whitener in the PC
>library, so that any irregularities in the output should be well hidden
>by this step. But even without this the data looks very good.
The SHA-1 whitener is required to make FIPS certification possible --
otherwise they can claim that your RNG isn't based on a standard.
--
-William "Billy" Tanksley
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: trapdoor one way functions
Date: Tue, 29 Jun 1999 20:09:00 -0400
Anton Stiglic wrote:
>
> It may become more clear with an example of a one-way trap door function:
>
> Menezes Van O. and Vanstone (alias: the big green book) gives an example
> of a one-way function (tought not to be one-way trap door):
>
> Take X = {1, 2, ...., 16} AND F(X) = remainder of (3^x)/17
>
> It's easy to compute the function but not so easy to found the inverse
> (try to found what x gives f(x) = 7) . This function has a small space,
> so of course it's feasable to found the inverse, but the point is that it's
> MUCH more work than to compute f(x).
> There doesn't seem to be any element that could help us compute the
> inverse easily (no trap door).
So far, you are the only person who gets my point (and chooses to add
something to this thread).
Nicol
------------------------------
** 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
******************************
