RSA 2012 #sophospuzzle

Came across this puzzle today at

http://nakedsecurity.sophos.com/2012/02/27/take-on-the-rsa-2012-sophospuzzle-and-win-a-nerf-gun/?utm_source=feedburner&utm_medium=feed&utm_campaign=Feed:+nakedsecurity+(Naked+Security+-+Sophos)

It looks like an interesting problem. The first step is to copy and paste the c program into a text editor:

#include~!int~putchar(int~c);char~*m="noncen.cmh/alu/puyxs.hrhb\xd\xa";void~main(int~argc,char~**argv){if(argc>1&&strlen(argv[1])==8){int~i=0;while(*m){putchar(*m+(*m<0x41?0:argv[1][(++i>8?i=1:i)-1]-0x61));m++;};};}

After some minor twisting, it can be compiled successfully. It accepts input with length of eight. Let's try abcdefgh, the output is nppfis.ith/bnx/tzs.itkf

Let's take a close look at the source code, it looks like a simple encoding between command line parameter and a constant string "noncen.cmh/alu/puyxs.hrhb\xd\xa". Any character with ASCII value less than 0x41 will be unchanged. The list should include "./". Since the puzzle is from sophos.com. The best guess is that noncen.cmh will be encoded as "sophos.com". A couple of trials shows that this is the right path. Here is the so-called password:

./test2 facfkfac

sophos.com/anz/zzyzx.html

The instructions for the second step comes from http://www.sophos.com/anz/zzyzx.html

The DECODEME fashion test

Take the text of an RFC - call it RFC x. Append the eight-character password from the previous stage of the puzzle. Append the text of some other RFC - call it RFC y. (For what it's worth, x and y are different.)

The data lump you've just created will have this MD5:

01b9e8adf4dd660c7e4cb6dd8a304691

Now, compute the product of x and y, and find the smallest integer greater than xy which has exactly two prime factors.

Email the larger of these prime factors to:

duck@sophos.com

before 3pm San Francisco time on Thursday 01 March 2012. (That's 2012-03-01T15:00-5.)

You will be entered in a draw to win a NERF N-STRIKE Vulcan EBF-25.

If you are at the RSA 2012 conference, you have extra chances to win! Wear the puzzle shirt and be on the Sophos booth (#1817) at 2.10pm on Tuesday, Wednesday and Thursday. For further details, check out Naked Security.

You can follow Paul Ducklin and the puzzle on Twitter. Look for the hashtag #sophospuzzle.

Of course, you can also stop by the Sophos Booth (#1817) whenever you like to ask for advice. You never know – you might catch one of us in an unguarded moment.

The problem is to find two RFCs which contents combined with the password (facfkfac) generate a md5 hash value of (01b9e8adf4dd660c7e4cb6dd8a304691). How many RFCs are there? According to http://www.rfc-editor.org/rfc-index2.html, there are 6557 RFCs. Let's download them to local machine using Curl.

curl -o "rfc#1.txt" http://www.ietf.org/rfc/rfc[1-6557].txt

Next, a python script is created to calculate md5 sum from rfcx.txt+password+rfcy.txt. The script stops when a match is found. However, this approached turned out non-working. There are no matching MD5 found. The only explanation is that those RFC text are not exactly same as those used by puzzle creator. Another approach is tried, all RFC texts can be downloaded from ftp://ftp.rfc-editor.org/in-notes/tar/RFC-all.zip

A quick comparison between rfc1.txt from two approaches shows: rfc1.txt from curl has length of 21088 with md5 hash (99c9bdf9b63044f27de4fa8ac8ccba38). However, rfc1.txt from ftp approach has length of 21707 with md5 hash (ee350c347a17f0b46564c113667be323).

The same python script runs against new rfc text files and a match is found:

6533

6532

6531

6530

6529

6528

*****Matched***** (6528, 6533) => 01b9e8adf4dd660c7e4cb6dd8a304691

Bingo! Now, we have two numbers 6528 and 6533. Their product is 42647424. The last hurdle is to find the smallest number which is bigger and have only two prime factors.

Google search found a decent solution at http://stackoverflow.com/questions/171765/what-is-the-best-way-to-get-all-the-divisors-of-a-number

A simple modification turns out the magic number is

42647426

[1, 2, 21323713, 42647426]

The larger prime factor is 21323713. Puzzle solved. Now, it is time for a NERF Gun which I do not think that I have any chance.

Lesson learned:

It is better practice to open files using binary mode for calculation of md5 hash. Different hashes are generated for text mode and binary mode.