# How to Hide Secrets from Operating System: Architecture Level Support for Dynamic Address Trace Obfuscation Page: 4

This
**report**
is part of the collection entitled:
UNT Scholarly Works and
was provided to Digital Library
by the UNT College of Engineering.

#### Extracted Text

The following text was automatically extracted from the image on this page using optical character recognition software:

objects are linked from the protected program, we will need to

transfer significant amount of dynamic linker responsibilities

to the VM blackbox. Moreover, the binary format such as

ELF would have to be modified not to keep such relevant

information in plaintext. This will lead into yet another prob-

lem. The dynamic linking sections of the ELF file for the

protected linking program can be securely encrypted by the

compiler used by the software producer. Which key should

be used for this encryption? This leads into the same "last

mile" issue faced by XOM and AEGIS. The initial handover

of the program is done by the software vendor encrypting

the program with respect to an advertised public key for

the processor chip. Hence, the software is specialized on a

per processor chip basis before distribution, which can be an

undesirable characteristic. For the time being, we have chosen

not to address this issue.

Similarly, if linked objects also needed to be protected, VM

blackbox will need to undertake many of the dynamic linker

activities. For the time being, DRMAr does not address the

issue of migrating dynamic linking into the VM blackbox.

D. Virtual Address Translation

This is the heart of the VM blackbox responsibilities. This

includes the virtual to physical address translation of TLB and

much more. Program loading is one of these activities. We

could let the OS interact with VM blackbox with a primitive

such as VM_l1d A, size which signifies loading of virtual

addresses from the virtual address A to A+ size. If we merely

have the VM blackbox return the physical address mapping

of the virtual addresses [A : A + size], the OS can infer the

entire mapping. Hence the actual storing of the program/data

at these virtual addresses needs to be performed by the VM

blackbox. Hence the VM_ld file, A, size can specify

that the next size bytes from file be loaded at virtual

addresses [A : A + size]. Note that the argument file is

really a proxy for a system program with a pointer to the

current location in the file so that VM blackbox can ask it to

provide the next size bytes from this file.

If the size is a small value (say 32 B), the OS can observe

the memory bus traffic and with some effort, reconstitute the

virtual to physical address mapping. Hence, we need some

type of "shelter" or "dummy" word storage of Goldreich &

Ostrovsky [11] to build up the combinatorial choices of the

mapping. We propose to do the load on the page granularity,

i.e., VM_ld file, virtual_page will load a virtual page

into memory. Our assumption is that a typical page is about

64KB (if necessary such a restriction can be placed on the

OS).

Let a virtual address A correspond to the block #B(A) in the

virtual page number V(A). The VM black box will randomly

permute the block B(A) into block fR(B(A)) through the use

of block address translation reconfigurable logic.

a) Reconfigurable Block Address Translation Logic:

Note that the objective is to permute the blocks within a page.

However, we wish the permutation to be different for each

page. This is so that the adversary cannot gain informationmonotonically over time by observing the memory traffic.

Reconfigurable logic provides a good platform for such "soft"

random functions. Figure 1 shows the schema for the reconfig-

urable random permutation function logic. This schema shows

a permutation of 12 bits. With 64KB page size and 16B block

size, one needs to permute the 12 address bits corresponding

to the block number within a page.

Note that fR(B(A)) needs to be a bijective function: both

injective and onto. Hence, we cannot choose an arbitrary

FPGA like structure and populate it with a randomly selected

configuration. This could result in non-bijective mappings.

Each column in the schema of Figure 1 consists of 4-LUT

(4-input lookup table). However, We wish to implement only

reversible (conservative) gates [7], [3] within these LUTs. A

conservative/reversible gate does not lose any information in

going from its inputs to outputs. We should be able to tell the

input values uniquely by observing the output bits of such a

gate. Obviously, a 2-input AND gate is not reversible (since

on output 0 we cannot tell whether it was input 00, 01 or 10).

In general, a reversible gate needs to have as many inputs as

outputs. Hence, we need 4x16 LUTs (truth tables on 4 inputs

specifying 4 output bits simultaneously). For instance a 2-input

gate with 2 inputs X and Y and 2 outputs X and X e Y

is a reversible gate. The intuition behind using reversible

gates is that since each reversible gate defines a bijection, a

composition of these reversible gates will automatically result

in larger bijections.

Both Fredkin [7] and Toffoli [18] have defined classes of

reversible gates.

Definition 1 (Toffoli, 1980): Toffoli gate

Toffoli(n, n) (C, T) is defined over a support set

{x1, x2, ..., xn} as follows. Let the control

set C = {x1, xi2 ..., xi } and the target set

T - {xz} be such that C n T - . The mapping

is given by Toffoli(n, n)(C, T) [x1, x2,..., x]

[X1, X2,..., xj-1, xj i (xi2 ...ix ), Xj+ 1 ", n]. ]

A Fredkin gate is defined similarly:

Definition 2 (Fredkin, Toffoli, 1982): Fredkin gate

Fredkin(n, n) (C, T) is defined over a support

set {x , X2, ..., xn} as follows. Let the control

set C = {x1, xi2 ..., xi } and the target set

T - {xz, x1} be such that Cn T - . The mapping

is given by Fredkin(n,n)(C,T)[xz, x2,..., x]

[X1, X2,.. ., xj-1, l, Xj+l, ..., Xl-1, j , ..., xn] iff

xi A 2 ...A x - 1. In other words, target bits are

switched iff the control bits are all 1.

For the time being, we use Toffoli(4,4) gates with 4-

input bits and 4-output bits in Figure 1. However, we could

easily replace them by Fredkin(4,4) gates. The domain of

configurations mappable to each of these LUTs consists of

selections of sets T and C such that Tn C - 0. For a support

set of 4 variables, the number of unique reversible Toffoli

functions is 3 ( )+ 2 2 )+ 3 ). First term

captures the control sets C of size 1, the second one of size

2 and the third one of size 3. We will ignore control sets

## Upcoming Pages

Here’s what’s next.

## Search Inside

This report can be searched. **Note: **Results may vary based on the legibility of text within the document.

## Tools / Downloads

Get a copy of this page or view the extracted text.

## Citing and Sharing

Basic information for referencing this web page. We also provide extended guidance on usage rights, references, copying or embedding.

### Reference the current page of this Report.

Gomathisankaran, Mahadevan & Tyagi, Akhilesh. How to Hide Secrets from Operating System: Architecture Level Support for Dynamic Address Trace Obfuscation, report, 2004; (https://digital.library.unt.edu/ark:/67531/metadc94282/m1/4/: accessed March 21, 2019), University of North Texas Libraries, Digital Library, https://digital.library.unt.edu; crediting UNT College of Engineering.