[bem94]

>> "several million" undocumented instructions.. is that right?

Bear in mind that doesnt really mean that there are several million operations / opcode mnemonics which are undocumented but each distinct instructions.

It is more likely they are "loose" decodings of other instructions, where changing a single bit of the opcode still causes the CPU to decode the same instruction.

Toy example: If I encode my (imaginary ISA) 8bit instruction for "ADD EAX EBX" as 0101_X000 where X is "don't care" then regardless of whether the core gets 0101_0000 or 0101_1000 , it will still execute the ADD instruction.

Now imagine your instructions can be upto 16 bytes long, and you see how loose decoding can lead to a lot of instructions which are undocumented, but that the processor is perfectly happy to execute.

[SilasX]

Correct me if I'm horribly misunderstanding [1], but isn't there a more general point here?

A CPU is, at root, a massive Boolean circuit wrapped in a flip-flop and some persisted state. The binary [sequence corresponding to an] opcode is just an input that determines which inputs go where.

Thus, for an n-bit opcode width, there are 2^n valid opcodes. Only m of them will correspond to intelligible, "I might want to use that some day" instructions. (Others, as you note, will be functionally equivalent versions of the m and ignorable as well.)

And so you will have 2^n - m "undocumented opcodes".

[1] based on reading NAND to Tetris

[thethirdone]

> And so you will have 2^n - m "undocumented opcodes".

Not quite, there will be 2^n - m possible opcodes, but not all of them will have functionality attached. Many may end up being illegal.

So you could have a processor with m=400 and n=16, but no valid opcodes besides the 400. All 2^16 - 400, could throw an Illegal instruction exception.

[SilasX]

So I must have some big misunderstanding then -- in what sense can a different binary input to a boolean circuit throw an illegal exception? How does the concept make sense at that level?

[muricula]

Processors have "traps" or "exceptions" which work kind of like interrupts. They are utterly unlike exceptions in say C++. They transfer control to another location you specify in an interrupt table. The most well known of these is the "page fault" which occurs when you write/read/fetch from memory you're not allowed to.

Say you have a userland process which dereferences a NULL pointer in C. In the CPUs page table the NULL virtual address is not mapped to a physical address, so a page fault occurs. Control transfers to the OS page fault handler which then delivers the SIGSEGV signal to the process.

There's also a division by zero exception, and several more. You can read more about them here: http://wiki.osdev.org/Exceptions

[SilasX]

That much makes sense, but the original framing of the opcode as illegal still comes off as a category error to me (though perhaps that phrasing is common and excepted). The opcode itself isn't illegal, as opcodes are a CPU-level concept, where nothing is illegal.

Rather, the opcode may bring the memory state to something that might violate some OS's security model. But the opcode still does something to the CPU (Boolean) circuit state.

[sand500]

You could think of it as a switch case statement where the valid opcodes are the cases and there is a default that catches all non defined opcodes and throws an error. Its illegal in the sense you should never expect to run an instruction with those opcodes.

[hellbanner]

Thanks. The scale is still hard to wrap my head around but I see what you're saying.

Could this tool find hardware backdoors?

[duskwuff]

> Could this tool find hardware backdoors?

Only very crude ones. A competently implemented hardwre backdoor would probably be data-dependent. For instance, it might trigger when REP CPUID is called with four specific 64-bit values in R8, R9, R10, and R11 -- and if that were the case, there would be absolutely no way to discover it by searching.

[teeray]

There's also the fascinating variant where a control line charges a capacitor over time to activate backdoor behavior. Triggering it would look like a bunch of nonsense instructions that just so happen to keep that control line energized long enough for the capacitor to cross some activation voltage.

[hellbanner]

No way to discover because of the immense search space? And/Or that if the backdoor was triggered, no way to immediately detect its effects?

[bem94]

I guess that if there was a special "Open backdoor" instruction which was undocumented, then yes I guess it could find it.

Backdoors tend to be separate systems which pry into something larger though (like the intel managment engine being a small, separate core which probes the main system). This means you normally need other means of access to the system other than the standard instruction sequence. Again, the IME needed network access to be abused I think, rather than instructions running on the main processor itself.

Implementing backdoors is stupid. Opening / accessing them with an undocumented instruction is moronic, but distressingly possible.

[wolfgke]

I would rather assume that the backdoor can be accessed via some at least a little bit documented opcode, such as setting some value in an MSR (model specific register) or let some instruction do interesting side effects on some obscure preconditions, such as if the registers are filled with specific values, the instruction will do something completely different.