Cryptography-Digest Digest #109, Volume #14 Sun, 8 Apr 01 23:13:00 EDT
Contents:
Re: Concerning United States Patent 4979832 (Dynamic Substitution) (Benjamin
Goldberg)
Re: How good is steganography in the real world? (Joe H Acker)
Re: Would dictionary-based data compression violate DynSub? (Benjamin Goldberg)
Re: How good is steganography in the real world? ("Trevor L. Jackson, III")
Re: Self Enforcing Protocol (Slightly OT and Long!) (Benjamin Goldberg)
Is this a block cipher? ("Mr. Smith")
Re: Is this a block cipher? ("Tom St Denis")
Re: Steganography with natural texts (Yamaneko)
Re: Dynamic Substitution Question ("r.e.s.")
Re: Is this a block cipher? ("Mr. Smith")
Re: Is this a block cipher? ("Tom St Denis")
Re: Is this a block cipher? (Rick Wash)
----------------------------------------------------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Concerning United States Patent 4979832 (Dynamic Substitution)
Date: Mon, 09 Apr 2001 00:15:25 GMT
Benjamin Goldberg wrote:
>
> John Savard wrote:
> >
> > I was startled to see Terry Ritter claiming a broader interpretation
> > of his Dynamic Substitution patent than I had imagined had applied.
> >
> > However, I see even from the abstract of the patent that it does
> > refer to more than I had associated with the term "Dynamic
> > Substitution":
> >
> > As I quote from that patent: "Each data value from the first data
> > source is transformed by substitution using one of potentially
> > multiple translation tables. The translations within each table can
> > be changed after each substitution operation using a changes
> > controller.
>
> If a cipher can be considered a substitution table [or rather a set of
> substitution tables, of which one is selected by a key], we can define
> an example of Dynamic Substitution cipher as the following:
What I should have said above was, if any kind of substitution of one
[fixed length? Well, not necessarily, but it makes things simpler]
block for another can be considered a table, then ... .
Interestingly, I've come up with another dynamic substitution cipher.
All the data elements are instances of permutations of 1..N.
perm table;
perm dynamic_substitution(perm di, perm ri) {
perm do = di.compose(table);
table = table.compose(ri);
return do;
}
> > Commonly, the just-used table is re-arranged or permuted;
> > permutation retains invertibility, so that the ciphertext may be
> > deciphered.
To invert:
perm dyn_unsubstitute(perm di, perm ri) {
table = table.compose( ri.inverse() );
return di.compose( table.inverse() );
}
> > Thus, the specific design I associated with the term "Dynamic
> > Substitution" is indicated as simply a *particular design*.
>
> Right, so other things are Dyn Sub other than that one design.
>
> > Changing elements in the table in other ways than by permuting them
> > is also noted.
>
[snip]
> If you compose the permutation with another permutation, the result is
> a permutation.
[snip]
>
> > Dynamic Substitution operates by taking a table, and modifying that
> > table directly by an operation on its entries.
>
> Whoops! No, it works by making a table, and modifying that table.
> Where did you see mention of operations directly on its entries?
I should have said, "Where did you see *explicit* mention ..."
After all, there are such operations in the "prefered embodiedment."
[snip]
> > This allows any possible arrangement of the table to be reached, and
> > therefore has an effect different from merely producing an effective
> > table from a fixed table and an operation with a varying quantity
> > such as XOR or addition.
>
> Ahh, now this is something new, introduced by you.
>
> Nothing in DS requires that any possible arrangement of the table be
> reachable. It's a nice property, and is certainly a property of the
> "preferred embodiedment" but not one of DS in general.
In my newest version (where elements combined by ds are permutations),
this property is produced. Now, why would one want to combine
permutations [as opposed to bitstrings] with dynamic substitution?
Well, I'm sure that it's possible to bijectively convert a bitstream to
a stream of permutations, and values for RI can easily produced by
Durstenfeld shuffle (aka algorithm-p).
Another possible use, is that it might possibly be used for combining
two psuedo-randomly produced permutations in a way that hides the
generator sequences, and then use the resulting permutation to encipher
one block in Ritter's DT cipher. Surely this is more effective that the
double-shuffling that the DT papers suggest.
--
Sometimes the journey *is* its own reward--but not when you're trying to
get to the bathroom in time.
------------------------------
From: [EMAIL PROTECTED] (Joe H Acker)
Crossposted-To: comp.security.misc,talk.politics.crypto
Subject: Re: How good is steganography in the real world?
Date: Mon, 9 Apr 2001 02:16:09 +0200
SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
> The reason that neither one is good enough is that if you
> want to concel the fact your encrypting which is a large part
> of what stego is about. Then you can't make it obvious that
> your encrypting. If an enemy know what program you have, Then
> by exaiming a few gifs. He can almost be certain that you are
> encrypting and that is bad.
Yes, I think that's because good encryption usually does output data
that appears to be random while good steganography should output data
that has the same statistical properties than any "possible variation"
of the message of the media you use for hiding the secret message. E.g.
many different GIFs can display the same picture, but the differences
are not random at all, they depend on the GIF format and on the picture
displayed. Just spreading the bits of the secret message randomly over
the GIF does not help, they need to be spread in a way that the
resulting GIF is just a different GIF that displays the same picture but
could occur as probably as the original GIF.
Regards,
Erich
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Would dictionary-based data compression violate DynSub?
Date: Mon, 09 Apr 2001 00:47:34 GMT
David Formosa (aka ? the Platypus) wrote:
>
> On Sat, 07 Apr 2001 07:29:55 GMT, Terry Ritter <[EMAIL PROTECTED]> wrote:
> >
> > On Sat, 07 Apr 2001 06:24:53 GMT, in
> ><[EMAIL PROTECTED]>, in sci.crypt
> > [EMAIL PROTECTED] (David Formosa (aka ? the Platypus)) wrote:
>
> [...]
>
> >>How is the application diffrent from Algorithm M?
> >
> > Perhaps you should first try to replace the XOR in a stream cipher
> > or OTP with Algorithm M, and see what the problems might be.
>
> So basically the Patant covers using a dynamic substition table when
> combining a keystream with a datastream? And not when combining two
> keystreems (in Algorithm M) or used to generate a keystreem (in the
> case of RC4).
The patent does try to cover combining two keystreams to produce a
stronger keystream, but these I think that the keystreams must somehow
be two distinct sources. If both sources are PRNGs, whose states are
both within the the computer doing the combining, then I believe that
they can be considered one source. Mr. Ritter will probably disagree
with that.
If DS is used to combine a plaintext and a PRNG-produced-keystream, or a
publicly visible random stream and a PRNG-produced-keystream, or a
plaintext with a public random stream, then the patent surely covers it.
However, if what you have are two deterministic PRNGs, then they could
concievably be viewed as one PRNG with two outputs, rather than as two
seperate sources. You can combine the outputs of the PRNG with the
"prefered embodiement" of DS if you want, but it will not be a Dynamic
Substitution scheme, and not covered by the patent.
If the above paragraph were untrue, then RC4, all by itself, could be
considered a violation of DS.
> > And of course since there are no distinct sequences of data and
> > confusion in Algorithm M, there is also no thought about how the
> > process might be undone or the data extracted on the other end.
>
> Ok that helps.
--
Sometimes the journey *is* its own reward--but not when you're trying to
get to the bathroom in time.
------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: comp.security.misc,talk.politics.crypto
Subject: Re: How good is steganography in the real world?
Date: Mon, 09 Apr 2001 00:49:04 GMT
Mok-Kong Shen wrote:
> It's absurd, but porno sites could do that kind of job
> well, I suppose.
In an intensely Muslim nation? That traffic might be more dangerous than the
plaintext.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Self Enforcing Protocol (Slightly OT and Long!)
Date: Mon, 09 Apr 2001 01:19:12 GMT
For the purposes of discussion, let's assume that each player's
libraries initially consist of an entire deck.
Jim Farrand wrote:
[snip]
> Cards have a TypeID which represents the card type. It is fixed for
> the duration of the game. There may be several cards with the same
> TypeID in the game.
[snip]
> The Library operates slightly differently. A Player will always know
> the TypeID of cards in his library because he knows:
>
> 1. What cards he started with.
> 2. What cards are in his hand.
> 3. What cards are in play.
>
> (1-(2+3)) is the cards in his library.
The cards in play are those contributed by both players. Suppose that
player A has played an ace of spades. Player B also has an ace of
spades in his library, but he thinks he doesn't, cause he's subtracted
the one on the table.
It seems to me that it would be better to explicitly keep track of what
cards he has in his library.
With all of the above in mind, I think I can see another way of
cheating, if the protocol isn't modified.
After Player A draws an Ace of spades from his library, then when some
card is returned to the library, he renames one of the cards in his
library as an Ace of spades. As long as he doesn't end up with two aces
of spades in his library, and doesn't have two of his aces of spades in
play, he can get away with it. This may sound unuseful, but it changes
the odds significantly.
--
Sometimes the journey *is* its own reward--but not when you're trying to
get to the bathroom in time.
------------------------------
From: "Mr. Smith" <[EMAIL PROTECTED]>
Subject: Is this a block cipher?
Date: Mon, 09 Apr 2001 01:28:03 GMT
Greetings! I'm a newbie here, trying to grasp the basic structure of
ciphers, and cryptography in general. I know what a stream ciper is.
However, the block ciper is a bit confusing. Does it work like the example
below?
Key 1:
aaa = gws
aab = wjc
aac = qlg
...
zzz = eut
Key 2:
aaa = jsd
aab = nas
aac = qlm
...
zzz = haa
I'd also like a clarification on exactly what a ket is. I think I know, but
re-enfocement wouldn't hurt! ;-) Thanks.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Is this a block cipher?
Date: Mon, 09 Apr 2001 01:35:00 GMT
"Mr. Smith" <[EMAIL PROTECTED]> wrote in message
news:De8A6.94286$[EMAIL PROTECTED]...
> Greetings! I'm a newbie here, trying to grasp the basic structure of
> ciphers, and cryptography in general. I know what a stream ciper is.
> However, the block ciper is a bit confusing. Does it work like the example
> below?
>
> Key 1:
> aaa = gws
> aab = wjc
> aac = qlg
> ...
> zzz = eut
>
> Key 2:
> aaa = jsd
> aab = nas
> aac = qlm
> ...
> zzz = haa
>
> I'd also like a clarification on exactly what a ket is. I think I know,
but
> re-enfocement wouldn't hurt! ;-) Thanks.
Conceptually a block cipher is a huge book where you look up an input (say a
page number) and you output the text on that page. In practive block
ciphers are not implemented as big lookup tables. They are done as
algorithms which form bijections.
May I suggest you read a few good books (the other sci.crypters will fill ya
in)
Tom
------------------------------
From: Yamaneko <[EMAIL PROTECTED]>
Subject: Re: Steganography with natural texts
Date: Mon, 09 Apr 2001 00:37:30 -0100
Reply-To: [EMAIL PROTECTED]
Mok-Kong Shen wrote:
>
> Let's partition the set of words that are relevant to the
> normal messages of the communication partners into
> disjoint subsets, ...
Good idea. Advantage: A completely natural looking and intelligible text.
Disadvantage: Both parties must to have two identical and rather large
(~1000 couples of words) dictionaries.
> Of course, the covertext must be long enough to be able to
> embed all the bits of the secret message. A technical point
> is how to signal the end of the embedded bit sequence,
> since there may be further words in the covertext that also
> belong to the agreed-upon subsets. One possibility is to
> reserve one or two words in each subset for that purpose.
In order to be safe, the entire secret message must be pseudo random.
That means: Only ciphertext, random initialization vectors and hashes,
and no plaintext headers, no unencrypted stop bytes, no unencrypted
lengths etc. You're idea wouldn't be safe (= statistically undetectable)
in the long run without complete encryption before hiding.
The hidden message could have the format:
IV + E(k, ["12345"] + length + message [+ checksum]) + random padding
When unpacking, you'd interpret the first extracted bytes as an IV,
decrypt the following bytes and interpret the result as a length, then
decrypt <length> extracted bytes to form the plaintext and discard the
rest.
Optionally the message could be prepended with a known plaintext for
verifying the key k, and appended with a checksum.
Yamaneko
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: Re: Dynamic Substitution Question
Date: Sun, 8 Apr 2001 18:51:53 -0700
"newbie" <[EMAIL PROTECTED]> wrote ...
| Is your idea working in this way
| (as explained by John Savard)?
|
| Plaintext: 4 3 1 9 0 2 4 7
| Keystream: 1 7 0 9 8 1 6
| Table: 0|5 5 5>7 7>6 6 6
| 1|2>7 7>5 5 5>9 9
| 2|9 9 9 9 9 9>5 5
| 3|0 0>4 4 4 4 4 4
| 4|7>2 2 2 2 2 2>3
| 5|1 1 1 1 1 1 1 1
| 6|3 3 3 3 3 3 3>2
| 7|4 4>0 0 0 0 0 0
| 8|6 6 6 6 6>7 7 7
| 9|8 8 8 8>8 8 8 8
| Ciphertext: 7 0 7 8 7 9 2 0
|
| If it is the case, then this process
| contain big hole.
What do you see as the "big hole"?
--r.e.s.
------------------------------
From: "Mr. Smith" <[EMAIL PROTECTED]>
Subject: Re: Is this a block cipher?
Date: Mon, 09 Apr 2001 01:58:27 GMT
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:8l8A6.61021$[EMAIL PROTECTED]...
>
> "Mr. Smith" <[EMAIL PROTECTED]> wrote in message
> news:De8A6.94286$[EMAIL PROTECTED]...
> > Greetings! I'm a newbie here, trying to grasp the basic structure of
> > ciphers, and cryptography in general. I know what a stream ciper is.
> > However, the block ciper is a bit confusing. Does it work like the
example
> > below?
> >
> > Key 1:
> > aaa = gws
> > aab = wjc
> > aac = qlg
> > ...
> > zzz = eut
> >
> > Key 2:
> > aaa = jsd
> > aab = nas
> > aac = qlm
> > ...
> > zzz = haa
> >
> > I'd also like a clarification on exactly what a ket is. I think I know,
> but
> > re-enfocement wouldn't hurt! ;-) Thanks.
>
> Conceptually a block cipher is a huge book where you look up an input (say
a
> page number) and you output the text on that page. In practive block
> ciphers are not implemented as big lookup tables. They are done as
> algorithms which form bijections.
>
> May I suggest you read a few good books (the other sci.crypters will fill
ya
> in)
>
> Tom
>
>
Hmmm.... So we have something like this?
Page 1:
abcd
Page 2:
thas
Page 3:
voaq
How do we get the page number?
I always though they went like this...
|This| is |a te|st m|essa|ge. |
(The | show the blocks)
And then you somehow used these blocks in conjuction with a text to find
replacement text.
Or is this idea totally wrong? Thank you for the added clarification.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Is this a block cipher?
Date: Mon, 09 Apr 2001 02:10:00 GMT
"Mr. Smith" <[EMAIL PROTECTED]> wrote in message
news:7H8A6.94296$[EMAIL PROTECTED]...
>
> "Tom St Denis" <[EMAIL PROTECTED]> wrote in message
> news:8l8A6.61021$[EMAIL PROTECTED]...
> >
> > "Mr. Smith" <[EMAIL PROTECTED]> wrote in message
> > news:De8A6.94286$[EMAIL PROTECTED]...
> > > Greetings! I'm a newbie here, trying to grasp the basic structure of
> > > ciphers, and cryptography in general. I know what a stream ciper is.
> > > However, the block ciper is a bit confusing. Does it work like the
> example
> > > below?
> > >
> > > Key 1:
> > > aaa = gws
> > > aab = wjc
> > > aac = qlg
> > > ...
> > > zzz = eut
> > >
> > > Key 2:
> > > aaa = jsd
> > > aab = nas
> > > aac = qlm
> > > ...
> > > zzz = haa
> > >
> > > I'd also like a clarification on exactly what a ket is. I think I
know,
> > but
> > > re-enfocement wouldn't hurt! ;-) Thanks.
> >
> > Conceptually a block cipher is a huge book where you look up an input
(say
> a
> > page number) and you output the text on that page. In practive block
> > ciphers are not implemented as big lookup tables. They are done as
> > algorithms which form bijections.
> >
> > May I suggest you read a few good books (the other sci.crypters will
fill
> ya
> > in)
> >
> > Tom
> >
> >
> Hmmm.... So we have something like this?
>
> Page 1:
>
> abcd
>
> Page 2:
>
> thas
>
> Page 3:
>
> voaq
>
> How do we get the page number?
>
> I always though they went like this...
>
> |This| is |a te|st m|essa|ge. |
>
> (The | show the blocks)
>
> And then you somehow used these blocks in conjuction with a text to find
> replacement text.
>
> Or is this idea totally wrong? Thank you for the added clarification.
Hmm well you have to think in terms of computers. The message is divided
into fixed length blocks and then transformed. I would seriously pick up a
few texts such as Bruce Schneier's Applied Crypto.
Tom
------------------------------
From: Rick Wash <[EMAIL PROTECTED]>
Subject: Re: Is this a block cipher?
Date: 08 Apr 2001 22:33:23 -0400
I myself have been trying to work out the difference between stream
ciphers and block ciphers.
Here is what I have so far. Please let me know if this is correct, or
if I am missing something.
In all cases, Alice and Bob share a key K of size K_n. Alice wants to
send Bob a message M. The goal of the cryptosystem is to replace this
message with C such that only someone who knows K can recover M from
C. This is the definition of a cryptosystem.
In old-days classical cryptography, the message M would be divided
into letters (which was the smallest division that was easy to work
with). Each letter would be replaced with another letter (C->F,
etc. for caesar cipher). The problem with this method is that any
statistical properties of the language of letters is preserved in the
transformation (e.g. since the letter "e" is most likely the most
common letter, whatever letter "e" encrypts to will also be the most
common letter).
To get around this statistical problem, two solutions were proposed.
The first solution is to group letters together into block, and
encrypt whole blocks together. The goal here is that even when the
statistical properties of single letters are strong, groups of
letters have less statisticall significant properties. As the blocks
get larger, the statistical significance decreases. As such, normally
each block is encrypted independent of all other blocks. This is
normally known as a block cipher. Note only whole blocks can be
encrypted at one time.
The second solution to this is to make the encryption depend not only
on the key, but also on some kind of state that is updated with a
feedback loop. In this case, when a letter is encrypted based on the
key and the current state. Then the state is updated, and the next
letter is encrypted with the key and the new state. In this way, each
time the letter "e" is encrypted, it is encrypted to a different value
based on the current state. This obscures the statistical properties
of the plaintext. This is normally known as a stream cipher.
This is my understanding of the difference. Once tries to group
letters into blocks to obscure statistics, and the other tries to add
relationships between letters (state) to obscure statistics.
In modern cryptography (which is normally performed using computers on
bits), a letter is normally 8 bits, and a block is normally 64 or 128
bits. However this is not always the case, and the distinction
between the two is decreasing as "letter-size" increases. Also, the
distinction decreases when using block ciphers in chaining modes
(which essentially adds a "state" to the cryptosystem). This is
probably why is has been difficult for me to properly distinguish
between block ciphers and stream ciphers. The best answer I have for
this is "a block cipher primitive specifies no state between blocks",
and that normally it is used in some mode (like a chaining mode) which
may or may not add state to make it a cryptosystem.
Hope this helps,
Rick Wash
------------------------------
** 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
******************************
