Nick P • June 20, 2014 5:00 PM

Crafting a Usable Microkernel, Processor, and I/O System
with Strict and Provable Information Flow Security (2011) Tiwari et al

http://users.ece.utexas.edu/~tiwari/pubs/ISCA-11-starlogic.pdf

A very interesting piece of work combining many good ideas. This would be the “clean slate” version of the separation kernel paradigm. That paradigm, which I pushed here much in the past, was about minimizing the TCB while decomposing a system into partitions with strict enforcement of CPU time, memory allocation, I/O access, and message passing. Aside from integrating that, this work tries to do for hardware what microkernels and TCB concept do for software. Excellent and worthy of further research.

Note: The team behind this also did the work on the PHANTOM Oblivious Computation scheme and the more recent Sapper hardware security policy enforcement scheme.

Nick P • June 22, 2014 6:47 PM

@ Andrew Wallace

re blog style

The standards that failed to protect us were created by meetings of acknowledged expert minds along with some bureaucrats. This blog has produced much stronger technical, psychological and other measures for security. It also has a very diverse array of other content with many perspectives. Quite a treasure trove of information going back years that few other blogs compare to. The acknowledged experts contributed a significant portion, but so did people nobody saw coming (myself included). I always judge a thing by its results. The results tell me the blog is best the way it is.

I have considered building a forum dedicated to high assurance systems. These would include assurance in correctness, reliability, and/or security. The topics would range from hardware to software tools to economic incentives. Only people who have contributed something to the fields would be allowed to post. I’d probably do that through looking at work in academia, business, open source, etc. Referrals would be used, too. I’d probably copy the moderation approach used here, along with letting thread creators moderate their own threads so long as discussion isn’t stifled. The board might be opened to the public for reading, although private threads/messaging would be available. It would also serve as a subversion resistant repository of software, designs, documentation and so on. It would cost a small monthly or yearly fee with waivers available where reasonable. The project is a bit too big to manage for me right now but I’m posting it here in case it inspires someone else to do it.

re anti-government commenters

The interesting thing about that is that consumer crypto got started through those types. Groups of geeks with libertarian type ideas, such as Cypherpunks, started creating many ways to be private and anonymous on the Internet. They did this because they didn’t want to trust the government to respect their freedoms. The theory is that an architecture with less trust is always superior. (eg PGP vs Lavabit) The ideas dispersed to the point that people of many mindsets are involved today.

I’m actually not seeing the current reactions as anti-government. There’s been a few posts of that nature. Most of it, though, is aimed at a government that serves its own interests, has little to no accountability, and mistreats/deceives its people. These are specific governments doing specific types of abuse. Some people want more accountability, some want punishments, some want certain programs gone entirely due to understandable distrust, and a few hate government in general. We also have to remember what the TLA’s have been doing to motivate this attitude. That conspiracy nuts were more on the mark than the average American about what was happening says a lot.

Personally, I’m for a government with strong accountability to the point of prison sentences (that actually happen) for instances of corruption. Otherwise, corruption takes over and the government is essentially a mob representing elite’s interests. The U.S. government, for instance, mostly backs the interests of a priveleged few while harming most of its citizens and many in foreign countries. Certain groups in it also won’t hesitate to kidnap, torture, or murder their opponents. People opposing that kind of government makes a ton of sense. I’m opposed. I think we can do much better as a republic.

@ Moderator

“(2) it doesn’t make sense if taken out of the context of this website”

That’s a clever idea. I’m going to try to remember to see if anyone in security field is working on schemes just like that. Someone has to be. There’s probably a scheme waiting to be found that uses the principle while being as simple and low-admin-overhead as a CAPTCHA .

Nick P • June 23, 2014 12:07 PM

Time for more papers. Todays topic is obfuscation of operation at the chip level.

Arc3D: A 3D Obfuscation Architecture (2005)

Abstract: “In DRM domain, the adversary has complete control of the computing node – supervisory privileges along with full physical as well as architectural object observational capabilities. Thus robust obfuscation is impossible to achieve with the existing software only solutions. In this paper, we develop architecture level support for obfuscation with the help of well known cryptographic methods. The three protected dimensions of this architecture Arc3D are address sequencing, contents associated with an address, and the temporal reuse of address sequences such as loops. Such an obfuscation makes the detection of good tampering points infinitesimally likely providing tamper resistance. With the use of already known software distribution model of ABYSS and XOM, we can also ensure copy protection. This results in a complete DRM architecture to provide both copy protection and IP protection.”

