[Cryptography] How to find hidden/undocumented instructions

[Henry Baker]

FYI --

https://raw.githubusercontent.com/xoreaxeaxeax/sandsifter/master/references/domas_breaking_the_x86_isa_wp.pdf

Breaking the x86 ISA

Christopher Domas  xoreaxeaxeax at gmail.com  July 27, 2017

A processor is not a trusted black box for running code; on the
contrary, modern x86 chips are packed full of secret instructions and
hardware bugs.  In this paper, we demonstrate how page fault analysis
and some creative processor fuzzing can be used to exhaustively search
the x86 instruction set and uncover the secrets buried in a chipset. 
The approach has revealed critical x86 hardware glitches, previously
unknown machine instructions, ubiquitous software bugs, and flaws in
enterprise hypervisors.

While the x86 architecture has been around for over 40 years, there
exist no public tools for auditing and validating the processor's
instruction set.  With a history of processor errata, security flaws,
and secret instructions, such introspection tools are necessary for
establishing trust in a computing system built on an x86 platform.
Here, we introduce the first effective technique for auditing the x86
instruction set, through guided fuzzing.  The approach uses a
depth-first instruction search algorithm in conjunction with page
fault analysis to exhaustively enumerate the distinct x86
instructions, while requiring no pre-existing knowledge of the
instruction format.  The generated instructions are executed directly
on an x86 platform, and the results of the execution -- including
observed instruction length and exceptions produced -- are compared
against the expected results from a disassembler.  The technique
reveals a multitude of undocumented instructions in a variety of x86
chips...

Whereas the techniques for finding bugs, secrets, backdoors
in software are well studied and established, similar
techniques for hardware are non-existent.  This is troubling, in
that it is the processor that enforces the security of the system,
and is ultimately the system's most trusted component.  It
seems necessary to stop treating a processor as a trusted black
box for running software...

----
Among other problems, undocumented/hidden instructions cannot be
properly handled by hypervisors & containers & emulators, and so
those tools cannot be used to guarantee safe execution in their
absence.