Cryptography-Digest Digest #701, Volume #11 Thu, 4 May 00 04:13:02 EDT
Contents:
Re: RC6 as a Feistel Cipher (Francois Grieu)
Re: Fixed: Sboxgen tool (Terry Ritter)
Re: GPS encryption turned off (Francois Grieu)
Re: Any good attorneys? (Jerry Coffin)
Re: Cipher Contest Update (Boris Kazak)
Re: A naive question (Mok-Kong Shen)
Re: Any good attorneys? (Mok-Kong Shen)
Re: Interleaving for block encryption (wtshaw)
Re: Any good attorneys? (Mok-Kong Shen)
kryptos ([EMAIL PROTECTED])
Re: Any good attorneys? (Mok-Kong Shen)
Re: Silly way of generating randm numbers? (Richard Heathfield)
Re: Interleaving for block encryption (Mok-Kong Shen)
Re: Any good attorneys? (Richard Heathfield)
Re: Silly way of generating randm numbers? (Mike Oliver)
Re: Silly way of generating randm numbers? ("Douglas A. Gwyn")
KRYPTOS Something new ? (Collomb)
Re: quantum crypto breakthru? ("Douglas A. Gwyn")
Re: Interleaving for block encryption ("Douglas A. Gwyn")
Re: GPS encryption turned off (Paul Rubin)
Re: KRYPTOS Something new ? ("Douglas A. Gwyn")
----------------------------------------------------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Re: RC6 as a Feistel Cipher
Date: Thu, 04 May 2000 06:46:01 +0200
[EMAIL PROTECTED] (David A. Wagner)
defines a Feistel Cipher
> as a composition of "rounds", where each round encrypts the
> input (L,R) to the output (R,L+f(R)) for some key-dependent
> function f and some group operation + (both of which may
> possibly depend on the round number).
The definition 7.81 in the Handbook of Applied Cryptography is
with XOR as the group operation. This might be a significant
difference.
As a minor aside, HAC makes f of the form f(R,Ki) with f
independant of the round number, but that can be fixed:
simply include information on the round number in Ki.
Francois Grieu
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Fixed: Sboxgen tool
Date: Thu, 04 May 2000 05:25:53 GMT
On Thu, 04 May 2000 02:13:35 GMT, in <[EMAIL PROTECTED]>,
in sci.crypt Tom St Denis <[EMAIL PROTECTED]> wrote:
>Tim Tyler wrote:
>>
>> Tom St Denis <[EMAIL PROTECTED]> wrote:
>>
>> : [...] The SAC test actually works now. I misunderstood the changed bit
>> : count must equal have the output size, it's suppose to be at least
>> : half.
>>
>> This doesn't sound /quite/ right to my ears:
>>
>> SAC says that if you flip a particular input bit, half the output bits
>> flip - *if you consider all possible input vectors*.
>
>I do a double loop
>
>for x = 0 to n-1
> for y = 0 to log2(n)
> if HT[f(x) xor f(x xor (1 << y))] < log2(n)/2
> return non_sac.
>
>> In other words, the /probability/ of each output bit flipping, on flipping
>> any input bit, is 1/2.
>
>Well I think you can get by checking that at least half the bits change
>when one input changes.
No, that is not right. The desired situation is to have *about* half
the bits change, not *at* *least* *half*.
See, for example:
http://www.io.com/~ritter/VSBC.HTM#Diffusion
from late 1995. And the more recent Glossary:
http://www.io.com/~ritter/GLOSSARY.HTM#StrictAvalancheCriterion
'Strict Avalanche Criterion (SAC)'
'As introduced in Webster and Tavares:
"If a cryptographic function is to satisfy the strict avalanche
criterion, then each output bit should change with a probability of
one half whenever a single input bit is complemented." [p.524]
Webster, A. and S. Tavares. 1985. On the Design of S-Boxes.
Advances in Cryptology -- CRYPTO '85. 523-534.
Although the SAC has tightened the understanding of "avalanche,"
even SAC can be taken too literally. Consider the scaled-down block
cipher model of a small invertible keyed substitution table: Any input
bit-change thus selects a different table element, and so produces a
random new value (over all possible keys). But when we compare the new
value with the old, we find that typically half the bits change, and
sometimes all the bits change, but never is there no change at all.
This is a tiny bias toward change.
>Which bits change is upto the linearnity of the
>function. Obviously if it's non-linear it will be a random subset of
>bits that change.
Not necessarily.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Re: GPS encryption turned off
Date: Thu, 04 May 2000 07:43:42 +0200
[EMAIL PROTECTED] (Paul Rubin) wrote:
> Are you saying they're going to rekey all the receivers
> *except* the one left in the bar? How?!
A possible solution:
In each receiver store a permanent serial number j and a
rekeying key KRj derived from a master rekeying key KR
as KRj = ENC(KR,j). KRj is called a diversified key.
Have the global (!) current traffic key Kt used to encipher
the bulk of the traffic at a given time sent over the air as
multiple (j, Ktj = ENC(ENC(KR,j),Kt)) pairs, for those sole
receivers j you want to rekey (i.e. are white-listed).
Each receiver tests i in a received pair (i,Kti) against
it's own j, and if it matches decodes Kt = DEC(KRj,K).
I whish my own company will not sue me for not checking this
is not patented :-)
Francois Grieu
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: Any good attorneys?
Date: Wed, 3 May 2000 23:50:44 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
[ ... ]
> An essential question, I think, is by how much a variant of a patented
> algorithm must deviate from the patented algorithm before it is no longer
> considered to be an imfringement of the patent?
That depends. A patent contains a set of claims that describe
exactly what the patent covers. To infringe a patent, you have to
use each element (or a reasonable equivalent of it) that's described
in at least one independent claim of the patent.
In any case, it's up to the person applying for the patent to decide
how general of a patent they want to try to get. The more general it
is, the more likely the patent office is to reject the patent on the
basis that it's been done before. At the opposite extreme, a patent
that's extremely narrow is easier to get, but also likely to be
easier to avoid infringing while doing essentially the same thing.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Cipher Contest Update
Date: Thu, 04 May 2000 06:26:26 GMT
[EMAIL PROTECTED] wrote:
>
> Hi,
>
> Is there any place where we can access and view the analysis and
> comments on the ciphers? For example Matt Fisher's comments on LETSIEF?
>
> Raphael
>
=========================
Originally we tried to post these comments to the group, but they
expire pretty quickly.
If you so desire, I can mail you all the messages exchanged between
Matthew and myself (sorry, I don't yet have a WWW page).
Best wishes BNK
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: A naive question
Date: Thu, 04 May 2000 08:59:47 +0200
William Rowden wrote:
> My answer is therefore "exhaustive key searches may produce false
> solutions unless the amount of ciphertext is beyond the unicity distance
> of the cipher."
If finding a meaningful text and a second block also produce meaningful
text, then it is quite sure that one has found the correct key, though it
is not absolute 'proof'. Am I right?
If a k bits key is used in a block cipher to encrypt n blocks of k bits
each,
then the protection evidently decreases as n increases, since the opponent
with larger n has more material, which, at least in case of brute forcing,
can be processed in parallel.
If a block cipher is used to encrypt only one block of k bits with a k bits
key, then the protection depends on whether its design of the block cipher
is such that for a given ciphertext the 2^n different keys lead to 2^n
different plaintexts on decryption. If yes, then the encryption is as good
as
using OTP with xor, otherwise it is weaker. I suppose this view is also o.k.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Any good attorneys?
Date: Thu, 04 May 2000 08:59:38 +0200
"Trevor L. Jackson, III" wrote:
> Jeffrey Williams wrote:
>
> > Choose your fights wisely. Very few people can take on the world and win.
>
> There's a few major differences between "taking on the world" and "standing your
> ground". First and foremost the TOTW is probably silly under any circumstances,
> while SYG is a reasonable default. So they are close to polar opposites.
>
> Another major difference is that TOTW is an offensive goal while SYG is almost
> purely defensive. The defense always has a significant advantage. In this case it
> has a huge advantage because Tom probably broke and RSA isn't. So RSA can't win
> much, but Tom can. Any lawyer worthy of a contingency fee will smile at that. And
> RSA's lawyer is probably going through the motions of protecting RSA's IP because
> it is good form to do so no matter who the infringer is.
>
> But it may all be moot if the only focus is RC5.
There is indeed a problem if in a law case the opposing parties have
different financial resources available. The one can appeal to a higher
court, while the other may be at the end of his money. In the present
case, I think the best is for Tom St Denis to write back with one single
and very clear sentence that he finds out that the algorithm is not patented
and hence it is open for free use by anyone in Canada, period. It would
be interesting to see what the commercial guys respond. One then
publishes all the correspondences on the web page together with the
algorithm.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Interleaving for block encryption
Date: Thu, 04 May 2000 00:00:50 -0600
In article <[EMAIL PROTECTED]>, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
> It is my humble opinion though that any message that really needs
> security protection should have an encryption of its own and not rely
> on encryption en masse.
>
The shorter the message, the lamer the forms of crypto that will work.
While some say it is overkill to use a cipher stronger that that which you
need, best to have a margin of error and make contents any length shorter
than that necessary to produce obvious good plaintext results.
The problem with most forms of crypto that are being pushed is that it
does not take must message to satisfy Shannon. Therefore, if size of
keyspace is your idea of strength, a lucky guess can do you in. It makes
better sense to avoid that possible fatal error with a better choice of
algorithm that allows you to really work subrosa.
--
Laughter is often the most pleasing result of successful analysis.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Any good attorneys?
Date: Thu, 04 May 2000 09:02:19 +0200
Mok-Kong Shen wrote:
>
> I wonder whether it woundn't be a good idea to request that
> NIST arranges for an insurance of there being no unknown
> patent involvement in the AES winner. For if AES successfully
> replaces DES and 3DES and gets widely used, it would be a
> catastrophe should someday some person stands up and demands
> big amounts of patent loyalties. This scenario is not 'virtual'.
> I remember that in connection with the Y2K problem there was
> a person who demanded loyalties form firms that offered Y2K
> services. (I don't know how the story ended.) With an
> insurance, the insurance company would have to come up with
> the payments. It is fairly concevable that no insurance
> company would venture to enter such deals. In that case a
> viable alternative would be that NIST, which knows the best
> about AES, does the insurance itself. If nobody is ready to
> do the insurance, then it is clear to the users of AES that
> there is very substantial chance of having oneday to pay
> patent loyalties of yet unknown amount.
Addendum:
I mean that in all cases the insurance fees, if any, should be
carried by NIST and not by the users of AES. Actually, I don't
think it is difficult at all for NIST to give a guarantee
statement that AES will not involve patent problems, since
it certainly has experts in patents and can do a very
careful check. If that relatively simple task couldn't be done,
how could one count on the strength of AES at all?
M. K. Shen
------------------------------
From: [EMAIL PROTECTED]
Subject: kryptos
Date: Thu, 04 May 2000 06:52:15 GMT
I've finished the Specialists directory of University Mathematics
department websites with contact info.
The Library containing grad level papers on Mathematics is completed.
Currently, I'm working on the Archives section which will be a subject
based directory (no search engine) providing links to many topics, but
under Physics: People of, History of, and other.
If you have any Math and Crypto sites that should be posted, please
email me at [EMAIL PROTECTED]
You can visit the site at http://www.Great-Mind.com Your assistance is
appreciated, thank you.
-Jeanette
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Any good attorneys?
Date: Thu, 04 May 2000 09:07:30 +0200
Jerry Coffin wrote:
> That depends. A patent contains a set of claims that describe
> exactly what the patent covers. To infringe a patent, you have to
> use each element (or a reasonable equivalent of it) that's described
> in at least one independent claim of the patent.
Tahnks. I suppose you mean 'one element' instead of 'each element'.
M. K. Shen
------------------------------
Date: Thu, 04 May 2000 08:07:38 +0100
From: Richard Heathfield <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Silly way of generating randm numbers?
Tom St Denis wrote:
>
> Richard Heathfield wrote:
> >
> > Julio César wrote:
> > >
> > > I dont know if this could help, but pi is in no way random.
> > >
> >
> > For a contrary viewpoint, see Knuth, TAOCP, Vol II, p41.
>
> Actually he begins that chapter by noticing the patterns in pi....
...just as we can notice patterns in /all/ numbers, and Knuth is
showing, therefore, that we are not qualified to judge whether a number
is random merely by looking at it. I think you're paying undue attention
to Knuth's quote of I. J. Matrix, presumably a Martin Gardner pseudonym,
which mentions the "numerology" of pi.
> not a good counterexample.
Why not? As far as I'm aware, pi passes all mathematical tests for
randomness.
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
35 K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html (62
to go)
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Interleaving for block encryption
Date: Thu, 04 May 2000 09:17:54 +0200
wtshaw wrote:
> <[EMAIL PROTECTED]> wrote:
>
> > It is my humble opinion though that any message that really needs
> > security protection should have an encryption of its own and not rely
> > on encryption en masse.
> >
> The shorter the message, the lamer the forms of crypto that will work.
> While some say it is overkill to use a cipher stronger that that which you
> need, best to have a margin of error and make contents any length shorter
> than that necessary to produce obvious good plaintext results.
>
> The problem with most forms of crypto that are being pushed is that it
> does not take must message to satisfy Shannon. Therefore, if size of
> keyspace is your idea of strength, a lucky guess can do you in. It makes
> better sense to avoid that possible fatal error with a better choice of
> algorithm that allows you to really work subrosa.
It is my intuitive belief that using a weak cipher, e.g. a simple
transposition,
to pre-process the plaintext before feeding it to a good block cipher ( i.e.
one has now a superencryption) essentially contritutes to defeating the
opponent's brute forcing, since it is much more difficult now for him to
know whether the key he tries is correct.
M. K. Shen
------------------------------
Date: Thu, 04 May 2000 08:12:08 +0100
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: Any good attorneys?
Mok-Kong Shen wrote:
>
> There is indeed a problem if in a law case the opposing parties have
> different financial resources available. The one can appeal to a higher
> court, while the other may be at the end of his money. In the present
> case, I think the best is for Tom St Denis to write back with one single
> and very clear sentence that he finds out that the algorithm is not patented
> and hence it is open for free use by anyone in Canada, period. It would
> be interesting to see what the commercial guys respond. One then
> publishes all the correspondences on the web page together with the
> algorithm.
Bear in mind that the copyright in private correspondence lies with the
sender. It is, strictly speaking, illegal to put privately received
correspondence onto your Web site without the permission of the sender.
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
35 K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html (62
to go)
------------------------------
From: Mike Oliver <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Silly way of generating randm numbers?
Date: Thu, 04 May 2000 00:16:28 -0700
Richard Heathfield wrote:
> Why not? As far as I'm aware, pi passes all mathematical tests for
> randomness.
In some informal sense that may be true. But I can think of at
least one "mathematical test for randomness" that it doesn't
pass. Specifically, the linear correlation between the digits
of a random number, and the digits of pi, should approach zero
as the number of digits considered goes to infinity.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Silly way of generating randm numbers?
Date: Thu, 04 May 2000 07:40:59 GMT
almis wrote:
> Douglas A. Gwyn wrote in message <[EMAIL PROTECTED]>...
> |Presumably, any actual implementation of this method would have to
> |pick some parameters, so the irreproducibility of the method would
> |be no better than the irreproducibility of the parameter selection.
> Yea ! That's right.
> We choose two parameters, a and b.
> We let it be known that a is a positive integer, not 0 or 1.
> Furthermore, b is a real quadratic irrational.
> We then generate a transcendental number a^b.
> ...
But to actually do this in practice, b would at best be represented
in a form suitable for symbolic arithmetic based on integer codes
(since computers cannot represent all real numbers in even a finite
range). So it seems to boil down to picking a collection of integer
parameters, which would be limited in practice to a (possibly large)
finite set of choices that could in principle be tested for a match.
------------------------------
From: [EMAIL PROTECTED] (Collomb)
Subject: KRYPTOS Something new ?
Date: 4 May 2000 07:43:47 GMT
KRYPTOS Something new ?
I am writing from France. I am passionately fond of Kryptos which is an
enigma still not revealed, dissimulated in a text of 5 series of letters
<or characters> which decorates a sculpture of Jim Sanborn, located at
the heart of the CIA in Langley <Virginia >.
One year ago, American medias, newspapers and TV, published articles
saying that three senior cryptographers had deciphered most of the Kryptos
secrecy, except the last fifth part comprising 97 characters.
If, after one year past, these 97 characters were still not deciphered, it
is possible to doubt the accuracy of the work of these three decipherers.
For these three ones, they resort obviously to the system of coding of
the French Vigenere, since, on one face of the sculpture, appears a square
which points out this system of encoding. But this is only a decoy to
lead astray some researchers ....full of cryptographic science..
A child who would have been placed in front of the sculpture, would say
he does not know Vigenere at all, he would see only one square filled
with characters. As the first series of Kryptos comprising 100
characters, it immediately comes to the child¹s mind to build one square
of 10 X 10 = 100 characters. I have followed this simple idea to the
very end. For deciphering the 97 last characters, it is necessary to
resort to a trick , seldom met
in < industrial > cryptography, consisting in adding the three
characters of the word GOD. This addition of GOD is suggested by the
preceding decipherings.
It is necessary to give a glance, without preconception, on Kryptos to
discover its hidden sense. Kryptos is not only a cryptographical one but
also and above all a <PUZZLE>.
Let us add that Sanborn is not a cryptographer but an artist who
naturally privilegies the forms.
I offer on my website :
http://calvaweb.calvacom.fr/collomb /
a complete and original solution of entire Kryptos, which precisely is
based on the forms.
Best regards
[EMAIL PROTECTED]
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: quantum crypto breakthru?
Date: Thu, 04 May 2000 07:48:02 GMT
Danilo wrote:
> ... So, he will use quantum cryptography, and send the information
> to his bosses. But, when he will send the cipher ray of light,
> Russians will catch it and read it. So, CIA (or the diplomat) will
> know that someone (probably Russians had read the message), ...
No, that's not how quantum cryptography is (usually) designed.
What is exchanged in an intrusion-detectable manner is the *key*
to be used for a conventional encryption. Sender and receiver
can negotiate a key stream that has only a negligible fraction
stolen by an eavesdropper. Protocols for doing that are tedious
and (in my opinion) not very interesting; the important thing is
that eavesdropping is detected (with high reliability). The
message is then sent using the secure key (e.g. by simple XOR
of the bit streams) over any non-secure channel; it's in effect
a one-time pad system with a quantum solution to the key
distribution problem.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Interleaving for block encryption
Date: Thu, 04 May 2000 07:52:45 GMT
Mok-Kong Shen wrote:
> It is my intuitive belief that using a weak cipher, e.g. a simple
> transposition,
> to pre-process the plaintext before feeding it to a good block cipher ( i.e.
> one has now a superencryption) essentially contritutes to defeating the
> opponent's brute forcing, since it is much more difficult now for him to
> know whether the key he tries is correct.
But any block cipher worth using is not going to be cracked using
key-guessing methods. Historically, systems have combined two
forms of encryption such as codebook+polyalphabetic_substitution,
and cryptanalysts have found ways to more or less routinely strip
off one of the layers of encryption so that they could work on the
other. In the context of modern block ciphers, any extra key bits
would be better used in a single integrated encipherment than
split between two orthogonal encipherments.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: GPS encryption turned off
Date: 4 May 2000 07:57:30 GMT
In article <[EMAIL PROTECTED]>, Nicol So <see.signature> wrote:
>> Interesting. Are you saying they're going to rekey all the receivers
>> *except* the one left in the bar? How?!
>
>It's not that difficult. Periodic rekeying of all authorized receiver
>units is routinely done in satellite TV.
I don't think it's the same situation. Satellite TV's don't have to
be rekeyed under battlefield conditions and they don't have to be
simultaneously rekeyed all over the world. Anyway, sooner or later
a receiver will be captured or lost and *not* reported missing/gone.
The current rekeying system (keys are encapsulated in secure hardware
modules which have to be physically replaced in the receiver) avoids
that problem and I thought that was part of the intention.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: KRYPTOS Something new ?
Date: Thu, 04 May 2000 08:02:47 GMT
Collomb wrote:
> If, after one year past, these 97 characters were still not
> deciphered, it is possible to doubt the accuracy of the work
> of these three decipherers.
Not when the sculptor and the cryptographer who created the
cipher text have verified the correctness of that work!
97 characters is not much material to work with if the
encipherment is (as suggested by the evidence) in a system
somewhat harder than the ones used in the first three parts.
Most likely a breakthrough will require a lucky guess about
the method and one or more keywords used in constructing
the enciphering alphabets.
------------------------------
** 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
******************************
