Retrofit or Redesign? Hardware-Validated Constant-Time Defense and Cost Analysis for the M-Step Side-Channel on TrustZone-M

Imagine you are the guardian of a secret vault, and the only way to open it is by solving a complex math puzzle. In the world of digital security, this puzzle is often a "modular inversion," a calculation used to lock and unlock messages. For years, experts believed that if you made the time it took to solve the puzzle the same every single time, no one could steal the secret. This is called "constant-time" security. The idea was that if a thief couldn't tell if you were thinking hard or just guessing based on how long the door took to open, they were safe.

But there's a sneaky new trick called a "single-stepping attack." Imagine a thief who doesn't just wait for the door to open; they have a magical stopwatch that lets them freeze time after every single step of your puzzle-solving process. They can watch exactly which path you take through the maze. If your maze has secret shortcuts that you only take when you know the answer, the thief sees you take the shortcut and learns your secret. This paper explores a high-stakes choice for security engineers: when a vulnerability is found, should you try to patch the old, leaky maze to make it look uniform (a "retrofit"), or should you tear it down and build a brand-new maze that has no shortcuts by design (a "redesign")? The answer isn't just about which is faster; it's about which one actually stops the thief from seeing your secrets.

---

The Great Maze Patch: Retrofit vs. Redesign

In this study, researchers Arash Razban and his team tackled a real-world security hole (known as CVE-2025-54764) found in a popular library used to protect data on small, embedded computers like those in smart cards or medical devices. The hole was in the "binary GCD" and "modular inversion" routines—basically, the math engines that handle secret keys. A hacker using a technique called "M-Step" could freeze the computer after every single instruction and watch the path the math took to steal the secret key.

The researchers set up a head-to-head battle on real silicon hardware (a Cortex-M33 chip) to see which defense strategy worked better: The Retrofit or The Redesign.

The Retrofit (The Patch Job):
The team tried to fix the old, leaky math routines. They took the original code, which had secret-dependent shortcuts (like a maze with hidden doors), and forced it to walk the same path every time. They did this by making the code run through every possible step, even the ones it didn't need, and using "branchless" tricks to hide which path was actually taken. It was like forcing a runner to jog through every single room in a house, regardless of where the exit is, so an observer can't tell which room they actually left from.

The Redesign (The New Build):
The alternative was to throw away the old math entirely and replace it with a brand-new algorithm (called safegcd) that was built from the ground up to have no shortcuts. This new maze has a fixed path that looks exactly the same no matter what the secret is.

The Shocking Results: Speed and Sneaky Leaks

The researchers measured two things: how much it cost (in time and energy) to run these defenses, and whether they actually stopped the thief.

1. The Cost of the Patch
The results were staggering. The "Redesign" was incredibly efficient. However, the "Retrofit" was a disaster in terms of speed.

• For the GCD routine, the retrofit was 192 times slower than the redesign.
• For the modular inversion, the retrofit was 532 times slower.

To put this in perspective, on the hardware they tested, the redesigned routine took milliseconds to run. The retrofitted routine? It took seconds. Specifically, the retrofitted GCD took about 4.5 seconds per call, and the modular inversion took a whopping 25 seconds. For a device that needs to unlock a door or sign a message instantly, waiting 25 seconds is practically useless. The redesign was not just better; it was the only option that made the device usable.

2. The "Ghost" Leak
Here is where the story gets really interesting. The researchers thought the Retrofit was a success. When they measured the total time it took to run, the Retrofit looked perfect. The time varied by less than 2% between different secrets, which is usually considered "safe."

But then, they used a super-precise tool to check the exact instructions the computer executed, step-by-step. They found a "ghost leak."

• In the Retrofit, there was a tiny, hidden loop at the very end of the math process. For most inputs, it ran a fixed number of times. But for one specific secret, it ran one extra time.
• This extra step added only a few dozen clock cycles to the total time. Because the total time was so huge (billions of cycles), this tiny difference was completely invisible to standard timing tests. It was like a thief noticing a single extra blink of an eye in a 25-second movie.
• The M-Step attacker, who watches every single step, would have seen this extra blink and known exactly what the secret was.
• The researchers had to go back and fix this tiny loop, replacing it with a fixed sequence, to truly close the door.

The Verdict: Build New, Don't Patch

The paper concludes with a clear message for security engineers: Do not try to patch these specific types of math routines.

1. Redesign is King: The "constant-time-by-design" approach (the Redesign) is vastly superior. It is roughly two orders of magnitude (100 times) faster than trying to patch the old code.
2. Timing Tests Lie: You cannot trust standard timing tests to tell you if a patch is safe. A patch can look perfect on a stopwatch but still have a tiny, exploitable leak that only a "single-stepping" attacker can see.
3. Check the Steps, Not the Clock: To be sure a defense works, you must verify the exact sequence of instructions (the path taken), not just the total time it took.

The researchers found that even after fixing the ghost leak, a tiny amount of time variation remained (about 2%). However, they proved this wasn't a secret leak; it was just the hardware itself behaving slightly differently depending on the numbers it was crunching, a "hardware floor" that even the best software can't eliminate. But crucially, the path the computer took was now identical every time, meaning the thief could no longer learn the secret by watching the steps.

In short: When it comes to these critical math secrets, don't try to patch the old house. Tear it down and build a new one that was designed to be secure from the start. It's faster, safer, and you won't miss the tiny cracks that a patch leaves behind.