Cryptography-Digest Digest #781, Volume #12 Tue, 26 Sep 00 19:13:00 EDT
Contents:
Re: On block encrpytion processing with intermediate permutations (Mok-Kong Shen)
Re: On block encrpytion processing with intermediate permutations (Mok-Kong Shen)
Re: On block encrpytion processing with intermediate permutations (Mok-Kong Shen)
PRNG improvment?? ([EMAIL PROTECTED])
Re: continuous functions and differential cryptanalysis (Doug Kuhlman)
Re: continuous functions and differential cryptanalysis (Doug Kuhlman)
Re: continuous functions and differential cryptanalysis (Tom St Denis)
Re: differnetials... (Tom St Denis)
Re: PRNG improvment?? ("Paul Pires")
Re: On block encrpytion processing with intermediate permutations (Mok-Kong Shen)
Re: What am I missing? (Scott Craver)
Re: Steganography and secret sorting ([EMAIL PROTECTED])
Re: PRNG improvment?? (Eric Lee Green)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On block encrpytion processing with intermediate permutations
Date: Tue, 26 Sep 2000 22:36:36 +0200
Tom St Denis wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > Let's first agree that we are arguing about what I call
> > the full version of my scheme. You compute the differences.
> > but do you know which differences correspond to which
> > word/block of the original plaintext? Note that, due to
> > the word (or groups of words) permutation, everything
> > has got mixed up in a way that the opponent can't find
> > out. Please kindly re-read my original post and forget
> > for the time being the last two paragraph and do a
> > sketch with pencil of how you would go about with your
> > differential analysis with, say, DES as block encryption
> > algorithm and a message of 20 blocks. I think that my
> > idea would then be clear to you. Note in particular that
> > you have no knowledge of the permutations that are being
> > done. There could be poor permutations. Let's assume
> > that 2 are poor but 14 are good.
>
> That's just it, you can't have 2 good perms and 14 bad ones. it's the
> composition of them all... so either the entire perm is balanced (each
> word combines into DES with equally once...) or they don't. Realize
> that in 16 rounds of this protocal you need 17 blocks to get equal
> mixing (I think)... otherwise the mixing cannot be balanced...
Suppose you have a reasonably good PRNG, please tell
me what is the chance of having 2 good perms and 14
bad ones in comparison to having 14 good perms and
2 bad ones?
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On block encrpytion processing with intermediate permutations
Date: Tue, 26 Sep 2000 22:39:57 +0200
Bryan Olson schrieb:
>
> Mok-Kong Shen wrote:
>
> > Suppose each half is a word (e.g. DES), the permutation
> > is rendering each one of them to go to a different
> > location that is unknown to the opponent. I don't yet
> > see how he can 'follow' the individual halves as they
> > get processed in the different cycles in order to be
> > able to exploit differentials etc.
>
> No need to follow the path. Just recognize that when
> all other input blocks are held constant, the input
> differential on block i always becomes the final output
> differential on block j.
Then you have at least a work factor equal to the
number of blocks of the message. And you have to
manage that all messages for your investigation
have the same length.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On block encrpytion processing with intermediate permutations
Date: Tue, 26 Sep 2000 22:46:40 +0200
Mok-Kong Shen wrote:
>
> Then you have at least a work factor equal to the
> number of blocks of the message. And you have to
> manage that all messages for your investigation
> have the same length.
I was not quite right. Even if the all input blocks
are constant, in case a block has, say, 4 words,
then permutation still has an effect. In that case
one would have to prescribe that all words are
the same in the input.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED]
Subject: PRNG improvment??
Date: Tue, 26 Sep 2000 20:50:40 GMT
I have a question to the group. Will the idea below work or is it
deeply flawed, and if so, where and how.
If I fill an array of 2560 elements with 10 consecutive instantces of
0..255, then I have a uniform distribution of keys that have such an
obvious pattern that they are usless for cryptography. However, if I
take a readily available pseudo random number generator and use the
PRNG to generate INDEX values in the range of 0-2559, then I could
'randomly' pick elements from my first array and populate a second
array, in order picked, with the values in the first array the PRNG
points to. This is a simple shuffling exercise.
Now if I seed the PRNG with true random numbers, license plates,
system clock, keyboard latency measurements, etc. and seed often, and
shuffle often, will I, after say 10,000 shuffles & 30,000 seeds, begin
to approach the level of patternless 'randomness' necessary for a
cryptographical secure One Time Pad? It's uniform. It's long. The
question is, will this method introduce enough randomness?
Where can I find statistical tests for randomness that I can employ to
test this idea?
Thanks,
David Sosna
------------------------------
From: Doug Kuhlman <[EMAIL PROTECTED]>
Subject: Re: continuous functions and differential cryptanalysis
Date: Tue, 26 Sep 2000 15:29:26 -0500
Dido Sevilla wrote:
>
>
> Has he properly defined a derivative in GF(2^n)? To define a
> derivative, we have to begin with a definition of a metric in GF(2^n),
> then work our way to a definition of a limit, then the definition of a
> derivative.
Not true.... In fact, it's routine in higher mathematics to define a
derivative by the power rule, product rule, and chain rule. We'll get
to the why in a bit....
> Let's say we do come up with a valid metric, coming up with
> a metric function d(x, y) for x and y in GF(2^n) that satisfies all the
> metric axioms (I suppose it would be possible).
Actually, it's impossible. That's not that hard to show. To get a
metric, you need a greater than zero criteria (positive). To be a
metric, any sum of positives must be positive. But we know that 2a=0
for any a in GF(2^n), so we're doomed.
<SNIP>
> But hey, a proper definition for a derivative in
> finite fields *may* exist that doesn't use the notions of metrics or
> limits, but if so, I haven't heard of it. Maybe there's even a whole
> field of math called discrete analysis built around it. I'm not a
> mathematics major, I wouldn't know...
>
There are many uses for "formal" derivatives which are defined over
finite fields. The most obvious is the check for repeated roots of a
polynomial. If GCD(f(x),f'(x))!=1, then f(x) has a repeated root. But
there are other uses, too.
Of course, none of this (I don't think) helps Tom with his desire to use
differentials to analyze symmetric ciphers. I can do the upper-level
math, but I've not studied differential cryptanalysis enough to
tell...sigh!
Doug
------------------------------
From: Doug Kuhlman <[EMAIL PROTECTED]>
Subject: Re: continuous functions and differential cryptanalysis
Date: Tue, 26 Sep 2000 15:38:24 -0500
Mok-Kong Shen wrote:
>
> Tom St Denis wrote:
> > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > > Mika R S Kojo wrote:
> > > >
> > > > Derivative is well-defined for any field, but its usually called
> > > > "formal derivative". It is even possible to talk about continuous
> > > > functions, but for for this you need p-adic numbers.
> > >
> > > Dumb question: Are p-adic numbers inside the theory of
> > > GF or else at least compatible with it? If yes, could
> > > you please provide references? Thanks.
> >
> > I can top that, what are p-adic numbers?
>
> I only know that p-adic numbers belong to the topic of
> algebraic number fields. Once I found in the library
> a book dealing quite a lot with that but the stuff was
> apparently too advanced for my knowledge level, so that
> I didn't attempt to look into it.
>
At the risk of putting my foot in my mouth (I didn't deal with p-adic
numbers much), I think they are the completion of the localization of
the integers around p. Now, what does that mean?
OK, I feel comfortable with localization. It basically means you can
divide by anything you like except p (and multiples of p), in this
case. In actuality, it's a fair bit more complicated, but I think we're
already far enough afield.
Then, to complete this, you basically allow infinite sequences in powers
of p. Again, this is a gross oversimplification.
So, a 3-adic number could look like...
(1 + 2*3 + 3*3^2 + 4*3^3 + 5*3^4 + ...)/7
This has a nice metric, in that you give powers of p ever-decreasing
size values and write things in a nice form....
If you want more details (and I can't imagine why you would), let me
know.
Doug
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: continuous functions and differential cryptanalysis
Date: Tue, 26 Sep 2000 21:04:57 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>
> Tom St Denis wrote:
> > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > > Mika R S Kojo wrote:
> > > >
> > > > Derivative is well-defined for any field, but its usually called
> > > > "formal derivative". It is even possible to talk about
continuous
> > > > functions, but for for this you need p-adic numbers.
> > >
> > > Dumb question: Are p-adic numbers inside the theory of
> > > GF or else at least compatible with it? If yes, could
> > > you please provide references? Thanks.
> >
> > I can top that, what are p-adic numbers?
>
> I only know that p-adic numbers belong to the topic of
> algebraic number fields. Once I found in the library
> a book dealing quite a lot with that but the stuff was
> apparently too advanced for my knowledge level, so that
> I didn't attempt to look into it.
>
> M. K. Shen
>
> P.S. How did it occur that your post was repeated 4 times?
My browser took 10 mins to acknowledge it...
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: differnetials...
Date: Tue, 26 Sep 2000 21:04:09 GMT
In article <[EMAIL PROTECTED]>,
Doug Kuhlman <[EMAIL PROTECTED]> wrote:
>
>
> Mike Rosing wrote:
> >
> > Tom St Denis wrote:
> > > Arrg... calculus is all new to me... please help!
> >
> > You're mixing finite fields and continuous analytic numbers.
> > As my kids would say "that does not include". The idea behind
> > calculus is that you can "infinitly" divide things down very
> > smoothly. The idea behind finite fields is that every element
> > is distinct. A better way to combine these is thru p-adic
> > numbers. I'd suggest you keep finite field ideas completely
> > separate from calculus ideas, at least for a few months :-)
> >
> > Follow the proof carefully for why d/dx ( 1/x) = 1/x^2. You
> > use limits. Can't do that with a finite field!!
> >
> Don't mean to nitpick, but if Tom's learning calculus, he should at
> least see the correct answer that...d/dx(1/x) = - 1/x^2.
I got that on paper I copied it wrong.. . but thanks for correcting it.
> Also, Tom, in GF(2^8), -1/x^2 *is* a bijection, if you make a little
> proviso that 0 goes to 0.... This follows from the fact that squaring
> is an isomorphism of a field of characteristic two (Frobenius).
but x^2 in GF(257) is not a bijection... so is it just in GF(2^8)?
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: PRNG improvment??
Date: Tue, 26 Sep 2000 14:15:21 -0700
<[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> I have a question to the group. Will the idea below work or is it
> deeply flawed, and if so, where and how.
1, Put Phone book in blender.
2, Push "Frappe"
3, Repeat step 2 30,000 times.
It's not deeply flawed but it isn't very elegant.
>
> If I fill an array of 2560 elements with 10 consecutive instantces of
> 0..255, then I have a uniform distribution of keys that have such an
> obvious pattern that they are usless for cryptography. However, if I
> take a readily available pseudo random number generator and use the
> PRNG to generate INDEX values in the range of 0-2559, then I could
> 'randomly' pick elements from my first array and populate a second
> array, in order picked, with the values in the first array the PRNG
> points to. This is a simple shuffling exercise.
>
> Now if I seed the PRNG with true random numbers, license plates,
> system clock, keyboard latency measurements, etc. and seed often, and
> shuffle often, will I, after say 10,000 shuffles & 30,000 seeds, begin
> to approach the level of patternless 'randomness' necessary for a
> cryptographical secure One Time Pad? It's uniform. It's long. The
> question is, will this method introduce enough randomness?
>
> Where can I find statistical tests for randomness that I can employ to
> test this idea?
Don't use 10 of anything. Use 8 or 16. Using a muptiple of 10 will
just introduce hardships in converting the PRNG output selector to
the array range.
Try the DiehardC test program. It is a cleaned up C version of George
Marsaglia's
Diehard tests (originally in FORTRAN). Executables and source code are both
availiable.
http://www.helsbreth.org/random/diehard.html
Suggestions, Check out the 12 or so PRNGs he supplies
in the Makewhat.exe program for comparison.
Check out George Marsaglias page. Some good papers to read there.
Maybe some one will post a link. If not, a search should pick it up.
Paul
>
> Thanks,
>
> David Sosna
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On block encrpytion processing with intermediate permutations
Date: Tue, 26 Sep 2000 23:56:41 +0200
Addendum:
At the risk of adding too much 'complexity' (hence code and
computing cost), I like to mention that in addition to the
random permutation of the words of the whole message, one
can do a rotation of each word, with the amount of rotation
being determined by the PRNG. Without the PRNG, one could
obtain the amount of rotation of a word e.g. from certain
bits of another word that is at a symmetrical position to
it with respect to the whole message.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Scott Craver)
Subject: Re: What am I missing?
Date: 26 Sep 2000 21:54:04 GMT
Lon Willett <[EMAIL PROTECTED]> wrote:
>
>Keeping in mind that I'm only talking theory, not practice, your
>examples are all flawed. If something is OK for your watermarking
>scheme to do, then it is OK for my magical super-AI compressor to
>remove the viewable/audible redundancy.
Ah. Very well: I'm kind of assuming my "perfect compressor"
is less intelligent than your perfect compressor.
>> >But reverse-engineering of the scheme need only be done _once_ by
>> >_one_person_, and the whole thing is dead.
>>
>> But this is true for anything. RSA need only be cracked
>> once by one person. That doesn't mean it will be done, or
>> should not be trusted.
>
>RSA doesn't need to be reverse-engineered. It is known. Its security
>rests on keeping secret a private key that is sufficiently difficult
>to crack.
Oh, more semantic confusion. I thought you meant cracking.
Secret-key-based watermarking schemes are not dead if
the algorithm is made public. Only schemes in which all
embedders and detectors use the same key.
I understand that SDMI marks will not be secret-key based,
but sometimes I see people claim that all watermarking, or
in fact all steganography, commits this violation of Kerckhoff's
criterion.
But there's more: people are presently trying to attack the
problem of public-key watermarking, meaning watermarks for
which a public detector can exist, but for which one can still
not remove it. I've personally proposed 3 methods for this,
two of which now look attackable in general. The third one has
problems with practicality.
> (i) is_marked(mark(D)) is true.
> (ii) is_marked(D) has a _very_ low probability of being true.
> (iii) It is cryptographically hard, given mark(D), to find a
> D' that differs from mark(D) in m or fewer bits and does not
> satisify is_marked(D').
>
> With, of course, the corollary:
>
> (iii') is_marked(distort(mark(D))) has a _very_ low
> probability of being false, where distort() is a function that
> flips up to "m" random bits of its input.
>
>Off the type of my head, this looks impossible; requirements (ii) and
>(iii') seem to be working directly contrary to each other. Am I
>mistaken? Has someone solved this problem?
Here's the idea I presented at IHW-3:
a) Embed a watermark using a watermark w: E=mark_w(D).
Now, is_marked_w(E) is true.
b) Find, using inversion attacks, a bunch of marks x_i
such that is_marked_{x_i}(E) is also true.
[In an "inversion" attack, you take the target image and find some
watermark, by inspection, that sets off the detector. These
attacks are usually avoided by requiring each watermark to be
"legally generated," e.g. the output of a pseudo-random
generator based on a key. Thus, any fake x_i you find is HIGHLY
unlikely to have a key generating it.]
c) Publish the set of marks { w, x_1, ..., x_n }, not in that
order. A public detector will find them all in the image.
d) To "prove" the image marked, you use a zero-knowledge proof
that one of the n+1 marks is a legal one, without revealing
which mark is the legally generated one.
-----------
An attacker can use the algorithm to remove any one of the n+1
marks, or maybe any 2 or 3. You let n+1 be so large that
removing n+1 watermarks severely degrades the image. In the
embedding process you only embedded 1 mark; the rest are just
fictional.
>Lon Willett <[EMAIL PROTECTED]>
-Scott
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Steganography and secret sorting
Date: Tue, 26 Sep 2000 21:57:12 GMT
In article <8phkeo$nik$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Matthew Skala) wrote:
[snip]
>
> Would anyone care to comment on this scheme? Do you know if anyone's
> investigated schemes like this before, where a secret message is
concealed
> in the order of a bunch of things that don't have to be in any
particular
> order?
In general, the ordering of N distinct items can hold
log2( N! ) bits of information.
Since there are N possible choices for the first output item, the item
chosen conveys log2(N) bits of information. This leaves N-1 items left
to be chosen. The next choice conveys log2(N-1) bits of information ,
all the way down to the second to last item. The last item conveys no
information, since there is no choice.
You can get full capacity by looking at the message M as a large
integer < N!
You can then chip away at M by using division and modulus operations.
in pseudocode (this may not be entirely correct, so check my work):
for each k in 1 to N-1
StoreNumberViaChoice( M % (N-k+1) )
M = floor( M / (N-k+1) )
endfor
where % denotes modulus remainder operation
You can sacrifice some capacity for a much faster, more scaleable
algorithm by limiting yourself to storing floor(log2(N-k)) bits for
each item k in [1,N-1].
--
Gregor B. Dramkin
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Eric Lee Green <[EMAIL PROTECTED]>
Subject: Re: PRNG improvment??
Date: Tue, 26 Sep 2000 15:13:54 -0700
[EMAIL PROTECTED] wrote:
> Where can I find statistical tests for randomness that I can employ to
> test this idea?
You are not looking for statistical tests of randomness. Well, yes, you do
need your distribution to be random before you get to what you need, but there
are plenty of random distributions which are completely and utterly
predictable. You are looking for statistical tests of predictability. As far
as I know, there are none. It is possible to occasionally prove that a
supposedly unpredictable pseudo-random-number generator is predictable using
mathematical methods (for example, PRNG's which produce the next number as the
remainder of a mathematical operation upon the previous value can be easily
shown to be predictable using normal mathematical induction), but as far as I
know there is no ironclad test that will "prove" that any given RNG or PRNG is
unpredictable (that is, that given an output or set of outputs, you cannot
predict future, intervening, or prior outputs with greater than random chance
probability).
--
Eric Lee Green [EMAIL PROTECTED]
Software Engineer "The BRU Guys"
Enhanced Software Technologies, Inc. http://www.estinc.com/
(602) 470-1115 voice (602) 470-1116 fax
------------------------------
** 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
******************************
