I recently participated in Samsung’s Hacker’s Playground CTF with Wreck The Line. We finished with 1592 points, in 26th place of 1075 teams. Most of my time was spent on Legonigma, an interesting 500 point challenge based on two renders of a Lego cryptography gadget.

The Challenge

Decipher ciphertext: 59x8wl9pjsava3grn0il79aoq307f20a6huc3xnos289cd8xv1fn2znuoa2bq8959chbktwfow8c3azpvo3c59jz4

First Impressions

Cool!

I had a limited selection of possible parts, assuming it was built with production Lego pieces. The only moving parts were gears and a differential, so I suspected the relationships between input and outputs were just a series of ratios.

Why were there three outputs? Maybe it produced 3 ciphertext characters per plaintext character? No, the ciphertext was 89 characters total, which isn’t divisible by 3… I must need to guess the order?

Pieces in Play

Using the images and information from a blog post about Lego gears I listed the pieces I might face, by type, tooth count, and features:

• Regular gears (no bevel)
  • 8 (axle)
  • 16 (axle and small spaces)
  • 24 (axle and four round post holes)
  • 40 (axle and a bunch of axle and post holes)
• Double Bevel
  • 12 (axle)
  • 20 (axle, spaces)
  • 28 (axle and four post holes)
  • 36 (axle plus two posts and two axles)
• Differential
  • Three identical single-bevel inside, so ratios don’t matter
  • Outside: 16 and 24 tooth

Attempt One: Procedural

My first instinct was to follow the gearing through, noting each number of teeth:

36 (input, green)
hard link to 20 (grey)
rotates 12 (blue)
rotates 20 (grey)
splits to A

A1:
rotates 12 (blue)
hard link to 36 (grey)
rotates 12 (blue)
hard link to 36 (yellow, out1)

A2:
hard link to 28 (blue)
...

I intended to turn this into a simple procedure that would just do the math for each step, keeping track of the angle of each gear, but I realized there’s a much easier way to simplify it…

Attempt Two: Mathematical

If I pretend I’ve turned the input one full rotation clockwise, how does each gear – and therefore each output – behave?

input 1 CW
grey 1 CW
blue (irrelevant) CCW
grey 1 CW (split A)

A1 (left):
blue 20/12=5/3 CCW
grey 5/3 CCW
blue 5 CW
yellow 5 CW (out1)

A2:
blue (irrelevant) CCW
grey 1 CW
blue 20/12=5/3 CCW (split B)

...

Following this through, I arrived at the following ratios between input and output:

• 1:5 for the front left output
• 1:5/3 for the front right output
• 1:38/9 for the rear output

Having made up simple ciphers in the past, after finding the 1:5 output I was kind of expecting the others to also be prime numbers. Oh well, the math doesn’t lie… Right?

But after writing some python code to show outputs for every possible first couple characters of input, I couldn’t get the outputs to match the ciphertext. Notably, for lots of valid inputs, the rear and right-side outputs sat between letters. Unless this machine would be provided to users with specific instructions, that seemed odd.

I spent a long time chasing guesses about what those instructions might be - “Keep turning until the outputs are all exactly at a tooth/letter”? “Keep turning until the one output for this step is exactly at a tooth/letter”? After some rubber duck debugging and a gentle nudge from the challenge author, I re-examined my understanding of the machine, but still couldn’t find anything wrong.

The Nuclear Option

If I couldn’t logic it out, I’d try to rebuild the device’s mechanics using a tool.

There were several relatively simple tools for Lego gear ratios, but besides them being a bit difficult to build a complex machine in, it didn’t seem they would be able to handle the differential, or possibly even the splits.

I ended up finding the Technic Brick Power Gearing Ratio Calculator, which seemed to do exactly what I needed! …when provided with a “Lego Technic .ldr file”. Okay, it seems I need to use something like LeoCAD to build that…

A lot of twiddling and building later, I had reproduced the machine:

But when I loaded it into the gearing ratio tool, attaching a motor, and running it, the entire model turned red, indicating a jammed motor.

I assumed the tool just didn’t know how to handle the differential, and removed the gear before the rear output to let both sides of that branch run separately, then combined the adjacent gears’ motion myself. The results matched my original calculations perfectly, and I was lost again.

After many more lines of code and attempts to figure out how the machine would be used, I eventually arrived at a realization: In a row of three gears, turning the first clockwise at 1 RPM and the third clockwise at 2 RPM does not cause the middle one to rotate counterclockwise at 3 RPM. Don’t ask how I had arrived at my original understanding – I do not know, and it is as obviously wrong in retrospect as it is to you. The resulting conclusion was that the branch through the front-right output and the differential was not modifying the ratio of the rear output. The simulation was correct. My understanding of the machine actually was a deadlock.

I stared at the challenge’s renders more, and eventually found the problem: There was in fact no motion going through the front-right output’s axle, and the direction of control through the differential is the opposite of what I thought.

See it? I sure didn’t.

After some logic, some trial-and error, and a lot of staring at close-ups of small details in the original render, I moved a few elements around. Here’s a bottom view of the change, with the front-right output gear at the top center:

Then I loaded the amended model into the simulator:

And got some much nicer ratios for the outputs…

So I updated my code to use these much more reasonable ratios, aaaaand… No valid input produced an output matching the first three characters of ciphertext.

Reaching further

Lacking any idea how the outputs were meant to be read, I figured it was time to investigate the challenge name’s call-out to the German Enigma machine to look for hints.

Enigma

• Known-plaintext attack
• Not ECB (advances rotors by each character)
• Random mapping in each code wheel and on plugboard
• Never encrypted a letter to itself
• Decryption == encryption (if a->r, r->a)
• Key is rotor selection, rotor position, reflector position, plugboard config

This machine

• No known-plaintext available
• ECB (all rotors end up back at A when input is rotated back to A)
• Probably not enough ciphertext to do statistics for random mappings
• Encrypts A to A,A,A
• How to decrypt, besides “turn input til all three outputs match your ciphertext block”?
• If there’s a key, how is it configured? 4 pointer positions * 4 rotors * 6 output rotor orders = 96 possibilities?

Maybe I was missing an instruction like “Advance the input by n teeth, where n is the index of the next plaintext character”? I couldn’t figure out how to turn the three outputs into a ciphertext.

Feeling Dumb (Again)

There’s no galaxy brain instructions, I just needed read the outputs in a particular order, trivially discovered. 1:13 first, then 1:5, then 1:7.

I achieved the second solve for Legonigma, for 460 points, 17 minutes after the first team. SCTF{th3w0rld1sadang3rou5placeno7becau5e0fth0sewh0do3v1lbutbecau5eofth053wh0l00konandd0n0th1ng} (“The world is a dangerous place, not because of those who do evil, but because of those who look on and do nothing”)

Conclusion

I wish the ratios hadn’t been whole numbers, so the “no reversing” instruction meant something!

Thanks to “Your expectations are reasonable” Cybrosis for a really neat challenge and a couple nudges, rebuilding the machine was fun. Thanks also to Samsung for organizing this event, and my teammates at WreckTheLine for all of their work and for putting up with my rubber ducking.

Downloads

My Python code, including a lot of commented-out wrong attempts, and overbuilt since I originally expected one full input rotation to not return to the starting state: legonigma.py

The .ldr model of the machine I built in LeoCAD: legonigma.ldr