Cryptography-Digest Digest #509, Volume #10 Fri, 5 Nov 99 00:13:04 EST
Contents:
Re: How protect HDisk against Customs when entering Great Britain (That guy...from
that show!)
Re: Data Scrambling references ("Trevor Jackson, III")
Re: Data Scrambling references ("Trevor Jackson, III")
Re: Q: Removal of bias (Scott Nelson)
Re: Q: Removal of bias - reply (vic)
Re: Q: Removal of bias (Scott Nelson)
Re: Doesn't Bruce Schneier practice what he preaches? (K. Y. Lemonair)
Re: How protect HDisk against Customs when entering Great Britain (Shaitan)
Re: Incompatible algorithms (Max Polk)
----------------------------------------------------------------------------
From: That guy...from that show! <[EMAIL PROTECTED]>
Crossposted-To:
alt.security.pgp,comp.security.pgp.discuss,comp.security.pgp.tech,alt.privacy,alt.privacy.anon-server
Subject: Re: How protect HDisk against Customs when entering Great Britain
Date: 5 Nov 1999 00:54:34 -0000
Reply-To: [EMAIL PROTECTED]
On Thu, 04 Nov 1999 23:23:53 GMT , [EMAIL PROTECTED] (Ike R.
Malony) wrote
>pgp651 <[EMAIL PROTECTED]> wrote:
>
>Oops! I was going to make a suggestion, but this is cross-posted to too
>many groups.
You idiot, you posted to them anyway. Argh....AOLers
------------------------------
Date: Thu, 04 Nov 1999 20:18:03 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Data Scrambling references
Larry Mackey wrote:
> Hi,
>
> I have a project where we need to scramble (and unscramble) a parallel data
> stream such that when the data stream is serialized, the stream is a fairly
> symetrical set of ones and zeros.
Who do you need protection against? What is your "threat model" ?
> The data does not need to be compressed or encrypted rather we need to
> randomize the data on a bit level.
If you need to have the scrambled data pass statistical tests you can simply
use an RNG which pass the requisite tests and maks your data stream with the
stream from the RNG using exclusive-or, addition, or subtraction. This might
work if you are using a bit-phase sensitive recording method. But it provides
zero security.
If you need cryptographic security you'll need a cipher. A side effect of a
good cipher is that the output is statistically equivalent to noise so you get
balanced sets of bitstrings of all lengths including one.
> I am trying to find a scheme that encodes and decodes the data words in as
> uncomplicated manner as possible. This is presently a bi-directional path
> but we would like to be able to do this in a single direction only if
> possible. Since all the data in the stream needs to be randomized, the
> decoding procress information needs to be extracted from the data stream or
> decoding logic.
>
> Does anyone have any suggestions, pointers to references, thoughts or
> ideas??
> We have been doing a number of web searches and have not found any
> references that go into enough detail to understand the process enough to
> replicate it.
>
> It appears that high speed data links 100 Mbit/sec and above use this
> approach but we are unable to find a detailed description anywhere of the
> logic, or process. We don't have the $$ to buy all the various upper level
> reference documents called out to determine if they have the information we
> are looking for.
------------------------------
Date: Thu, 04 Nov 1999 20:20:40 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Data Scrambling references
Larry Mackey wrote:
> Thanks for reply
>
> Unfortunately, we have to do the "scrambling" while the data is in parallel
> format before the serializer. I agree that implementing LFSR at the serial
> stream would be the norm for this type of application but this application
> won't allow us to do that.
Sure it will. You can use an LFSR that is as wide as your data register and
update all of the bits in the register one every clock cycle. No shifts
required.
How wide is your data when it is in parallel format?
>
>
> Regards
> Larry
> John Savard <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > "Larry Mackey" <[EMAIL PROTECTED]> wrote, in part:
> >
> > >I have a project where we need to scramble (and unscramble) a parallel
> data
> > >stream such that when the data stream is serialized, the stream is a
> fairly
> > >symetrical set of ones and zeros.
> >
> > >The data does not need to be compressed or encrypted rather we need to
> > >randomize the data on a bit level.
> >
> > Well, modems do this by using a simple LFSR, and XORing the bit stream
> > with its output. This "scrambling", as it is called, prevents long
> > runs of 1s and 0s, it is hoped.
> >
> > More elaborate techniques are used when the ratio of ones and zeroes
> > must be more strictly controlled. Thus, data written to disk drives is
> > coded using one or more forms of GCR (group-coded recording), a
> > technique whose name was introduced by IBM when it came out with its
> > 6250bpi tape drives.
> >
> > Using a 4 of 8 code to represent 6 bits in 8 bits, for example, one
> > could keep the number of zeroes and ones exactly equal within every
> > eight bits.
> >
> > John Savard ( teneerf<- )
> > http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (Scott Nelson)
Subject: Re: Q: Removal of bias
Reply-To: [EMAIL PROTECTED]
Date: Fri, 05 Nov 1999 01:48:54 GMT
On Thu, 04 Nov 1999 20:52:20 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>Scott Nelson wrote:
>> Assuming a biased bit which is '1' .75 and '0' .25
>> (entropy = 0.8112781)
>> Using XOR to combine N bits,
>> 1 bits: Entropy = 0.8112781
>> 2 bits: Entropy = 0.9544340
>> 3 bits: Entropy = 0.9886994
>> 4 bits: Entropy = 0.9971804
>> (after 12 bits, it's 1.0 to seven places.)
>
>Is is possible to do an analogous computation for the von Neumann's
>device? Thanks.
>
Well, yes and no.
Von Neumann's method doesn't produce a deterministic number of
bits from a stream of biased bits.
Thus it's not quite the same - however, assuming independent
but biased bits which are '1' .75 and '0' .25 _on average_
Von Neumann's method will produce .1875 bit of entropy per
biased-bit processed. These just add up;
1 biased bits: average entropy = 0.1875
2 biased bits: average entropy = 0.375
3 biased bits: average entropy = 0.5625
4 biased bits: average entropy = 0.75
In another thread, Tony T. Warnock pointed out that Von
Neumann's method can be expanded. Using that method,
groups of 4 biased bits will produce _on average_
1.289 bits of entropy. Taken in groups of 20, you can get
slightly more than 12 bits of entropy (about .6 unbiased
bits per biased bit.)
Scott Nelson <[EMAIL PROTECTED]>
------------------------------
From: vic <[EMAIL PROTECTED]>
Subject: Re: Q: Removal of bias - reply
Date: Fri, 05 Nov 1999 02:03:27 GMT
!!In article <[EMAIL PROTECTED]>,
!! Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
!!1> Could anyone give references to practical results of removal of
!!> bias in random number/bit sequences, showing the efficiency of
!!> the techniques? Thanks in advance.
!!> M. K. Shen
===================================================================
Your question is rather broad - read the following and let me know if
this tells you what you want to know :
Subject: Re: What the hell did Santha-Vazirani paper actually say?
Summary: algorithm doesn't work, this one does
From: [EMAIL PROTECTED] (david lewis @ EECG, University of Toronto)
I have no significant crypto experience, but I believe that
the enclosed is correct.
The solution I ultimately devised is completely general and efficient.
It takes a source of bits with some randomness which can be modelled
by pone(prevbits), giving the probability of seeing a one as the next
bit given any number of previous bits. The pone function can be
arbitrarily complicated; as long as it exactly models the non-
randomness in the input, the output will be completely random. In
practice, a table listing pone(prevbits) for some finite number of
previous bits is sufficient.
An explanation of the algorithm follows.
Suppose we have a real number x, x member [0,1),
and the probability distribution of x is completely uniform. Then
it is trivial to generate any number of random bits by inspecting the
binary representation of x.
The next step is to realise that a sequence of nearly random bits can
be used to generate some extra bits. Given some nearly
random sequence of bits r[i], i = 1..n, with probabilty of a one pone
[i],define z[0] = x, and
z[i] = (1 - pone [i]) + z[i-1] * pone [i] if r[i] is 1
z[i] = z[i-1] * (1 - pone [i]) if r[i] is 0
As long as x is random, and pone[i] exactly models the probabilty
of a one in r[i], then z[i] is randomly distributed in [0,1).
The problem, of course, is that we don't have a perfectly random number
x to start with. So lets represent the unknown x by the interval [0,1),
and perform the same calculation. Then each z[i] is an interval [zmin
[i],zmax[i]), and the same calculations apply. After consuming some
number of bits, then the interval [zmin[i],zmax[i]) will become small.
We can produce some random bits by simply reading out those bits of
zmin and zmax that agree.
For example, we might find
zmin[i]=.101110110110101011....
and
zmin[i]=.101110110111011101....
^^^^^^^^^^^
where the underlined bits agree
This means that z[i] is somewhere in this interval. It is thus
safe to produce 10111011011 as completely random bits even though
we don't know what x is!
The following program uses this algorithm to generate random bits.
It rescales each zmin,zmax (called rmin, rmax in the code)
to the interval [0,1) as it generates each bit.
The program uses a more limited model of pone that is dependent
on k previous bits.
.....
[snipped}
David Lewis
=============================
I don't have any practical experience, I only deal with theory aspects.
I think that Lewis' work is generalized by M. Blum:
"Independent unbiased coin flips from a correlated biased source: a
finite state Markov chain", combinatorica, 6 (1986), pp. 97-108.
In this work, a source is modelled as a finite state Markov chain (with
unknown transition probabilities). In this mode it is possible to
describe the dependency of the next bit (output by the source), on the
previous c bits (for any constant c).
Santha and Vazirani have further relaxed the restrictions on the
physical source: an output bit may depend on all the preceding bits.
A even weaker model of randomness was suggested by Benny Chor and Oded
Goldreich, and they show for it the same results SV had for their model.
For a good survey, you can look at the introduction to Chor and
Goldreich's paper: "Unbiased bits from sources of weak randomness and
probabilistic communication complexity", SIAM J. COMPUT., Vol. 17, No.
2, April 1988.
======================================
In short, the ideas expressed above say that that the proposed
algorithm is optimal in the sense that it can distil maximum entropy
from a random source whose distribution is known. The method is
strangely reminiscent of arithmetic coding, which is also optimal in a
certain sense.
Vic Drastik
Decode my email address with the following key :
1=v,2=i,3=c,4=d,5=r,6=a,7=s,8=t,2=i,9=k
[EMAIL PROTECTED]
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Scott Nelson)
Subject: Re: Q: Removal of bias
Reply-To: [EMAIL PROTECTED]
Date: Fri, 05 Nov 1999 02:18:14 GMT
On Wed, 03 Nov 1999 22:47:09 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>Scott Nelson wrote:
>>
>> On Wed, 03 Nov 1999 08:40:52 +0100, Mok-Kong Shen
>> <[EMAIL PROTECTED]> wrote:
>>
>> >Could anyone give references to practical results of removal of
>> >bias in random number/bit sequences, showing the efficiency of
>> >the techniques? Thanks in advance.
>> >
>>
>> Well, assuming independence and for simple techniques
>> like XOR or CRC, it's just straight math;
>.............
>>
>> Assuming a biased bit which is '1' .75 and '0' .25
>............
>> Is this the sort of thing you were looking for?
>
>I like to know a little bit more than that: How is the practice
>in comparison to theory? Further, can we somehow check the assumption
>of independence (IMHO this could be quite hard) made above?
>
Most tests I know of are negative rather than positive. That is,
failing the test proves (or strongly suggests) dependance, but
passing doesn't prove independence. A simple example:
Take 1,000 single bit samples. Assume you get 250 one-bits
and 750 zero bits. This is the .75/.25 1/0 case I've been using.
Now check the samples in pairs. If they are independent,
then we'd should see approximately 563 '11' pairs, 63 '00' pairs,
187 '10' pairs and 187 '01' pairs. But suppose instead we see
700 '11' pairs, 15 '10' pairs, 35 '01' pairs, and 250 '00' pairs.
Then we strongly suspect the bits are not independent. For this
example, the probabilities seem to be;
.81 of a '0' and .19 of a '1' if the previous bit was a '0'
.14 of a '0' and .96 of a '1' if the previous bit was a '1'
Using those numbers, Von Nuemann's method, instead of producing
a perfectly unbiased bit, now produces a '1' 62% of the time,
and a '0' 38%. (It also takes longer than we might otherwise
expect to get that bit.) This looks bad, but at least it's an
improvement over the original, biased-bit.
When xoring 2 biased, dependant bits, the prob of '1' = .95,
prob of '0' = .05 XOR actually makes things worse!
The 4 bit CRC on the other hand shows a steady improvement in the
quality, albeit less than we get with independence.
After 1 bits: Entropy = 0.8112781 (Entropy per crc bit = 0.2028195)
After 2 bits: Entropy = 1.6225562 (Entropy per crc bit = 0.4056391)
After 3 bits: Entropy = 2.4338344 (Entropy per crc bit = 0.6084586)
After 4 bits: Entropy = 3.2451125 (Entropy per crc bit = 0.8112781)
After 5 bits: Entropy = 3.5027971 (Entropy per crc bit = 0.8756993)
After 6 bits: Entropy = 3.7965876 (Entropy per crc bit = 0.9491469)
After 7 bits: Entropy = 3.8681690 (Entropy per crc bit = 0.9670422)
After 8 bits: Entropy = 3.9210099 (Entropy per crc bit = 0.9802525)
Larger CRCs work better, and secure hashes should work even
better, since they are both larger and more evenly distributed.
Unfortunately, they are also much harder to analyze, so I don't
plan on calculating the entropy for them any time soon.
One of the main advantages of hashing, is that we don't have
know much about the input data. If it has some entropy in it
somewhere, the hash will distill it out.
Scott Nelson <[EMAIL PROTECTED]>
------------------------------
From: [EMAIL PROTECTED] (K. Y. Lemonair)
Crossposted-To: alt.security.scramdisk
Subject: Re: Doesn't Bruce Schneier practice what he preaches?
Date: Fri, 05 Nov 1999 02:14:53 GMT
John Kennedy <[EMAIL PROTECTED]> wrote:
>Ya, and their AES candidate is even fishier.
As David Scott just wrote in another thread:
>... do you ever read or think about the carp you post.
--
"K. Y. Lemonair" better known as [EMAIL PROTECTED]
0 1 23456789 <- Use this key to decode my email address.
Fun & Free - http://www.5X5poker.com/
------------------------------
Date: 5 Nov 1999 02:40:33 -0000
From: [EMAIL PROTECTED] (Shaitan)
Subject: Re: How protect HDisk against Customs when entering Great Britain
Crossposted-To:
alt.security.pgp,comp.security.pgp.discuss,comp.security.pgp.tech,alt.privacy,alt.privacy.anon-server
On 4 Nov 1999 22:06:21 -0000 pgp651 <[EMAIL PROTECTED]> wrote:
>-----BEGIN PGP SIGNED MESSAGE-----
>
>I'm considering to be crossing border of Great Britain [ GB ] very soon on
>business & pleasure trip.
>My friend did tell me that GB is scanning in / out coming computers for some
>specific data / images / information. I'm privacy advocate & can not allow this
>invasion of privacy to occur to me & my possessions.
>I'm using PGP day in / day out but excluding PGPdisk. I'm protecting my files
>by PGP on folders or / and individual files routinely.
>
>I need now to implement more advance disk protection to protect myself when
>entering GB.
>- From my knowledge, we have 2 comparable products : PGPdisk & Scramdisk. Please
>provide advise which I should implement to achieve the best hide & camouflage
>results.
>
>The points of interest are:
>- - I do not like to create precedence at the border.
>- - Very possible, when Customs can not scan / read info, they may opt for
>detention / seizure & this will ruin my trip.
>- - The best will be to camouflage the encrypted disk / partition / folders and
>not to have encrypted disk / partition / folders readily visible / recognize by
>Customs Scan as ENCRYPTED.
>- - I need the appropriate balance between encrypt & camouflage.
>- - Where the camouflage should play more important role than encryption.
>- - I'm encrypting now my files but I'm not implementing camouflage technique.
>- - Should be applicable to HD, CD-rom, CD-RW, CD-R [ Iomega ZIP when possible ]
>
>With the above preferences what I should implement to protect my privacy ?
>Any other techniques should I use ?
Unlike Mr. Maloney, I don't feel obligated to discipline you for
cross-posting.
Unlike Mr. Maloney, I have a useful suggestion to offer.
Scramdisk offers steganography, which permits you to use 1/4 to 1/2 of
a .wav file to store encrypted data. The .wav file will play with a
suitable player. It's probably not foolproof, but should pass cursory
scrutiny.
If you're really paranoid, keep the scramdisk program itself somewhere
else.
You could always download another copy when you arrive at your
destination.
And don't forget to securely erase free space and your swap file before
you expect to be scanned.
------------------------------
From: Max Polk <[EMAIL PROTECTED]>
Subject: Re: Incompatible algorithms
Date: Thu, 4 Nov 1999 21:50:34 -0500
I had said:
> > Has any research been done on the existence of "incompatible"
> > algorithms, especially in the context of producing arbitrarily
> > secure ciphertext?
In article <7vob2g$2lv$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
> Refer to the MARS AES submission, and do not reply until you know why I
> said that.
I just downloaded and read the detailed description of MARS from:
http://www.research.ibm.com/security/mars.html
I suppose the topic of focus is a "type-3 Feistel network". The non-
copyrighted document stated:
"A type-3 Feistel network consists of many rounds, where in each round
one data word (and a few key words) are used to modify all the other data
words. Compared with a type-1 Feistel network (where in each round one
data word is used to modify one other data word), this construct provides
much better diffusion properties with only a slightly added cost. Hence,
fewer rounds can be used to achieve the same strength."
Some test data showed using the output of one "round" as the input to the
next. By repeating the same sub-algorithm 40 or 100 or more times, the
bits of data spread well.
There were several sub-algorithms used to make up the MARS algorithm.
Steps were taken at the beginning and end differently than in the middle.
Lots of bit-shifting, addition, multiplication, table lookup and other
techniques were used. It was stated MARS could replace DES for many
years to come.
And I suppose that by using different kinds of sub-algorithms in
different combinations using bits from various places, it produced enough
confusion of data so as to make cryptanalysis difficult.
Still, I would like to see if anyone has researched mathematically
"incompatible" algorithms that by simply applying in sequence, you can
make plaintext arbitrarily security.
------------------------------
** 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
******************************
