Cryptography-Digest Digest #638, Volume #14 Mon, 18 Jun 01 11:13:01 EDT
Contents:
Re: BigNum Question (Tim Tyler)
Re: New Directions in Cryptography (Nigel Smart)
Re: SSL/TLS compression methods??? (Erwann ABALEA)
Re: Single-cycle sbox question ("Tom St Denis")
Re: CipherText E-mail encryption ("Tom St Denis")
Re: BigNum Question ("Tom St Denis")
Re: Single-cycle sbox question ("Tom St Denis")
Re: SHA2 PRNG. ("Cristiano")
Re: quadratic functions (Klaus Pommerening)
Re: SHA2 PRNG. ("Cristiano")
Re: BigNum Question (Ian Crawford)
Help on GF(2^N) (Phil Carmody)
Re: Notion of perfect secrecy (Mark Borgerding)
Re: BigNum Question (Tim Tyler)
Re: My auction protocol ("Adam O'Brien")
Re: Notion of perfect secrecy ("Robert J. Kolker")
Re: FIPS 140-1 test ("Harris Georgiou")
Re: Notion of perfect secrecy ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: BigNum Question
Reply-To: [EMAIL PROTECTED]
Date: Mon, 18 Jun 2001 08:34:59 GMT
Harris Georgiou <[EMAIL PROTECTED]> wrote:
: Ο Tim Tyler <[EMAIL PROTECTED]> έγραψε στο μήνυμα συζήτησης:
:> If there's a problem with Java's cryptography stuff, it seems to be that
:> these classes are immutable, so there's no way of deleting objects - you
:> can only null them, and wait for the garbage collector to clean
:> up afterwards.
: Not true. Of course garbage collector is there to free the programmer of
: several "boring" lines of cleanup code, but there are always functions to
: actually delete any object on call. Try Runtime.gc() and destroy() and
: delete() methods in various objects.
Those don't "eliminate" anything - they just attempt to free up the memory
that was allocated. This is a *very* different operation to the
repeatedly overwriting with random bitstrings that is often
used in cryptographic applications.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Nigel Smart <[EMAIL PROTECTED]>
Subject: Re: New Directions in Cryptography
Date: Mon, 18 Jun 2001 09:10:03 GMT
Nomen Nescio wrote:
>
> > Someone recently asked whether Diffie & Hellman's 1976 paper
> > "New Directions in Cryptography" was on-line. It is (without figures):
> >
> > <http://citeseer.nj.nec.com/340126.html>
> >
> > Well worth reading.
>
> Didn't I see recently a listing for a talk with the same title by
> one of the greats (maybe Shamir)? It was either a recent talk or one
> coming up shortly. The implication was that it might be something cool.
> Can't remember where I saw it though. Anyone?
Was in CHES 2001, was by Shamir and the title was...
"New Directions in Croptography"
Notice the spelling difference
Nigel
--
Dr Nigel P. Smart | Phone: +44 (0)117 954 5163
Computer Science Department, | Fax: +44 (0)117 954 5208
Woodland Road, | Email: [EMAIL PROTECTED]
University of Bristol, BS8 1UB, UK | URL: http://www.cs.bris.ac.uk/~nigel/
------------------------------
From: Erwann ABALEA <[EMAIL PROTECTED]>
Subject: Re: SSL/TLS compression methods???
Date: Mon, 18 Jun 2001 11:26:07 +0200
On Sun, 17 Jun 2001, Bryan Olson wrote:
>
>
> Erwann ABALEA wrote:
> >
> > On Sat, 16 Jun 2001, Ricardo wrote:
> >
> > > 1) Does anyone know which compression methods are used in SSLv3 and TLSv1?
> > > (I only know two: gzip and zip)
> >
> > I think that no compression method is really defined. Compression can be
> > enabled by the SSL and TLS standards, but the real mechanisms will be
> > defined latter (in a future version).
>
> Correct, though the standard takes a different point of view.
> From the TLS spec (RFC 2256)
>
> There is always an active compression algorithm; however, initially
> it is defined as CompressionMethod.null.
> [...]
> A CompressionMethod.null operation is an identity operation; no
> fields are altered.
>
> The RFC doesn't define any other compression methods, and currently
> there are no others for standard SSL/TLS.
Yes, I noticed it, and told it in private to the original requester.
I also noticed that actually 2 compression methods were defined, the first
one identified by null(0), and the other by (255) (both are defined in an
enum). The rest of the document doesn't define this (255)-identified
compression method...
--
Erwann ABALEA
[EMAIL PROTECTED]
- RSA PGP Key ID: 0x2D0EABD5 -
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Single-cycle sbox question
Date: Mon, 18 Jun 2001 10:04:38 GMT
"Benjamin Goldberg" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Tom St Denis wrote:
> >
> > "Benjamin Goldberg" <[EMAIL PROTECTED]> wrote in message
> > news:[EMAIL PROTECTED]...
> > > I know of two methods for generating a single-cycle sbox.
> > >
> > > The first one is:
> > >
> > > do { sbox = random_permutation } until( single_cycle(sbox) );
> > >
> > > The second one is:
> > >
> > > temp = random_permutation
> > > for( i = 0 to N-2 ) {
> > > sbox[ temp[i] ] = sbox[ temp[i+1] ];
> > > sbox[ temp[N-1] ] = sbox[ temp[0] ];
> > >
> > > Now, while I know that method two is of course much, much, faster
> > > than method one, I *don't* know whether or not it can produce all
> > > possible single-cycle sboxes, or whether it is biased. I don't
> > > *think* it's biased, but I'm not sure...
> > >
> > > Tom's sboxgen uses method 1. I plan on making a change in my own
> > > copy to use method 2, but I want to first know that it will be
> > > correct.
> >
> > Well you can always list a single cycle as (x y z) for example (3 2 1)
> > which means 1 => 3, 3 => 2, 2 => 1, so the table would be { 3, 1, 2 }
> >
> > Just make a random sbox, then find the entries and see the next
> > element. I.e search for 1 first, then 2, then 3... etc..
> >
> > Not too hard.
>
> Huh? Searching for stuff sounds like it would take quadratic time.
> My algorithm should take linear time wrt the number of elements.
It's actually easier. given say {3, 1, 2}
You know 3=>1, 1=>2, 2=>3 right?
Then just do
L = {3, 1, 2}
S = {}
for x = 1 to 3 do
S[L[x]] = L[(x+1) mod 3]
Tada. Linear time solution.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: CipherText E-mail encryption
Date: Mon, 18 Jun 2001 10:41:39 GMT
"Bryan Olson" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> Tom St Denis wrote:
> [...]
> > This is pure irony. I wrote the code to output fixed block sizes to
make it
> > simple (i.e KISS) then you propose to handle variable sized blocks.
>
> I think you miss the point. For any octet string x, encoding x
> then decoding that result should give us back x. I've now checked
> your decode procedure. If we encode a single octet with the value
> zero; the result is "aaaa". Decode "aaaa" and the result is three
> octets long.
>
> It looks like your code only works when the length of the original
> octet string is a multiple of three.
True. However, if you pre-append the original length you can get around
this.
Also for my intents and purposes it doesn't matter. Since I will be
decoding a buffer that has a header appended bytes [even random ones] won't
affect the outcome.
I agree that it shouldn't do this though and I thank you for pointing this
out.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: BigNum Question
Date: Mon, 18 Jun 2001 10:43:29 GMT
"Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Harris Georgiou <[EMAIL PROTECTED]> wrote:
> : Ο Tim Tyler <[EMAIL PROTECTED]> έγραψε στο μήνυμα συζήτησης:
>
> :> If there's a problem with Java's cryptography stuff, it seems to be
that
> :> these classes are immutable, so there's no way of deleting objects -
you
> :> can only null them, and wait for the garbage collector to clean
> :> up afterwards.
>
> : Not true. Of course garbage collector is there to free the programmer of
> : several "boring" lines of cleanup code, but there are always functions
to
> : actually delete any object on call. Try Runtime.gc() and destroy() and
> : delete() methods in various objects.
>
> Those don't "eliminate" anything - they just attempt to free up the memory
> that was allocated. This is a *very* different operation to the
> repeatedly overwriting with random bitstrings that is often
> used in cryptographic applications.
In memory "repeated overwrites" are not typically required. Once the bit is
changed it's gone!
And I do believe that the designers of the crypto portions did think of
this.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Single-cycle sbox question
Date: Mon, 18 Jun 2001 10:44:09 GMT
"SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> [EMAIL PROTECTED] (Benjamin Goldberg) wrote in
> <[EMAIL PROTECTED]>:
>
> >Henrick Hellstrφm wrote:
> >>
> >> See http://www.streamsec.com/createsc.asp The proof is incuded. I
> >> suppose that's where you got the idea in the first place.
> >
> >No, I got the idea to create single-cycle sboxes in this manner from the
> >key schedule of the LJA1 cipher, which predates your code significantly.
> >
> >And I'm sure that he got his code from somewhere else. Don't try to
> >steal credit from others.
> >
> >> If you are using key data to create the permutation and want to avoid
> >> key collisions, you should use the algorithm at our homepage.
> >> Otherwise you would obtain each permutation n times, where n is the
> >> length of the permutation. Consequently:
> >
> >In other words, you're saying that if there are 256 elements, my method
> >will end up mapping 256! unstructured permutations down to 255! cingle
> >cycle permutations, a collision factor of 256? Gee, what a surprise.
> >Are you saying that yours doesn't? Yeah, right.
> >
>
> Actually I have been doing keyed S-boxes longer than either
> of you. But I don't mess with small ones. try 19x19.
Just curious. Why did you pick 19x19? Why not 18x18 or 20x20?
I think originally it had todo with fitting on a floppy right?
Tom
------------------------------
From: "Cristiano" <[EMAIL PROTECTED]>
Subject: Re: SHA2 PRNG.
Date: Mon, 18 Jun 2001 13:14:18 +0200
"Tom St Denis" wrote:
> "Cristiano" <[EMAIL PROTECTED]> wrote in message
> news:9gj15m$fan$[EMAIL PROTECTED]...
> > "Tom St Denis" <[EMAIL PROTECTED]> ha scritto:
> > >
> > > "Cristiano" <[EMAIL PROTECTED]> wrote in message
> > > news:9gimtg$d4d$[EMAIL PROTECTED]...
> > Now I changed the generator in this way:
> > 1) I fill a 256 bits vector with 8 pseudorandom 32 bits numbers;
>
> Careful here. You should typically bring in more bits then you put out.
> This is because you want to make sure the amount of entropy comming in is
> sufficient. Let's say you bring in 256 bits from say the mouse
co-ordinates
> [the lsbs]. But there is a huge skew of say p=0.95 for 1 in the lsb, this
> means your 256 bits has only -256 * log2(0.95) = 19 bits of real entropy.
> You would need 3460 bits to get your 256 bits of entropy.
Is there any empirical method that allows me to calculate how much do bits
need?
> > 2) I hash the vector and I store the result in the same vector;
>
> I don't get this part. Use some pseudocode like
>
> H[i+1] = HASH(H[i])
This is what I do in pseudocode (RND[i] is a 256 bits vector):
H[i] = HASH(RND[i])
H[i+1] = HASH(RND[i+1])
this is c++ code:
#define SHA2b 256
ULONG SHA2rnd(void)
{
static ULONG sha[SHA2b/32]; static int j=SHA2b/32;
if(j==SHA2b/32) {
j=0; for(int i=0;i<SHA2b/32;i++) sha[i]=MT19937();
SHA256(sha,SHA2b/8,sha);
}
return sha[j++];
}
> > 3) I get the 8 numbers;
> > 4) go to step 1.
> >
> > It pass all tests. Is there some weakness now? Is there a better way?
>
> Yes it may appear random but keep in mind so do LFSRs.
>
> How is your "modification" any better?
The MT19937() is a very good generator. In this way I hash each time 256
bits with good statistical property and I hope that the hash result is also
good (this is what NIST test show to me).
Thank you
Cristiano
------------------------------
From: [EMAIL PROTECTED] (Klaus Pommerening)
Subject: Re: quadratic functions
Date: 18 Jun 2001 11:24:39 GMT
In <q9TW6.137107$[EMAIL PROTECTED]> "Tom St Denis"
wrote:
> F(x) = x^tAx
> ...
> Are "quadratic" sboxes ones where each row has a hamming weight of two?
>
No. Take a math book and look for "quadratic forms".
And for "degree of a polynomial".
--
Klaus Pommerening [http://www.Uni-Mainz.DE/~pommeren/]
Institut fuer Medizinische Statistik und Dokumentation
der Johannes-Gutenberg-Universitaet, D-55101 Mainz, Germany
------------------------------
From: "Cristiano" <[EMAIL PROTECTED]>
Subject: Re: SHA2 PRNG.
Date: Mon, 18 Jun 2001 13:50:46 +0200
> > > 3) I get the 8 numbers;
> > > 4) go to step 1.
> > >
> > > It pass all tests. Is there some weakness now? Is there a better way?
> >
> > Yes it may appear random but keep in mind so do LFSRs.
> >
> > How is your "modification" any better?
>
> The MT19937() is a very good generator. In this way I hash each time 256
> bits with good statistical property and I hope that the hash result is
also
> good (this is what NIST test show to me).
This is not true, my mistake. DFT of NITS test fail also in this way.
Cristiano
------------------------------
From: [EMAIL PROTECTED] (Ian Crawford)
Subject: Re: BigNum Question
Date: 18 Jun 2001 05:59:37 -0700
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:<lXkX6.151031$[EMAIL PROTECTED]>...
<snip>
> In memory "repeated overwrites" are not typically required. Once the bit is
> changed it's gone!
>
> And I do believe that the designers of the crypto portions did think of
> this.
>
> Tom
Right you are. And if everyone had enough good ol' volatile RAM to
store all their run-time data, the world would be a better place.
Ian.
--
=============================
http://www.stasis.org/~codic/
------------------------------
From: Phil Carmody <[EMAIL PROTECTED]>
Subject: Help on GF(2^N)
Date: Mon, 18 Jun 2001 13:25:08 GMT
About 8 centuries ago I did a maths degree, but I can't remember shite.
Lots of questions, sorry.
A pointer to a 'everything you wanted to know about GF(2^N) for dummies'
webpage is more than enough.
(I've read a set of ucla.edu/~matache/rsc/ pages, which was a good
start.
Can anyone give an example demonstrating why /irreducible/ polynomials
are not /prime/ in GF(p)[x]? (i.e. a C=AB=XY for irreducible A, B, X, Y.
I understand (but can't instantly prove) that the field is not a unique
factorisation domain, I'd just like an example to sweaten the idea).
Are there any (families of) GFs that are UFDs?
Side question (not that important, just curoisity) - Is there such a
thing as an 'infinite' GF (no finite N)? (I feel I could construct a
ring that behaves that way, but whether it's actually a field is another
matter).
When trying to express elements of GF(2^N) in 'polynomial' form, does it
make any difference what irreducible polynomial in GF(2)[x] I chose? I
assume all of the choices yield isomorphic fields? How many such
polynomials are there? Is it always that case that if I chose an
irreducible polynomial of degree N that I'll generate GF(2^N)?
It looks like everything is abelian and the usual distribution of
operators I'm used to applies - a(b+c)=ab+ac; a^(b+c)=a^b.a^c.
Finally, can anyone verify my maths:
A) '0...010' ^ (2^N-1) == '0...001', and by extension 'abc...xyz' ^
(2^N-1) == '000...001'
B) '...abc'^-1 == '...abc'^(2^N-2), and this yields the quickest method
of calculating inverses.
C) '...abc'^2 == '...0a0b0c'
Cheers,
Phil
------------------------------
From: [EMAIL PROTECTED] (Mark Borgerding)
Subject: Re: Notion of perfect secrecy
Date: 18 Jun 2001 06:43:43 -0700
my $0.02:
Gathering information from the length of the message is traffic analysis.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: BigNum Question
Reply-To: [EMAIL PROTECTED]
Date: Mon, 18 Jun 2001 13:30:35 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: "Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
:> Harris Georgiou <[EMAIL PROTECTED]> wrote:
:> : Ο Tim Tyler <[EMAIL PROTECTED]> έγραψε στο μήνυμα συζήτησης:
:> :> If there's a problem with Java's cryptography stuff, it seems to be
:> :> that these classes are immutable, so there's no way of deleting
:> :> objects - you can only null them, and wait for the garbage
:> :> collector to clean up afterwards.
:>
:> : Not true [...] there are always functions to actually delete any
:> : object on call. Try Runtime.gc() and destroy() and delete() methods
:> : in various objects.
:>
:> Those don't "eliminate" anything - they just attempt to free up the memory
:> that was allocated. This is a *very* different operation to the
:> repeatedly overwriting with random bitstrings that is often
:> used in cryptographic applications.
: In memory "repeated overwrites" are not typically required. Once the bit is
: changed it's gone!
: And I do believe that the designers of the crypto portions did think of
: this.
Not in the classes in question. You can check for yourself.
There is no API for wiping them out. There are no destroy() or delete()
methods in the class, or in any of its parents - and they are immutable -
so you can't access their contents.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: "Adam O'Brien" <[EMAIL PROTECTED]>
Subject: Re: My auction protocol
Date: Mon, 18 Jun 2001 14:20:06 GMT
AY wrote in message <9ge60g$nfu$[EMAIL PROTECTED]>...
>For my school project I have come up with this open cry auction protocol,
>with the aim to reduce the amount of trust required to be placed by the
user
>(bidder) on the auction server in terms of fairness and correctness of
>outcome. It is based on one of Stuart Stubblebine's paper available at
>
>http://www.stubblebine.com/99fc-stubblebine.pdf
>Any comments welcome and any help will be fully acknowledged in my report
>(unless one chooses not to be!). Thanks in advance!
>
>Assumptions:
>1. There are three services: the auction server, the notary (a trusted
>timestamping service), and a certified delivery service (also trusted)
>2. The user has registered with the auction system and there exists some
>strong authentication mechanism for the registered user to identify himself
>to the auction server.
>3. The user holds all the necessary public keys to verify the servers'
>signatures. They are all correct.
>4. The server holds the user's public key for signature verification
>
>Only registered users can engage in bidding activities. Each auction has
its
>own unique ID. At any given time an active auction has a highest bidder
>(which may be null) and a current asking price. Once a user has identified
>his auction of interest:
>
>1. he initiates the bidding process by requesting from the auction server
>for auction status message, which contains the following information:
>? - the auction ID
>? - the user ID of the current highest bidder
>? - the amount of the current highest bid
>? - auction parameters including start and end time
>The message is signed by the auction server and then timestamped by the
>notary.
>
How would the user know that this information was correct?
Couldn't the auction server record dummy bids in an attempt to push up the
price?
This idea is explored in The Cocaine Auction Protocol by Ross Anderson.
>If the bid is valid but the server fails to update its records to reflect
>this fact, the message received by bidder at step 3 along with the
temporary
>key would be the evidence for the server's wrongdoings, which is the main
>aim of my project.
>
>Is this any good? What are the weaknesses?
>(one I can think of is that signing arbitrary data might be a bad idea in
>general...)
>
>
------------------------------
From: "Robert J. Kolker" <[EMAIL PROTECTED]>
Subject: Re: Notion of perfect secrecy
Date: Mon, 18 Jun 2001 10:24:24 -0400
Mark Borgerding wrote:
> my $0.02:
> Gathering information from the length of the message is traffic analysis.
In a military context traffic analysis also includes, time, frequency,
call sign, direction from and approximate location of the transmission
origin.
The Brits and the Americans were able to piece together a
fairly good picture of Japanese naval activity in the far east
up to a period not long before the attacks came, just from
the traffic analysis.
The Japanese imposed a radio silence when their fleets
went into action.
Bob Kolker
------------------------------
From: "Harris Georgiou" <[EMAIL PROTECTED]>
Subject: Re: FIPS 140-1 test
Date: Mon, 18 Jun 2001 04:35:53 +0300
Ο Tim Tyler <[EMAIL PROTECTED]> έγραψε στο μήνυμα συζήτησης:
[EMAIL PROTECTED]
> Peter Gutmann <[EMAIL PROTECTED]> wrote:
>
> : As a followup question, has anyone ever looked at doing the tests which
> : require an FPU in an (admittedly approximate) integer-only way? There
are
> : some embedded systems which don't do FP-maths too well.
>
> I'm always after more integer-friendly randomness tests. Chi-squared,
> entropy, serial correlation, monte-carlo PI - *many* tests seem to use FP.
Then why not try to implement any of them as integer-only calculation
methods?
Given the specific precision needed (say 3 digits on the fp part), the whole
deal normally renders into number scaling.
Just a thought.
--
Harris
- 'Malo e lelei ki he pongipongi!'
------------------------------
Subject: Re: Notion of perfect secrecy
From: [EMAIL PROTECTED]
Date: 18 Jun 2001 10:44:18 -0400
"Robert J. Kolker" <[EMAIL PROTECTED]> writes:
> Mark Borgerding wrote:
>>
>> my $0.02:
>> Gathering information from the length of the message is traffic
>> analysis.
Agreed.
> In a military context traffic analysis also includes, time, frequency,
> call sign, direction from and approximate location of the transmission
> origin.
>
> The Brits and the Americans were able to piece together a
> fairly good picture of Japanese naval activity in the far east
> up to a period not long before the attacks came, just from
> the traffic analysis.
Specifically, they mapped the chain of command, where each node was
identified by call-signs. Shortly before the attack on Pearl, all the
call-signs were changed. This destroyed the previous ``maps'', and
caused a flurry of activity while American listeners attempted to
remap the chain of command. (This raised eybrows, because it happened
unusually soon after the previous call-sign change.)
Also, when the carriers left for Pearl they dropped off their old
radio men, and took on new ones. Listeners could recognize a sender
by his distinctive ``fist'' on the code key. Up until the call-sign
changes and radio blackout, the old radio men sent messages around the
Japanese islands using the old call-signs of their carriers.
Len.
--
Frugal Tip #39:
Buy a lot of disaster insurance on the next Kevin Costner movie.
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
