Good morning, Las Vegas! Some genuinely serious hints to finish the #sophospuzzle in time!


Good morning, Las Vegas!

A cheery greeting to everyone attending BlackHat 2013, and an even cheerier greeting to everyone attempting the #sophospuzzle.

As I write this, 19 people have announced they solved the crossword; seven have completed all four stages of the puzzle.

But so far, we haven’t heard much from the BlackHatters.

And time is now of the essence, especially if you will be attending BlackHat sessions today, with or without the deleterious side-effects caused by vendor-sponsored “Nevada-size” glasses of wine yesterday evening.

So here are some genuinely serious hints to help you along.

The bits that read like illiterate Klingon gobbledegook have been rot13ed so you can avoid seeing them if you don’t want spoilers.

Stage 1a: Starting the crossword

There are 22 answers in a 13×13 grid, with two answers that run the full 13-character width.

1 Across: You'll read it if you want to win the prize.

22 Across: Why you are doing this puzzle.

A few people said they struggled to get going, so here are those big answers to kick start your day:



Stage 1b: Finishing the crossword

Maybe you’re stuck on 21 Down: Mad King George was one; Bill Gates is one, too. [4]? (It’s a vocal pun. The answer is a number, at least to a poker player like Bill used to be.)

The crossword JavaScript has a [Check puzzle] button, so it must have some way of working out if you have entered the correct answers, even if it doesn’t know the answers precisely itself.

Perhaps you should look at the source of the HTML page?

Gur vzcbegnag ovg vf guvf:

// Ergheaf n bar-jnl unfu sbe n jbeq.
shapgvba UnfuJbeq(Jbeq)
    ine k = (Jbeq.punePbqrNg(0) * 719) % 1138;
    ine Unfu = 837;
    ine v;
    sbe (v = 1; v <= Jbeq.yratgu; v++)
        Unfu = (Unfu * v + 5 + 
        (Jbeq.punePbqrNg(v - 1) - 64) * k) 
        % 98503;
    erghea Unfu;

Fnqyl, guvf vf n irel onq unfu jvgu ybgf bs pbyyvfvbaf, fb lbh cebonoyl jnag gb fgneg jvgu (be svygre qbja gb) qvpgvbanel jbeqf gb nibvq trggvat ybgf bs tneontr. Grfgvat bayl qvpgvbanel jbeqf jvyy yrg lbh grfg zhpu ybatre cbffvovyvgvrf.

Ba Havk-glcr flfgrzf, ‘nfcryy qhzc znfgre’ tvirf n dhvpx yvfg.

Stage 2a: Decrypting the ZIP

Assuming you didn’t brute force the password to the ZIP with a cracking tool, you will now have the letters of the password but not the case (UPPER or lower) of each.

If you don’t want to type all 64 variations in case of six characters, build the list with a script and test them from the command line using ‘unzip -P password’, e.g.

unzip -P TRY
unzip -P TRy
. . .

Don’t use unzip -P in real life. Passwords on command lines are best avoided, for obvious reasons.

Stage 2b: Making sense of the pseudocode in the ZIP

The code has a loop that keeps doing this:

P = 1 + 1/P

If you try it a bit, you’ll see it seems to converge, with more and more decimal places settling down to a fixed value.

You might want to see whether you can find out more about the number that seems to be emerging. It’s famous, and fascinating, and (right now, if you want that 3D printer) important.

Be lbh pbhyq gel na nyroenvp nccebnpu, nffhzvat va gur yvzvg gung gur nobir nffvtazrag vf npghnyyl n gehr zngurzngvpny rdhngvba.

Vs C = 1 + 1/C, gura:

      C - 1 = 1/C
   C(C - 1) = 1
    C^2 - C = 1
C^2 - C - 1 = 0

Gel fbyivat gur dhnqengvp rdhngvba.

Vs lbh pna’g erzrzore ubj gb fbyir dhnqengvpf, gur nafjre lbh jnag vf gur ynetre bs gur gjb ebbgf, (1+fdeg(5))/2.