A Secure Processor Architecture for Encrypted Computation on Untrusted Programs (2012)

Abstract: “This paper considers encrypted computation where the user specifies encrypted inputs to an untrusted program, and the server computes on those encrypted inputs. To this end we propose a secure processor architecture, called Ascend, that guarantees privacy of data when arbitrary programs use the data running in a cloud-like environment (e.g., an untrusted server running an untrusted software stack). The key idea to guarantee privacy is obfuscated instruction execution; Ascend does not disclose what instruction is being run at any given time, be it an arithmetic instruction or a memory instruc-
tion. Periodic accesses to external instruction and data memory are performed through an Oblivious RAM (ORAM) interface to prevent leakage through memory access patterns. We evaluate the processor architecture on SPEC benchmarks running on encrypted data and quantify overheads.”

Proactive Obfuscation (2010)

Abstract: “Proactive obfuscation is a new method for creating server replicas that are likely to have fewer shared vulnerabilities. It uses semantics-preserving code transformations to generate diverse executables, periodically restarting servers with these fresh versions. The periodic restarts help bound
the number of compromised replicas that a service ever concurrently runs, and therefore proactive obfuscation makes an adversary’s job harder. Proactive obfuscation was used in implementing two prototypes: a distributed firewall based on state-machine replication and a distributed storage
service based on quorum systems. Costs intrinsic to supporting proactive obfuscation in replicated systems were evaluated by measuring the performance of these prototypes. The results show that employing proactive obfuscation adds little to the cost of replica-management protocols.”

Using Address Independent Seed Encryption and Bonsai Merkle Trees to Make Secure Processors OS- and Performance-Friendly (2007)

Abstract: “…researchers have proposed designs for secure processors which utilize hardware-based memory encryption and integrity verification to protect the privacy and integrity of computation even from sophisticated physical attacks. However, currently proposed schemes remain hampered by problems that make them impractical for use in today’s computer systems: lack of virtual memory and Inter-Process Communication support as well as excessive storage and performance overheads. In this paper, we propose 1) Address Independent Seed Encryption (AISE), a counter-mode based memory encryption scheme using a novel seed composition, and 2) Bonsai Merkle Trees (BMT), a novel Merkle Tree-based memory integrity verification technique, to eliminate these system and performance issues associated with prior counter-mode memory encryption and Merkle Tree integrity verification schemes. We present both a qualitative discussion and a quantitative analysis to illustrate the advantages of our techniques over previously proposed approaches in terms of complexity, feasibility, performance, and storage. Our results show that AISE+BMT reduces the overhead of prior memory encryption and integrity verification schemes from 12% to 2% on average, while eliminating critical system-level problems.”

Compiler-Assisted Memory Encryption for Embedded Processors (2007)

Abstract: “A critical component in the design of secure processors is memory encryption which provides protection for the privacy of code and data stored in off-chip memory. The overhead of the decryption operation that must precede a load requiring an off-chip memory access, decryption being on the critical path, can significantly degrade performance. Recently hardware counter-based one-time pad encryption techniques [11, 13, 9] have been proposed to reduce this overhead. For highend processors the performance impact of decryption has been successfully limited due to: presence of fairly large on-chip L1 and L2 caches that reduce off-chip accesses; and additional hardware support proposed in [13, 9] to reduce decryption latency. However, for low- to medium-end
embedded processors the performance degradation is high because first they only support small (if any) on-chip L1 caches thus leading to significant off-chip accesses and second the hardware cost of decryption latency reduction solutions in [13, 9] is too high making them unattractive for embedded processors. In this paper we present a compiler-assisted strategy that uses minimal hardware support to reduce the overhead of memory encryption in low- to medium-end embedded processors. Our experiments show that the proposed technique reduces average execution time overhead of memory encryption for low-end (medium-end) embedded processor with 0 KB (32 KB) L1 cache from 60% (13.1%), with single counter, to 12.5% (2.1%) by additionally using only 8 hardware
counter-registers.”

