encrypted pointers, encrypted code and encrypted memory.

[Michael Clark]

Hi Folks,

I guess this is probably appropriate for the security or crypto working groups but I thought it might be worthwhile to promote some public discussion on “encrypting the computer” vs “computing encryption”, the rationale being to add to the pool of methods, whether in formal academic papers or methods and ideas published on mailing lists or short essays.

Background: My particular interest that led me to RISC-V was piqued by the lowRISC project, particularly the work on tagged pointers, as part of self-study investigating security vulnerabilities and mitigations, combined with some cryptography research.

I’m emailing today because of the recent release of arm authenticated pointers which are now in production on iOS 12 devices. I believe the lowRISC work, and a general body of work in this area predates arm’s authenticated pointers. There are several papers that publish well known schemes for in-memory permutations of binary images, control flow integrity via keys in landing pads and many other techniques to thwart modern attacks such as ROP.

I wrote a short essay, possibly inspired in part by the lowRISC project, and previous experiences, reading in cryptography. The essay if high-level, mentions storing keys in the unused address bits of canonical pointers which we all know are presently all zeros or all ones in the conventional canonical pointer scheme. The essay is titled Crypto Binary Translation:

https://github.com/michaeljclark/rv8/blob/master/doc/src/bintrans.md

While I mention Embedded keys in pointers I did not go into details of pointer authentication mechanisms. There however have been several discussions on this list in the past regarding somewhat elaborate pointer encoding schemes as well as control flow integrity schemes that authenticate returns and other indirect calls. i.e. the list serves as a good place for public prior art.

My question is whether anyone has any detailed knowledge of prior art in this area and whether there is enough prior art for authenticated pointers to be part of a non-proprietary open standard. I have a small bibliography of papers in the area of binary translation, librando being one technique I found that was similar in essence to my hypothesis. Applying a random projection from a known ABI and ISA into a set of many incompatible translations (from an exploit payload perspective) from many vectors, and with the potential for hardware assistance.

lowRISC tagged pointers, and some somewhat exotic discussions about pointer protection mechanisms have already been discussed on this list predating arm v8.3 authenticated pointers, within the context of preventing ROP style attacks; where pointers to gadgets are injected onto the stack, escalating to execution of arbitrary text. 

I believe bit shuffling permutations on instruction fetch along with bitflips/xor have been discussed in the context of instruction decode as a morphological transform and these are in the literature. For example there are 2^44 (arbitrary 16-bit packet bit order permutations) * 2^16 (xor bit flip combinations) or 2^60 bits of entropy just in re-projection of the in-memory binary text. If more than one round of a reversible GF2 polynomial transform was applied in decode stage, then the keyspace of decodable instruction text could be widened at the expense of more cycles delay during decode (whose performance could be ameliorated with decoded I$). Keys could be stored in page tables to further increase the number of keys bits required for “external” code to run at any arbitrary address, while still preserving text sharing across processes. This forms a second layer of text morphing from a “Defense in depth” perspective and provides protection of the first line of defense is violated and a ROP-style exploitation is promoted to arbitrary text execution, to get the processor to decode and execute the attackers chosen text. Observation: a RISC ISA with fixed size packets or 16-bits or 32-bits is more amenable to text encryption than bytes.

There have also been discussions about FD-PIC, whereby instead of a having a static relationship between text, rodata, data and bss, (which can be statically analysed) but instead to have these offsets varied. ASLR entropy currently applies to text+rodata+data+bss as a whole, so a leak of a known pointer can not compromise the security of the entire binary, not withstanding brk() heap allocators where leak of pointers with predictable offsets from text can be used to break ASLR and find ROP gadgets. On the contrary FD-PIC separates text+rodata and data+bss so that pointers to known data can no longer be used to break ASLR. malloc implementations that randomise the heap offset vs using brk also add another layer of protection.

In any case, while we’ve all got present day deadlines, ... the future is now ... so to speak. I haven’t made any progress in this area but just noting an interest in published work in this area.

