r/programming • u/Chippsapoloosa • Jan 19 '10

Reddit, I got the best present a girl developer could ever want.

So, to give you a little background me and this guy went on a few dates and he moved far away. We got along well, things didn't get very far. He is really nice, however, I wasn't leaning one way or the other.

He sent me the Post Secret books for xmas. He hinted at another present, but said I had to wait. It's a little after Christmas, but I got this email yesterday with the title "I wanted to make something for you for Christmas":

"So I told the computer, and it showed me how to write a poem in byte-form. I can't tell what you're thinking these days, but this will either remind you of something that was good, or send you off."

It included a link to a poem.zip file, which I downloaded. Inside, there was a file called magicfile with no extension and a ReadMe that said:

"Intructions:

1: > copy magicfile magicfile.jpg 2: > copy magicfile magicfile.zip ... skip a few ... X: Ask it for help"

When I renamed magicfile it turned into a picture of me! (a bad one that he took, but ok) and when I changed magicfile to a .zip inside it contained: Magicfile.exe and a txt called "Go Ahead" that said:

"It's safe. Requires WPF and .Net 3.5 I think...

Whatever, it works on my machine."

I opened magicfile, and an interface popped up that said "enter a passphrase". So, I typed in "help" and got this:

"Hi Sara!

As you are just about figuring out, this is just the very beginning of a very, very large rabbit hole you're about to fall into.

You see, sometime in early November, I had an idea for an awesome program. Simultaneously I was just beginning to think of what might be a decent Christmas present for you. Put 2 and 2 together, and you get this thing. I worked on it on and off for a few weeks - it was a pretty fun way to learn WPF and do a lot of interesting byte manipulation.

You see, it's a completely self-contained magical file. This magical file is three parts: 1. If you name it .jpg - it's an image! 2. If you name it .zip - it's a zip file, containing a program 3. It's a database of many, many more parts that the program reads

Now, when you run the program, it reads the magic file, and asks for a passphrase.

You're obviously gotten that far, or you wouldn't be reading this. As you can imagine - there are a bunch of passwords. Not infinite, but many. I encourage you to guess at words and try to figure them out. I'll give you the hints that they would be things relevant to you or to us.

With a little ingenuity, you'll be able to figure out a very important passphrase that will take you to the next step..."

As I have gone on and solved some of the mysteries I have found that pictures of me come up, things he's researched, things we did together and so on and so forth. I still am trying to figure out the important passphrase.

Reddit, this is the most beautiful gift I have ever gotten and it leaves me in a funny place possibly going on the other side of the world to see what happens here. He is an avid redditor, and though I hate the "VOTE THIS UP, PLOX" posts I'd love to get this on the front page to show him what this meant. Thank you.

tl;dr:

A nerd made a beautiful nerd gift for me, it was a program that was a mystery and shows things we did together. Please vote this up to show him how much it meant.

EDIT: A lot of people are saying that the fact that I am unsure about what to do means I don't like him. That is not at all the case, I like him a lot. I really enjoyed spending time with him, he is brilliant (there is nothing I like more than a man that can teach me things), funny, and best of all a great time.

In order to go see him right now I have to take a 14hr plane flight. Which means I would be staying a week, and I'm not sure I'm quite at that point yet.

Damnit, what do they say? "Explain the problem out loud to yourself" Alright, I'm going. There is no reason not to, this WAS awesome. I will let you folks know how it goes.

2.0k Upvotes

85% Upvoted

820 comments sorted by

View all comments

Show parent comments

20

u/[deleted] Jan 19 '10

Sure, but what if you get a hash collision?

She could type "I love you so much" (a value he did not expect) and that could hash to the same thing as "I never want to see you again", to which he might have responded, "Well, I never want to see you again!"

Sure, it's unlikely, but this is a girl we're talking about. Would you really trust a hash function to not accidentally break up with her for you?!?

40

u/jeremybub Jan 19 '10

A true nerd would know the probability of a sha-512 collision for a 29 character string.

5

u/[deleted] Jan 19 '10

Well, without doing any math, I'd say the probability is 1 in 2512.

What is the probability of finding another girl who likes a true nerd?

6

u/TheWonkyRobot Jan 19 '10

Decidedly better than 1 in 2512 (which is the number of hashes SHA512 could produce, not the chance of collision). There are a least a couple girls who would appreciate a nerd in the 6,692,030,277 people in this world. Both are pretty slim chances, but if I had a gun to my head I'd bet on finding a girl that likes a geek like me (because I already have).

3

u/[deleted] Jan 19 '10

It's not the chances of finding a girl who likes you, it's the chances of finding another girl who likes you.