On the Secure Obfuscation of Deterministic Finite Automata

Abstract: “In this paper, we show how to construct secure obfuscation for Deterministic Finite Automata, assuming non-uniformly strong one-way functions exist. We revisit the software protection approaches originally proposed by [5, 10, 12, 17] and revise them to the current obfuscation setting of Barak et al. [2]. Under this model, we introduce an efficient oracle that retains some “small” secret about the original program. Using this secret, we can construct an obfuscator and two-party protocol that securely obfuscates Deterministic Finite Automata against malicious ad-
versaries. The security of this model retains the strong “virtual black box” property originally proposed in [2] while incorporating the stronger condition of dependent auxiliary inputs in [15]. Additionally, we show that our techniques remain secure under concurrent self-composition with
adaptive inputs and that Turing machines are obfuscatable under this model.”

A Flexible Framework for Secure and Efficient Program Obfuscation (2013)

Abstract: “In this paper, we present a modular framework for constructing a secure and efficient program obfuscation scheme. Our approach, inspired by the obfuscation with respect to oracle machines model of [4], retains an interactive online protocol with an oracle, but relaxes the original computational and storage restrictions. We argue this is reasonable given the computational resources of modern personal devices. Furthermore, we relax the information-theoretic security requirement for computational security to utilize established cryptographic primitives. With this additional flexibility we are free to explore different cryptographic building-blocks. Our approach combines authenticated encryption with private information retrieval to construct a secure program obfuscation framework. We give a formal specification of our framework, based on desired functionality and security properties, and provide an example instantiation. In particular, we implement AES in Galois/Counter Mode for authenticated encryption and the Gentry-Ramzan [13] constant communication-rate private information retrieval scheme. We present our implementation results and show that non-trivial sized programs can be realized, but scalability is quickly limited by computational overhead. Finally, we include a discussion on security considerations when instantiating specific modules.”

Hardware Assisted Control Flow Obfuscation for Embedded Processors (2004)

Abstract: “…However, as this paper points out that protecting software with either encryption or obfuscation cannot completely preclude the
control flow information from being leaked. Encryption has been widely studied and employed as a traditional approach for software protection, however, the control flow information is not 100% hidden with solely encrypting the code. On the other hand, pure software-based obfuscation has been proved inefficient to protect software due to its lack of theoretical foundation and considerable performance overhead introduced by complicated transformations. Moreover, even though obfuscation can prevent static reverse engineering, attacker can still successfully bypass the obfuscation by monitoring the dynamic program execution. To address all of these shortcomings, this paper presents a hardware assisted obfuscation technique that is capable of obfuscating the control flow information dynamically. Dynamic obfuscation changes memory access sequence on-the-fly and conceals recurrent instruction access sequences from being identified. Our scheme makes it provably difficult for the attacker to extract any useful information. Our results show that a high-level security protection is possible with only minor performance penalty. Finally, we show that our scheme can be implemented on embedded systems with very little hardware overhead.”

Embedded Software Security through Key-Based Control Flow Obfuscation (2011)

Abstract: “Protection against software piracy and malicious modification of software is proving to be a great challenge for resource-constrained
embedded systems. In this paper, we develop a non-cryptographic, key-based, control flow obfuscation technique, which can be implemented by computationally efficient means, and is capable of operating with minimal hardware support. The scheme is based on matching a series of expected keys in sequence, similar to the unlocking process in a combination lock, and provides high levels of resistance to static and dynamic analyses. It is capable of protecting embedded software against both piracy as well as non-self-replicating malicious modifications. Simulation results on a set of MIPS assembly language programs show that the technique is capable of providing high levels of security at nominal computational overhead and about 10% code-size increase.

HARPOON: An Obfuscation-Based SoC Design Methodology for Hardware Protection (2009)

Abstract: “Hardware intellectual-property (IP) cores have emerged as an integral part of modern system-on-chip (SoC) designs. However, IP vendors are facing major challenges to protect hardware IPs from IP piracy. This paper proposes a novel design methodology for hardware IP protection using netlist-level obfus-
cation. The proposed methodology can be integrated in the SoC design and manufacturing flow to simultaneously obfuscate and authenticate the design. Simulation results for a set of ISCAS-89 benchmark circuits and the advanced-encryption-standard IP core show that high levels of security can be achieved at less than 5% area and power overhead under delay constraint.”

