Cryptography-Digest Digest #837, Volume #11 Mon, 22 May 00 16:13:01 EDT
Contents:
Yet another block cipher: Storin (Mark Wooding)
Re: pentium timings (Jerry Coffin)
Re: Q: Recording on magnetic cards (James Felling)
Re: Is OTP unbreakable? (Sundial Services)
Re: Patent state of Elliptic Curve PK systems? (Mike Rosing)
Re: ZKPs in practice? (David A. Wagner)
Re: Blowfish Claims ... something not right (David A. Wagner)
Re: Patent state of Elliptic Curve PK systems? (Paul Rubin)
Re: pentium timings (Gisle Sælensminde)
Re: More on Pi and randomness (Tim Tyler)
Re: pentium timings (Helger Lipmaa)
Re: About Hardware RNG (Will Dickson)
Re: More on Pi and randomness (Tim Tyler)
Re: Blowfish Claims ... something not right (Helger Lipmaa)
Re: 3DES SOURCE (Paul Koning)
Re: Blowfish Claims ... something not right (Will Dickson)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Yet another block cipher: Storin
Date: 22 May 2000 16:52:46 GMT
I've submitted a block cipher to the contest. It's called Storin, and
it's been designed to take advantage of the fast multiply-and-
accumulate instructions available on DSPs. It's an 8-round SP-network
(ish), not a Feistel network; it works on 96-bit blocks. The main
operation is multiplication by a fixed invertible 4x4 matrix over
Z_{2^{24}}. The key can be any number of 24-bit words up to 864, in
theory. I'm not recommending more than 120 bits (5 24-bit words) yet.
Certainly, more than 576 bits would be bad for a number of reasons.
My objective is to test the strength of the matrix multiplication as a
primitive. If it looks good, I may try building a faster stream cipher
around it. Even as it is, I don't think Storin is terribly slow on
24-bit DSPs.
You can fetch the package from the usual place (which, if memory serves,
is http://www.wizard.net/~echo/crypto-contest.html) if you like. You
can get just the paper, as compressed postscript, from my own web pages
at http://www.excessus.demon.co.uk/crypto/storin.ps.gz.
Any cryptanalysis is welcome.
-- [mdw]
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: pentium timings
Date: Mon, 22 May 2000 11:17:23 -0600
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
[ ... ]
> Well if the cpu doesn't do the rdtsc, won't it store the wrong
> values? I can see my routines being off by a couple cycles
> because of the pop ebx/ecx, but other then that, should be
> close.
This is getting ridiculous -- as far as sci.crypt goes (i.e. from a
vewpoint of simply using it) your code is just plain wrong.
If you want to discuss the sources of the problems in detail,
comp.lang.asm.x86 would be a reasonable place to do so -- I'll be
happy to go over the problems and their cures in considerable detail
there. It's just not topical here...
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: James Felling <[EMAIL PROTECTED]>
Subject: Re: Q: Recording on magnetic cards
Date: Mon, 22 May 2000 12:26:03 -0500
I think that I may have a solution to this mystery.
My guess is that there is a central account server. The cards are inductive
and work in a similar manner to the anti-theft tags used in many stores.
The card is presented. It gets "pinged" by the antena and responds with a
"pong" of its own at a characteristic frequency(ies) that uniquely ID the
card. The account is then billed. The Mag stripe is there as a backup
method in case of reader failure or other issues.
------------------------------
Date: Mon, 22 May 2000 10:38:35 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Is OTP unbreakable?
It is provable (and obvious) that if you do not know the random stream
that has been mixed with the ciphertext, and if the stream is genuinely
random, you cannot know what the plaintext is. Kahn has a simple
description of this.
But all of this does not make OTP the perfect cipher. A cipher has to
be used by flesh-and-blood humans (poor slobs, glad they're not like you
and me ;-)), over imperfect communication links, in a world filled by
hostiles and snoopers and "spoofers," and it even involves computers
which never fail.. never fail.. never fa.%GENERAL ERROR READING DRIVE C:
ABORT, RETRY, IGNORE?
;-)
>Richard Herring wrote:
> Sure. I'm just pointing out that the "classical" OTP may be totally
> *secret* but that's not the same thing as being *secure*.
>
==================================================================
Sundial Services :: Scottsdale, AZ (USA) :: (480) 946-8259
mailto:[EMAIL PROTECTED] (PGP public key available.)
> Fast(!), automatic table-repair with two clicks of the mouse!
> ChimneySweep(R): "Click click, it's fixed!" {tm}
> http://www.sundialservices.com/products/chimneysweep
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Patent state of Elliptic Curve PK systems?
Date: Mon, 22 May 2000 12:35:41 -0500
Frank M. Siegert wrote:
>
> I am just thinking about integrating a form of public key encryption
> in one of my software products, however I would like to be free of any
> patent problems. So if I should build in a form of elliptic curve PK
> system will I stumble into the deep waters of the sea of patents?
Not if you stick with software. Most ECC patents cover specific
hardware speedups or special fields. Too much has been in the
public domain for too long for this to be a real threat.
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: ZKPs in practice?
Date: 22 May 2000 11:05:50 -0700
In article <8g43a3$sd4$[EMAIL PROTECTED]>,
David A Molnar <[EMAIL PROTECTED]> wrote:
> The recent question on "an introduction to zero-knowledge proofs"
> had me thinking : where have zero-knowledge proofs been implemented
> in the real world?
I believe Schnorr signatures have their roots in an efficient
zero-knowledge proof of identity. (Fiat-Shamir signatures, too.)
But I might have the details wrong -- it may be some notion related
to zero-knowledge, and not strictly speaking zero-knowledge, so don't
trust me here.
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Blowfish Claims ... something not right
Date: 22 May 2000 11:11:07 -0700
It's hard for me to imagine a reasonable scenario where we should
be worried about exhaustive keysearch attacks on 256-bit keys. If
not for defense against keysearch, what do longer keys buy you?
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Patent state of Elliptic Curve PK systems?
Date: 22 May 2000 18:17:30 GMT
In article <[EMAIL PROTECTED]>,
Mike Rosing <[EMAIL PROTECTED]> wrote:
>Frank M. Siegert wrote:
>>
>> I am just thinking about integrating a form of public key encryption
>> in one of my software products, however I would like to be free of any
>> patent problems. So if I should build in a form of elliptic curve PK
>> system will I stumble into the deep waters of the sea of patents?
>
>Not if you stick with software. Most ECC patents cover specific
>hardware speedups or special fields. Too much has been in the
>public domain for too long for this to be a real threat.
Are you sure of that? The most interesting ECC variant is ECC over
GF(2^n) with optimal normal basis representation, since you can do that
in software without any multiplication. But I thought it was patented
by Certicom. Is it not? What about ECC over GF(2^n) in general, an
obvious method if there ever was one?
------------------------------
From: [EMAIL PROTECTED] (Gisle Sælensminde)
Subject: Re: pentium timings
Date: 22 May 2000 20:27:10 +0200
In article <[EMAIL PROTECTED]>, Mok-Kong Shen wrote:
>
>
>"Gisle Sælensminde" wrote:
>
>> I haven't tried Tom's code, but most operation systems runs each thread
>> for slices of 10-100 ms at a time. On a 100 MHz computer with 10 ms time
>> slices, that is 1_000_000 cycles, which means that the probability of a context
>> swich in the middle is small if you measure ciphers, which in most cases runs
>> on less than 1000 cycles.
>
>A supplementary question: If a run takes such a small time, wouldn't
>the initialization time of the thread make out a substantial portion of
>the total time measured? Thanks.
It seems for me like you not ar talking about measurement of
cpu-cycles, but cpu time, and that is quite different.
When meassuring cpu cycles you basicly do the following:
1. read the cycle-counter
2. do _one_ encryption or whatever you want to meassure
3. read the cycle counter again
4. the cycle count is the difference between the two
measurement - fixed cost (the measurement costs some clk)
Reading of the cycle counter is a thing you typically must do
in assembly, and not all processors have a cycle counter.
The older x86 processors have not such an instruction.
Due to that, it's common to meassure the CPU-time by testing
how long a large number of encryption takes (say 1_000_000),
and find an estimate of the cycle count from the number of
seconds a test program used and the clock frequency of the
test computer.
This is a far less precise way of measuring clock cycles, and
things like startup time of the test program and other things
becomes a part of the timing. For that reason you must run
a large number of encryptions, and do the test several times
to get anything near an accurate result. A clock cycle
counter will usually be more precise.
To write a clock cycle counter is not trivial, even if you
have an instruction for it. As other discussed in this thread,
there are several oddities and incompatibilities between
processors.
--
Gisle Sælensminde ( [EMAIL PROTECTED] )
ln -s /dev/null ~/.netscape/cookies
------------------------------
Crossposted-To: sci.math
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: More on Pi and randomness
Reply-To: [EMAIL PROTECTED]
Date: Mon, 22 May 2000 17:55:40 GMT
In sci.crypt r.e.s. <[EMAIL PROTECTED]> wrote:
: "Clive Tooth" <[EMAIL PROTECTED]> wrote ...
: [...]
: | Some things are known about the decimal digits of pi
: | in general. For example, for no positive integer n
: | are the digits n thru 100*n all equal to zero.
: Some such things are known in general, but I think that
: that last sentence isn't one of them [...]
It is - in fact the bound can be made smaller than 100*n - it can be
reduced to 41*n. See the reference I presented earlier for details.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ UART what UEAT.
------------------------------
From: Helger Lipmaa <[EMAIL PROTECTED]>
Subject: Re: pentium timings
Date: Mon, 22 May 2000 23:28:26 +0300
Jerry Coffin wrote:
> In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
> says...
>
> [ ... ]
>
> > If you maintain a webpage, I suggest that you put it there for convenient
> > access by other people.
>
> I'm perfectly happy to provide it to anybody who wants it, but I
> don't maintain a web page. Perhaps one of these days I'll get around
> to doing that, but no such thing exists at the present time.
A good measuring code can be downloaded from http://www.agner.org/assem. An
explanation (a quite good one) is present at his "How to optimize...". Sample
code is also included (although I dislike it due to its complexity). I
benefited a lot from Agners manual when writing Pentium II assembly
implementations of AES finalists (see http://www.tcm.hut.fi/~helger).
Partially, this manual is more complete than Intels official manuals.
Helger
http://www.tcm.hut.fi/~helger
------------------------------
From: [EMAIL PROTECTED] (Will Dickson)
Subject: Re: About Hardware RNG
Date: Mon, 22 May 2000 18:43:06 GMT
[EMAIL PROTECTED] (Guy Macon) wrote:
>In article <[EMAIL PROTECTED]>,
>[EMAIL PROTECTED] wrote:
>>
>>[EMAIL PROTECTED] (Guy Macon) wrote:
>>
>>>How does the circuit determine the threshhold to compare the noise to
>>>in order to decide whether to call the current bit a 1 or a 0? Is this
>>>a logic input, comparator, op-amp, Transistor (FET or bipolar?) or what?
>>
>>My circuit (I presume you mean that one, rather than the one Tom
>>found) uses split supplies (+/- 15V) and uses a plain op-amp
>>comparator to compare the signal to 0V. The noise source is
>>capacitively coupled so the capacitor output oscillates about 0V.
>
>You have a 0/1 bias then. The input to the opamp is slightly
>imperfect, and thus there is a small offset. Have you tried
>any long runs with a count of how many zeros and ones you get?
I posted some results earlier on this thread, but yes, there is a
definite bias. The arithmetic mean is in the 140's when it ought to be
127.5.
>
>I also suspect that there is a slight corolation between sucessive bits.
There is a little, but not very much. Obviously it varies between
samples, but it's very little larger than one sees from good
ciphertext or PRNG output. The correlation is negligible but the bias
is significant. But that's OK, since I hash it a lot before I use it.
------------------------------
Crossposted-To: sci.math
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: More on Pi and randomness
Reply-To: [EMAIL PROTECTED]
Date: Mon, 22 May 2000 18:06:33 GMT
In sci.crypt Mike Kent <[EMAIL PROTECTED]> wrote:
: Guy Macon wrote:
:> [EMAIL PROTECTED] wrote:
:> >Some things are known about the decimal digits of pi in general. For
:> >example, for no positive integer n are the digits n thru 100*n all equal
:> >to zero.
:>
:> ...which is NOT true of a true random set of decimal digits.
:> Thus proving that PI doesn't behave randomly.
: Not really; this is a statement about the digits in _a particular location_
: of the decimal expansion of pi. [...]
He said this is true for *any* n.
I believe that no random stream is likely to display this property (if
you are prepared to test enough values of n) - since this property has
been described as a way to win money by betting on the digits of PI.
If so, this is indeed a way in which PI systematically deviates from
statistical randomness.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ VIPAR GAMMA GUPPY.
------------------------------
From: Helger Lipmaa <[EMAIL PROTECTED]>
Subject: Re: Blowfish Claims ... something not right
Date: Mon, 22 May 2000 23:40:50 +0300
Bohdan Tashchuk wrote:
> Paul Rubin wrote:
> >
> > >8 cycles a byte with blowfish? That's hard to believe, mainly
> > >because the look ups in the F function would be a source of
> > >bottleneck.
> >
> > Wait a sec, I must have meant 8 cycles per *round*. This is coming
> > back to me. That would be 16 cycles/byte.
>
> The value of 16 cycles/byte is a little better than the performance claim
> by Schneier et all in the book they wrote called
>
> The Twofish Encryption Algorithm
> ISBN 0-471-35381-7.
>
> But since the book was written a year or two ago, they may have improved
> their algorithm in the meantime. In the book in Table 10.1 they claim that
> Blowfish runs at 19.8 clocks/byte on a Pentium. The Counterpane web page
> (presumably more recent than the book) that was referenced at the start of
> this thread claims 18 clocks/byte on a Pentium.
>
> More interesting to me is Twofish, since it has twice the ley length and is
> faster. In the book they give a lot of different values for various options
> of pre-computing keys, various number of plaintext bytes, ASM versus C,
> etc. As an asymptotic case see:
>
> Table 5.3. Best Speed to Encrypt a Message
> with a New 128-bit Key on a Pentium Pro
>
> They claim:
>
> for 1 Megabyte of plaintext
> Total Clocks per Byte is 16.1
>
> The key setup time isn't too bad, because:
>
> for 1 Kilobyte of plaintext
> Total Clocks per Byte is 24.5
>
> Put another way, an 800 MHz P3 processor is capable of encrypting Twofish
> at roughly 50 Megabytes per second, which is pretty darn good IMHO.
For uptodate information about the speed of Twofish and other AES candidates,
see http://www.tcm.hut.fi/~helger/aes. Twofish achieves 16.1 cycles per byte
if the so called compiled code is used (which basically is a restricted form
of self-modifying code). The best normal implementation takes 17.3 cpb. This
should be compared, e.g., to RC6 (13.9 cpb) or Rijndael (14.8 cpb). RC5 could
be faster (I'm not sure, never tried - RC5 is obsolete; 16-rounds is not
recommended again due to weaknesses in cipher). Blowfish is not faster.
Helger Lipmaa
http://www.tcm.hut.fi/~helger
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: 3DES SOURCE
Date: Mon, 22 May 2000 14:36:16 -0400
Karim A wrote:
>
> Hi all,
>
> Where can I find source code of Triple DES encryption ?
www.openssl.org
paul
------------------------------
From: [EMAIL PROTECTED] (Will Dickson)
Subject: Re: Blowfish Claims ... something not right
Date: Mon, 22 May 2000 19:18:22 GMT
[EMAIL PROTECTED] (David A. Wagner) wrote:
>It's hard for me to imagine a reasonable scenario where we should
>be worried about exhaustive keysearch attacks on 256-bit keys. If
>not for defense against keysearch, what do longer keys buy you?
Extra resistance to implementational cockups. While 256 bits (and
probably 128 bits) of _entropy_ are safe, maybe the cipher's execution
context provides it with a key that is 128 bits long (say) but
contains only on average 4 bits of entropy per byte. Then you only
have 64 bits of entropy, which might well be crackable in a few years.
OTOH if the same flawed key generator supplies a 448 bit key, then it
contains 224 bits of entropy, which is still safe. As many have
pointed out (and I have recently being discovering) generating entropy
is rather harder than it's sometimes given credit for.
Alternatively, maybe the implementor got it wrong and came up with
something s/he thought was blowfish, but wasn't, and either didn't
know about the standard test vectors or neglected to test against
them. (This happened to me as well - I found out about the test
vectors long after I found out about the algorithm, and nearly put out
a beta featuring a blowfish "variant" that effectively had 1 round
instead of 16.) Such a broken cipher might just still be OK if it has
a lot of overkill in the keyspace - at least until the mistake got
discovered and patched.
Will.
------------------------------
** 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
******************************