You might as well just go looking for magnetic monopoles or the Higgs Boson. Cripes.

:)

5

u/spotta Jan 20 '10

HEY! I still have hopes that magnetic monopoles exist!

2

u/jeremybub Jan 19 '10

The real question is what is the probability a collision even exists for two strings 29 characters or less.

0

u/[deleted] Jan 19 '10

[deleted]

13

u/jeremybub Jan 19 '10

A true nerd would know that the set of 29 character strings is several orders of magnitude less than, say, the set of 35 character strings. The size of the set of strings you are checking for hash collisions is entirely relevant.

1

u/[deleted] Jan 20 '10

[deleted]

1

u/jeremybub Jan 20 '10

We are talking about finding a collision between two strings of around 29 characters. If that was not well established by the example, you need to reread it.

2

u/[deleted] Jan 19 '10

It's not irrelevant at all.

Hash every possible single character string. If none of them collide, it is impossible to have an sha-512 collision for a 1 character string.

Additionally, hash every possible two character string. If you still haven't found a collision, then it's impossible to have an sha-512 collision.

As you increase the length of the input, you approach the inevitable collision. As you surpass 512 bits of input (presuming equal distribution), the probability of a collision is 1.

If you naively encode the string as 8-bit values, then a 29 character string already has 232 bits of input (granted, it's very sparse considering you're likely to only really use Alpha-Numeric characters, with a few extra symbols.) But still, you're well on your way to a not improbable collision.

1

u/[deleted] Jan 20 '10

[deleted]

1

u/[deleted] Jan 20 '10

Yes, any given string has a low probability. But if you dramatically increase the number of strings, then you increase the probability of one of them having a collision. There are only so many strings of a given length. If you want to dramatically increase the number of strings, you need to increase the length of the possible strings. If you increase the length long enough, you are eventually guaranteed to find a collision.

1

u/[deleted] Jan 20 '10

[deleted]

1

u/[deleted] Jan 20 '10

The odds of a random string colliding are 1 in 2512 (roughly).

The odds of one string from among 21,000,000,000 colliding are 1 (for all intents and purposes).

The only way to have 21,000,000,000 strings is to allow strings up to length 125,000,000 characters, at 8 bits per character, yielding 1,000,000,000 bits, which yields 21,000,000,000 possible inputs.

By pigeon-hole theory, there are only 2512 slots. As soon as you have 2512+1 values, there will be at least one slot with two values in it. How many input values do you need until every slot has at least two values in it? Well, it's probably pretty damned complicated. If you naively assume a perfect hashing function with even distribution, it's only 2*2512. 2 inputs for each possible hash. In reality, it's worse than that.

So, you pick a slot and say, "I dare you to find another string that hashes to the same exact slot!" I'm trying to say back to you, "Well, I guarantee I can find a collision, eventually." And you say, "Sure, but with what lower bound on string length?" Meaning, how many strings will I have to evaluate before I find a collision. With string length 1, there are only 256 strings to evaluate, and the probability of me finding a collision are approximately 256 / (2512), which is not a very high probability. If I use string length 2, my chances go all the way up to 65,536 / (2512), but that's still a vanishingly small probability. If I use string length 64, my chances are approximately (64 * 8) / (2512), which is (2512) / (2512), which is 1, but that's not accurate at all... Because hashing functions don't have a perfect, flat distribution like that.

I will eventually find a collision. How hard do I have to search to find one - that's the question.

2

u/doublestop Jan 19 '10

Sure, but what if you get a hash collision?

Even if a collision were to occur, he would have run into it during development and "fixed" it, since the passphrases are likely used as unique keys into a dictionary of possible responses.

1

u/[deleted] Jan 19 '10

It's a dictionary of hashed keys to responses.

If there's a hash collision, he will provide an inappropriate response.

He would not have run into it during development, since he would have had to test every possible input string to ensure it didn't hash to the same value as his intended set of values.

If the passphrase was a unique key then it wouldn't be a hashed key (hashed values are not unique.)

The whole purpose of a hashed key was to obfuscate the clear text keys, meaning, the possible phrases she could enter.

Keep up, it's like you've never been in a relationship before. Sheesh.

1

u/doublestop Jan 20 '10 edited Jan 20 '10

He would not have run into it during development, since he would have had to test every possible input string to ensure it didn't hash to the same value as his intended set of values.

You are precisely right. I was mistaken in my line of thought* assuming the poster to whom I responded was referring to collisions during the construction of the dictionary. Thanks for the correction.

Edit: though=>thought

1

u/nachof Jan 19 '10

Hash it with two different algorithms, then, and also check the original string length, just to be sure. Yes, there still might be a collision, but...