Embedded Reconfigurable Logic for ASIC Design Obfuscation Against Supply Chain Attacks (2014)

Abstract: “Hardware is the foundation and the root of trust of any security system. However, in today’s global IC industry, an IP provider, an IC design house, a CAD company, or a foundry may subvert a VLSI system with back doors or logic bombs. Such a supply chain adversary’s capability is rooted in his knowledge on the hardware design. Successful hardware design obfuscation would severely limit a supply chain adversary’s capability if not preventing all supply chain attacks. However, not all designs are obfuscatable in traditional technologies. We propose to achieve ASIC design obfuscation based on embedded reconfigurable logic which is determined by the end user and unknown to any party in the supply chain. Combined with other security techniques, embedded reconfigurable logic can provide the root of ASIC design obfuscation, data confidentiality and tamper-proofness. As a case study, we evaluate hardware-based code injection attacks and reconfiguration-based instruction set obfuscation based on an open source SPARC processor LEON2. We prevent program
monitor Trojan attacks and increase the area of a minimum code injection Trojan with a 1KB ROM by 2.38% for every 1% area increase of the LEON2 processor.”

Authenticating executions for trusted systems (2013)

Abstract: “Constructing trustworthy computer systems requires validating that every executed piece of code is genuine and that the programs do exactly what they are supposed to do. However, pre-execution code integrity validations can fail to detect runtime compromises, such as code injection, return and jump-oriented programming, and illegal linking of code to compromised library functions. In this dissertation, we propose and investigate three distinct mechanisms for authenticating code execution at run-time. The common goal of these techniques is to detect run-time compromises, irrespective of
the specific type of attack that may have been carried out. Thus, these solutions are universal and are in sharp contrast to piecemeal solutions that have been proposed to detect specific types of attacks that compromise execution.

Our first technique does not rely on specialized hardware support within the
platform and uses a challenge-response mechanism to verify the signature of the execution program running on a remote host. The execution signature at randomly chosen points in the code is verified against a reference. This technique is limited in its use of run time modifications of the binary and has a high execution overhead. Our next technique attempts to avoid these limitations by performing run-time authentication of control flow by using existing hardware support in contemporary CPUs for branch tracing, a mechanism that was originally added to support debugging. As the program executes, its trace of taken branches, as logged by the tracing hardware is verified against a reference control flow graph, that has edges corresponding to control flow paths, by a separated and ivtrusted control thread. The execution overhead for full authentication of the control flow path is considerable. However, used judiciously, this mechanism can authenticate the full control flow path in critical functions, such as frequent systems calls, with a reasonably low execution overhead, as low as 20% of 30%. This technique does not require any modification of the binaries, so reentrancy is ensured.

The final mechanism for execution recognizes and addresses the need for full execution authentication with a low overhead, where both code integrity and control flow integrity are simultaneously validated. This mechanism, called REV (Run-time Execution Validator) can be retrofitted into an existing out-of-order CPU pipeline. Prior to presenting REV, we also formulate the ideal requirements of a mechanism for authenticating execution and use it later to see if REV meets these requirements. REV not only authenticates the control flow path and instructions along the instructions along the execution path but it also prevents the results of compromised executions from propagating to memory. REV offers a scalable solution that handles multiple execution modules, irrespective of their sizes and does not require any binary modification, nor access to the source code. The assessment of REV using a cycle-accurate simulator shows that execution overhead is limited to an average of less than 2% on the SPEC benchmarks. REV thus meets all of the requirements of an ideal mechanism for authenticating code and control flow integrity at run-time.”

Nick P • June 23, 2014 4:48 PM

@ Mike the Goat

Quite a few of these submissions and those from my last huge paper release report sub-10% performance drops with small chip utilization too. Some were closer to 1%. This is typically the case where the mechanism does one thing and is designed well.

