Cryptography-Digest Digest #665, Volume #11 Sat, 29 Apr 00 21:13:00 EDT
Contents:
Re: What are SBoxes? (Tom St Denis)
Re: Janet and John learn about bits (was Re: Problems with OAP-L3) (Tom St Denis)
Re: sci.crypt think will be AES? (Jerry Coffin)
Re: sci.crypt think will be AES? (Jerry Coffin)
Re: Karatsuba threshold (Jerry Coffin)
Re: Vs: Vs: sci.crypt think will be AES? (David A. Wagner)
Re: new Echelon article (Diet NSA)
Re: combine hashfunctions (David Hopwood)
Re: AEES 16 rounds (David Hopwood)
----------------------------------------------------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: What are SBoxes?
Date: Sat, 29 Apr 2000 23:22:47 GMT
Monolo wrote:
>
> Stupid question, and I am sorry. What is an S-Box? I have seen it on several
> posts. Thanks!
>
> JJ
An sbox is just a subtitution box where something goes in and something
goes out. Typically you will see them refered to as "m by n" sboxes
which means m-bits go in, and n-bits come out. They normally form the
non-linear or Avalanche part of an algorithm. For example { 3, 0, 2, 1
} would be an 2 by 2 sbox because there are four entries (2^2 = 4) and
each output is 2 bits.
When you have an sbox where n is greater then m, you have an expansion
substitution (see Blowfish and CAST), when m is greater you have a
compression substitution (see DES and LOKI).
Rate of Avalanche refers to the rate (number of substitutions, or rounds
in a feistel structure) which must be performed before every bit of
plaintext (input) affects every other bit and vice versa. For DES (for
example) five rounds are required before this property is met. To help
ensure that this occurs quickly most sboxes conform to the Strict
Avalanche Criterion (SAC) which states (briefly) that when any single
input bit changes exactly half the output bits will change as well. For
example in a 8x8 sbox if you change one bit going in, 4 bits will change
comming out. This property is really usefull. If the bits that change
going out are non-uniform the sbox is essentially non-linear, but that's
another story.
I hope this helps (and for the rest of sci.crypt if I made a mistake
please let me know).
Tom
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Janet and John learn about bits (was Re: Problems with OAP-L3)
Date: Sat, 29 Apr 2000 23:27:04 GMT
Richard Heathfield wrote:
> unsigned char num[] = { 0x16, 0x30, 0x47, 0x91 }; /* binary coded
> decimal (almost!) - wastes 6 combinations per nybble */
>
> as opposed to
>
> unsigned char num[] - { 0xF8, 0xCA, 0x97 }; which is clearly more
> efficient, as it uses all the bits available to it.
>
> So perhaps we're in violent agreement?
No since not all combinations of 3 byte values are possible you are
still wasting space. That was my point.
>
> > > If we have two cryptography applications, one of which uses its memory
> > > efficiently, runs on my PII/400 at an acceptable speed, and offers me
> > > reliable security, and the other which doesn't use its memory
> > > efficiently, runs on my 400 MHz box at a speed which even its author
> > > says is far too slow, and is based on source code which has not been
> > > published and therefore has not had the chance to be validated by the
> > > cryptographic community - thus making its security untrustworthy - which
> > > application do you think anyone with a brain will buy?
> >
> > Or just use. Why do you have to buy good crypto programs?
>
> I agree entirely. Just roll your own...
>
> > If you have enough time on your hands you can even write your own.
>
> Ah, I don't have enough time on my hands. But I'm trying to write my own
> anyway <g>. Unfortunately, I'm too inexperienced in cryptanalysis to
> perform serious cryptanalytic attacks on my own code, let alone other
> people's. (I've cracked a couple of 'unbreakable' algorithms presented
> to me by other would-be cryptographers, but these were only 'kid-sister
> unbreakable', of course.)
Well it's one thing to take already developed and analyzed algorithms
and stick it together, and it's another thing *entirely* to invent your
own ciphers at the same time. If you want a 5kb file crypto program
just take RC4 and a hash (say md2) and write a small program (I have
done it more then once.... :)).
> >
> > Mr Szopa has some thinking todo about making his algorithm(s) not only
> > public but efficient.
> >
>
> Possibly, but that's not his main problem. He has some really serious
> thinking to do about his ability to deal with fellow professionals in a
> professional way. It seems that anyone who dares take issue with him is
> instantly killfiled - in a mysterious and magical process which allows
> Mr Szopa to read their posts anyway, presumably so that he can killfile
> them again, and again, and again.
>
> When he learns to talk to grown-ups as if they are grown-ups, I suspect
> he can look forward to some excellent help from the heavyweight computer
> scientists in this newsgroup (Doug Gwyn and so on) in making his
> algorithm efficient.
Well the pros are really turned off from him, so at best he will have to
deal with the-less-than-amateurish people like You and I....
Tom
--
Want your academic website listed on a free websearch engine? Then
please check out http://tomstdenis.n3.net/search.html, it's entirely
free
and there are no advertisements.
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: sci.crypt think will be AES?
Date: Sat, 29 Apr 2000 17:40:05 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
[ ... ]
> As a practical matter, you will have to goto court to enforce
> your patents. You will look very silly when you argue:
>
> 1. You applied for a patent because you thought you had
> something new and unique, and yet you cannot easily recognize
> whether someone is using your invention.
Why would being new and unique automatically translate to easy
recognition of its use? Speaking from personal experience (my day
job consists primarily of finding evidence of people using patented
technology) it's often _quite_ difficult to prove the use, even in
cases where there's absolutely NOBODY who questions the validity of
the patent.
Assume for the moment that you had a method of building hardware to
compute the square root of a floating point number faster or with
fewer gates than conventional methods. Think of what it could take
to figure out what parts of a Pentium III were used to compute a
square root, and whether they worked the way your patent described.
Don't get me wrong: proving such things can be done, but doing so is
often _quite_ slow and expensive.
> 2. You had an opportunity to stop infringement, but chose
> not to (for whatever reasons).
This is perfectly fine -- in fact, it's quite common. A patent
holder might decide not to enforce a patent for any number of
reasons. For a few examples: a really big company is unlikely to sue
a really small company or something like a charitable organization
because the it would make them look like big bullies. A company that
depends heavily upon a single major supplier or customer is VERY
unlikely to sue them. Big companies often have such large patent
portfolios that it's difficult for them to even keep track of their
patents well enough to keep maintainence fees paid on them, not to
mention keeping track of everything that might infringe. Tracking
possible infringement can be somewhat difficult when it's being done
by a direct competitor, but tremendously MORE so when it's being done
by somebody in a completely different field.
Just for one example I happen to know about, years ago the company I
work for did some work for a company that holds some patents on
housings used for underwater and underground cabling. One patent was
on a covering that helped wick moisture away from the conductors.
Now, the company in question might have a pretty easy time knowing
about what's being done by other people who manufacture underground
and underwater cabling, but how likely are they to realize that their
patent might cover some of the ways that disposable diapers are made?
The same thing could happen in this case. Just for example, there
are enough similarities between encryption and data compression, that
it wouldn't surprise me a whole lot if somebody might have written
something about one that at least _might_ apply to the other. That
particular connection is a fairly obvious one, but there might be
something that as a fairly mainstream programmer I'd be unlikely to
know about at all.
One thing I happened to run across recently was the fact that in some
cases companies scramble data for reasons completely unrelated to
making it hard to "decrypt". Just for example, data sent over CDDI
networks is scrambled -- without the scrambling, an idle network
produces a strong signal at one specific frequency. By scrambling
the data, the RF emmisions at any particular frequency are reduced.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: sci.crypt think will be AES?
Date: Sat, 29 Apr 2000 17:40:08 -0600
In article <8eeukc$7s2$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
[ ... ]
> The two URL's I offered are damning evidence about Mr. Ritter's claim that
> his idea has been confirmed new and unqiue.
You might want to realize that at least in the US, the rules are that
once a patent has been issued, the courts are required to _presume_
the invention is new and unique -- if a patent holder takes you to
court and you think it's not new or unique, it's up to you to _prove_
it. You can't get by with "well, it sure looks pretty obvious to
me" or anything similar; you've got no choice but to show where
somebody published or used the invention previously, or else the
patent will remain valid.
> No one here has claimed that it is easy or cheap to get a patent.
> However, no one honest, sane, and with a clue would claim that the cost
> or effort to get a whatever Mr. Ritter means by a "serious patent" differ
> from what is required to get one of the other kinds or types.
Actually, anybody with a clue would be well aware that there are (for
example) both design patents and utility patents, and getting a
design patent really IS a whole lot easier and cheaper than getting a
utility patent.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: Karatsuba threshold
Date: Sat, 29 Apr 2000 17:40:03 -0600
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
[ ... ]
> Also, what are the next thresolds, like when does Toom-Cook [3] or FFT
> multiplication [4] becomes usefull ?
Based on an ancient project computing Pi, FFT multiplication doesn't
become useful until MUCH larger than anything I know of related to
cryptography. When you're dealing with hundreds of thousands or
millions of digits, yes, it's absolutely useful. When you're dealing
hundreds of digits or so, I don't believe it's even close.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Vs: Vs: sci.crypt think will be AES?
Date: 29 Apr 2000 16:22:31 -0700
In article <8een72$ggp$[EMAIL PROTECTED]>,
Helger Lipmaa <[EMAIL PROTECTED]> wrote:
> I started the sentence with saying 'the fastest bulk encryption mode', i.e.,
> in the mode were Twofish achieves the best encryption rate per block.
But what's the justifiction for imposing such a restriction?
I must admit that it sounds pretty artificial to me.
If you care about key setup cost, use a mode where key setup is cheap.
If you care about encryption rate per block, use a mode where that is cheap.
Twofish gives you both. Sure, if you use the wrong mode for your application,
performance is sub-optimal -- so don't do that. ("Doctor, doctor, it hurts..")
I'd argue that a much more realistic way to measure cost of key schedules
is by estimating the average number of blocks, N, you expect to encrypt in
your application before doing a new key setup operation. Then you should
compare ciphers by the time it takes to do 1 key-setup + N block encryptions.
And, if you do this, you'll find that N=1 is the worst case for Twofish,
and even in this worst case, the Twofish/Rijndael ratio is nothing like 40x.
------------------------------
Subject: Re: new Echelon article
From: Diet NSA <[EMAIL PROTECTED]>
Date: Sat, 29 Apr 2000 17:35:21 -0700
In article <[EMAIL PROTECTED]>
, "Trevor L. Jackson, III" <
[EMAIL PROTECTED]> wrote:
>
>Politicians realize that a federal deficit is a useful
political tool for
>managing political control. This has nothing to do with
economics.
>
Yes, I am certain that politics & money
(or its deficit) have nothing to do with
economics. NOT !!! I am still using your
views as toilet paper and it looks like I
will never run out !!!
>Yup, and this process is so wasteful that it decreases the
efficiency of the
>various activities below that which would have obtained without
gov't "help".
This sentence does not make sense. What
do you mean by "below"?
>Look up the origin of the term "Laissez Faire" -- it has
nothing to do with lack
>of regulation. It has to do with lack of gov't "help".
This term originated in the 18th century.
Newsflash !!!- We are no longer living in
the 18th century and, anyways, I never
disputed any definition of "laissez faire".
>
>Actually, it's important that we keep the "ball" out of gov't
hands".
>
This is a meaningless statement which
has nothing to do with what I wrote. I
was implying that one way to decrease
gov't waste is to make the gov't more
efficient via the use of IT.
>
>How can you have it both ways? You have claimed that gov't
spending has helped
>various portions of society to the benefit of society as a
whole. This
>_requires_ an assumption that you know what would have
happenned without
>government interference.
No it doesn't. Consider, for instance, the
role of the CDC & related gov't efforts. If
they had never done anything then society
would most likely have suffered more
disease. Instead gov't funding helped in
the effective eradication of polio, small
pox, etc. (Unfortunately, Gov't funding
doesn't seem to do anything for
eradicating *your* ignorance).
The fact that you have no clue as to the
destructive
>effects of government "help"
Of course I have a clue. For example, just
consider the government's lousy handling
of the Waco incident.
>about the true results of government actions, and stop
believing the claims made
>before the facts.
What claims?
>by the legislators. Either Congress had no clue regarding the
effects of their
>programs, in which case they had no business legislating those
programs, or they
>_did_ know about the effects, but passed the programs anyway.
Which programs?
In either case
>government action is to be condemned.
If Senator Moynihan believes this then
why is he in government?
>
>That is laughable. There is no credible source of government
science.
What an extreme & absolute statement!
Now I have *bullshit* in addition to toilet
paper.
man behind the curtain", the EPA was
>revealed to be completely corrupt.
Yes, I am sure that they are all corrupt.
NOT !!! It is beginning to seem that it is
only your intellect that is thoroughly
corrupted.
Since all government activity is
dominated
>by politics,
How can you be sure that "all government
activity" is dominated by politics?
there is no, zero, nada, room for
scientific objectivity.
Again, how do you know these "truths" so
absolutely?
>
>OTOH, the desire for profits is not an ulterior motive.
Is this desire always "not an ulterior
motive"? I have determined why you are
able to be so all-knowing: You are the
King of False Absolutes (not to mention
horse shite).
It is a perfectly valid
>reason for engaging in scientific research.
Now you have said something reasonable.
Hallelujah !!!
Note that privately funded research
>is distinct from publicly funded research.
False & (very) messy bullshit again !!
Consider where my father works: Harvard
University. Here a researcher can receive
public & private funding simultaneously.
Privately funded research has to be
>objective because it is a search for the scientific truth.
No. The research is part of a search for
(corporate) profits more than it is part of
a search for some abstract or objective
truth. Also, the research could be
misrepresented for marketing reasons or
it could even be fudged.
One cannot sell
>products that don't work.
You are a bold faced liar. You should
contact consumer groups to learn about
the many products that have not worked
properly.
Now, in gov't research the results are
irrelevant to
>the process of getting funded,
Another absolute statement & lie.
so scientific truth is not a relevant
criteria.
>
Liar, liar, pants on fire.
>>
>This betrays an ignorance of the ways government works. It
does _not_ work for
>the benefit of society.
You're right. Government works only for
the benefit of robots from the future. See,
it is easy to imitate you by writing
complete crap.
>Why are the margins low? Because the products and services are
things people do
>not want.
This is not always true. [Returning to
toilet paper], more people want toilet
paper than IT bandwidth but the profit
margins are lower in the toilet paper
industry because it is much easier to
produce on demand. You are unaware of
what is probably the most basic concept
in economics- the relationship
*between* supply & demand.
So what source of wisdom does the
government use to decide what
>people should have they don't want?
This is gibberish with nonsensical
grammar.
>>
>> It is a myth that government *always*
>> does things more inefficiently.
>
>No, it's not a myth. It's a fact.
How would the private sector command &
run the military more efficiently than the
gov't? First of all, the military shouldn't
even be under the command of private
entities such as corporations. Thus, what
I said is not a myth & you are wrong yet
again.
Government is not reason, government is
>force.
Why does this always have to be true? Oh,
I forgot- you are the King of False
Absolutes. Flamewars are more fun than
any computer game, because I get to shoot
down real-life idiots !!!
" V hfdt afogx nfvw ufo axb (o)(o) " - Gtnjv
====================================================
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
Date: Sat, 29 Apr 2000 02:42:25 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: combine hashfunctions
=====BEGIN PGP SIGNED MESSAGE=====
Tom St Denis wrote:
> Joseph Ashwood wrote:
> > Tom St Denis wrote:
> > > If h1 and h2 are unrelated then this is obviously true.
> > > For example SHA-1 || TIGER will give you a 160+192=352 bit
> > > hash, this composite hash function is believed to be collision
> > > resistant iff h1 and/or h2 is collision resistance.
Which do you mean, "and", or "or"? (If "or", then the minimum work
to find a collision is only guaranteed to be on the order of 2^80.)
> > > The resistances (in this case) is equal to a 352 [bit] hash
> > > (i.e O(2^176) to find a collision) iff *both* hashes are
> > > collision resistant.
> >
> > You have forgotten a VERY important additional statement, it
> > must be proven that h1 and h2 are unrelated in every way,
> > you stated it at the beginning but you then proceeded to
> > forget that statement when you gave particulars. There has been
> > no proven unrelation between SHA-1, TIGER, MD2, MD5, RIPEM, etc.
Correct, and in fact they are all quite similar in some respects.
> > You also seem to have forgotten that iff they
> > are completely unrelated, only one has to be resistent,
This is somewhat misleading, because there are significant
constraints on the randomness of the output of the other hash, and
meeting those constraints would usally result in it being collision-
resistant. A simple non-cryptographic hash certainly will not do.
> > so it would make more sense to use a simple checksum as the
> > second portion (assuming it is unrelated to the other hash),
> > simply because of the speed. On my personal machine I get
> > SHA-1 speeds of around 16 MB/sec if I remember correctly,
> > but 32-bit checksumming I get a little over a gigabyte a
> > second, speeding up the entire process.
>
> No because if one of the hashes is easy to break then the complexity of
> the system is closest to the stronger algorithm. If it takes 2^16 work
> to break the 32-bit crc and 2^80 work to break SHA-1 (random birthday
> thingy) then the entire complexity is 2^96 at the most only.
That's not really saying much, since the complexity of finding collisions
is at most on the order of 2^96 for *any* hash function of output length
192 bits.
As it happens, since CRC is easily invertible, there is an attack
against this with complexity 2^80, since you can do the collision-search
for SHA-1 using only input texts that are known to have a specific CRC-32.
> That's assuming it takes 2^16 steps to break a CRC-32.
>
> If on the otherhand I used TIGER+SHA-1 then I get at the most 2^92 *
> 2^80 = 2^172 complexity of an attack [against collision-resistance].
You mean 2^96 * 2^80 = 2^176. But again, that's the upper bound for
*any* 352-bit hash function.
> And I assume they are unrelated since they don't even use similar
> design structures in their construction.
Of course they do: they're both instances of Merkle's meta-method
(Handbook of Applied Cryptography Algorithm 9.25).
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOQo9wDkCAxeYt5gVAQEYwQf+JFaesVTLLBdg+4cIJ19yWw7ERsE5X1OH
K6hYTwN9wEkWb+W4XmbJd5pyqKTJE2izPJM38X3fLgSieZWZmScAt+epOtiIhSvZ
BP1gVOgyDfHSftysFSABGomjVcJsZULssK4xekLeCOQ6aDlJpxL79bpP6iPjeKQ+
/t3t8nNTVPYC935tAOtenJeWBdVg5WER+BmCnZVvnjSeCH+TqVY8oVtToSqcR3Vd
Z886esRa7l7br/spQTcL4B20nkfncQo+RvuRMQ9Jsvd9zmI6AFrgmcAYHgTSQjWr
2Nc38FYD/BheiPn5O9xqByzH5zVyK4I1dgOkBIsS+gCmq76ctPNRLw==
=c8+b
=====END PGP SIGNATURE=====
------------------------------
Date: Sat, 29 Apr 2000 02:54:44 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: AEES 16 rounds
=====BEGIN PGP SIGNED MESSAGE=====
[EMAIL PROTECTED] wrote:
> You are right. My explanations are not clear enough.
> If I show multiplication table in the form
> 1 2 3 4
> 2 3 4 1
> 3 4 1 2
> 4 1 2 3
> then I mean following
> | 1 2 3 4
> ------------------
> 1 | 1 2 3 4
> 2 | 2 3 4 1
> 3 | 3 4 1 2
> 4 | 4 1 2 3
Why not simply use addition mod 4, with values relabelled as 0..3
instead of 1..4?
> You see that 1 is unit of so defined cyclic group.
The group is actually Z_4 under addition. I had a brief look at your
web pages the first time you posted here, and didn't see why they
described the system in such an unnecessarily complicated way.
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOQpAyDkCAxeYt5gVAQG6YQf/RvUHICrBD5wF4U0N/UAXiK2WUQKfc5B5
HYjYhEFysyzL/q3CsXGjnlbK3H8IsIKVjaoh3tQ3wlyvwcTFk+87K1QoIruqPBbu
AIyxv3lK/hvg0eScSssLPWp0kK2WIufbLvfuluojvJBxPqXJTnoKH1KHUzgKC0L4
RFB/Q+XgF/cigP5HchdU7hvfTWZyVCmWvACTxw2CEHqia3ghe0PFjH8iIapHV/Gj
3GoD0t6QoQa0dINC14lgVgQfR5MAwvDuST5mhp0/Zv8GhqTVqHIwDI9mfXb3MAJo
7yykn6mWXvW4iWLg87iqOxeGtWWiNOSkAaMOaXKHyTocTOR8QYQHvw==
=TmtP
=====END PGP SIGNATURE=====
------------------------------
** 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
******************************
