Puzzles from the xkcd book (big puzzle SOLVED!)

[aspragg]

I was just looking at the part 8/8 puzzle, and figured something else out (maybe?)

Spoiler:

The pairs of letters for the ENIGMA machine are

DO
NT
CR
LY
IK
EH
GU

If you read down in a snaking sort of fashion, you can get: DONT CRY LIKE HUG

With some punctuation: Don't cry. Like hug?

[Adacore]

Kudos on solving it, guys! Unfortunately, I'm on the wrong side of the world, but I hope those that can be there have a blast!

[cdehaan]

Good job on the document. I was being a bit too perfectionist in my attempt. =p

Also, I really like the animation for the 6th key.

- Chris

[Lukeonia1]

You know, I KNEW that's what it was going to turn out to be. I was actually worried that we wouldn't have it solved in time.

Spoiler:

I also knew it would be a location that I couldn't possibly get to. The more I look at hotel prices and airfare between Bumpkisville, North Dakota and San Francisco the less feasible this looks. Does anyone in the upper Midwest want to carpool? Gas would only be $400 at 28 MPG, both ways.

And where the hell would you PARK around there?? Halp, I really wanna go!

[aspragg]

I'm a little surprised the brute-force attack on the 6th key didn't work. Any ideas why not?

Now that the whole key was discovered, I was able to create a brute force attack which worked, but it's a lot easier to do once you know what results you want.

[skeptical scientist]

I'm a little surprised the brute-force attack on the 6th key didn't work. Any ideas why not?

Now that the whole key was discovered, I was able to create a brute force attack which worked, but it's a lot easier to do once you know what results you want.

I thought we determined there was a bug in the program? After all it failed to decode a test message also.

[Sentynel]

There was a revised version of the brute force released which I confirmed worked with a test message.

I guess the failure of the brute force is related to the problems I'm having decrypting the text. I'm not sure what's going wrong, so here's a console log:

Spoiler:

Code: Select all

sam@skynet:~/python/xkcd$ openssl aes-256-ecb -d -iv 00000000000000000000000000000000 -K EE98511873CD4542DA101CBC735646B09BE32BE0D0E0C9A6CB4D62AE8662384F -in ciphertext
bad decrypt
16375:error:06065064:digital envelope routines:EVP_DecryptFinal_ex:bad decrypt:evp_enc.c:461:
<3<3<3 2010-06-26 14:28:57 37.76sam@skynet:~/python/xkcd$

Where ciphertext contains, in hex, 772A3A35DEF88CA70BDFD18620B05684934721F8F64762FD03F8D76B3FA0CB8C2756B2D0A9F00A1BCFF1603EDB05426C

I'm not sure if I'm doing anything wrong there (that command works fine for my own tests), but if not whatever's going wrong would also have caused the brute force to fail, as that uses the host computer's openssl library.

[aspragg]

There was a revised version of the brute force released which I confirmed worked with a test message.

I guess the failure of the brute force is related to the problems I'm having decrypting the text. I'm not sure what's going wrong, so here's a console log

For what it's worth, when I did this in C#, I had to specify a particular padding type, or I'd get this error:

"Padding is invalid and cannot be removed."

I had to specify the Padding as PaddingMode.Zeros. Not sure how that translates to openssl, but FYI.

[Sentynel]

For what it's worth, when I did this in C#, I had to specify a particular padding type, or I'd get this error:

"Padding is invalid and cannot be removed."

I had to specify the Padding as PaddingMode.Zeros. Not sure how that translates to openssl, but FYI.

Ah, interesting, if I append a bunch of zeros to the file manually (since I don't know if there's an openssl option for that), I get the complete message out, though I still get the bad decrypt error as well.

Encrypting the plaintext using openssl with the known key gives me this as the encoded text in hex:

Code: Select all

772A3A35DEF88CA70BDFD18620B05684934721F8F64762FD03F8D76B3FA0CB8C2756B2D0A9F00A1BCFF1603EDB05426CC149726DCAB9ACEF5C8C03FD398CD97D

...which is the same as the data in the book, but with an extra sixteen bytes appended. I don't know enough about AES to know what's going on here. As an experiment, I'm just running the brute force on that data, but I'm pretty sure it's going to work.
Edit: Yes, it does.

[danm]

Spoiler:

Where ciphertext contains, in hex, 772A3A35DEF88CA70BDFD18620B05684934721F8F64762FD03F8D76B3FA0CB8C2756B2D0A9F00A1BCFF1603EDB05426C

