Cryptography-Digest Digest #763, Volume #12 Sun, 24 Sep 00 17:13:01 EDT
Contents:
Re: What make a cipher resistent to Differential Cryptanalysis? (Tom St Denis)
Re: 128-bit Secure LFSR (Whoops) (Tom St Denis)
Re: What make a cipher resistent to Differential Cryptanalysis? (Tom St Denis)
Re: What make a cipher resistent to Differential Cryptanalysis? (Terry Ritter)
Re: Music Industry wants hacking information for cheap (Matthew Skala)
Re: 128-bit Secure LFSR (Whoops) ("bubba")
Re: LFSR as a passkey hashing function? (Simon Johnson)
Re: LFSR as a passkey hashing function? (Tom St Denis)
Re: RSA occasional failure? (Peter Pearson)
Re: LFSR as a passkey hashing function? (Simon Johnson)
Re: LFSR as a passkey hashing function? (Joaquim Southby)
Re: 128-bit Secure LFSR (Joaquim Southby)
Re: RSA occasional failure? (Peter Pearson)
Re: Software patents are evil. (Darren New)
Re: What am I missing? (Scott Craver)
----------------------------------------------------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: What make a cipher resistent to Differential Cryptanalysis?
Date: Sun, 24 Sep 2000 18:19:29 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>
> Tom St Denis wrote:
> >
> > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > > "David C. Barber" wrote:
> > > >
> > > > DES, for example is considered resistant to Differential
> > Cryptanalysis,
> > > > particularly in its selection of S-boxes. What about them, or
any
> > cipher,
> > > > makes it DF resistant?
> > >
> > > I believe that one good way is to arrage to have the
> > > S-boxes of the cipher be all different and to have
> > > them either key-dependent or fixed but having their
> > > ordering dependent on the key. I like to know references
> > > to analysis results for such situations, if any.
> >
> > That's not entirely correct. It's possible to have random key
> > dependent sboxes and still be vulnerable to attacks.
>
> No practical cipher is absolutely secure. I am at least
> not aware that the differential analysis can be applied
> to such S-boxes. And I am also asking for literatures
> of other attacks, if any.
Um the attack on blowfish is a differential attack... And it's
possible to use structural weaknesses against the structures not the
values. I.e I don't need to know your sbox to attack the algorithm.
Take SAFER for example, change the sboxes with keyed ones and replace
the 3PHT with something weaker (i.e an incomplete 2PHT or something).
I could attack that and get your keys...
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: 128-bit Secure LFSR (Whoops)
Date: Sun, 24 Sep 2000 18:17:33 GMT
In article <39ce3cef$0$62628$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Jeff Gonion) wrote:
>
> I don't maintain a website, but if anybody is aware of somplace else
> to post it, I'd be glad to.
>
email it to [EMAIL PROTECTED] and I will shove it on my website
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: What make a cipher resistent to Differential Cryptanalysis?
Date: Sun, 24 Sep 2000 18:22:40 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>
> Simon Johnson wrote:
> >
> > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > > "David C. Barber" wrote:
> > > >
> > > > DES, for example is considered resistant to Differential
> > Cryptanalysis,
> > > > particularly in its selection of S-boxes. What about them, or
any
> > cipher,
> > > > makes it DF resistant?
> > >
> > > I believe that one good way is to arrage to have the
> > > S-boxes of the cipher be all different and to have
> > > them either key-dependent or fixed but having their
> > > ordering dependent on the key. I like to know references
> > > to analysis results for such situations, if any.
>
> >
> > I don't see how an s-box can have its structure dependent on the key
> > without a probability of producing very poor s-boxes. Is this an
> > accepted risk or do they use some fool proof transformation.
>
> I have personally no experience in S-box design. But
> I suppose one could incorporate some checks to prevent
> very poor boxes or else simply rely on the fact that
> the chance of their occuring is very small and there
> are many rounds of the cipher to compensate for that.
> One could also let the key to select from a large set
> of tested S-boxes. There are presumably better ways,
> but I can't tell for lack of knowledge.
Speaking from an empircle stand point your idea is very flawed. Almost
all 3x3 sboxes are ideal (low dp/lp max), most 4x4's are ok, but when
you get to 8x8 and above most are not ideal. Actually a while ago I
did stats on them.. I found about 99% of all 8x8's had a LPmax of about
34, and a DPmax of 16 or more. In fact I have yet to see a randomly
generated 8x8 with a LPmax under 28 and a DPmax under 8...
However, why does a low DPmax or LPmax have to equate to the only means
of security? (Hint: Decorrelation Theory)
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: What make a cipher resistent to Differential Cryptanalysis?
Date: Sun, 24 Sep 2000 18:43:03 GMT
On Sun, 24 Sep 2000 10:32:37 GMT, in <8qkl86$8m7$[EMAIL PROTECTED]>, in
sci.crypt Simon Johnson <[EMAIL PROTECTED]> wrote:
>[...]
>I don't see how an s-box can have its structure dependent on the key
>without a probability of producing very poor s-boxes. Is this an
>accepted risk or do they use some fool proof transformation.
I suppose the real answer is to study the characteristics of random
s-boxes of various size and see just what the distribution of
"poorness" really is.
I have measured many random tables with respect to nonlinearity and
have developed the distribution of nonlinearity at different table
sizes. (See, for example
http://www.io.com/~ritter/JAVASCRP/NONLMEAS.HTM
). A random "4-bit" table with 16 4-bit entries has a typical
nonlinearity of 2, so changing just 2 bits in one of the Boolean
functions will produce an true affine function.
In contrast, a random "8-bit" table has a typical nonlinearity of 100,
so 100 bits must change to reach the closest affine Boolean function.
In actual experiments measuring 1,000,000 8-bit tables, exactly one
was found with a nonlinearity as low as 78.
So if the probability of getting a really poor s-box is much smaller
than the probability of simply guessing the key, there may not be much
risk to accept.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Matthew Skala)
Subject: Re: Music Industry wants hacking information for cheap
Date: 24 Sep 2000 11:17:21 -0700
In article <8qjlq4$4k$[EMAIL PROTECTED]>,
Scott Craver <[EMAIL PROTECTED]> wrote:
> Even if you connected a surveillance camera to a digital video
> recording device with DVD watermark detection (which would be
> stupid overkill, considering the low quality of the camera,)
> it wouldn't somehow refuse to record. Input from your camera
> won't have any watermark magically embedded in it! The
> proposed DVD watermarking scheme would only refuse to record
> something that has already been marked, "do not record."
One of the scenarios someone on this thread suggested went like this:
Alice is a bank robber; she knows that Bob, the police officer, has placed
a surveillance camera in the bank and it's attached to a recording device
that detects watermarks and refuses to record marked data. So she walks
into the bank wearing a T-shirt with a watermark printed on it, or perhaps
puts a video screen playing a watermark pattern in view of the
camera. The recording device refuses to record it, and so her crime
doesn't show up on the tape.
--
Matthew Skala
[EMAIL PROTECTED] I'm recording the boycott industry!
http://www.islandnet.com/~mskala/
------------------------------
From: "bubba" <[EMAIL PROTECTED]>
Subject: Re: 128-bit Secure LFSR (Whoops)
Date: Sun, 24 Sep 2000 19:00:09 GMT
Here is a fast primitive polynomial search that includes some builds
that are supposed to work on a Pentium II (ot AMD K6-2).
http://sduplichan.home.att.net/primitive/primitivePolynomials.htm
ppsearch256 bits=128 hex search=10
100000000000000000000000000000087
100000000000000000000000000000173
100000000000000000000000000000175
1000000000000000000000000000003F9
10000000000000000000000000000068D
1000000000000000000000000000006F3
100000000000000000000000000000743
1000000000000000000000000000007B5
1000000000000000000000000000007DF
10000000000000000000000000000083B
ppsearch256 bits=128 hex search=10 poly=0x123456789abcdef0123456789abcdef
10123456789ABCDEF0123456789ABCECD
10123456789ABCDEF0123456789ABD015
10123456789ABCDEF0123456789ABD023
10123456789ABCDEF0123456789ABD031
10123456789ABCDEF0123456789ABD105
10123456789ABCDEF0123456789ABD39D
10123456789ABCDEF0123456789ABD46F
10123456789ABCDEF0123456789ABD5AD
10123456789ABCDEF0123456789ABD7F3
10123456789ABCDEF0123456789ABD87B
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:8qlgff$4ll$[EMAIL PROTECTED]...
> In article <39ce3cef$0$62628$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (Jeff Gonion) wrote:
> >
> > I don't maintain a website, but if anybody is aware of somplace else
> > to post it, I'd be glad to.
> >
>
> email it to [EMAIL PROTECTED] and I will shove it on my website
>
> Tom
>
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: LFSR as a passkey hashing function?
Date: Sun, 24 Sep 2000 19:08:33 GMT
In article <8qlapf$uhu$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
> In article <8qlaa8$u4v$[EMAIL PROTECTED]>,
> Simon Johnson <[EMAIL PROTECTED]> wrote:
> > In article <8ql9oo$tgt$[EMAIL PROTECTED]>,
> > Tom St Denis <[EMAIL PROTECTED]> wrote:
> > > In article <8ql8cb$rte$[EMAIL PROTECTED]>,
> > > Simon Johnson <[EMAIL PROTECTED]> wrote:
> > > > Say we take a 128-bit primitive polynomial mod 2 and covert it
to
> > an
> > > > LSFR. If we want to store a 128-bit passkey for a 128-bit key
> > > > encryption algorithm, for example, we would enter the key as the
> > > > initial state of the register. We then clock it 128 times, to
> clear
> > > out
> > > > the passkey. Then we clock it a futher 128-bit times, and record
> > this
> > > > bit sequence as the hash. Any problems with this design?
> > >
> > > Not really except the fact that I can step it backwards and find
> your
> > > passkey :-)
> > >
> > > Tom
> > >
> > > Sent via Deja.com http://www.deja.com/
> > > Before you buy.
> > >
> >
> > Ooops :) -> How, may i ask?
>
> Well consider the four bit LFSR x0..x3, with a feedback x0^x3 we get,
> with
>
> x0 = x0^x3
> ... rotate bits ...
> x0 = x0^x3
> ... rotate bits ...
>
> You can invert it by rotating the opposite direction and xor'ing
again.
>
> I think that would work...
>
> All LFSR's have predecessor states and they are linear so there should
> be a nice inverse...
> Tom
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
>
Yup, it seems to work on paper. Damn! :)
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: LFSR as a passkey hashing function?
Date: Sun, 24 Sep 2000 19:22:38 GMT
In article <8qljf5$85l$[EMAIL PROTECTED]>,
Simon Johnson <[EMAIL PROTECTED]> wrote:
> In article <8qlapf$uhu$[EMAIL PROTECTED]>,
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> > In article <8qlaa8$u4v$[EMAIL PROTECTED]>,
> > Simon Johnson <[EMAIL PROTECTED]> wrote:
> > > In article <8ql9oo$tgt$[EMAIL PROTECTED]>,
> > > Tom St Denis <[EMAIL PROTECTED]> wrote:
> > > > In article <8ql8cb$rte$[EMAIL PROTECTED]>,
> > > > Simon Johnson <[EMAIL PROTECTED]> wrote:
> > > > > Say we take a 128-bit primitive polynomial mod 2 and covert
it
> to
> > > an
> > > > > LSFR. If we want to store a 128-bit passkey for a 128-bit key
> > > > > encryption algorithm, for example, we would enter the key as
the
> > > > > initial state of the register. We then clock it 128 times, to
> > clear
> > > > out
> > > > > the passkey. Then we clock it a futher 128-bit times, and
record
> > > this
> > > > > bit sequence as the hash. Any problems with this design?
> > > >
> > > > Not really except the fact that I can step it backwards and find
> > your
> > > > passkey :-)
> > > >
> > > > Tom
> > > >
> > > > Sent via Deja.com http://www.deja.com/
> > > > Before you buy.
> > > >
> > >
> > > Ooops :) -> How, may i ask?
> >
> > Well consider the four bit LFSR x0..x3, with a feedback x0^x3 we
get,
> > with
> >
> > x0 = x0^x3
> > ... rotate bits ...
> > x0 = x0^x3
> > ... rotate bits ...
> >
> > You can invert it by rotating the opposite direction and xor'ing
> again.
> >
> > I think that would work...
> >
> > All LFSR's have predecessor states and they are linear so there
should
> > be a nice inverse...
> > Tom
> >
> > Sent via Deja.com http://www.deja.com/
> > Before you buy.
> >
> Yup, it seems to work on paper. Damn! :)
Try this.
1. Feed the state with 'n-bits' of userkey
2. Run the LFSR for 2n times thru a self-shrinking generator
3. Take the final state as the hash
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Peter Pearson <[EMAIL PROTECTED]>
Subject: Re: RSA occasional failure?
Date: Sun, 24 Sep 2000 12:38:23 -0700
Paul Rubin wrote:
>
> [EMAIL PROTECTED] (Mark-Jason Dominus) writes:
>
> > But Fermat's theorem only applies in this case if x is not a multiple
> > of p; if x is a multiple of p then x^(p-1) (mod p) might be something
> > other than 1.
> >
> > Since x is the plaintext, it is chosen by someone who doesn't know p
> > or q. It seems that if x unfortunately turned out to be a multiple of
> > p, then the decryption process would fail and yield a gibberish
> > result.
>
> Since N=pq, the chance of a random x < N being a multiple of p is 1/q.
> Since q is normally > 10^100, this probabilit is negligible. But
> you're correct, if you pick some small primes (p=3, q=5) and try to
> work an RSA example on the blackboard and choose the wrong x, you can
> sometimes get bitten by this.
Absolutely wrong. Correct RSA decryption does not require that the
plaintext be relatively prime to the modulus. I invite you to make
a monkey of me by finding a counterexample.
- Peter
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: LFSR as a passkey hashing function?
Date: Sun, 24 Sep 2000 19:34:33 GMT
Yeah, after iterating the attack you describe further it does break
down after quite a few iterations. (This doesn't matter, it still
proves insecurity)
Are Self Shrinking generators secure? - Schneier seems a little warry
in Applied Cryptography - has much work been done on them since the
time of writing?
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Joaquim Southby <[EMAIL PROTECTED]>
Subject: Re: LFSR as a passkey hashing function?
Date: 24 Sep 2000 19:52:54 GMT
In article <8qlapf$uhu$[EMAIL PROTECTED]> Tom St Denis,
[EMAIL PROTECTED] writes:
>Well consider the four bit LFSR x0..x3, with a feedback x0^x3 we get,
>with
>
>x0 = x0^x3
>... rotate bits ...
>x0 = x0^x3
>... rotate bits ...
>
>You can invert it by rotating the opposite direction and xor'ing again.
>
>I think that would work...
>
Not exactly, although you're on the right track. The XOR'ing in the
reverse direction is performed on different bits than in the forward
direction.
Ex., using 0001 as the initial state of the LFSR, the succeeding states
in the "forward" state space are:
0001
1000
1100
1110
1111
0111
1011
0101
1010
I'll define the leftmost bit as both bit 4 and the input bit and the
rightmost bit as both bit 1 and the output bit.
To move backwards from the last state (state n), a shift left is
performed:
010x
The x in bit 4 represents the output bit that was shifted out in during
the forward movement of the state machine. We have the information that
this bit, XOR'ed with bit 1 in state n-1, produced bit 1 in state n.
Therefore, an XOR performed between bit 1 of state n and bit 1 of state n
- 1 will produce the value of bit 4 of state n - 1. In the example, bit
1 of state n is a 1 and bit 1 of state n - 1 is a zero; the XOR gives a
1, so state n - 1 is 0101.
Repeating this operation:
1010
0101 (XOR the two bit 1's together to get a 1 for bit 4)
1011 (XOR the two bit 1's together to get a 1 for bit 4)
0111 (ditto --> 1 for bit 4)
1111 (1 for bit 4)
1110 (this time it's a 0 for bit 4)
1100 (another 0 for bit 4)
1000 (0 for bit 4)
0001 (1 for bit 4; this is the original state)
Note that you could also get the same results by XOR'ing bits 1 and 2 of
state n and using the result as bit 4 of state n - 1. This is because
bit 2 of state n is bit 1 of state n - 1.
While this is extremely easy for a trinomial, a dense polynomial would
take a little more exercise to reconstruct. Applied Crypto lists some
papers that describe how to attack an LFSR in this manner.
------------------------------
From: Joaquim Southby <[EMAIL PROTECTED]>
Subject: Re: 128-bit Secure LFSR
Date: 24 Sep 2000 20:01:06 GMT
In article <39ce3cef$0$62628$[EMAIL PROTECTED]> Jeff Gonion,
[EMAIL PROTECTED] writes:
>I don't maintain a website, but if anybody is aware of somplace else
>to post it, I'd be glad to.
>
> - Jeff
>
Try [EMAIL PROTECTED] (the usual instructions apply here). Forrest
maintains a website <http://homepage.mac.com/afj/lfsr.html> on LFSR's and
he would probably post it up there. Forrest, are you lurking?
------------------------------
From: Peter Pearson <[EMAIL PROTECTED]>
Subject: Re: RSA occasional failure?
Date: Sun, 24 Sep 2000 13:15:52 -0700
Mark-Jason Dominus wrote:
[...snip...]
>
> But Fermat's theorem only applies in this case if x is not a multiple
> of p; if x is a multiple of p then x^(p-1) (mod p) might be something
> other than 1.
True, but RSA encryption and decryption don't actually require that
x^(p-1) = 1 (mod p); they require something more akin to x^p = x (mod
p).
Consider the case with modulus 10. Phi(10) = (5-1)*(2-1) = 4, so
an RSA cryptosystem based on this modulus requires that x^5 mod 10 = x.
You might expect 2 to be a bad player, since 2^4 mod 10 = 6, not 1;
but note that 2^5 mod 10 = 2, as desired.
Fermat's theorem is the easiest way to give a plausibility argument
for RSA encryption and decryption, but as you observe, it doesn't
prove that RSA encryption and decryption *always* work.
Fortunately RSA encryption and decryption *do* always work, but the
proof for the general case is just a little more complex than Fermat's
theorem. You can sketch it for yourself with this hint from the
Chinese Remainder theorem: if p and q are different primes
and x=y mod p and x=y mod q, then x=y mod pq.
Enjoy.
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Software patents are evil.
Date: Sun, 24 Sep 2000 20:22:20 GMT
Jerry Coffin wrote:
> Please actually READ what I say before you call it nonsense. Take
> particular note of the fact that I said "valid patent."
Well, I'd assume that "valid patent" means "a patent passed by the patent
office that has not yet been sucessfully disputed." If you mean "should
have been issued" when you say "valid", then you're using terms differently
from any business, court, or legal system I've encountered.
Since you can always challenge a patent, regardless of how often it has been
challenged and found "still valid", there would be no such thing as a "valid
patent" if your definition was used. In particular, you would have to define
what *you* mean by "valid patent" in a non-vacuous way.
> enough effect to ignore. In particular, the effect on society as a
> whole is essentially nil: if somebody hasn't published it, hasn't
> sold a product that uses it, etc., from the viewpoint of the rest of
> society it's essentially the same as if it didn't exist at all.
Then you need to read my post again. We were selling the product for three
years. Then someone else applied for a patent, and it was cheaper to license
than fight. That, I would say, is broken.
I think if the only patents that got issued were for actually innovative
stuff (like RSA, say), then it would certainly be much less painful.
--
Darren New / Senior MTS & Free Radical / Invisible Worlds Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
"No wonder it tastes funny.
I forgot to put the mint sauce on the tentacles."
------------------------------
From: [EMAIL PROTECTED] (Scott Craver)
Subject: Re: What am I missing?
Date: 24 Sep 2000 20:26:45 GMT
Sagie <[EMAIL PROTECTED]> wrote:
>Before going any further, I feel I should state that I have not
>downloaded any of the SDMI samples. Their just too damn big and I have
>got other things to do with my already narrow 33.6K dial-up bandwidth.
Okay. A more fruitful search might be looking for research
papers on watermarking schemes: those should take up less
memory (50meg worth of research is a mighty large read) and
would be more enlightenting.
Try starting w/ the following excellent resources:
http://www.cl.cam.ac.uk/~fapp2/steganography/
http://www.isse.gmu.edu/~njohnson/
And the book mentioned on the first site is a great reference
book [ad ad ad.]
>> They do indeed survive MP3 compression. That is probably their
>> main design goal.
>
>I am sure that this is one of their primary goals, but how can you tell
>that they really do survive MP3 compression?
It would be unbelievable if they didn't. If you'd like, I
can submit a compressed-then-decompressed audio track to one
of their oracles, but I'm almost absolutely certain that
all the proposed schemes do survive MP3.
>> Many of these schemes are based on techniques that clearly can't
>> be compressed out. And anything that survives MP3 or AAC
>> compression is going to survive subsequent codecs for a long
>> time.
>
>First of all, you don't know (well not for sure) what techniques are
>being used by any of these watermark technologies. Secondly, I think
>you are being short-sighted. Psycho-acoustic models are constantly
>being improved.
That doesn't matter. There are some operations that SHOULD
NOT be undone by a compressor, even if they COULD.
Here's a stupid example: take an audio clip (we'll call it
clip B) and do a little multirate on it to shift all the
frequencies up one half step (we'll call this version clip C.)
Now sic some amazing compression algorithm on both clips B and C.
Is there any chance the compressor could undo that half-step shift?
Of course not: given clip C, there is no way a compressor could
know whether C is a deformation of B, or if C was really recorded
that way, the musicians actually playing in a key a half step up.
Any compression scheme that compresses B and C to the same thing is
a broken compression scheme!
It's a stupid example, of course, because shifting the frequencies
up a half-step is very unreasonable modification. Notice, however,
that without the original clip B for reference, most people wouldn't
notice anything "wrong" with clip C: only those musically inclined,
who may know the song is usually in the key of B.
See?
There's this set of operations that are considerably more subtle,
which would turn a clip A into a clip B such that A and B
_should not_ be compressed to the same file. By "subtle" I mean
such that one can listen to A and B one at a time and not tell
how they are different. Maybe playing both at once one can hear
the difference, but since only B will be distributed that doesn't
matter.
>> I'm pretty confident it will. Many clever methods will
>> survive anything the compression people can come up with.
>> You should read some papers on audio embedding methods,
>> and then see if you have any doubts.
>
>Maybe I should. But only future will tell how the watermarking
>techniques will survive future compression methods.
Really, this is the wrong tree. It's not compression they
have to worry about, but hackers. I'm extremely, very, super-
duper confident that any serious audio watermarking scheme
will survive any compression algorithm developed during the
scheme's expected lifetime of deployment. I say this as a
(relative) expert.
>> I don't think you understand the amount of work that is
>> required to defeat a watermark, if you don't know the algorithm.
>
>Actually, I do. But I think it is quite obvious that with the data that
>SDMI have provided us with, there is nothing serious you can really do.
<shrug>
>The analytical information that can be gathered from Photoshop is not
>as abundant as the information that is provided by audio editors
>nowadays.
>A picture has much more information than sound does, and Photoshop
>doesn't provide nearly as much analytical tools as audio editors.
Fine, then:
>> Throw in a program to do various tranforms like DCTs or FFTs if
>> you want.
>
>Sure, if you'll give me some. I thought we were talking about readily-
>available, popular, easy-to-use editing tools (namely Photoshop).
Still, with these extra utilities, you are still not going to
figure it out just by looking around. You'll see some patterns
(symmetry in the FFT, for instance,) but getting from that to
how it works is like getting from the discovery that DES ciphertext
is in 8-byte blocks to figuring out the plaintext.
>I'm afraid *YOU* don't know what analysis is (look it up in the
>dictionary). Each of the methods that I have described are all
>different kinds of analysis. They are not important _for_ analysis,
>they *ARE* analysis (by definition! one method is even
>called "frequency analysis" for god's sake).
Let me hop up to the newsgroups: line...
No, this is only being posted to sci.crypt.
Guy, in cryptography the word "analysis" has a special meaning.
It means, roughly, "deciphering" or "breaking." I.e., cryptanalysis
or steganalysis. If someone publishes a paper titled "An Analysis
of cipher XYZZY," then readers will expect to read that the author
either cracked XYZZY, or at least successfully extracted some useful
information about how it works that takes us a big step to cracking.
Successfully analyzed schemes are trusted less.
Successfully performing a Fourier analysis of a watermarked
clip is not "a successful analysis" of the watermarking scheme.
It's just a semantic quibble, but you should keep this in mind
when hanging out on crypto groups or lists.
>That's not quite the same. You are talking about encryption, but we
>were discussing watermarking. Encryption is designed to avoid
>mathematical models, watermarking is designed to avoid human sensory
>systems.
Often true, but _good_ watermarking schemes are also designed
to avoid discovery by hackers. Of watermarking schemes that use
secret keys, for instance, many are such that you will NEVER find
any pattern. The pioneering work by Ingemar Cox et al is a
fantastic example. Digimarc is less so, because it doesn't
involve a secret key to detect the mark.
Also see the work of Lisa Marvel et al, who developed a spread-
spectrum stego scheme that can conceal about 5 kilobytes very
robustly (and error correction is all taken care of) in a 512x512
monochrome image. It's keyed, and without the key you probably have
pretty much no hope (other than brute force) of extracting the
message.
>For instance, phase changes are usually inaudible and undetectable to
>the human ear. Using mathemtical analytic tools, however, it is easy to
>detect such changes. I have no doubt that certain audio watermarking
>use phase modulation techniques. Furthermore, even *you* said that the
>Digimarc watermark is a coherent pattern. If it is a coherent pattern,
>than it is detectable with analytical tools.
Fair enough, but unless you're a real whiz, you'll still not
detect it. If you hit upon just the right filter, then yes.
And again, the difference between noticing a pattern and
deciphering the thing is great. You will instantly find that
the Digimarc mark is almost periodic and rotationally symmetric.
You're still a long, long way from seeing the bits.
Better to just get the algorithm by reading the patent.
-S
------------------------------
** 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
******************************
