-
Robust Constant-Time Cryptography
Authors:
Matthew Kolosick,
Basavesh Ammanaghatta Shivakumar,
Sunjay Cauligi,
Marco Patrignani,
Marco Vassena,
Ranjit Jhala,
Deian Stefan
Abstract:
The constant-time property is considered the security standard for cryptographic code. Code following the constant-time discipline is free from secret-dependent branches and memory accesses, and thus avoids leaking secrets through cache and timing side-channels. The constant-time property makes a number of implicit assumptions that are fundamentally at odds with the reality of cryptographic code.…
▽ More
The constant-time property is considered the security standard for cryptographic code. Code following the constant-time discipline is free from secret-dependent branches and memory accesses, and thus avoids leaking secrets through cache and timing side-channels. The constant-time property makes a number of implicit assumptions that are fundamentally at odds with the reality of cryptographic code. Constant-time is not robust. The first issue with constant-time is that it is a whole-program property: It relies on the entirety of the code base being constant-time. But, cryptographic developers do not generally write whole programs; rather, they provide libraries and specific algorithms for other application developers to use. As such, developers of security libraries must maintain their security guarantees even when their code is operating within (potentially untrusted) application contexts. Constant-time requires memory safety. The whole-program nature of constant-time also leads to a second issue: constant-time requires memory safety of all the running code. Any memory safety bugs, whether in the library or the application, will wend their way back to side-channel leaks of secrets if not direct disclosure. And although cryptographic libraries should (and are) written to be memory-safe, it is unfortunately unrealistic to expect the same from every application that uses each library. We formalize robust constant-time and build a RobustIsoCrypt compiler that transforms the library code and protects the secrets even when they are linked with untrusted code. Our evaluation with SUPERCOP benchmarking framework shows that the performance overhead is less than five percent on average.
△ Less
Submitted 9 November, 2023;
originally announced November 2023.
-
MSWasm: Soundly Enforcing Memory-Safe Execution of Unsafe Code
Authors:
Alexandra E. Michael,
Anitha Gollamudi,
Jay Bosamiya,
Craig Disselkoen,
Aidan Denlinger,
Conrad Watt,
Bryan Parno,
Marco Patrignani,
Marco Vassena,
Deian Stefan
Abstract:
Most programs compiled to WebAssembly (Wasm) today are written in unsafe languages like C and C++. Unfortunately, memory-unsafe C code remains unsafe when compiled to Wasm -- and attackers can exploit buffer overflows and use-after-frees in Wasm almost as easily as they can on native platforms. Memory-Safe WebAssembly (MSWasm) proposes to extend Wasm with language-level memory-safety abstractions…
▽ More
Most programs compiled to WebAssembly (Wasm) today are written in unsafe languages like C and C++. Unfortunately, memory-unsafe C code remains unsafe when compiled to Wasm -- and attackers can exploit buffer overflows and use-after-frees in Wasm almost as easily as they can on native platforms. Memory-Safe WebAssembly (MSWasm) proposes to extend Wasm with language-level memory-safety abstractions to precisely address this problem. In this paper, we build on the original MSWasm position paper to realize this vision. We give a precise and formal semantics of MSWasm, and prove that well-typed MSWasm programs are, by construction, robustly memory safe. To this end, we develop a novel, language-independent memory-safety property based on colored memory locations and pointers. This property also lets us reason about the security guarantees of a formal C-to-MSWasm compiler -- and prove that it always produces memory-safe programs (and preserves the semantics of safe programs). We use these formal results to then guide several implementations: Two compilers of MSWasm to native code, and a C-to-MSWasm compiler (that extends Clang). Our MSWasm compilers support different enforcement mechanisms, allowing developers to make security-performance trade-offs according to their needs. Our evaluation shows that the overhead of enforcing memory safety in software ranges from 22% (enforcing spatial safety alone) to 198% (enforcing full memory safety) on the PolyBenchC suite. More importantly, MSWasm's design makes it easy to swap between enforcement mechanisms; as fast (especially hardware-based) enforcement techniques become available, MSWasm will be able to take advantage of these advances almost for free.
△ Less
Submitted 26 September, 2022; v1 submitted 29 August, 2022;
originally announced August 2022.
-
From Fine- to Coarse-Grained Dynamic Information Flow Control and Back, a Tutorial on Dynamic Information Flow
Authors:
Marco Vassena,
Alejandro Russo,
Deepak Garg,
Vineet Rajani,
Deian Stefan
Abstract:
This tutorial provides a complete and homogeneous account of the latest advances in fine- and coarse-grained dynamic information-flow control (IFC) security. Since the 70s, the programming language and the operating system communities have proposed different IFC approaches. IFC operating systems track information flows in a coarse-grained fashion, at the granularity of a process. In contrast, trad…
▽ More
This tutorial provides a complete and homogeneous account of the latest advances in fine- and coarse-grained dynamic information-flow control (IFC) security. Since the 70s, the programming language and the operating system communities have proposed different IFC approaches. IFC operating systems track information flows in a coarse-grained fashion, at the granularity of a process. In contrast, traditional language-based approaches to IFC are fine-grained: they track information flows at the granularity of program variables. For decades, researchers believed coarse-grained IFC to be strictly less permissive than fine-grained IFC -- coarse-grained IFC systems seem inherently less precise because they track less information -- and so granularity appeared to be a fundamental feature of IFC systems. We show that the granularity of the tracking system does not fundamentally restrict how precise or permissive dynamic IFC systems can be. To this end, we mechanize two mostly standard languages, one with a fine-grained dynamic IFC system and the other with a coarse-grained dynamic IFC system, and prove a semantics-preserving translation from each language to the other. In addition, we derive the standard security property of non-interference of each language from that of the other via our verified translation. These translations stand to have important implications on the usability of IFC approaches. The coarse- to fine-grained direction can be used to remove the label annotation burden that fine-grained systems impose on developers, while the fine- to coarse-grained translation shows that coarse-grained systems -- which are easier to design and implement -- can track information as precisely as fine-grained systems and provides an algorithm for automatically retrofitting legacy applications to run on existing coarse-grained systems.
△ Less
Submitted 29 August, 2022;
originally announced August 2022.
-
A Turning Point for Verified Spectre Sandboxing
Authors:
Sunjay Cauligi,
Marco Guarnieri,
Daniel Moghimi,
Deian Stefan,
Marco Vassena
Abstract:
Spectre attacks enable an attacker to access restricted data in an application's memory. Both the academic community and industry veterans have developed several mitigations to block Spectre attacks, but to date, very few have been formally vetted; most are "best effort" strategies. Formal guarantees are particularly crucial for protecting isolated environments like sandboxing against Spectre atta…
▽ More
Spectre attacks enable an attacker to access restricted data in an application's memory. Both the academic community and industry veterans have developed several mitigations to block Spectre attacks, but to date, very few have been formally vetted; most are "best effort" strategies. Formal guarantees are particularly crucial for protecting isolated environments like sandboxing against Spectre attacks. In such environments, a subtle flaw in the mitigation would allow untrusted code to break out of the sandbox and access trusted memory regions.
In our work, we develop principled foundations to build isolated environments resistant against Spectre attacks. We propose a formal framework for reasoning about sandbox execution and Spectre attacks. We formalize properties that sound mitigation strategies must fulfill and we show how various existing mitigations satisfy (or fail to satisfy!) these properties.
△ Less
Submitted 2 August, 2022;
originally announced August 2022.
-
Blocked or Broken? Automatically Detecting When Privacy Interventions Break Websites
Authors:
Michael Smith,
Peter Snyder,
Moritz Haller,
Benjamin Livshits,
Deian Stefan,
Hamed Haddadi
Abstract:
A core problem in the development and maintenance of crowd-sourced filter lists is that their maintainers cannot confidently predict whether (and where) a new filter list rule will break websites. This is a result of enormity of the Web, which prevents filter list authors from broadly understanding the impact of a new blocking rule before they ship it to millions of users. The inability of filter…
▽ More
A core problem in the development and maintenance of crowd-sourced filter lists is that their maintainers cannot confidently predict whether (and where) a new filter list rule will break websites. This is a result of enormity of the Web, which prevents filter list authors from broadly understanding the impact of a new blocking rule before they ship it to millions of users. The inability of filter list authors to evaluate the Web compatibility impact of a new rule before shipping it severely reduces the benefits of filter-list-based content blocking: filter lists are both overly-conservative (i.e. rules are tailored narrowly to reduce the risk of breaking things) and error-prone (i.e. blocking tools still break large numbers of sites). To scale to the size and scope of the Web, filter list authors need an automated system to detect when a new filter rule breaks websites, before that breakage has a chance to make it to end users.
In this work, we design and implement the first automated system for predicting when a filter list rule breaks a website. We build a classifier, trained on a dataset generated by a combination of compatibility data from the EasyList project and novel browser instrumentation, and find it is accurate to practical levels (AUC 0.88). Our open source system requires no human interaction when assessing the compatibility risk of a proposed privacy intervention. We also present the 40 page behaviors that most predict breakage in observed websites.
△ Less
Submitted 2 May, 2022; v1 submitted 7 March, 2022;
originally announced March 2022.
-
SoK: Practical Foundations for Software Spectre Defenses
Authors:
Sunjay Cauligi,
Craig Disselkoen,
Daniel Moghimi,
Gilles Barthe,
Deian Stefan
Abstract:
Spectre vulnerabilities violate our fundamental assumptions about architectural abstractions, allowing attackers to steal sensitive data despite previously state-of-the-art countermeasures. To defend against Spectre, developers of verification tools and compiler-based mitigations are forced to reason about microarchitectural details such as speculative execution. In order to aid developers with th…
▽ More
Spectre vulnerabilities violate our fundamental assumptions about architectural abstractions, allowing attackers to steal sensitive data despite previously state-of-the-art countermeasures. To defend against Spectre, developers of verification tools and compiler-based mitigations are forced to reason about microarchitectural details such as speculative execution. In order to aid developers with these attacks in a principled way, the research community has sought formal foundations for speculative execution upon which to rebuild provable security guarantees.
This paper systematizes the community's current knowledge about software verification and mitigation for Spectre. We study state-of-the-art software defenses, both with and without associated formal models, and use a cohesive framework to compare the security properties each defense provides. We explore a wide variety of tradeoffs in the expressiveness of formal frameworks, the complexity of defense tools, and the resulting security guarantees. As a result of our analysis, we suggest practical choices for developers of analysis and mitigation tools, and we identify several open problems in this area to guide future work on grounded software defenses.
△ Less
Submitted 8 April, 2022; v1 submitted 12 May, 2021;
originally announced May 2021.
-
Isolation Without Taxation: Near Zero Cost Transitions for SFI
Authors:
Matthew Kolosick,
Shravan Narayan,
Evan Johnson,
Conrad Watt,
Michael LeMay,
Deepak Garg,
Ranjit Jhala,
Deian Stefan
Abstract:
Software sandboxing or software-based fault isolation (SFI) is a lightweight approach to building secure systems out of untrusted components. Mozilla, for example, uses SFI to harden the Firefox browser by sandboxing third-party libraries, and companies like Fastly and Cloudflare use SFI to safely co-locate untrusted tenants on their edge clouds. While there have been significant efforts to optimi…
▽ More
Software sandboxing or software-based fault isolation (SFI) is a lightweight approach to building secure systems out of untrusted components. Mozilla, for example, uses SFI to harden the Firefox browser by sandboxing third-party libraries, and companies like Fastly and Cloudflare use SFI to safely co-locate untrusted tenants on their edge clouds. While there have been significant efforts to optimize and verify SFI enforcement, context switching in SFI systems remains largely unexplored: almost all SFI systems use \emph{heavyweight transitions} that are not only error-prone but incur significant performance overhead from saving, clearing, and restoring registers when context switching. We identify a set of \emph{zero-cost conditions} that characterize when sandboxed code has sufficient structured to guarantee security via lightweight \emph{zero-cost} transitions (simple function calls). We modify the Lucet Wasm compiler and its runtime to use zero-cost transitions, eliminating the undue performance tax on systems that rely on Lucet for sandboxing (e.g., we speed up image and font rendering in Firefox by up to 29.7\% and 10\% respectively). To remove the Lucet compiler and its correct implementation of the Wasm specification from the trusted computing base, we (1) develop a \emph{static binary verifier}, VeriZero, which (in seconds) checks that binaries produced by Lucet satisfy our zero-cost conditions, and (2) prove the soundness of VeriZero by developing a logical relation that captures when a compiled Wasm function is semantically well-behaved with respect to our zero-cost conditions. Finally, we show that our model is useful beyond Wasm by describing a new, purpose-built SFI system, SegmentZero32, that uses x86 segmentation and LLVM with mostly off-the-shelf passes to enforce our zero-cost conditions; our prototype performs on-par with the state-of-the-art Native Client SFI system.
△ Less
Submitted 18 November, 2021; v1 submitted 30 April, 2021;
originally announced May 2021.
-
Solver-Aided Constant-Time Circuit Verification
Authors:
Rami Gokhan Kici,
Klaus v. Gleissenthall,
Deian Stefan,
Ranjit Jhala
Abstract:
We present Xenon, a solver-aided method for formally verifying that Verilog hardware executes in constant-time. Xenon scales to realistic hardware designs by drastically reducing the effort needed to localize the root cause of verification failures via a new notion of constant-time counterexamples, which Xenon uses to automatically synthesize a minimal set of secrecy assumptions. Xenon further exp…
▽ More
We present Xenon, a solver-aided method for formally verifying that Verilog hardware executes in constant-time. Xenon scales to realistic hardware designs by drastically reducing the effort needed to localize the root cause of verification failures via a new notion of constant-time counterexamples, which Xenon uses to automatically synthesize a minimal set of secrecy assumptions. Xenon further exploits modularity in Verilog code via a notion of module summaries, thereby avoiding duplicate work across multiple module instantiations. We show how Xenon's assumption synthesis and summaries enable the verification of a variety of circuits including AES, a highly modular AES-256 implementation where modularity cuts verification from six hours to under three seconds, and ScarV, a timing channel hardened RISC-V micro-controller whose size exceeds previously verified designs by an order of magnitude.
△ Less
Submitted 1 April, 2021;
originally announced April 2021.
-
Swivel: Hardening WebAssembly against Spectre
Authors:
Shravan Narayan,
Craig Disselkoen,
Daniel Moghimi,
Sunjay Cauligi,
Evan Johnson,
Zhao Gang,
Anjo Vahldiek-Oberwagner,
Ravi Sahita,
Hovav Shacham,
Dean Tullsen,
Deian Stefan
Abstract:
We describe Swivel, a new compiler framework for hardening WebAssembly (Wasm) against Spectre attacks. Outside the browser, Wasm has become a popular lightweight, in-process sandbox and is, for example, used in production to isolate different clients on edge clouds and function-as-a-service platforms. Unfortunately, Spectre attacks can bypass Wasm's isolation guarantees. Swivel hardens Wasm agains…
▽ More
We describe Swivel, a new compiler framework for hardening WebAssembly (Wasm) against Spectre attacks. Outside the browser, Wasm has become a popular lightweight, in-process sandbox and is, for example, used in production to isolate different clients on edge clouds and function-as-a-service platforms. Unfortunately, Spectre attacks can bypass Wasm's isolation guarantees. Swivel hardens Wasm against this class of attacks by ensuring that potentially malicious code can neither use Spectre attacks to break out of the Wasm sandbox nor coerce victim code-another Wasm client or the embedding process-to leak secret data.
We describe two Swivel designs, a software-only approach that can be used on existing CPUs, and a hardware-assisted approach that uses extension available in Intel 11th generation CPUs. For both, we evaluate a randomized approach that mitigates Spectre and a deterministic approach that eliminates Spectre altogether. Our randomized implementations impose under 10.3% overhead on the Wasm-compatible subset of SPEC 2006, while our deterministic implementations impose overheads between 3.3% and 240.2%. Though high on some benchmarks, Swivel's overhead is still between 9x and 36.3x smaller than existing defenses that rely on pipeline fences.
△ Less
Submitted 19 March, 2021; v1 submitted 25 February, 2021;
originally announced February 2021.
-
Automatically Eliminating Speculative Leaks from Cryptographic Code with Blade
Authors:
Marco Vassena,
Craig Disselkoen,
Klaus V. Gleissenthall,
Sunjay Cauligi,
Rami Gökhan Kici,
Ranjit Jhala,
Dean Tullsen,
Deian Stefan
Abstract:
We introduce BLADE, a new approach to automatically and efficiently eliminate speculative leaks from cryptographic code. BLADE is built on the insight that to stop leaks via speculation, it suffices to $\textit{cut}$ the dataflow from expressions that speculatively introduce secrets ($\textit{sources}$) to those that leak them through the cache ($\textit{sinks}$), rather than prohibit speculation…
▽ More
We introduce BLADE, a new approach to automatically and efficiently eliminate speculative leaks from cryptographic code. BLADE is built on the insight that to stop leaks via speculation, it suffices to $\textit{cut}$ the dataflow from expressions that speculatively introduce secrets ($\textit{sources}$) to those that leak them through the cache ($\textit{sinks}$), rather than prohibit speculation altogether. We formalize this insight in a $\textit{static type system}$ that (1) types each expression as either $\textit{transient}$, i.e., possibly containing speculative secrets or as being $\textit{stable}$, and (2) prohibits speculative leaks by requiring that all $\textit{sink}$ expressions are stable. BLADE relies on a new new abstract primitive, $\textbf{protect}$, to halt speculation at fine granularity. We formalize and implement $\textbf{protect}$ using existing architectural mechanisms, and show how BLADE's type system can automatically synthesize a $\textit{minimal}$ number of $\textbf{protect}$s to provably eliminate speculative leaks. We implement BLADE in the Cranelift WebAssembly compiler and evaluate our approach by repairing several verified, yet vulnerable WebAssembly implementations of cryptographic primitives. We find that Blade can fix existing programs that leak via speculation $\textit{automatically}$, without user intervention, and $\textit{efficiently}$ even when using fences to implement $\textbf{protect}$.
△ Less
Submitted 7 December, 2020; v1 submitted 1 May, 2020;
originally announced May 2020.
-
Retrofitting Fine Grain Isolation in the Firefox Renderer (Extended Version)
Authors:
Shravan Narayan,
Craig Disselkoen,
Tal Garfinkel,
Nathan Froyd,
Eric Rahm,
Sorin Lerner,
Hovav Shacham,
Deian Stefan
Abstract:
Firefox and other major browsers rely on dozens of third-party libraries to render audio, video, images, and other content. These libraries are a frequent source of vulnerabilities. To mitigate this threat, we are migrating Firefox to an architecture that isolates these libraries in lightweight sandboxes, dramatically reducing the impact of a compromise.
Retrofitting isolation can be labor-inten…
▽ More
Firefox and other major browsers rely on dozens of third-party libraries to render audio, video, images, and other content. These libraries are a frequent source of vulnerabilities. To mitigate this threat, we are migrating Firefox to an architecture that isolates these libraries in lightweight sandboxes, dramatically reducing the impact of a compromise.
Retrofitting isolation can be labor-intensive, very prone to security bugs, and requires critical attention to performance. To help, we developed RLBox, a framework that minimizes the burden of converting Firefox to securely and efficiently use untrusted code. To enable this, RLBox employs static information flow enforcement, and lightweight dynamic checks, expressed directly in the C++ type system.
RLBox supports efficient sandboxing through either software-based-fault isolation or multi-core process isolation. Performance overheads are modest and transient, and have only minor impact on page latency. We demonstrate this by sandboxing performance-sensitive image decoding libraries ( libjpeg and libpng ), video decoding libraries ( libtheora and libvpx ), the libvorbis audio decoding library, and the zlib decompression library.
RLBox, using a WebAssembly sandbox, has been integrated into production Firefox to sandbox the libGraphite font shaping library.
△ Less
Submitted 9 March, 2020; v1 submitted 1 March, 2020;
originally announced March 2020.
-
Gobi: WebAssembly as a Practical Path to Library Sandboxing
Authors:
Shravan Narayan,
Tal Garfinkel,
Sorin Lerner,
Hovav Shacham,
Deian Stefan
Abstract:
Software based fault isolation (SFI) is a powerful approach to reduce the impact of security vulnerabilities in large C/C++ applications like Firefox and Apache. Unfortunately, practical SFI tools have not been broadly available.
Developing SFI toolchains are a significant engineering challenge. Only in recent years have browser vendors invested in building production quality SFI tools like Nati…
▽ More
Software based fault isolation (SFI) is a powerful approach to reduce the impact of security vulnerabilities in large C/C++ applications like Firefox and Apache. Unfortunately, practical SFI tools have not been broadly available.
Developing SFI toolchains are a significant engineering challenge. Only in recent years have browser vendors invested in building production quality SFI tools like Native Client (NaCl) to sandbox code. Further, without committed support, these tools are not viable, e.g. NaCl has been discontinued, orphaning projects that relied on it.
WebAssembly (Wasm) offers a promising solution---it can support high performance sandboxing and has been embraced by all major browser vendors---thus seems to have a viable future. However, Wasm presently only offers a solution for sandboxing mobile code. Providing SFI for native application, such as C/C++ libraries requires additional steps.
To reconcile the different worlds of Wasm on the browser and native platforms, we present Gobi. Gobi is a system of compiler changes and runtime support that can sandbox normal C/C++ libraries with Wasm---allowing them to be compiled and linked into native applications. Gobi has been tested on libjpeg, libpng, and zlib.
Based on our experience developing Gobi, we conclude with a call to arms to the Wasm community and SFI research community to make Wasm based module sandboxing a first class use case and describe how this can significantly benefit both communities.
Addendum: This short paper was originally written in January of 2019. Since then, the implementation and design of Gobi has evolved substantially as some of the issues raised in this paper have been addressed by the Wasm community. Nevertheless, several challenges still remain. We have thus left the paper largely intact and only provide a brief update on the state of Wasm tooling as of November 2019 in the last section.
△ Less
Submitted 4 December, 2019;
originally announced December 2019.
-
Iodine: Verifying Constant-Time Execution of Hardware
Authors:
Klaus v. Gleissenthall,
Rami Gökhan Kıcı,
Deian Stefan,
Ranjit Jhala
Abstract:
To be secure, cryptographic algorithms crucially rely on the underlying hardware to avoid inadvertent leakage of secrets through timing side channels. Unfortunately, such timing channels are ubiquitous in modern hardware, due to its labyrinthine fast-paths and optimizations. A promising way to avoid timing vulnerabilities is to devise --- and verify --- conditions under which a hardware design is…
▽ More
To be secure, cryptographic algorithms crucially rely on the underlying hardware to avoid inadvertent leakage of secrets through timing side channels. Unfortunately, such timing channels are ubiquitous in modern hardware, due to its labyrinthine fast-paths and optimizations. A promising way to avoid timing vulnerabilities is to devise --- and verify --- conditions under which a hardware design is free of timing variability, i.e., executes in constant-time. In this paper, we present Iodine: a clock precise, constant-time approach to eliminating timing side channels in hardware. Iodine succeeds in verifying various open source hardware designs in seconds and with little developer effort. Iodine also discovered two constant-time violations: one in a floating-point unit and another one in an RSA encryption module.
△ Less
Submitted 7 October, 2019;
originally announced October 2019.
-
Constant-Time Foundations for the New Spectre Era
Authors:
Sunjay Cauligi,
Craig Disselkoen,
Klaus v. Gleissenthall,
Dean Tullsen,
Deian Stefan,
Tamara Rezk,
Gilles Barthe
Abstract:
The constant-time discipline is a software-based countermeasure used for protecting high assurance cryptographic implementations against timing side-channel attacks. Constant-time is effective (it protects against many known attacks), rigorous (it can be formalized using program semantics), and amenable to automated verification. Yet, the advent of micro-architectural attacks makes constant-time a…
▽ More
The constant-time discipline is a software-based countermeasure used for protecting high assurance cryptographic implementations against timing side-channel attacks. Constant-time is effective (it protects against many known attacks), rigorous (it can be formalized using program semantics), and amenable to automated verification. Yet, the advent of micro-architectural attacks makes constant-time as it exists today far less useful.
This paper lays foundations for constant-time programming in the presence of speculative and out-of-order execution. We present an operational semantics and a formal definition of constant-time programs in this extended setting. Our semantics eschews formalization of microarchitectural features (that are instead assumed under adversary control), and yields a notion of constant-time that retains the elegance and tractability of the usual notion. We demonstrate the relevance of our semantics in two ways: First, by contrasting existing Spectre-like attacks with our definition of constant-time. Second, by implementing a static analysis tool, Pitchfork, which detects violations of our extended constant-time property in real world cryptographic libraries.
△ Less
Submitted 8 May, 2020; v1 submitted 3 October, 2019;
originally announced October 2019.
-
CT-Wasm: Type-Driven Secure Cryptography for the Web Ecosystem
Authors:
Conrad Watt,
John Renner,
Natalie Popescu,
Sunjay Cauligi,
Deian Stefan
Abstract:
A significant amount of both client and server-side cryptography is implemented in JavaScript. Despite widespread concerns about its security, no other language has been able to match the convenience that comes from its ubiquitous support on the "web ecosystem" - the wide variety of technologies that collectively underpins the modern World Wide Web. With the new introduction of the WebAssembly byt…
▽ More
A significant amount of both client and server-side cryptography is implemented in JavaScript. Despite widespread concerns about its security, no other language has been able to match the convenience that comes from its ubiquitous support on the "web ecosystem" - the wide variety of technologies that collectively underpins the modern World Wide Web. With the new introduction of the WebAssembly bytecode language (Wasm) into the web ecosystem, we have a unique opportunity to advance a principled alternative to existing JavaScript cryptography use cases which does not compromise this convenience.
We present Constant-Time WebAssembly (CT-Wasm), a type-driven strict extension to WebAssembly which facilitates the verifiably secure implementation of cryptographic algorithms. CT-Wasm's type system ensures that code written in CT-Wasm is both information flow secure and resistant to timing side channel attacks; like base Wasm, these guarantees are verifiable in linear time. Building on an existing Wasm mechanization, we mechanize the full CT-Wasm specification, prove soundness of the extended type system, implement a verified type checker, and give several proofs of the language's security properties.
We provide two implementations of CT-Wasm: an OCaml reference interpreter and a native implementation for Node.js and Chromium that extends Google's V8 engine. We also implement a CT-Wasm to Wasm rewrite tool that allows developers to reap the benefits of CT-Wasm's type system today, while developing cryptographic algorithms for base Wasm environments. We evaluate the language, our implementations, and supporting tools by porting several cryptographic primitives - Salsa20, SHA-256, and TEA - and the full TweetNaCl library. We find that CT-Wasm is fast, expressive, and generates code that we experimentally measure to be constant-time.
△ Less
Submitted 17 December, 2018; v1 submitted 3 August, 2018;
originally announced August 2018.
-
Liquid Information Flow Control
Authors:
Nadia Polikarpova,
Deian Stefan,
Jean Yang,
Shachar Itzhaky,
Travis Hance,
Armando Solar-Lezama
Abstract:
We present Lifty, a domain-specific language for data-centric applications that manipulate sensitive data. A Lifty programmer annotates the sources of sensitive data with declarative security policies, and the language statically and automatically verifies that the application handles the data according to the policies. Moreover, if verification fails, Lifty suggests a provably correct repair, the…
▽ More
We present Lifty, a domain-specific language for data-centric applications that manipulate sensitive data. A Lifty programmer annotates the sources of sensitive data with declarative security policies, and the language statically and automatically verifies that the application handles the data according to the policies. Moreover, if verification fails, Lifty suggests a provably correct repair, thereby easing the programmer burden of implementing policy enforcing code throughout the application.
The main insight behind Lifty is to encode information flow control using liquid types, an expressive yet decidable type system. Liquid types enable fully automatic checking of complex, data dependent policies, and power our repair mechanism via type-driven error localization and patch synthesis. Our experience using Lifty to implement three case studies from the literature shows that (1) the Lifty policy language is sufficiently expressive to specify many real-world policies, (2) the Lifty type checker is able to verify secure programs and find leaks in insecure programs quickly, and (3) even if the programmer leaves out all policy enforcing code, the Lifty repair engine is able to patch all leaks automatically within a reasonable time.
△ Less
Submitted 30 June, 2020; v1 submitted 12 July, 2016;
originally announced July 2016.
-
On Dynamic Flow-Sensitive Floating-Label Systems
Authors:
Pablo Buiras,
Deian Stefan,
Alejandro Russo
Abstract:
Flow-sensitive analysis for information-flow control (IFC) allows data structures to have mutable security labels, i.e., labels that can change over the course of the computation. This feature is often used to boost the permissiveness of the IFC monitor, by rejecting fewer runs of programs, and to reduce the burden of explicit label annotations. However, adding flow-sensitive constructs (e.g., ref…
▽ More
Flow-sensitive analysis for information-flow control (IFC) allows data structures to have mutable security labels, i.e., labels that can change over the course of the computation. This feature is often used to boost the permissiveness of the IFC monitor, by rejecting fewer runs of programs, and to reduce the burden of explicit label annotations. However, adding flow-sensitive constructs (e.g., references or files) to a dynamic IFC system is subtle and may also introduce high-bandwidth covert channels. In this work, we extend LIO---a language-based floating-label system---with flow-sensitive references. The key insight to safely manipulating the label of a reference is to not only consider the label on the data stored in the reference, i.e., the reference label, but also the label on the reference label itself. Taking this into consideration, we provide an upgrade primitive that can be used to change the label of a reference in a safe manner. We additionally provide a mechanism for automatic upgrades to eliminate the burden of determining when a reference should be upgraded. This approach naturally extends to a concurrent setting, which has not been previously considered by dynamic flow-sensitive systems. For both our sequential and concurrent calculi we prove non-interference by embedding the flow-sensitive system into the original, flow-insensitive LIO calculus---a surprising result on its own.
△ Less
Submitted 22 July, 2015;
originally announced July 2015.
-
Electron Neutrino Classification in Liquid Argon Time Projection Chamber Detector
Authors:
Piotr Płoński,
Dorota Stefan,
Robert Sulej,
Krzysztof Zaremba
Abstract:
Neutrinos are one of the least known elementary particles. The detection of neutrinos is an extremely difficult task since they are affected only by weak sub-atomic force or gravity. Therefore large detectors are constructed to reveal neutrino's properties. Among them the Liquid Argon Time Projection Chamber (LAr-TPC) detectors provide excellent imaging and particle identification ability for stud…
▽ More
Neutrinos are one of the least known elementary particles. The detection of neutrinos is an extremely difficult task since they are affected only by weak sub-atomic force or gravity. Therefore large detectors are constructed to reveal neutrino's properties. Among them the Liquid Argon Time Projection Chamber (LAr-TPC) detectors provide excellent imaging and particle identification ability for studying neutrinos. The computerized methods for automatic reconstruction and identification of particles are needed to fully exploit the potential of the LAr-TPC technique. Herein, the novel method for electron neutrino classification is presented. The method constructs a feature descriptor from images of observed event. It characterizes the signal distribution propagated from vertex of interest, where the particle interacts with the detector medium. The classifier is learned with a constructed feature descriptor to decide whether the images represent the electron neutrino or cascade produced by photons. The proposed approach assumes that the position of primary interaction vertex is known. The method's performance in dependency to the noise in a primary vertex position and deposited energy of particles is studied.
△ Less
Submitted 3 May, 2015;
originally announced May 2015.
-
Image Segmentation in Liquid Argon Time Projection Chamber Detector
Authors:
Piotr Płoński,
Dorota Stefan,
Robert Sulej,
Krzysztof Zaremba
Abstract:
The Liquid Argon Time Projection Chamber (LAr-TPC) detectors provide excellent imaging and particle identification ability for studying neutrinos. An efficient and automatic reconstruction procedures are required to exploit potential of this imaging technology. Herein, a novel method for segmentation of images from LAr-TPC detectors is presented. The proposed approach computes a feature descriptor…
▽ More
The Liquid Argon Time Projection Chamber (LAr-TPC) detectors provide excellent imaging and particle identification ability for studying neutrinos. An efficient and automatic reconstruction procedures are required to exploit potential of this imaging technology. Herein, a novel method for segmentation of images from LAr-TPC detectors is presented. The proposed approach computes a feature descriptor for each pixel in the image, which characterizes amplitude distribution in pixel and its neighbourhood. The supervised classifier is employed to distinguish between pixels representing particle's track and noise. The classifier is trained and evaluated on the hand-labeled dataset. The proposed approach can be a preprocessing step for reconstructing algorithms working directly on detector images.
△ Less
Submitted 27 February, 2015;
originally announced February 2015.
-
IFC Inside: Retrofitting Languages with Dynamic Information Flow Control (Extended Version)
Authors:
Stefan Heule,
Deian Stefan,
Edward Z. Yang,
John C. Mitchell,
Alejandro Russo
Abstract:
Many important security problems in JavaScript, such as browser extension security, untrusted JavaScript libraries and safe integration of mutually distrustful websites (mash-ups), may be effectively addressed using an efficient implementation of information flow control (IFC). Unfortunately existing fine-grained approaches to JavaScript IFC require modifications to the language semantics and its…
▽ More
Many important security problems in JavaScript, such as browser extension security, untrusted JavaScript libraries and safe integration of mutually distrustful websites (mash-ups), may be effectively addressed using an efficient implementation of information flow control (IFC). Unfortunately existing fine-grained approaches to JavaScript IFC require modifications to the language semantics and its engine, a non-goal for browser applications. In this work, we take the ideas of coarse-grained dynamic IFC and provide the theoretical foundation for a language-based approach that can be applied to any programming language for which external effects can be controlled. We then apply this formalism to server- and client-side JavaScript, show how it generalizes to the C programming language, and connect it to the Haskell LIO system. Our methodology offers design principles for the construction of information flow control systems when isolation can easily be achieved, as well as compositional proofs for optimized concrete implementations of these systems, by relating them to their isolated variants.
△ Less
Submitted 16 January, 2015;
originally announced January 2015.
-
Flexible Dynamic Information Flow Control in the Presence of Exceptions
Authors:
Deian Stefan,
Alejandro Russo,
John C. Mitchell,
David Mazières
Abstract:
We describe a new, dynamic, floating-label approach to language-based information flow control. A labeled IO monad, LIO, keeps track of a current label and permits restricted access to IO functionality. The current label floats to exceed the labels of all data observed and restricts what can be modified. Unlike other language-based work, LIO also bounds the current label with a current clearance t…
▽ More
We describe a new, dynamic, floating-label approach to language-based information flow control. A labeled IO monad, LIO, keeps track of a current label and permits restricted access to IO functionality. The current label floats to exceed the labels of all data observed and restricts what can be modified. Unlike other language-based work, LIO also bounds the current label with a current clearance that provides a form of discretionary access control. Computations may encapsulate and pass around the results of computations with different labels. In addition, the LIO monad offers a simple form of labeled mutable references and exception handling. We give precise semantics and prove confidentiality and integrity properties of a call-by-name λ-calculus and provide an implementation in Haskell.
△ Less
Submitted 5 July, 2012;
originally announced July 2012.