Cryptography-Digest Digest #760, Volume #13 Tue, 27 Feb 01 22:13:00 EST
Contents:
Re: Rnadom Numbers (Benjamin Goldberg)
A few questions ("Koen Van Baelen")
Re: What is the probability that an md5sum of a group of md5sums will be the same?
("Peter Webb")
Re: OverWrite freeware completely removes unwanted files from harddrive (Benjamin
Goldberg)
Re: how long can one Arcfour key be used?? ("Julian Morrison")
Re: ideas of D.Chaum about digital cash and whether tax offices are delighted ?
("Ryan M. McConahy")
Re: ideas of D.Chaum about digital cash and whether tax offices are delighted ?
("Ryan M. McConahy")
Re: Was there ever a CRM-114 Discriminator? (John Savard)
Re: In RSA, how d is calculated? ("Ryan M. McConahy")
Re: Was there ever a CRM-114 Discriminator? (John Savard)
Re: Again on key expansion. (Benjamin Goldberg)
Re: how long can one Arcfour key be used?? (Benjamin Goldberg)
Re: Hash strength question (Benjamin Goldberg)
Re: A few questions ("bubba")
Re: A few questions ("bubba")
Re: encryption and information theory (John Savard)
Re: What is the probability that an md5sum of a group of md5sums will be the
(Benjamin Goldberg)
Re: A few questions (Benjamin Goldberg)
Re: How to find a huge prime(1024 bit?) ("Dik T. Winter")
----------------------------------------------------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Rnadom Numbers
Date: Wed, 28 Feb 2001 00:15:07 GMT
Simon Johnson wrote:
>
> Benjamin Goldberg <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > Douglas A. Gwyn wrote:
> > >
> > > Simon Johnson wrote:
> > > > yeah, good point. I assume that this question cannot be answered
> > > > then until the problem surrounding p=np is solved, right?
> > >
> > > P?=NP has absolutely nothing to do with whether a PRNG output can
> > > be successfully cryptanalyzed.
>
> This is stating the question again i think.... but: "is it possible to
> show that no attack can ever exists for an algorithm without P?=NP?
> below a certain complexity?"
>
> I simply assumed (probably incorrectly) that without this proof we
> couldn't say with total certainty that some algorithm had no solution
> faster than brute-force.
If we prove that P=NP, then we know that many algorithms may be solved
significantly faster than brute force, simply by converting them to
3SAT. However, proving that P!=NP does NOT prove that brute force is
the fastest solution. Remember that NPC problems are only exponential
time in worst case; for some data sets, solving may take polynomial
time.
AFAIKS, linear analysis is exactly identical to converting a cipher to a
SAT problem. SAT problems can be converted in polynomial time to 3SAT
problems. 3SAT problems are NPC. Let's do some computations, shall we?
Let N be the number of bits in the key.
I know for a fact that converting a cipher and a bunch of plaintext/
ciphertext pairs to a 3SAT problem produces it into a polynomial number
of 3SAT terms wrt (key bits + known plaintexts). So there are O(N^a)
terms.
Assume we have a P time NPC solver, which takes O(N^b) time, where N is
the size of the NPC problem.
For a cipher with an N bit key, solving take O(N^ab).
Try N=256, or 2^8. Now suppose ab >= 32. Thus, worst case time is no
faster than brute force.
Gee. Looks like a proof that P=NP won't automatically give us a way of
breaking ciphers faster than brute force -- it will only do so if the
solution has a LOW exponent.
What does P!=NP give us that we couldn't have if P=NP?
PS, consider: FEAL4, as a linear analysis problem, is easy. Does this
fact mean that NP problems are easy? No, only that the FEAL4 SAT
problem is an easy dataset -- EVEN IF P!=NP!!! Thus, even if P!=NP,
broken ciphers stay broken.
--
A solution in hand is worth two in the book.
------------------------------
From: "Koen Van Baelen" <[EMAIL PROTECTED]>
Subject: A few questions
Date: Wed, 28 Feb 2001 00:33:34 GMT
Hi everybody,
I've got two questions :
1 :
How can I generate real random numbers? And i don't mean the numbers
generated by the 'random' functions you find in all programming languages. I
want something that produces totally unpredictable numbers. I know there's
some mathematical theory for producing random numbers, so if anybody knows
about it, pleasy let me know!
2 :
Does anybody have an electronic version of "Applied cryptography"? I can't
find it in any bookstore and it way to expensive at amazon.com.
------------------------------
Reply-To: "Peter Webb" <[EMAIL PROTECTED]>
From: "Peter Webb" <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: What is the probability that an md5sum of a group of md5sums will be the
same?
Date: Wed, 28 Feb 2001 00:34:19 GMT
The following is extracted from the URL you provided:
The MD5 message-digest algorithm is simple to implement, and provides
a "fingerprint" or message digest of a message of arbitrary length.
It is conjectured that the difficulty of coming up with two messages
having the same message digest is on the order of 2^64 operations,
and that the difficulty of coming up with any message having a given
message digest is on the order of 2^128 operations.
In other words, the chance that a new file has the same md5sum as an
existing file is one in 2^128 or about one in 10 to the 38th power. Aint
going to happen.
"jtnews" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> 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
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Crossposted-To: alt.hacker
Subject: Re: OverWrite freeware completely removes unwanted files from harddrive
Date: Wed, 28 Feb 2001 00:35:39 GMT
Anthony Stephen Szopa wrote:
>
> "Trevor L. Jackson, III" wrote:
[snip]
> > the OS might never write to the disk at all.
>
> I told you what the coded instructions are.
>
> You and others suggest that just maybe these coded instructions are
> somehow not being carried out.
>
> You are suggesting that maybe sometimes they are and sometimes they
> are not.
>
> Urban Legend or FUD.
You say that the "coded instructions" are carried out 100% of the time.
But the problem is that you clearly have NO CLUE as to what those
instructions actually are. An instruction to "write" is actually an
instruction to schedule a write operation. I will agree with you that
100% of the time, the write operation is indeed scheduled.
However, if two writes requests in a row are made for the same disk
address, and the second occurs before the first scheduled write is
carried out, the disk scheduler will CANCEL THE EARLIER SCHEDULED WRITE.
This is what happens. 100% of the time.
> This is no trivial matter.
No, it's not a trivial matter. Noone said it was.
The coded instructions are never "ignored", but later requests cause
eariler requests to be discarded.
Here's a little analogy: Think about the cpu as a king, the device
driver as his steward, the cpu as his mounted messengers, and the device
as his lords. Suppose that the king tells his steward, "Tell Sir Foobaz
that his taxes for this month are 80 gold," and then, less than a day
later, before the messenger sets out on his horse, the king tells his
steward, "Tell Sir Foobaz that his taxes for this month are 90 gold."
What do you think will happen? Does the steward stupidly send out two
messengers? Or does he only send one messenger, saying that taxes are
90 gold? The steward didn't *ignore* the earlier order, he did indeed
hear it when he was told, and wrote it down on the list of things to
tell the messengers to do.. but he crossed it out it when the later
order arrived.
Get it?
--
A solution in hand is worth two in the book.
------------------------------
From: "Julian Morrison" <[EMAIL PROTECTED]>
Subject: Re: how long can one Arcfour key be used??
Date: Wed, 28 Feb 2001 00:35:56 +0000
"Scott Fluhrer" <[EMAIL PROTECTED]> wrote:
>> 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.
Does key length affect its security at all? (Same question for
number-of-mixes?)
------------------------------
From: "Ryan M. McConahy" <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt,talk.politics.crypto,alt.cypherpunks
Subject: Re: ideas of D.Chaum about digital cash and whether tax offices are
delighted ?
Date: Tue, 27 Feb 2001 19:38:12 -0500
>The best way I know of to stop drive-by shooters and mall
>terrorists is to kill them on the spot. Which means that
>enough of the general public has to be armed to make that
>a significant risk for potential assailants. Indeed, it is
>well established that civilian access to firearms and the
>incidence of violent crime are inversely related. England
>and Australia recently performed the experiment (adjusting
>ease of arming in the wrong direction), confirming once
>again this relationship.
Smart thinking! Yes! Pass a law saying that anyone who kills a drive-by
shooter gets $$$!!
------------------------------
From: "Ryan M. McConahy" <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt,talk.politics.crypto,alt.cypherpunks
Subject: Re: ideas of D.Chaum about digital cash and whether tax offices are
delighted ?
Date: Tue, 27 Feb 2001 19:38:12 -0500
>The best way I know of to stop drive-by shooters and mall
>terrorists is to kill them on the spot. Which means that
>enough of the general public has to be armed to make that
>a significant risk for potential assailants. Indeed, it is
>well established that civilian access to firearms and the
>incidence of violent crime are inversely related. England
>and Australia recently performed the experiment (adjusting
>ease of arming in the wrong direction), confirming once
>again this relationship.
Smart thinking! Yes! Pass a law saying that anyone who kills a drive-by
shooter gets $$$!!
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Was there ever a CRM-114 Discriminator?
Date: Tue, 27 Feb 2001 20:33:23 GMT
On Tue, 27 Feb 2001 14:26:07 -0600, Ed Kubaitis <[EMAIL PROTECTED]> wrote,
in part:
>On another front, just came across this information just suggesting
>that CRM-114 was a continuing motif in Kubrick movies:
> http://www.eeggs.com/items/1589.html
Like THX-1138 with George Lucas...
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "Ryan M. McConahy" <[EMAIL PROTECTED]>
Subject: Re: In RSA, how d is calculated?
Date: Tue, 27 Feb 2001 19:54:43 -0500
Where is the website for the RSA demonstration that you got that from?
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Was there ever a CRM-114 Discriminator?
Date: Tue, 27 Feb 2001 20:36:23 GMT
On Tue, 27 Feb 2001 20:33:23 GMT, [EMAIL PROTECTED]
(John Savard) wrote, in part:
>On Tue, 27 Feb 2001 14:26:07 -0600, Ed Kubaitis <[EMAIL PROTECTED]> wrote,
>in part:
>>On another front, just came across this information just suggesting
>>that CRM-114 was a continuing motif in Kubrick movies:
>> http://www.eeggs.com/items/1589.html
>Like THX-1138 with George Lucas...
In addition to the license plate on a car in the movie American
Graffiti, could it have been the actual number on the license plate of
a car *owned* by George Lucas? And could CRM-114 have similarly
appeared on the license plate of a car owned by Stanley Kubrick?
In fact, I have a suspicion that I may have decoded why these men
might have each found their first cars to be such an intensely
emotional experience...
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Again on key expansion.
Date: Wed, 28 Feb 2001 01:10:54 GMT
Cristiano wrote:
>
> > [...]
> > 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?
You are adding (4 + log2(512)), or 13 effective bits of entropy.
> > 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.
Sure, it's called diceware. Each word of a diceware passphrase has ~12
bits. For a passphrase with 64 bits of entropy, use a 5 word
passphrase.
--
A solution in hand is worth two in the book.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: how long can one Arcfour key be used??
Date: Wed, 28 Feb 2001 01:17:24 GMT
Julian Morrison wrote:
>
> "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.)
There seems to be no reason to generate primes on the fly... you should
be able to hardcode one prime into your program. However, you do need
to pick an exponent, and do modular exponentiation on the fly.
> For example, CipherSaber suggests a 62 byte key + IV; for how long
> could that be used?
The reason they suggest that length key is that they expect the key to
be in ASCII, and thus low entropy per byte. Thus, if there are just
over two bits of entropy per byte, you've got a key of 128 bits of
strength. However, the length of the key does not in any way protect
against distinguishing attacks, only from attacks against the key.
--
A solution in hand is worth two in the book.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Hash strength question
Date: Wed, 28 Feb 2001 01:31:22 GMT
Thanks! And while you're clearly right about the XOR method being
trivially insecure, since
H("acegik") XOR H("bdfhjl") == H("bdfhjl") XOR H("acegik").
What about if each hash chip is seeded with it's index:
H(1||"acegik") XOR H(2||"bdfhjl")
I think it is very unlikely that:
H(1||"acegik") XOR H(2||"bdfhjl") == H(1||"bdfhjl") XOR H(2||"acegik")
--
A solution in hand is worth two in the book.
------------------------------
From: "bubba" <[EMAIL PROTECTED]>
Subject: Re: A few questions
Date: Wed, 28 Feb 2001 01:42:17 GMT
A web search service might help with the online book, is this it?
http://www.cacr.math.uwaterloo.ca/hac/
"Koen Van Baelen" <[EMAIL PROTECTED]> wrote in message
news:yHXm6.33453$[EMAIL PROTECTED]...
> Hi everybody,
> I've got two questions :
>
> 1 :
> How can I generate real random numbers? And i don't mean the numbers
> generated by the 'random' functions you find in all programming languages.
I
> want something that produces totally unpredictable numbers. I know there's
> some mathematical theory for producing random numbers, so if anybody knows
> about it, pleasy let me know!
>
> 2 :
> Does anybody have an electronic version of "Applied cryptography"? I can't
> find it in any bookstore and it way to expensive at amazon.com.
>
>
------------------------------
From: "bubba" <[EMAIL PROTECTED]>
Subject: Re: A few questions
Date: Wed, 28 Feb 2001 01:46:15 GMT
Oops, my finger slipped before I finished. There are lots of ways
to generate random numbers. Dice and coins are a proven method.
"Koen Van Baelen" <[EMAIL PROTECTED]> wrote in message
news:yHXm6.33453$[EMAIL PROTECTED]...
> Hi everybody,
> I've got two questions :
>
> 1 :
> How can I generate real random numbers? And i don't mean the numbers
> generated by the 'random' functions you find in all programming languages.
I
> want something that produces totally unpredictable numbers. I know there's
> some mathematical theory for producing random numbers, so if anybody knows
> about it, pleasy let me know!
>
> 2 :
> Does anybody have an electronic version of "Applied cryptography"? I can't
> find it in any bookstore and it way to expensive at amazon.com.
>
>
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: encryption and information theory
Date: Wed, 28 Feb 2001 01:45:59 GMT
On Tue, 27 Feb 2001 10:30:33 +0000, Andreas Moser
<see@http://www.ztop.freeserve.co.uk> wrote, in part:
>Does the encryption change the entropy, i.e. does the
>encrypted message still reflect the information content of
>the original message? Say the original message had an
>entropy of 1 kbit, then use, say, PGP encryption, does it
>increase?
>If the answer is yes, where does the additional information
>come from, and if the answer is no, isn't there a way to see
>through the encryption?
It has been answered that conventional encryption increases the
entropy of a message by the amount of the key.
That is true only if the message is not compressed.
More precisely: if the message contains N bits of information, and
occupies M bits of bandwidth, and the K is K bits long, the entropy of
the encrypted message is N+K bits, *or* M bits, whichever is less.
In the case of RSA encryption, given that you know the public key, no
increase of entropy takes place.
Does that imply there is a way to see through the encryption?
In the case of RSA encryption, yes.
In the case of conventional encryption, where N+K is less than M, yes.
But that way is brute-force search; that it is possible just means
that you don't have a one-time-pad. Brute force search with a big
enough key is simply not possible, so the fact that there is 'a way to
see through the encryption' due to information-theoretic
considerations is not really a problem.
You have a problem if there is a much faster way to break the code,
because it is weak for some reason, but this has nothing to do with
the entropy.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: What is the probability that an md5sum of a group of md5sums will be the
Date: Wed, 28 Feb 2001 02:47:30 GMT
This seems identical to my recently posted hash strength question (the
one at the start of the thread).
Unless MD5 is broken, then if one of the N files is changed, [at
random], then MD5 of the file should change with probability
(1-1/2^128).
If one of the elements of array S is changed, then MD5(S) should change
with probability (1-1/2^128).
So the odds of MD5(S) changing when one of the files changes is:
(1-1/2^128)^2, which is slightly smaller than (1-1/2^128), but not by a
detectable amount.
--
A solution in hand is worth two in the book.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: A few questions
Date: Wed, 28 Feb 2001 03:00:08 GMT
Koen Van Baelen wrote:
>
> Hi everybody,
> I've got two questions :
>
> 1 :
> How can I generate real random numbers? And i don't mean the numbers
> generated by the 'random' functions you find in all programming
> languages. I want something that produces totally unpredictable
> numbers. I know there's some mathematical theory for producing random
> numbers, so if anybody knows about it, pleasy let me know!
As John von Neumann said, "Anyone who considers arithmetic methods of
producing random digits is, of course, in a state of sin."
What you can do, however, is find some things on your computer which
produce real randomness, and use some method of mixing them up in a
secure way. I would suggest something like the "Yarrow" RNG to do this.
Alternatively, you can buy a hardware random number generator.
> 2 :
> Does anybody have an electronic version of "Applied cryptography"? I
> can't find it in any bookstore and it way to expensive at amazon.com.
AC is not itself online. HAC, however is. If you want Applied
Cryptography, and aren't willing to spend for it, go to your local
library, and make an interlibrary loan request. If you Handbook of
Applied Cryptography, go to http://www.cacr.math.uwaterloo.ca/hac/ where
the author has made it available -- for free!
--
A solution in hand is worth two in the book.
------------------------------
From: "Dik T. Winter" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,sci.math
Subject: Re: How to find a huge prime(1024 bit?)
Date: Wed, 28 Feb 2001 02:51:53 GMT
In article <[EMAIL PROTECTED]> [EMAIL PROTECTED] writes:
> Thomas Boschloo wrote:
> > Take the proof for infinite primes by the greek. They use a number 'N'
> > that is composed by multiplying all the primes up to the largest prime
> > and adding 1. This new number can't be divided by any of the primes you
> > used to generate 'N' because e.g. the next increment of 'N' can be
> > divided by two, the next one by three, etc. They all just mis out, so
> > the new number 'N' must be a prime also! (Not only that, but it is
> > larger than the largest prime we assumed, thus falsifying the argument
> > that there is a largest prime).
>
> Not correct, here.
Well, I say it is correct. The premissa is: "there is a finite number
of primes". Multiplying them all together and adding 1 shows that the
resultant number is not divisible by any prime. Hence by the definition
of prime it must be prime, contradicting the premissa.
But let's analize it more completely:
Def: a prime is an integer number > 1 that is not divisible by any smaller
number, except 1.
Theorem: a non-prime > 1 is divisible by a prime.
Proof: it is divisible by a smaller number which is either prime or non-
prime, so by infinite descent the result holds.
Theorem: there is an infinitude of primes.
Proof:
Suppose there is only a finite number of primes. Multiply them all
together and add 1. Suppose the result is non-prime, but according
to the theorem above it should be divisible by a prime, but none of
the primes fit, so it is prime. A contradiction, we have found a
new prime.
The confusion is that the new number is indeed not necessarily prime, but
when the premissa is "a finite number of primes" we just showed that the
number *is prime*, contradicting the premissa, and so the premissa is
false, but also its conclusion, that the number is prime.
>From a false premissa it is fairly easy to get false conclusions. It is
only needed to show that a conclusion contradicts the premissa to show
that the premissa is false, and so the conclusion is not necessarily true.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
------------------------------
** 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
******************************
