Cryptography-Digest Digest #515, Volume #14 Mon, 4 Jun 01 14:13:00 EDT
Contents:
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler)
Re: Def'n of bijection (Anton Stiglic)
Re: Def'n of bijection (Tim Tyler)
Re: National Security Nightmare? ("Douglas A. Gwyn")
Re: National Security Nightmare? ("Douglas A. Gwyn")
Re: Def'n of bijection ("Douglas A. Gwyn")
Re: Best, Strongest Algorithm (gone from any reasonable topic) ("Tom St Denis")
Re: Best, Strongest Algorithm (gone from any reasonable topic) ("Tom St Denis")
Re: Best, Strongest Algorithm (gone from any reasonable topic) ("Tom St Denis")
Re: Best, Strongest Algorithm (gone from any reasonable topic) ("Tom St Denis")
Re: Best, Strongest Algorithm (gone from any reasonable topic) ("Tom St Denis")
Re: Sv: Top Secret Crypto ("Douglas A. Gwyn")
----------------------------------------------------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Reply-To: [EMAIL PROTECTED]
Date: Mon, 4 Jun 2001 16:11:11 GMT
I, Tim Tyler <[EMAIL PROTECTED]> wrote:
: I read an rather eloquent defense of counter mode not very long ago:
: http://www.cs.berkeley.edu/~daw/papers/ctr-aes00.ps
: ``Comments to NIST Concerning AES-modes of Operations: CTR-mode Encryption''
: - Helger Lipmaa, Phillip Rogaway, and David Wagner''
They say something else which seems open to debate as well - though it
strengthens their overall case, rather than weakening it.
Under a section entitled:
"Perceived disadvantages of CTR mode" they say:
``Successive blocks ctr and ctr + 1 usually have small Hamming
difference. This has lead to the concern that an attacker can
obtain many plaintext pairs with a known small plaintext difference,
which would facilitate the differential cryptanalysis. However, this
concern is only valid if the underlying cipher is differentially
weak. It is not the responsibility of a mode of operation to try to
compensate (likely without success) for weaknesses in the underlying
block cipher; this concern should be addressed when designing the block
cipher.''
Fair enough. However, ISTM that here a case is being made for relying on
the underlying block cypher where it is not necessary to do so.
A maximal period counter does not need to work by repeatedly adding 1 -
there are other types of counter that work just as well.
LFSRs are one candidate - probably a far superior condidate if you know
you're going to be in hardware.
Also, all the relevant properties of a "+1" arithmetic counter appear to
be present in a "+n" counter where n is relatively prime to the size of
the counter.
A "+n" counter with a reasonable spread of set bits in n avoids the low
Hamming distance issue.
Since you can use a counter which avoids the possible stigmata of all the
high bits remaining fixed 99% of the time - and this has practically no
cost - I see no good reason to shy away from doing so.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Def'n of bijection
Date: Mon, 04 Jun 2001 12:20:43 -0400
Yes. One property that does hold is that the cardinality of the
sets are equal for finite sets. For sets with infinite many elements,
other properties hold (like you can't have a bijection between an
infinite enumerable set and an infinite non-enumerable set, like
between the set of all natural numbers |N and that of the real
numbers |R).
--Anton
[EMAIL PROTECTED] wrote:
>
> [EMAIL PROTECTED] (John Savard) writes:
> > <[EMAIL PROTECTED]> wrote, in part:
> >> Correct me if i am wrong but the whole point of the BICOM stuff was
> >> that all inputs map to an output and all elements on the output side
> >> map to an input.
> >
> > The point is, though, that in a bijection, the domain need not equal
> > the range.
>
> Right--in other words, they need not be the same set. So Tom, you were
> abusing the equals sign when you said ``...from set A to set B, A=B?''
>
> Of course, in most discussions one remarks something like, ``From now on,
> we won't bother to distinguish set A from it's image under the bijection.''
> After making that remark, you've given yourself permission to abuse the
> equals sign (or the subset symbol, in the case of an injection).
>
> Tom, a bijection is also known as a ``one-to-one correspondence''. All a
> bijection really establishes is that two sets have the same cardinality.
>
> Len.
>
> --
> We neglected the Noah principle: predicting rain doesn't count, building
> arks does.
> -- Warren Buffett, 1981
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Def'n of bijection
Reply-To: [EMAIL PROTECTED]
Date: Mon, 4 Jun 2001 16:32:16 GMT
SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
: see.signature (Nicol So) wrote in <[EMAIL PROTECTED]>:
:>Tom St Denis wrote:
:>> That means it's invertible and closed right (i.e from set A to set B,
:>> A=B)?
:>
:>Invertible? yes. Domain = range? No.
: Tommy in in his weasel mode. He knows perfectly well what
: bijections are. [...]
If so, it beats me how he managed to write:
"A bijection is where the domain and range are the same set."
On a different (but related) subject: is it just me - or are
the terms "expansion permutation" and "compression permutation"
verging on literally being contradiction-in-terms?
Permutations are bijections where the domain *does* equal the range.
The whole idea of "expansion permutations" and "compression permutations"
is that the domain and range are of different sizes.
Shouldn't these be called "expansion bijections" and
"compression bijections" - or some such...? ;-)
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: National Security Nightmare?
Date: Mon, 4 Jun 2001 16:51:40 GMT
> Ahh, yes, FOIA: ...
It's still your best available option. Unfortunately, a lot of
FIOA office staff work has had to go into researching trash like
UFO references. That is now somewhat under control, so perhaps
response time will improve. If undue delays keep resulting in
court actions and complaints to Congressmen, one would expect
that more resources will be directed toward this function.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: National Security Nightmare?
Date: Mon, 4 Jun 2001 16:47:41 GMT
David Wagner wrote:
> There is no reason that the latest executive orders couldn't include
> the clear language found in EO 11905. Moreover, it seems that the NSA
> could easily publish excerpts from its training manuals to substantiate
> claims that employees are instructed to treat civil liberties seriously.
There is little if any incentive for any employee to take initiative
when the job description doesn't require it. That's why I suggested
using FOIA to obtain information that otherwise would remain
releasable but unreleased.
> If electronic surveillance is so critical to national security, why can't
> the intelligence agencies spare 0.1% of their budget to openness and and
> transparency? One is led to the impression that this is not a priority
> for the intelligence community. It seems that the intelligence community
> has not taken any of these easy, no-cost, confidence-inspiring steps.
> Should anyone be surprised if people view this as an indication that
> maybe the intelligence community doesn't care about civil liberties as
> much as it should?
The "community" is actually a collection of individuals with certain
common characteristics, not a single entity with a single voice.
What transpires at the "public policy" level is controlled by a small
handful of people, who have their own set of priorities, in many cases
largely reactive to pressure by Congress (which controls the budget).
Therefore another approach to getting more reassurance is to petition
your Congressman, especially if he's on an intell. oversight committee.
> ... I'm disappointed that the stewards of our intelligence agencies
> do not seem to be taking this as seriously as they (IMHO) should be.
General Hayden has already done much more than previous DIRNSAs to
open up the Agency's operation to the general public, and if you
address your request for more to him and his staff it would do a lot
more good than complaining to me and other readers of this newsgroup.
I am sure that Gen. Hayden understands that it is not in the nation's
best interest for its citzenry to hold widespread paranoid
misconceptions about IC activities.
I personally think it would be best for the Agency to promote a PR
policy that invests substantial resources into making as much
information available as is consistent with national security
requirements. Unfortunately, a lot of decisions are made by Boards
consisting primarily of old Cold Warriors, who have a long-entrenched
attitude of making as little information available as possible. There
are other, more important problems for (and with) Agency management
than this one, however, so the shift in "openness" will be gradual,
due to not getting the attention that it might if everything were
otherwise in good shape.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Def'n of bijection
Date: Mon, 4 Jun 2001 16:58:23 GMT
John Savard wrote:
> On Mon, 04 Jun 2001 02:58:38 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
> wrote, in part:
> >The point about D.Scott's style of bijection is that it maps
> >an infinite discrete set into itself, but with infinite sets
> >you need to avoid applying intuition learned from experience
> >with finite sets. It has *very* different properties from,
> >say, a bijection of 128 bits onto 128 bits.
> True. But I don't think Mr. Scott is the one committing the fallacy
> here. His bijection _is_ a bijection, it's just that it doesn't map
> the set of "files up to n bytes long" to the set of "files up to n
> bytes long" at any point along the way. Which is entirely OK; it's
> saying that prevents the infinite set from mapping to itself which
> would be a fallacy.
Note, I was agreeing with D.Scott and disagreeing with Tom St. Denis.
Otherwise, what you say is correct and relevant.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: Mon, 04 Jun 2001 17:41:23 GMT
"Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Tom St Denis <[EMAIL PROTECTED]> wrote:
>
> : "Tim Tyler" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> :> Tom St Denis <[EMAIL PROTECTED]> wrote:
> :> : "Tim Tyler" <[EMAIL PROTECTED]> wrote in message
> : news:[EMAIL PROTECTED]...
> :> :> Roger Fleming <[EMAIL PROTECTED]> wrote:
> :> :> : [EMAIL PROTECTED] wrote:
>
> :> That was an example of how to do it simply - not an example of how
> :> to do it efficiently. Getting diffusion across a whole key is not
> :> rocket science - but it /can/ be computationally expensive, relative
> :> to the effort necessary with smaller keys.
>
> : If you're not discussing how todo it efficiently there is no point now
is
> : there?
>
> Efficiency is generally low on my list of priorities. Security is often
> near the top. I'm a believer in Knuth's "premature optimisation is the
> root of all evil" dictum.
I will let you in on a secret (#1) I learnt the hardway. in most security
companies actual theoretic security is not #1 on their list of priorities.
Here is secret #2. Most companies don't care what you think. They want to
check the boxes to sell a product.
>
> :> :> Hmm. This is what I was afraid of. Trusting that one's cypher's
won't
> :> :> be broken is not something that everyone is prepared to do.
>
> :> Anyway, trusting that one's cypher's won't be broken is not something
that
> :> everyone is prepared to do - and the mere possibility of things like
> :> quantum computers being built in secret to crack AES messages rapidly
will
> :> be enough to deter some people from using it.
>
> : That's a bogus arguement and you know it. [...]
>
> I'm defending the thesis that "Trusting that one's cypher's won't
> be broken is not something that everyone is prepared to do". This
> appears to me to be a true statement.
>
> : Provided QC actually comes to exist in a state to solve such problems,
> : so few people will have access to it that it won't matter.
>
> Hmm - I don't buy the ideas expressed there.
>
> I'd put myself down as quite a Quantum Computation sceptic - but I
> don't think it's obviously going to be out of the question for
> government organisations - and I definitely don't think that
> a cypher-cracker owned a the government "doesn't matter".
You're going down the route thinking the govt actually cares about you. How
foolish. Remember you live in a country with 300 million others (I assume
you're from the states... forgive me if you're not). Even assuming the govt
has super QC computers, chances are next to null they will use it against
you.
Secret #3. The govt is not out to get you.
Secret #4. The ones out to get you are criminals after your money.
Criminals probably won't have access to QCs any time soon.
> : Besides using this arugment against you, I don't want to use *your*
cipher
> : because QC will break it too. [...]
>
> I'm sure that if an AES cracker could be built along these lines, then
> something similar would work on other similar systems. However, there's a
> question of economics to consider:
>
> Today there's a DES-cracker - but if you use some obscure variant of DES
> (that is not in theory any more secure) your messages will be /much/
> harder to crack - because you can't simply plug your message into the
> existing DES cracker and turn the handle - you may have to build a whole
> new machine.
>
> This may be "securtiy through obscurity" - but that's not necessarily to
> be sneezed at. To quote BS from AC (p.301):
>
> ``Almost any change to DES will be more annoying; maybe the resultant
> cypher will be easier to break, but the NSA might not have the resources
> to devote to the problem.''
Secret #5. If you research things you will learn.
Look up Eli's papers on how to strengthen existing implementations of DES.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: Mon, 04 Jun 2001 17:45:05 GMT
"Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> : "Tim Tyler" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> :> : But an OTP is provably secure so your question is moot.
> :>
> :> Actually, if you use an OTP in the same way that you use CTR mode -
> :> i.e. you chop off any cyphertext beyond the end of the message -
> :> the cyphertext in an OTP system leaks length information about the
> :> plaintext - and consequently fails to have Shannon's "perfect
> :> secrecy" property.
>
> : "Chop off any cyphertext beyond the end"?
>
> : What does that mean?
>
> i.e. length of cyphertext = length of plaintext message.
What's your point? This just makses sense. I don't want my 4kb message
turning into 100kb.
> i.e. algorithm: XOR message with encrypted counter and stop when you reach
> the end of the plaintext.
This isn't an OTP.
> : I hate to burst your bubble but an OTP is provably
> : secure so you might as well not argue this with me.
>
> It /doesn't/ have the perfect secrecy property if you use it in the way
> that counter mode is commonly used when encrypting files.
That's not an OTP either.
> If used in such a way it leaks information about the length of the
> plaintext.
So what? I know that 45893475893475893475378893573895 is an n-digit
composite, but I don't know the factors...
Knowing the length or cardinality of a challenge rarely leads to a solution.
> If you're taling about some /other/ sort of use of CTR mode, then perhaps
> you need to describe in more detail the implementation you're talking
> about. This is probably why David complained that "you have no working
> program".
The CTR mode is as secure as the block cipher upto the 2^n/2 texts (n=block
size). This is provable too. (Note I don't say provably secure against all
attacks, I just say it's as secure as the block cipher).
Proof. Suppose you know the counter values but not the outputs. Suppose
given some ciphertext C you can determine with prob=1 what P is. Then you
can determine from the input and output of the cipher with prob 1.
Therefore, you have broken the cipher. QED (sorta).
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: Mon, 04 Jun 2001 17:45:50 GMT
"Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> : "Tim Tyler" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> :> Tom St Denis <[EMAIL PROTECTED]> wrote:
> :> : "Tim Tyler" <[EMAIL PROTECTED]> wrote in message
>
> [BICOM vs Rijndael in CTR mode]
>
> :> :> He explained it - you just didn't understand the explanation.
> :>
> :> : What explanation? All he does is flame me.
> :>
> :> This sort of thing, repeated several times now:
> :>
> :> DS> And you never anwsered the FACT that a one byte ouput file
> :> DS> from CTR mode (though you have no working program) would imediately
> :> DS> lead an attacker to realize that the input file could only have
> :> DS> come from 1 of 256 possible messages. With BICOM you have many
> :> DS> many more messages. That alone makes it more secure.
>
> [snip]
>
> : His logic is flawed. He states a feature of BICOM then assumes its a
> : security bonus.
>
> Knowledge that a message comes from a set of billions of possible key
> selected messages, rather than a set of 256 possible key selected messages
> *is* a feature that has an immediate impact on security.
>
> If you can narrow the plaintext down to one of 256 possibilities, then
> that is already a significant leak of information about the message
> contents.
OTP encrypted message.
C=1101111010001
What is P?
(How long must this go on?)
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: Mon, 04 Jun 2001 17:46:57 GMT
"Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
>
> : His mind as captured some words from one of his crypto gods that CTR is
> : provably sercure. [...]
>
> I read an rather eloquent defense of counter mode not very long ago:
> http://www.cs.berkeley.edu/~daw/papers/ctr-aes00.ps
>
> ``Comments to NIST Concerning AES-modes of Operations: CTR-mode
Encryption''
> - Helger Lipmaa, Phillip Rogaway, and David Wagner''
>
> It formalises the 1-byte message -> 1-byte cyphertext idea by saying:
>
> ``Messages of arbitrary bit�length. Unlike other common modes of
> operation, handling messages of arbitrary bit� length is made
> trivial. No bits are wasted in doing this---the ciphertext C is
> of the same length as the plaintext M''.
>
> It also claims security:
>
> ``In fact the standard cryptographic assumption about a block cypher's
> security [...] is enough to prove the security of CTR mode encryption''.
>
> I can only guess that they think that a message only having 256 possible
> decrypts is considered acceptable :-(
Why do you think that's a problem? If you can't tell a byte from random
it's provably secure. I.e if the prob of the output is exactly 1/256 what
advantage do you have?
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: Mon, 04 Jun 2001 17:48:16 GMT
"Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> I, Tim Tyler <[EMAIL PROTECTED]> wrote:
>
> : I read an rather eloquent defense of counter mode not very long ago:
> : http://www.cs.berkeley.edu/~daw/papers/ctr-aes00.ps
>
> : ``Comments to NIST Concerning AES-modes of Operations: CTR-mode
Encryption''
> : - Helger Lipmaa, Phillip Rogaway, and David Wagner''
>
> They say something else which seems open to debate as well - though it
> strengthens their overall case, rather than weakening it.
>
> Under a section entitled:
>
> "Perceived disadvantages of CTR mode" they say:
>
> ``Successive blocks ctr and ctr + 1 usually have small Hamming
> difference. This has lead to the concern that an attacker can
> obtain many plaintext pairs with a known small plaintext difference,
> which would facilitate the differential cryptanalysis. However, this
> concern is only valid if the underlying cipher is differentially
> weak. It is not the responsibility of a mode of operation to try to
> compensate (likely without success) for weaknesses in the underlying
> block cipher; this concern should be addressed when designing the block
> cipher.''
>
> Fair enough. However, ISTM that here a case is being made for relying on
> the underlying block cypher where it is not necessary to do so.
>
> A maximal period counter does not need to work by repeatedly adding 1 -
> there are other types of counter that work just as well.
>
> LFSRs are one candidate - probably a far superior condidate if you know
> you're going to be in hardware.
>
> Also, all the relevant properties of a "+1" arithmetic counter appear to
> be present in a "+n" counter where n is relatively prime to the size of
> the counter.
>
> A "+n" counter with a reasonable spread of set bits in n avoids the low
> Hamming distance issue.
>
> Since you can use a counter which avoids the possible stigmata of all the
> high bits remaining fixed 99% of the time - and this has practically no
> cost - I see no good reason to shy away from doing so.
Because if the cipher is any good a change in any bit should have drastic
confusing consequences. Seriously Tim may I suggest you do some research
before posting? I know I've zinged myself a few times but at least I try!
Tom
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Sv: Top Secret Crypto
Date: Mon, 4 Jun 2001 17:20:43 GMT
Peter Nielsen wrote:
> I have read this in the instruction to the program. What is your opinion
> about this ?. That is what have convinced me that it is a good program.
There is no real innovation there; these ideas are quite
well known among cryptologists. Some relevant facts that
were not mentioned include:
(1) Using a true OTP creates a significant problem in
distributing key material to the communicating parties.
If this weren't so, then most cryptosystems would have
been OTP systems long ago.
(2) Resistance to brute-force key search is necessary
but not sufficient.
(3) Whether or not moderately large keys (a few Kbits)
provide much security depends on many factors; for
example, without further precautions, it does not
protect against a "known plaintext" attack. If the 3
PRNGs have somewhat simple structures and are combined
in a somewhat simple way, it is quite possible that a
"ciphertext only" attack can succeed, if enough cipher
data is available.
------------------------------
** 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
******************************
