Cryptography-Digest Digest #758, Volume #13 Tue, 27 Feb 01 14:13:00 EST
Contents:
Re: How to find a huge prime(1024 bit?) ("Brendan Shaw")
Re: how long can one Arcfour key be used?? ("Scott Fluhrer")
Re: How to find a huge prime(1024 bit?) (Christian Bau)
Re: On RC4 in C ("Roger Schlafly")
Re: On RC4 in C (Ted Dennison)
Re: How to find a huge prime(1024 bit?) (Christian Bau)
Re: Again on key expansion. (Paul Crowley)
Re: Rijndael S-box inverse (Paul Crowley)
Re: The Key Vanishes: Scientist Outlines Unbreakable Code, Read it and Weep Boys
([EMAIL PROTECTED])
Re: Was there ever a CRM-114 Discriminator? (Mike Rosing)
Re: On RC4 in C (William Hugh Murray)
Re: Again on key expansion. ("Cristiano")
What is the probability that an md5sum of a group of md5sums will be the (jtnews)
----------------------------------------------------------------------------
From: "Brendan Shaw" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,sci.math
Subject: Re: How to find a huge prime(1024 bit?)
Date: Tue, 27 Feb 2001 16:18:38 -0000
"Lynn Killingbeck" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
<snip>
> Not correct, here. This is the proof that there is no largest prime.
> When you compute 1*2*...*N+1, then either: (1) this number is also a
> prime, and larger than N; or (2) there is a prime larger than N that
> divides this number. In either case, there is a prime larger than N,
> completing the proof-by-contradiction. Your statement that this number
> is necessarily prime, is not a correct statement (but, it is a common
> mis-statement!). Try N=4, for example, where 1*2*3*4+1=25 is not prime.
>
As I said in an earlier post, I think the Greeks (Euclid?) multiplied the
first N *prime* numbers together.
And re this by Thomas Boschloo -
> by 4, etc. So in fact, I have proven that in the distribution of prime
> numbers, you can find a gap of ANY length you like. The gap in the
> previous example is e.g. x-1, and maybe even larger. Now what does this
> mean if we still want the number of primes until 'N' to approach
> N/ln(N)? (I can't prove this fact myself, but I have a book that has the
> proof for this I think). Well, if there are large gaps like this (and I
> don't feel like calculating P(1..x)/log(P(1..x)), I guess it is getting
> late again), maybe there are also places where there are a lot of prime
> numbers after one-other. Which the prime generation methode of PGP 263i
> will (statistically) MISS!!
Yes there are abritrarily large runs of composite numbers. But there aren't
such runs of prime numbers. Every
second number is even and thus, er, composite :))
And don't forget, if you do have some billion long sequence of numbers
without a prime, the number of decimal digits
in those numbers is probably in the quadrillions of quadrillions. So when
you step back and look at the amount
of 'space' that doesn't contain a prime, it is still pretty small. I guess
the number of primes, pi(n), is still somewhere
near n/ln(n).
I'm not a mathmetician, as should be fairly obvious ;)
Brendan.
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: how long can one Arcfour key be used??
Date: Tue, 27 Feb 2001 08:28:13 -0800
Julian Morrison <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "Scott Fluhrer" <[EMAIL PROTECTED]> wrote:
>
> >> Also, does anyone know how this varies with key length and
> >> number-of-mixes (N in CipherSaber-2)?
> > Is 'number-of-mixes' the number of passes you do during key setup (with
> > 1 being standard RC4)?
>
> Yes.
>
> > If so, then no, that has no effect.
>
> Ok. How about key length? One of my intended algorithms will use throwaway
> from-scratch DH to setup a key, but creating DH primes for a full length
> 256 byte RC4 key would take several minutes a pop, way too slow. (I'm
> doing it this way so as to have "forward security" - once the transaction
> is over, there should be no way to decrypt it from wiretap records and a
> siezed machine.)
>
> For example, CipherSaber suggests a 62 byte key + IV; for how long could
> that be used?
Again, that has no effect against the best known distinguishing attacks.
--
poncho
------------------------------
From: [EMAIL PROTECTED] (Christian Bau)
Crossposted-To: alt.security.pgp,sci.math
Subject: Re: How to find a huge prime(1024 bit?)
Date: Tue, 27 Feb 2001 16:47:39 +0000
In article <97gk1v$1rm$[EMAIL PROTECTED]>, "Brendan Shaw"
<[EMAIL PROTECTED]> wrote:
> "Lynn Killingbeck" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> <snip>
>
> > Not correct, here. This is the proof that there is no largest prime.
> > When you compute 1*2*...*N+1, then either: (1) this number is also a
> > prime, and larger than N; or (2) there is a prime larger than N that
> > divides this number. In either case, there is a prime larger than N,
> > completing the proof-by-contradiction. Your statement that this number
> > is necessarily prime, is not a correct statement (but, it is a common
> > mis-statement!). Try N=4, for example, where 1*2*3*4+1=25 is not prime.
> >
>
> As I said in an earlier post, I think the Greeks (Euclid?) multiplied the
> first N *prime* numbers together.
You multiply the first N primes and add 1.
The result is not necessarily a prime, but its smallest factor is a prime,
and since the number is clearly not divisible by any of the first N primes
the smallest factor is a prime which is not one of the first N primes.
------------------------------
From: "Roger Schlafly" <[EMAIL PROTECTED]>
Crossposted-To: comp.lang.ada,talk.politics.crypto
Subject: Re: On RC4 in C
Date: Tue, 27 Feb 2001 16:40:51 GMT
"William Hugh Murray" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> > > Arcfour is not illegal, but the name "RC4" is trademarked. To use a
> > > cipher called "RC4" without liscencing that trademark is illegal. To
> > > use the algorithm is perfectly legal.
This is an incorrect statement of trademark law. The law relates to
confusing the consumers about the origin of products. Lots of companies
use the term "RC4" without any licensing, and it is completely legal.
> Arguably. One can also argue that that they have made a lot of money
publishing high quality code
> cheaper than others can replicate it for themselves. When MS, not to
mention Kilgallen, does
> that we call it software publishing. We say they made money publishing,
they made money on what
> they published. We do not say that they made money by not publishing, on
what they chose not to
> publish. One does not describe unpublished MS design documents or source
code as "hidden," much
> less secret, simply because they do not publish them. One has no
obligation to publish something
> in one form or language simply because one chooses to publish it in
another. We do not call
> something published in one language hidden or secret because it is not
published in another.
Actually, a lot of people are unhappy that MS Windows is closed source, and
that MS uses it together with its monopoly power to enforce undocumented
APIs,
bundled products, and system insecurities. Witness the recent Anna K virus,
the explosive growth of Linux, and yesterday's antitrust hearing. Here are
some
sample docs:
Judge Jackson's findings of fact:
http://www.usdoj.gov/atr/cases/f3800/v.pdf
US appeal brief:
http://news.findlaw.com/cnn/docs/microsoft/briefus020901.html
------------------------------
Crossposted-To: comp.lang.ada
From: Ted Dennison<[EMAIL PROTECTED]>
Subject: Re: On RC4 in C
Date: Tue, 27 Feb 2001 16:51:11 GMT
In article <[EMAIL PROTECTED]>, William Hugh Murray says...
>
>publish. One does not describe unpublished MS design documents or source code
>as "hidden," much less secret, simply because they do not publish them. One
Which "One" are we talking about? I often hear it described that way.
---
T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html
home email - mailto:[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Christian Bau)
Crossposted-To: alt.security.pgp,sci.math
Subject: Re: How to find a huge prime(1024 bit?)
Date: Tue, 27 Feb 2001 16:57:36 +0000
In article
<[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Christian Bau) wrote:
> In article <97gk1v$1rm$[EMAIL PROTECTED]>, "Brendan Shaw"
> <[EMAIL PROTECTED]> wrote:
>
> > "Lynn Killingbeck" <[EMAIL PROTECTED]> wrote in message
> > news:[EMAIL PROTECTED]...
> > <snip>
> >
> > > Not correct, here. This is the proof that there is no largest prime.
> > > When you compute 1*2*...*N+1, then either: (1) this number is also a
> > > prime, and larger than N; or (2) there is a prime larger than N that
> > > divides this number. In either case, there is a prime larger than N,
> > > completing the proof-by-contradiction. Your statement that this number
> > > is necessarily prime, is not a correct statement (but, it is a common
> > > mis-statement!). Try N=4, for example, where 1*2*3*4+1=25 is not prime.
> > >
> >
> > As I said in an earlier post, I think the Greeks (Euclid?) multiplied the
> > first N *prime* numbers together.
>
> You multiply the first N primes and add 1.
>
> The result is not necessarily a prime, but its smallest factor is a prime,
> and since the number is clearly not divisible by any of the first N primes
> the smallest factor is a prime which is not one of the first N primes.
Sorry, didn't read the whole post properly. Of course Lynn Killingbeck's
construction also gives a number whose smallest factor (which is a prime)
is greater than N.
------------------------------
Subject: Re: Again on key expansion.
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Tue, 27 Feb 2001 17:02:00 GMT
Benjamin Goldberg <[EMAIL PROTECTED]> writes:
> It is impractical for adding 64 effective bits of strength, sure, but
> that's not what it's designed for. The idea is to give a 40 bit key 56
> effective bits of strength. This can be done, and is practical -- 2^12
> iterations would take .75 seconds on your pc.
Yup. Basically decide how long you can stand to wait before your
passphrase is confirmed correct - a second is probably about right -
and stretch that much. It's not a cure to the generally low entropy
of passphrases, but it's a wise precaution nonetheless, and since it
takes at least a second to type in a passphrase anyway, it's nearly
always worth doing.
Under some circumstances, strong password protocols like SRP can also
be used to secure passphrases against brute force search. But these
should be used in combination with key stretching; they complement
each other.
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
Subject: Re: Rijndael S-box inverse
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Tue, 27 Feb 2001 17:02:00 GMT
> "Panu Hämäläinen" <[EMAIL PROTECTED]>
>
> > In Rijndael specification and some other papers it has been stated that
> Rijdael
> > encryption and decryption can share the S-boxes. Assuming that I have the
> > encryption S-box, how can I use this to produce the inverse S-box?
> >
(I can't find the original article here, so I'm replying to a
followup)
Rijndael sbox:
byte sbox(byte t) {return linearmix[multinv[t]];}
"multinv[i]" is the nonlinear step. It's a self-inverse
transformation based on multiplicative inverses in GF(2^8).
"linearmix[i]" is a linear mixing of the bits. Normally, this is
optimised away, not done as a separate step, but you can do it at
run-time with shifts and XORs. You can invert it the same way.
So, instead of storing tables for S[i] and RS[i] (512 bytes total),
store one table (multinv), and do the linear mixing "by hand". Then
byte multinv[256];
byte linearmix(byte t) {/* a bunch of shifts and XORs */}
byte inv_linearmix(byte t) {/* inverse bunch of shifts and XORs */}
byte sbox(byte t) {return linearmix(multinv[t]);}
byte inv_sbox(byte t) {return multinv[inv_linearmix(t)];}
If you're *really* pushed for space, there's a few *very slow* but
shorter ways to express this sbox in code. However, it's best to use
a table if you can.
hope this helps,
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: The Key Vanishes: Scientist Outlines Unbreakable Code, Read it and Weep
Boys
Date: 27 Feb 2001 09:47:40 -0800
"Mxsmanic" <[EMAIL PROTECTED]> writes:
> <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > You may not need this much data. Fiber optic systems
> > have been demonstrated at close to a terabit per second.
>
> How do you string fiber between you and the satellite?
Obviously any system which can transmit data down a fiber can do
so through empty space.
> Besides, it's not the transmission speed I worry about; it's the
> _generation_ speed. Where do you find all those _completely random_
> bits?
Lots of thermal resistors? This is a situation which begs for
parallelism.
> > It's true that the papers in the literature don't
> > discuss what happens if two people use the same data
> > stream. But it's probably still okay.
>
> It's a cinch to crack a OTP if you have two ciphertexts that use the
> same key.
You're not doing that here.
> > You are mistaken to think that you just index into
> > the data stream and use it for a OTP. Rather, the
> > communicators share a PRNG which indexes randomly
> > into the data stream, and these bits are then xored
> > together to form the OTP. This means that different
> > groups can use the same data stream and have completely
> > different pads.
>
> If their PRNGs are so insecure that they need to XOR with a truly random
> source, why bother with the PRNGs?
Because you can prove that even using relatively insecure PRNGs you
can still get provable security by using them to index into a random
source larger than will fit into the eavesdropper's memory. That's
right, you can prove it. Surprised?
> And if the PRNGs are so secure that
> no truly random source is required, why the need to XOR with the random
> source from the satellite?
A truly random source is required.
> I really don't see them buying anything with
> the satellite. If their PRNG is not secure, and they use bits from the
> satellite, and anyone else overlaps a message with theirs, cryptanalysis
> is easy.
The PRNG is not secure, yet by using it to index into the random bit
stream, you get provable security, even though the bit stream is public.
That's what is proven; read the papers (Maurer 97, Rabin 99).
> There are so many holes in any _practical_ implementation of this scheme
> that I don't see how it can be much more than a thought experiment.
At present, yes, but the stream may be practical in some situations.
After all, ultimately, "All crypto is economics" (Hughes). This
provides a way to lower-bound the cost for an attacker, if you know
how much data storage costs. And unlike computational based bounds,
you only need to know how much data storage costs today, not in the
indefinite future.
> > True, except the secret key does not determine only
> > the starting point, but also how the bits are selected
> > and skipped and xored together to form the OTP.
>
> That has no effect on the security of the algorithm. The secrecy of the
> cryptosystem as a whole depends on the effective key length of the
> secret portion of the system. In this case, the effective key length
> isn't so very great.
Wrong, wrong, wrong! The shared secret can be of modest size, yet you
get far more security than that. This is because the attacker cannot
try out each possible secret key. He doesn't have enough memory. So
this scheme actually amplifies the security beyond the size of the
shared secret! And it does so in a provable fashion. Starting to
sound more revolutionary?
> > He'll just encrypt the bits and charge for the decryption
> > key...
>
> Encryption of a random stream of bits isn't encryption at all.
It's a joke, son.
Alpha
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Was there ever a CRM-114 Discriminator?
Date: Tue, 27 Feb 2001 12:21:19 -0600
Mxsmanic wrote:
>
> In Kubrick's classic film _Dr. Strangelove_, airborne SAC bombers use an
> encryption device called a CRM-114 Discriminator to receive encrypted
> communications from the ground. The device required a three-letter key
> (which doesn't sound very secure). Was there ever such a device
> actually in use?
That movie was made around 1959 I think. Even then a 3 letter code would
have been *way* too small. Kubrik used 3 letters for "precious bodily
fluids" and "poe" ( a reference to the poet maybe?) and wanted an artistic
link between the nut case commander and the planes. Other than a few
real close calls of actual almost launching nukes, there's not much
in that movie that was even close to real.
One of my favorites tho!
Patience, persistence, truth,
Dr. mike
------------------------------
From: William Hugh Murray <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Crossposted-To: comp.lang.ada,talk.politics.crypto
Subject: Re: On RC4 in C
Date: Tue, 27 Feb 2001 18:37:41 GMT
Roger Schlafly wrote:
> "William Hugh Murray" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > > > Arcfour is not illegal, but the name "RC4" is trademarked. To use a
> > > > cipher called "RC4" without liscencing that trademark is illegal. To
> > > > use the algorithm is perfectly legal.
>
> This is an incorrect statement of trademark law. The law relates to
> confusing the consumers about the origin of products. Lots of companies
> use the term "RC4" without any licensing, and it is completely legal.
>
> > Arguably. One can also argue that that they have made a lot of money
> publishing high quality code
> > cheaper than others can replicate it for themselves. When MS, not to
> mention Kilgallen, does
> > that we call it software publishing. We say they made money publishing,
> they made money on what
> > they published. We do not say that they made money by not publishing, on
> what they chose not to
> > publish. One does not describe unpublished MS design documents or source
> code as "hidden," much
> > less secret, simply because they do not publish them. One has no
> obligation to publish something
> > in one form or language simply because one chooses to publish it in
> another. We do not call
> > something published in one language hidden or secret because it is not
> published in another.
>
> Actually, a lot of people are unhappy that MS Windows is closed source, and
> that MS uses it together with its monopoly power to enforce undocumented
> APIs,
> bundled products, and system insecurities. Witness the recent Anna K virus,
> the explosive growth of Linux, and yesterday's antitrust hearing. Here are
> some
> sample docs:
Granted. Similarly, there are those who are unhappy with the business
practices of CA, IBM, and the RIAA, not to mention RSA Security. However, that
is to raise a different point than the one made by Larry and to which I
responded. I was not defending their business practices, in part because they
were not at issue.
I was with IBM when the DoJ was even more unhappy with their business practices
than they are with Microsoft's. There was never a final judgement in IBM's
case but my reading of history suggests that the issues are, for the most
part, moot. DoJ abandoned its requests for relief and IBM never achieved the
kind of dominance which the DoJ seemed to fear. Some have suggested that that
was because, if IBM ever dreamed of such dominance, it took its eye off the
ball while it battled the government. I await the final judgement of the
courts in the Microsoft case, though I might prefer a settlement. However the
battle now joined ends, I hope that MS is not guilty of such an error. However
it ends, I doubt seriously that it will make anybody, much less everybody,
happy with any, much less all, of Microsoft's business practices. (Does that
sentence scan?) On the other hand, I also doubt that, at least in the long run,
it will make any difference.
[I will leave a discussion of the practices of the DoJ for another day and
another forum.]
> Judge Jackson's findings of fact:
> http://www.usdoj.gov/atr/cases/f3800/v.pdf
> US appeal brief:
> http://news.findlaw.com/cnn/docs/microsoft/briefus020901.html
------------------------------
From: "Cristiano" <[EMAIL PROTECTED]>
Subject: Re: Again on key expansion.
Date: Tue, 27 Feb 2001 19:50:13 +0100
> [...]
> In point of fact, I suspect that there IS no practical way to add 64 bits
of strength to cryptokey.
This sound a little strange in the world of cryptography, where averything
is possible :-)
I have thought about to use the elliptic curve (as posted in other message),
but I have not received any comment...
Now, I have slightly modified the algorithm:
- I convert the low-entropy password in a number: t;
t=t^-1 mod Ord(Base point);
- for 16 times I do the following:
Q=t*Base point;
t=Qx||Qy (concatenate x and y coordinates of Q)
t=SHA512(t).
This take about 1 second in my pc. Any comment?
> I would suggest that you just use a longer key. There *are* easy ways to
make long, easily memorizable, secure, keys.
I would be you really thankful if you tell me some method.
Thanks
Cristiano
------------------------------
From: jtnews <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: What is the probability that an md5sum of a group of md5sums will be the
Date: Tue, 27 Feb 2001 19:04:39 GMT
Given:
Files: 1 to N
A program takes files 1 to N and generates
an array of N md5sums S[1..N].
An md5sum is then generated on array S.
What is the probability that the md5sum
generated on array S will be the same
if only one of the files 1 to N
is changed?
Does anyone have a clue on how to proceed
with such a calculation?
I've made up a security-audit script which
does the above and I want to calculate
the probability of an undetected compromise.
References:
http://www.ietf.org/rfc/rfc1321.txt?number=1321
RedHat 7.0 md5sum Manual Page
man md5sum
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
