Cryptography-Digest Digest #37, Volume #12 Thu, 15 Jun 00 15:13:01 EDT
Contents:
Re: Can we say addicted? (Mike Rosing)
Re: RIP Bill 3rd Reading in Parliament TODAY 8th May (JimD)
Re: salt length? (David A. Wagner)
Re: salt length? (David A. Wagner)
Re: GeekPress: Will Cyber Criminals Run the World? (Mike Rosing)
Serpent S-Boxes question (Dido Sevilla)
Re: Cipher design a fading field? (Norman D. Megill)
Re: Def of "nonlinear order" (Mike Rosing)
Re: small subgroups in Blum Blum Shub ([EMAIL PROTECTED])
Re: quantum cryptography at nytimes.com (Bill Unruh)
Re: Def of "nonlinear order" (tomstd)
Re: Random sboxes... real info (David A. Wagner)
Re: Random sboxes... real info (tomstd)
Those darn sboxes (tomstd)
Re: public/private encryption keys and biometrics (Peter Pearson)
Re: Cipher design a fading field? (James Felling)
----------------------------------------------------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Can we say addicted?
Date: Thu, 15 Jun 2000 12:09:11 -0500
Tim Tyler wrote:
>
> tomstd <[EMAIL PROTECTED]> wrote:
> : <[EMAIL PROTECTED]> wrote:
>
> :>http://www.terracom.net/~ereserch/float/movie and
> :>http://www.terracom.net/~ereserch/float/movie2
>
> : Dude I got a four-oh-four.
>
> The correct URLs are:
>
> http://mendota.terracom.net/~eresrch/float/movie/
> http://mendota.terracom.net/~eresrch/float/movie2/
>
> I still can't help thinking Mike should try some bigger doses ;-)
Yeah, I'm gonna need it for asking my ISP why tom has problems :-)
The DNS is supposed to do that translation for ya tom. mendota isn't
always up (but the lake is over full right now :-)
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED] (JimD)
Subject: Re: RIP Bill 3rd Reading in Parliament TODAY 8th May
Reply-To: JimD
Date: Thu, 15 Jun 2000 16:11:49 GMT
On 15 Jun 2000 15:15:38 GMT, [EMAIL PROTECTED] (MagiconInc) wrote:
>What if the key is material which it is illegal to disclose under the Official
>Secrets Act? Is one obliged to disclose it, or not?
It would appear that if it is in the public interest, you may
disclose such material. Believe it or not!
--
Jim Dunnett.
g4rga at thersgb.net
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: salt length?
Date: 15 Jun 2000 10:15:33 -0700
In article <[EMAIL PROTECTED]>,
Mark Wooding <[EMAIL PROTECTED]> wrote:
> > You should feed the RC4 key schedule the hash of the password and
> > salt.
>
> Why? RC4's key schedule can cope with a reasonably-sized password and a
> salt just fine.
Actually, I, too, would recommend pre-hashing the password and salt
and feeding only the result to RC4's key schedule.
RC4's key schedule has some funny properties when fed with non-random
keys, especially with multiple related keys, and I'm not sure how much
to trust it for that use.
Even if you spin it a bunch of extra times (which is probably slower
than just doing the hash), I'm not entirely convinced RC4's key schedule
is strong enough for these purposes. Why take any chances?
The safe, conservative thing to do is to pre-hash, IMHO.
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: salt length?
Date: 15 Jun 2000 10:21:06 -0700
> The `right' solution would seem to be to use a pseudo-random function,
> keyed from the supplied password and salt, to fill RC4's 256-byte key
> space.
I hope you mean, a pseudo-random function F keyed by the secret key
material and applied to the salt, e.g., F_k(salt).
Feeding non-secret information into the key port of a pseudo-random
function violates the security warranty, and all bets are off. (It's not
too hard to construct an explicit example of a secure pseudo-random
function that breaks when used this way.)
(Actually, even a pseudo-random function is probably not enough if your
keying material is a password, because pseudo-random functions are only
guaranteed secure if you feed in uniformly-distributed key material,
and passwords usually don't fulfill this condition.)
> But we have a pseudo-random function: RC4! (Well, it's at least
> as good as RC4 is, anyway.) So why don't we just use that? ;-)
No, RC4 is a pseudo-random generator G : key |--> output, not a
pseudo-random function F : (key,input) |--> output. As stated in my
comments above, a pseudo-random generator is insufficient; you need a
full pseudo-random function.
> > The salt should be long enough so that's it's never used twice (with
> > high probability). If you are sending a message a day then just use
> > the time_of_day in seconds.
>
> No. It also needs to be long enough to dissuade precomputed dictionary
> attacks.
Yup, good point. And, choosing an extra-long salt doesn't really cost
you anything, so it seems like good practice.
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: GeekPress: Will Cyber Criminals Run the World?
Date: Thu, 15 Jun 2000 12:26:44 -0500
zapzing wrote:
> If you know about a retail source of
> inexpensive DES chips, please let
> me know, thanks.
You can get DES and 3-DES cores for about $10k. See Xilinx and Xentec.
www.xilinx.com/ipcenter has data sheets.
Patience, persistence, truth,
Dr. mike
------------------------------
From: Dido Sevilla <[EMAIL PROTECTED]>
Subject: Serpent S-Boxes question
Date: Fri, 16 Jun 2000 01:27:11 +0800
I'm in the process of writing a compact implementation of Serpent to run
on the Am186 microcontroller (a 16-bit 80x86-equivalent processor), and
there are a number of things I don't quite understand about the
implementations. Reading through the algorithm description, it says
that an efficient way of implementing it would be a bit slice method,
applying a sequence of logical operations on a 32-bit chunk of data at a
time which would be equivalent to actually applying the S-boxes to each
4-bit chunk of the word. I wrote code that does this, using a lookup
table based on the S-boxes described in section A.5 of the algorithm
specification. But the code comes up with different results from the
results of applying the S-box macros used in the bitslice implementation
on disc 2 of the Serpent submission code.
My code, which uses a lookup table to compute the S-boxes, gives, when
applying S-box 0 to the data: 0x01234567 0x89abcdef 0xfedcba98
0x76543210, comes up with:
0xfc27905a 0x1be86d34 0x43d68eb1 0xa50972cf
My understanding of how the S-boxes should work tells me that these
results are correct. It's also consistent with the code to apply
S-boxes in the reference implementation.
The C macro that is used by the optimized ANSI C implementation of
Serpent (in the second floppy), applying S-box 0 (macro RND00 in
serpentsboxes.h) to the same data, gives:
0xffffffff 0x76543210 0xfedcba98 0x00000000
What is going on here? Do the RNDxx macros actually apply the S-boxes as
I understand from the algorithm specification paper? If my
understanding is flawed, then my implementation is also bogus... *sigh*
I'd much rather use a lookup table to compute the S-boxes rather than
write code to implement the S-boxes manually, because it makes for much
smaller code. The lookup table code is only 16 instructions long, and
the lookup tables for the S-boxes are a total of 128 bytes. Each S-box
would probably require as much code to support it, so the lookup table
may be more efficient, space-wise.
--
Rafael R. Sevilla <[EMAIL PROTECTED]> +63 (2) 4342217
ICSM-F Development Team +63 (917) 4458925
University of the Philippines Diliman
------------------------------
From: [EMAIL PROTECTED] (Norman D. Megill)
Subject: Re: Cipher design a fading field?
Date: 15 Jun 2000 13:32:39 -0400
In article <[EMAIL PROTECTED]>, Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
>Tim Tyler wrote:
>> This is irrelevant - a program exists which specifies which program
>> halts, and which does not.
>
>No, there is no such program.
>If there were, we could apply it to the rather small program that
>tests successive combinations of integers (in increasing order) and
>halts when it finds one for which Goldbach's conjecture is false.
>That would settle Goldbach's conjecture one way or the other.
There exists a program to determine the halting of any program whose
executable code AND DATA are confined to a finite number of bits. This
is because there are a finite number of possible states that the program
and its data can be in. Eventually any program will either halt or
cycle back to some previous state.
In the case of the Goldbach conjecture, integers can grow without bound,
potentially requiring an infinite amount of memory.
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Def of "nonlinear order"
Date: Thu, 15 Jun 2000 12:41:29 -0500
tomstd wrote:
>
> I am confused now (uh-oh) I thought the nonlinear order of a
> function can be computed using a modification of the Bit
> Independence Criterion (BIC). For example a function is
> nonlinear to the order r if for all masks with a hamming weight
> of 2..r you can perform a BIC test and pass.
>
> For example the mask '3' would be 11 in binary and mean to test
> the first and second nx1 sboxes. 7 would be 111 and mean to
> test the first three.
>
> In otherwords no r-tuple of nx1 sboxes are linearly dependent.
>
> If this is the case then the findings of Knudsen and Jakobsen
> are wrong when they discuss the nonlinear order of cubics and
> quadratics (etc) in GF(2^n). For my 20 sboxes I posted earlier
> they were found to be perfectly nonlinear upto 7-tuples of 8x1
> sboxes...
I have no idea what you're talking about, so I expect that by the
time you explain it to me you'll have figured out the problem :-)
Linearly dependent means we can build a function from the sboxes
with constant coefficients. I don't understand what you mean by
"nonlinear order". If you build a function with powers of sboxes
(is that what qudratics and cubics mean?) then it's automaticly
nonlinear.
For example, if S(x) = x1 + x2 + x3 is the sum of 3 sboxes, it's
linear. If S(x) = x1^2 + x2^3 + x3^5 it's nonlinear. The order
of S is 5 in this case. Is that what you mean?
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: small subgroups in Blum Blum Shub
Date: Thu, 15 Jun 2000 17:47:48 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Terry Ritter) wrote:
> >> Blum, L., M. Blum and M. Shub. 1983. Comparison of Two
> >> Pseudo-Random Number Generators. Advances in Cryptology:
> >> CRYPTO '82 Proceedings. Plenum Press: New York. 61-78.
Does anyone know an electronically available source for this paper?
Ok.I learned an important lesson --- Bruce might be good, but he doesn't
have the space nor the time in his books to completely cover material.
Relying on the one source is a Bad Idea.
Terry, thank you for the wonderful resources on your web page.
So, now, back to square one; BB&S had the property of being 'indexable'
such that one could request a particular output. I would very much like
to keep this property. Are there any other PRNGs available with this
property?
My current thinking is to use an HMAC construction to generate these
things. By using a key with an 'index' being simply tossed into HMAC
as-is, my gut feeling tells me I can get reasonably random-looking
numbers out of it, with low ability to predict from a lot of known
outputs to another output (thanks to our key).
Have I missed something similarly blatant with this construction?
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: quantum cryptography at nytimes.com
Date: 15 Jun 2000 18:03:34 GMT
In <[EMAIL PROTECTED]> Roger Schlafly <[EMAIL PROTECTED]>
writes:
>So they want to use quantum crypto to generate a random key,
>and then use it as a pure OTP. Dumb idea, and it will never
>happen. Banks would be better of sticking with (single) DES.
??? That is how quantum crypto works. It is a key exchange mechanism
with an inherent eavesdropping detection.
They would be better sticking with DES for what purpose? So outsiders
could crack the system?
------------------------------
Subject: Re: Def of "nonlinear order"
From: tomstd <[EMAIL PROTECTED]>
Date: Thu, 15 Jun 2000 11:10:10 -0700
In article <[EMAIL PROTECTED]>, Mike Rosing
<[EMAIL PROTECTED]> wrote:
>tomstd wrote:
>>
>> I am confused now (uh-oh) I thought the nonlinear order of a
>> function can be computed using a modification of the Bit
>> Independence Criterion (BIC). For example a function is
>> nonlinear to the order r if for all masks with a hamming
weight
>> of 2..r you can perform a BIC test and pass.
>>
>> For example the mask '3' would be 11 in binary and mean to
test
>> the first and second nx1 sboxes. 7 would be 111 and mean to
>> test the first three.
>>
>> In otherwords no r-tuple of nx1 sboxes are linearly dependent.
>>
>> If this is the case then the findings of Knudsen and Jakobsen
>> are wrong when they discuss the nonlinear order of cubics and
>> quadratics (etc) in GF(2^n). For my 20 sboxes I posted
earlier
>> they were found to be perfectly nonlinear upto 7-tuples of 8x1
>> sboxes...
>
>I have no idea what you're talking about, so I expect that by
the
>time you explain it to me you'll have figured out the problem :-
)
>
>Linearly dependent means we can build a function from the sboxes
>with constant coefficients. I don't understand what you mean by
>"nonlinear order". If you build a function with powers of
sboxes
>(is that what qudratics and cubics mean?) then it's automaticly
>nonlinear.
>
>For example, if S(x) = x1 + x2 + x3 is the sum of 3 sboxes, it's
>linear. If S(x) = x1^2 + x2^3 + x3^5 it's nonlinear. The order
>of S is 5 in this case. Is that what you mean?
I actually am not sure. In Knudsens paper on Interpolation
Attacks they discuss nonlinear order but never define it.
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: Random sboxes... real info
Date: 15 Jun 2000 11:11:40 -0700
Nope, I stand by my statement.
You might want to think about this more carefully. Here's a useful
thought experiment. Consider the following two universes:
Universe A: We encrypt using a permutation chosen uniformly at random
from the set of all permutations.
Universe B: We encrypt using a permutation chosen uniformly at random
from everything but the identity permutation.
I claim that (A) is strictly stronger than (B).
The way to think about this is to look for an attack that lets you
read encrypted traffic. If you can find an attack which works strictly
better against (A) then (B), you will have proven your point. I claim
you can't. Have a try! :-)
To give a feeling for it, let me debunk the proposed attack you sketched:
> An OTP is used once. A block cypher may potentially be used to encypher
> *many* blocks. If the permuting transform used is the identity
> transformation, the analyst is likely to notice this at once in (say) ECB
> mode. The cyphertext *is* the original plaintext. *No* other permutation
> would have this effect over a number of blocks of differnet plaintext.
Careful here! I think you haven't thought this through deeply enough.
Consider, as a representative example, the following scenario. You have
some known plaintext/ciphertext pairs; let's say you know that "foo"
encrypts to "foo", and "bar" encrypts to "bar". Now you have a third
ciphertext C of unknown decryption, and you want to find the corresponding
plaintext P. (If you can't find any information P, you don't have an attack.)
What possibilities are there for P?
Obviously, P can be anything except "foo" and "bar". Moreover, in (A),
all the possibilities are _equally likely_. The reason is that all
(2^n - 2)! permutations of the remaining 2^n - 2 elements of the plaintext
space can be permuted in every way, and each such possibility is equally
likely. In other words, we get _no_ information whatsoever on P, in
Universe A.
Universe B, however, is slightly different. The identity permutation
is impossible in (B), so only (2^n - 2)! - 1 of the permutations of the
remaining elements are possible. In other words, P has an ever-so-slight
bias: Prob[P=C] < Prob[P=x] for all x != C. So, in Universe B, we do get
a teeny bit of extra information on P: the values other than "foo", "bar",
and C are slightly more likely to be the plaintext than C is.
(If this isn't clear, go do the math, crunch the numbers, and compare.)
This shows that your proposed attack does not in fact work; you get more
information about the unknown plaintext if the identity permutation is
excluded than if the identity permutation is permitted.
------------------------------
Subject: Re: Random sboxes... real info
From: tomstd <[EMAIL PROTECTED]>
Date: Thu, 15 Jun 2000 11:22:40 -0700
In article <8ib68s$heo$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (David A. Wagner) wrote:
>Nope, I stand by my statement.
>
>You might want to think about this more carefully. Here's a
useful
>thought experiment. Consider the following two universes:
> Universe A: We encrypt using a permutation chosen uniformly
at random
> from the set of all permutations.
> Universe B: We encrypt using a permutation chosen uniformly
at random
> from everything but the identity permutation.
>I claim that (A) is strictly stronger than (B).
While I agree with this sense, getting back to the topic-at-hand
we are discussing permutations that are dictated by a key. If
the keyspace includes weak permutations then it's not a strong
cipher is it?
For example in RC5 we have the class of keys (prob 2^-10r) which
are weak. These permutations formed by the key are easy to
detect and break.
Whereas in RC6 there are no weak keys (yet) so essentially every
key determines a unique (so far) permutation that is hard to
distinguish from random.
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: Those darn sboxes
From: tomstd <[EMAIL PROTECTED]>
Date: Thu, 15 Jun 2000 11:39:35 -0700
You know the 20 sboxes [1] I posted yesterday, well they fail
the input-output independence test. Some bits are correlated
more then random. At
http://tomstdenis.com/files/good8x8_cor.txt is a table giving
the (input along the vertical) and output (horizontal)
correlation.
Ideally it should be zero in each element (or very close). For
example the very first entry is 16, which means the output bit
zero flips 144/256 times when the first input bit flips. This
is a bias of 1/16. The highest entry is 24 which is a bias of
about 1/11.
Hmm... too bad..
Tom
[1] http://tomstdenis.com/files/good8x8.c
* 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: Peter Pearson <[EMAIL PROTECTED]>
Subject: Re: public/private encryption keys and biometrics
Date: Thu, 15 Jun 2000 11:49:56 -0700
[EMAIL PROTECTED] wrote:
>
> I need some information. My company is looking for software that
> incorporates public/private key encryption with biometrics. Or at least
> a company that offers an SDK (software development kit) that will allow
> us to mesh the two.
>
> Our primary goal is to substitute biometrics (fingerprint or photo) for
> the passphrase when creating a key.
Scott Strait, Sailes Sengupta, and I demonstrated a proof-of-principle
of a way of reliably deriving cryptographic keys from biometric
measurements. It requires some accessory (but non-secret) data. The
best public description is probably the patent, #6,038,315.
- Peter
------------------------------
From: James Felling <[EMAIL PROTECTED]>
Subject: Re: Cipher design a fading field?
Date: Thu, 15 Jun 2000 14:00:26 -0500
"Trevor L. Jackson, III" wrote:
> "Douglas A. Gwyn" wrote:
>
> > "Trevor L. Jackson, III" wrote:
> > > "Douglas A. Gwyn" wrote:
> > > > Tim Tyler wrote:
> > > > > If the size of the program is constrained, a halting determination program
> > > > > could be written which enumerates all programs of that size or shorter and
> > > > > lists whether they halt or not.
> > > > It "lists" them how?
> > > Turing programs can be written as input to a UTM. Such inputs are a sequence of
> > > ones and zeros, so they are an integer. The list is ordered by the respective
> > > integer values.
> >
> > You missed the point
>
> Could be, but I doubt it.
>
> > -- *how* does it determine whether they halt?
>
> It doesn't. It simply reports the facts that are encoded by the author. Essentially
> it's a lookup function. The key question becomes whether the program can be written
> small enough to fit within itself (this is a data compression issue). If so then the
> Halting Problem can't be constructed because such a lookup program will halt after
> reporting that it will do so.
>
Yes, but this still leaces small and indeterminate programs .( unless of course one
assumes an omnicient author) A good example is the n/2 if n is even, 3n+1 if n is odd
programs. EG it takes an input n0, and repeatedly applies this rule. It ends if at
any
point n=1. This is a short program to write/ implement, especially if you fix n0, but
for
many n, it is very indeterminate. ( How can this be evaluated using your algorithim?)
>
> >
> >
> > > ... Is there any reason to believe that the growth in our
> > > understanding of the universe will stop in the near future?
> >
> > No, but that is not a counterargument. All knowledge is contextual,
> > and if some physical knowledge has been properly validated, it holds
> > in the context for which it was established, even if more is
> > discovered later. For our most fundamental physical principles,
> > that is already a wide context indeed.
>
> I suspect you have missed this point. Of the knowledge that was known to science
>over
> the last 500 years most of it was wrong. Some of the problems were of the form of
> limited context, such as the extension of Newtonian mechanics near the speed of
>light,
> and some of it was simply incorrect, such as epicycles, tomatoes are poisonous due to
> their similarity to nightshade, bleeding the sick allows bad humors to escape, black
> holes are black, charge is conserved, the coldest spot in the solar system is the
>back
> of Mercury. The former's correctness can be preserved by bounding the valid
> contexts. The latter's correctness cannot be preserved.
>
> The fact is that _everything_ is subject to revision in light of new information.
>Any
> other attitude is a religious one.
------------------------------
** 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
******************************
