[Cryptography] VW/EPA tests as crypto protocols ?

[Henry Baker]

By now, you've all heard of the VW SW that cheats/defeats the EPA testing protocol.

But VW isn't alone, and expect further revelations as the white hats start investigating these types of misbehavin' SW.

So what's a regulator to do?

Recall that error-detecting codes were designed to counteract "random" errors, but are incapable of dealing with intelligent/malicious adversaries.

Similarly, traditional statistical quality control techniques (e.g., "six sigma") were designed to deal with "random" manufacturing errors, and are incapable of dealing with intelligent/malicious saboteurs.

These differences are crystallized by the difference between a traditional random number generator and a crypto-quality random number generator.

We're now in a SW era in which regulators must bless equipment that may have incorporated malware, whether injected by saboteurs or whether injected by the manufacturer itself.

We're in the same position as Apple and Google (Android) in policing their App Stores; we must ensure that none of the apps will misbehave when released into the wild.

This is a very tall order, and in general, it is undecidable -- even when the criteria for "misbehavin'" are rigorously precise, which they aren't.

Many -- most prominently Cory Doctorow and Eben Moglen -- have called for changes to the DMCA to allow for source code inspection.  I predict that some changes will be allowed so that the white hats can challenge this "dark firmware".

But changes to the DMCA won't be sufficient.  Various types of SW obfuscation will make finding such cheats/defeats difficult to find -- e.g., Apple's "goto FAIL" ;-) ;-) bug -- and providing enough incentives for all this white hat code inspection work will be difficult.

But it's even worse still.  Techniques such as "HARES" (split data/instruction caches + encrypted instruction pages) will make even the *examination* of code extremely difficult, while techniques such as nVidia's "DCO" (Dynamic Code Optimization aka JIT compilation) means that examination of code won't tell you *anything*, since the code that *runs* is decided by the JIT compiler itself, with the binary firmware code simply being a "suggestion" about what the executed instructions are supposed to do.

HARES:

http://www.wired.com/2015/02/crypto-trick-makes-software-nearly-impossible-reverse-engineer/

http://blog.jacobtorrey.com/hares-faq

DCO:

https://web.stanford.edu/class/ee380/Abstracts/150304.html

http://youtu.be/oEuXA0_9feM

Since nVidia's DCO technology is being targeted directly at the *automotive* industry, a future VW-wannable can simply instruct the JIT compiler to hide the cheats/defeats in the JIT compiler itself, so that the binary firmware itself is 100% legit.  However, after the JIT compiler runs, the cheat/defeat is installed and/or executed, so that the car fraudulently passes the EPA test.

So whether we want to or not, we're also going to have to deal with *behavioral observation*, since source code inspection won't be sufficient.  (There may also be a number of simpler HW techniques that can be used to modify/mask the malware's behavior when undergoing EPA tests; hopefully, behavioral testing can uncover some of those cases.)

We have to perform a kind of "Turing Test" -- except in reverse: the malware has to correctly guess when it's being EPA-tested so that it behaves correctly, and only misbehave when it feels certain that it's running in the wild.

When the memory available to the malware is limited, the malware's ability to store a chess program-like "book" (e.g., a list of standard EPA testing cycles) is also limited.  In a memory-limited era, the malware didn't have enough memory to memorize all of the EPA testing cycles.

Unfortunately, that era is long gone; modern embedded processors have gigabytes of storage available to memorize 100's of thousands of miles of EPA tests, so producing a test challenging enough to force a VW-wannabe's malware out of its "book" is also extremely difficult.

So the question remains: how to generate a cryptographically secure challenge test that is *indistinguishable* enough from a real-world drive so that the firmware misbehaves a negligible fraction of the time while in the wild?