Cryptography-Digest Digest #755, Volume #10 Fri, 17 Dec 99 14:13:02 EST
Contents:
Re: Questions about message digest functions (James Felling)
Re: I was just thinking about a potential Cipher system... (John Savard)
Re: DES key safety (John Savard)
Re: Enigma - theoretical question (UBCHI2)
The 20 years periods did apply to 2 of the 3 patents. Why not for RSA ?
([EMAIL PROTECTED])
Re: ARC4 cipher... ("r.e.s.")
Re: Off topic -- 4 year old (Keith A Monahan)
Re: Euclid Algorithm (Medical Electronics Lab)
Re: ARC4 cipher... (John Savard)
Re: Cryptologia journal (John Savard)
Re: More idiot "security problems" (Xcott Craver)
Re: US Patent Office: How Stupid? Look Here... (Paul Koning)
Re: ARC4 cipher... (Paul Koning)
Re: More idiot "security problems" (JPeschel)
Re: First step in finding primes (Keith A Monahan)
----------------------------------------------------------------------------
From: James Felling <[EMAIL PROTECTED]>
Subject: Re: Questions about message digest functions
Date: Fri, 17 Dec 1999 11:45:59 -0600
Tim Tyler wrote:
> James Felling <[EMAIL PROTECTED]> wrote:
> : Tim Tyler wrote:
> :> wtshaw <[EMAIL PROTECTED]> wrote:
> :> : In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
> :> :> wtshaw <[EMAIL PROTECTED]> wrote:
>
> :> : Since you asked, I resolve a portion of my comment: collisions and
> :> : security of a hash function work in opposition, no collisions meaning
> :> : that the input can be solved, be that perhaps inconvenient. But, if
> :> : lots rode on the solution, it might be worth it.
>
> :> Surely collision resistance and security are generally positively
> :> connected - rather than negatively.
>
> : Simply put, in a hash both are desirable properties.
>
> Yes, indeed.
>
> : Ideally youur hash should be as collision resistant as possible. Ideally
> : it should also be resistant to being worked backward (if every message
> : has a unique hash this can be a problem as far as keeping the messages
> : secure).
>
> Can it? How?
>
> This can only happen if hash-size = message size. The alternative is to
> give some messages the same hash as one another. This makes little
> difference to the ability to locate the hash for any given message, but
> makes collisions infinitely more probable :-(
If Hashsize>=message size.
>
>
>
> : However, pursuing any one of them is a bad thing.
>
> /How/ is pursuing collision resistance a bad thing?
Pursuing any one of them to the exclusion of the other is a bad thing. ( I
should have added that qualifier for clarity)
>
>
> *Ignoring* the difficulty of reversing the hash /would/ be a bad thing.
> But "one-way"ness does not require increased probability of hash
> collisions as far as I can see.
>
> : XORing the message with a fixed key/ permuting it with a fixed permutation
> : is completely resistant to collision [...]
>
> This is only possible if hash size = message size, of course.
If messagesize>hash size then treat hash(block1) as the key. By completely
resistant I mean that it is as resistant to collision as it is possible to be
for a hash of that size.
>
>
> [...] but is horribly insecure [...]
>
> Yes. For one thing, this is not a one-way function.
>
> : [...] and maping all values to 1 of 4 values is very resistant to being
> : worked backward [...]
>
> No. It's likely to be trivial to "work backwards":
>
> Validate the hashes on a few messages - until the values of all four
> hashes are known.
>
> Then append these four hashes in turn to your target message. One of them
> will validate as being correct. You don't need the private information
> about the primes (or whatever) that are used to generate the hash in order
> to be able to do this.
Accepted -- though this attack is equivalent to for an n bit hash append all 2^N
possible hashes to the message and see which one works. In addition if you are
given two messages, both of which hash to value #4 which message was the valid
one?
>
>
> This attack can be applied in a large number of the cases where hashes are
> applied in practice.
>
> : One must seek to maximize both and remain aware that when it gets down
> : to it, there are tradeoffs that must occur.
>
> Tradeoffs are not required. Collision resistance and security do not
> pull in opposed directions.
They do indeed, it is simply that if one posseses a very good hash that manages
a high level of both, it is hard to improve one without hurting the other.
>
>
> I'll qualify this. Look at the attack that minimal collision-resistance
> leads to in the case when message size = hash size:
>
> Having a message (of the same length as the hash) with a correct hash
> gives the attacker information that no other messages (again of the same
> length of the hash) do not have this hash.
>
> The attacker would not have this information if the hash simulated a
> genuinely random function.
>
> This attack /could/ conceivably lead somewhere if most possible
> messages of that length had had their hashes discovered - except
> the one in question.
>
> These circumstances are pretty unlikely.
>
> To think that eliminating this attack by removing this information - and
> consequently opening the door for random hash collisions - is worth it
> seems to me to be utterly fantastic.
I agree that this is mostly an academic argument, but I do feel that at the
highest end there are definite design tradeoffs here.
>
> --
> __________
> |im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
>
> A good traveller leaves no track.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: I was just thinking about a potential Cipher system...
Date: Fri, 17 Dec 1999 10:45:46 GMT
"Pipian" <[EMAIL PROTECTED]> wrote, in part:
>There would be 26 Enigma-like mechanisms, theoretically labeled A-Z...
>According to a certain keyword/words, you would switch between the machines
>containing the letters of the keyword...
Each Enigma machine, and therefore this resulting cipher, has the
weakness that no letter is enciphered to itself.
If you used another kind of rotor machine, without that problem,
and if you used another rotor machine, instead of just a repeating
keyword, to switch between rotor machines,
I think that you would probably have something reasonably secure. But
it is possible to make mistakes.
If you used a complicated method to decide which of the unused rotor
machines step, then you would improve the strength of the cipher as
well.
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: DES key safety
Date: Fri, 17 Dec 1999 10:41:41 GMT
"Tom Pedersen" <[EMAIL PROTECTED]> wrote, in part:
>Is DES safe towards the key? I mean if you have the cleartext and the
>ciphertext could you derrive the key? Theory and practise is two different
>issues, so actually I'm asking two questions.
Except for brute-force search - which is possible with a 56-bit key -
DES is quite safe against attacks aimed at finding the key from known
plaintext.
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (UBCHI2)
Subject: Re: Enigma - theoretical question
Date: 17 Dec 1999 17:53:22 GMT
If you are going to use the enigma software that you can download off the
internet, you should rewire the rotors to a custom pattern. The wiring of the
rotors can be an important secret.
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: alt.security.pgp
Subject: The 20 years periods did apply to 2 of the 3 patents. Why not for RSA ?
Date: Fri, 17 Dec 1999 13:06:08 -0500
The 3 most known patents in the encryption area are :
Name Number Filed Expires
================================================================
Diffie-Hellman 4,200,770 Sept. 6, 1977 Sept. 6, 1997
Hellman-Merkle 4,218,582 Oct. 6, 1977 Oct. 6, 1997
RSA 4,405,829 Dec. 14, 1977 Sept. 20, 2000
The 20 years periods did apply to 2 of the 3 patents.
Why it is not applicable to the last one ?
--
Thanks, Richard
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: Re: ARC4 cipher...
Date: Fri, 17 Dec 1999 10:17:02 -0800
"Andrej Madliak" <[EMAIL PROTECTED]> wrote ...
: -----BEGIN PGP SIGNED MESSAGE-----
: Hash: SHA1
[...]
: -----BEGIN PGP SIGNATURE-----
: Version: PGPfreeware 6.5.2 for non-commercial use <http://www.pgp.com>
: Comment: Quis custodiet ipsos custodes?
:
: iQA/AwUBOFnpUoaZUlJQw2ggEQKzGQCfaQL39a/dK7wji1gsahd66YjMhYQAoNwf
: FUkdYax6qXlYJZcv1Cpec0CV
: =hUzp
: -----END PGP SIGNATURE-----
Sorry to butt in, and off-topic at that, but I have to ask...
What is the significance of the "SHA1" at the top of your post?
(I know SHA1 is a hashing algorithm, but if PGP uses SHA1, why
mention it? Obviously I am not much acquainted with PGP ;-)
--
r.e.s.
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Keith A Monahan)
Subject: Re: Off topic -- 4 year old
Date: 17 Dec 1999 18:18:18 GMT
Unfortunately, whether it's legit or not, it doesn't belong in
this forum, anyways.
Keith
Jim Gillogly ([EMAIL PROTECTED]) wrote:
: "r.e.s." wrote:
: > This looks to me like a re-run of the hoax known
: > as "the Internet's most prevalent thought virus".
: > See
: > http://www.web.co.za/arthur/craig01b.htm
: Agreed, but it's not. The Urban Legends site researched this one,
: and as of 9 Dec 1999 Miss Paige Lane was alive and expected to
: live a few more weeks, and has gotten sacks of cards already.
: Spamming it to unrelated groups is a terrible idea, but the info
: appears legit. See www.snopes.com, select Search at the bottom,
: and search for Paige. I imagine she has plenty of cards by now.
: --
: Jim Gillogly
: 26 Foreyule S.R. 1999, 05:29
: 12.19.6.14.4, 6 Kan 12 Mac, Fifth Lord of Night
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: Euclid Algorithm
Date: Fri, 17 Dec 1999 12:15:15 -0600
Miryadi wrote:
> What is the best way of implementing Euclid Algorithm,
> regarding its time complexity, using recursive or iterative method?
>
> Is there any web site that give information on this topic?
Check out Knuth, "Semi Numerical Algorithms". You'll find several
implementations and lots of reasons why you should pick one over
the other for your application.
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: ARC4 cipher...
Date: Fri, 17 Dec 1999 11:36:12 GMT
"r.e.s." <[EMAIL PROTECTED]> wrote, in part:
>(I know SHA1 is a hashing algorithm, but if PGP uses SHA1, why
>mention it? Obviously I am not much acquainted with PGP ;-)
The format of the header lines in PGP is designed for compatibility
with programs using the same format, but also other algorithms, such
as MD5 for hashing.
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Cryptologia journal
Date: Fri, 17 Dec 1999 11:32:32 GMT
[EMAIL PROTECTED] wrote, in part:
>I would like to acquire all back issues of
>Cryptologia, but I cannot afford the $ 12.00 per
>piece� !
>And a good number is out-of-print.
>Is there someone that would have them available ?
If you visit their web site, some of the _older_ issues are now
available at 75% off, so at least you can acquire some of them...
but I suspect you won't find too many people with complete sets
willing to part with them for less than they've paid themselves!
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (Xcott Craver)
Subject: Re: More idiot "security problems"
Date: 17 Dec 1999 18:42:35 GMT
Eric Lee Green <[EMAIL PROTECTED]> wrote:
>
[undoing copy protection]
>The lesson that I gained from that is that all "encryption" which relies upon
>having a decryption key buried in the code is insecure.
This is way too general. We were talking about hostile applets
harvesting your key, a different threat scenario.
Certainly the standard model of copy protection is pretty pointless,
encrypting a program but leaving the key under the doormat, and
and in that case you don't benefit from strong crypto, or multiple
layers of crypto. However, in the hostile applet threat scenario,
we can take advantage of the difficulty of using that key via remote.
For instance, imagine a (big fat) application which employs a kind
of widespread function hiding which can only accommodate a handful
of bytes (bandwidth is always a problem in data hiding.) A handful
of bytes is enough to hold one strong key, with the cryptotext
stored in the registry or in some other known, insecure location.
Note that the hiding method would be parametrized by a locally
generated key, a different key per license.
Now, while you could take a debugger and tear this application
apart, if you had access to the machine; a hostile applet could not.
The function hiding would just need to be such that a sufficient
amount of time, computation, and human intervention be required
to make it practically impossible to suck the password out through
a straw like that.
These kinds of data hiding problems are still hard, but there are a
lot of talented people researching them. I've seen some pretty
amazing holy grails in the field so far, some I thought would be
provably impossible, and so I wouldn't jump to any conclusions.
>The point, the point: Netscape could have used 3DES to encrypt the password
>stored in the registry, but the fact of the matter is that it has to be
>decrypted to plain text in order to pass via IMAP. What that means is that the
>decryption key has to be stored somewhere, either in the Netscape program text
>or whatever.
The sending of the password in plain text certainly negates any
posturing over key hiding. So does an application which uses
the same key per license, rather than generating a random one
and going to the trouble to try to foil applets. Beyond that,
I would still consider it a security hole to put an easily
decryptable password in a standard location. It's a third hole
that can be exploited even without the other two holes, without
sniffing, without a debugger, without knowledge of Netscape,
without a copy of Netscape.
And be careful about concluding insecurity simply because the
key is "stored somewhere" public. When you use public-key
cryptography, session keys are "stored somewhere" public
(sent along with the message data that they encrypt,) and
obfuscated with a public algorithm fed publicly known parameters.
All the information needed to extract all keys is right there.
Yet your debugger won't help you, the source code won't help you.
It's secure because it's done in such a way that reverse-engineering
the decryption method is not known to be tractible.
Presently, research is being done in identifying data hiding methods
with similar "public-key" mechanisms. Not to mention concealing
key data in compromised systems. It's neat stuff.
>And I'm not a so-called "security expert". No wonder I have nothing but
>disdain for the "security expert" who discovered this "security problem".
That makes you the third person I've seen on this group going to
the trouble to use double-quotes and so-calleds whenever referring
to known security experts.
The other two are Bob Knauer and David A. Scott.
Goodbye and, really, truly, from the bottom of my heart, good luck.
>-- Eric Lee Green http://members.tripod.com/e_l_green
> [EMAIL PROTECTED]
-X
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: US Patent Office: How Stupid? Look Here...
Date: Fri, 17 Dec 1999 13:45:25 -0500
Anthony Stephen Szopa wrote:
>
> US Patent Office: How Stupid? Look Here...
Or look here... then you won't be surprised anymore.
http://patent.womplex.ibm.com/details?&pn=US05446889__
(And yes, there are others of that caliber...)
paul
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: ARC4 cipher...
Date: Fri, 17 Dec 1999 13:47:12 -0500
Andrej Madliak wrote:
> Has anybody heard of
>
> ARC4 stream cipher ...
That's just another name for RC4 (chosen to avoid being
hassled by RSA's trademark police). So look up what's
known about RC4. As I recall, it's considered to be
good (if you use a real key, of course, like 128 bits).
paul
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: More idiot "security problems"
Date: 17 Dec 1999 19:05:14 GMT
[EMAIL PROTECTED] writes,in part:
>Game makers tried all
>kinds of tricks to stop me and my ilk, such as, e.g., encrypting their
>encryption code with one key, then the decrypted code contained yet another
>key to decrypt another entire block of encryption code, etc., etc., but I
>always got my man. The reason? No program is immune to a good debugger (and
>by
>the end, what finally got game makers to give up on copy protection, HARDWARE
>ASSISTED debuggers marketed at crackers were pretty darned cheap!).
>
>The lesson that I gained from that is that all "encryption" which relies upon
>having a decryption key buried in the code is insecure.
You'll find most commercial encryption programs, including PGP, do some
sort of check for a correct password during decryption. Is this what you
mean by "having a decryption key buried in the code?"
>David Wagner proved in his cryptanalysis of the Netscape 1.0 SSL
>code that it's possible to run even a program as huge as Netscape through a
>binary debugger and gain critical insight into its security (he found they
>had
>a buggy PRNG, btw, though that has been fixed since). So any hacker could get
>the decryption key needed to decrypt the password stored in the registry --
>no
>matter what the algorithm used.
Sure, it's possible, and usually fairly easy to run a large program in a
debugger
and target certain chunks of code. If the program is buggy a cracker may find
snippets of code to patch, or may develop code that reverses the algorithm
and recovers the password.
In some cases, a cracker may find, during a debugging session, that during
decryption the entered password is compared in-the-clear to the correct
password.
Often though, he isn't that lucky.
>I guarantee you that if Netscape had used 3DES to encrypt that password, I
>could *STILL* have decrypted the password, simply by stepping through
>Netscape
>until I found the portion of the code that decrypted the key, finding the
>place inside Netscape where the key was stored, and then duplicate that code
>and decryption key into a stand-alone "decode all Netscape passwords
>everywhere".
I think you're glamorizing your childhood code-cracking glory-days a tad. :-)
Stepping through and editing snippets of code, or applying a patch, won't
work if the the password checking algorithm, usually a one-way hash,
is secure.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: [EMAIL PROTECTED] (Keith A Monahan)
Subject: Re: First step in finding primes
Date: 17 Dec 1999 19:08:33 GMT
Tom,
Have you looked at NTL(Number Theory Library) ? It's a C++ library
for working with large numbers. Included in it, are things like
the Miller-Rabin Witness test and other algorithms for finding and testing
large primes. Most of the algorithms are fairly state of the art and
fast, too.
http://www.shoup.net/ntl/
I used it when creating a small RSA crypto proggie.
Keith
Tom St Denis ([EMAIL PROTECTED]) wrote:
: In AC he suggests dividing by primes upto 256 which would give you
: 1.12/lnx or ~79.8% of all odd composites. I was thinking wouldn't it
: be easier just to check gcd(n, x) = 1, where n = 2 * 3 * 5 ... * phi
: (256) [phi(x) is the x th prime]. The number would be huge at first,
: but after the first few itterations would get smaller. It would save
: space and probably time as well.
: Just a thought.
: Tom
: Sent via Deja.com http://www.deja.com/
: Before you buy.
------------------------------
** 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
******************************