Some have much larger performance impacts more in range of 30%-70%. The largest hit comes with oblivious or secure multiparty computing schemes. Although long thought impractical, one of these papers manages a 15x slowdown putting it in range of first Java VMs. So, for first time, that’s now practical in some applications.

@ Wael

Nah, Google presents me more options rather than less to ensure NSA has a continuing record of my online activity. People in Ft. Meade sleep better that way and don’t feel the need to have FBI SWAT teams “investigate” what I might be doing. 😉

Nick P • June 23, 2014 10:56 PM

Two more tagged architectures

HARDWARE SECURITY TAGS FOR ENHANCED OPERATING SYSTEM SECURITY (2013)

Abstract: “This paper addresses the design and implementation of a new tagging scheme for access control and information flow; specifically the implementation at the assembly language level for a zero-kernel operating system. We also discuss key lessons learned that we have not seen addressed in related literature.”

Hardware Enforcement of Application Security Policies Using Tagged Memory

Abstract: “We present the Loki tagged memory architecture, along with a novel operating system structure that takes advantage of tagged memory to enforce application security policies in hardware. We built a full-system prototype of Loki by modifying a synthesizable SPARC core, mapping it to an FPGA board, and porting HiStar, a Unix-like operating system, to run on it. One result is that Loki allows HiStar, an OS already designed to have a small trusted kernel, to further reduce the amount of trusted code by a factor of two, and to enforce security despite kernel compromises. Using various workloads, we also demonstrate that HiStar running on Loki incurs a low performance overhead.”

Note: Both of the above modify a SPARC architecture processor.

@ Mike the Goat

One thing I was thinking about recently is licensing cost for processor architecture and baseline implementation. I promoted MIPS designs because they cost from $700,000-900,000 vs $1-15 mil for ARM. The SPARC architecture is open so you can freely build your own so long as you don’t call it SPARC. You can say SPARC-compatible or something like that. That’s nice given that open MIPS and ARM cores all mention they’re taking steps to avoid lawsuits, including using obsolete versions. I can’t find anyone talking about the price of SPARC licensing so, given it’s open, it might be much cheaper than MIPS. And a few security modifications for processors (examples above) already put it to use. And there’s quite a few open-ish cores. And OpenBSD always had good support for it. So, I see those being the selling points for going with a SPARC instead of the others.

Wait, you actually use a SPARC machine. Why the hell am I telling you of all people lol… (shrugs) (submits anyway)

Nick P • June 24, 2014 7:14 PM

@ Mike the Goat

You might find this MPP/NUMA security architecture interesting. (skip to bold heading) It’s one of my few truly original works and can integrate almost anything I’ve posted here without middleware killing performance. I also found prior art for the most critical component in 20+ year old systems. Only problem might be cost to develop and operate. Interconnect switch, cables and custom chips that is. The individual boards can get pretty cheap.

Which is where this budget, SPARC-based, DSM machine comes into play. 😉 It just required two custom chips, theoretically scaled to 512 nodes, and was actually built to 128 I think. Could always pay SGI to port their NUMAFlex architecture to it, too, as they focus on technical computing rather than secure business computing. That they’re not really the competition and especially not Oracle are both nice points for me.

Nick P • June 25, 2014 1:16 PM

@ Figureitout

“Where’s Nick’s Note?”

Lol. I was rushing it out so didn’t bother to analyze them. The most practical one’s are a bit self-explanatory, though. 🙂

Nick P • June 26, 2014 4:56 PM

@ Clive Robinson and other chip design enthusiasts

Check out this radical, cellular, computing architecture:

http://www.zettaflops.org/fec05/Thomas-Sterling.pdf

The guy had been working on it for several years before this paper. It combines computation, memory, and communication into primitive processing elements. The overall hardware is a large 3D construct of layers that are each a grid of these and other logic (eg external I/O connectors). The author also maps a parallel computing model onto it that even uses continuations. The idea is achieve exascale computing by using an architecture that eliminates most bottlenecks caused by traditional Turing-style architecture. It’s quite an interesting design.

Far as security, I’d use a guard with data validation, a safe API, and certifying compilers. Although it’s too early to worry about security of Continuum Computing Architecture, but we know it will take a few decades at the least. So, I’ll stick to putting less radical computer in front using methods I can actually understand. 😉