Cryptography-Digest Digest #651, Volume #11 Fri, 28 Apr 00 03:13:00 EDT
Contents:
Re: AEES 16 rounds ("Joseph Ashwood")
Re: [OT] Re: U-571 movie ([EMAIL PROTECTED])
Re: sboxes for the bored... (Terry Ritter)
Re: sci.crypt think will be AES? (Terry Ritter)
Speaking of HD Overwriting... (NFN NMI L. a.k.a. S.T.L.)
A naive question (Mok-Kong Shen)
Re: AEES 16 rounds (Boris Kazak)
----------------------------------------------------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: AEES 16 rounds
Date: Thu, 27 Apr 2000 22:12:10 -0700
> #After reading through your documentation, I found a few
> #problems:
> Only a few? My congratulations!
I didn't get into analysis, because of other problems.
>
> #1) You have no clue what a multiplication table is
>
> It is more then strange. My implementation of
multiplication tables
> of finite groups is described with all details in
description marked
> as 'Alex Encryption'. Please take a look at it. Would you
have additional
> questions I am to your service.
Last I checked multiplication table were defined in about
3rd grade around here, with sequential x along the top,
sequential y along the left, and each location in the grid
filled with x*y for the coresponding row and column.
>
> #2) You have not defined some of the functions you use
>
> Which of them?
The function that you used to define your so-called
multiplication tables
> #Perhaps if you were to follow the guidelines used by the
AES
> #finalists I might be inclined to give it another look.
>
> Concerning AES contest I can only laugh.
On what grounds do you even consider laughing? Last I
checked it was basically the best of the best as finalists.
Joe
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: [OT] Re: U-571 movie
Date: Thu, 27 Apr 2000 22:20:52 -0700
On Fri, 28 Apr 2000 03:22:31 GMT, [EMAIL PROTECTED] wrote:
>[EMAIL PROTECTED] wrote:
>>>Of course, hindsight is always 20/20. On the morning of the raid,
>>>radar was in its infancy (not even standard on ships yet!) and
>>>_everyone_ knew that the Japanese would _never_ attack the US.
>> Sarcasm plays badly, but I get the message.
>
>It actually wasn't meant sarcastically. As I understand it (I wasn't
>alive then, so I could be wrong) the conventional wisdom then was that
>Japan didn't pose a serious threat.
First I want to apologize to the group for continuing the off topic
post. This will be my last on this subject anyway.:)
>From discussions with my Father (Master Gunner, USMC, Retired) and
with other officers and persons who were at Pearl on the day of the
attack (including two uncles and several other relations) the Japanese
were believed only to be waiting for the proper moment to attack.
That they didn't invade the Hawaiian Islands and continue on to attack
the US West Coast was considered an amazing thing.
ON December 8-24, 1941, the West Coast was under Alert for just such
an Attack. Marine units from 29 Palms and Other bases were put on
alert and according to my Father, he was told the entire West Coast
was to be on mobilization readiness until sometime in February.
Though it was standard practice to do such mobilizations as a drill,
he said this was the first time he had heard it being done along the
entire coast at one time.
Now, I have no military documents to back any of this up. My Father
has always been honest with me, but I won't say he didn't exaggerate
or "See things from a single view point". It does however tie with
other pieces of information I've read or heard.
Now, I thank you all for your patience in this OT discussion. I really
want to learn more about Cryptography. I'm still just learning how.
Oh, and in case anyone was wondering, I'm 50 yo. so I'm not old enough
to have been in PH either. Missed Korea too. And was fortunate to be
enrolled in college for my Vietnam days. Desert Storm and later
actions are also beyond my personal involvement. So, I read, listen,
ask questions, and compile the information to make an informed
hypothesis.
Has anyone completed their CyberSaber? If so, would you be willing to
assist me in mine. I can't seem to get the program to work correctly.
Sed Quis Custodiet Ipsos Custodes?
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: sboxes for the bored...
Date: Fri, 28 Apr 2000 05:30:55 GMT
On Thu, 27 Apr 2000 16:00:50 GMT, in <[EMAIL PROTECTED]>, in
sci.crypt Tim Tyler <[EMAIL PROTECTED]> wrote:
>Terry Ritter <[EMAIL PROTECTED]> wrote:
>: in sci.crypt Tim Tyler <[EMAIL PROTECTED]> wrote:
>
>:>Large s-boxes take up too much space in hardware, and chew up your cache
>:>in software.
>
>: An 8-bit s-box only takes 256 bytes.
>
>That's true. There are several ways to look at this. On one hand an
>8-bit s-box isn't *terribly* large.
>
>On the other hand, it's quite a lot bigger than a four bit one. onsider
>that a 4-bit s-box takes up 8 bytes. That means you could fit about 32 of
>them into the same space as a single 8-bit s-box. It also means that they
>are likely to go about 5-6 times faster when implemented on a
>two-dimensional substrate.
But we *need* 32x as many 4-bit tables to get the same complexity as
an 8-bit table. There's no free lunch here. Having substantial
complexity is an *advantage*, if not overdone.
>:>If you use enough independent small s-boxes in series the resulting system
>:>can still be made quite strong.
>
>: Chaining substitutions in sequence just produces another substitution.
>: No possible sequence of 4-bit substitutions can be any different than
>: some other 4-bit substitution.
>
>That's not what I was trying to say. If you are making larger
>permutations out of smaller ones you could use (for example) a "brickwall"
>partitioning arrangment - i.e.
>
>|v v v v v v v v v v v v v v v v|
>|X X X X|X X X X|X X X X|X X X X|
>|v v v v v v v v v v v v v v v v|
>|X X|X X X X|X X X X|X X X X|X X|
>|v v v v v v v v v v v v v v v v|
>|X X X X|X X X X|X X X X|X X X X|
>|v v v v v v v v v v v v v v v v|
>|X X|X X X X|X X X X|X X X X|X X|
>|v v v v v v v v v v v v v v v v|
>|X X X X|X X X X|X X X X|X X X X|
>|v v v v v v v v v v v v v v v v|
>|X X|X X X X|X X X X|X X X X|X X|
>|v v v v v v v v v v v v v v v v|
>
>Data flows in at the top and out at the bottom.
>Xs represent bits. One "|X X X X|" represents a 4-bit permutation.
>
>Here the layers are applied in series (like rounds) to produce a
>"simulated" 16-bit permutation. There aren't enough layers in the above
>diagram to get proper diffusion from the top-left most bit in the input to
>the bottom-right-most one - but you probably can see the idea I was trying
>to convey.
But diffusion is *the* issue: we can't just handwave that into
existence. Producing an even diffusion from boxes which always cover
4 contiguous bits is going to be a problem, and I have serious doubts
that it can be resolved.
Another approach is to have each 2nd-level box take a bit from a
different top level box, but using just one bit that way leaves one
open to peculiarities with that bit, either from data or the box. For
example, if that input bit changes, and that has no effect on one bit
of that box output, the complexity of that box has not participated in
the diffusion of that bit, and all the subsequent boxes which depend
upon that will also not participate. So it would appear that such a
design might well have the additional requirement (also needed in
substitution-permutation ciphers) that a change in input be guaranteed
to cause a change in output.
>Using this sort of idea you could build a type of 16-bit s-box which
>would work much faster and take up /much/ less area than a "real"
>LUT-based one. You could vary the security level quite smoothly by
>adding more layers.
>
>: And no 4-bit substitution has a nonlinearity over 4. That means that
>: changing only 4 bits in the Boolean function for some bit position
>: will yield a linear Boolean function.
>
>: In contrast, it is difficult to even *find* an 8-bit substitution with
>: a nonlinearity below 78.
>
>Well, it's /easy/ to "find" such a function - provided you're not doing a
>completely blind search ;-)
We hardly even have to *look* to find it at the 4-bit level.
But if we *only* use 4-bit tables with maximum nonlinearity, we have
changed the universe of nonlinearity distribution: we have performed a
selection which may be identifiable and useful to the opponent. For
example, if the set of all acceptable boxes is not bit-balanced, then
the opponent can expect to find a bias and possibly even localize it.
>[making large permutations out of smaller ones]
>
>:>The disadvantage is probably additional concern over security as a result
>:>of the greater structure involved.
>
>: I think that is exactly backwards: There is much less "structure" in
>: a random 256-byte table than in a random 16-nybble table. That's what
>: linearity means.
>
>Again, I probably wasn't very clear in saying what I meant. A "genuine"
>8-bit s-box made with a 256-bute LUT is maximally difficult to crack.
>I was considering this structure to be uniform and flat - it's just a
>simple look-up table.
>
>A /simulated/ 8-bit s-box made up of a dozen or so 4-bit s-boxes may work
>faster and take up less space, but it's probably not as secure.
It may be that one 4-bit table will work faster than one 8-bit table.
But the above construction uses 6 layers of 4 table operations each
(24 4-bit memory accesses, or 6 functional layers) to get not
particularly good diffusion characteristics in a 16-bit block. In
contrast, we can get better diffusion from just two 256-byte 8-bit
orthogonal Latin squares and just one 16-bit memory access (we store
both squares together as 16-bit elements).
>It has
>more "structure" - in that it can be divided into a series of
>partially-independent components.
>
>Anyway, the security concern seems real enough. If using multiple small
>s-boxes is a viable approach, care will need to be taken to ensure that
>the difference between a real 8-bit s-box and the simulated one which is
>composed of samller, more atomic components is not one on which practical
>attacks can be based.
The diffusion characteristics (the average change in an output bit for
a change in an input bit, over each possible input and output bit),
and the nonlinearity distribution of the resulting cipher must be
carefully checked.
>:>If a block cypher is usually a large permutation constructed from smaller
>:>ones, it seems sensible to ask how large the smaller components should be.
>:>
>:>The possible answers seem to be "as small as possible while retaining
>:>non-linearity" - i.e. 3x3 or possibly 4x4 - "as large as possible
>:>without slowing things down to a crawl" - or "of a variety of sizes".
>
>: First, none of this works unless you have some sort of mixing which
>: does in fact effectively create large boxes from small ones.
>
>Well, yes. The "brickwall partitioning scheme" I mentioned earlier would
>be one approach. There are a number of other methods. Fundamentally, the
>art of building large permutations from smaller ones is simply the art of
>block cypher design.
"Simply" is not exactly the word I would use.
>: Then, to obtain simulated large boxes from small ones we need multiple
>: small boxes, and a mixing process which does that. The larger the
>: tables we start out with, the fewer tables and fewer mixing layers
>: that are needed.
>
>Yes, this is exactly what I'm attempting to talk about.
>
>: My answer is: "large enough for each actual table to have substantial
>: nonlinearity on its own, to protect against the case where the
>: opponent reaches the actual table." Since that only needs 8-bit
>: tables, which take only 256 bytes each, that seems a very reasonable
>: solution.
>
>I'm lost here. By "reaching the actual table" you /seem/ to refer to the
>case where the opponent knows (or has some idea of) the relationship
>between the inputs and outputs of the box. If this happens things are
>not good for an s-box of 4-bits, 8-bits, or 12 bits; since in either
>case the internal state is likely to be revealed with relatively little
>known plaintext.
The great danger in linearity is the ease of manipulating a symbolic
expression which represents the target; that allows us to *infer* the
target from external values, instead of actually having direct access
to it. Such an approach is unlikely to be useful with 8-bit boxes
(and above) simply because each such table will have enough
nonlinearity on its own to make linear symbolic expressions unhelpful.
>Burying each small s-box in a pile of other similar s-boxes seems
>a reasonable way of stopping the opponent from "reaching the table"
>in the first place.
I think that before we say that 4-bit tables are useful in this way,
we must first have substantial experimental results which approach
those for the ideal block cipher. We cannot simply *assume* those
results and say that 4-bit tables are a better choice than larger
tables. They may not be any choice at all.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: sci.crypt think will be AES?
Date: Fri, 28 Apr 2000 05:59:42 GMT
On Fri, 28 Apr 2000 01:44:02 GMT, in <8eaqcv$dhq$[EMAIL PROTECTED]>, in
sci.crypt Bryan Olson <[EMAIL PROTECTED]> wrote:
>Terry Ritter wrote:
>> Richard Parker wrote:
>
>> >Presumably at least some of those who are aware
>> >of the AES process and who hold a patent that they
>> >feel is infringed upon by one of the AES candidates would
>> >have contacted the author by now.
>>
>> Why would the patent holders contact *anybody*?
>
>Because they operate in good faith. This isn't just an
>issue in cryptography; standards committees in all areas ask
>about assertions of patent rights, and reputable companies
>answer.
Here you seek to imply that a company which does not answer is not
reputable. But that is false: A reputable company may not answer for
not being informed, or as a rational response to a request which
cannot be answered accurately and which could have substantial
negative consequences. Once again, NIST has certainly not informed me
(and, presumably, others like me), so they can hardly expect anything
from that direction. Perhaps they think that if it is "in the air"
everyone with some possible interest will know about it. But that is
ridiculous.
Nor does everyone with cryptographic patent rights for some reason
have a duty to analyze each of the AES submissions -- for free --
simply to "operate in good faith." What law requires that? And I
would suggest that NIST has not operated "in good faith" with respect
to patents from the beginning.
Personally, I chose to not enter the AES "contest" because it would
have required me to give away rights which I own and have obtained at
substantial cost and effort. Other entrants had no such rights, and
thus were not required to give anything up to participate. I view
that as an example of unequal protection under the law, and an obvious
lack of "good faith" from NIST.
There certainly can be no argument that I had a right to not
participate in AES. Now you and NIST would like to argue that I have
some sort of responsibility to that process, even though I declined to
participate specifically because I found it unfair and unjust. Not
only do I doubt there exists any such requirement, I repeat that the
inventor often simply does not know that sort of information.
>> Patents
>> are about money: licenses and use. It is only when
>> things go into production that patent holders would get
>> serious.
>
>[...]
>> >While comforting, this of course does not rule out the
>> >possibility that someone hopes to make money by
>> >deliberately not making public the fact that one of the
>> >AES finalists infringes on one of their patents in the
>> >hope that the infringing algorithm is chosen as the
>> >AES winner.
>>
>> Comforting or not, it obviously is *not* a matter of
>> "deliberately not making public," since patents *are*
>> public. Indeed, US patents are issued by the Commerce
>> Department, the parent of NIST, and if *they* don't
>> know what they have done, that is their problem.
>
>I don't think your legal theory will hold up. As Richard set
>up the hypothetical situation, the potential plaintiff knows
>he has the opportunity to avoid incurring any damages, but
>deliberately does not respond so that he can later sue for
>those damages. That will fail the common-law requirement of
>good faith.
I doubt that Richard has intended to set up a situation which does not
reflect reality. The reality is that an inventor may not know whether
an AES design infringes. As a crypto patent holder, I certainly have
spent no time at all thinking of AES infringement. And as far as I
know, I cannot be required to spend time and treasure addressing some
possible future NIST standard.
>> Nor does a patent holder necessarily *know* what infringes: A patent
>> is a *legal* document, intended to "read on" as much technology as
>> possible. The inventor may have a narrow personal interpretation
>> which is only tiny subset of the owned technology. It may take a
>> *patent* *lawyer* to understand that a particular patent actually
>> covers something which seems distinct to the inventor.
>
>Alas, patent lawyers do not reliably determine infringement
>either. There is a chance that a claim will come up which
>was not known at the time, but NIST has a fine reputation
>for avoiding such problems.
You must be thinking of some *other* NIST.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (NFN NMI L. a.k.a. S.T.L.)
Subject: Speaking of HD Overwriting...
Date: 28 Apr 2000 06:16:26 GMT
Speaking of HD overwriting, does anyone know anything about recovering data
from erased CD-RW discs? Probably the laser misses the outer fringes of a
written bit, or perhaps it doesn't flip completely - after all, the things can
only be rewritten oh, 1000 times, some brands anyways. (Or why disc and not
disk is applied to those plastic things?)
-*---*-------
S.T. "andard Mode" L. ***137***
STL's Wickedly Nifty Quotation Collection: http://quote.cjb.net
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: A naive question
Date: Fri, 28 Apr 2000 08:28:44 +0200
If one has, say 56 bits of truly random bits, one can use
that as an OTP to encrypt 56 bits of message and obtain
superior protection. If one use that instead as a key to an
encryption algorithm, say a very good block cipher, to encrypt
n*56 bits of message, an intuitive feeling is that the
protection would quickly get worse as n increases. Since the
algorithm itself can't generate any entropy, it seems that the
security pro bit of the message decreases monotonely, maybe even
'proportionly', with increasing n. Like mixing water into whisky,
the qualtity of each cup of the drink rapidly deteriorates as
more water is involved. Is this line of thought reasonable?
Thanks.
M. K. Shen
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: AEES 16 rounds
Date: Fri, 28 Apr 2000 06:43:20 GMT
Adam Durana wrote:
*****************
> you are forgetting about the people who just read the newsgroup
> and rarely post. These people would also most likely check out your cipher.
> And keep another thing in mind, it is possible to learn even from people you
> don't care for. Perhaps if you got together with your friend Boris, maybe
> he would help you write your algorithm in C?
>
> - Adam
================
Dear Adam, I would gladly help Alex with whatever I can, but there is
a geographical problem - he is in Stuttgart, Germany, I am in San Diego,
USA. A bit difficult to get together, maybe Internet will help.
Besides, I am not really a fan of neither C nor Pascal, my favorite
is FORTH, but it is definitely out of favor among the readers and
posters
here. So it goes...
Best wishes BNK
------------------------------
** 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
******************************
