Cryptography-Digest Digest #923, Volume #11 Fri, 2 Jun 00 16:13:00 EDT
Contents:
Re: Contest rule proposal ("Trevor L. Jackson, III")
Re: TC3 Update (tomstd)
Re: TC3 Update (tomstd)
Re: Contest rule proposal (David A. Wagner)
Re: Contest rule proposal ("Trevor L. Jackson, III")
Re: TC3 Update (tomstd)
Re: DVD encryption secure? -- any FAQ on it (Mok-Kong Shen)
Re: Contest rule proposal (Mark Wooding)
Re: Contest rule proposal (David A. Wagner)
Re: TC3 Update (David A. Wagner)
Re: TC3 Update (tomstd)
Re: TC3 Update (David A. Wagner)
Re: Contest rule proposal ("Paul Pires")
Re: Good ways to test. (Mark Wooding)
Re: Contest rule proposal ("Paul Pires")
----------------------------------------------------------------------------
Date: Fri, 02 Jun 2000 15:35:47 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Contest rule proposal
Relax.
1) Your position requires no defense.
2) The opposing position cannot be defended.
Paul Pires wrote:
> Terry Ritter <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
>
> Thanks Terry.
>
> I was feeling lonely again.
>
> One comment thought.
>
> >I have an even simpler proposal: the patent holder offers fair use of
> >the patented techniques within the non-commercial context of the
> >context. I certainly would not agree to someone else's definition of
> >"free software."
>
> Does everybody else have to wear a sign that says "leper" too?
>
> Why must I assert that I won't do something bad if I have not given
> cause for the suspicion? Nothing in patent law allows me to go after people
> for evaluating my submission to an academic contest that I entered it in.
> Boy, RSA and PKP sure pissed off a bunch of people. That's partly what this
> whole issue is about.
>
> Now, the group.
>
> This group should worry about larger issues. Like the intellectual
> intolerance which is being shown here based on myth, legend and
> misinformation.
>
> It seems that every one here (almost) has made up their mind that
> someone who applies for a patent is greedy, rapacious and incapable of
> contributing to the groups common good. This is a polar issue, either you
> are on the side of the angels or the slime doggies. Look back on times when
> this kind of "Every body Knows" group intolerance was present and be
> ashamed.
>
> I have been grandfathered, what am I griping about? You stand up and be
> counted when it is required, I can do no less. If that means that you folks
> take away my slot, so be it. I just asked to play too, you don't have to
> beat me bloody.
>
> Why so adamant? Why the instant assumption of criminality? How can you
> accuse someone of atrocious behavior just because of the side of an issue
> that they are associated with?
>
> Look at the "reasons" that everybody is trotting out here:
>
> Folks think I want free analysis and yet keep my rights to myself.
>
> I want you to consider that I may be putting up as much for free as you.
> I have diligently presented my paper and asked for comments. I have reserved
> the right to commercialize it. Your analysis (if you choose to stoop so low)
> is your property not mine. I have not hired you as a consultant. You would
> laugh if I pointed a potential licensee at you and said " Ask Andru, He
> likes it". I have no rights to the commercialization of your analysis. If
> you want to make an exchange, fair to both sides, I'm open. Why do you feel
> that I must prostrate myself and surrender all rights in advance, with no
> agreement of exchange?
>
> I saw no Rule that said "You must give up all rights to your stuff and in
> exchange all analysts will work diligently on your idea and post quality
> results" Yeh, right.
>
> It isn't about the freedom of Ideas its about preserving the hierarchy
> of control . (That's you guys)
>
> It's not easy being a filthy patent monger in sci.crypt. This whole
> thread is off topic! You guy's sat back fat dumb and happy and jumped all
> over this, confident in the assumption of moral superiority. I was invited,
> I looked at the rules, I didn't post any suggestions to clear MY OWN WAY
> when the contest was being formed.
>
> Now you have to decide. Sneer and dismiss these pleas as being from
> someone who just doesn't understand the real issue. You can't back down from
> these weighty social concerns can you? Or admit that this group needs an
> enema when it comes to this topic.
>
> Paul
------------------------------
Subject: Re: TC3 Update
From: tomstd <[EMAIL PROTECTED]>
Date: Fri, 02 Jun 2000 12:23:15 -0700
In article <8h90li$49u$[EMAIL PROTECTED]>, zapzing <zapzing@my-
deja.com> wrote:
>In article <[EMAIL PROTECTED]>,
> tomstd <[EMAIL PROTECTED]> wrote:
>> I changed TC3 to use 128x128 sboxes (multiplicative inverse in
>> the galois field 2^128 mod p) instead of the hybrid F
function.
>>
>> With 4 rounds my cipher is provably secure against diff and
>> linear attacks since the LP/DP max for both is 2^-126.
>>
>> I have a more complete "key schedule" to avoid weak keys.
>>
>> The cipher is slow, but conceptually simple and provably
secure.
>>
>> It's at http://www.tomstdenis.com/tc3.c
>>
>> I am betting there is something I overlooked, so cutos to the
>> first person to break it.
>>
>> Tom
>>
>
>Thank you. I'm glas to see that people are beginning
>to consider other things in cryptography besides
>just chosen plaintext attacks. Conceptual simplicity
>*is* important and I'm glad you used it as a design
>criterion.
Have you checked it out yet? I am dying to hear of
comments/attacks :)
TC3 is a fairly simple cipher... Take a 128-bit block called X
and do this
for r = 0 to 3 do
X = X + key[r]
X = X^-1 mod p
next r
addition is done as four 32-bit units not a single 128bit word,
and 'p' is a deg-128 polynomial (coefficients are mod 2).
It's slow but from a math standpoint very easy to look at, and
of course like all my other work it's perfectly free for
everyone to use. That is, if it's not broken by someone first.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
Subject: Re: TC3 Update
From: tomstd <[EMAIL PROTECTED]>
Date: Fri, 02 Jun 2000 12:27:03 -0700
In article <8h91cs$p8s$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (David A. Wagner) wrote:
>In article <[EMAIL PROTECTED]>,
>tomstd <[EMAIL PROTECTED]> wrote:
>> Sorry... I am calculating the inverse of the input in GF(p)
>> where p is a degree-128 polynomial (with coefficients taken
mod
>> 2).
>
>Sorry, that still doesn't make any sense. You mean you are
>calculating the inverse in GF(2^128) [*]. You might want to
>read up on finite fields a bit more...
Ok you take the 128-bit input from GF(2) and convert it into a
polynomial in GF(2)^127. Then you perform the multiplicative
inverse on it. Say the input was '3' or '11' (binary) you are
essentially performing something like
S(3) = (x + 1)^-1 mod x^4 + 1
S(1) = (1)^-1 mod x^4 + 1
etc...
>[*] It just so happens that one way to construct a finite field
>(isomorphic to) GF(2^128) is by taking the ring of polynomials
>with coefficients in GF(2) and quotienting it with the ideal
>generated by some irreducible polynomial p of degree 128.
My 'p' is a polynomial with coffiecients mod 2, and it is a
degree 128 polynomial...
I dunno how to say that, I always thought it was GF(2)^128.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Contest rule proposal
Date: 2 Jun 2000 12:26:26 -0700
On the issue of Chutzpah, IMHO it should not be considered a complete
submission to the contest anyway. Forget the patent stuff -- the Chutzpah
document simply doesn't contain enough information to independently implement
the cipher [*]. How can anyone be expected to do cryptanalysis when the
cipher isn't fully specified?
[*] Specifically, the generation of the "Test Permutation" is never fully
described [**].
[**] Well, unless you read the source code, presumably, but if you do that,
you'd better be awfully patient. Thanks, but no thanks.
------------------------------
Date: Fri, 02 Jun 2000 15:41:26 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Contest rule proposal
Andru Luvisi wrote:
> You hit the nail quite squarely on the head: Why should we give a
> designer no cost analysis when he won't give us the algorithm for no
> cost?
You shouldn't if you believe it would be unfair. Neither should you restrict
those who believe it is fair from doing so.
Note that the subject of the second sentence of the quote above has no
referent. There is no "we" here. There are only individual contributors who
are quite capable of exercising their own organs of discretion. Any other
assumption is an egregious insult.
------------------------------
Subject: Re: TC3 Update
From: tomstd <[EMAIL PROTECTED]>
Date: Fri, 02 Jun 2000 12:29:03 -0700
In article <8h91cs$p8s$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (David A. Wagner) wrote:
>In article <[EMAIL PROTECTED]>,
>tomstd <[EMAIL PROTECTED]> wrote:
>> Sorry... I am calculating the inverse of the input in GF(p)
>> where p is a degree-128 polynomial (with coefficients taken
mod
>> 2).
>
>Sorry, that still doesn't make any sense. You mean you are
>calculating the inverse in GF(2^128) [*]. You might want to
>read up on finite fields a bit more...
To quote the paper where I got the idea from
"Let S(x) = x^-1 over the galois field GF(2^n),"
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: DVD encryption secure? -- any FAQ on it
Date: Fri, 02 Jun 2000 21:39:34 +0200
There is an article in New Scientist, 27 May, p.11,
entitled 'Licence to thrill' that seems to be of interest
to those interested in DVD. The first sentence of the
article is reproduced below:
From this week, well-heeld gadget fans will be able
to buy a home-cinema system that lets them watch
the astonischingly high-quality pictures that till
now have stayed locked inside DVD movie discs.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Contest rule proposal
Date: 2 Jun 2000 19:28:17 GMT
Terry Ritter <[EMAIL PROTECTED]> wrote:
>
> On 2 Jun 2000 14:59:11 GMT, in <[EMAIL PROTECTED]>,
> in sci.crypt [EMAIL PROTECTED] (Mark Wooding) wrote:
>
> >Terry Ritter <[EMAIL PROTECTED]> wrote:
> >
> >> I don't guess you would. A worldwide royalty-free license might as
> >> well mean there was no patent at all.
> >
> >That's clearly not what Adams and Tavares thought when they granted such
> >licences for CAST-128 and CAST-256. And it's clearly not what RSA
> >Security Inc. thought when they submitted RC6 to the AES contest.
>
> If you have something to say I suggest you say it more directly.
Oh, it's not clear enough. Oh, well.
The point is that you can have a patent on a particular structure of
cipher, or a method for designing ciphers. While this clearly covers
all ciphers designed in this way, you can make specific instances of
your design free while maintaining your `rights' over the underlying
method or structure.
I gave examples. Here's one in more detail. Messrs C. Adams and
S. Tavares came up with a design method for block ciphers based around
bent functions, which they called CAST, apparently nothing to do with
their initials. The design procedure is, according to Schneier's book,
patented. However, two ciphers designed using this design procedure,
CAST-128 and CAST-256 (the latter of which was submitted to the AES
contest, but didn't make it to the final five) are licensed, free of
change, to everyone. They clearly thought that providing the free
licence to the specific ciphers wasn't equivalent to not having patent
protection for their design procedure.
> One point of a patent is to *reveal* information, as opposed to
> keeping it secret. This choice is always available, and if there is
> no profit from exposure, then there will be more secrecy and less
> public advance. Congratulations on being on the wrong side.
In the case of ciphers, I don't see very much in the way of worthwhile
secret ciphers. The two best-known ones which spring to mind are
Rivest's RC2 and RC4. RC2 is a fairly dull block cipher, about the same
speed as DES and not a lot more secure[1]. RC4 is quite a nice stream
cipher. Neither stayed secret for a particularly long time, and neither
is *very* exciting.
On the subject of RC4, IBM has a patented stream cipher (well, actually
it's a pseudo-random function family) called SEAL. It's actually
slightly faster than RC4 (!). As far as I'm aware, hardly anyone
actually uses SEAL, and as a result it's not very interesting to
analyse.
> There is no distinction: Each individual new technology takes time to
> research and prepare, and unless costs are recovered, that research
> cannot continue.
Let's pretend that you have a pint of beer. (If you don't like beer,
substitute something else you do like. Alcohol content and general
liquidity are unnecessary for the argument.) If I take your pint away
and drink it, then you'll become upset because you no longer have your
delightful beverage, which you paid good money for. That's fine and
reasonable.
Let's say I have a gadget which can duplicate pints of beer, and I use
it to take a copy of your pint. You've lost nothing in this process
that I can see. The world is exactly the same except that I now have a
pint too. Who's done harm here, and to whom?
> So-called "free" ciphers are one of the worst possible deals that
> society could have made. Not only does society get to pay for the
> systems which use those "free" ciphers,
While you don't have to pay for systems which use patented ciphers?
Yeah, right!
> they simultaneously reduce the financial basis for an industry of
> cipher development and measurement which would produce a continuing
> flow of good ciphers.
I don't see Anderson, Biham, Daemen, Knudsen, Massey, Rijmen, Schneier,
or Vaudenay stopping any time soon.
[1] Knudsen has some good differentials for RC2. I suspect that the
attack can be improved by using Wagner's boomerangs. I'll try this
out over the weekend and see what happens.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Contest rule proposal
Date: 2 Jun 2000 12:30:44 -0700
Oh, and by the way, there is an important error in the Chutzpah document.
It claims that Chutzpah is a block cipher, not a stream cipher. That's
just plain wrong, and the mistake highlights a fundamental misunderstanding
of the standard terminology.
Stream ciphers are stateful; block ciphers are stateless. Chutzpah is
a stream cipher. And the contest is supposed to be for block ciphers only.
Therefore, I think we can conclude that Chutzpah does not belong.
Am I missing something here?
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: TC3 Update
Date: 2 Jun 2000 12:35:41 -0700
Yes, I know how the construction works. The point is that using the
standard terminology correctly is *important*. Using the terminology
incorrectly only spreads confusion. It is better to avoid using the
short-hand notations entirely if they are going to be used incorrectly.
And, by the way, your latest post got it wrong again: it's GF(2^128),
not GF(2)^128 (the latter means something very different).
------------------------------
Subject: Re: TC3 Update
From: tomstd <[EMAIL PROTECTED]>
Date: Fri, 02 Jun 2000 12:40:14 -0700
In article <8h92ad$pb6$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (David A. Wagner) wrote:
>Yes, I know how the construction works. The point is that
using the
>standard terminology correctly is *important*. Using the
terminology
>incorrectly only spreads confusion. It is better to avoid
using the
>short-hand notations entirely if they are going to be used
incorrectly.
>
>And, by the way, your latest post got it wrong again: it's GF
(2^128),
>not GF(2)^128 (the latter means something very different).
What is the diff? The paper does say 'GF(2^n)' so I just
misunderstood it.
Ok I admit I just copy/pasted/rewrote stuff to get 128-bit
sboxes from it. Now onto the theory :)
Some questions:
1. Explain the notation please :)
2. Can anyone explain why those sboxes are "provably"
cryptographically secure?
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: TC3 Update
Date: 2 Jun 2000 12:47:19 -0700
In article <[EMAIL PROTECTED]>,
tomstd <[EMAIL PROTECTED]> wrote:
> TC3 is a fairly simple cipher... Take a 128-bit block called X
> and do this
>
> for r = 0 to 3 do
> X = X + key[r]
> X = X^-1 mod p
> next r
>
> addition is done as four 32-bit units not a single 128bit word,
> and 'p' is a deg-128 polynomial (coefficients are mod 2).
If you replace addition by xor, the result can -- I think -- be attacked
with interpolation attacks. In particular, I believe there will be a,b,c,d
so that aXY + bX + cY + d = 0 for every plaintext/ciphertext pair (X,Y), and
thus with four known texts we may solve for a,b,c,d and break the variant.
Since addition is pretty close to xor (addition isn't very non-linear),
I'd be very concerned that interpolation attacks might apply to TC3, too.
(By the way, I hope you've noticed that the final application of p is useless:
it is unkeyed and thus can be removed by the cryptanalyst.)
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Contest rule proposal
Date: Fri, 2 Jun 2000 12:49:56 -0700
Trevor L. Jackson, III <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Relax.
>
> 1) Your position requires no defense.
>
> 2) The opposing position cannot be defended.
That is wonderful advice. I think I'll take it.
Thank You,
Paul
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Good ways to test.
Date: 2 Jun 2000 19:55:02 GMT
tomstd <[EMAIL PROTECTED]> wrote:
> What about provably secure block ciphers that use components with well
> understood structures, say CAST sboxes?
Apart from ciphers like the one-time pad, `provably secure' ciphers are
only secure against some attacks. In particular, note that some CAST
ciphers, not CAST-128, have been successfully broken using new attacks.
Similarly, one of Vaudenay's `decorrelated' designs, COCONUT98, was
cryptanalysed by David Wagner, using boomerangs.
-- [mdw]
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Contest rule proposal
Date: Fri, 2 Jun 2000 13:05:59 -0700
David A. Wagner <[EMAIL PROTECTED]> wrote in message
> Not true, actually. As Mark Wooding has pointed out, you can't test
> attacks (e.g., implement them) without implementing the cipher, and by
> law, you're not allowed to implement a patented cipher without a grant.
>
> You probably can't even implement parts of it, so forget your calculations
> of the difference table for the S-boxes, for instance.
One of us needs to do some research. I'll keep you company and do some too.
The applicability of patents is to commercial endevors to "Make, Use or
Sell"
That is:
"Make", The manufacturing of a product for sale or distribution.
"Use" A product to provide a service for hire or derive some advantage
therefrom.
"Sell" Even I understand that one.
An inventor has no legal standing or remedies from someone who is using
information in a patent in any way unless they commercialize it.
> Since the whole *point* of the cipher contest is to practice analysis,
> I can't see any reason to accept ciphers where analysis is prohibited.
I read nothing of the sort in the posts or the contest site.
------------------------------
** 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
******************************
