Cryptography-Digest Digest #554, Volume #12 Mon, 28 Aug 00 07:13:00 EDT
Contents:
Re: On pseudo-random permutation (Mok-Kong Shen)
Re: PRNG Test Theory (Mok-Kong Shen)
Re: Steganography vs. Security through Obscurity ("Douglas A. Gwyn")
Re: My encryption algorithm (Mok-Kong Shen)
Re: PRNG Test Theory ("Douglas A. Gwyn")
Re: Patent, Patent is a nightmare, all software patent shuld not be (Mok-Kong Shen)
Re: Who can show me a good Cryptology site? ("kihdip")
Re: PRNG Test Theory (Mok-Kong Shen)
Re: Patent, Patent is a nightmare, all software patent shuld not be allowed (qun
ying)
Re: On pseudo-random permutation (Benjamin Goldberg)
Re: My (New) New algorithm (Mok-Kong Shen)
Re: SHA-1 program, wrongo ! (those who know me have no need of my name)
Re: avalanche characteristic (Mok-Kong Shen)
e-cash protocol concept, comments wanted (Julian Morrison)
Re: Patent, Patent is a nightmare, all software patent shuld not be
([EMAIL PROTECTED])
Re: Patent, Patent is a nightmare, all software patent shuld not be (Mok-Kong Shen)
Re: On pseudo-random permutation (Tim Tyler)
Re: e-cash protocol concept, comments wanted (Ragni Ryvold Arnesen)
Re: PGP ADK Bug: What we expect from N.A.I. ("Michel Bouissou")
Re: The DeCSS ruling - Reverse engineering? (Gisle =?iso-8859-1?Q?S=E6lensminde?=)
Re: Bytes, octets, chars, and characters (Johnny Billquist)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: comp.programming
Subject: Re: On pseudo-random permutation
Date: Mon, 28 Aug 2000 10:22:14 +0200
Bryan Olson wrote:
>
> Mok-Kong Shen wrote:
>
> [...]
> > If the collision resolution is chosen such that the first
> > element of the pair is always considered less than the
> > second, then indeed there is a bias. The effect is however
> > dependent on the chance of collision, which is practically
> > negligible when the space of the random numbers is large,
> > e.g. 32 bits.
>
> Specifically, the when the space of the random numbers is
> large compared to the number of elements being permuted.
>
> > One can on the other hand use a random
> > choice rule to resolve collision, in which case no bias
> > can occur.
>
> False for any of the usual sorting algorithms. Remember
> that collisions are not limited to two elements. You could
> achieve zero bias (assuming a perfect RNG) by recursively
> applying the procedure to each non-singleton collision set.
>
> Though the recursive procedure terminates with probability
> one, it is technically a non-terminator. Given a generator
> of perfect random bits as the one and only source of
> randomness, can you find any procedure for generating
> perfectly uniform random permutations (of more than two
> elements) that strictly terminates? Can you show that no
> such procedure exists?
(Theoretically) technically the matter is even much
worse. For, in order to have a meaningful result, one has
to be sure that one has a perfect random sequence at hand
but there is no way of verifying that in practice.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: PRNG Test Theory
Date: Mon, 28 Aug 2000 10:22:07 +0200
Bryan Olson wrote:
>
> There is no universal test of randomness. There is no
> algorithm that can distinguish bits produced by an algorithm
> from truly random bits.
Right, though lots of theories apparently assume there
IS something that is perfectly random. Whether this
could mean a problem of certain philosophical nature I
am not very certain.
BTW, the gist of the other follow-ups was questioning
whether the approach indicated by the original poster
is methodologically meaningful even under practical
points of view.
M. K. Shen
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Steganography vs. Security through Obscurity
Date: Mon, 28 Aug 2000 04:14:05 -0400
Runu Knips wrote:
> So stenography does NOT require obscurity. It only hides the
> fact if there is an encrypted message OR if there is random
> data.
No, that's wrong. Some successful steganographic schemes hide
the message without encrypting it; the method of hiding itself
uses a crypto key, but that is used to select sites, modes,
etc., while the data itself is used directly.
In many applications, the main goal of steganography is to
avoid detection, which is in effect a requirement for obscurity.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: My encryption algorithm
Date: Mon, 28 Aug 2000 10:28:00 +0200
Runu Knips wrote:
>
> The funnier part is that I miss the previous posting of the one I'm
> now answering, while all postings I've written friday didn't
> appeared on my server.
Couldn't a server crash be an explanation?
M. K. Shen
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: PRNG Test Theory
Date: Mon, 28 Aug 2000 04:20:39 -0400
Mok-Kong Shen wrote:
> Bryan Olson wrote:
> > There is no universal test of randomness. There is no
> > algorithm that can distinguish bits produced by an algorithm
> > from truly random bits.
> Right, though lots of theories apparently assume there
> IS something that is perfectly random. Whether this
> could mean a problem of certain philosophical nature I
> am not very certain.
It's not a problem. The characteristics of random processes
are solidly defined, and deductions can be made on that basis.
The observation that there is no perfect test for randomness
is almost trivial, because it would require an infinite amount
of data, which of course is not feasible.
However, there are some very good tests for deviation from
randomness, some of which are routinely used in cryptanalysis.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Patent, Patent is a nightmare, all software patent shuld not be
Date: Mon, 28 Aug 2000 10:38:48 +0200
Paul Rubin wrote:
>
> There are lots of bogus patents and it's good to post about them. But
> please, always include the patent number. What is the patent number
> of this one?
I am fairly sure that the web page, from which the quote
was made, is bogus (not serious). On the other hand there
are problematical and troubling patents, e.g. Hitachi's
rotation that menaces AES.
M. K. Shen
------------------------------
From: "kihdip" <[EMAIL PROTECTED]>
Subject: Re: Who can show me a good Cryptology site?
Date: Mon, 28 Aug 2000 10:26:58 +0200
>Where should I go to get the most on Cryptology?
John Savard has a pretty good site:
http://fn2.freenet.edmonton.ab.ca/~jsavard/crypto.htm
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: PRNG Test Theory
Date: Mon, 28 Aug 2000 10:47:09 +0200
"Douglas A. Gwyn" wrote:
>
> Mok-Kong Shen wrote:
> > Bryan Olson wrote:
> > > There is no universal test of randomness. There is no
> > > algorithm that can distinguish bits produced by an algorithm
> > > from truly random bits.
> > Right, though lots of theories apparently assume there
> > IS something that is perfectly random. Whether this
> > could mean a problem of certain philosophical nature I
> > am not very certain.
>
> It's not a problem. The characteristics of random processes
> are solidly defined, and deductions can be made on that basis.
I suppose that could be an arguable point. If something is
'solidly' defined, it should be verifiable in my view.
One could namely say that, if something is not (ultimately)
discernable, then it doesn't exist in the world, I suppose.
M. K. Shen
------------------------------
From: qun ying <[EMAIL PROTECTED]>
Subject: Re: Patent, Patent is a nightmare, all software patent shuld not be allowed
Date: Mon, 28 Aug 2000 08:31:34 GMT
The patent number is US 6,061,448
In article <8od5aa$egs$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Paul Rubin) wrote:
>
> There are lots of bogus patents and it's good to post about them. But
> please, always include the patent number. What is the patent number
> of this one?
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Crossposted-To: comp.programming
Subject: Re: On pseudo-random permutation
Date: Mon, 28 Aug 2000 08:46:17 GMT
Bryan Olson wrote:
[snip]
> Though the recursive procedure terminates with probability
> one, it is technically a non-terminator. Given a generator
> of perfect random bits as the one and only source of
> randomness, can you find any procedure for generating
> perfectly uniform random permutations (of more than two
> elements) that strictly terminates? Can you show that no
> such procedure exists?
For a list of objects that has no more than 2**N elements, associate
each element with an N bit number.
for( i = N-1; i >= 0; --i ) {
foreach group that has the same number
do {
foreach item in group
item.number ^= randbit() << i;
} while( all items in group have the same number );
sort( list by number );
if( no_collisions(list) )
break;
}
Note that if the RNG is broken the do-while loop will continue forever,
and the algorithm won't terminate.
--
... perfection has been reached not when there is nothing left to
add, but when there is nothing left to take away. (from RFC 1925)
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: My (New) New algorithm
Date: Mon, 28 Aug 2000 11:05:30 +0200
[EMAIL PROTECTED] wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >
> > [EMAIL PROTECTED] wrote:
>
> > > This seems like an example of a Maurer stream cipher.
> >
> > What is a 'Maurer stream cipher'?
>
> Look on the web.
>
> http://www.counterpane.com/labs.html
I suppose it is not good to use terminology that are not
used in standard texts like AC or HAC, in particular
when used without giving references.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (those who know me have no need of my name)
Subject: Re: SHA-1 program, wrongo !
Date: Mon, 28 Aug 2000 08:51:06 GMT
<[EMAIL PROTECTED]> divulged:
><<doesn't your environment support stat or fstat?>>
>My sole C resource to this date has been K&R2.
you don't even have the documentation to djgpp. tragic.
--
okay, have a sig then
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: avalanche characteristic
Date: Mon, 28 Aug 2000 11:07:17 +0200
Terry Ritter wrote:
>
> Avalanche Effect
> The result of avalanche. As described by Webster and Tavares:
>
> "For a given transformation to exhibit the avalanche effect, an
> average of one half of the output bits should change whenever a single
> input bit is complemented." [p.523]
>
> Webster, A. and S. Tavares. 1985. On the Design of S-Boxes.
> Advances in Cryptology -- CRYPTO '85. 523-534.
They also proposed the strict avalanche criterion. See Menezes
et al. p.277.
M. K. Shen
------------------------------
From: Julian Morrison <[EMAIL PROTECTED]>
Crossposted-To: alt.cypherpunks,alt.cypherpunks.technical
Subject: e-cash protocol concept, comments wanted
Date: Mon, 28 Aug 2000 10:34:05 +0100
If you are knowledgeable about ecash, please check out my idea for a
signature-based ecash protocol at
http://fling.sourceforge.net/concepts.html
Are there any major design bugs?
Are there major improvements you could suggest?
How does this compare to other ecash proposals you know of?
Thanks in advance for any comments.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Patent, Patent is a nightmare, all software patent shuld not be
Date: Mon, 28 Aug 2000 09:42:24 GMT
Mok-Kong Shen wrote:
> > There are lots of bogus patents and it's good to post about them. But
> > please, always include the patent number. What is the patent number
> > of this one?
>
> I am fairly sure that the web page, from which the quote
> was made, is bogus (not serious). On the other hand there
> are problematical and troubling patents, e.g. Hitachi's
> rotation that menaces AES.
> M. K. Shen
http://www.patents.ibm.com/details?&pn=US06061448__
== <EOF> ==
Disastry
http://i.am/disastry/
remove .NOSPAM.NET for email reply
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Patent, Patent is a nightmare, all software patent shuld not be
Date: Mon, 28 Aug 2000 12:30:15 +0200
[EMAIL PROTECTED] wrote:
>
> Mok-Kong Shen wrote:
> > > There are lots of bogus patents and it's good to post about them. But
> > > please, always include the patent number. What is the patent number
> > > of this one?
> >
> > I am fairly sure that the web page, from which the quote
> > was made, is bogus (not serious). On the other hand there
> > are problematical and troubling patents, e.g. Hitachi's
> > rotation that menaces AES.
> > M. K. Shen
>
> http://www.patents.ibm.com/details?&pn=US06061448__
Indeed! Unless someone detects real points of patentability
(as commonly understood) in there, which is not at all
discernable from the text available as such, this means
there is really a risk of what I mentioned sacarstically
long time ago, namely oneday someone will get a patent of
how a human being breathes the air and from that point on
those who can't afford to pay loyalities must find a way
of living an-aerobically (there are organisms of that
sort).
M. K. Shen
------------------------------
Crossposted-To: comp.programming
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: On pseudo-random permutation
Reply-To: [EMAIL PROTECTED]
Date: Mon, 28 Aug 2000 10:17:48 GMT
In sci.crypt Bryan Olson <[EMAIL PROTECTED]> wrote:
: Given a generator of perfect random bits as the one and only
: source of randomness, can you find any procedure for generating
: perfectly uniform random permutations (of more than two
: elements) that strictly terminates? Can you show that no
: such procedure exists?
This appears to be essentially much the same question as:
It it possible to pick an integer from {1,2,3} with each element
occurring with exactly equal frequency - and with termination
guaranteed - if one is only given a random bitstream.
AFAIK, the answer to this question is "no" - on the grounds that no
power of two is divisible by three, and any truncation to produce a
range that /is/ divisible by three introduces potential termination
problems.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: Ragni Ryvold Arnesen <[EMAIL PROTECTED]>
Crossposted-To: alt.cypherpunks,alt.cypherpunks.technical
Subject: Re: e-cash protocol concept, comments wanted
Date: Mon, 28 Aug 2000 12:31:29 +0200
Julian Morrison wrote:
> If you are knowledgeable about ecash, please check out my idea for a
> signature-based ecash protocol at
> http://fling.sourceforge.net/concepts.html
>
> Are there any major design bugs?
> Are there major improvements you could suggest?
> How does this compare to other ecash proposals you know of?
>
> Thanks in advance for any comments.
Two major considerations for a bank deciding whether or not to support
an e-cash system are security and transaction costs (not necessarily in
that order). At first glance I cannot see any security problems with
your system, but the transaction costs will probably be huge if there
are many small coins floating around.
-Ragni
------------------------------
From: "Michel Bouissou" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,comp.security.pgp.discuss
Subject: Re: PGP ADK Bug: What we expect from N.A.I.
Date: Mon, 28 Aug 2000 12:36:55 +0200
Ed Reppert <[EMAIL PROTECTED]> a écrit dans le message :
[EMAIL PROTECTED]
>
> If I understand this whole thing (and I'm not sure I do) ADK is a means
> for a third party to require that its public key be included in the
> public keys of certain parties
ADK is more accurately the indication, embedded in somebody's public key,
that every message encrypted to this public key *should* be as well
encrypted to a 2nd public key which fingerprint is given (which identifies
the 2nd key the message should be encrypted to).
In a "normal" situation, the ADK is included in the public key at key
generation time.
The bug recently discovered allowed a forger to include an ADK of its own
into an already existing public key over which the attacker normally has no
control.
>(employees, in the one somewhat unclear
> reference to ADK I've seen, and perhaps citizens, in a country which
> requires that agencies of its government have access to all encrypted
> data transmitted to or from its citizens or locations {eg, RIP in the
> UK, or similar efforts in the US) so that anything destined for that
> party can be decrypted by the third party.
ADK has been designed for company use, not for goverment use, because it
would necessitate that all citizens keys would be generated by a system that
would include a governement ADK into them, which is not the case in PGP.
> While I can see the interest
> in such a capability, it seems to me to violate the spirit of the whole
> concept of personal privacy in communications. However, that's a
> political question more than a technical one, and I have some technical
> ones.
This is highly a political question, but also a technical one, because
incorporating features such as ADK into PGP creates new possible technical
weaknesses, and thus creates a new path for possible attacks, as this story
unfortunately showed.
On a political standpoint, ADK for sure was not designed in the "personal
privacy" spirit, but in a "business privacy" spirit, for companies that have
a need for cryptography, but wouldn't allow their employees to use
cryptosystems, sending or receiving messages that would be out of control of
the management.
> I have downloaded the freeware 6.5.8 version (for MacOS) that was put up
> at mit on Friday. Looking at it, the pgp 6.5 manual that came with it,
> and at the previous version (6.5.4) of the freeware package, I can find
> no reference to how to include an ADK in a public key. I infer that this
> capability is *only* in the commercial version of the software. Is that
> correct?
As far as I know, this is correct.
> Freeware 6.5.8 does have a flag which would indicate if an ADK is
> present, but not, if I understand correctly, whether it is inside or
> outside the encrypted "envelope" of the key file. IOW one can tell if an
> ADK is present, but not if it breaks confidence in the privacy of the
> encryption (assuming one doesn't care -- or is resigned to accepting it
> -- if a known third party can decrypt the message). Is this correct?
No. This problem was present with versions prior to 6.5.8. The matter was
that PGP didn't make any difference between a "legitimate" ADK and a
"forged" one. In both situations, PGP was processing the ADK and encrypting
to the corresponding key -- provided this key was also present in the user's
keyring.
PGP 6.5.8 is the fix N.A.I. made to PGP. With 6.5.8., a "legitimate" ADK
will be processed, but, a "forged" ADK will be ignored, and PGP will behaves
as if the forged public key was a good one, but without any ADK.
PGP 6.5.8 will not encrypt a message to a forged ADK, but will not warn that
there is a forged ADK in the key either.
My previous posts on the 6.5.8. versions test explain why this hotfix is not
enough.
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Gisle =?iso-8859-1?Q?S=E6lensminde?=)
Subject: Re: The DeCSS ruling - Reverse engineering?
Date: 28 Aug 2000 12:41:01 +0200
In article <8o5hs7$5on$[EMAIL PROTECTED]>, rot26 wrote:
>Putting the debate of legality of reverse engineering (RE) aside, I just
>wonder whether any such act of RE has actually taken place. Since it is
>clearly stated on the paper "Cryptanalysis of Contents Scrambling
>System" that analysis is based on "a piece of source code claiming to be
>the css algorithms, and which have since been confirmed to interoperate
>with the CSS system."
>
>The point I want to make is that in order to write the paper the author
>need not perform any decompilation, disassembly, or taking apart
>physical components. Little doubt that DeCSS software is based on the
>paper
No, DeCSS is _not_ based on that paper. The paper was released after
DeCSS, and DeCSS did not use the attack in the paper, but exhaustive
key search, or found an actual player key by reverse engineering of
a software DVD player. Of cause they may have used the same piece
of sourcecode as analysed in the paper, but they do not use any
of the information that was fist presented there, so I doubt they
knew about the paper. It was probably not even written yet.
> and I suspect little further info about the CSS algorithm is
>required (i.e. not given on the paper), how is it that anyone would have
>violated the law regarding RE?
The DeCSS theam have probably extracted a player key from a piece
of software, and that is undoubtly reverse engineering. Thay said
so when DeCSS was released anyway.
So it's possible to write a program decoding DVD without knowledge
of keys, by only using the DVD analysis paper and the source code
it was based on, and in that case you point is valid.
--
Gisle Sælensminde ( [EMAIL PROTECTED] )
With sufficient thrust, pigs fly just fine. However, this is not
necessarily a good idea. It is hard to be sure where they are going
to land, and it could be dangerous sitting under them as they fly
overhead. (from RFC 1925)
------------------------------
From: Johnny Billquist <[EMAIL PROTECTED]>
Crossposted-To: comp.lang.c,alt.folklore.computers
Subject: Re: Bytes, octets, chars, and characters
Date: Mon, 28 Aug 2000 11:06:24 GMT
David Thompson wrote:
>
> John Savard <[EMAIL PROTECTED]> wrote :
> ...
> > However, in the past, it had been customary to refer to a six-bit area
> > in a computer's memory, where such an area was the span of memory
> > occupied by a character of a text, as a character.
> >
> Not necessarily six bits. It is usual to refer to the storage for one
> (fixed-length) character code as a character, yes, of course,
> and six bits is enough for one (Roman) alphabet, (decimal) digits,
> and modest punctuation and specials (e.g. BCDIC).
Yup.
> > The term byte did not come into general use until computers stored
> > characters in 8-bit areas.
> >
> I don't think so. The PDP-8 had 6-bit bytes (often but
> not always used for characters) by 1966, which is
> close to the first S/360, which AFAIK was the first
> *widespread* machine using and addressing an 8-bit byte.
The PDP-8 didn't. I thought we had already covered this.
The PDP-8 have nothing but word handling in hardware until
the PDP-8/E, which came 1971 and had the BSW instruction, which
is 6-bit oriented, and coule be argued as a sign that the PDP-8
regarded bytes as 6 bits.
(I think the connection between BSW and 6-bit bytes is strenous
at best, but before BSW you will not find anything in the hardware).
> The PDP-10 (and -6?) at very nearly the same time,
> as others have already said, had variable bytes,
> most commonly 6, 7, 9.
Yes. And on the PDP-10 atleast, the term byte does exist in the hardware,
and you have different insturctions that handles bytes.
And the PDP-10 was before the 8/E, and if the PDP-6 also have the
byte instructions, then we're back to about 1965.
> ASCII is not an international standard, although there are several
> for character codes based on and intentionally similar to ASCII.
I think there is some ISO standard which matches ASCII, but I have
no idea what it is called.
Johnny
--
Johnny Billquist | [EMAIL PROTECTED]
Net Insight AB | phone: +46 8 685 04 88
Västberga Allé 9 | fax: +46 8 685 04 20
Box 42093 |
SE-126 30 STOCKHOLM, Sweden | http://www.netinsight.net
------------------------------
** 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
******************************
