Cryptography-Digest Digest #704, Volume #11 Thu, 4 May 00 14:13:01 EDT
Contents:
Note on the Hill Cipher (Mok-Kong Shen)
Re: Interleaving for block encryption (wtshaw)
Re: Interleaving for block encryption (wtshaw)
Re: GPS encryption turned off (Doug Stell)
Re: Fingerprints and encryption (Runu Knips)
Re: about search and seisure of computers again (Anonymous Sender)
Re: Fixed: Sboxgen tool (Runu Knips)
Re: Fingerprints and encryption ("ink")
Re: Any good attorneys? (Paul Koning)
Re: Interleaving for block encryption (Paul Koning)
Re: GPS encryption turned off (Paul Schlyter)
Re: KRYPTOS Something new ? (Lincoln Yeoh)
Re: GPS encryption turned off ([EMAIL PROTECTED])
Re: Any good attorneys? (Joaquim Southby)
Re: public/private (Mike Rosing)
Re: RC6 as a Feistel Cipher (John Myre)
I saw this in /. and I thought of you (all) (arnold yau)
Re: Sample Output from SBOXGEN (Mike Rosing)
Re: Fixed: Sboxgen tool (Terry Ritter)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Note on the Hill Cipher
Date: Thu, 04 May 2000 17:25:22 +0200
Kahn commented in his book (p.407) in connection with the
Hill cipher that the matrix method is less secure than a
linear encipherment of the same amount of letters.
To illustrate, in
C = H * P
where C, H and P are n*n matrices, each element of the n^2
elements of C is dependent only on n elements of P. If the
n^2 elements of P are put into a vector U, then one can
use an n^2*n^2 matrix G to obtain an n^2 element vector V
according to
V = G * U
Here each element of V is dependent on n^2 elements of U.
However, computing with the larger matrix G is certainly
inconvenient, particularly if n is large.
One better way to achieve the purpose of higher dependency
of plaintext letters on ciphertext letters is to use two
n*n Hill matrices, thus
C = H1 * P * H2
As special cases, we can have
C = H * P * H
or
C = H * P * H^(-1)
where, as a variant, one may choose to replace one of the
H's by its transpose.
M. K. Shen
=============================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Interleaving for block encryption
Date: Thu, 04 May 2000 08:39:55 -0600
In article <[EMAIL PROTECTED]>, Mok-Kong Shen
<[EMAIL PROTECTED]> 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.
>
Chaining can be done effectively to produce an effective algorithm which
is stronger than one part alone. The produce strength can be less than
the sum of the parts, for instance an external tranposition stage combined
with DES might null-out part of the combined keyspace.
--
Laughter is often the most pleasing result of successful analysis.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Interleaving for block encryption
Date: Thu, 04 May 2000 08:47:00 -0600
In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn"
<[EMAIL PROTECTED]> wrote:
>
> 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.
You are still playing the odds. Besides, the bit demon seems to possess
you, which means that the meaning of the string 252726 is sure to escape
you....a riddle for the day to illustrate a point.
--
Laughter is often the most pleasing result of successful analysis.
------------------------------
From: [EMAIL PROTECTED] (Doug Stell)
Subject: Re: GPS encryption turned off
Date: Thu, 04 May 2000 15:11:12 GMT
On 4 May 2000 00:27:13 GMT, [EMAIL PROTECTED] (Paul Rubin) wrote:
>Doug Stell <[EMAIL PROTECTED]> wrote:
>>Also, they are trying to phase out the current encryption scheme and
>>go to a new one that is ultra-secure and ultra-secret. Not even the
>>GPS manufacturer or trusted manufacturer of crypto equipment is
>>allowed to know what it uses. It also supports Over The Air Rekey. The
>>idea is that some GI could leave his GPS receiver in a bar somewhere
>>and it will be useless in a very short time.
>
>Interesting. Are you saying they're going to rekey all the receivers
>*except* the one left in the bar? How?!
Yes, OTAR. The compromised receiver will simply revert to being an
inaccurate one in a short time. OTAR is done all the time in military
crypto.
>Of course it's just a matterof time before someone captures a unit
>and reverse engineers the algorithm.
Knowing the algorithm would be of no help, as any cryptographer would
assume. Also, the algorithm will be highly protected by physical
means, designed to prevent reverse engineering. Any attempt to access
it would destroy it before you get to it. To keep the algorithm away
from the GPS manufacturer, the operational code is squirted in by a
single facilitty AFTER the GPS unit is built, physically secure and
tested.
Personally and without any substantiating information, I believe that
this new approach is being put into place due to a compromise of the
keys for the current system. For satelites, it was common to store a
decade of Red keys in the bird, under the belief that they would be
physically secure in a geo orbit. There was a newpaper article about
another nation launching a satelite for a US party and having to blow
up the rocket. When the bird was recovered, the GPS was missing.
Blowing it up may have been a cover for stealing the GPS and its keys.
> Surely this has already been done (I mean by foreign
>intelligence agencies, not sci.crypt nerds) for the existing algorithm.
I am not sure if it has been fielded yet. By the way, the new scheme
is called SAASM.
------------------------------
Date: Thu, 04 May 2000 17:41:13 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Crossposted-To: alt.politics.org.cia,soc.culture.russian,soc.culture.nordic
Subject: Re: Fingerprints and encryption
"Markku J. Saarelainen" wrote:
> Actually too many suppliers seem to be limiting their offering to RSA
> and some Microsoft CryptoAPI (an element of their business startegy).
> This is very unfortunate, because you can have hundreds of other
> options. Actually, I may soon have a smartcard with thousand encryption
> algorithms in it ....
Thousands ? AFAIK smartcard only have small 8-bit processors and very
limited resources (memory etc).
------------------------------
Date: Thu, 4 May 2000 11:45:53 -0400
From: Anonymous Sender <[EMAIL PROTECTED]>
Subject: Re: about search and seisure of computers again
Crossposted-To: alt.privacy.anon-server,alt.privacy
jungle <[EMAIL PROTECTED]> wrote:
<snip>
'jungle', I don't know why this took me so long... *PLONK*
see ya.
------------------------------
Date: Thu, 04 May 2000 17:52:35 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Fixed: Sboxgen tool
Terry Ritter schrieb:
> No, that is not right. The desired situation is to have *about* half
> the bits change, not *at* *least* *half*.
And I think its impossible to build any function where at least
half of the bits changes between two possible inputs (except in
trivial cases).
------------------------------
From: "ink" <[EMAIL PROTECTED]>
Crossposted-To: alt.politics.org.cia,soc.culture.russian,soc.culture.nordic
Subject: Re: Fingerprints and encryption
Date: Thu, 4 May 2000 17:56:46 +0200
Runu Knips <[EMAIL PROTECTED]> wrote:
> "Markku J. Saarelainen" wrote:
> > Actually too many suppliers seem to be limiting their offering to RSA
> > and some Microsoft CryptoAPI (an element of their business startegy).
> > This is very unfortunate, because you can have hundreds of other
> > options. Actually, I may soon have a smartcard with thousand encryption
> > algorithms in it ....
>
> Thousands ? AFAIK smartcard only have small 8-bit processors and very
> limited resources (memory etc).
You mean, he's not in your killfile yet? ;-)
Rgds
Kurt
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: Any good attorneys?
Date: Thu, 04 May 2000 11:07:02 -0400
Mok-Kong Shen wrote:
> ...
> I mean that in all cases the insurance fees, if any, should be
> carried by NIST and not by the users of AES.
To be paid for by US taxpayers, for the protection of
people in random countries? That's not likely to be
accepted...
> 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?
You obviously don't know much about the patent process.
First of all, cryptographic skill is not relevant to
interpreting patents (except to the extent that you
think of legal language as "cryptic" :-) ).
Second, patents are interpreted by lawyers and judges and
the like, whose opinions are often based on limited if
any understanding of what they are dealing with and
what the state of the art is.
For an engineer, or reasonable facsimile, it is often
very hard to figure out why anyone would issue a patent
for "invention" X, never mind guessing what would happen
to such a patent if it is subject to legal challenges.
This argument also suggests that "patent insurance"
is likely to be impossible to get. Where are you
going to find an insurer dumb enough to write such
a policy?
paul
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: Interleaving for block encryption
Date: Thu, 04 May 2000 11:14:05 -0400
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.
No, it isn't. If I know you are doing, say, simple substitution
followed by DES (and you must assume I know that, Kerchoff's
rule) then I can test candidate plaintext by looking for
high Index of Coincidence values. While that adds a few
gates to the search engine, it's in no way "much more
difficult".
paul
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: GPS encryption turned off
Date: 4 May 2000 16:59:13 +0200
In article <8eraha$5rq$[EMAIL PROTECTED]>,
Paul Rubin <[EMAIL PROTECTED]> wrote:
> 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.
That's only because a TV satellite doesn't cover the whole world. It
usually doesn't even cover all of the visible hemisphere of the world.
Anyway, all satellite TV receivers within the "footprint" of that
satellite (or at least all those receivers which are used to receive
that satellite) will have a "window" within which its keys must be
updated. New keys are transmitted some time before they're starting
to get used, and perhaps some time after too. If you miss that
opportunity (e.g. because you never tuned in that satellite, for
instance because you were away for an extended period of time), you
may find that you can no longer decrypt that satellite TV channel.
If this happens, you will need to call your subscriber so they can
arrange for that new key to be transmitted again.
> 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.
The SmartCard used in satellite TV receivers is the equivalent of that
"secure hardware module".
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: [EMAIL PROTECTED] (Lincoln Yeoh)
Subject: Re: KRYPTOS Something new ?
Date: Thu, 04 May 2000 16:29:50 GMT
Reply-To: [EMAIL PROTECTED]
In the absence of feedback many systems oscillate or behave erratically.
Cheerio,
Link.
****************************
Reply to: @Spam to
lyeoh at @[EMAIL PROTECTED]
pop.jaring.my @
*******************************
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: GPS encryption turned off
Date: Thu, 04 May 2000 16:33:52 GMT
Nogami <[EMAIL PROTECTED]> wrote:
> If the pilot is within 50m of a terminal and is relying on GPS, I
> don't want to be on the plane :P
If the pilot's within 50m of the terminal, I should hope he's on the
ground, and following the ground guide's visual signals. ;)
Seriously though, it's important to remember that the difference
between 50m and 5m is a decent percentage, but in most gps
applications doesn't matter.
--
Matt Gauthier <[EMAIL PROTECTED]>
------------------------------
From: Joaquim Southby <[EMAIL PROTECTED]>
Subject: Re: Any good attorneys?
Date: 4 May 2000 16:57:10 GMT
In article <8WfQ4.10151$[EMAIL PROTECTED]> DD,
[EMAIL PROTECTED] writes:
>Why not send a very polite reply to RSA saying:
>you believe you are not violating their patent(s) as you live in Canada
>
I don't believe it's a matter of where he lives. If he is marketing or
distributing some product in a country where the patent is in effect,
that's what they will stake their claims on.
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: public/private
Date: Thu, 04 May 2000 11:00:41 -0500
James Thomson wrote:
>
> Does anyone know where I can get my hands on a few public/private
> encryption algorythms? I'm trying to gain a better view of the subject
> matter and determine how to make one myself, just for the hell of doing
> it.
Applied Cryptography has quite a few described as well as some source
code.
Patience, persistence, truth,
Dr. mike
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: RC6 as a Feistel Cipher
Date: Thu, 04 May 2000 11:05:20 -0600
"David A. Wagner" wrote:
>
> In article <[EMAIL PROTECTED]>, John Myre <[EMAIL PROTECTED]> wrote:
> > With respect to (mathematical) proofs, how is "Fiestel Cipher" defined?
>
> There's nothing really tricky here.
>
> Suppose a cipher may be written 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).
>
> Then the cipher is a Feistel cipher.
Ok, then
(1) When we say the cipher "may be written" does that mean we
are free to reformulate how it works as much as we want, as
long as we get the same plaintext <-> ciphertext mappings?
(2) Can f or + be round-dependant? Obviously the key is. I
suppose we can make f round-dependant anyway, by defining a
suitable "key expansion" algorithm, and an f that depends on
the "subkey" in the right way?
(3) Is the usual swap(L,R) at the end part of the definition,
or is it optional, or is it wlog or something?
Thanks -
John M.
------------------------------
From: arnold yau <[EMAIL PROTECTED]>
Subject: I saw this in /. and I thought of you (all)
Date: Thu, 04 May 2000 10:50:12 +0100
Basically some kind of cryto "challenge"... I'll leave you to read the
article.
(Sorry if I am a bit slow and everyone knew about this already...)
http://slashdot.org/articles/00/05/03/1843215.shtml
http://www.jdueck.org/challenge.html
thoughts and comments welcomed!
arnold
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Sample Output from SBOXGEN
Date: Thu, 04 May 2000 11:42:20 -0500
Tom St Denis wrote:
[*] Does SAC mean only half the bits change when an input changes or
*at
> least* half the bits change? I noticed one of the rules for DES sboxes
> is that 'at least' half the bits have to change...
It's a *probability* of 1/2. That means it can be damn close to 1/2 and
still count, like .499 or .501. So the real question is how do you
measure it?
Let's look at the input bits as b[i] and i runs from 0 ... m. Let's
call
the output bits s[j] and j runs from 0 ... n. Ritter quotes 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."
So what we have to do is pick any b and it's corresponding s as a
starting point.
Then flip one bit of b, say b[0], and find it's corresponding s, say
s'. find
s XOR s' and count the number of bits set. Divide this by n to get the
probability
of the number of bits that changed.
To get the total probability of the sbox, we need to find the average
probability
of the whole thing. Since there are m bits of input, there are 2^(m-1)
pairs to
check. Since division by n is constant in the above formula, we can
just perform
2^(m-1) sums over j of XOR's, then divide that by n*2^(m-1) and see how
close
that gets to .500000000000... to whatever precision you want.
To program this you might just want to count over b and use a mask table
to
mark off the pairs you've already done. There's probably a slick way to
do this,
so you might check Tavares' paper and see what he says.
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Fixed: Sboxgen tool
Date: Thu, 04 May 2000 18:06:53 GMT
On Thu, 04 May 2000 10:14:57 GMT, in <[EMAIL PROTECTED]>,
in sci.crypt Tom St Denis <[EMAIL PROTECTED]> wrote:
>Terry Ritter wrote:
>>
>> 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*.
>
>What is wrong when more then half change?
We're talking about Simple Substitutions, right? Then, over all
possible input values, and all possible changes to those values, we
expect to see a binomial distribution of bit-change results. That is
the statistical universe: There will be a case where all bits change,
and cases where only single bits change. But most cases will have
about half of the bits changing.
Testing for 1-bit changes is a subset of this testing. If we demand
that 1-bit-changes produce a (biased) result *over* the expected
distribution, we necessarily imply that multi-bit changes will become
biased *under* the expected distribution. That makes 1-bit changes
"special," and perhaps statistically identifiable. Any time we start
to deviate from the random expectation I get nervous. By "improving"
what we consider to be a weakness, we both signal the input event with
an output statistic and also "weaken" some other bit-change aspect
which we generally ignore.
I think it is possible in general to build s-boxes so that, say, 2
output bits change for any 1 input bit change. We then *hope* that
the difference in bit-change distribution will be hidden in the many
other bit-change possibilities. But not enforcing that hope makes me
very nervous. At the least we should then do additional checks, as in
*all* *but* 1 input change (walking '0' instead of walking '1').
Currently, I disagree with the approach, although one can understand
that in a Feistel cipher there would be some interest in "improving"
avalanche.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
** 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
******************************
