Cryptography-Digest Digest #944, Volume #12 Tue, 17 Oct 00 12:13:00 EDT
Contents:
Block length newbie question ("mac")
Re: Smartcard, Mathematical Proof? (Mykhailo Lyubich)
Re: Algorithm Performance (Dido Sevilla)
Re: What is meant by non-Linear... ("Stephen M. Gardner")
Re: Counting one bits is used how? (Dido Sevilla)
"The code book" where ([EMAIL PROTECTED])
Re: Basic skills and equipment... (Bob Silverman)
Re: The sci.crypt FAQ (David A Molnar)
Re: MS's fast modular exponentiation claims II (JCA)
Re: Basic skills and equipment... (Richard Heathfield)
Re: Works the md5 hash also for large datafiles (4GB) ? (Daniel Leonard)
Re: Block length newbie question (Sundial Services)
Re: Smartcard, Mathematical Proof? (Sundial Services)
Re: Block length newbie question ("Scott Fluhrer")
Re: Counting one bits is used how? (David Wagner)
Re: algo to generate permutations (Richard Heathfield)
SALT + stream cipher ("William A. McKee")
----------------------------------------------------------------------------
From: "mac" <[EMAIL PROTECTED]>
Subject: Block length newbie question
Date: Tue, 17 Oct 2000 14:59:48 +0200
Hello
I have one beginner's question about Rijndael and block-ciphers in general.
If I got right, it is not the same if you crypt some text using, say 128-bit
block size and decrypt it using some other block length, 256 for example.
So when the key is passed should the receiver get the block length as well?.
If that's true, is there any standard today defining what's the block length
for common use of Rijndael?
Thank you.
------------------------------
From: Mykhailo Lyubich <[EMAIL PROTECTED]>
Subject: Re: Smartcard, Mathematical Proof?
Date: Tue, 17 Oct 2000 15:10:20 +0200
Reply-To: [EMAIL PROTECTED]
Tom St Denis wrote:
>
> You mean as a login token or a "dongle"?
>
> Dongles are stupid "snake oil" and login tokens are just physical
> passwords. if it's used in the sense that having the card is the only
> secret, then it can be quite secure. Otherwise....
I mean the following:
There are two client systems, S1 and S2, the architectures of which
are different. The both systems are the implementation of a
communication protocol. The system S1 is simple implementation of this
protocol. On the other hand, system S2 uses a chipcard to construct some
parts of the exchanged messages inside the chipcard.
____ ____ __
| | | |__| |
| S1 | | S2 | |__|
|____| |____|
The systems behave identically.
The systems use identical set of messages to communicate
with a service and the sequences of exchanged messages are also identical.
We would like to know about whether the intrusion into the S1
is harder than the intrusion into S2 and how to describe these
systems in a formal manner.
With best regards
--
Mykhailo Lyubich
Dept.of Computer Science office phone +49-381-4983407
University of Rostock office fax +49-381-4983440
Albert Einstein Strasse 21
http://wwwtec.informatik.uni-rostock.de/~ljubich/
D-18051 Rostock, Germany mailto:[EMAIL PROTECTED]
------------------------------
From: Dido Sevilla <[EMAIL PROTECTED]>
Subject: Re: Algorithm Performance
Date: Tue, 17 Oct 2000 21:00:56 +0800
Tom St Denis wrote:
>
> In article <8sg4qr$djd$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
> > I was curious if anyone had a quick and easy application to measure
> the
> > speed of crypto algorithms.
>
> A very not-so-super-accurate method is to run it for a few million
> itterations and count the clock ticks. If for example you output a
> million bytes from RC4 in five seconds... well you know you're going at
> about 200,000 bytes a second.
>
Much more reliable than the second part:
> If you want to get very technical (often a big waste of time) you could
> get out the "good 'ol processor manual" and count cycles... but
> often "30 cycles" on a i586 is "10 cycles" on a K6-2 or "12 cycles" on
> a MII 300, or ... This means that cycle counts are often taken out of
> context. (very often in fact). So a good idea is to test your app on
> several cpus (K6-2, K7, PIII and PII sounds sufficient) just to get
> the "ball park" idea.
>
The only real way to perform any kind of good profiling is to actually
RUN THE CODE YOU HAVE. The processor manuals will only give approximate
figures, the truth depends on a lot of factors which the microprocessor
designer has little or no control over, e.g. DRAM refresh cycles, L2
cache size, etc., and especially with modern processors, there are too
many rules and special cases so that it's difficult to see what actually
applies, e.g. what instruction will actually run in the Pentium's V
pipe, and whether your loop will cause your cache to thrash. When you
perform timing, things like the Pentium's TSC are especially useful.
Do what the AES committee did when they proposed a speed benchmark: pick
out one reference machine, e.g. 200 MHz Pentium Pro, and run the
algorithms on the same machine. See which one runs faster, based on a
good method of timing the algorithm, e.g. the aforementioned Pentium TSC
registers. Make sure that all algorithms run on the same playing field;
use the same compiler, optimization flags, and library for all
algorithms you want to compare.
It's not necessary to run the tests on more than one machine, unless you
get inconclusive results. Just settle on one, and that ought to give
you an idea.
--
Rafael R. Sevilla <[EMAIL PROTECTED]> +63 (2) 4342217
ICSM-F Development Team, UP Diliman +63 (917) 4458925
OpenPGP Key ID: 0x0E8CE481
------------------------------
From: "Stephen M. Gardner" <[EMAIL PROTECTED]>
Subject: Re: What is meant by non-Linear...
Date: Tue, 17 Oct 2000 08:12:44 -0500
==============4430F0E301376C354342F026
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Tim Tyler wrote:
> "I can plot "straight lines" through the points in the finite field.
>
> The "straight lines" curve on the surface of the cylinder - but they have a
> fixed
> local gradient with respect to the {theta,x} co-ordinate system, and don't
> "jump around".
I notice that you didn't answer this part:
y = 2x + 1 defined on GF(3) gives the following set of ordered pairs
{(0,1), (1,0),
(2,2)}. Draw that on a cylinder if you want but how does it lie on
a line or line
segment?
how do you figure that this set of points lies on a line (or a line wrapped
on a cylinder)? The y-coordinate goes 1->0->2 (down to zero, up to 2). Finite
fields "hop around" or they wouldn't be very good in Cryptography.
--
Take a walk on the wild side: http://www.metronet.com/~gardner/
There is a road, no simple highway, between the dawn and the
dark of night. And if you go no one may follow. That path is
for your steps alone.
The Grateful Dead ("Ripple")
==============4430F0E301376C354342F026
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit
<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
<html>
Tim Tyler wrote:
<blockquote TYPE=CITE>"I can plot "straight lines" through the points in
the finite field.
<p>The "straight lines" curve on the surface of the cylinder - but they
have a
<br>fixed
<br>local gradient with respect to the {theta,x} co-ordinate system, and
don't
<br>"jump around".</blockquote>
I notice that you didn't answer this part:
<blockquote><i><u>y = 2x + 1 defined on GF(3) gives the following set of
ordered pairs {(0,1), (1,0),</u></i>
<br><i><u>(2,2)}. Draw that on a cylinder if you want but how
does it lie on a line or line</u></i>
<br><i><u>segment?</u></i></blockquote>
<p><br> how do you figure that this set of points lies on a line
(or a line wrapped on a cylinder)? The y-coordinate goes 1->0->2
(down to zero, up to 2). Finite fields "hop around" or they wouldn't
be very good in Cryptography.
<p>--
<br>Take a walk on the wild side: <A
HREF="http://www.metronet.com/~gardner/">http://www.metronet.com/~gardner/</A>
<p>There is a road, no simple highway, between the dawn and the
<br>dark of night. And if you go no one may follow. That path is
<br>for your steps alone.
<br> The Grateful Dead ("Ripple")
<br> </html>
==============4430F0E301376C354342F026==
------------------------------
From: Dido Sevilla <[EMAIL PROTECTED]>
Subject: Re: Counting one bits is used how?
Date: Tue, 17 Oct 2000 21:10:44 +0800
Peter van der Linden wrote:
>
> How does counting the number of 1 bits in a word
> relate to crypto?
>
> Just curious about why this seemingly recondite instruction
> pops up in various instruction sets. How is it useful?
Well, it's also a pretty good way of seeing how vulnerable a
cryptographic algorithm is to power analysis. If the number of 1 bits
in a cipher's state happens to show significant bias that could be
correlated to sensitive information such as a block cipher's key or key
schedule, well, then you may well be vulnerable.
--
Rafael R. Sevilla <[EMAIL PROTECTED]> +63 (2) 4342217
ICSM-F Development Team, UP Diliman +63 (917) 4458925
OpenPGP Key ID: 0x0E8CE481
------------------------------
From: [EMAIL PROTECTED]
Subject: "The code book" where
Date: Tue, 17 Oct 2000 13:37:43 GMT
Hey
I have just ordered "The code book" but I have to wait 3-4weeks before
I can get it. Do somebody know where I can download an PFD of it,
becouse I will like to spend some time whit breaking the codes?
Best reg.
Nenad
[EMAIL PROTECTED]
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Basic skills and equipment...
Date: Tue, 17 Oct 2000 13:54:08 GMT
In article <[EMAIL PROTECTED]>,
"Sam Simpson" <[EMAIL PROTECTED]> wrote:
> Tom St Denis <[EMAIL PROTECTED]> wrote in message
> Tom, you're the most prolific poster in this forum and you sometimes
> shoot from the hip - are you really surprised that some people will
> disagree with you on occasion? I think you could quite correctly
> call Bobs comments "a flame",
Huh? I made it quite clear that I was NOT flaming in my original reply!
Or do you automatically assume the equation "any criticism = flame"???
It was *HIS* subsequent reply that was insulting. Have you forgotten
his slurs on Bruce Shneier (and other professionals in the thread
a few months ago about why the "pros" never post)??
> but he has problems being civil to most
> people here,
I never respond to "most people" here. The vast majority of my posts
amount to "pouring water on nonsense". It is not surprising that
this comes across as uncivil. But then, many people are quick to
take offense when none was intended.....
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: The sci.crypt FAQ
Date: 17 Oct 2000 13:41:48 GMT
Dido Sevilla <[EMAIL PROTECTED]> wrote:
> me a Bad Thing(tm). It kinda defeats the purpose of having a FAQ. Who
> maintains it anyhow, and why does it seem that no one has contacted this
> person in more than seven years to update it even a little?
Check part 1 of the FAQ for a note on this topic. This note appeared out
of the blue one day, presumably put there by someone who maintains the
FAQ.
My personal speculation is that the problem stems from the fact that the
original FAQ was done by a committe of people (see acknowledgements) who
are now too busy to maintain it...and even too busy to figure out to whom
to pass along the maintenance job.
-David
------------------------------
From: JCA <[EMAIL PROTECTED]>
Subject: Re: MS's fast modular exponentiation claims II
Date: Tue, 17 Oct 2000 07:06:11 -0700
OK, this is more like it. Thanks everybody for your replies.
It would be interesting to find out how this MS implementation
performs. If anybody has got MS CAPI and can come up with a
simple RSA private key operationbenchmark that would great.
JCA wrote:
> I asked a few days ago a question about some claims the MS made (at
> Crypto '95,
> I believe) to the effect that they possess an algorithm that outperforms
> Montgomery's
> techniques when doing modular exponentiation. Much to my surprise, given
> the high
> caliber of some of the regulars in this group, nobody has said anything
> yet.
>
> At the risk of coming across as pig-headed allow me please to
> restate my question:
> does anybody know if such claims have been independently substantiated?
> Has anybody
> got more information about them?
------------------------------
Date: Tue, 17 Oct 2000 15:25:56 +0100
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: Basic skills and equipment...
Bob Silverman wrote:
>
> In article <[EMAIL PROTECTED]>,
> "Sam Simpson" <[EMAIL PROTECTED]> wrote:
<snip>
>
> > but he has problems being civil to most
> > people here,
>
> I never respond to "most people" here. The vast majority of my posts
> amount to "pouring water on nonsense". It is not surprising that
> this comes across as uncivil. But then, many people are quick to
> take offense when none was intended.....
I resent that!
------------------------------
From: Daniel Leonard <[EMAIL PROTECTED]>
Subject: Re: Works the md5 hash also for large datafiles (4GB) ?
Date: Tue, 17 Oct 2000 14:45:31 GMT
On Tue, 17 Oct 2000, Tom St Denis wrote:
> In article <[EMAIL PROTECTED]>,
> Runu Knips <[EMAIL PROTECTED]> wrote:
> > [EMAIL PROTECTED] wrote:
> > > I have to compare diskimages. To save diskspace I want to use
> > > a hash (md5).
> > >
> > > Work md5 for such large files?
> > > I know I would generate a 128bit signature, what I mean is, is
> > > the probability that two different large files have the same
> > > signature as low as for smaller files.
> > >
> > > In other words, is the algorthm of md5 only designed for "small"
> > > files?
> >
> > AFAIK MD5, SHA-1, RIPE MD160 and Tiger/192 all work with 64 bit
> > size counters. I guess SHA256 does, too.
>=20
> SHA-512/384/256 all use the exact same MD-Strengthing as MD5 so yes,
> they are 64-bit counters.
>=20
> Tom
SHA512 (and thus SHA384) have a _*128*_ bit counter. Read carefully p.20
of the draft:
Pad the message in the usual way: Suppose the length of the message M, in
bits, is l. Append the bit ``1'' to the end of the message, and then k
zero bits, where k is the smallest non-negative solution to the equation l
+ 1 + k <=3D> 896 mod 1024. To this append the 128-bit block which is equa=
l
to the number l written in binary.
==========
Daniel L=E9onard
OGMP Informatics Division E-Mail: [EMAIL PROTECTED]
D=E9partement de Biochimie Tel : (514) 343-6111 ext 5149
Universit=E9 de Montr=E9al Fax : (514) 343-2210
Montr=E9al, Quebec Office: Pavillon Principal G-312
Canada H3C 3J7 WWW : http://megasun.bch.umontreal.ca/~leonard
------------------------------
Date: Tue, 17 Oct 2000 07:56:20 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Block length newbie question
In any block cipher, AFAIK, the block-size used for decryption must
always be the same as the one used for encryption. Not only is the
output a function of every one of the input bits (no more and no less),
but the key used for the next block will be different from the key used
for the previous one (so-called "block chaining").
Also AFAIK, the block-size used for each cipher is standardized for that
cipher.
The core assumption in every cryptographic situation is that, not only
do Alice and Bob have the same cipher-machines (programs), but Eve has
an identical copy as well and knows precisely how the messages are being
encrypted. The only thing Eve does not know, and cannot determine, is
"the one and only key that works."
>mac wrote:
> I have one beginner's question about Rijndael and block-ciphers in general.
> If I got right, it is not the same if you crypt some text using, say 128-bit
> block size and decrypt it using some other block length, 256 for example.
> So when the key is passed should the receiver get the block length as well?.
> If that's true, is there any standard today defining what's the block length
> for common use of Rijndael?
------------------------------
Date: Tue, 17 Oct 2000 08:04:33 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Smartcard, Mathematical Proof?
Mykhailo Lyubich wrote:
> I mean the following:
> There are two client systems, S1 and S2, the architectures of which
> are different. The both systems are the implementation of a
> communication protocol. The system S1 is simple implementation of this
> protocol. On the other hand, system S2 uses a chipcard to construct some
> parts of the exchanged messages inside the chipcard.
> ____ ____ __
> | | | |__| |
> | S1 | | S2 | |__|
> |____| |____|
>
> The systems behave identically.
> The systems use identical set of messages to communicate
> with a service and the sequences of exchanged messages are also identical.
>
> We would like to know about whether the intrusion into the S1
> is harder than the intrusion into S2 and how to describe these
> systems in a formal manner.
Assuming that this is not part of your homework ... ;-) ... if the two
systems implement the same protocol, and behave identically, then for
all external intents and purposes they -are- the same.
If S1 and S2 are the same then there's really nothing to "intrude" upon
or with. The intruder can simply use the equivalent S1 device, instead.
If System S2 uses a chipcard as part of its implementation, then the
only difference between S1 and S2 is that S2 contains a part that can be
removed and locked in the safe each night. But the device could also be
stolen, or secretly replaced with a device that contains some kind of a
trojan horse, or left on one's dashboard during lunch in a hot Phoenix,
Arizona summer, or dropped on the floor by accident and run-over with
one corner of the operator's desk-chair while he's reaching down to pick
it back up... crunch. Oops.
The chipcard would enable S2 to be disabled when not in use and would
render the device inoperable without it. Certainly a small chipcard is
easier to lock-up than the entire device would be. But it also
represents a vulnerability of its own if the intruder is creative --
"crunch, oops."
I don't know if a mathematical proof could possibly consider "crunch,
oops." ;-)
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Block length newbie question
Date: Tue, 17 Oct 2000 07:53:13 -0700
Sundial Services <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In any block cipher, AFAIK, the block-size used for decryption must
> always be the same as the one used for encryption. Not only is the
> output a function of every one of the input bits (no more and no less),
> but the key used for the next block will be different from the key used
> for the previous one (so-called "block chaining").
Actually, block chaining typically does not change the keys. Instead, it
usually always uses the same key, and mask identical plaintext blocks by
combining it (often with an xor) with previous ciphertext blocks (and
possibly previous plaintext blocks).
>
> Also AFAIK, the block-size used for each cipher is standardized for that
> cipher.
Well, there are some ciphers that are defined for multiple block sizes --
examples would be RC5, RC6 and Rijndael.
>
> The core assumption in every cryptographic situation is that, not only
> do Alice and Bob have the same cipher-machines (programs), but Eve has
> an identical copy as well and knows precisely how the messages are being
> encrypted. The only thing Eve does not know, and cannot determine, is
> "the one and only key that works."
To amplify that statement: yes, Alice and Bob may use a block cipher with
variable block lengths. However, the security of the cipher does not depend
on keeping the length of the block secret -- they can share that publicly,
and as long as the key is secret, they are safe (assuming they are using a
decent block cipher, of course).
>
>
> >mac wrote:
> > I have one beginner's question about Rijndael and block-ciphers in
general.
> > If I got right, it is not the same if you crypt some text using, say
128-bit
> > block size and decrypt it using some other block length, 256 for
example.
> > So when the key is passed should the receiver get the block length as
well?.
> > If that's true, is there any standard today defining what's the block
length
> > for common use of Rijndael?
Rijndael is still rather new (it just got the NIST seal of approval), and so
it's somewhat early to talk about what's common. However, my opinion is
that, while Rijndael is defined for 192 and 256 bit blocks, I don't expect
very many people to use anything other than the 128 bit block size.
--
poncho
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Counting one bits is used how?
Date: 17 Oct 2000 15:45:05 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Rob Warnock wrote:
>David Wagner <[EMAIL PROTECTED]> wrote:
>| 1. Calculating the dot-product x.y can be computed in three instructions
>| as popcount(x^y)&1
>
>I think you probably meant "popcount(x&y)&1", since the "product" in
>dot-product needs an AND, not an XOR.
Right. Sorry.
>| Dot-products are used all over the place in GF(2) math: e.g., in LFSR's.
>
>Well, yes, dot-products are used sometimes in GF math, but LFSRs are more
>likely to use N-way parity, that is, "popcount(x)&1", in the feedback terms.
Are you sure? I'd say that LFSRs are more likely to use popcount(r&t)&1,
where r is the state of the shift register and t represents the feedback taps.
------------------------------
Date: Tue, 17 Oct 2000 17:00:30 +0100
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: algo to generate permutations
[EMAIL PROTECTED] wrote:
>
> And another, 15x faster than the last (minus the printf()s). Still not
> lexicographic order. Generating permutations comes up in attacking rc4.
Nice. In fact, very nice.
Now, one nit and one question...
The nit: you should really #include <stdio.h> and <string.h> (for printf
and strlen) - C headers are not just there for decoration! :-)
The question: for the input aaa, I get six outputs - i.e. the first 'a'
is considered to be different from the second 'a' and the third 'a'.
Now, I don't mean to seem ungrateful, but it strikes me that you could
have had any of three reasons for writing the program this way:
(1) you couldn't be bothered to filter out duplicates - after all, perm
aaa | sort | uniq would do the Right Thing anyway. (Yes, I know, for
this particular input, the sort step is optional...)
(2) you couldn't work out how to do this filtering in C.
(3) you have some deep cryptanalytic reason for retaining the
duplicates.
I'm betting on (1). Am I right? :-)
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html
------------------------------
Reply-To: "William A. McKee" <[EMAIL PROTECTED]>
From: "William A. McKee" <[EMAIL PROTECTED]>
Subject: SALT + stream cipher
Date: Tue, 17 Oct 2000 16:00:28 GMT
When you encrypt a file with a stream cipher, you choose a password and salt
(random number) to seed the pseudo random number generator. Then you xor
the file with the output from the PRNG. My question is how do you remember
the salt? Do have to keep it secret or can you save it as the first few
bytes of the encrypted file?
TIA,
Will McKee.
--
William A. McKee
[EMAIL PROTECTED]
Asia Communications Quebec Inc.
http://www.cjkware.com
"We're starfleet: weirdness is part of the job." - Janeway
------------------------------
** 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
******************************