Jim Wilson mentioned the other day about basic block reorder in GCC the and this reminded me of my essay. After becoming more familiar with the RISC-V ABI (or traditional C ABIs) it’s made me aware that to achieve this with traditional tools we would need to preserve a certain amount of relocation metadata. The added metadata could allow runtime linking and profile guided optimisation. Indeed this was a strategy employed in Facebook BOLT (Binary Optmization and Layout) which I must add to a bibliography.

Just curious if anyone is working in this area i.e. applying cryptographic principles to ABIs (beyond Apple), and has any literature they wish to share.

Kerckhoffs’s Principle applies here. i.e. the mechanism must be secure even if it’s implementation details are well-known, and what is crypto if it is not security by obscurity; rather the order of obscurity (> 2^112), the alternate form of the same principle; Shannon’s Maxim. Authenticated pointers are an example of this principle, but if broken, the second stage which requires hardware decode keys would be to prevent arbitrary text execution.

Food for thought.

Michael

[Michael Clark]

Interestingly, I had not seen this until this moment, whether you believe me is another story (I think it is obvious):

https://community.arm.com/processors/b/blog/posts/arm-a-profile-architecture-2018-developments-armv85a

Keys in the page tables (which I mentioned below). Obvious; as many will have been thinking of the same thing. What is the obvious place to put per page keys; page tables, TLBs and BCAM/TCAM like structures such as RISC-V PMP.

There is quite a bit of prior art in this area fortunately (IBM’s 1960’s storage key patents which they keep extending in typical ways e.g. storage keys while standing on one leg with right arm extended). Keys in pointers and PTEs and whatever other vectors one can find with spare bits to stuff keys.

"Armv8.5-A incorporates a new feature called Memory Tagging. When Memory Tagging is in use, a tag is assigned to each memory allocation. All accesses to memory must be made via a pointer with the correct tag."

[Michael Clark]

Ulrich Drepper, Red Hat, 2007; Pointer Encryption, but in hardware.

https://udrepper.livejournal.com/13393.html

I guess the key point is here that folk are buying it.

[Andrew Waterman]

On Tue, Sep 18, 2018 at 11:34 PM 'Michael Clark' via RISC-V ISA Dev
<isa...@groups.riscv.org> wrote:
>
> Ulrich Drepper, Red Hat, 2007; Pointer Encryption, but in hardware.
>
> https://udrepper.livejournal.com/13393.html
>
> I guess the key point is here that folk are buying it.

This is tangential to your original point, but since you brought it
up, I should point out that RISC-V's glibc port (like several others)
does not implement the pointer-mangling scheme this blog post
describes. Implementing it, or something cleverer, would be a good
project for anyone looking to get involved in RISC-V GNU stuff.

> --
> You received this message because you are subscribed to the Google Groups "RISC-V ISA Dev" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to isa-dev+u...@groups.riscv.org.
> To post to this group, send email to isa...@groups.riscv.org.
> Visit this group at https://groups.google.com/a/groups.riscv.org/group/isa-dev/.
> To view this discussion on the web visit https://groups.google.com/a/groups.riscv.org/d/msgid/isa-dev/B81C4556-2FC1-4E46-BE0F-7907671E4400%40mac.com.

[Michael Clark]

On 19/09/2018, at 6:45 PM, Andrew Waterman <and...@sifive.com> wrote:

On Tue, Sep 18, 2018 at 11:34 PM 'Michael Clark' via RISC-V ISA Dev
<isa...@groups.riscv.org> wrote:

Ulrich Drepper, Red Hat, 2007; Pointer Encryption, but in hardware.

https://udrepper.livejournal.com/13393.html

I guess the key point is here that folk are buying it.

This is tangential to your original point, but since you brought it
up, I should point out that RISC-V's glibc port (like several others)
does not implement the pointer-mangling scheme this blog post
describes.  Implementing it, or something cleverer, would be a good
project for anyone looking to get involved in RISC-V GNU stuff.

Agree.

