Cryptography-Digest Digest #467, Volume #12 Thu, 17 Aug 00 12:13:00 EDT
Contents:
Crypto Coprocessor on Javacard ([EMAIL PROTECTED])
Re: New Stream Cipher like SEAL ([EMAIL PROTECTED])
Re: New Stream Cipher like SEAL ([EMAIL PROTECTED])
Re: OTP using BBS generator? (Mark Wooding)
Re: New Stream Cipher like SEAL ("Scott Fluhrer")
Re: Funny Observation (SCOTT19U.ZIP_GUY)
Re: Cracking RC4-40 in FPGA hardware ("CMan")
Re: 215 Hz five-qubit quantum processor (Bernd Paysan)
Help with a reference from Kahn. (James Muir)
Re: Crypto Related Professional Attitude ("CMan")
Re: New Stream Cipher like SEAL (Mark Wooding)
Re: WAP gateway to WWW - Will this configuration really fly from a security
perspective ? (Mark Currie)
Re: New Stream Cipher like SEAL ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Crypto Coprocessor on Javacard
Date: Thu, 17 Aug 2000 14:06:43 GMT
I am interested to know if anyone has benchmarked Crypto Functions on a
Javacard with and without a crypto processor on the card...
3DES encryption
1024 RSA Key generation
etc
What type of speed improvement factors does one get , with the crypto
coprocessor.
TIA
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: New Stream Cipher like SEAL
Date: Thu, 17 Aug 2000 14:08:14 GMT
In article <8ngg16$dp0$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> hello tom
>
> one question
> why in your c code
>
> return (x<<(r&31)) | (x>>((32-r)&31));
>
> you do &31
>
> the processor realize the mask
> automatically no ???
>
> another prob i pass your cipher with
> diehardc and the result is not very good
>
> The tests OPSO, OQSO and DNA
>
> Output: No. missing words (mw), equiv normal variate (z), p-value (p)
> mw z p
> OPSO for sc1.dat using bits 23 to 32 157695
54.433
> 1.0000
> OPSO for sc1.dat using bits 22 to 31 146631
16.282
> 1.0000
> OPSO for sc1.dat using bits 21 to 30 142867
3.302
> 0.9995
> OPSO for sc1.dat using bits 20 to 29 141798 -
0.384
> 0.3505
> OPSO for sc1.dat using bits 19 to 28 142008
0.340
> 0.6332
> OPSO for sc1.dat using bits 18 to 27 142155
0.847
> 0.8015
>
> value 1.0000 is not recommended !!!
Any hints onto why only the upper bits of the output are non-random? I
don't actually have the faintest clue right now...
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: New Stream Cipher like SEAL
Date: Thu, 17 Aug 2000 14:08:15 GMT
In article <8ngg16$dp0$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> hello tom
>
> one question
> why in your c code
>
> return (x<<(r&31)) | (x>>((32-r)&31));
>
> you do &31
>
> the processor realize the mask
> automatically no ???
>
> another prob i pass your cipher with
> diehardc and the result is not very good
>
> The tests OPSO, OQSO and DNA
>
> Output: No. missing words (mw), equiv normal variate (z), p-value (p)
> mw z p
> OPSO for sc1.dat using bits 23 to 32 157695
54.433
> 1.0000
> OPSO for sc1.dat using bits 22 to 31 146631
16.282
> 1.0000
> OPSO for sc1.dat using bits 21 to 30 142867
3.302
> 0.9995
> OPSO for sc1.dat using bits 20 to 29 141798 -
0.384
> 0.3505
> OPSO for sc1.dat using bits 19 to 28 142008
0.340
> 0.6332
> OPSO for sc1.dat using bits 18 to 27 142155
0.847
> 0.8015
>
> value 1.0000 is not recommended !!!
Any hints onto why only the upper bits of the output are non-random? I
don't actually have the faintest clue right now...
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: OTP using BBS generator?
Date: 17 Aug 2000 14:36:17 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> Sorry, doesn't this result of Vazirani and Vazirani conflict with the
> sentence 'There is no proven reduction in the other direction' above,
> or have I understood your text entirely in the wrong manner? Could you
> please say a bit more?
You've misunderstood.
We have QRP <=_P IFP, but we *don't* have IFP <=_P QRP. The BBS paper
shows QRP <=_P BBS. The V&V paper shows IFP <=_P BBS, which doesn't
contradict the previous statements: we have QRP <=_P IFP <=_P BBS.
If someone had shown that BBS <=_P QRP then that would have been
interesting.
> I hope that this efficient choice does not result in severe
> reduction of the space of N.
No. It offers a *much* larger space of N than any other method I know
of for obtaining guaranteed cycle bounds, including the `special' primes
which Ritter likes so much. Indeed, it's the increase of the space for
N which makes the method efficient.
I'll try to get an implementation of my method and offer a few examples
of numbers chosen using my method.
> Unpredictablility to the right seems to be actually more useful, isn't
> it?
I think that both are useful.
This is just a gap in my knowledge or understanding -- I'm sure that
this property has actually been proven somewhere.
> But to be meaningul one needs to know what that large class of tests
> is, or more exactly one should have a practical way of determining
> whether a given test belongs to that set. Is there any availble
> information/literature to that effect?
There's the name of the class. It's rather precise. Probabilistic
statistical tests are the usual sort. They have a probability of
failure, and there are two types of failures: type I (which misidentify
random things as being nonrandom) and type II (which misidentify
nonrandom thins as being random). The `poly-time' qualifier just limits
the range of tests to those taking an amount of time bounded by a
polynomial in the size (bit-length) of the BBS modulus.
-- [mdw]
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: New Stream Cipher like SEAL
Date: Thu, 17 Aug 2000 07:21:05 -0700
<[EMAIL PROTECTED]> wrote in message news:8nfapv$4r1$[EMAIL PROTECTED]...
> This is a stream cipher like SEAL where it stretches a 32-bit value
> into a larger value. I don't see any obvious flaws in it so I figured
> someone here may want to beat at it before I actually write up a report
> on it.
>
> The C source (really easy to read) is at
>
> http://www.geocities.com/tomstdenis/files/sc1.c
>
> On my K6-2 I get 15 cycles per byte with the C code which is really
> kinda cool.
>
> Please comment if possible.
Well, one thing that is vaguely troubling is that each fundamental step
(varients of which you do 16 times between state outputs):
> A = ROL(A ^ D, D>>27) + key[D&1023];
is noninvertable, and so loses a little entropy. Not a whole lot, but if
you do this enough times, you start being liable to getting into a loop, or
start repeating the output that occurs for another seed. You should
definitely restrict how much output you can generate for a single seed.
Alternatively, to make sure that neither a loop nor two distinct seeds can
converge to the same sequence after a period of time, one possibility would
be to (once every nextstate function) update the state based on the seed and
the possition in the output sequence, as (for example):
/* now create the output */
for (i = 0; i < len; i++) {
for (j = 0; j < PASSES; j++) {
A = ROL(A ^ D, D>>27) + key[D&1023];
B = ROL(B ^ A, A>>27) + key[A&1023];
C = ROL(C ^ B, B>>27) + key[B&1023];
D = ROL(D ^ C, C>>27) + key[C&1023];
}
*out++ = A + key[D&1023]; *out++ = B + key[C&1023];
*out++ = C + key[B&1023]; *out++ = D + key[A&1023];
/* Make sure two different seeds create distinct sequences, */
/* even if they happen onto the same state */
C += seed;
/* Make sure we never get into a loop in less than 4G outputs */
B += i;
}
However, this does leave in the weakness that (for example), if we have two
streams with last outputs XXXX and YYYY, and if XXXX and YYYY have exactly
the right differential, then the very next output for each stream will be
identical. However, this is better than the analogous problem we had
before, where the two output streams would then be identical for *all*
outputs afterwards.
On a different topic, you may want to change the order of the operations in
the inner loop, as in:
D = ROL(D ^ C, C>>27) + key[C&1023];
B = ROL(B ^ A, A>>27) + key[A&1023];
C = ROL(C ^ B, B>>27) + key[B&1023];
A = ROL(A ^ D, D>>27) + key[D&1023];
This does make differentials propogate slower through the cipher in the
forward direction, however, I would claim that that isn't very important, as
the attacker can use differentials in both directions, and in the original
code, differentials propogated slowly in the reverse direction. In the
revised code, I claim that forward and reverse differentials are somewhat
better than the original reverse differentials, and as an added bonus, the
code would be much more parallizable.
--
poncho
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Funny Observation
Date: 17 Aug 2000 14:45:46 GMT
[EMAIL PROTECTED] (John Savard) wrote in
<[EMAIL PROTECTED]>:
>On Wed, 16 Aug 2000 20:02:06 GMT, [EMAIL PROTECTED] wrote, in part:
>
>>Anyone ever notice that Dave Scott calls himself the 'Zip Guy' but
>>known of his software involves the deflate algorithm.
>
>Ah, but what he calls (called?) himself the "Scott19u_zip" guy, and
>his encryption package, no doubt, _is_ distributed in a file
>compressed in the .ZIP format.
>
>That, for encryption, he prefers adaptive arithmetic compression to
>Lempel-Ziv is one thing I _don't_ fault him for, I think his judgement
>is correct on that.
>
>My own tastes run towards having a compressor with canned starting
>information for various types of file. For text files, I would use a
>multi-state Huffman, with one state containing symbols for word
>lengths - and a _word_ dictionary maintained on Lempel-Ziv principles.
>
>John Savard
>http://home.ecn.ab.ca/~jsavard/crypto.htm
>
John then write ONE what is stopping you?
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website **now all allowed**
http://members.xoom.com/ecil/index.htm
Scott rejected paper for the ACM
http://members.xoom.com/ecil/dspaper.htm
Scott famous Compression Page
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
"The road to tyranny, we must never forget, begins with the destruction
of the truth."
------------------------------
From: "CMan" <[EMAIL PROTECTED]>
Subject: Re: Cracking RC4-40 in FPGA hardware
Date: Thu, 17 Aug 2000 08:00:06 -0700
Go ahead and compute the value of the engineering time, the fabrication,
debug and test time as well as the cost of writing specialized code to
interface with the FPGA card. Compare this wit the cost of implementing an
RC4 and MD5 loop on a few PC's in a cluster using diskless COTS hardware and
Linux.
I think you will find the later is much cheaper if you are building just one
unit.
It is really hard to believe that anyone would ever need to build more than
one (codebreaking cluster). If there is a need for hundreds of clusters,
the economics change drastically.
Unless the FPGA could bring a massive increase in raw performance per chip,
the PC route would appear to be better. That was really the crux of the
original discussion. The question is: Is there a really clever way to
arrange the FPGA hardware so as to achieve a massive increase in raw code
busting performance using custom hardware?
After seeing the discussion, I feel that the answer is no.
Just my opinion.
JK
--
CRAK Software
http://www.crak.com
Password Recovery Software
QuickBooks, Quicken, Access...More
Spam bait (credit E. Needham):
root@localhost
postmaster@localhost
admin@localhost
abuse@localhost
webmaster@localhost
[EMAIL PROTECTED]
[EMAIL PROTECTED]
[EMAIL PROTECTED]
Paul Rubin <[EMAIL PROTECTED]> wrote in message
news:8ngkmn$er2$[EMAIL PROTECTED]...
> In article <8ngap1$86k$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
> >In article <8mco74$erk$[EMAIL PROTECTED]>,
> > [EMAIL PROTECTED] wrote:
> >
> >>
> >> Each cycle requires a memory read and a pair of 8 bit adds, so 10ns
> >> looks like a good estimate. Then we have 10 usec/key, or 10^5 keys
> >> per second. 2^40 is about 10^12, so even with one such piece of
> >> hardware we have 10^7 seconds, or about 2800 hours to search all
> >> keys. We expect success on the average in 1/2 this time, or 1400
> >> hours.
> >>
> >
> >Sorry guys, I've seen your discussion too late. I'd like to say that it
> >is possible to achieve the speed of 280.000 key/sec on Pentium II/333
> >(or 45 days to finish 2^40 keys) when cracking simple RC4 (like PDF
> >implementation) and 180.000 keys/sec (or 70 days) when cracking RC4+MD5
> >(like MS Word does). It means that on _ONE_ modern P III/1000 the
> >average time to crack RC4-40 is one week, not 1400 hours ;-).
>
> Remember that the Xilinx chip had 4 of those blocks with 1400 hour
> average crack time. So the 4 blocks working together crack in 350
> hours on average--half the speed of that PIII/1000. That means a
> machine with 50 Xilinx chips can *always* (worst case) crack in under
> 24 hours and you'd need 25 PIII's to do the same. But the Xilinx
> chips cost about 10 USD each and use a lot less power than the
> Pentiums. The 50-chip Xilinx machine can probably be built in a
> single PC-sized box (card cage with a few wire-wrapped boards) with
> materials cost equal to not much more than one or two PIII machines.
>
> To the person who was doing this project: any news?
------------------------------
Date: Thu, 17 Aug 2000 16:19:52 +0200
From: Bernd Paysan <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: 215 Hz five-qubit quantum processor
Paul Rubin wrote:
> That's not even in NP. The shortest decompressor might have
> exponential (or worse) running time or space requirements.
There's a derivative, the practical compressor. It assigns cost for
decompressing, and costs for transfer. I.e. if you can transfer a bit in
1 million instructions, a compression that needs one million instruction
cycles more to complete isn't worth if it only saves one bit. So you can
generate programs for your VM, and simulate them for n*1M cycles (n is
the bitness of the result), and look at the first program that matches
your criteria. Same goes for space (you can abort all programs that take
"too much" space, whatever your requirement for the space limitation
is). This will not give the shortest program, but the shortest
"practical" program. And the search algorithm for sure is NP, but with
the positive side that for a 2^n input, it has only to test up to 2^m
outputs, where m is the bit length of the compressed file (which should
be smaller than n).
--
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://www.jwdt.com/~paysan/
------------------------------
From: James Muir <[EMAIL PROTECTED]>
Subject: Help with a reference from Kahn.
Date: Thu, 17 Aug 2000 15:00:31 GMT
In a paper on side channel cryptanalysis the authors ( Kelsey, Schneier,
Wagner and Hall ) mention a reference from Kahn's "The Codebreakers"
where a mechanical enciphering device was comprised when an adversary
recorded the clicks of the gears as it operated. I'd like to read that
passage from Kahn myself -- could someone point me to the right chapter
or page?
Thanks.
-James
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "CMan" <[EMAIL PROTECTED]>
Subject: Re: Crypto Related Professional Attitude
Date: Thu, 17 Aug 2000 08:19:49 -0700
<begin piffle>
Perhaps they respond but under assumed names or in a stenographic context.
I understand Monica Leweinski writes here all the time under the moniker
"Deep Cigar". (That would be Monica's moniker).
Or maybe they have real, honest-to-god lives to lead and don't have time for
the piffle produced by gnomes such as we. :-))
<end piffle>
JK
--
CRAK Software
http://www.crak.com
Password Recovery Software
QuickBooks, Quicken, Access...More
Spam bait (credit E. Needham):
root@localhost
postmaster@localhost
admin@localhost
abuse@localhost
webmaster@localhost
[EMAIL PROTECTED]
[EMAIL PROTECTED]
[EMAIL PROTECTED]
tomstd <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> This post is for the professionals such as Biham, Rivest,
> Schneier, Wagner, Shamir, Coppersmith, etc...
>
> Why don't you guys ever participate even a little in sci.crypt?
>
> No offense but you claim to be active in crypto, and honest you
> guys know way more then most of us (including me). So why not
> post from time to time excluding posts to plug your papers?
>
> It seems like there are alot of arrogant professionals in the
> world. Honestly there are what 50 posts a day here, and about
> 25 active posters. It's not like there are 1000s of messages to
> read through so time is not an issue. It takes me about 30 mins
> to go through the news messages, often under 10mins since alot
> of posts are not within my resonable answering range.
>
> I agree that professionals are/may be busy and have work to
> attend to, but seriously so do I. Big deal. I post here
> because I want to learn and share. Why can't the big shots do
> the same?
>
> I invite the professionals (a.k.a big shots) to reply to this
> thread with their opinions since I want to know why they remain
> so silent when they apparently have lots to share.
>
> Sincerely,
> Tom
>
>
> -----------------------------------------------------------
>
> Got questions? Get answers over the phone at Keen.com.
> Up to 100 minutes free!
> http://www.keen.com
>
>
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: New Stream Cipher like SEAL
Date: 17 Aug 2000 15:40:22 GMT
Scott Fluhrer <[EMAIL PROTECTED]> wrote:
> Well, one thing that is vaguely troubling is that each fundamental step
> (varients of which you do 16 times between state outputs):
>
> > A = ROL(A ^ D, D>>27) + key[D&1023];
>
> is noninvertable, and so loses a little entropy.
It looks invertible enough to me. In particular, computing
A = ROR(A - key[D & 1023], D >> 27) ^ D
looks like a most convincing inverse function to me.
-- [mdw]
------------------------------
Subject: Re: WAP gateway to WWW - Will this configuration really fly from a security
perspective ?
From: [EMAIL PROTECTED] (Mark Currie)
Date: 17 Aug 2000 15:51:56 GMT
In article <8kHm5.4593$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
>
>Well, I thought ITSEC included just the parts that the card manufacturer
wanted,
It is true that ITSEC only tests against a set of manufacturer stated
objectives. Therefore if you purchase a certified device, you should read the
Security Target document which specifies the security objectives and how they
are met. The disadvantage of this is that important testing may be left out,
but the advantage is that you can add additional tests that other certification
standards may not do. If you are developing a device that you are trying to get
adopted in a big system that includes a variety of stakeholders from different
institutions, I would imagine that there would be wide enough scrutiny by all
the players, and that they would all have a say in the security objectives.
Having said that though, it is true that you don't easily find the type of
people capable of understanding all the applicable security threats.
>and in that respect its different from i.e. FIPS 140-1 level 4. The ITSEC-E6
>report I have seen, included no such things as physical panetration testing or
>side-channel attacks. But, there was some interesting formal methods used to
>'prove' the security from a theoretical view point, in fact the ITSEC report
>only included analysis of SW development and that this SW worked correct. HW
>where only analysed from its blueprint, no physical test/attacks at all...
It depends on the application. I know that penetration testing can be done if
the ITSEC certification is required for compliance to a signature law but this
may be dependant on the country and/or certification body.
Mark
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: New Stream Cipher like SEAL
Date: Thu, 17 Aug 2000 15:54:20 GMT
In article <8ngthl$kmi$[EMAIL PROTECTED]>,
"Scott Fluhrer" <[EMAIL PROTECTED]> wrote:
>
> <[EMAIL PROTECTED]> wrote in message news:8nfapv$4r1
$[EMAIL PROTECTED]
> > This is a stream cipher like SEAL where it stretches a 32-bit value
> > into a larger value. I don't see any obvious flaws in it so I
figured
> > someone here may want to beat at it before I actually write up a
report
> > on it.
> >
> > The C source (really easy to read) is at
> >
> > http://www.geocities.com/tomstdenis/files/sc1.c
> >
> > On my K6-2 I get 15 cycles per byte with the C code which is really
> > kinda cool.
> >
> > Please comment if possible.
> Well, one thing that is vaguely troubling is that each fundamental
step
> (varients of which you do 16 times between state outputs):
>
> > A = ROL(A ^ D, D>>27) + key[D&1023];
>
> is noninvertable, and so loses a little entropy. Not a whole lot,
but if
> you do this enough times, you start being liable to getting into a
loop, or
> start repeating the output that occurs for another seed. You should
> definitely restrict how much output you can generate for a single
seed.
Actually you are wrong. The inverse is merely
A = ROR(A - KEY[D&1023], D>>27) ^ D
So no "entropy" is lost in that step.
> Alternatively, to make sure that neither a loop nor two distinct
seeds can
> converge to the same sequence after a period of time, one possibility
would
> be to (once every nextstate function) update the state based on the
seed and
> the possition in the output sequence, as (for example):
>
> /* now create the output */
> for (i = 0; i < len; i++) {
> for (j = 0; j < PASSES; j++) {
> A = ROL(A ^ D, D>>27) + key[D&1023];
> B = ROL(B ^ A, A>>27) + key[A&1023];
> C = ROL(C ^ B, B>>27) + key[B&1023];
> D = ROL(D ^ C, C>>27) + key[C&1023];
> }
> *out++ = A + key[D&1023]; *out++ = B + key[C&1023];
> *out++ = C + key[B&1023]; *out++ = D + key[A&1023];
>
> /* Make sure two different seeds create distinct sequences, */
> /* even if they happen onto the same state */
> C += seed;
> /* Make sure we never get into a loop in less than 4G outputs
*/
> B += i;
> }
>
> However, this does leave in the weakness that (for example), if we
have two
> streams with last outputs XXXX and YYYY, and if XXXX and YYYY have
exactly
> the right differential, then the very next output for each stream
will be
> identical. However, this is better than the analogous problem we had
> before, where the two output streams would then be identical for *all*
> outputs afterwards.
>
> On a different topic, you may want to change the order of the
operations in
> the inner loop, as in:
>
> D = ROL(D ^ C, C>>27) + key[C&1023];
> B = ROL(B ^ A, A>>27) + key[A&1023];
> C = ROL(C ^ B, B>>27) + key[B&1023];
> A = ROL(A ^ D, D>>27) + key[D&1023];
>
> This does make differentials propogate slower through the cipher in
the
> forward direction, however, I would claim that that isn't very
important, as
> the attacker can use differentials in both directions, and in the
original
> code, differentials propogated slowly in the reverse direction. In
the
> revised code, I claim that forward and reverse differentials are
somewhat
> better than the original reverse differentials, and as an added
bonus, the
> code would be much more parallizable.
I want the strong avalanche though, that's what I hope will make it
secure. Note that I will have to use more passes with the reverse
direction and likely the code will be no faster because of that.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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
******************************
