Cryptography-Digest Digest #163, Volume #14 Mon, 16 Apr 01 21:13:01 EDT
Contents:
Re: MS OSs "swap" file: total breach of computer security. (David Schwartz)
Re: NSA is funding stegano detection (Walter Roberson)
Re: Long repeat (Steve Portly)
Re: Note on combining PRNGs with the method of Wichmann and Hill (Mok-Kong Shen)
Re: Reusing A One Time Pad ("Joseph Ashwood")
Re: LFSR Security ("Trevor L. Jackson, III")
"I do not feel secure using your program any more." (Anthony Stephen Szopa)
Re: "I do not feel secure using your program any more." ("Tom St Denis")
Re: combiner? ("Joseph Ashwood")
Re: LFSR Security (Gregory G Rose)
----------------------------------------------------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto,alt.hacker
Subject: Re: MS OSs "swap" file: total breach of computer security.
Date: Mon, 16 Apr 2001 17:05:06 -0700
Anthony Stephen Szopa wrote:
>
> MS OSs "swap" file: total breach of computer security.
>
> Unbelievable.
>
> For me, the "swap" file implementation in MS OSs is proof positive
> that MS is in a conspiracy to control OUR information (and all of
> US by implication) and is most probably cooperating with the
> government in this regard. MS is intentionally placing our right
> to privacy at risk.
It might be remotely possible that you were interested in an honest
discussion of swap file implementations and security risks, but your
wording suggests otherwise. I will note that you provide absolutely no
information *about* MS's implementation and no comparison to other
implementations, you just bash,
DS
------------------------------
From: [EMAIL PROTECTED] (Walter Roberson)
Crossposted-To: comp.security.misc,talk.politics.crypto
Subject: Re: NSA is funding stegano detection
Date: 17 Apr 2001 00:11:35 GMT
In article <[EMAIL PROTECTED]>,
<[EMAIL PROTECTED]> wrote:
:Compression by definition involves *retention* of information
:(notwithsanding that JPEG is 'lossy'). That is the data is decidedly
:not random, but is contained in minimal size using an efficient
:structure to organise the requisite information. So while compression
:may reduce the obvious patterns in the values of the data (such as the
:high frequency of the letter e in English text), it does so by
:imposing a non-random structure. So compression alone does not
:eliminate discoverable information
You are confusing the source information with its compressed
representation. The compressed representation does not necessarily
have any discernable structure, and any apparent structure might
be coincidental.
Modern compression has several independant steps. There is
a predictive model which supplies a probability for each successive
symbol, and there is an encoding procedure which turns the probabilities
into a bitstream. The predictive model can be context-sensitive to any
desired extent, and can be static or adaptive -- and there is a choice
of initial assignments for parameters of the model. The relative
ordering of the symbols is another parameter. Usually the relative ordering
is fixed, but that is seldom important to encoding phase -- the
sequence of orderings is another parameter that could be supplied
[and thus becomes yet another "key" to the decodings.]
The algorithm that is usually used these days for turning the
probability stream into a bitstream, is "arithmetic encoding".
It has been proven theoretically that arithmetic encoding will
produce the shortest probability-weighted bitsteam for a given set of
discrete probabilities (excluding possibly the effects of the
end-of-stream symbol that requires flushing the buffers -- that symbol
doesn't have a well-defined probability, and there are several ways
of dealing with it.) Structure in the encoded output is either
accidental or the effect of using a probability model which disagrees
with the source data.
The output of usual arithemtic encoding has uniform random
distribution. It would be trivial to add a mapping step into any
"memoryless" distribution over the closed interval [0,1]; it would be a
little more work but theoretically easy (I think) to use stocastic
distributions over [0,1] instead. A large enough stocastic chain could
be used to impose any desired external markers -- headers, trailers,
record format, and so on.
Compression algorithms have many different parameters whose values
could be secret; to the extent that the secrecy of these values
can be preserved and that known-text analysis is blocked, compression
can act as a form of cryptographic encoding.
"General" encryption programs such as gzip *do* present a partly-
structured output, with the initial values of the datastream being
used to compactly share the encoding parameters. gzip is not designed
with cryptography in mind: it is designed as generalized compression
program that does well on many "common" files, and is designed for public
decoding. This does not change the fact that compression algorithms
can be used to encrypt when the choice of parameters is kept secret.
[Of course, to someone looking at it from the compression point
of view, the question that would be asked would be about the size
of the data needed to represent the compression parameters: they would
add the size of the parameter representation to the size of the compressed
data in order to determine the effectiveness of the algorithm from a
compression point of view. An algorithm that involved permutation
of the symbol ordering to effect encryption, would be called
inefficient from a compression viewpoint because of the extra data
needed to represent the permutation sequence to the decompression
program.]
------------------------------
From: Steve Portly <[EMAIL PROTECTED]>
Subject: Re: Long repeat
Date: Mon, 16 Apr 2001 20:20:13 -0400
Tom St Denis wrote:
> "Jacques Thériault" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > I am presently testing a PRNG to see how much I can generate without it
> > looping.
> >
> > I can do about 2^40 characters in 20 days.
> >
> > My dilem is this. Should I let continue to get maybe to 2^44 in a year
> > or should I try another seed to maybe find a weak key?
> >
>
> Why not just analyze the design to try and find a weakness?
>
> Tom
The FIPS 140 test requires less than 100,000 bits to qualify a PRNG.
If a function does not have looping output in 2^30 you are probably safe,
although as Tom pointed out you might run into some machine limitations such
as big number truncations if your PRNG uses big numbers for example.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: Note on combining PRNGs with the method of Wichmann and Hill
Date: Tue, 17 Apr 2001 02:19:59 +0200
Brian Gladman wrote:
>
> "Mok-Kong Shen" <[EMAIL PROTECTED]> wrote:
> >
> > Brian Gladman wrote:
> > >
> > > "Mok-Kong Shen" <[EMAIL PROTECTED]> wrote:
> > > >
> > > >
> > > > Brian Gladman wrote:
> > > > >
> > > >
> > > > > If two different PRNGs giving unfiformly distributed random numbers
> in
> > > > > [0.0:1.0) are added and the result is taken 'mod 1.0', this output
> will
> > > then
> > > > > be uniformly distributed in [0.0:1.0). A bit of maths shows that
> the
> > > output
> > > > > in [0.0-2.0) is not uniform but that the mod function combines the
> > > ranges
> > > > > [0.0:1.0) and [1.0:2.0) in such a way that a uniform distribution
> > > results.
> > > > >
> > > > > But if the outputs of the generators are multiplied by constants
> close
> > > to
> > > > > 1.0 before combination, the output will not generally be uniformly
> > > > > distributed in [0.0:1.0).
> > > > >
> > > > > This can be seen by considering a single PRNG giving uniformly
> > > distributed
> > > > > random numbers in [0.0:1.0) and considering the output after
> multiplying
> > > by
> > > > > a number (1.0 + delta), close to 1.0, and taking the output 'mod
> 1.0'.
> > > In
> > > > > this case numbers in the range [0.0:delta) will occur twice as often
> as
> > > > > those in the range [delta:1.0).
> > > > >
> > > > > Although the maths is more complicated when several generators are
> > > > > combined, the same issue turns up.
> > > > >
> > > > > The uneven distributions that result may not be a problem in some
> > > > > applications but they will frequently be undesirable.
> > > >
> > > > One can consider the continuous case as the limiting
> > > > case of the discrete case. In the discrete case, i.e.
> > > > for integer range [0, n-1], it can be easily proved that
> > > > the sum of a uniform random variable and an arbitrary
> > > > random variable (more exactly one that is not degenerate
> > > > in that it has non-zero frequency for at least one value
> > > > relatively prime to n) mod n is a uniform variable.
> > >
> > > Unless I misunderstood your intentions, your original post suggested -
> by
> > > using the terminology '1.0 + delta' - that the multipliers involved were
> > > intended to be close to 1.0. It also seemed that your starting PRNGs
> had
> > > outputs in the range [0.0:1.0). But maybe this was not your intention.
> > >
> > > In any event, this was this case I was referring to, not one where the
> > > multipiers are large.
> > >
> > > If several PRNGs with uniformly distributed outputs in the range
> [0.0:1.0)
> > > are combined by adding 'mod 1.0' after multiplying each of them by
> factors
> > > close to 1.0, then the resulting distributions will be very non-uniform.
> >
> > I suppose I don't yet understand you. Do you mean that
> > the case where the multipliers are close to 1.0 produces
> > a worse result than the case where they differ more?
>
> Yes, this is my guess, by considering the limiting case of a single
> generator multiplied by a number close to 1.0 with the output then taken
> 'mod 1.0'.
>
> If the multiplier is less than one there will be numbers close to 1.0 that
> cannot be output. And if the multiplier is greater than 1.0, numbers above
> 1.0 will add to the numbers close to zero when the 'mod 1.0' is taken so
> numbers in this range will be twice as probable as higher numbers.
>
> My gut feeling is that when multiple generators are used with multipliers
> close to 1.0 the uneven distribution will be more complex but it will still
> be there unless the mutlipliers used are chosen very carefully to restore
> uniformity (I am not sure what the conditions on the multipliers would be to
> achieve this - e.g. if the multiplers on two combined generators add up to
> 2.0 is the result then uniform?)
First I want to correct what I wrote previously: In what
is quoted at the top, the phrase in the parentheses
'(more exactly .....)' should be deleted, because for
the present issue this restriction is not necessary.
Please note, as I wrote in another previous post, that
for 'exact' argumentation one of the multipliers has
to be 1.0.
Now, you said you were employing your gut feeling. Let
me appeal to your gut feeling to consider the following:
Let r1 and r2 be two uniform random variable in [0, 1).
Consider r3 = 1.0*r1 + 1.0*r2 mod 1. I suppose you
don't have difficulty in accepting that r3 is uniform.
Now consider r4 = 1.0*r1 + 0.999999*r2 mod 1. According
to what you wrote previously, r4 would be very
non-uniform. Do you still have that feeling? How about
replacing 0.999999 with one that increases and become
infinitely close to 1.0, though not exactly equal to it
(we ignore the fact that one can't do that on computer)?
Do you think that there is sort of a 'jump' phenomenon?
If still yes, you could do an experimental check if you
have a numerical library like NAG available, which has
a good standard uniform pseudo-random number generator.
You can use two different seeds for getting r1 and r2.
(They are, exactly speaking, not independent, but that
shouldn't matter too much here.) You can then do a
chi-square test to see whether you get the very (large)
non-uniformity you conjectured. Otherwise, you have
to do some math to see if you can prove your claim.
(I am quite sure that you can't, for the reason I
wrote previously.)
M. K. Shen
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Reusing A One Time Pad
Date: Mon, 16 Apr 2001 17:14:58 -0700
Sorry can't give you something formed like
> time to break (pad size, chunk size, # of times message block is
encoded)
> = ?
However I can tell you that you can do something akin to this. Simply keep a
pointer to the next unused bit in the large pad. It becomes a OTP as
commonly envisioned. If you do not do this and instead choose a random
location in the large randblock at random you will very quickly reduce your
security to 0. In particular once you reach sqrt(length randblock) bits
encrypted there is already a 50% likelihood that an attacker can read at
least one bit.
Joe
"Mark G Wolf" <[EMAIL PROTECTED]> wrote in message
news:9bcpb4$290q$1@newssvr06-
------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: LFSR Security
Date: Tue, 17 Apr 2001 00:27:53 GMT
David Wagner wrote:
> Trevor L. Jackson, III wrote:
> >David Wagner wrote:
> >> That's exponential-time.
> >
> >In pathological cases yes.
>
> Proof, please.
If I had a mathematical proof you would already have seen it.
Preliminary to finding a proof of good performance is finding a proof of
correct output. Since I've not accomplished the latter, asking for the
former is fruitless.
> How do you know it's not exponential-time on average?
I don't.
>
> Without a proof (and considering how many plausible-sounding claims
> about this approach turned out to be false -- thanks, Ian!), I hope
> you'll forgive me if I'm skeptical.
Forgiven. If I manage to find a better than exponential solution I'll
deliver a formal ", but not forgotten". ;-)
------------------------------
From: Anthony Stephen Szopa <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.misc,alt.hacker
Subject: "I do not feel secure using your program any more."
Date: Mon, 16 Apr 2001 17:35:05 -0700
"I do not feel secure using your program any more."
You sure jumped to a hasty conclusion.
I certainly appreciate your effort in arriving at this noteworthy
observation.
But if you think about it this approach to generating random digits
is essentially a finite step function on a row to row basis. Thus
for a set of 3 permutations you give me I can give you another that
will produce the same random digit output. But it is finite. This
is obvious from direct observation.
Have you thought about this: You could have guessed forever if you
did not already know the random digit sequence.
So you are somewhat correct in that there are many other possible
permutations sequences that will generate the same output. But
there are practicably an infinite number of others that won't.
But let us not stop there.
As you are aware, the random digit sequences are not the OPTs. The
random digit sequences are only the starting point for generating the
OTPs.
For instance, one could suggest: "Why even generate these random
digit sequences using the OAP-L3 methods. I will just generate a
file containing nothing but the digit sequence 0123456789 repeated
until I have created a file of 18,144,000 bytes in length then I
will use the other methods from OAP-L3 to scramble these up to create
a random digit sequence."
You surely know that it won't take very many of these processes to
scramble up THIS file before the odds of guessing the final sequence
becomes practicably impossible to guess or analyze because there will
simply not be enough computing power available or time or energy to
accomplish this.
Again, using the methods of OAP-L3 to generate your random digit
sequences is just the first step of creating your OTPs. And since I
believe you would agree that even if you started with a known file
containing the sequences of 0123456789 of length 18,144,000 bytes
and this becoming very quickly practicably impossible to guess
using the methods from OAP-L3, then by actually generating the random
digit files using OAP-L3 makes this impossibility that much more
impossible.
This is because if you have gone to ciphile.com and looked up the
Sterling Approximation web page you would know that there are about
1E66,000,000 possible sequences to arrange three permutation files.
Of course there may be trillions and trillions of useable sequences.
How lucky are you at guessing one in 1E24 or 1E48 or 1E96, etc.
sequences from 1E66,000,000. Not even incredible Chinese gamblers
think they are this lucky.
Now you may feel that the problem is greatly simplified (as if
anything could simplify a problem with 1E66,000,000 possible
outcomes) if you just had some plaintext and encrypted text. How
so?
The random number sequence you determine from having these two data
sources has so little relationship with the random digit file(s)
generated from using the OAP-L3 methods as to be worthless for
attacking subsequent numbers from the OTPs because this original
random digit file has been further processed using all the methods
available with OAP-L3, where above I hope you agreed, even
if you knew this file and its sequences, it would make no
difference.
OAP-L3 is not meant to provide security for the random digit files
its methods can generate. OAP-L3 looks through this sequence of
steps to arrive at the security level obtained from using its methods
in the creation of the OTP files.
Practicably, the process leading to the final OTP files is a one way
process.
Look back from the vantage point of the OTP files, all the way back
back to the three files of permutations sequences and consider
recreating these from just some cyphertext and corresponding
plaintext.
Still a little shaky, then simply assume that someone knows (which
they cannot possibly know from figuring it out as I just pointed
out but let's just assume) that the cracker actually knows the random
digits you have generated from the methods from OAP-L3.
Continuing to process this file(s) as I am sure you realize will soon
make it impossible for this cracker to gain any headway. The
computations may be simple but their probabilities soon become
unmanageable.
14! = about 87,000,000,000. So a cracker guessing will have to guess
this many possible outcomes for just this one process assuming the
cracker even knows this was the process run. Set's assume the
cracker does.
Just running this process 10 times makes the possible outcomes
(87E9)^10 = 87E90. How can a hacker increasingly keep track of all
this? This is why OAP-L3 is so powerful. It allows the user to
effectively determine the security level by how many processes run.
Here is a real problem for the cracker. Let's say a cracker does
guess a short length of the random number sequence or OTP used to
encrypt a message or messages. Is this any different than guessing
the sequence of any other encryption software or any other encryption
method? Your premise is "by guessing." If a guess is made and is
good then does this necessarily imply subsequent guesses are correct
as well.
You suggest that if a cracker guesses the three permutation sequences
that they will be able to break the encryption. How? Or more
specifically how will the cracker even know that the original or
useable three permutation sequences are valid?
The cracker has nothing to verify this with. ABSOLUTELY NOTHING.
The nature of OAP-L3 and many other encryption schemes is that even
if you guess and obtain a readable plaintext message you need to ask
yourself if this is the correct plaintext message.
You can essentially see this entire argument by reading the Help Files
at ciphile.com.
Thanks for allowing me to refresh my memory.
I hope this helps in your considered deliberations.
AS
PS I assume you were using OAP-L3 according to instructions and
recommendations.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.misc,alt.hacker
Subject: Re: "I do not feel secure using your program any more."
Date: Tue, 17 Apr 2001 00:47:38 GMT
"Anthony Stephen Szopa" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "I do not feel secure using your program any more."
>
> You sure jumped to a hasty conclusion.
Who posed the quotation text? (BTW I may be in his killfile, so for fun
could someone please just repost this message in it's completeness....)
> For instance, one could suggest: "Why even generate these random
> digit sequences using the OAP-L3 methods. I will just generate a
> file containing nothing but the digit sequence 0123456789 repeated
> until I have created a file of 18,144,000 bytes in length then I
> will use the other methods from OAP-L3 to scramble these up to create
> a random digit sequence."
Why not juse use 0 and 1? for a binary system... I surely don't make files
that are base10 in size...
> You surely know that it won't take very many of these processes to
> scramble up THIS file before the odds of guessing the final sequence
> becomes practicably impossible to guess or analyze because there will
> simply not be enough computing power available or time or energy to
> accomplish this.
Perhaps. Where does the source of entropy come from? What "mixing" process
is used? Not all mixing algorithms are equal. If only use 14 bits of
entropy and a trivially stupid algorithm to shuffle the array it should be
simple to figure out what the state is.
> Again, using the methods of OAP-L3 to generate your random digit
> sequences is just the first step of creating your OTPs. And since I
> believe you would agree that even if you started with a known file
> containing the sequences of 0123456789 of length 18,144,000 bytes
> and this becoming very quickly practicably impossible to guess
> using the methods from OAP-L3, then by actually generating the random
> digit files using OAP-L3 makes this impossibility that much more
> impossible.
Unless the # of bits into OAP is the same as the # of bits out OAP can never
be a OTP (assuming OAP doesn't degrade the entropy). It's as simple as
that.
Again you assume that you shuffled your array with some good source of
entropy at hand...
> This is because if you have gone to ciphile.com and looked up the
> Sterling Approximation web page you would know that there are about
> 1E66,000,000 possible sequences to arrange three permutation files.
> Of course there may be trillions and trillions of useable sequences.
> How lucky are you at guessing one in 1E24 or 1E48 or 1E96, etc.
> sequences from 1E66,000,000. Not even incredible Chinese gamblers
> think they are this lucky.
So what. Lucifer had a 128-bit key... that's
340,282,366,920,938,463,463,374,607,431,768,211,456.... what a big number!
Does that mean it's secure... er NOPE!
> Now you may feel that the problem is greatly simplified (as if
> anything could simplify a problem with 1E66,000,000 possible
> outcomes) if you just had some plaintext and encrypted text. How
> so?
>
> The random number sequence you determine from having these two data
> sources has so little relationship with the random digit file(s)
> generated from using the OAP-L3 methods as to be worthless for
> attacking subsequent numbers from the OTPs because this original
> random digit file has been further processed using all the methods
> available with OAP-L3, where above I hope you agreed, even
> if you knew this file and its sequences, it would make no
> difference.
You assume your OAP methods are sound and non-degenerate. You have yet to
prove this.
<snip rest of your msg>
Why not show us how good your OAP methods are? You never discuss
efficiency, design or security in a sound method. Giving ad hoc
descriptions and poor excuses for "security" are not ideal. You can't claim
a big key size as a means to a secure block cipher...
Tom
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: combiner?
Date: Mon, 16 Apr 2001 17:51:57 -0700
Let's begin a bit earlier in this line of thought. What do you consider a
combiner? A very strong argument could be made for any invertable function
that takes at least 2 variables is a combiner.
I will assume two different types of assumptions (the stream cipher and the
block cipher assumption).
Given the stream cipher assumption, in particular that the combiner used is
not inherently strong, however it has certain behavior that is vital. In
general simply to maintain ease we state these as being fully bijective and
the block size being fixed (an input is the same size as the output). We
also tend to restrict ourselves to XOR, Addition, and block ciphers. Of
these XOR is by far the most common, and block ciphers the least common.
Under this assumption the combiner does not in fact need any resistance to
much of anything.
Given the block cipher assumption, that a repeated value is used to encrypt.
The assumption requires that the combiner be immune to all cryptanalysis to
maintain security. The generally used example are Linear and Differential
Cryptanalysis. A very quick very sloppy overview of these is:
Linear Cryptanalysis:
Create a linear approximation of your encryption function.
Count the length, that's approximately the resistance. The more you optimize
the equation the more accurate your estimate
Find the probability of your linear function holding to the cipher, compute
a few things.
Differential Cryptanalysis:
find behavior that happens with a probability P
Common types of behavior are things like:
0000k00000000x0000000001->xxxxkkkkkkk000000011001xxxxxx
This would be a particularly bad differential behavior unless it had an
extremely low probability (1/2^40+)
the odds of that differential occuring and being passed along the structure
dictates the resistance to that differential attack.
The problem is that with both of these it depends on the skill of the
analyst to find the best attacks, determine where you can make a trade off
on probility and size, and through that gain knowledge of the strengths. Of
course simply having known, or even provable resistance to
linear/differential cryptanalysis says nothing about your cipher's actual
strength and you need a skilled analyst to find any other flaws. What I
suggest is that you use this knowledge to attack currently unbroken ciphers
(Rijndael is a great target, but likely to be very hard, so start with
already broken ones and work your way up), publish your results, and build a
very big name for yourself. Good luck, and feel free to contact me if you
need any help, I'm always interested in helping people gain knowledge.
Joe
"newbie" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
------------------------------
From: [EMAIL PROTECTED] (Gregory G Rose)
Crossposted-To: sci.crypt.random-numbers
Subject: Re: LFSR Security
Date: 16 Apr 2001 17:59:11 -0700
In article <bw3C6.8369$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
>Question: Does the BM algorithm apply when non consecutive outputs are
>known?
A regular decimation (say, every 3rd output) of an
LFSR is another LFSR. B-M will apply to that. If
the decimation doesn't divide the period of the
original LFSR, you can get it back entirely.
If you know the taps and where the bits came from,
then David's solution works anyway, the equations
just get more complicated. But basically, it's
entirely linear, so when you have any N equations
in N variables, (and they're independent,) you can
solve them.
Greg.
--
Greg Rose INTERNET: [EMAIL PROTECTED]
Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199
Level 3, 230 Victoria Road, http://people.qualcomm.com/ggr/
Gladesville NSW 2111 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
