Cryptography-Digest Digest #536, Volume #14 Wed, 6 Jun 01 14:13:01 EDT
Contents:
AES question ("ajd")
Re: function notation (injection, bijection, etc..) one last time ("Douglas A. Gwyn")
Re: Def'n of bijection (Tim Tyler)
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler)
Re: AES question (Mok-Kong Shen)
Re: Def'n of bijection ("Douglas A. Gwyn")
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Mok-Kong Shen)
Re: Def'n of bijection (Mok-Kong Shen)
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler)
Re: Knapsack security??? Ah....huh (Al)
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Mok-Kong Shen)
Re: Factoring via BBS cycle length (Anton Stiglic)
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler)
Re: practical birthday paradox issues ("Dirk Bruere")
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler)
----------------------------------------------------------------------------
From: "ajd" <[EMAIL PROTECTED]>
Subject: AES question
Date: Wed, 6 Jun 2001 17:14:47 +0100
Hi All,
I was wandering about the algorithms that were nominated for the Advanced
Encryption Standard, it seems obvious that Rijndael will be used a lot as it
is the replacement for 3DES, but what about the other finalists. Does anyone
know of any companies using TwoFish, RC6, Mars, or Serpent in products.
Would they be used in addition to or instead of the older algorithms like
IDEA, RC4, RC5 etc.
thanks
andrew
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: function notation (injection, bijection, etc..) one last time
Date: Wed, 6 Jun 2001 15:55:53 GMT
[EMAIL PROTECTED] wrote:
> No offense, but these are the first terms a person *ever* learns when
> studying about functions. Their definitions are *not* subject to debate,
> and they are almost always stated in exactly the same way. ...
Len gave a nice summary of the standard definitions.
Part of the problem seems to be that *learning* requires more than
mere memorization of standard definitions. For example, the standard
approach is unnecessarily asymmetric in use of A and B; a more general
development would define a "relation" as a specific set of ordered
pairs (a,b) with a in A and b in B, and a function as a relation that
has additional constraints; with such an approach, A would not be the
domain of the function, but the analogue in the input set of the
concept of codomain, i.e. a set that contains the domain. Definitions
would have to be adjusted to fit this new model, and the fact that the
"domain" and "codomain" were not analogous would be worrisome. The
standard definitions evolved from originally less precise usage, and
exploring the history would show where the emphasis on certain aspects
came from.
> ... I believe that ``dual'' here really means ``dual'' in
> a category-theoretic sense, but it's been too long; ...
I think it's right. Diagrams somewhat like those used in category
theory often help the student to understand these concepts. It is
particularly useful to draw the sets as "clouds" and mark limits of
(simply connected) subsets, with arrows showing the mapping action
of the function from one cloud to another. (Note: the inhabitants
of separate clouds come from different planets and speak totally
different languages.) I would hope that there are textbooks that
do a good job of this, but from my experience with current public
education in math I have my doubts.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Def'n of bijection
Reply-To: [EMAIL PROTECTED]
Date: Wed, 6 Jun 2001 16:16:43 GMT
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
: [EMAIL PROTECTED] wrote:
:> And the idea doesn't even ``seem'' obvious, because of one fact you
:> keep ignoring: even if BICOM gives a bijection of binary files to
:> itself, almost all preimages under BICOM are not in fact plausible
:> messages. There is no a priori reason to believe that potential
:> decrypts will be rich in plausible messages; indeed it seems rather
:> unlikely.
: It *is* unlikely. [...]
However there are *excellent* reasons for thinking that potential decrypts
will be richer in plausble messages than they would be if compression had
not been employed. That is what was actually claimed.
Compression *increases* the probability that decrypting will yield a
plausible looking message.
The messages that the compressor compresses will get smaller,
while other files are made larger. As a direct consequence of
this, the proportion of files of any given size that decompress to
plausible-looking messages increases.
This assumes that the plausible messages are in the set that the
compressor compresses, of course. If this is not true, then the
compressor would be better described as an "expander".
: General-purpose compressors don't
: "prefer" one possible plaintext over another.
They compress some sorts of messages while expanding others.
Different kinds of plaintext may require different types of compressor
to get the best results.
--
__________
|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: Wed, 6 Jun 2001 16:23:12 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
: My problem is more with your citation about the length
: of OTP. My understanding hithertofore is that OTP is
: supposed to be a very long bit sequence that is securely
: transported to the communication partner and used
: in sequential order (one part after another) for many
: messages irrespective of their length. If that sequence
: is used up, the partner has to be supplied with a new
: sequence. So both (fairly) long and short messages could
: be sent securely (if the OTP is from an ideal source)
: and the length of them has no implication about the
: security of using OTP (unless there are other factors
: that link the length to the content of the messages).
The question under discussion is whether such usage exhibits
Shannon's perfect secrecy - a property that is often associated
with an OTP.
It doesn't - since cyphertexts contain information about the plaintexts,
which violates the conditions required for perfect secrecy.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: AES question
Date: Wed, 06 Jun 2001 18:29:05 +0200
ajd wrote:
>
> I was wandering about the algorithms that were nominated for the Advanced
> Encryption Standard, it seems obvious that Rijndael will be used a lot as it
> is the replacement for 3DES, but what about the other finalists. Does anyone
> know of any companies using TwoFish, RC6, Mars, or Serpent in products.
> Would they be used in addition to or instead of the older algorithms like
> IDEA, RC4, RC5 etc.
I suppose that your questions are yet premature. It
appears to be yet unknown whether AES has already been
applied in practice in extents worthy of special mention.
M. K. Shen
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Def'n of bijection
Date: Wed, 6 Jun 2001 16:27:26 GMT
Mok-Kong Shen wrote:
> There is the term 'apriori probability of a message'.
> Basically I am wondering whether it is 'practically'
> feasible at all to determine that quantity.
Even an a priori probability is still contextual, i.e.
its assigned value depends on what you know a priori.
> ... he can hardly know the probability of a new message.
When one is considering the assignment of values it is
almost always better to think in terms of likelihoods
rather than probabilities. Probabilities are appropriate
for exact (statistical) parameters of models. The
difference between likelihood and probability is somewhat
controversial, but is pretty well understood by Bayesians.
It is *always* the case that there is theoretically an
a priori likelihood; in the case that one has absolutely
no information about it, every possible outcome is
equally likely. Once one has information, all of it
must be factored into the computation of likelihoods.
I.J. Good explains this rather well in some of his articles.
If one has a priori knowledge (or properly weighted
expectation) that the plaintext comes from a source
with known characteristics, e.g. telegraphic English,
then with no additional information at hand, correct
a priori likelihoods would be the corresponding
probabilities computed from the source statistics.
There is an associated issue, namely: How does one assign
likelihoods (probability estimates) for possible events
that have never yet been observed? (Or, with N samples,
should a single occurrence really be assigned likelihood
1/N?) The first practical solution to this was devised
by Turing at B.P. and was eventually published by Good
in a context as far removed from cryptology as possible
(Biometrika, 1953). There have been further developments
since then, but the Good-Turing estimation method is still
quite useful.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: Wed, 06 Jun 2001 18:51:13 +0200
Tim Tyler wrote:
>
> The question under discussion is whether such usage exhibits
> Shannon's perfect secrecy - a property that is often associated
> with an OTP.
>
> It doesn't - since cyphertexts contain information about the plaintexts,
> which violates the conditions required for perfect secrecy.
I must admit that I haven't followed this thread in detail,
hence I evidently have context problems. Does 'such use'
refer to sending both short and long messages or something
else? You probably question whether such usage leads to
Shannon's perfect security which, as you said, is claimed
to be a property of OTP. However, I don't see where in the
literature about OTP (in connection with perfect security)
the length enters into the argumentation, i.e. plays a role
in the proof. My memory of Shannon's paper is no good,
but I don't think that he considered the length of the
messages. Could you refer me to papers or books about that?
Thanks.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Def'n of bijection
Date: Wed, 06 Jun 2001 19:02:36 +0200
"Douglas A. Gwyn" wrote:
>
> Mok-Kong Shen wrote:
> > There is the term 'apriori probability of a message'.
> > Basically I am wondering whether it is 'practically'
> > feasible at all to determine that quantity.
>
> Even an a priori probability is still contextual, i.e.
> its assigned value depends on what you know a priori.
>
> > ... he can hardly know the probability of a new message.
>
> When one is considering the assignment of values it is
> almost always better to think in terms of likelihoods
> rather than probabilities. Probabilities are appropriate
> for exact (statistical) parameters of models. The
> difference between likelihood and probability is somewhat
> controversial, but is pretty well understood by Bayesians.
>
> It is *always* the case that there is theoretically an
> a priori likelihood; in the case that one has absolutely
> no information about it, every possible outcome is
> equally likely. Once one has information, all of it
> must be factored into the computation of likelihoods.
> I.J. Good explains this rather well in some of his articles.
>
> If one has a priori knowledge (or properly weighted
> expectation) that the plaintext comes from a source
> with known characteristics, e.g. telegraphic English,
> then with no additional information at hand, correct
> a priori likelihoods would be the corresponding
> probabilities computed from the source statistics.
>
> There is an associated issue, namely: How does one assign
> likelihoods (probability estimates) for possible events
> that have never yet been observed? (Or, with N samples,
> should a single occurrence really be assigned likelihood
> 1/N?) The first practical solution to this was devised
> by Turing at B.P. and was eventually published by Good
> in a context as far removed from cryptology as possible
> (Biometrika, 1953). There have been further developments
> since then, but the Good-Turing estimation method is still
> quite useful.
That's all very respectable in a theoretical sense.
What I wonder is whether in a concrete case in practice,
i.e. for the opponent having in hand a bunch of
messages, he can assign any (concrete) probability or
likelihood values to the individual messages, without
invoking wild speculations or doing similar things.
M. K. Shen
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Reply-To: [EMAIL PROTECTED]
Date: Wed, 6 Jun 2001 17:02:36 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> The question under discussion is whether such usage exhibits
:> Shannon's perfect secrecy - a property that is often associated
:> with an OTP.
:>
:> It doesn't - since cyphertexts contain information about the plaintexts,
:> which violates the conditions required for perfect secrecy.
: I must admit that I haven't followed this thread in detail,
: hence I evidently have context problems. Does 'such use'
: refer to sending both short and long messages or something
: else?
I referred to your own description of a pad-based system.
Yes, the main feature that I was referring to was sending
variable-size messages with it.
: You probably question whether such usage leads to
: Shannon's perfect security which, as you said, is claimed
: to be a property of OTP. However, I don't see where in the
: literature about OTP (in connection with perfect security)
: the length enters into the argumentation, i.e. plays a role
: in the proof.
I also think that it's not mentioned. I beleive it is common to
consider the domain where all plaintexts are the same length -
perhaps in order to get the "perfect secrecy" result.
: My memory of Shannon's paper is no good, but I don't think that he
: considered the length of the messages.
I don't think it was mentioned either - all the messages were the same
length in the system in question.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: [EMAIL PROTECTED] (Al)
Subject: Re: Knapsack security??? Ah....huh
Date: 6 Jun 2001 10:14:08 -0700
Subset sum systems with density >=1 are computationaly secure but no
one can firmly say if they are theoretically so.
eg
S[i]=(RandomNumber[i] OR 1)*(2^i)+(X[i])A+(Y[i])B (Always n bits
ie(mod 2(^n))
0<=i<n
A permutation of set is published.
RandomNumber[i],Xi,A,,Yi,B, chaff & permuation are private and are
such that the diophantine component is < MA+NB where all combinations
of MA+NB can be brute forced relatively fast.
Any sums can be inversed by going thru all diophantine combinations
and checking from bit 0 where bits are on and subtracting random
component.
Since no solution are multiple solutions is possible,signing is more
complex but can be used for software authentication where the signer
can pick a variant of the name to be signed that has a checksum at end
or is always ASCII, or a certain format. This is inverted and the
result published, only the signer that created the subset could do
that.
If signing only chaff random numbers can be published which are never
used to increase density. Or multiple subsets of chaff can add to 0 if
used.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: Wed, 06 Jun 2001 19:12:58 +0200
Tim Tyler wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
[snip]
> : You probably question whether such usage leads to
> : Shannon's perfect security which, as you said, is claimed
> : to be a property of OTP. However, I don't see where in the
> : literature about OTP (in connection with perfect security)
> : the length enters into the argumentation, i.e. plays a role
> : in the proof.
>
> I also think that it's not mentioned. I beleive it is common to
> consider the domain where all plaintexts are the same length -
> perhaps in order to get the "perfect secrecy" result.
>
> : My memory of Shannon's paper is no good, but I don't think that he
> : considered the length of the messages.
>
> I don't think it was mentioned either - all the messages were the same
> length in the system in question.
>From what you said, I don't think it is valid to consider
that the constant length of messages underlies the
proof of Shannon (unless one can demonstrate the
contrary).
M. K. Shen
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Factoring via BBS cycle length
Date: Wed, 06 Jun 2001 13:34:18 -0400
Tom St Denis wrote:
>
> I got bored in math class (intro algebra stuff... complex numbers
> etc...)
>
> And developped a neat algorithm.
>
> Let's suppose you have an unfactored BBS prime (blum integer) N and
> don't know the factors. You then guess some integer A such that A^2 =
> B, B^2 = A or in other words the period is two.
>
> We then can re-write this as
>
> A^2 = B
> A = B^2
How many such elements exist?
Hint, write it this way:
A^2 = A*A = B,
B^2 = (A*A)*(A*A),
B^2 = A => A*A*A*A = A,
so A^3 = 1, (if A is inversible)
so this means that A has order <= 3.
How many elements in your group have order <= 3?
How many elements are not inversible, so that the above
doesn't apply to them? What can you do with those?
--Anton
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Reply-To: [EMAIL PROTECTED]
Date: Wed, 6 Jun 2001 17:33:24 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
:> : You probably question whether such usage leads to
:> : Shannon's perfect security which, as you said, is claimed
:> : to be a property of OTP. However, I don't see where in the
:> : literature about OTP (in connection with perfect security)
:> : the length enters into the argumentation, i.e. plays a role
:> : in the proof.
:>
:> I also think that it's not mentioned. I beleive it is common to
:> consider the domain where all plaintexts are the same length -
:> perhaps in order to get the "perfect secrecy" result.
:>
:> : My memory of Shannon's paper is no good, but I don't think that he
:> : considered the length of the messages.
:>
:> I don't think it was mentioned either - all the messages were the same
:> length in the system in question.
: From what you said, I don't think it is valid to consider
: that the constant length of messages underlies the
: proof of Shannon (unless one can demonstrate the
: contrary).
Without such an assumption, there's no proof of perfect secrecy,
because the system doesn't exhibit it.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: "Dirk Bruere" <[EMAIL PROTECTED]>
Subject: Re: practical birthday paradox issues
Date: Wed, 6 Jun 2001 18:50:33 +0100
"Richard D. Latham" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "Dirk Bruere" <[EMAIL PROTECTED]> writes:
>
> >
> > One might make a guess at h/w capability given that the old WW2 custom
> > electromech system was roughly as powerful as a Pentium 100MHz.
> Surely you jest ?
No. Based on recently declassified Brit stuff being used at Bletchley Park
in WW2, namely things called 'bombes'.
http://www.bcs.org.uk/publicat/ebull/mar99/news.htm
>From the British Computer Society (above):
"The Bombe was an electro-mechanical device but so tuned to its one task
that a simulation on a modern PC takes 15 hours to do what a Bombe did in 15
minutes."
Similar detail from
http://www.privacy.nb.ca/cryptography/archives/cryptography/html/1998-07/007
9.html
> The WW2 custom electromech system probably wasn't nearly as powerful
> as the keyboard controller in the $10 keyboard attached to a 100Mhz
> Pentium.
The thing is, you are comparing a general purpose modern computer to highly
customised hardware.
I read somewhere that the situation is not as bad as the quotes would
suggest, but for the purposes of extrapolating cypher breaking h/w a rough
equivalence will be assumed.
So, assuming that modern circuitry is actually about 10^6 faster, a PC
complexity equivalent codebreaker would be that much more powerful. Add in
some cash for highly parallel computers and multiply again by 10^6.
How much you want to multiply again for better algorithms, h/w design etc is
a matter of taste.
Still, we are looking at an increase of a minimum of 10^12 over WW2
capability.
Dirk
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Reply-To: [EMAIL PROTECTED]
Date: Wed, 6 Jun 2001 18:01:10 GMT
Tim Tyler <[EMAIL PROTECTED]> wrote:
: Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
: : From what you said, I don't think it is valid to consider
: : that the constant length of messages underlies the
: : proof of Shannon (unless one can demonstrate the
: : contrary).
: Without such an assumption, there's no proof of perfect secrecy,
: because the system doesn't exhibit it.
I looked up what Bruce Schneier has to say about perfect secrecy in
A.C.
He says this:
``There is such a thing as a cryptosystem that achives perfect secrecy:
a cryptosystem in which the cyphertext tields no possible information
about the plaintext (except possibly its length).''
He goes on to give Shannon's theory that perfect secrecy is only possible
if the number of possible keys in the cryptosystem is equal to the number
of possible messages.
IMO, Shannon has it right - while Bruce seems a bit uncertain about
whether the length is included or not.
I suppose if Bruce isn't clear about the issue, that probably explains why
other folk are not clear about it either.
Certainly if you see a 1-byte cyphertext, you know that most possible
plaintexts have a probability of zero.
This means that an OTP that preserves length information does not conceal
plaintext information as well as is possible to do. If anyone has been
calling this is perfect secrecy, they really ought to consider the fact
that systems which better hide the identity of the plaintext are available.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
** 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
******************************
