Cryptography-Digest Digest #267, Volume #9 Tue, 23 Mar 99 01:13:04 EST
Contents:
Re: Newbie, what a stupid term... ([EMAIL PROTECTED])
Re: Analysing ([EMAIL PROTECTED])
Re: Common Modulus Attack (Scott Fluhrer)
Basic OTP questions ("Tim Mavers")
Re: Random Walk ("karl malbrain")
Re: Common Modulus Attack ([EMAIL PROTECTED])
Re: Random Walk ("Trevor Jackson, III")
Re: Random Walk ("Trevor Jackson, III")
Re: Newbie, what a stupid term... ("Trevor Jackson, III")
Re: Random Walk ("Trevor Jackson, III")
unicity, redundancy, and crypto help ([EMAIL PROTECTED])
unicity, redundancy and help ([EMAIL PROTECTED])
Re: Basic OTP questions (Pat Ekman)
Re: Common Modulus Attack ("_DEFAULT")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Newbie, what a stupid term...
Date: Mon, 22 Mar 1999 23:02:29 GMT
leadacid wrote:
> So if the salt value is saved, what's the point in computing it in the
> first place?
It's used to prevent an attacker from searching for multiple
password at once. If I'm password-cracking, I have to attack
one password at a time, because they all use a different salt.
If there were no salt, I could hash each candidate password
and check it against many users passwords at once, or
pre-compute a dictionary of common passwords and their
digests.
--Bryan
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Analysing
Date: Mon, 22 Mar 1999 23:40:17 GMT
Werner Lang wrote:
> is there a group, who
> test cryptographic algorithm for free.
There are people who sometimes do so, but those few are
vastly outnumbered by people who design cryptographic
algorithms, for free or otherwise.
What's more, the way the game is played it's unlikely that
anyone will, for free, say that a new cipher is strong.
If Paul attacks Dave's algorithm for free, he can report
the attack if successful, and never has to admit he tried
if unsuccessful. On the other hand, if Dave pays Paul to
attack the cipher he'll surely want the work done under
an agreement that lets Dave cite the attempt if Paul
doesn't find any significant weakness, but keeps Paul
under non-disclosure in case the system falls.
--Bryan
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: Scott Fluhrer <[EMAIL PROTECTED]>
Subject: Re: Common Modulus Attack
Date: Tue, 23 Mar 1999 00:29:11 GMT
In article <7d4m8h$af4e$[EMAIL PROTECTED]>,
"_DEFAULT" <[EMAIL PROTECTED]> wrote:
>Thanks for reading this post!
>
>I was reading Bruce's book where he talked about Common Modulus Attack on
>RSA:
>c1 = m ** e1 mod n
>c2 = m ** e2 mod n
>e1 and e2 are relatively prime, the cryptanalyst knows n, e1, e2, c1, and
>c2.
>The extended Euclidean algorithm can find r and s:
>r * e1 + s *e2 = 1
>assume r is negative, extended Euclidean algorithm can be used to find c1
>** -1, then
>[(c1 ** -1) ** -r] * [c2 ** s] = m mod n
>
>My question is: does c1 ** -1 always exist?
Not always, but it really doesn't matter. For one, for realistic n's,
c1 ** -1 will almost always exist. In addition, if c1 ** -1 does not
exist, that means that either:
c1 == 0 mod n, in which case you know m == 0 mod n,
or
c1 is nonzero, and is not relatively prime to n. In this case,
gcd( c1, n ) is a nontrivial factor of n, and given a factorization
of n, you can find the private keys directly.
> If the cryptanalyst knows c1,
>why does he need to use extended Euclidean algorithm to find c1 ** -1 ? I
>tried to use the following number but I can't recover the message m:
>m = 13, e1 = 2, e2 = 3, n = 5
One of the requirements of RSA is the the encryption (and decryption)
exponents be relatively prime to phi(n), which is 4 in this case. Since
2 is not relatively prime to 4, the first encryption is cannot be
unambiguous decoded, after all:
13 ** 2 mod 5 == 4 == 12 ** 2 mod 5, even though 13 != 12 mod 5
(and, uses of RSA usually require 0 <= m < n, because RSA encryption and
decryption only preserves m modulo n).
Try it again with better parameters, such as:
m = 2, e1 = 3, e2 = 5, n = 15
--
poncho
------------------------------
From: "Tim Mavers" <[EMAIL PROTECTED]>
Subject: Basic OTP questions
Date: 22 Mar 1999 18:17:01 -0600
I just started reading Applied Cryptography and had some basic questions
regarding OTPs. In the book, he says that in theory a OTP is the perfect
encryption because as long as you have random numbers in your keys, it would
be impossible to determine the message because the ciphertext could be
deciphered to any phrase. Not knowing the phrase would make it impossible
to tell if you had the right key.
Now isn't this the case with most encryption algorithms? You really have to
know what your looking for in order to find it, right?
On that note, how does one know if you have the right message? I was
always curious to know this after reading about Deep Crack and the other
various brute-force attacks against DES. With the kinds of possible
combinations they go through, how the heck do they know when they have found
the right message? I am sure at some point, certain phrases may come up
that appear to be legimate, where in all actuality, they are just anomolies
generated by coincidence.
------------------------------
From: "karl malbrain" <[EMAIL PROTECTED]>
Subject: Re: Random Walk
Date: Mon, 22 Mar 1999 17:37:59 -0800
R. Knauer <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>(...)
> Unfortunately the criterion of "unpredictability" is too vague to be
> of any analytical value other than a qualitative guide to the motive
> behind crypto. The reason is that obscurity can also pass for
> unpredictability, and we know that is not a good way to build
> cryptosystems. Unpredictability is an intuitive notion, and therefore
> cannot serve as a formal specification. It is very valuable in guiding
> you to the formal specification, since whatever it is that makes
> numbers crypto-grade random also makes them unpredictable.
MeThinks you've gone quite over the edge on this one -- the very NATURE of
the OTP is one of OBSCURING the plaintext under <<white>> noise XOR with the
KEYSTREAM (or other LINEAR function).
> The best specification for a crypto-grade random number generator that
> I am aware of is that it is capable of generating all possible finite
> sequences equiprobably, namely in an independent and equidistributed
> manner. With that specification for crypto-grade randomness, the
> cryptanalyst can have no reasonable certainty that the plaintext he
> has decrypted is the intended message, because it is just one possible
> plaintext out of a sample space of 2^N equiprobable plaintexts of
> length N.
Again, for sequences of question (e.g. all TEXT encoded under a
<<time-framed>> key stream, a statistical test over EQUIDISTRIBUTED
group-wise ciphertext (to 24 bits is good enough for 1KK total text) would
make any INDEPENDENT criteria fall-out.
In other words, YOU'RE STILL NOT WORKING UNDER PRIORITIZATION!
Karl M
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Common Modulus Attack
Date: 23 Mar 99 02:57:27 GMT
[EMAIL PROTECTED] wrote:
> Now ... assume we only know the public keys (e1,n) (for Ralph, say) and
> (e2,n) (for Betty, say) and the n's are the same and see the original
> message "m" (somehow we know that this is the same message -- say, Jane
> sends the same message to Ralph and Betty who have the same modulus in
> their public keys) sent to Ralph and Betty, so we see c1 and c2. We know
> e1, e2, n and c1, c2. We DON'T know either d1 or d2 (the private keys for
> Ralph or Betty).
With e1 and e2 relatively prime (so there exist r and s with r*e1+s*e2=1).
> Just knowing e1 and e2 (NOT KNOWING d1 OR d2!) we can find r,s.
------------------------------
Date: Mon, 22 Mar 1999 22:07:48 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Random Walk
Douglas A. Gwyn wrote:
>
> "Trevor Jackson, III" wrote:
> > Could you please amplify your description of this or provide a
> > reference? It sounds extremely interesting.
>
> I may write it up later, if I get my web site off the ground,
> but there is a quick summary in a man page in my I-hat package
> that you can find in various crypto archives around the net.
> The classic book is "Information Theory and Statistics" by
> Solomon Kullback, 416 pp. Dover paperback reprint July 1997,
> ISBN 0486696847. That basically develops the theoretical
> foundation, and if you're not familiar with conjugate
> distributions, exponential families, etc. you might prefer
> "The Information in Contingency Tables" by D.V. Gokhale and
> Solomon Kullback, 365 pp. Marcel Dekker 1978, ASIN 082477261X.
Don't bother. The above references are just what I need. Thank-you.
[snip]
> > In fact (to paraphrase your leading sentence above) statistical
> > tests evaluate *order*.
>
> I prefer to say that such a test is a test of how well a specific
> simple model fits the observed data (or vice versa). "Lack of
> discernable order" is not a testable model, which explains why
> actual tests are for the alternate hypothesis "a specific form
> of detectable order". We can relate the results to confidence
> levels a la Fisher, but that isn't necessary from the likelihood-
> ratio point of view (which is nicely compatible with information
> statistics, as it happens).
As long as we agree that any deterministic model is an instance of
ordering our conclusions will be congruent. Of course you need a
specific ordering (model) to test for because there is no generalzed
definition of "order". Yet. Information theory is still coming out of
its alchemical phase I suspect.
------------------------------
Date: Mon, 22 Mar 1999 21:53:43 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Random Walk
R. Knauer wrote:
>
> On Sun, 21 Mar 1999 20:21:44 -0500, "Trevor Jackson, III"
> <[EMAIL PROTECTED]> wrote:
>
> >Crap. I defy you to find a single expert who believes statistical
> >testing is "worthless" in the evaluation of random number generators.
>
> >Cite someone; ANYONE, other than your own posts.
>
> Where the Hell have you been? I have quoted several mainstream sources
> repeatedly. Yet you ignore them, even when I give explicit citations
> to exact pages in their works.
>
> Don't give me this bullcrap that I am making this up - I know better
> than to do that. I have based all my comments, without a single
> exception, on published comments of acknowledged experts.
Wrong. None of the experts you have quoted have said that statistical
tests are worthless. many of them, as well as many people here, have
said that statistical tests cannot be used to test for randomness. Both
the experts you quote and the experts and scholars here hold that
statistical tests find patterns; order; the opposite of randomness.
>
> Just look at the archives.
>
> Bob Knauer
>
> "If you think health care is expensive now, wait until it's FREE!"
------------------------------
Date: Mon, 22 Mar 1999 22:21:57 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Newbie, what a stupid term...
Tim Mavers wrote:
>
> Shawn Willden wrote in message <[EMAIL PROTECTED]>...
> >More usefully, an attacker could take a dictionary, hash every word in it
> and
> >then just match the resulting hashes against the contents of a system's
> >password file. He's almost guaranteed to get a few hits.
>
> >The salts makes all of this significantly harder by ensuring that there are
> a
> >large number of different encryptions of a given password. If users then
> >choose reasonably good passwords, the attacker will find it very difficult
> to
> >guess passwords.
>
> But I though the salt value (in it's native form) is also stored along with
> the password (at least in the examples previously given in this thread).
> Doesn't that negate any "randomness", e.g.:
>
> My password is stored in ciphertext
> The salt value is also stored
>
> A hacker could then run a dictionary hash using the salt value above. I
> must be missing something.
What you are missing is an appreciation for a dictionary attack. It
does not take place against individual passwords, but against an entire
file of passwords. Without the salt the attacker can hash a dictionary
of 10^6 words once and compare the hashes agains those in the password
file. There are likely to be some hits.
With the salts, unique to each entry in the file, the attacker has to
rehash the dictionary with the salt of each indivudal password in order
to check for a match on that password. This reduces the unsalted
dictionary attack to a sequence of attacks on individual passwords,
where each password attack is about as hard as the unsalted attack on
the entire file
------------------------------
Date: Mon, 22 Mar 1999 21:50:35 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Random Walk
R. Knauer wrote:
>
> On Mon, 22 Mar 1999 07:19:29 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
> wrote:
>
> >> Oh, come on - read Feller, fer chrissakes. It's all there.
>
> >I did read Feller, certainly before you did, probably before you
> >were born.
>
> Hey, dude - don't pull rank on me. I was already grown up before you
> were no more than a lascivious look in your father's eye.
>
> >It was a classic work, widely used as a general
> >reference for basic applications of probability theory in Agency
> >articles decades ago.
>
> Which edition did you read? You are aware that Feller made significant
> revisions in the 3rd edition. It is the 3rd edition that I am
> referring to.
>
> >And I take exception to your distortion of the legitimate point he was making.
>
> You can huff and puff all you want, but that will do no good.
>
> Give us reasons to believe your contention. And while you are at it,
> give me reasons that my contention is incorrect. Here - I will present
> it one more time:
>
> If statistical tests could be used to characterize a process as
> random, they could be used to generate random numbers from that very
> process it has characterized as random.
You make this same nonsensical jump so often and so consitently that it
cannot be accident. You must be doing in on purpose.
As far as I can tell noone here has ever suggested that statistical
tests can be used to characterize a process as random except you.
*Many* people have suggested that statistical tests can be used to
characterize a process as NON-random.
If you want to beat up something, at least fill the dummy with straw
before you strike.
>
> For example, all that would be needed to generate random numbers
> algorithmically would be to pass the output of a pseudo-random number
> generator thru the statistical tests and accept that output which
> passes those tests and reject that output that fails those tests.
>
> Statistical tests by their very nature a algorithms. They are only
> tests for pseudo-randomness - that is, they only test for the
> *appearance* of randomness based on some pre-conceived notion of what
> constitutes randomness - such as the lack of 1-bit bias or whatever
> other algorithmic criterion one can concoct.
>
> I realize that appeals to authority are weak, but I did adapt that
> argument above from the comments made by Kolmogorov as quoted and
> expounded upon in Li & Vitanyi's book on Kolmogorov Complexity. I also
> tapped heavily on the considerations of modern physicists, and quoted
> several comments from Williams & Clearwater's book on quantum
> computing. Now I am adding Feller's comments as new arrows to my
> quiver.
>
> Now stop all that blustering and pontification and tell us in
> unequivocal terms what is wrong with maintianing the position that I
> hold. But plan on jumping up high if you do, because I am standing on
> the shoulders of giants.
>
> Bob Knauer
>
> "If you think health care is expensive now, wait until it's FREE!"
------------------------------
From: [EMAIL PROTECTED]
Subject: unicity, redundancy, and crypto help
Date: Tue, 23 Mar 1999 04:05:16 GMT
Does anyone know of papers or articles (on the web or in journals) that
address unicity and key redundancy with RSA, Eliptic Curve, ElGamal or DES?
Or for that matter ways of analyzing unicity and key redundancy using
methods other than what shannon came up with in "Communication Theory of
Secrecy Systems"?
I am stumbling over how to prove the 'perfect security' of a product system.
I am working on proving this for the affine cipher. I assume that this is a
rather trivial proof, but I am stuck none-the-less. The keyspace is much
larger than the messagespace or the cipherspace, and I am unsure how this
would affect the calculation of the a priori probablity of a message. Would
it just be the product of the probabilities of a message from the 'component'
systems?
Any help would be appreciated. Reply by email if possible:
[EMAIL PROTECTED]
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED]
Subject: unicity, redundancy and help
Date: Tue, 23 Mar 1999 04:10:42 GMT
My apologies if this posts twice, dejanews freaked out on me.
Does anyone know of papers or articles (on the web or in journals) that
address unicity and key redundancy with RSA, Eliptic Curve, ElGamal or DES?
Or for that matter ways of analyzing unicity and key redundancy using
methods other than what shannon came up with in "Communication Theory of
Secrecy Systems"?
I am stumbling over how to prove the 'perfect security' of a product system.
I am working on proving this for the affine cipher. I assume that this is a
rather trivial proof, but I am stuck none-the-less. The keyspace is much
larger than the messagespace or the cipherspace, and I am unsure how this
would affect the calculation of the a priori probablity of a message. Would
it just be the product of the probabilities of a message from the 'component'
systems?
Any help would be appreciated. Reply by email if possible:
[EMAIL PROTECTED]
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: Pat Ekman <[EMAIL PROTECTED]>
Subject: Re: Basic OTP questions
Date: Tue, 23 Mar 1999 05:27:30 +0000
The reason an OTP works is because the key is the same length as the
message, as well as truly random (ie. generated by some natural source
of noise and not by a mathematical algorithm). There is absolutely no
relationship between one bit of the key and any other bit.
Imagine you have a message that has been encrypted by an OTP. You know
that the message is plain text, and that it begins with the words
"Commence your attack at..." What can you do to find the remainder of
the message? From a cryptography standpoint, nothing--you'd better try
the more tried-and-true methods of surveilance, interrogation and
torture. :-)
The reason is simple. Even though you can XOR (or subtract--depending
on how the key was added in the first place) the known part of the
message from the ciphertext to get that part of the key, it won't do you
any good. The key is truly random. There's no use in looking for some
sort of relationship between this part of the key and any other--there
simply isn't one. Knowing one part of the key won't help you learn
another part.
If the message is encrypted with a different cipher... say IDEA, you now
have a chance. You know the first part of the message. You also know
that the message was encrypted in 64 bit blocks. Now, if you can
discover what key decrypts the beginning of the message back to
"Commence your attack at...," you can use that key to decrypt the rest
of the message. (Of course, with IDEA you'd still have your work cut
out for you, but (excuse the pun) you get the idea--learning the entire
message is at least theoretically possible--even if it might take
billions of years).
I hope this helps you see the difference.
To answer your other question, knowing if you've found the right message
isn't necessarily an exact science. However, it is almost always
possible to learn part of the plaintext--most file formats and protocols
have standard headers and such.
Plus, if you think about it, the number of legitimate-looking messages
is infinitesimally small compared to the number of random-looking ones.
If you find a key that decrypts a message to something reasonable, the
key is almost certainly the right one.
Have fun reading Applied Cryptography--it's a great introduction to
cryptography.
--
Pat Ekman
[EMAIL PROTECTED]
Tim Mavers wrote:
>
> I just started reading Applied Cryptography and had some basic questions
> regarding OTPs. In the book, he says that in theory a OTP is the perfect
> encryption because as long as you have random numbers in your keys, it would
> be impossible to determine the message because the ciphertext could be
> deciphered to any phrase. Not knowing the phrase would make it impossible
> to tell if you had the right key.
>
> Now isn't this the case with most encryption algorithms? You really have to
> know what your looking for in order to find it, right?
>
> On that note, how does one know if you have the right message? I was
> always curious to know this after reading about Deep Crack and the other
> various brute-force attacks against DES. With the kinds of possible
> combinations they go through, how the heck do they know when they have found
> the right message? I am sure at some point, certain phrases may come up
> that appear to be legimate, where in all actuality, they are just anomolies
> generated by coincidence.
------------------------------
From: "_DEFAULT" <[EMAIL PROTECTED]>
Subject: Re: Common Modulus Attack
Date: Mon, 22 Mar 1999 23:39:01 -0600
Thanks for your answer to my post, it helps me A LOT in understanding this
type of attack and how to avoid it. Working out examples really helps.
Again, thanks!
[EMAIL PROTECTED] wrote in message <[EMAIL PROTECTED]>...
>[EMAIL PROTECTED] wrote:
>
>> Now ... assume we only know the public keys (e1,n) (for Ralph, say) and
>> (e2,n) (for Betty, say) and the n's are the same and see the original
>> message "m" (somehow we know that this is the same message -- say, Jane
>> sends the same message to Ralph and Betty who have the same modulus in
>> their public keys) sent to Ralph and Betty, so we see c1 and c2. We know
>> e1, e2, n and c1, c2. We DON'T know either d1 or d2 (the private keys for
>> Ralph or Betty).
>
>With e1 and e2 relatively prime (so there exist r and s with r*e1+s*e2=1).
>
>> Just knowing e1 and e2 (NOT KNOWING d1 OR d2!) we can find r,s.
------------------------------
** 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
******************************
