Cryptography-Digest Digest #547, Volume #14 Thu, 7 Jun 01 08:13:00 EDT
Contents:
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler)
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler)
Re: Best, Strongest Algorithm (gone from any reasonable topic)
([EMAIL PROTECTED])
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler)
Re: Notion of perfect secrecy (Tim Tyler)
Re: shifts are slow? (Tim Tyler)
Re: Best, Strongest Algorithm (gone from any reasonable topic)
([EMAIL PROTECTED])
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Mok-Kong Shen)
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Mok-Kong Shen)
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Mok-Kong Shen)
----------------------------------------------------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Reply-To: [EMAIL PROTECTED]
Date: Thu, 7 Jun 2001 10:58:12 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: "Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
:> JPeschel <[EMAIL PROTECTED]> wrote:
:> "perfect secrecy is defined by requiring of a system after a
:> cyptogram is intercepted by the enemy the a posteriori probabilites
:> of this cryptogram representing various messages be identaically the
:> same as the a priori probabilites of the same message before the
:> interception."
:>
:> If the length of the plaintext is revealed by the cyphertext, this
:> condition does not hold.
: How? [...]
It is obvious how the length of the plaintext is revealed by the
cyphertext.
The length of the plaintext is the same as the length of the cyphertext.
: If you have an 8-bit ciphertext all 256 plaintexts are equally
: probable. That follows this distribution.
I am not considering a system with only 256 possible plaintexts.
That's a toy system, with no practical use.
: You're idea of security only works if your cipher can produce infinite
: length ciphertexts.
Not so. Finite plaintexts can produce perfect secrecy.
: (of course your idea of security is vastly flawed)
How so, pray tell?
: I would hate to use 1.7 x 10^55 bytes of ram to send a 10 byte message
: home....
No - that is not correct. You could send a 10 byte message home while
retaining prefect secrecty - assuming a genuinely random shared key was
available.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Reply-To: [EMAIL PROTECTED]
Date: Thu, 7 Jun 2001 11:15:08 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: "Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
:> The opponent knows more about the plaintext after observing the
:> cyphertext than he knew before he saw it - namely the length.
:>
:> The violates perfect secrecy.
: Only if the message is determined by the length.
No. Regardless of what the message is, in fact - provided that messages
of more than one length are transmitted.
: "Oui" or "Non". The length will not determine the message.
It won't distinguish between those two particular messages anyway.
Are those the only possible messages in the system?
: Or if you just pad the bloody thing to a multiple of say 64 bytes. [...]
Still not enough for perfect secrecy :-(
: Even still people won't use an OTP to encrypt single byte messages.
The argument that an OTP does not have perfect secrect does not depend on
single byte messages in any way. I beleive Scott mentioned two and
three byte messages as an example.
Any discussion about one-byte messages seems to be a hangover from the
CTR mode discussion.
:> Traffic analysis information is indeed often present -
:> but we are talking about once a message exists, does
:> the attacker gain anything by looking at the cyphertext.
:>
:> That's what the definition of "perfect secrecy" talks about.
: No [...]
Yes. Look it up. Or read the posted definitions in this thread.
: perfect secrecy is defined as having no ability to tell one plaintext
: from another.
Since telling one plaintext from another is normally a trivial operation,
that statement is nonsense if taken literally.
What you probably mean is that the attacker has no ability to distinguish
between enctyptions of different plaintexts given only a single cyphertext
to work on - which is an equivalent formulation to the one I gave above.
: Who cares if you know the entire set of plaintexts [...]
Well, knowledge of the entire set of plaintexts is better than nothing at
all.
However I've not mentioned that subject AFAICS - I believe you've just
raised it for the first time in this thread.
:> Perfect secrecy applies to encryption devices. Time of
:> message transmission etc is considered to be outside its scope.
:>
:> A conventional OTP, that preserves message length and is
:> asked to deal with variable length messages does *not*
:> have Shannon's perfect secrecy property.
: Yes it does. [...]
<punch and judy>No it does not</punch and judy>
: All messages are equal probable without a priori knowledge.
: Seems to fit the bill.
Nope.
Even *if* all messages are equally probable without knowledge of the
cyphertext, not all messages are equally probably once the cyphertext is
known.
The difference between these two states is where the violation of perfect
secrecy arises.
: Tell me why exactly you think the length of the ciphertext will reveal the
: message? Give an example.
It won't always reveal the message - thought it will always reveal
information about it.
See Scott's Yes/No example for a case of it revealing the entire message.
--
__________ http://rockz.co.uk/ http://alife.co.uk/ http://hex.org.uk/
|im |yler http://atoms.org.uk/ http://mandala.co.uk/ [EMAIL PROTECTED]
------------------------------
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
From: [EMAIL PROTECTED]
Date: 07 Jun 2001 07:34:19 -0400
Tim Tyler <[EMAIL PROTECTED]> writes:
> Tom St Denis <[EMAIL PROTECTED]> wrote:
>: Or if you just pad the bloody thing to a multiple of say 64 bytes. [...]
>
> Still not enough for perfect secrecy :-(
Right--no matter what ``a multiple'' means. It could mean 64 million
bytes, or 64 quintillion terabytes, but that's ``still not enough for
perfect secrecy.'' If the ciphertext has finite length, then some
possible plaintexts will be longer.
That's why all messages must be infinite in length in order to enjoy
``perfect secrecy''. (And note: this is true whether or not any sort
of compression is used.)
Len.
--
The concept of ``security-critical'' depends on what you're trying to
protect.
-- Dan Bernstein
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Reply-To: [EMAIL PROTECTED]
Date: Thu, 7 Jun 2001 11:28:59 GMT
Mark Wooding <[EMAIL PROTECTED]> wrote:
: Tim Tyler <[EMAIL PROTECTED]> wrote:
:> That uses Rijndael in CBC mode.
: Now I'm very confused. You can't get a one-byte ciphertext out of a
: 128-bit block cipher in CBC mode. There's nowhere to put an IV, for one
: thing.
Firstly, Rijndael doesn't use an random IV. It uses a fixed one which is
(I believe) wired into the algorithm.
In order to disguise the first blocks of the message it uses a whitening
step, which preprocesses the plaintext by appling unkeyed diffusion to the
first few K of the plaintext - not /quite/ the same as an IV - but good
enough for many purposes.
Now, about how BICOM gets a 1-byte output from Rijndael output while
remaining invertible and bijective:
I won't describe how it /actually/ does it (though see the end of the post)
- but instead I'll tell a simplified story that indicates how it is possible.
First the set of all byte granular plaintexts is transformed to the set of
128-bit granular messages using a bijection between these two sets.
[e.g. number the elements in each set, smallest first, and map between
elements which are given the same number].
Then that is fed through Rijndael in CBC mode, with a fixed IV.
Then the above bijection is applied in reverse, from the set of 128-bit
granular files to the set of 8-bit granular ones.
The result will sometimes be a single byte.
The BICOM page has actual details:
http://www3.sympatico.ca/mtimmerm/bicom/bicom.html
To quote the explanation of what it's /actually/ doing from there:
``The bijective arithmetic encoder produces an intermediate representation
called a finitely odd stream -- it is an infinitely long sequence of
bits, but with the last 1 bit at a position finitely far from the
beginning, i.e., it is a finite sequence of 0s and 1s, followed by an
infinite sequence of 0s. [...]
``When a passphrase is specified, bicom encrypts (or decrypts) this
intermediate representation using the currently proposed AES cipher,
Rijndael, in CBC mode with a constant initial value and whitening of the
first 16K. Because the finitely odd stream is infinitely long, and all
bits are significant to the output, you can encrypt any part of it
without affecting the bijective nature of the compressor. David Scott
provided the idea of encrypting all but the final 1 bit in this stream,
possibly using overlapping blocks at the end. The result is that all
significant bits of the file are encrypted, with no known or biased
plaintext.''
Hope that helps.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Notion of perfect secrecy
Reply-To: [EMAIL PROTECTED]
Date: Thu, 7 Jun 2001 11:36:56 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: "Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
:> Tom St Denis <[EMAIL PROTECTED]> wrote:
:> : Typically the MEANING of the message is not stored in the length.
:> Shannon refers to *any* information about the identity of the plaintext.
:>
:> For perfect secrecy, observation of the cyphertext should make no
:> difference to the attacker.
:>
:> This is not the case if he was unaware of the length of the plaintext
:> before observing it - and he knows that the length of the cyphertext
:> matches that of the plaintext.
: You don't understand his results that's all. [...]
My understanding is fine thanks.
: In his model WHO, WHEN, LENGTH were not the information he wanted to protect.
"Who" and "when" are not modelled by Shannon. However length /is/
information that relates to the identity of the plaintext
(except in the case where all possible plaintexts are the same length)
and *is* covered by Shannon's definition of perfect secrecy.
: You're really mocking the dead here. I sincerely hope you are some
: 12yr kid trying to get a rise out of people, otherwise I wonder how you
: did in College challenging all your profs without listening to their
: proofs... No offense Tim but you have a lot of growing up todo. Even
: if you are 76 yrs old you're an immature brat as far as I am concerned.
Sorry you feel that way Tom. It seems this is the thanks I get for
pointing out your errors. Maybe I won't bother in the future.
: Anyways this is all OT.
You started this thread about perfect secrecy - which incidentally is not
off topic at all.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: shifts are slow?
Reply-To: [EMAIL PROTECTED]
Date: Thu, 7 Jun 2001 11:39:04 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: "Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
:> Tom St Denis <[EMAIL PROTECTED]> wrote:
:> : "Joseph Ashwood" <[EMAIL PROTECTED]> wrote in message
:> :> In order to shift by X takes X clocks.
:>
:> : This is so wrong. I can shift a 512-bit register 211 bits in one cycle.
:> : (Just re-wire the outputs).
:>
:> You're talking about rewiring a P4?
:>
:> Are you going to do this while it's running? ;-)
: You're kidding right?
Thus the smiley - but you *did* seem to be suggesting rewiring a P4 -
not a terribly practical task regardless of whether it is running or not.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
From: [EMAIL PROTECTED]
Date: 07 Jun 2001 08:01:31 -0400
Tim Tyler <[EMAIL PROTECTED]> writes:
>
> ``The bijective arithmetic encoder produces an intermediate representation
> called a finitely odd stream -- it is an infinitely long sequence of
> bits, but with the last 1 bit at a position finitely far from the
> beginning, i.e., it is a finite sequence of 0s and 1s, followed by an
> infinite sequence of 0s. [...]
Complete red herring; in the material you posted, that ``infinite
sequence of 0s'' is not used for anything.
> ``...Because the finitely odd stream is infinitely long, and all
> bits are significant to the output...''
Actually, everything up to (but not including) the last 1 bit is
all you need--the rest can be reconstructed from the definition of a
``finitely odd stream''. Namely, ``after that comes a 1 and then 0s all
the way.'' Anyway, what comes later demonstrates that the ``infinitely
many zeros'' aren't actually doing anything:
> ``David Scott provided the idea of encrypting all but the final 1 bit
> in this stream, possibly using overlapping blocks at the end.''
This is the part that actually means something. In lieu of padding,
you encrypt the whole blocks in the message, and then encrypt the final
(blocksizeX8) bits at the end. Which is fine, although I don't know
offhand why that would be better or worse than padding those last bytes
out to a full block, and encrypting the result.
> ``The result is that all significant bits of the file are encrypted,
> with no known or biased plaintext.''
Part of the original plaintext message might be known. So the statement
``no known...plaintext'' can mean only one of two things. Either (1) the
compressor ADDS no known plaintext, beyond what was already there, or
(2) the compressor OBSCURES plaintext which was already there--i.e., it
offers some sort of diffusion property.
Len.
--
Frugal Tip #19:
Discover the secret to happiness, then sell the franchise rights.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: Thu, 07 Jun 2001 14:01:06 +0200
Tim Tyler wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> : Tim Tyler wrote:
>
> :> Consider BICOM for example. It can map a 8 bit cyphertext to
> :> one of some 2^128 plaintexts - considerably more than your figure of 2^8.
>
> : There are in total 2^8 possible ciphertexts.
>
> You were talking about a *particular* 8 bit cyphertext, of which there was
> one, not 2^8
>
> There are *many* more than 2^8 possible cyphertexts altogether.
Sorry, I still don't understand. How could there be more
than 2^8 possible ciphertexts of length 8 bits? (The
formula of combinatorics gives 2^8, isn't it?)
>
> : What is the cardinality of the set of plaintexts that correspond to them?
>
> Well you don't /really/ want to know that, but...
>
> The size of the set of plaintexts that could correspond to
> 2^8 cyphertexts them in some cyphersystems can be calculated by:
>
> How many possible plaintexts are there in your whole system?
>
> How many can be represented by your key? Multiply that by 2^8
> (for the number of different cyphertexts you asked me to consider).
>
> Take the smaller of these two figures, and you have my reply.
What if my key is 8 bits? I am confused.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: Thu, 07 Jun 2001 14:00:57 +0200
JPeschel wrote:
>
> [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
[snip]
> Point me to where Shannon says that the length of the plaintext
> must be kept secret.
After dabating with David Scott and in particular with
Tim Tyler, I posted a view point (stated in a response
to Tyler) which I hope would quite well fit all aspects.
(Currently Scott negates that though. I am awaiting his
counter-argument.)
Let me explain in some detail my view point. An encrypted
message Y, on arrival in the hand of the opponent, has a
'concrete' form. It has a bit pattern and also a length,
which in the case of OTP processing with xor is equal to
the length of the plaintext X that the sender has input
into his software. Trivailly, (note) X has ALSO a concrete
form. We consider our X to be the original, i.e. the
ASCII text that the sender has actually written down
manually. Shannon's argument guarantees in this case that
the opponent's knowledge about X is not enhanced by his
having 'in addition' a corresponding Y. Now consider
carefully what this actually claims. Note that the
term 'his knowldege about X' is dependent on the very
'existence' of X. Before X comes into being, 'his
knowledge about X' is not well-defined (excepting
perhaps the 'idea' of its non-existence). After X comes
into being, the opponent's a-priori knowledge of X
(now that we can talk about X) 'can' include the size of
X. (See the example further below.) The theory says that
his a-posteriori knowledge, namely with Y in addition,
is no greater. One can however reduce that a-priori
knowledge through varying the size of X, i.e. through
somehow transforming X to X_1 (reversibly, in effect
doing a superencipherment step) such that the size of
X_1 is now random (within a range that is feasible, of
course) and send with OTP processing the corresponding
Y_1. Shannon's argument again applies, now concerning
the pair X_1 and Y_1. But the 'a-priori knowldege of
the opponent' (and with it his a-posteriori knowldege,
of course) gets changed. For now, in lieu of the length
of the original ASCII text, he has a random value which
is no information for him.
Note the difference in the two cases lies in the size
of X and X_1. If that size is independent of the content,
which is apparently true in many practical cases where
the length of messages is (in some very rough sense)
'random', this 'randomizing' of the size as described
above is unessential. But there could be cases that the
size plays a role. To illustrate, let's consider a
hypothetical case where among the messages communicated
between a company A and a company B there is a particular
class of messages that always has a fixed length,
because it is a routine purchasing order that the manager
of A makes through filling a form (nowadays commonly in
a window on his computer) and sends. Let's say that
the other messages between A and B are all of varying
lengths, e.g. diverse business letters etc. etc. Now the
opponent can simply count the number of messages of the
said fixed length and know how many orders A has placed
with B, isn't it? One might say that this belongs to
traffic analysis and not encryption proper, but anyway
information is still information. Through randomizing
the size of the messages we make it difficult for the
opponent to gain that information. This constructed
example is certainly not very good, but I hope that the
idea is nonetheless clear. There is in particular no
conflict with Shannon's argument througout the above.
Certainly I don't exclude that there are logical
deficiencies in the above, maybe even fatal ones. I
should be satisfied, however, if it could help elicit
eventually really good and satisfactory explanation of
the issues involved.
M. K. Shen
==============================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: Thu, 07 Jun 2001 14:01:18 +0200
Tim Tyler wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> : Meanwhile I believe that the following is correct about
> : the issue: The OTP processing only guarantees that the
> : particular work that is performed doesn't give the opponent
> : any (more) information.
>
> The opponent knows more about the plaintext after observing the
> cyphertext than he knew before he saw it - namely the length.
>
> The violates perfect secrecy.
>
> : It doesn't exclude however the existence of other processing
> : that could reduce the information that he could otherwise
> : have about the message. As a special example, if any
> : message is sent from my home, the opponent knows that
> : some person is present there (or at least someone has
> : programmed my computer to undertake that action) at
> : the particular time point. (That could mean under
> : circumstances quite a lot, e.g. when for months no
> : message had ever been sent.) No encryption
> : scheme, however 'perfect', could deprive him from
> : obtaining that knowledge. On the other hand, I could
> : manage to send the message from another place, in which
> : case he wouldn't have that information. Thus in a sense
> : the word 'perfect' in 'perfect security' is only to be
> : understood as one of terminology (definition) only and
> : does not have the common connotation of 'perfection'
> : (the ideal, the absolute best).
>
> Traffic analysis information is indeed often present -
> but we are talking about once a message exists, does
> the attacker gain anything by looking at the cyphertext.
>
> That's what the definition of "perfect secrecy" talks about.
>
> Perfect secrecy applies to encryption devices. Time of
> message transmission etc is considered to be outside its scope.
>
> A conventional OTP, that preserves message length and is
> asked to deal with variable length messages does *not*
> have Shannon's perfect secrecy property.
I am not of the opinion that size is 'inherently' different
from time etc. in the present context.
In a follow-up to Joe Peschel (just posted) I have presented
my previous view point in some more detail. You might
criticize that. I hope we could further discuss.
M. K. Shen
------------------------------
** 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
******************************
