One-way hashes and arguments

| Comments (6) | COMSEC Environment
Julian Sanchez's post about the difficulty of evaluating technical arguments has been circulating fairly widely. In the middle is a somewhat strained analogy to cryptography:
Sometimes, of course, the arguments are such that the specialists can develop and summarize them to the point that an intelligent layman can evaluate them. But often--and I feel pretty sure here--that's just not the case. Give me a topic I know fairly intimately, and I can often make a convincing case for absolute horseshit. Convincing, at any rate, to an ordinary educated person with only passing acquaintance with the topic. A specialist would surely see through it, but in an argument between us, the lay observer wouldn't necessarily be able to tell which of us really had the better case on the basis of the arguments alone--at least not without putting in the time to become something of a specialist himself. Actually, I have a possible advantage here as a peddler of horseshit: I need only worry about what sounds plausible. If my opponent is trying to explain what's true, he may be constrained to introduce concepts that take a while to explain and are hard to follow, trying the patience (and perhaps wounding the ego) of the audience.

Come to think of it, there's a certain class of rhetoric I'm going to call the "one way hash" argument. Most modern cryptographic systems in wide use are based on a certain mathematical asymmetry: You can multiply a couple of large prime numbers much (much, much, much, much) more quickly than you can factor the product back into primes. A one-way hash is a kind of "fingerprint" for messages based on the same mathematical idea: It's really easy to run the algorithm in one direction, but much harder and more time consuming to undo. Certain bad arguments work the same way--skim online debates between biologists and earnest ID afficionados armed with talking points if you want a few examples: The talking point on one side is just complex enough that it's both intelligible--even somewhat intuitive--to the layman and sounds as though it might qualify as some kind of insight. (If it seems too obvious, perhaps paradoxically, we'll tend to assume everyone on the other side thought of it themselves and had some good reason to reject it.) The rebuttal, by contrast, may require explaining a whole series of preliminary concepts before it's really possible to explain why the talking point is wrong. So the setup is "snappy, intuitively appealing argument without obvious problems" vs. "rebuttal I probably don't have time to read, let alone analyze closely."

Unfortunately, Sanchez has the cryptography pretty much wrong. He's confused two totally separate cryptographic concepts: public key cryptography, and one-way hashes. Some PKC (but not all) involves multiplying large prime numbers. Hash functions (with the exception of VSH, which is impractically slow and not in wide use), don't involve prime numbers at all. Neither does symmetric encryption, which is what you actually use to encrypt data (PKC is used primarily for key exchange and authentication/signature). Now, it's true that prime multiplication is indeed a one-way function (or at least we hope it is) and hash functions are intended to be as well, but other than that, there's not much of a connection.1 That said, however, I've seen this post referenced several places, and with the exception of Paul Hoffman, who pointed it out to me, few seem to have noticed, that, well, it's horseshit. I suppose this is an argument in favor of Sanchez's thesis.

1.Hash functions are actually one-way in an important sense that prime number multiplication is not: any given integer only has one unique factorization, whereas there are many messages that hash to a single value, so it's always possible with enough computational effort to reconstruct the original primes. However, given a hash value and no other information, it's not possible to determine which of the possible input messages was fed in.

6 Comments

I think he meant "one-way function" instead of "one-way hash." I actually like his analogy, but I doubt it did anything to explain his point to non-cryptographers.

I think he meant "one-way function" instead of "one-way hash." I actually like his analogy, but I doubt it did anything to explain his point to non-cryptographers.

When I read Julian's original, I had a "wait, that's not right" moment where he switches from factoring products of large primes to talking about hashes. But when I went back and read closer, I'm not sure whether he has the wrong idea or not.

The key sentence is: "A one-way hash is a kind of "fingerprint" for messages based on the same mathematical idea: It's really easy to run the algorithm in one direction, but much harder and more time consuming to undo."

If you parse "the same mathematical idea" as "factoring products of large primes", it's wrong. But if it's "functions that are easy to run in one direction but hard to undo" (an interpretation that's supported by the rest of the sentence), it's just confusing for people who know about PKC and one way hashes.

If it is the latter, I won't speculate whether it was just inapt wording or an illustration of his point. :-)

Yes, of course I understand they're not the same thing. I mentioned factoring products of primes in public key crypto because I assumed it was the example of a one-way function with which readers were most likely to be at least vaguely familiar. For the purposes of my rather loose metaphor, the details didn't seem especially relevant.

David, Edgewood, even if you parse the PKC and one-way hashes as parallel rather than saying that this implies that one-way hashes are based on factoring, the paragraph is still wrong. The previous sentence states that "Most modern cryptographic systems in wide use are based on a certain mathematical asymmetry: You can multiply a couple of large prime numbers much...", but this isn't correct either. Let's take a look at a sample protocol, TLS, which "in wide use" uses something like 5 cryptographic primitives: RSA, DH, AES, RC4, MD5, and SHA-1. Only one of these (RSA) is based on factoring.

I'll let people draw their own conclusions about whether this kind of detail is relevant.

Sure, I could've worded that better. I just meant that this particular mathematical idea was widely used, insofar as lots of popular protocols make use of RSA. Again, I glossed a lot of details because I was trying to quickly lay out a metaphor in service of a point that didn't actually have anything to do with cryptography. If I had known people would try to read the post as a CS primer, I would've been more careful.

Leave a comment