I'm not sure if I'm doing anything wrong there (that command works fine for my own tests), but if not whatever's going wrong would also have caused the brute force to fail, as that uses the host computer's openssl library.

The source needs to be binary, not hex. It can also be ASCII-armored in base-64 if you use the -a switch. You need to convert it with something like:

echo -n -e $(sed 's/../\\x&/g' ciphertext) >ciphertext2

and then decrypt ciphertext2.

-Dan

[Sentynel]

The source needs to be binary, not hex. It can also be ASCII-armored in base-64 if you use the -a switch. You need to convert it with something like:

echo -n -e $(sed 's/../\\x&/g' ciphertext) >ciphertext2

and then decrypt ciphertext2.

-Dan

Sorry, I should have been clearer; I created the source file by inputting the hex into a hex editor and saving it. It decrypts the first part successfully before hitting the bad decrypt error - see the final line of the code block I posted.

[danm]

I see. Well, the block is short, so you can add 16 null bytes at the end (00000000000000000000000000000000) so the whole thing is decrypted.

Or, if you want it to come out without an error, you can fill it with:

Spoiler:

C149726DCAB9ACEF5C8C03FD398CD97D
I was trying to find if something like this is represented in the coordinates in the comic, but no luck so far.

Thanks,
-Dan

[Sentynel]

Yes, I know, I worked those two out a couple of posts ago. I'm just wondering why aspragg was getting error-free decryption using zero padding and C#, but it errors out for me with zero padding and openssl. I'd assume this was some clever method on Randall's part to defeat brute force attacks without rendering the message illegible, but had the force been written in C# it would have worked.

[danm]

Sorry, I misunderstood.

Spoiler:

The ciphertext doesn't have padding, so you can just add "-nopad" to the command line to get rid of the error.

Apologies if you know all of this, but here's why you're getting the error. Normally padding is mandatory, so the number of bytes in the padding is repetitively added to make the length a multiple of 16 bytes long (if it's already a multiple, a full block of padding is added). OpenSSL can detect if the decryption is successful because it should end with a final number that matches all of the padding bytes.

Spoiler:

Since the encrypted text is exactly 3 blocks long, it decrypts correctly, but it needs a final, decrypted block of "10101010101010101010101010101010" (hex) or 16 padded bytes, so it can check for success. It's not that something tricky was done but rather that the plaintext exactly fills the block. C#'s PaddingMode.Zeros doesn't add padding if it's block-aligned, so it doesn't complain when it hits the end of the ciphertext.

[Sentynel]

Ah, I gotcha. Cheers! =)

[cdehaan]

I'm planning to drive there from London, Ontario. I'm willing to entertain the idea of picking up people who are on the way. I'm debating if North Dakota is; is there anyone else out there also interested? This is where I'm starting from:
This post had objectionable content.

- Chris

[ethan1701]

Posting your home address to a public forum (even of loving, trustworthy XKCD fans) is a bad idea.
I'd suggest you alter the starting point to a public location near your home.

-Ethan

[jestingrabbit]

Posting your home address to a public forum (even of loving, trustworthy XKCD fans) is a bad idea.
I'd suggest you alter the starting point to a public location near your home.

-Ethan

Agreed.

If you guys want to make this a huge meetup there's a whole subforum for that. Moving the discussion there wouldn't be a bad idea imo.

Edit: someone already did.

viewtopic.php?f=16&t=57850

My advice: move meetup discussion to there.

[fireice289]

has anyone looked at page 10110? i cannot claim that i have alot of experiance with binary code and translating the old code reads :
100110001101000

new code(from the book obviously):
0011110000110011
help is appreciated on this as well as a link to where i can learn to do this myself in the future if you know on... sorry that it is not a solution

[danm]

Wow, crazy. Well, There are 16 bits, or two bytes. You can convert them to hexidecimal by grouping them by four bits at a time.

0011 1100 0011 0011

Each position is worth 2^x where x is the position from right (0) to left (3), so each column is worth:

8421

so, 0011 = twos place + ones place = 2+1=3 and 1100 = 8+4=12
in hex, A is 10, B is 11, ... F is 15, so the value is (grouping in pairs):

3C 33

looking those in ASCII, we see he's sending a message of love.

Spoiler:

the ASCII is < 3 (<3) which is also the start of the secret message