There are many more smaller practical steps forward that we can make towards better security for RISC-V. In some ways it is perhaps easier to add a function in hardware but take a lot more work to standardise it and get it used in firmware and OSes and we’re still working to get PMP tested in QEMU. That said, RISC-V is going to be an important ISA for both research and industrial implementation in this security related area due to its extensible nature. There is also a public interest for protection mechanisms that are a public good like the NIST cryptographic standards and IETF open cryptographic protocols. We are now entering a stage where cryptography is being seen in practice at the ISA Level to protect the computer itself versus data it stores. It’s probably someone more devoted to this area that may come up with practical solutions, but time will tell.

Also tangential and more sw-dev related. We need to improve Linux kernel memory protection on the RISC-V Linux port. I would like to spend time on some generic code for managing page tables like x86 and S390 have in Linux. Someone may beat me to it but I’m working on memory system tests for QEMU and we need some VM protection code that figures out mapping sizes and sets up individual PTEs. Background: S390 and x86 can call an API to set protections on ranges and it does the work to split it into megapages or regular pages. It must need a page allocator hook to get PTE pages and they need to be self-mapped to be written to. If it’s BSD/MIT code it can go into tests, examples, firmware and Linux. I’m on PMP/VM testing/verification for QEMU. The  set_memory API is separate from the standard VM code for page fault mappings, rather it exists to set protection for special ranges where a mix of large pages and regular pages could be used. The open source emulators kind of constrain us towards opening up some of the verification IP. Nobody has told me off yet 😀

e.g. here is the S390 API https://github.com/torvalds/linux/blob/master/arch/s390/include/asm/set_memory.h

arm init code currently futzes with the page tables directly to set the kernel text, rodata and data segment page table protections (last time I looked). We should probably follow S390 because the API looks clean.

Note: my RISC-V mailing list subs are still on my personal email, not my SiFive email, and if they were the normal personal disclaimers apply; it’s implied.

Thanks,

Michael

To view this discussion on the web visit https://groups.google.com/a/groups.riscv.org/d/msgid/isa-dev/CA%2B%2B6G0AOs5AAVz6iUYUu%2BJtdot5Yr8QqaP95acHboD4mGK0QYA%40mail.gmail.com.

[Alex Bradbury]

On 18 September 2018 at 21:43, Michael Clark <michae...@mac.com> wrote:
> Hi Folks,
>
> I guess this is probably appropriate for the security or crypto working
> groups but I thought it might be worthwhile to promote some public
> discussion on “encrypting the computer” vs “computing encryption”, the
> rationale being to add to the pool of methods, whether in formal academic
> papers or methods and ideas published on mailing lists or short essays.
>
> Background: My particular interest that led me to RISC-V was piqued by the
> lowRISC project, particularly the work on tagged pointers, as part of
> self-study investigating security vulnerabilities and mitigations, combined
> with some cryptography research.
>
> I’m emailing today because of the recent release of arm authenticated
> pointers which are now in production on iOS 12 devices. I believe the
> lowRISC work, and a general body of work in this area predates arm’s
> authenticated pointers. There are several papers that publish well known
> schemes for in-memory permutations of binary images, control flow integrity
> via keys in landing pads and many other techniques to thwart modern attacks
> such as ROP.
>
> I wrote a short essay, possibly inspired in part by the lowRISC project, and
> previous experiences, reading in cryptography. The essay if high-level,
> mentions storing keys in the unused address bits of canonical pointers which
> we all know are presently all zeros or all ones in the conventional
> canonical pointer scheme. The essay is titled Crypto Binary Translation:
>
> https://github.com/michaeljclark/rv8/blob/master/doc/src/bintrans.md

Hi Michael, thanks for starting this discussion and sharing your thoughts.

Regarding obfuscating binaries, it would be worth looking at prior
work on "software diversification". This paper seems to provide a good
overview of work in this area
<https://www.ics.uci.edu/~perl/automated_software_diversity.pdf>. As
work like blind ROP shows
<http://www.scs.stanford.edu/brop/bittau-brop.pdf>, attackers may
still be able to extract sufficient information about the binary to
craft a successful exploit even without access to the target
executable. You might also be interested in looking up work on
instruction set randomisation, which attacks the same problem from a
slightly different angle.

