pmetzger@lehman.com said:
Each DES block is eight bytes. You can't use hashing -- the idea is nonsense in context. Did you read the original post?
Yes, I did. If hashing doesn't work, you'll have to say why not. It's a technique that works in most other situations.
First of all, its actually twice that because you really need 16 bytes.
As I said, we can tackle this if anyone cares to...it's unclear that this is an invitation, but assuming it is: hashing gives a first-pass screening good for every 1/256 calculations, given the assumptions I stated. For each collision more work is needed...but you haven't invited that analysis, nor addressed it yourself.
Second of all, the method is still impractical. I was merely giving the easiest and most obvious attack on it.
Impractical? Your response to Karl implied that it was *impossible*. If you wish to apologize to Karl, and say that it is merely "impractical", then I will agree with you and drop the subject. The expense required definitely indicates that it is "impractical."
I see no reason to continue this. I don't think your argument has credibility.
Clearly you are preparing to drop the argument because you sense that your tactic of flaming didn't work. I welcome the lessening of flames, so thank you for that. We could use less flames here. Doug
Doug Merritt says:
pmetzger@lehman.com said:
Each DES block is eight bytes. You can't use hashing -- the idea is nonsense in context. Did you read the original post?
Yes, I did. If hashing doesn't work, you'll have to say why not.
It's a technique that works in most other situations.
You don't know anything about hashing, then. When I use a hash table, it is never a substitute for storing the actual value of the thing I'm hashing. Its always just a way of rapidly FINDING the underlying object. I have to store the underlying object in order to compare to it. As an example, in a hashed symbol table, I store the actual symbols. If you tried to work out your proposed cracking algorithm instead of requesting that other people do all your thinking for you, you'd see what was wrong with it.
Second of all, the method is still impractical. I was merely giving the easiest and most obvious attack on it.
Impractical? Your response to Karl implied that it was *impossible*.
The two are very similar in our field. Cracking RSA with a 2000 bit key is merely impractical, not impossible, where "impractical" is defined as completely beyond human ability.
Clearly you are preparing to drop the argument because you sense that your tactic of flaming didn't work.
You can lead a horse to water, but you can't make him think. Perry
"Perry E. Metzger" writes:
Doug Merritt says:
pmetzger@lehman.com said:
Each DES block is eight bytes. You can't use hashing -- the idea is nonsense in context. Did you read the original post?
Yes, I did. If hashing doesn't work, you'll have to say why not.
It's a technique that works in most other situations.
You don't know anything about hashing, then.
When I use a hash table, it is never a substitute for storing the
^^^^^^^^^^^^^^^^^^
actual value of the thing I'm hashing. Its always just a way of ^^^^^^ rapidly FINDING the underlying object. I have to store the underlying object in order to compare to it. As an example, in a hashed symbol table, I store the actual symbols.
I haven't been following this thread very closely, but I do want to point out some serious errors in Perry's previous paragraph. Hashing can indeed be a substitute for storing the actual value of the thing being hashed, and it can often be used to reduce storage requirements. I'm not sure if it can be used in the case of a meet in the middle attack on double DES encryption; I'll have to leave the answer to that question up to those that are following this thread. I have used hashing in ways other than for *FINDING* the underlying object. Often, I don't need to know the correct answer to a question with 100% confidence. When I'm satisfied with an algorithm that gives the correct answer 99.999999999999999995% of the time I can use a good 64 bit hash as a surrogate for the actual value that may be too costly to store, compare, look up, or compute. The use of a message digest, like MD5, to insure message integrity is an example of this kind of "hashing". Other uses include keeping a short (say 32 bit) hash value in memory for every record stored in secondary storage. This allows very fast lookups that return negative answers, if the hash value isn't found there is no need to examine the values stored in secondary storage. For a large class of problems one expects not to find an entry for the record at all for most lookups. (Knuth uses the example of a hyphenation dictionary that stores exceptions to some hyphenation algorithm. Before applying the general algorithm consult the in-memory table to see if the word being hyphenated might even appear in the exception dictionary; there is no need to search the exception dictionary if it contains no words with the same hash value as the word being hyphenated. An example more appropriate for this group might be detecting replay attempts. One doesn't expect replay attacks to happen so the algorithm should be performance optimized with this in mind.) Finally, there are times when space-time kinds of trade-offs are being made in the design of an algorithm where hashing can be used. For example, if computing some value takes too long it may be possible to pre-compute it or cache previous computations of the value. Techniques like this are easy to apply and are frequently used, but there are times when it is infeasible to store all of the values one would like to for space or even security reasons. Instead one can store a hash of each value (presumably, the hash is smaller than the value like a 32 bit hash instead of a 64 byte value) and only bother to recompute the value when a matching hash indicates a high likelyhood that it will be useful to compute the value and check for an actual match.
You can lead a horse to water, but you can't make him think.
The discussion on this thread doesn't seem to warrant statements like this. I've had the pleasure of working with some of the world's most talented computer scientists over the years, and I simply can't imagine one of them using a statement like this in the context of this topic thread. Statements like this are cute and impress me with the cleverness and humor of the author, but in writing they are so easy to misinterpret. In my opinion, they are best saved for use in social situations where some friendly kidding is going on, not mail groups where people are simply asking for help in understanding a subject they are unfamiliar with. Todd -- Todd Smith TIVOLI Systems, Inc. todd@tivoli.com 6034 West Courtyard Dr. Suite 210 (512) 794-9070 [794-0623 fax] Austin, TX 78730
participants (3)
-
doug＠netcom.com -
Perry E. Metzger -
todd＠tivoli.com