Stage 2c: Calculating the answer

The loop calls for one billion iterations. Too many!

Every 2.4 loops gives about one decimal digit, so even using the static formula above needs hundreds of millions of digits. Too many for a regular floating point number.

Look for an arbitrary-precision maths library. There are lots of good ones. As for how many decimal places you really need, that’s determined by the 10**Q part of the code.

We already hinted on that: have a look here.

Bs pbhefr, lbh pbhyq pnyphyngr n srj bs gur qvtvgf, naq hfr n CQS penpxre gb svaq gur erznvavat barf.

(Lbh cebonoyl unir whfg rabhtu gvzr gb hf n CQS penpxre sbe nyy avar qvtvgf. Yrg zr whfg fnl gung V qba’g erpbzzraq gung nccebnpu, jvgubhg fnlvat jul.)

Stage 3a: Understanding the Lua code

It looks like a giant array that gets decrypted, largely because that’s what it is.

At the end of the code is the important part: the decrypted data (in the string ‘p’) is processed with load(p)().

If you are wondering about the final pair of round brackets, all that really matters here is that load(p) is a bit like eval(p) in other scripting languages, except it doesn’t compile and run p, it compiles p and turns it into a Lua function.

Which you can then call, thus the final round brackets to denote a function invocation.

Nygubhtu ybnq() pna pbafhzr cer-pbzcvyrq Yhn olgrpbqr, vg’f hfhnyyl hfrq jvgu fbhepr pbqr. Fb gur inyhr bs c orsber gur ybnq(c) vf bs vagrerfg. Vg’f cebonoyl Yhn fbhepr, nyy va NFPVV.

Lbh pna ercynpr ybnq(c)() jvgu cevag(c) vs lbh jnag gb frr jung pnzr bhg bs gur qrpelcgbe.

Lbh pna hfr c:fho(1,20) gb trg whfg punenpgref 1-20 bs c. (Yhn fgevatf fgneg ng bar, yvxr Nzrevpna tebhaq sybbef, abg mreb, yvxr oveguqnlf.)

Stage 3b: What’s going on in the xit() function?

Remember that multiplying by two is a left-shift by one bit. Shifting and XORing a number bit-by-bit is a characteristic of a well-known sort of algorithm.

Gel frnepuvat sbe gur gjb pbafgnagf va gur shapgvba. Gurl zvtug cebivqr n uvag ba jung guvf vf nobhg.

Stage 3c: I know the keyspace, but the decryptor runs too slowly

Above, we suggested truncating the decrypted output before printing it, if all you wanted was a guideline.

If you can do that, you may as well just shorten the amount you decrypt instead, throwing away the excess before you do the work, not after.

Gur bcrengbe # va Yhn zrnaf ‘gur fvmr bs’, fb #p va sbe v=1,#p zrnaf ‘gur yratgu bs gur ragver neenl p‘.

Gel sbe v=1,5 vafgrnq.

Stage 3d: Do I have to do it all over again?

A few people who cracked e.9 asked that.

Maybe. Maybe not. If you decrypted e.9 you will notice something interesting about what I’ll call e.8. (You should be able to guess what the 9 and 8 imply, if you guess that e means ‘encrypted’.)

Fb lbh pna cebonoyl znxr n tbbq thrff gung r.8 fgnegf jvgu x=?, juvpu zrnaf lbh xabj gur cynvagrkg bs gur svefg gjb olgrf, naq pna erfgevpg gur enatr bs inyhrf sbe gur guveq.

Naq vs lbh KBE gur cynvagrkg jvgu gur pvcregrkg va p[1] (Yhn pbhagf neenlf, yvxr fgevatf, sebz bar, abg mreb), lbh erpbire gur xrl!

Can I really still make it?

The hints above should be enough to get you there in time for the 3.30pm Las Vegas deadline on Thursday 01 August 2013, even without working at the back while you’re in the sessions.

We wouldn’t want to encourage that sort of anti-social behaviour at all.

When you are done, submit your answer to Booth #641 (or by email if you are not at BlackHat) as detailed here.