[Qaanol]

8. (page 10020) The comic on this page is #240, incase it's connected.

Code: Select all

772A3A35 DEF88CA7  0BDFD186 20B05684  934721F8 F64762FD
03F8D76B 3FA0CB8C  2756B2D0 A9F00A1B  CFF1603E DB05426C

Spoiler:

This is the 256-bit AES cipher referenced in the code on page 11.

That comic holds a special place in Randall's heart, as he explained in the intro (and elsewhere). Also, this code seems to be the focus of several other codes in the book, so it seems important. I'm guessing that deciphering this code, when deciphered, will lead to another meetup or other real-world happening. That could mean there's a time limit on it, but hopefully Randall will have made it far enough in advance that we have some time.

Two things have changed between this comic and the original. The coordinates went from 42.39561 -71.13051 2007 09 23 14 38 00 to 42.39561 -79.13051 2007 09 23 02 38 00, and the conversation on the last panel changed completely. I'm not sure what either of these changes might mean; possibly deciphering the encrypted message might provide some clues.

Unsolved.

Spoiler:

The new time is twelve hours before the original time. The new location is due west of the original location. Putting the two locations into Google maps gives this route which starts in Villenova, NY, and follows I-90 which parallels the Erie canal and then continues across Massachusetts. Google estimates a travel time of 8 hours and 7 minutes.

If we factor in some time to stop for food and so forth, and a desire to arrive early enough so as not to be late, and perhaps get a nap along the way, then giving oneself 12 hours to do an 8 hour drive is reasonable. I would suggest that perhaps our esteemed author made the implied journey between those two coordinates beginning at the earlier time. What exactly does the last panel of the comic in the book say?

Although when I look up what his address is and map the route between what I find for that and the destination, it does not go near the new location. Perhaps I have his address wrong (actually, almost certainly, since it looks like it may be his parents’ address) or perhaps he was not leaving from home. In any case, those are my thoughts.

[danm]

What exactly does the last panel of the comic in the book say?

Code: Select all

. AND THERE WAS     THERE
.  NOBODY THERE?   NEVER IS.

[Sarda]

Man, I'm going to miss this one as well

[itwill]

Wow, that was impressive.

I feel somewhat sad, though, that the actual changed dialog on page 10020 never meant anything but to attract the readers attention; a code hidden in literature would have been interesting. Still, this has been a phenomenal learning experience, and maybe next time, if I can learn this method of thought, and

Spoiler:

the location isn't across the country, I'll be able to join the fun.

Congrats from Florida; I've never seen a forum thread do so much good.

[itwill]

Kudos on solving it, guys! Unfortunately, I'm on the wrong side of the world, but I hope those that can be there have a blast!

Spoiler:

Where? Because if you reverse the longitude, you end up North of Chaoyanggang,in the Sea of Okhost. Who knows? Maybe you could have your own party for the fans in that region?

[Kimmel]

In case you are wondering about the page numbers, I can explain:

Spoiler:

http://en.wikipedia.org/wiki/Ternary_numeral_system

It's in trinary! Yep, that's right! It's just like binary, but as binary is to two, decimal is to three, and hexadecimal is to 16, trinary is to three! Example:

0, 1, 2, 10, 11, 12, 20, 21, 22, 100, 101, 102, 110, 111, 112, 120, 121, 122, 200, 201, 202, 210, 211, 220, 221, 222, 1000

[danm]

In case you are wondering about the page numbers, I can explain:

I thought it was at first, too, but some numbers seem to be skipped, so it's not.

Spoiler:

It's skew binary, as someone mentioned above.
http://en.wikipedia.org/wiki/Skew_binary_number_system

It's useful because the distribution minimizes carries and borrows when adding and subtracting.

[skeptical scientist]

In case you are wondering about the page numbers, I can explain:

Spoiler:

http://en.wikipedia.org/wiki/Ternary_numeral_system

It's in trinary! Yep, that's right! It's just like binary, but as binary is to two, decimal is to three, and hexadecimal is to 16, trinary is to three! Example:

0, 1, 2, 10, 11, 12, 20, 21, 22, 100, 101, 102, 110, 111, 112, 120, 121, 122, 200, 201, 202, 210, 211, 220, 221, 222, 1000

I love it when someone registers for the forums and posts at the top of their lungs (in a five-month-dead thread no less), just to tell us an incorrect answer to a puzzle we already solved.