feature article
Subscribe Now

An Epic Feat of Reverse Engineering

Could You Crack a CPU Design from One Single Program?

“It’s just 1s and 0s. How hard can it be?”

Here’s the ultimate debugging challenge. You’re presented with a string of 20,000 binary bits and told you have to identify it – what it does, how it works, and what machine it’s written for. Unfortunately, you don’t have a disassembler. Or any source code. In fact, you don’t know anything at all about the programming language, instruction set, whether it’s big- or little-endian, or even the word length of the machine. All you get is 1s and 0s. Ready… Go! 

Could you do it? 

If you’re anything like computer science professor Dr. Robert Xiao, you can solve the riddle in about ten hours. This seemingly impossible task was set up as an artificial challenge by Polish security team Dragon Sector to see if anyone could reverse-engineer a custom, completely unknown CPU architecture based on nothing but a single executable binary file. 

The only hints that Xiao and other ambitious challengers got was that the bitstream was a standalone program for a text-adventure game, sort of like the 1970s-era Rogue or Colossal Cave Adventure. Oh, and the processor, which was invented expressly for this challenge and was therefore wholly undocumented, has four registers. Apart from that, you’re on your own. 

As Xiao’s blog details, it was a tedious process, but not without its breakthroughs. A text adventure should have a lot of text, but there’s no point looking for ASCII strings because there’s no guarantee the program uses ASCII encoding. There’s not even any reason to believe it uses 8-bit bytes. 

His first step was somewhat counterintuitive: he dumped the bitstream into a text editor and tried out different line-wrap lengths to eyeball it, hoping to see repeating patterns. Magically, at 20 characters (bits) in width, the 1s and 0s seemed to line up and look less random. There must be a pattern here. Something about the bitstream is divisible by 20. 

Cryptanalysts who crack coded texts often look for patterns or differences in frequency. Certain words, phrases, or letters occur more often than others in human languages. Would the same trick work here? Maybe code loops recur like common phrases. Sure enough, Xiao’s next baby step was to discover a sequence of 425 bits that occurred twice – too long to be coincidental. 

He goes on to describe his method of separating code from data, and to eventually identify opcodes and their operands. But even when you know where the instructions are, that doesn’t tell you anything about what those instructions do. Like Napoleon’s army blowing sand off the Rosetta Stone, you might know you’re looking at writing without having a clue about what it says. 

In the end, Xiao and his debugging partner managed to not only reverse engineer the mystery processor and document the program, but they beat the game without cheating (sort of). You can find their disassembler and the entire game on GitHub

It’s a remarkable feat of debugging and reverse engineering, and it’s both inspiring and discouraging. On the one hand, it shows how resourceful a determined programmer can be, and how tangential skills and techniques can be brought to bear on tough computing problems. 

On the other hand, it makes true system security seem even more impossible. This program was encrypted in a profound way by implementing an imaginary processor with no precedent or documentation. It used 5-bit “bytes” and had its own unique instruction set. Yet a single programmer (with some help) was able to figure it all out in less than a day, with no unusual or expensive tools. Just brains and a deep familiarity with programming, security, and mathematics. If he can crack an unknown CPU, what chance do we have with popular, well-documented machines? “Security through obscurity” got blown apart in a maze of twisty little passages, all alike. 

One thought on “An Epic Feat of Reverse Engineering”

  1. Xiao certainly deserves some serious credit and bragging rights for that one.

    Reverse engineering at this level requires significant experience, that few people ever get a chance to learn.

Leave a Reply

featured blogs
Apr 16, 2021
The Team RF "μWaveRiders" blog series is a showcase for Cadence AWR RF products. Monthly topics will vary between Cadence AWR Design Environment release highlights, feature videos, Cadence... [[ Click on the title to access the full blog on the Cadence Community...
Apr 16, 2021
Spring is in the air and summer is just around the corner. It is time to get out the Old Farmers Almanac and check on the planting schedule as you plan out your garden.  If you are unfamiliar with a Farmers Almanac, it is a publication containing weather forecasts, plantin...
Apr 15, 2021
Explore the history of FPGA prototyping in the SoC design/verification process and learn about HAPS-100, a new prototyping system for complex AI & HPC SoCs. The post Scaling FPGA-Based Prototyping to Meet Verification Demands of Complex SoCs appeared first on From Silic...
Apr 14, 2021
By Simon Favre If you're not using critical area analysis and design for manufacturing to… The post DFM: Still a really good thing to do! appeared first on Design with Calibre....

featured video

The Verification World We Know is About to be Revolutionized

Sponsored by Cadence Design Systems

Designs and software are growing in complexity. With verification, you need the right tool at the right time. Cadence® Palladium® Z2 emulation and Protium™ X2 prototyping dynamic duo address challenges of advanced applications from mobile to consumer and hyperscale computing. With a seamlessly integrated flow, unified debug, common interfaces, and testbench content across the systems, the dynamic duo offers rapid design migration and testing from emulation to prototyping. See them in action.

Click here for more information

featured paper

Understanding the Foundations of Quiescent Current in Linear Power Systems

Sponsored by Texas Instruments

Minimizing power consumption is an important design consideration, especially in battery-powered systems that utilize linear regulators or low-dropout regulators (LDOs). Read this new whitepaper to learn the fundamentals of IQ in linear-power systems, how to predict behavior in dropout conditions, and maintain minimal disturbance during the load transient response.

Click here to download the whitepaper

Featured Chalk Talk

Cloud Computing for Electronic Design (Are We There Yet?)

Sponsored by Cadence Design Systems

When your project is at crunch time, a shortage of server capacity can bring your schedule to a crawl. But, the rest of the year, having a bunch of extra servers sitting around idle can be extremely expensive. Cloud-based EDA lets you have exactly the compute resources you need, when you need them. In this episode of Chalk Talk, Amelia Dalton chats with Craig Johnson of Cadence Design Systems about Cadence’s cloud-based EDA solutions.

More information about the Cadence Cloud Portfolio