[Cryptography] How to find hidden/undocumented instructions

[Rui Paulo]

On Aug 27, 2017, at 05:14 AM, Jerry Leichter <leichter at lrw.com> wrote:

The paper has a lot more details including the "page split" technique....
It's amusing to see a very, very old technique recycled for a new purpose.

The "split page" technique figures out the length of a variable-length instruction by aligning it so that, initially, the first byte is on page P, and the next is on page P+1. Page P is mapped; paged P+1 is unmapped (or mapped with no execute access). If you get a page fault, you know the process read past the first byte in decoding the instruction; in that case, you slide the instruction over so that the first two bytes are on P and try again. Otherwise, something other than a page fault occurs - in particular, the "debug fault after every instruction" mode is enabled so the processor will fault after a single full instruction. (There are additional details - some of which are only noted as bugs found i.e., the process specs say the page fault must occur if any bytes of the instruction can't be read, but in some cases on some processors, you get some other fault first.)

Now for some prehistory: Either TOPS-10 or TOPS-20 (or its original version, Tenex) - all operating system for the DEC PDP-10 back in the late 60's/early 70's - was broken into by this technique. There was an OS call that would validate a username and password. The system pre-dated the famous Unix paper that introduced the notion of one-way hashed passwords, so it compared the offered password with the stored password directly. It did the comparison of the values byte by byte, using the offered password in its original memory location, and returning immediately a failure. So you could align the test password with the first byte on page P and the next on P+1. You would get a page fault exactly when the first byte was correct. This turned an exponential search into a linear one.

Those who remember the PDP-10 will realize that this is a description in modern terms. The PDP-10 was a word-oriented machine - 36 bit words, usually packing 6 6-bit per word. There were built-in character manipulation functions that would do things like compare strings character by character. These were very general - strings could have arbitrary lengths and start part way into a word. (You could also specify the character size - the hardware knew, for example, how to skip the unused bit if you packed 5 7-bit ASCII characters in a word.) If a page fault occurred part way through, information about the position that had been reached was saved so the instruction could continue from where it left off after the page fault was resolved.

The final piece of the puzzle: Whichever OS it was allowed the user to provide a page-replacement algorithm. When a page fault occurred, the OS would call back to user mode with the full context of the fault, and the user code could decide what to do next. (Actual assignment of physical pages and manipulation of the virtual-to-physical mapping was still up to the OS, of course.) So a page fault handler could see exactly how far into a string the comparison had gotten.

There were other hacks in that era based on the vulnerability of accessing parameters to system calls directly from user memory (e.g., modifying the value from some kind of parallel thread after the OS had validated it but before it used it). Eventually we learned to immediately copy parameters into system space, and validate and use them from there.

Thanks for this story Jerry.  I forwarded it to the presenter and he was unaware of the same technique being used for password cracking in the past. 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20170830/ff54c84c/attachment.html>