For encrypted pointers I think you'd be interested in reading
Cryptographically Enforced Control Flow Integrity
<https://arxiv.org/pdf/1408.1451.pdf>. It notes that with a 48-bit
address space, the remaining 16-bits of a 64-bit pointer could be used
for other metadata. Though I think it only actually uses a single bit
to differentiate function pointers vs return address.

Obviously embedding metadata within pointers isn't a new idea. A
128-bit capability representation was proposed in an MIT tech report
in 2000 (co-authored by Andrew 'bunnie' Huang)
<http://www.ai.mit.edu/projects/aries/Documents/Memos/ARIES-05.pdf>.
It observed that a 64-bit encoding would be practical, using 48-bits
for the address and the other 16-bits to encode bounds information.
This idea was revisited much later with "low-fat pointers"
<http://www.crash-safe.org/assets/fatptr_ccs2013.pdf>. The CHERI
project of course also explores various capability representations.
Dynamic language runtimes also like to exploit unused address bits. As
this bug report shows
<https://bugzilla.mozilla.org/show_bug.cgi?id=1143022> this can lead
to portability issues if there is no kernel co-operation. For a long
time, I've thought it would be neat to have a configurable mask to
control which bits of a virtual address are ignored, and we discussed
this a bit on isa-dev a couple of years ago
<https://groups.google.com/a/groups.riscv.org/d/msg/isa-dev/Pm9mso-urM8/nRsoKBSsDAAJ>.
Cesar Eduardo Barros suggested a modification of the idea that has
less flexibility in hardware, but provides the same interface to the
process by having the kernel set up extra page mappings
<https://groups.google.com/a/groups.riscv.org/d/msg/isa-dev/Pm9mso-urM8/Ji8uLyrCDAAJ>.
I think such a mechanism alongside 1 or more tag bits to mark
integrity of the embedded pointer metadata is an interesting and
potentially powerful combination.

Best,

Alex

[Alex Bradbury]

On 19 September 2018 at 10:31, Alex Bradbury <a...@asbradbury.org> wrote:
> For encrypted pointers I think you'd be interested in reading
> Cryptographically Enforced Control Flow Integrity
> <https://arxiv.org/pdf/1408.1451.pdf>. It notes that with a 48-bit
> address space, the remaining 16-bits of a 64-bit pointer could be used
> for other metadata. Though I think it only actually uses a single bit
> to differentiate function pointers vs return address.

It's not directly related to the ideas you discuss, but this paper
from ISCA this year seems like an interesting idea
<http://www.cs.columbia.edu/~simha/preprint_isca18_REST_memory_safety.pdf>.
I haven't had a chance to step through it in full detail though. The
idea of

Best,

Alex

[Michael Clark]

Thanks for sharing references here on the list. This was indeed the goal. I’m glad you were armed with a sufficient set of pointers. I will most certainly read them...

Regarding obfuscation. I’m principally interested in mechanisms that defer obfuscation, encryption, call it what you will, to runtime. The goals of something like Facebook’s BOLT that does basic block re-ordering for performance optimisation and a crypto-system with block re-ordering as an entropy vector, are somewhat at odds with each from a performance perspective but share similar machinery. The combination of mechanisms, such as CFI and pointer authentication adds to “defense in depth”. By being in a semi-linked state; security mechanisms can be added post-hoc without requiring recompile (L1TF and shadow paging is one example where this would be easy). The reality is that some of the simpler ideas that can be quantified as adding the most protection for the least effort, can be explored first.

As Andrew mentioned, there are various present mitigations in glibc and Linux kernel that remain to be enabled on RISC-V (as they need ISA or ABI specific tuning). I’m sure this will happen quickly as there are many folk interested in the security of the platform: both Linux and IoT.

There is already interesting work that is demonstrated in practice such as the Keystone Project TEE which I believe builds on PMP.

At the moment I’m trying to make sure that the fundamental security mechanisms are all working in QEMU... which has meant time verifying against FPGA (as one of several contributors past and present). Emulation fidelity is improving.

Regards,
Michael