Cryptography-Digest Digest #565, Volume #10 Sun, 14 Nov 99 02:13:01 EST
Contents:
Re: Build your own one-on-one compressor (SCOTT19U.ZIP_GUY)
Re: about the win rng using the timer (Tom St Denis)
Re: Build your own one-on-one compressor (SCOTT19U.ZIP_GUY)
Re:SCOTT16U SOLUTION ON THE WEB (SCOTT19U.ZIP_GUY)
Re: Public Key w/o RSA? (DJohn37050)
Re: Proposal: Inexpensive Method of "True Random Data" Generation ("james d. hunter")
Quantum Cracking (UBCHI2)
Re: Proposal: Inexpensive Method of "True Random Data" Generation ("Trevor Jackson,
III")
Codebook examples on Web? (UBCHI2)
Re: Need technique for about 24 bytes (Boris Kazak)
Re: PALM PILOT PGP found here (Peter W)
Re: Public Key w/o RSA? (Jerry Coffin)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Crossposted-To: comp.compression
Subject: Re: Build your own one-on-one compressor
Date: Sun, 14 Nov 1999 01:07:05 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>In sci.crypt SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
>: In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>
>[snip]
>
>:>However, there /are/ techniques which attempt to disguise the file length,
>:>through the use of random padding.
>:>
>:>**If** these are used, the analyst may well be able to usefully discard
>:>supposedly compressed files if they are an odd number of bytes long.
>
>[snip]
>
>:>"Scott" commonly mentions that ``Comp(Decomp(X)) = X for all X''
>:>is what one-on-one compression involves.
>:>
>:>The scheme under discussion fails this - if X is an odd number of bytes long.
>:>
>:>I don't want to stress this too much - for most applications, it's probably
>:>a relatively minor issue.
>
>: Actually you still can make one to one compress if you redefine a byte to
>: be 16 bits.
>
>Well, that would be a "henious terminological sin" - a byte is 8 bits ;-)
>
>: That way all files of your english text when tokenized would
>: be a mulitply of 16bits.
>
>Fine if you're only compressing unicode. Not much help for other things ;-/
>
>To illustrate the nature of the problem when dealing with "ordinary"
>files an integral number of bytes long, consider the following example:
>
>Warning, this example is a little complex.
>
>"Hiding" consists of compressing with method "A", prepending between one
>and three random bytes to the file, and then applying David's "Adaptive
>Huffman" compression. The file is then encrypted.
>
>"Unhiding" consists of the reverse: decrypt, decompress, remove 1-3 bytes
>from the start of the file and decompress again.
>
>"Unhiding" will normally result in three possible messages, depending on
>the number of bytes removed. The recipient decides which message makes
>sense.
>
>I will consider only a brute force attack in this instance.
>
>If compression method "A" is my (8-bit) dictionary-based method,
>the analyst typically has to decompress all three files with David's
>decompressor, to decide if he can reject the key.
>
>If compression method "A" is a 16-bit method which leaves the files an
>even number of bytes long, the 1-byte addition and 3-byte additions can be
>rejected before the final decompression is attempted, based on the file
>length. This results in less work for the attacker, and a weaker system.
>
>I mentioned that this example was contrived? ;-)
>
>The point is only that the security considerations for an 8-bit 1-1
>compressor are not quite the same as for a 16-bit one.
I think one can if one wish trans fer the text to an intermiditae file of
16 bit multiples and then compress with a modiefed huffman compress
so that it still compress to 8 bit boudariers. that way all possible binary
8-bit multiple files wihen decompress fo to a 16 bit multiply intermediate
file and then to the text. I am not saying to do this I am saying you can
still get a 1-1 mapping from the ascii test to 8bit binary files.
What I said a few message back was before I gave it more thought.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website NOT FOR WIMPS
http://members.xoom.com/ecil/index.htm
Scott rejected paper for the ACM
http://members.xoom.com/ecil/dspaper.htm
Scott famous Compression Page WIMPS allowed
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: about the win rng using the timer
Date: Sun, 14 Nov 1999 00:05:28 GMT
In article <80jkrs$ekq$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
> I ran my version of his rng for 2^20 bits and got some results...
>
> Order-16 analysis, lo=?[can't remember sorry], hi=34, me=16,ame=~6500
>
> lo = lowest count
> hi = highest count
> me = median
> ame = # of counts at median
>
> I am doing a bigger test now. Generally though i think it will do
> well. The order-0 stats are good.
>
> I will do a 32x65536 test today [under 'load' conditions of
> icq+winamp+email] and copy the results. I will also check out # that
> are close to median [+/- 4 which is 12.5% error].
>
> I think under 'load' conditions which is pretty much all the time,
this
> rng works well.
Apparently it does. I did a test using the previous 8 bits to keep
statistics [basically using]
++tags[m = ((m << 1) | (c = get_bit())) & (T-1)];
Where m are the psat T bits, and tags[] are the counters for each
possible value from (0, T]. (did I get those brackets wrong?)
All tags (from 0..255) where ame, which means +/- 12.5% from the mean
over only 2^20 bits this is ok. This means no one predecessor (upto 8
bits) is more likely to occur.
If anyone wants the source to the entire test program just ask... it's
quite short, but requires a win32 c compiler (I would suggest lccwin32).
At anyrate this has some potential on computers with a load [say a few
apps]. I think the use of the self-shrinking style generator is good
to make the outputs more irregular.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Crossposted-To: comp.compression
Subject: Re: Build your own one-on-one compressor
Date: Sun, 14 Nov 1999 01:11:59 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>[total snip]
>
>This post is a public question, directed mainly at David.
>
>Do you think it would be possible to adapt your scheme of dealing with
>the file ending for Huffman coding to Arithmetic coding schemes?
>
I think it is possible but it would not be pure arithmetic. Since
in a highly biased file 1 bit could stand for many charaters. Example
would be a file of 2 character types but one is a thousand times more
likely. I woud have to mod the arthmetic but I am sure one can
do something.
>I don't doubt it's possible /in principle/ - and I also suspect it might
>not be easy in practice - this question is mainly intended to find out
>if you have any idea how it might be done, not whether you plan to
>actually do it.
I am thinking of working on it after a bit of it but I am not done
with the huffman thing yet.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website NOT FOR WIMPS
http://members.xoom.com/ecil/index.htm
Scott rejected paper for the ACM
http://members.xoom.com/ecil/dspaper.htm
Scott famous Compression Page WIMPS allowed
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re:SCOTT16U SOLUTION ON THE WEB
Date: Sun, 14 Nov 1999 01:17:23 GMT
In article <[EMAIL PROTECTED]>, Gondolin Remailer
<[EMAIL PROTECTED]> wrote:
>I have asked you this question before but did not get a satisfactory
>reply. Why do you object to the AES submissions. Have you done any
>cryptoanalysis on any of the candidates, and if so could you please
>publish your findings.
If you did not get a anwser you liked before I doubt I will give you
one you like this time. But to sum it up try to do a contest like
my SCOTT19U contest with any of the AES methods.
>
>1. If you know anything about crypto , you know its not just the length of
>the key that is the major issue of whether an algo is week or not. Also
>the key space and week keys are relavent.
Is this a question. Yes you are correct.
>
>2. You claim that the 3 letter Chaining techniques (ECB,CBC,CFB,OFB)
>weeken the algorithm , if that is my understanding of your statement. If
>not, perhaps you can explian here what your objections are.
You got it that is what I meant.
>
>
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website NOT FOR WIMPS
http://members.xoom.com/ecil/index.htm
Scott rejected paper for the ACM
http://members.xoom.com/ecil/dspaper.htm
Scott famous Compression Page WIMPS allowed
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Public Key w/o RSA?
Date: 14 Nov 1999 00:48:21 GMT
Also, there are concerns with RSA.
If there is a bit flip using CRT (Chinese Remainder Theorem, essentally all
implementations use this) then one can find your entire private key. For
example, if you send out a signature that does not verify, see Dan Boneh again
for this.
RSA public key validation (showing that a candidate RSA public key actually
meets the generation requirements) is still a research topic, doing validation
for DL or ECC keys is straightforward and is fact is already in standards (ANSI
X9.62, X9.42).
Don Johnson
------------------------------
From: "james d. hunter" <[EMAIL PROTECTED]>
Crossposted-To: sci.math,sci.misc,sci.physics
Subject: Re: Proposal: Inexpensive Method of "True Random Data" Generation
Date: Sat, 13 Nov 1999 22:03:55 -0500
Reply-To: [EMAIL PROTECTED]
John Savard wrote:
>
> "james d. hunter" <[EMAIL PROTECTED]> wrote, in part:
>
> >I think you better define random first, before you discuss it.
> >"Random" only makes sense in terms of a random process.
> >Strings are usually interpreted as -fixed- outputs of a
> >random process. "Incompressibility" has to do with the information
> >content of the -fixed- string. There is nothing really "random" about
> >it.
>
> You are correct here, as far as that goes.
>
> However:
>
> - there is a relationship between randomness and incompressibility.
> Given a properly random - or shall I be highfalutin' and say
> "stochastic" - message source, its output will be incompressible;
> there will be no net benefit in attempting to compress the occasional
> accidentally patterned output from it.
Given a properly random process, cryptographers obviously
would not keep asking what the definition "random" is. So, we
can assume that stochastic processes do not in reality exist.
------------------------------
From: [EMAIL PROTECTED] (UBCHI2)
Subject: Quantum Cracking
Date: 14 Nov 1999 03:42:42 GMT
Have there been any further developments in theoretical quantum factoring or
quantum list lookup functions?
------------------------------
Date: Sat, 13 Nov 1999 22:44:11 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: sci.math,sci.misc,sci.physics
Subject: Re: Proposal: Inexpensive Method of "True Random Data" Generation
Coen Visser wrote:
> "Trevor Jackson, III" wrote:
>
> > Coen Visser wrote:
>
> > > Keep in mind that compression is defined + O(1)
> > > [...]
> > > I have just compressed infinitely many strings of a special form
> > > "010101..." and left all other strings untouched (+O(1)).
>
> > Hardly. You have added a prefix bit to every string. So you did touch "all other
>strings". Their
> > representations are now larger, and the sum of their increase will outweigh the
>decrease in the
> > strings you compressed.
>
> I thought that the arbitrary large but constant factor O(1)
> was understood. Furthermore I gave an example of just one type
> of string containing a certain pattern. I hope you didn't expect me
> to do this for all strings that contain compressible patterns. That
> would bring the balance more in your direction. Especially when
> using optimal compression (which is just a theoretical concept).
No.
Your constant (the degree of compression of strings containing repeated "01") is
smaller than my constant
(the extra bit for all strings). This indicates that, while you are remapping the set
of strings onto
itself, you are not compressing it.
>
>
> > > So, you're use statistical tests. It happened to be proved that a string
> > > that passes all [*] statistical tests within the required confidence
> > > level
> > > is incompressible (and random because it passed the tests). So our
> > > definitions
> > > start to look dangerously equivalent.
> >
> > Not at all. You are assuming that a string that passes statistical tests is
>random. I am assuming
> > that a string that fails statistical tests is non-random. We are worlds apart.
>
> I disagree. We are just talking from other sides
> of an otherwise fair coin. Passing or failing *all* statistical
> tests is just a matter of how you define the tests.
I think there's a class of all classes problem with your last statement. But until
you deal with the
single instances I've mentioned, I'm not going to tackle one of your universal claims.
------------------------------
From: [EMAIL PROTECTED] (UBCHI2)
Subject: Codebook examples on Web?
Date: 14 Nov 1999 04:54:52 GMT
Are there any examples of famous codebooks on the net? I want to see how the
Gray code and other historical diplomatic codebooks were constructed.
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Subject: Re: Need technique for about 24 bytes
Date: Sat, 13 Nov 1999 20:57:32 -0800
Reply-To: [EMAIL PROTECTED]
Caesar Valenti wrote:
>
> Thanks to all of you for your suggestions. I am still looking into all
> the above posts emails; and am now reading Applied Crypto....a major
> undertaking in itself!
>
> Here is a bit more info:
> This will be used in a device that will essentially verify its own serial
> number (which the routine can read). All devices must use the same
> routine and probably the same key. I could base the key on the serial
> number, but the serial number is what is being encoded/decoded. The
> platform is Windows NT. I can use C/C++ or VB. What I envision is
> something similar to Microsofts CD key.
>
> For example, the plaintext would be somthing like this (ignore the
> dashes):
> SN-ABCD-0123456-9999999 where the first 13 chars are the serial number,
> and the remaining chars would be some device dependent info. At this point
> I don't know how many extra chars there will be...maybe 5 to 10?? The
> device could then verify that the first 13 chars match the serial number
> of that device. If so, it would then act upon the remaining bits. I
> would like the ciphertext to completely change even if only one char is
> changed. The actual length is not critical; it just must be relatively
> easy to enter....how much do YOU like entering Microsofts 25 char CD
> key!??
>
> And finally, security is only a moderate concern as it is unlikely our
> customers will go thru much
> effort to defeat this....besides, one could always monitor the CPU to
> reverse engineer this.
=========================
Are you sure that you need encryption and not hashing?
If I understand correctly your problem, the serial number of
the device is not secret, but you want to give the
customer a key which will combine itself with the
serial number and authenticate the customer as legitimate.
A hash function with a keyed hash will nicely serve this
purpose. If the resulting hash is stored somewhere inside the
device software, then even reverse-engineering the hash
function will serve no purpose. Only the legitimate user who
has the proper key can produce the proper hash for
authentication.
All devices can use the same routine, but correct hash will
be produced only when the serial number and the user's key
will both match.
Best wishes BNK
================================
>
> Thanks
>
> Gary wrote:
>
> > What is the destination platform?
> > IE What are the memory, bandwidth, error rate, and cpu (8,16,32 bit?)
> > limitations?
> > Is the string made up of completely random characters or does it have
> > redundancy which could squeeze the string into 15 8 bit bytes (each
> > character averaging 5 bits)?
> > These parameters effect what type of compression and cipher algorithms
> > should be used.
------------------------------
From: Peter W <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,comp.sys.palmtops.pilot
Subject: Re: PALM PILOT PGP found here
Date: Sun, 14 Nov 1999 00:18:44 -0500
Keith A Monahan wrote:
> I know a bunch of people (including myself) were looking for PGP
> for their 3com Palm Pilots. You can find it at the following URL
> which is at the North American Cryptography Archive,
> http://cryptography.org/
Has anyone tried Paul Gargan's PalmOS PGP?
http://www.compapp.dcu.ie/Projects/1999/pgarga.ca4/funcspec.html
It sounds very promising, but also appears to need a bit of work. Perhaps
somebody outside the black hole of the US & Canada could take a look at the
buggy and unimplemented parts?
-Peter
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: Public Key w/o RSA?
Date: Sat, 13 Nov 1999 22:35:26 -0700
In article <80higt$h25$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
> How many public-key crypto algorithms are there? I'm new to this, and I
> keep hearing about RSA, but are there others? And if so, then why is RSA in
> particular so popular?
There are LOTS of systems, but most are based on one of three
fundamental algorithms: factoring (RSA) discrete logarithms (Diffie-
Hellman) or elliptical-curve discrete logarithms (ECC).
There are probably a lot of reasons that RSA is the most popular of
these, some more obvious than others. First of all, RSA is quite
versatile. DH (for example) is useful almost exclusively for
distributing a key. By contrast, RSA can be used for distributing a
key, doing actual encryption (though this is rare due to its low
speed) digital signatures, etc. In addition, until recently, there
was little reason to favor DH over RSA: it allows slightly smaller
keys to retain the same level of security, but other than that it has
little technical advantage.
OTOH, the patent on DH has recently expired, so it's now used in quite
a few free programs of various kinds. I suspect RSA will come into
substantially wider use when its patent runs out as well.
Elliptical curve cryptography has a number of advantages. First of
all, its keys can be substantially smaller than those for either DH or
RSA. Second, it's possible to implement it without infringing on any
patents, though Certicom holds patents on some ways of doing things
more efficiently than (at least the well known) public-domain methods
of implementing it.
There are at least a couple of obvious reasons that ECC is less used.
First of all, it was introduced the most recently of these three
methods. Second, the math involved in either RSA or DH is
conceptually quite a bit simpler and more widely taught than the math
involved in ECC. Somebody who does reasonably well in a high-school
math class probably knows more than enough to understand RSA and DH
with only minimal explanation. If somebody has a degree in electrical
engineering (for one example) there's still a pretty fair chance that
they've never taken any classes in math closely related to elliptical
curves.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
** 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
******************************
