Cryptography-Digest Digest #465, Volume #12 Thu, 17 Aug 00 08:13:01 EDT
Contents:
Re: New Stream Cipher like SEAL (Paul Rubin)
Re: My first serious (kinda) paper. (David A. Wagner)
Re: Cracking RC4-40 in FPGA hardware ([EMAIL PROTECTED])
Re: What is up with Intel? (David Blackman)
Re: OTP using BBS generator? (Mok-Kong Shen)
Re: New Stream Cipher like SEAL ([EMAIL PROTECTED])
Re: OT (Proposal of drafting rules of conduct of posting) (Mok-Kong Shen)
blowfish problem ("P. Pascual")
Re: OTP using BBS generator? (Mark Wooding)
Re: blowfish problem (Mark Wooding)
Re: blowfish problem (Perique des Palottes)
Re: New Stream Cipher like SEAL (Mark Wooding)
Re: Empathic encryption? (Rob Warnock)
Re: 215 Hz five-qubit quantum processor (John Savard)
Re: blowfish problem ("Dmitry Kompaneets")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: New Stream Cipher like SEAL
Date: 17 Aug 2000 05:27:22 GMT
In article <8nfr0p$mme$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
>Actually there are
>
>16 xors, 16 ands, 24 adds, 16 luts, 16 shrs and 16 rols
>
>Giving the best theoretical as
>
>shr, and, add, xor = 1 cycle
>luts = 2 cycles
>rols = 2 cycles
>
>For a total of (56x1) + (16)(2) + (16)(2) = 120 cycles minimum. Plus
>pointer management we are talking about 160 or more cycles.
I don't have the algorithm in front of me but maybe you can design
it so that superscalar processors can overlap the operations more.
Also, the luts and rols don't necessarily need 2 cycles. I'm not
sure how long they take on the p3/k6.
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: My first serious (kinda) paper.
Date: 16 Aug 2000 15:47:50 -0700
Your proposed key schedule has serious biases. I don't recommend it.
Consider the last line to modify subkey[x]:
subkey[x] = rotl(subkey[x], 13) * stuff;
This is multiplication modulo 2^32, and `stuff' may be modelled as
a uniformly random 32-bit number. Thus, the low bit of `subkey[x]'
is strongly biased towards zero (it is zero 75% of the time). This
is true for each value of `x', i.e., for each of the 16 subkey words.
In any case, it's not clear to me how one can imagine to evaluate a
key schedule in isolation, without also considering it in the context
of a cipher. (Ok, I know a few exceptions, but this isn't one of them.)
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Cracking RC4-40 in FPGA hardware
Date: Thu, 17 Aug 2000 09:20:44 GMT
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 ;-).
--
SY / C4acT/\uBo Pavel Semjanov
_ _ _ http://www.ssl.stu.neva.ru/psw/
| | |-| |_|_| |-| 2:5030/145.17@fidonet
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: David Blackman <[EMAIL PROTECTED]>
Subject: Re: What is up with Intel?
Date: Thu, 17 Aug 2000 20:19:30 +1000
John Savard wrote:
>
> On Sun, 13 Aug 2000 16:54:23 -0700, tomstd
> <[EMAIL PROTECTED]> wrote, in part:
>
> >On page four of the IntelRNG.pdf from cryptography.com they said
> >intel is patentning the von neuman rejector i.e with [0,0] and
> >[1,1] output nothing, output 0 for [1,0] and 1 for [0,1] which
> >hopefully lowers bias towards any given bit.
>
> >This idea is what 50 years old? How on earth can Intel patent
> >it?
>
> Nobody felt the need to do it in hardware before, so Intel can patent
> _that_ idea. But they can't patent von Neumann rejection in software
> for the reason you note.
>
> John Savard
> http://home.ecn.ab.ca/~jsavard/crypto.htm
Given the age of this idea, i suspect it would have been done in
hardware for the first 20 years if it was done at all. And it probably
was. People were interested in random numbers even then.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: OTP using BBS generator?
Date: Thu, 17 Aug 2000 13:02:54 +0200
Mok-Kong Shen wrote:
>
> I have finally been able to obtain a copy of the BBS
> paper. The result of interest here says that modulo the
> quadratic residuacity assumption, the x^2 mon N is
> polynomial-time unpredictable to the left. Is there
> any concrete relation between the quadratic residuacity
> assumption and the assumption of hardness of factoring N?
I like to request the experts on BBS to kindly help me
out in some additional difficulties detailed below:
>From the global structure of the paper (i.e. without
understanding the details), I don't see where the argument
'finding short cycles is equivalent to factoring', which
seems to be one of the points repeatedly stressed in this
thread, is actually used in the paper. Am I missing
something?
If (I don't yet know) there is no definite (quantifiable)
relation between QRA and the hardness of factoring, then
one practical issue would be how to select the size of
the modulus of BBS, i.e. how large should N be such that
its output is safe for use. Note that the theorem contains
in parentheses the phrase 'for sufficiently large n',
which means that n (which appraently affects the size of
N) is a function of delta and t and that function is
unknown, at least not given in the paper. Wouldn't that
simply mean that if we use very very large N then we
are safe, without however saying what that 'very very
large' exactly is?
The theorem seems in fact not to directly (formally)
involve the issue of cycle length that has been much
disputed in this thread till the present. Does QRA,
which is the assumption used in the theorem, involve
the issue of cycle length? I don't see any material in
the paper about that.
But then the paper does devote a whole section to cycle
length. Thus the motivation of this seems to be unclear.
Further it says in that section: 'Since the x^2 mod N
generator is an unpredictable pseudo-random sequence
generator (modulo QRA), it follows that on the average,
pi(x_0) [the period] will be long'. This seems to be
a rather vague conclusion. I mean it appears to be not
entirely evident why unpredictability necessarily leads
to long periods, excepting extremely short periods,
of course. Note that what is 'long' is itself a vague
concept. The section does treat on the other hand
special cases for which the cycle length can be computed
from N. But even for these, the period is for x_i, not
for LSB. So there can't be direct utility of the
results. (The relationship between the two types of
periods is stated in the paper as an open question.)
The theorem concerns unpredictability to the left.
Why 'to the left' and not 'to the right'? Does
the one implies the other or is 'to the right' of
no use in practice?
The paper employs the term 'probabilistic poly-time
statistical test'. Is this a theoretical concept
like the Kolmogorov complexity or does there exist a
conrete implementation of such a test or at least a
practically realizable specification of it?
Many thanks in advance.
M. K. Shen
==============================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: New Stream Cipher like SEAL
Date: Thu, 17 Aug 2000 10:50:19 GMT
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 !!!
bye !!
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: OT (Proposal of drafting rules of conduct of posting)
Date: Thu, 17 Aug 2000 13:16:11 +0200
Paul Pires wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote
> > I have the impression that there is some misunderstanding.
> > I explained already that the proposed paper is not and cannot
> > be a 'ban'. It's intended to be an expression of what the
> > majority hopes to be a desirable state (if the majority
> > could agree on something at all). Anyway, I don't think that
> > your last sentence could be widely generalized. For it would
> > ultimately mean that we wouldn't need guildlines of any kind
> > in society, which I am afraid wouldn't well function, at
> > least in the world in which we are currently living.
>
> This is a cultural mindset, not self evident fact.
>
> We don't need guidleines of any kind in society.
Does that mean in the western (or whichever you mean)
cultural mindset laws and the like are entirely redundant?
> Just because you observe what you percieve to be a cause and then an effect
> doesn't mean that they are related. This can be coincidence. There are rules
> and to a certain extent there is civilized behavior which paralells these
> rules (or at least once did). This is also a coincidence. The rules came
> about codifying the behavior of folks living up to a certain standard, an
> ethic. The behavior and the civilization was there before the rules. The
> rules are there as a warning from the civilized "Here is the line, cross it
> at your peril" When civilized behavior is at risk of extinction, it is from
> a lack of civilized people. Rules will not stem the tide and can even hasten
> the fall.
So rules are of no value/use and should be disposed off.
Is that right?
M. K. Shen
------------------------------
From: "P. Pascual" <[EMAIL PROTECTED]>
Crossposted-To: comp.lang.c
Subject: blowfish problem
Date: Thu, 17 Aug 2000 13:05:34 +0200
Hi all.
I have a problem that's breaking my head.
I need to encrypt text in C, so i have decided to use the blowfish
algorithm.
But the encrypted text generated are composed of control caracters, \0
inclusive.
This is a problem to me because the application is web oriented and
i need to work with the encrypted text, to append it in a URL, for example.
I have seen in the web some implementation in java of blowfish that generate
a text encrypted
like this:
305c083744ad2de7cc52488a53dea2ca85
This is what i need, but i don't know how to do it with C.
Any help would be very, very appreciated.
Antonio.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: OTP using BBS generator?
Date: 17 Aug 2000 11:25:29 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > I have finally been able to obtain a copy of the BBS paper. The
> > result of interest here says that modulo the quadratic residuacity
> > assumption, the x^2 mon N is polynomial-time unpredictable to the
> > left. Is there any concrete relation between the quadratic
> > residuacity assumption and the assumption of hardness of factoring
> > N?
Yes. There is a polytime reduction from factoring to QRP. Since the
quadratic residuosity problem is easy modulo a prime number (we have
x^{(p - 1)/2} = 1 (mod p) iff x is a quadratic residue mod p) we can
decide quadratic residuosity mod each factor of n separately.
There is no proven reduction in the other direction. However, we don't
have any algorithm which can decide quadratic residuosity mod n = p q
with probability better than 1/2 without factoring n. This doesn't mean
that no such algorithm can exist.
The result is then that factoring is at least as difficult as QRP.
> I like to request the experts on BBS to kindly help me out in some
> additional difficulties detailed below:
>
> From the global structure of the paper (i.e. without understanding the
> details), I don't see where the argument 'finding short cycles is
> equivalent to factoring', which seems to be one of the points
> repeatedly stressed in this thread, is actually used in the paper. Am
> I missing something?
Firstly: in 1984, Vazirani and Vazirani showed that predicting the
output of the x^2 mod N generator reduced to factoring n. Since
traversing a cycle evidently permits prediction of the generator's
output, it must therefore also reduce to factoring n.
If we stick with the original 1982 paper by Blum, Blum and Shub, they
prove that any advantage in predicting the generator reduces to deciding
quadratic residuosity with the same advantage (except that the advantage
here is amplifiable). With this result, we see that traversing a cycle
allows prediction of the generator's output with advantage 1/2 (i.e.,
probability 1) and hence immediately reduces to determining quadratic
residuosity with advantage 1/2.
> If (I don't yet know) there is no definite (quantifiable) relation
> between QRA and the hardness of factoring, then one practical issue
> would be how to select the size of the modulus of BBS, i.e. how large
> should N be such that its output is safe for use.
Make N large enough that factoring N is impractical.
> Note that the theorem contains in parentheses the phrase 'for
> sufficiently large n', which means that n (which appraently affects
> the size of N)
If you read the paper, n = |N| = \lceil \log_2 N \rceil is the bit
length of N. It is n, the length of N, which is the parameter for the
polynomial bounds described in the paper.
> The theorem seems in fact not to directly (formally) involve the issue
> of cycle length that has been much disputed in this thread till the
> present. Does QRA, which is the assumption used in the theorem,
> involve the issue of cycle length? I don't see any material in the
> paper about that.
No, the subject of period lengths doesn't occur in the main proof. It's
irrelevant. Finding cycles permits prediction, and *all* prediction
methods reduce to solving QRP, so there's no problem here.
> But then the paper does devote a whole section to cycle length. Thus
> the motivation of this seems to be unclear. Further it says in that
> section: 'Since the x^2 mod N generator is an unpredictable
> pseudo-random sequence generator (modulo QRA), it follows that on the
> average, pi(x_0) [the period] will be long'. This seems to be a rather
> vague conclusion.
> I mean it appears to be not entirely evident why unpredictability
> necessarily leads to long periods, excepting extremely short periods,
> of course.
I can't believe that this is really causing you difficulty. If cycles
are short enough to traverse, then you can predict the generator's
output very easily. Since the generator is unpredictable, such cycles,
if they exist, must be very difficult to find.
> Note that what is 'long' is itself a vague concept. The section does
> treat on the other hand special cases for which the cycle length can
> be computed from N. But even for these, the period is for x_i, not for
> LSB.
> So there can't be direct utility of the results. (The relationship
> between the two types of periods is stated in the paper as an open
> question.)
Not that open. The parity sequence period must be a factor of the <x_i>
period. If the <x_i> period has only large prime factors then the
parity sequence period must be large. If the <x_i> sequence has prime
period then the parity sequence period must be the same.
Then see my own work, elsewhere in this group, about efficient choice of
parameters for ensuring large period for the parity sequence.
Please, if anyone else knows any other work along these lines could
someone send me a reference! Otherwise, I'm rather tempted to write
something up formally.
> The theorem concerns unpredictability to the left. Why 'to the left'
> and not 'to the right'? Does the one implies the other or is 'to the
> right' of no use in practice?
This puzzles me too. I've certainly seen (e.g., in HAC) claims that BBS
is unpredictable in both directions, so there's certainly been some
work done here.
> The paper employs the term 'probabilistic poly-time statistical
> test'. Is this a theoretical concept like the Kolmogorov complexity or
> does there exist a conrete implementation of such a test or at least a
> practically realizable specification of it?
It's the name for a (large) class of statistical tests. It does what it
says on the tin.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Crossposted-To: comp.lang.c
Subject: Re: blowfish problem
Date: 17 Aug 2000 11:33:16 GMT
P. Pascual <[EMAIL PROTECTED]> wrote:
> I have seen in the web some implementation in java of blowfish that
> generate a text encrypted like this:
>
> 305c083744ad2de7cc52488a53dea2ca85
>
> This is what i need, but i don't know how to do it with C.
Someone has encoded the binary ciphertext using a little-known technique
called `hexadecimal'. You can extract the `hexadecimal representation'
of an octet x in C into a buffer by saying `sprintf(buf, "%02x", x);'.
The `hexadecimal representation' of a string of octets is the
concatenation of the representations of the individual octets. This
encoding expands the data by a factor of 2.
This is really simple stuff. Try reading books about C programming
before posting next time.
Oh, and this was off-topic in sci.crypt.
-- [mdw]
------------------------------
From: Perique des Palottes <[EMAIL PROTECTED]>
Crossposted-To: comp.lang.c
Subject: Re: blowfish problem
Date: Thu, 17 Aug 2000 13:33:25 +0200
"P. Pascual" wrote:
>
> ...But the encrypted text generated are composed of control
> caracters, \0 inclusive ... and i need to work with the
> encrypted text, to append it in a URL, for example.
> I have seen in the web ... a text encrypted like this:
> 305c083744ad2de7cc52488a53dea2ca85
> This is what i need, but i don't know how to do it with C.
So, haven't you noticed that strings like the one above are
the hexadecimal dump version (two hexdigits x original byte)
of the whatever original encrypted string? 'So suspicious
only characters there are digits amb abcdef... so use printf
and %02x format etc.
--
All true believers shall break their eggs at the convenient end.
news:soc.culture.catalan FAQ at http://www.gea.cesca.es/~ipa/SCC/
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: New Stream Cipher like SEAL
Date: 17 Aug 2000 11:37:04 GMT
[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 ???
No. In C, if you shift a value by its bit length or more, the behaviour
is undefined.
Some processors will give a zero result for a shift by a value greater
than the word length. Others will truncate the the shift amount.
Tom's got this one right.
> OPSO for sc1.dat using bits 23 to 32 157695 54.433
> 1.0000
Ouch! That's really bad.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Rob Warnock)
Subject: Re: Empathic encryption?
Date: 17 Aug 2000 11:47:01 GMT
Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
+---------------
| I can think of one kind of [bizarre?] stenography for sending
| information to a musician. Start with music which has been generated by
| a computer following various rules of composition... so it will be a
| good, well formed, though probably unimaginative piece of music. Then,
| every nth note, change that note so that it is, to a professional
| musician, obviously not right, and where, hopefully, the note that
| *should* be there, is also obvious. The difference between the note
| that *is*, and the note that *should be* is one nibble of data. Print
| the data as sheet music, and send it in the mail.
+---------------
*Exactly* that situation/algorithm was used in an old black&white Sherlock
Holmes movie (that's run several times on late-night T.V. in recent months).
The information being communicated was the hidden location of the loot from
a robbery. The sender was in prison for life. And the "message" was three
music boxes [manufactured by the inmate] whose tunes were *slightly* different
from one another.
+---------------
| Of course, you'd have to be a musical genius to be able to decode it
| by just listening to it.
+---------------
I *did* say it was a *Sherlock Holmes* story, didn't I? ;-} ;-}
-Rob
=====
Rob Warnock, 41L-955 [EMAIL PROTECTED]
Applied Networking http://reality.sgi.com/rpw3/
Silicon Graphics, Inc. Phone: 650-933-1673
1600 Amphitheatre Pkwy. PP-ASEL-IA
Mountain View, CA 94043
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: comp.arch
Subject: Re: 215 Hz five-qubit quantum processor
Date: Thu, 17 Aug 2000 11:47:45 GMT
On Wed, 16 Aug 2000 07:53:21 -0400, "Trevor L. Jackson, III"
<[EMAIL PROTECTED]> wrote, in part:
<quotes rearranged to allow further reply>
>Steve Newman wrote:
>> It occurred to me some years back that with the appropriate "magic
>> box", you could trivially implement a theorem prover for arbitrary
>> theorems. Simply generate all possible strings up to a certain
>> length, and run each string through a theorem checker to see if it
>> constitutes a proof for the theorem. This requires a theorem
>> checker, but that's not hard to write.
>> Could this algorithm be implemented in a (sufficiently advanced)
>> quantum computer? Presumably the length of the theorem would be
>> bounded by some value proportional (at best) to the number of bits
>> supported by the computer. Still, this would be a heck of a thing
>> if it worked.
Actually, it's the length of the _proof_ that would be bounded by the
number of qbits supported by the computer.
>> Computers have already caught up with human chess players... maybe
>> in a few more decades, mathematicians will succumb?
>> (Seems unlikely somehow, but still an interesting thought.)
>I think Godel v. Russell established the fact that this is not possible.
>Russell wanted to show that all of math was consistently derived from a small
>set of foundation premises. Godel showed that math is incomplete in the sense
>that not all truths can be deduced from the premises. Godel used a special kind
>of theorem that implied something like "This theorem is false". When you run
>that through a prover you get an undecidable result -- like talking to a person
>who says "I always lie".
>This can be made quite personal. For instance, "Steve Newman cannot
>consistently defend the truth of this theorem." If you act as a manual theorem
>prover, how will you resolved the truth/falsity of it?
It certainly is true that, despite Godel's proof, one can test the
finite number of strings of length N or less to determine if they are
proofs of a given theorem. This doesn't contradict Godel, since it is
entirely possible that, when looking for a proof, you might fail to
find one.
Because of Godel's proof, of course, some theorems don't have proofs
within a given formal system, and yet can be seen to be true through
metamathematics or through enlarging the formal system. So even a
quantum computer that proves mathematical theorems wouldn't abolish
creativity in mathematics.
Note, of course, that the number of bits required to express the proof
of an interesting mathematical theorem is somewhat larger than the
number of bits typically used as a key in cryptography, and so
mathematicians are much safer than cryptographers from the quantum
computer.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "Dmitry Kompaneets" <[EMAIL PROTECTED]>
Crossposted-To: comp.lang.c
Subject: Re: blowfish problem
Date: Thu, 17 Aug 2000 18:28:08 +0600
Hello,
What you are speaking about is called hex, it's when you convert each byte
into two chars. I presonally whould advise you to use base64, there you have
4 chars from 3 bytes. You can lookup a c base64 implementation on the net.
Dmitry
"P. Pascual" <[EMAIL PROTECTED]> wrote in message
news:8ngh4a$[EMAIL PROTECTED]...
> Hi all.
> I have a problem that's breaking my head.
> I need to encrypt text in C, so i have decided to use the blowfish
> algorithm.
> But the encrypted text generated are composed of control caracters, \0
> inclusive.
> This is a problem to me because the application is web oriented and
> i need to work with the encrypted text, to append it in a URL, for
example.
>
> I have seen in the web some implementation in java of blowfish that
generate
> a text encrypted
> like this:
>
> 305c083744ad2de7cc52488a53dea2ca85
>
> This is what i need, but i don't know how to do it with C.
>
> Any help would be very, very appreciated.
>
> Antonio.
>
>
>
------------------------------
** 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
******************************
