Hashing Redux: Proving What You Know

Remember my post about hashing passwords? I recently encountered a tweet exchange between two of my co-workers that used hashing in a novel and nerdy way. 

It started with this:

image

Jorge is posting a quote from Minnesota congresswoman and amateur conspiracy theorist Michelle Bachmann, helpfully providing a link to the source. But he’s also added a mysterious string of letters and numbers in parentheses. Why? Let’s find out.

Harry replies with:

image

Pointing out to Jorge that the source is satirical, and that he’s been duped into believing that this is a real quote. And, to be honest, given Congresswoman Bachmann’s propensity for fanciful conspiracy theories, anyone might have fallen for that. Or would they?

Jorge could have tried to save face by tweeting “of course I knew it was satire, he he…” And we would have been forgiven for thinking “yeah right… if you knew that you would have said so in the original tweet”. Jorge could have then claimed “well, but I didn’t want to ruin the tweet by giving the game away”, but that would have sounded defensive and lame.

Instead, Jorge tweeted this:

image

What the hell does that mean? 

Saving Face via md5

If you’re on a mac right now, open up a terminal (Applications -> Utilities -> Terminal) and enter this:

md5 -s “Yes, I know this is satire.”

Hit enter. Does the result look familiar? Yep, it’s that strange string of letters and numbers that Jorge added to his original tweet. md5 is a type of hash - “a way of jumbling up text in a way that can’t be unjumbled”, as I put it in my old post.

What Jorge has cleverly done is use md5 to prove that he knew this was satire all along, without saying so explicitly and ruining the tweet. Not just claim, mind you, but prove.

The logic is as follows: “That hash I provided in my original tweet? That is the hash of the sentence ‘Yes, I know this is satire.’ And since hashes are not reversible, there was no way for me to use a random string and then later reverse-engineer it into a face-saving sentence. Therefore I must have derived that hash from that sentence when I was writing the tweet.”

Basically, Jorge did say “Yes I know this is satire” in the original tweet, but he did it in a clever way.

Not Giving the Game Away

A consequence of the fact that hashes aren’t reversible is that no one, no matter how nerdy, could have figured out what sentence Jorge used to derive the hash until he told them. So publishing that hash didn’t ruin the original tweet by giving the game away. 

This tweet exchange gives a small taste of the powerful applicability of computer science to so many real-life problems. This example may seem trivial, but here’s a more significant one:

Keeping Secrets

Imagine, for example, that you’re a secret agent. A fellow agent, whom you’ve never met,  approaches you and asks “hey, did you get that new top-secret document? I wanted to discuss it with you.” Sounds reasonable, right?

But wait! Maybe this person isn’t an agent after all. Maybe she’s a journalist, or worse, an enemy spy, trying to get something out of you by claiming to know more than she does. Pretending to have insider information is a classic form of social engineering.

So you say to the alleged agent, “tell you what, to prove to me that you have access to the top-secret document, send it to me.” But she, being, or at least pretending to be, a responsible agent, says “don’t be daft*, I don’t know if you yourself are allowed to read it”. What an impasse!

Then, remembering the CS classes you took in college before you went to secret agent school, you suggest this: “OK, let’s each compute the hash of the document, write it on a note, and exchange the notes.” Now, if you both give each other the same hash you can each be certain that the other has access to the document, and you can discuss it without fear of revealing anything to an unauthorized person. And if not - time to call security: you’ve uncovered an impostor without actually revealing any information to them.

This example shows that the ability to retroactively prove that you know something, without revealing that thing up front, is incredibly powerful. 

* Apparently this is a British secret agency…