Cryptography-Digest Digest #606, Volume #12 Mon, 4 Sep 00 02:13:00 EDT
Contents:
Re: Extending RC4 to 16 bits ("Scott Fluhrer")
At http://www.widders.com I searched for ([EMAIL PROTECTED])
Re: A good MAC algorithm? (D. J. Bernstein)
Re: Is there any free encryption scripts in perl and VBScript (Paul Rubin)
Blum Blum Shub question (Benjamin Goldberg)
Re: Extending RC4 to 16 bits (Benjamin Goldberg)
Re: Patent, Patent is a nightmare, all software patent shuld not be allowed (Greggy)
Re: one-time pad question (Greggy)
Inquiry (Teo Li Xi)
Re: R: R: R: R: R: Test on pseudorandom number generator. (Terry Ritter)
----------------------------------------------------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Extending RC4 to 16 bits
Date: Sun, 3 Sep 2000 18:59:48 -0700
Guy Macon <[EMAIL PROTECTED]> wrote in message
news:8oudfm$[EMAIL PROTECTED]...
> Scott Fluhrer wrote:
> >
> >
> >
> >Guy Macon <[EMAIL PROTECTED]> wrote in message
> >news:8os40u$[EMAIL PROTECTED]...
> >> Scott Fluhrer wrote:
> >>
> >> >- Ignoring that, the idea of generalizing RC4 to include other bit
sizes
> >has
> >> >already appeared in the literature. It may be a bit too late to try
to
> >try
> >> >to place it under the quite restrictive Gnu copyright...
> >>
> >> Did said literature conclude anything about the effect on cryptographic
> >> strength?
> >
> >Well, just about any attack in the literature that considers different
RC4
> >sizes gets much harder as the size increases. This includes:
> >
> >- Mister and Tavares' Cycle Analysis (SAC 98)
> >- Mister and Tavares' Tracking Analysis (SAC 98)
> >- Jenkin's Gap Length observation (quoted in SAC 98)
> >- Jovan Golic's linear distinguisher (Eurocrypt 97)
> >- My digraph distinguisher (FSE 2000)
> >
> >Now, as for how much stronger RC4 gets as you get beyond sizes of 8 bits,
> >well, no one seems to studied that all that closely. After all, 8 bit
RC4
> >itself is quite a handfull, and until we have a fruitful attack against
> >that, it doesn't make much sense to start attacking something that
appears
> >to be considerably harder. However, every attack that we know about that
> >fails against RC4 would fail even more miserably against 16 bit RC4.
> >
>
> Are you absolutely sure about that?
>
> I have been playing around with a 4 bit version of ciphersaber
> (which is just RC4 with well defined I/O, file structure, etc)
> and of course found that attacks such as brute force key guessing
> are much easier, but it seemed to me that, unless I also reduced
> my passphrase, that mixing was better in the early rounds.
Well, are we talking about 4 bit RC4? Then, according to the SAC 98 paper,
you can reconstruct the permutation state using the "Tracking Analysis"
attack, which is essentially a backtracking approach. According to the
paper, against 4 bit RC4, they had to track a maximum of about 1 million
possible solutions, which is essentially trivial. If you have the paper,
look at Figure 5, the "n=4, nonzero keystream" line. Against 8 bit RC4,
this attack is impractical, and gets even harder for 16 bits...
>
> Could it be that, in order to insure that you get 100% positive
> benefit from using a 16 bit version of RC4, you have to make your
> original passphrase twice as big as well?
No, the original passphrase can remain the same size. Of course, you remain
exactly as vulnerable to passphrase search attacks as before, but you gain
no vulnerabilities to any known attack that tries to reconstruct the
permutation state (or passphrase) from the keystream.
--
poncho
------------------------------
From: [EMAIL PROTECTED]
Subject: At http://www.widders.com I searched for
Date: Mon, 04 Sep 2000 02:15:57 GMT
At http://www.widders.com I searched for
crypto
and found
20,748 matches
There were some other
useful things too.
Hope that helps!
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (D. J. Bernstein)
Subject: Re: A good MAC algorithm?
Date: 4 Sep 2000 01:32:28 GMT
Scott Fluhrer <[EMAIL PROTECTED]> wrote:
> I believe D J Bernstein has one as well.
http://cr.yp.to/hash127.html
The hash127 function has a much simpler definition than 120-bit UMAC,
has somewhat lower circuit complexity, and performs well on a much wider
variety of computers. It won't be difficult to implement the same hash
on the embedded processor under discussion.
120-bit UMAC is faster than hash127 for big packets on the Pentium III,
the UMAC target processor. However, hash127 is still faster for small
packets, so hash127 can handle higher attack volumes. On most other
processors---the original Pentium, for example, and the UltraSPARC---
hash127 is faster for all message sizes.
(By the way, has anybody been able to get the UMAC code working on an
Athlon? Can it compete with hash127's speed, under 2 cycles per byte?)
Beware that the UMAC authors habitually quote performance results for
60-bit UMAC without mentioning that 60-bit UMAC is too small for
Internet applications. Their security levels---``light,''
``commercial,'' ``extra,'' and ``extremist''---should be called
``idiotic,'' ``breakable,'' ``shortsighted,'' and ``standard.''
---Dan
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Is there any free encryption scripts in perl and VBScript
Date: 4 Sep 2000 03:23:14 GMT
In article <[EMAIL PROTECTED]>,
<[EMAIL PROTECTED]> wrote:
>Can someone here tell if there are any free scripts with an algorithm
>for encryption (like pgp or something else with private and public
>keys) which has been implemented in both perlscript and VBScript ???
There are several public-key implementations in perl. I've never
heard of "perlscript".
If you want something that runs inside a browser, it's probably not
practical to do public-key decryption in vbscript or javascript, since
the script interpreters are so slow. You could do it with a java
applet and that's been done many times.
Coding symmetric cryptography in javascript or vbscript shouldn't
be too hard. I've done it in javascript though the code's not public.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Blum Blum Shub question
Date: Mon, 04 Sep 2000 03:45:05 GMT
I was recently looking over how the BBS public key system works, And I
think I might have an idea for a different way to use it.
Set up your public and private keys, using all the special
considerations for choosing your two primes.
The person encrypting, chooses some X and some Y, uses X as the key to
some secure block cipher, and sends Z=(X^2^Y mod n) (where n is the
public BBS key), and Y. The steps of BBS decryption should be able to
get X from Y and Z, and so we can get the key to decrypt. Y can be a
fairly small number maybe even a constant (which would mean that it
wouldn't need to be sent), and it would take far fewer steps to get Z
from X than would be needed for using the BBS stream cipher to encrypt
the entire message directly.
What do you folks think, and has anyone thought of this already?
--
... perfection has been reached not when there is nothing left to
add, but when there is nothing left to take away. (from RFC 1925)
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Extending RC4 to 16 bits
Date: Mon, 04 Sep 2000 03:51:15 GMT
Scott Fluhrer wrote:
>
> Guy Macon <[EMAIL PROTECTED]> wrote in message
> news:8oudfm$[EMAIL PROTECTED]...
[snip]
> > Could it be that, in order to insure that you get 100% positive
> > benefit from using a 16 bit version of RC4, you have to make your
> > original passphrase twice as big as well?
> No, the original passphrase can remain the same size. Of course, you
> remain exactly as vulnerable to passphrase search attacks as before,
> but you gain no vulnerabilities to any known attack that tries to
> reconstruct the permutation state (or passphrase) from the keystream.
However, one thing you do need to do, is discard the first 65536*2
values that it outputs, for the same reason you should discard the first
512 values of 8-bit ARC4.
--
... perfection has been reached not when there is nothing left to
add, but when there is nothing left to take away. (from RFC 1925)
------------------------------
From: Greggy <[EMAIL PROTECTED]>
Subject: Re: Patent, Patent is a nightmare, all software patent shuld not be allowed
Date: Mon, 04 Sep 2000 04:12:18 GMT
My guess is that the patent is very specific to the details in the
patent and you can get around it by changing one aspect of the protocol
and then file a patent on your own version. I don't think PKI itself
is the issue, but the way components are passed to and fro. But I
could be wrong. It just appears that way to me.
> Hi All,
>
> I just encountered this patent while surfing the net. How can the
> patent office issue a patent on such fundamental things? Anyone has
> some knowledge of PKI system will come out on this as a solutions. And
> PGP has long history of using public key to encrypted symmetric key
for
> e-mail, document transferred, long before the so call patent. Any one
> has comments on this issue?
>
> =======
> Title: Method and system for dynamic server document encryption
> Assignee & Date: Tumbleeweed Comm. Corp. may/09/2000
>
> Abstract
> A method and system are provided for secure document delivery over a
> wide area network,
> such as the Internet. A sender directs a Delivery Server to retrieve
an
> intended
> recipient's public key. The Delivery Server dynamically queries a
> certificate authority
> and retrieves the public key. The public key is transmitted from the
> Delivery Server to
> the sender. The sender encrypts the document using a secret key and
> then encrypts the
> secret key using the public key. Both encrypted document and encrypted
> secret key are
> uploaded to the Delivery Server, and transmitted to the intended
> recipient. The intended
> recipient then uses the private key associated with the public key to
> decrypt the secret
> key, and uses the secret key to decrypt the document. In an
> alternative, equally preferred
> embodiment of the invention, the sender uses the public key to encrypt
> the document.
> In yet another embodiment, the server transmits the document to the
> Delivery Server for
> encryption.
>
> Claims:
> 1. A method for secure document delivery from a sender over a wide
area
> network, comprising the
> steps of:
> a sender encrypting a document using a secret key;
> the sender contacting a Delivery Server to query a public key
> associated with an intended recipient;
> the Delivery Server dynamically retrieving the public key in real time
> from a certificate authority;
> the Delivery Server transmitting the public key back to the sender;
> the sender encrypting the secret key with the public key; and
> the sender transmitting the encrypted document and the encrypted
secret
> key to the Delivery Server
> for transmission to the recipient.
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
>
--
Theories lead to uncertainty.
Facts lead to certainty.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Greggy <[EMAIL PROTECTED]>
Subject: Re: one-time pad question
Date: Mon, 04 Sep 2000 04:21:07 GMT
> can someone explain to me (or point me to
> some resource) that explains how one can
> crack a one-time pad whose key is not
> perfectly random. i'm not sure i believe
> it can be done (in any but the most obvious
> of patterned data).
I once heard that when the government wants to build a one time pad (on
a CDROM), they measure the vibrations off a specific type of metal (I
cannot remember the type of metal filament) that is heated because the
vibrations are the most unpredictable they have ever found in nature.
Sources of random bit generation, such as keyboard or mouse movement,
are suppose to be inferior - more deterministic.
If you believe that such sources as keyboard and mouse movement are
more deterministic and weaken the random bit generation, then you have
some type of idea to the answer to your question. Otherwise, you are
like me.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Teo Li Xi <[EMAIL PROTECTED]>
Subject: Inquiry
Date: Mon, 04 Sep 2000 13:17:27 +0800
Dear all:
Am trying to implement a few algorithms eg. DES/IDEA/RSA in MS
Visual C++ environment. I realise that there are many egs in the public
domain which are written in C++, but I can't find any in VC++.
Can anyone suggest a place?
Thanks and regards,
jon.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: R: R: R: R: R: Test on pseudorandom number generator.
Date: Mon, 04 Sep 2000 05:27:20 GMT
On Mon, 4 Sep 2000 01:13:54 +0200, in <8oukj5$nsa$[EMAIL PROTECTED]>,
in sci.crypt "Cristiano" <[EMAIL PROTECTED]> wrote:
>> >It seems to be the best for this: I can seed it with 25 32 bits numbers,
>it
>> >pass always the several tests and the p-values of Diehard is far flat
>(many
>> >thanks to Tim Tyler for DiehardC).
>> >
>> >This is what I mean for "far flat":
>> >
>> >Class center p-values found
>> > 0,05 19 ===================
>> > 0,15 19 ===================
>> > 0,25 22 ======================
>> > 0,35 24 ========================
>> > 0,45 24 ========================
>> > 0,55 28 ============================
>> > 0,65 26 ==========================
>> > 0,75 16 ================
>> > 0,85 21 =====================
>> > 0,95 35 ===================================
>> > 1,05 0
>> >
>> >total p-values= 234
>> >Mean= 0,53492095603436
>> >Min= 0,00165856156182101
>> >Max= 0,998935636154854
>> >std. dev.= 0,284750179144904
>> >std. dev./mean= 53,2321973803197%
>> >
>> >KOLMOROGOV-SMIRNOV test of p-values= 0,924584850949655
>> >
>> >The shape of this distribution is good?
>>
>> I would now look at the weak parts again with additional tests.
>> Depending upon application, we might want to investigate the mean by
>> sampling 100 times as many values, to verify that it tightens up
>> toward 0.50.
>
>Done. This is the summary of 50 Diehard tests (100 require too much time:
>about 2 hours);
My reason for suggesting 100 tests was to expect 10 times better
accuracy in the sample results; in particular, the mean p-value count.
Using 100 times the data takes what time it takes. At least in
cryptography we have a better situation than exists in medical
"treatments," where the samples are very small, often cannot be
repeated, and trials take months or years.
>each test examine I generate 2124800 32 bits numbers. The 50
>KS p-value vary from 0,00882 to 0,9904 (mean= 0,559, std. dev.=0,2698).
>
>KS p-value on 11700 (234 p-value x 50 times) p-values = 0,9985 (very bad!)
I really prefer to avoid getting into a situation where we have to pin
all of our conclusions on a single value. We have far more data than
that, and we can analyze it in many ways. Statistics exposes problems
as repeatable biased p distributions, so if we depend upon one result,
when that is too high or low, we have to repeat everything several
times to see if that result repeats. (Actually we should always
repeat tests to evaluate any single result, no matter what p-value it
has.)
>Class center p-values found
> 0,05 1149
> 0,15 1180
> 0,25 1146
> 0,35 1171
> 0,45 1089
> 0,55 1123
> 0,65 1191
> 0,75 1148
> 0,85 1207
> 0,95 1296
> 1,05 0 (here fall only p-values=1)
Here, the .75 and .85 segments, which showed low originally, come
right up. I would have counted the number of times out of the 50
tests that each was below or above the expected value. Too high or
too low 45 times out of 50 or more would have been a real problem;
otherwise, probably not.
However, an overall p-value mean comparable to the original is not
reported. Since we have 50 times as many tests, we can "expect"
something like 7 times the accuracy we had. Since the original mean
was .534, we might have .505 or .495 or something like that. It would
be re-assuring to see the mean start to snap into place with more
tests. This is another case where we could also count the number
times out of 50 tests that the mean is too high or too low.
>If a good generator must give a uniform distribution of p-values, reporting
>these p-values in a graphical form we must see a triangle.
We can report p-values as counts in equal-spaced intervals, as above.
Then we "must" see a flat line, as above. There is no magic in a
cumulative distribution.
>To see how much
>the reals p-values differ from theoretical straight line, I have interpolate
>(with the least square method) the p-values with this line:
>y(x)=0,000715003224985495+8,6552152065671E-5·x
>
>from that I have computed the error given by
> SUM_i[(y(i)-pvalue_i)^2]=0,1414,
>and coeff. determ.= 0,99986.
>
>also, I have computed the same error but compared with the line beginning
>from 0 and ending to 1 so that for i=0, y=0 and for i=11699, y=1; in this
>case the error is 0,8834.
>These two errors seems better than those we get with KS (0,9985). In other
>words the p-values seems to be a good approximation of a triangle.
>My next step will be to compare some generators with this new method. But if
>the KS test will be always bad, I am at one's wit's ends!
The KS test you have may not be performing as you expect; maybe the
test is a problem rather than the results. I have had to battle this
sort of thing repeatedly, which is why I prefer simple, understandable
techniques that I can check by hand. K-S is tougher to check by hand
than chi-square, and if we arrange to have enough values in each bin,
chi-square can have all the accuracy than we need.
If we have random data, we should have a flat distribution of p-values
across multiple tests. Finding the p-value distribution to be
non-flat in repeatedly the same way means something is wrong, but that
something could be the test rather than the data.
>> I assume the K-S result is a p-value,...
>
>Yes; from DiehardC documentation: "After all the tests are performed, you'll
>see a summary of the 160 or p-values [?], and a KSTEST of all of them." (I
>think there is a mistake because the p-values are 234).
So, one approach is to simply take the K-S p-value as "the" result,
and only look at the others when one wishes to understand performance
at a finer level.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
** 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
******************************
