Papers tagged as NDSS
  1. Trident: Efficient 4PC Framework for Privacy Preserving Machine Learning 2020 MachineLearning MPC NDSS eprint.iacr.org
    Rahul Rachuri and Ajith Suresh

    Machine learning has started to be deployed in fields such as healthcare and finance, which involves dealing with a lot of sensitive data. This propelled the need for and growth of privacy-preserving machine learning (PPML). We propose an actively secure four-party protocol (4PC), and a framework for PPML, showcasing its applications on four of the most widely-known machine learning algorithms – Linear Regression, Logistic Regression, Neural Networks, and Convolutional Neural Networks.


    Our 4PC protocol tolerating at most one malicious corruption is practically efficient as compared to Gordon et al. (ASIACRYPT 2018) as the 4th party in our protocol is not active in the online phase, except input sharing and output reconstruction stages. Concretely, we reduce the online communication as compared to them by 1 ring element. We use the protocol to build an efficient mixed-world framework (Trident) to switch between the Arithmetic, Boolean, and Garbled worlds. Our framework operates in the offline-online paradigm over rings and is instantiated in an outsourced setting for machine learning, where the data is secretly shared among the servers. Also, we propose conversions especially relevant to privacy-preserving machine learning. With the privilege of having an extra honest party, we outperform the current state-of-the-art ABY3 (for three parties), in terms of both rounds as well as communication complexity.


    The highlights of our framework include using a minimal number of expensive circuits overall as compared to ABY3. This can be seen in our technique for truncation, which does not affect the online cost of multiplication and removes the need for any circuits in the offline phase. Our B2A conversion has an improvement of 7× in rounds and 18× in the communication complexity. In addition to these, all of the special conversions for machine learning, e.g. Secure Comparison, achieve constant round complexity.


    The practicality of our framework is argued through improvements in the benchmarking of the aforementioned algorithms when compared with ABY3. All the protocols are implemented over a 64-bit ring in both LAN and WAN settings. Our improvements go up to 187× for the training phase and 158× for the prediction phase when observed over LAN and WAN.

  2. Practical Traffic Analysis Attacks on Secure Messaging Applications 2020 Attacks NDSS SecureMessaging arxiv.org
    Alireza Bahramali, Ramin Soltani, Amir Houmansadr, Dennis Goeckel, Don Towsley

    Instant Messaging (IM) applications like Telegram, Signal, and WhatsApp have become extremely popular in recent years. Unfortunately, such IM services have been targets of continuous governmental surveillance and censorship, as these services are home to public and private communication channels on socially and politically sensitive topics. To protect their clients, popular IM services deploy state-of-the-art encryption mechanisms. In this paper, we show that despite the use of advanced encryption, popular IM applications leak sensitive information about their clients to adversaries who merely monitor their encrypted IM traffic, with no need for leveraging any software vulnerabilities of IM applications. Specifically, we devise traffic analysis attacks that enable an adversary to identify administrators as well as members of target IM channels (e.g., forums) with high accuracies. We believe that our study demonstrates a significant, real-world threat to the users of such services given the increasing attempts by oppressive governments at cracking down controversial IM channels.
    We demonstrate the practicality of our traffic analysis attacks through extensive experiments on real-world IM communications. We show that standard countermeasure techniques such as adding cover traffic can degrade the effectiveness of the attacks we introduce in this paper. We hope that our study will encourage IM providers to integrate effective traffic obfuscation countermeasures into their software. In the meantime, we have designed and deployed an open-source, publicly available countermeasure system, called IMProxy, that can be used by IM clients with no need for any support from IM providers. We have demonstrated the effectiveness of IMProxy through experiments.

  3. MACAO: A Maliciously-Secure and Client-Efficient Active ORAM Framework 2020 NDSS ORAM eprint.iacr.org
    Thang Hoang and Jorge Guajardo and Attila A. Yavuz

    Oblivious Random Access Machine (ORAM) allows a client to hide the access pattern and thus, offers a strong level of privacy for data outsourcing. An ideal ORAM scheme is expected to offer desirable properties such as low client bandwidth, low server computation overhead and the ability to compute over encrypted data. S3ORAM (CCS’17) is an efficient active ORAM scheme, which takes advantage of secret sharing to provide ideal properties for data outsourcing such as low client bandwidth, low server computation and low delay. Despite its merits, S3ORAM only offers security in the semi-honest setting. In practice, an ORAM protocol is likely to operate in the presence of malicious adversaries who might deviate from the protocol to compromise the client privacy.


    In this paper, we propose MACAO, a new multi-server ORAM framework, which offers integrity, access pattern obliviousness against active adversaries, and the ability to perform secure computation over the accessed data. MACAO harnesses authenticated secret sharing techniques and tree-ORAM paradigm to achieve low client communication, efficient server computation, and low storage overhead at the same time. We fully implemented MACAO and conducted extensive experiments in real cloud platforms (Amazon EC2) to validate the performance of MACAO compared with the state-of-the-art. Our results indicate that MACAO can achieve comparable performance to S3ORAM while offering security against malicious adversaries. MACAO is a suitable candidate for integration into distributed file systems with encrypted computation capabilities towards enabling an oblivious functional data outsourcing infrastructure.

  4. Dynamic Searchable Encryption with Small Client Storage 2020 NDSS SearchableEncryption eprint.iacr.org
    Ioannis Demertzis and Javad Ghareh Chamani and Dimitrios Papadopoulos and Charalampos Papamanthou

    We study the problem of dynamic searchable encryption (DSE) with forward-and-backward privacy. Many DSE schemes have been proposed recently but the most efficient ones have one limitation: they require maintaining an operation counter for each unique keyword, either stored locally at the client or accessed obliviously (e.g., with an oblivious map) at the server, during every operation. We propose three new schemes that overcome the above limitation and achieve constant permanent client storage with improved performance, both asymptotically and experimentally, compared to prior state-of-the-art works. In particular, our first two schemes adopt a “static-to-dynamic” transformation which eliminates the need for oblivious accesses during searches. Due to this, they are the first practical schemes with minimal client storage and non-interactive search. Our third scheme is the first quasi-optimal forward-and-backward DSE scheme with only a logarithmic overhead for retrieving the query result (independently of previous deletions). While it does require an oblivious access during search in order to keep permanent client storage minimal, its practical performance is up to four orders of magnitude better than the best existing scheme with quasi-optimal search.

  5. BLAZE: Blazing Fast Privacy-Preserving Machine Learning 2020 MachineLearning MPC NDSS arxiv.org
    Arpita Patra and Ajith Suresh

    Machine learning tools have illustrated their potential in many significant sectors such as healthcare and finance, to aide in deriving useful inferences. The sensitive and confidential nature of the data, in such sectors, raise natural concerns for the privacy of data. This motivated the area of Privacy-preserving Machine Learning (PPML) where privacy of the data is guaranteed. Typically, ML techniques require large computing power, which leads clients with limited infrastructure to rely on the method of Secure Outsourced Computation (SOC). In SOC setting, the computation is outsourced to a set of specialized and powerful cloud servers and the service is availed on a pay-per-use basis. In this work, we explore PPML techniques in the SOC setting for widely used ML algorithms– Linear Regression, Logistic Regression, and Neural Networks.
    We propose BLAZE, a blazing fast PPML framework in the three server setting tolerating one malicious corruption over a ring (\Z{\ell}). BLAZE achieves the stronger security guarantee of fairness (all honest servers get the output whenever the corrupt server obtains the same). Leveraging an input-independent preprocessing phase, BLAZE has a fast input-dependent online phase relying on efficient PPML primitives such as: (i) A dot product protocol for which the communication in the online phase is independent of the vector size, the first of its kind in the three server setting; (ii) A method for truncation that shuns evaluating expensive circuit for Ripple Carry Adders (RCA) and achieves a constant round complexity. This improves over the truncation method of ABY3 (Mohassel et al., CCS 2018) that uses RCA and consumes a round complexity that is of the order of the depth of RCA.
    An extensive benchmarking of BLAZE for the aforementioned ML algorithms over a 64-bit ring in both WAN and LAN settings shows massive improvements over ABY3.

  6. HisTorε: Differentially Private and Robust Statistics Collection for Tor 2017 DifferentialPrivacy NDSS Tor ndss-symposium.org
    Akshaya Mani and Micah Sherr

    A large volume of existing research attempts to understand who uses Tor and how the network is used (and misused). However, conducting measurements on the live Tor network, if done improperly, can endanger the security and anonymity of the millions of users who depend on the network to enhance their online privacy. Indeed, several existing measurement studies of Tor have been heavily criticized for unsafe research practices.


    Tor needs privacy-preserving methods of gathering statistics. The recently proposed PrivEx system demonstrates how data can be safely collected on Tor using techniques from differential privacy. However, as we demonstrate in this paper, the integrity of the statistics reported by PrivEx is brittle under realistic deployment conditions. An adversary who operates even a single relay in the volunteer-operated anonymity network can arbitrarily influence the result of PrivEx queries. We argue that a safe and useful data collection mechanism must provide both privacy and integrity protections.


    This paper presents HisTor , a privacy-preserving statistics collection scheme based on ( ; )-differential privacy that is robust against adversarial manipulation. We formalize the security guarantees of HisTor and show using historical data from the Tor Project that HisTor provides useful data collection and reporting with low bandwidth and processing overheads.

  7. Pushing the Communication Barrier in Secure Computation using Lookup Tables 2017 2PC NDSS eprint.iacr.org
    Ghada Dessouky, Farinaz Koushanfar, Ahmad-Reza Sadeghi, Thomas Schneider, Shaza Zeitouni and Michael Zohner

    Secure two-party computation has witnessed significant efficiency improvements in the recent years. Current implementations of protocols with security against passive adversaries generate and process data much faster than it can be sent over the network, even with a single thread. This paper introduces novel methods to further reduce the communication bottleneck and round complexity of semi-honest secure two-party computation. Our new methodology creates a trade-off between communication and computation, and we show that the added computing cost for each party is still feasible and practicable in light of the new communication savings. We first improve communication for Boolean circuits with 2-input gates by factor 1.9x when evaluated with the protocol of Goldreich-Micali-Wigderson (GMW). As a further step, we change the conventional Boolean circuit representation from 2-input gates to multi-input/multi-output lookup tables (LUTs) which can be programmed to realize arbitrary functions. We construct two protocols for evaluating LUTs offering a trade-off between online communication and total communication. Our most efficient LUT-based protocol reduces the communication and round complexity by a factor 2-4x for several basic and complex operations. Our proposed scheme results in a significant overall runtime decrease of up to a factor of 3x on several benchmark functions.

  8. WireGuard: Next Generation Kernel Network Tunnel 2017 NDSS VPN ndss-symposium.org
    Jason A. Donenfeld

    WireGuard is a secure network tunnel, operating at layer 3, implemented as a kernel virtual network interface for Linux, which aims to replace both IPsec for most use cases, as well as popular user space and/or TLS-based solutions like OpenVPN, while being more secure, more performant, and easier to use. The virtual tunnel interface is based on a proposed fundamental principle of secure tunnels: an association between a peer public key and a tunnel source IP address. It uses a single round trip key exchange, based on NoiseIK, and handles all session creation transparently to the user using a novel timer state machine mechanism. Short pre-shared static keys Curve25519 points are used for mutual authentication in the style of OpenSSH. The protocol provides strong perfect forward secrecy in addition to a high degree of identity hiding. Transport speed is accomplished using ChaCha20Poly1305 authenticated-encryption for encapsulation of packets in UDP. An improved take on IP-binding cookies is used for mitigating denial of service attacks, improving greatly on IKEv2 and DTLS s cookie mechanisms to add encryption and authentication. The overall design allows for allocating no resources in response to received packets, and from a systems perspective, there are multiple interesting Linux implementation techniques for queues and parallelism. Finally, WireGuard can be simply implemented for Linux in less than 4,000 lines of code, making it easily audited and verified.

  9. SilentWhispers: Enforcing Security and Privacy in Decentralized Credit Networks 2017 Blockchains NDSS Privacy eprint.iacr.org
    Giulio Malavolta, Pedro Moreno-Sanchez, Aniket Kate, and Matteo Maffei

    Credit networks model transitive trust (or credit) between users in a distributed environment and have recently seen a rapid increase of popularity due to their flexible design and robustness against intrusion. They serve today as a backbone of real-world IOweYou transaction settlement networks such as Ripple and Stellar, which are deployed by various banks worldwide, as well as several other systems, such as spam-resistant communication protocols and Sybil-tolerant social networks. Current solutions, however, raise serious privacy concerns, as the network topology as well as the credit value of the links are made public for apparent transparency purposes and any changes are logged. In payment scenarios, for instance, this means that all transactions have to be public and everybody knows who paid what to whom.


    In this work, we question the necessity of a privacy-invasive transaction ledger. In particular, we present SilentWhispers, the first distributed, privacy-preserving credit network that does not require any ledger to protect the integrity of transactions. Yet, SilentWhispers guarantees integrity and privacy of link values and transactions even in the presence of distrustful users and malicious neighbors, whose misbehavior in changing link values is detected and such users can be held accountable. We formalize these properties as ideal functionalities in the universal composability framework and present a secure realization based on a novel combination of secret-sharing-based multiparty computation and digital signature chains. SilentWhispers can handle network churn, and it is efficient as demonstrated with a prototype implementation evaluated using payments data extracted from the currently deployed Ripple payment system.

  10. OBFUSCURO: A Commodity Obfuscation Engine on Intel SGX 2019 IntelSGX NDSS Obfuscation ORAM ndss-symposium.org
    Adil Ahmad and Byunggill Joe and Yuan Xiao and Yinqian Zhang and Insik Shin and Byoungyoung Lee

    Program obfuscation is a popular cryptographic construct with a wide range of uses such as IP theft prevention. Although cryptographic solutions for program obfuscation impose impractically high overheads, a recent breakthrough leveraging trusted hardware has shown promise. However, the existing solution is based on special-purpose trusted hardware, restricting its use-cases to a limited few.


    In this paper, we first study if such obfuscation is feasible based on commodity trusted hardware, Intel SGX, and we observe that certain important security considerations are not afforded by commodity hardware. In particular, we found that existing obfuscation/obliviousness schemes are insecure if directly applied to Intel SGX primarily due to side-channel limitations. To this end, we present OBFUSCURO, the first system providing program obfuscation using commodity trusted hardware, Intel SGX. The key idea is to leverage ORAM operations to perform secure code execution and data access. Initially, OBFUSCURO transforms the regular program layout into a side-channel-secure and ORAM-compatible layout. Then, OBFUSCURO ensures that its ORAM controller performs data oblivious accesses in order to protect itself from all memory-based side-channels. Furthermore, OBFUSCURO ensures that the program is secure from timing attacks by ensuring that the program always runs for a pre-configured time interval. Along the way, OBFUSCURO also introduces a systematic optimization such as register-based ORAM stash. We provide a thorough security analysis of OBFUSCURO along with empirical attack evaluations showing that OBFUSCURO can protect the SGX program execution from being leaked by access pattern-based and timing-based channels. We also provide a detailed performance benchmark results in order to show the practical aspects of OBFUSCURO.

  11. Constructing an Adversary Solver for Equihash 2019 Blockchains NDSS ProofOfWork ndss-symposium.org
    Xiaofei Bai and Jian Gao and Chenglong Hu and Liang Zhang

    Blockchain networks, especially cryptocurrencies, rely heavily on proof-of-work (PoW) systems, often as a basis to distribute rewards. These systems require solving specific puzzles, where Application Specific Integrated Circuits (ASICs) can be designed for performance or efficiency. Either way, ASICs surpass CPUs and GPUs by orders of magnitude, and may harm blockchain networks. Recently, Equihash is developed to resist ASIC solving with heavy memory usage. Although commercial ASIC solvers exist for its most popular parameter set, such solvers do not work under better ones, and are considered impossible under optimal parameters. In this paper, we inspect the ASIC resistance of Equihash by constructing a parameter-independent adversary solver design. We evaluate the product, and project at least 10x efficiency advantage for resourceful adversaries. We contribute to the security community in two ways: (1) by revealing the limitation of Equihash and raising awareness about its algorithmic factors, and (2) by demonstrating that security inspection is practical and useful on PoW systems, serving as a start point for future research and development.

  12. Anonymous Multi-Hop Locks for Blockchain Scalability and Interoperability 2019 Blockchains NDSS PaymentChannels Privacy ndss-symposium.org
    Giulio Malavolta and Pedro Moreno Sanchez and Clara Schneidewind and Aniket Kate and Matteo Maffei

    Tremendous growth in cryptocurrency usage is exposing the inherent scalability issues with permissionless blockchain technology. Payment-channel networks (PCNs) have emerged as the most widely deployed solution to mitigate the scalability issues, allowing the bulk of payments between two users to be carried out off-chain. Unfortunately, as reported in the literature and further demonstrated in this paper, current PCNs do not provide meaningful security and privacy guarantees [30], [40].


    In this work, we study and design secure and privacy-preserving PCNs. We start with a security analysis of existing PCNs, reporting a new attack that applies to all major PCNs, including the Lightning Network, and allows an attacker to steal the fees from honest intermediaries in the same payment path. We then formally define anonymous multi-hop locks (AMHLs), a novel cryptographic primitive that serves as a cornerstone for the design of secure and privacy-preserving PCNs. We present several provably secure cryptographic instantiations that make AMHLs compatible with the vast majority of cryptocurrencies. In particular, we show that (linear) homomorphic one-way functions suffice to construct AMHLs for PCNs supporting a script language (e.g., Ethereum). We also propose a construction based on ECDSA signatures that does not require scripts, thus solving a prominent open problem in the field.


    AMHLs constitute a generic primitive whose usefulness goes beyond multi-hop payments in a single PCN and we show how to realize atomic swaps and interoperable PCNs from this primitive. Finally, our performance evaluation on a commodity machine finds that AMHL operations can be performed in less than 100 milliseconds and require less than 500 bytes of communication overhead, even in the worst case. In fact, after acknowledging our attack, the Lightning Network developers have implemented our ECDSA-based AMHLs into their PCN. This demonstrates the practicality of our approach and its impact on the security, privacy, interoperability, and scalability of today’s cryptocurrencies.

  13. Vault: Fast Bootstrapping for the Algorand Cryptocurrency 2019 Blockchains Consensus NDSS ndss-symposium.org
    Derek Leung and Adam Suhl and Yossi Gilad and Nickolai Zeldovich

    Decentralized cryptocurrencies rely on participants to keep track of the state of the system in order to verify new transactions. As the number of users and transactions grows, this requirement becomes a significant burden, requiring users to download, verify, and store a large amount of data to participate.


    Vault is a new cryptocurrency design based on Algorand that minimizes these storage and bootstrapping costs for participants. Vault’s design is based on Algorand’s proof-of-stake consensus protocol and uses several techniques to achieve its goals. First, Vault decouples the storage of recent transactions from the storage of account balances, which enables Vault to delete old account state. Second, Vault allows sharding state across participants in a way that preserves strong security guarantees. Finally, Vault introduces the notion of stamping certificates, which allow a new client to catch up securely and efficiently in a proof-of-stake system without having to verify every single block.


    Experiments with a prototype implementation of Vault’s data structures show that Vault’s design reduces the bandwidth cost of joining the network as a full client by 99.7% compared to Bitcoin and 90.5% compared to Ethereum when downloading a ledger containing 500 million transactions.

  14. rORAM: Efficient Range ORAM with O(log2 N) Locality 2019 NDSS ORAM ndss-symposium.org
    Anrin Chakraborti and Adam J. Aviv and Seung Geol Choi and Travis Mayberry and Daniel S. Roche and Radu Sion

    Oblivious RAM protocols (ORAMs) allow a client to access data from an
    untrusted storage device without revealing to that device any information
    about their access pattern. Typically this is accomplished through random
    shuffling of the data such that the storage device cannot determine where
    individual blocks are located, resulting in a highly randomized access
    pattern. Storage devices however, are typically optimized for
    sequential access. A large number of random disk seeks
    during standard ORAM operation induce a substantial overhead.
    In this paper, we introduce rORAM, an ORAM specifically suited for
    accessing ranges of sequentially logical blocks while minimizing
    the number of random physical disk seeks. rORAM obtains significantly better asymptotic efficiency than prior designs (Asharov et al., ePrint 2017, Demertzis et al., CRYPTO 2018)
    reducing both the number of seeks and communication complexity by a multiplicative factor of $mathbb{O}(log N)$. An rORAM prototype is 30-50x times faster than Path ORAM for similar range-query workloads on local HDDs, 30x faster for local SSDs, and 10x
    faster for network block devices.


    rORAM’s novel disk layout can also speed up standard ORAM constructions, e.g., resulting in a 2x faster Path ORAM variant. Importantly, experiments demonstrate suitability for real world applications – rORAM is up to 5x faster running a file server and up to 11x faster running a range-query intensive video server workloads compared to standard Path ORAM.

  15. ConcurORAM: High-Throughput Stateless Parallel Multi-Client ORAM 2019 NDSS ORAM ndss-symposium.org
    Anrin Chakraborti and Radu Sion

    ConcurORAM is a parallel, multi-client oblivious RAM (ORAM) that
    eliminates waiting for concurrent stateless clients and allows over-
    all throughput to scale gracefully, without requiring trusted third
    party components (proxies) or direct inter-client coordination.
    A key insight behind ConcurORAM is the fact that, during
    multi-client data access, only a subset of the concurrently-
    accessed server-hosted data structures require access privacy
    guarantees. Everything else can be safely implemented as oblivi-
    ous data structures that are later synced securely and efficiently
    during an ORAM “eviction”.


    Further, since a major contributor to latency is the eviction
    – in which client-resident data is reshuffled and reinserted back
    encrypted into the main server database – ConcurORAM also
    enables multiple concurrent clients to evict asynchronously, in
    parallel (without compromising consistency), and in the back-
    ground without having to block ongoing queries.
    As a result, throughput scales well with increasing number of
    concurrent clients and is not significantly impacted by evictions.
    For example, about 65 queries per second can be executed in
    parallel by 30 concurrent clients, a 2x speedup over the state-of-
    the-art. The query access time for individual clients increases
    by only 2x when compared to a single-client deployment.

  16. Balancing Image Privacy and Usability with Thumbnail-Preserving Encryption 2019 FPE NDSS Privacy ndss-symposium.org
    Kimia Tajik and Akshith Gunasekaran and Rhea Dutta and Brandon Ellis and Rakesh B. Bobba and Mike Rosulek and Charles V. Wright and Wu-Chi Feng

    In this paper, we motivate the need for image encryption techniques that preserve certain visual features in images and hide all other information, to balance privacy and usability in the context of cloud-based image storage services. In particular, we introduce the concept of ideal or exact Thumbnail-Preserving Encryption (TPE), a special case of format-preserving encryption, and present a concrete construction. In TPE, a ciphertext is itself an image that has the same thumbnail as the plaintext (unecrypted) image, but that provably leaks nothing about the plaintext beyond its thumbnail. We provide a formal security analysis for the construction, and a prototype implementation to demonstrate compatibility with existing services. We also study the ability of users to distinguish between thumbnail images preserved by TPE. Our findings indicate that TPE is an efficient and promising approach to balance usability and privacy concerns for images. Our code and a demo are available at: http://photoencryption.org.

  17. Component-Based Formal Analysis of 5G-AKA: Channel Assumptions and Session Confusion 2019 5G CellularProtocols FormalVerification NDSS ndss-symposium.org
    Cas Cremers and Martin Dehnel-Wild

    The 5G mobile telephony standards are nearing completion; upon adoption these will be used by billions across the globe. Ensuring the security of 5G communication is of the utmost importance, building trust in a critical component of everyday life and national infrastructure.


    We perform a fine-grained formal analysis of 5G’s main authentication and key agreement protocol (5G-AKA), and provide the first models that explicitly consider all parties defined by the protocol specification. Our formal analysis reveals that the security of 5G-AKA critically relies on unstated assumptions on the inner workings of the underlying channels. In practice this means that following the 5G-AKA specification, a provider can easily and ‘correctly’ implement the standard insecurely, leaving the protocol vulnerable to a security-critical race condition. We then provide the first models and analysis considering component and channel compromise in 5G, the results of which further demonstrate the fragility and subtle trust assumptions of the 5G-AKA protocol.


    We propose formally verified fixes to the encountered issues, and we have worked with 3GPP to ensure that these fixes are adopted.

  18. Coconut: Threshold Issuance Selective Disclosure Credentials with Applications to Distributed Ledgers 2019 AnonymousCredentials Blockchains NDSS Privacy ndss-symposium.org
    Alberto Sonnino and Mustafa Al-Bassam and Shehar Bano and Sarah Meiklejohn and George Danezis

    Coconut is a novel selective disclosure credential scheme supporting distributed threshold issuance, public and private attributes, re-randomization, and multiple unlinkable selective attribute revelations. Coconut integrates with Blockchains to ensure confidentiality, authenticity and availability even when a subset of credential issuing authorities are malicious or offline. We implement and evaluate a generic Coconut smart contract library for Chainspace and Ethereum; and present three applications related to anonymous payments, electronic petitions, and distribution of proxies for censorship resistance.


    Coconut uses short and computationally efficient credentials, and our evaluation shows that most Coconut cryptographic primitives take just a few milliseconds on average, with verification taking the longest time (10 milliseconds).

  19. Analyzing Semantic Correctness with Symbolic Execution: A Case Study on PKCS#1 v1.5 Signature Verification 2019 FormalVerification NDSS Signatures ndss-symposium.org
    Sze Yiu Chau and Moosa Yahyazadeh and Omar Chowdhury and Aniket Kate and Ninghui Li

    We discuss how symbolic execution can be used to not only find low-level errors but also analyze the semantic correctness of protocol implementations. To avoid manually crafting test cases, we propose a strategy of meta-level search, which leverages constraints stemmed from the input formats to automatically generate concolic test cases. Additionally, to aid root-cause analysis, we develop constraint provenance tracking (CPT), a mechanism that associates atomic sub-formulas of path constraints with their corresponding source level origins. We demonstrate the power of symbolic analysis with a case study on PKCS#1 v1.5 signature verification. Leveraging meta-level search and CPT, we analyzed 15 recent open-source implementations using symbolic execution and found semantic flaws in 6 of them. Further analysis of these flaws showed that 4 implementations are susceptible to new variants of the Bleichenbacher low- exponent RSA signature forgery. One implementation suffers from potential denial of service attacks with purposefully crafted signatures. All our findings have been responsibly shared with the affected vendors. Among the flaws discovered, 6 new CVEs have been assigned to the immediately exploitable ones.

  20. The use of TLS in Censorship Circumvention 2019 Censorship Measurement NDSS TLS ndss-symposium.org
    Sergey Frolov and Eric Wustrow

    TLS, the Transport Layer Security protocol, has
    quickly become the most popular protocol on the Internet, already
    used to load over 70% of web pages in Mozilla Firefox. Due
    to its ubiquity, TLS is also a popular protocol for censorship
    circumvention tools, including Tor and Signal, among others.


    However, the wide range of features supported in TLS makes
    it possible to distinguish implementations from one another by
    what set of cipher suites, elliptic curves, signature algorithms, and
    other extensions they support. Already, censors have used deep
    packet inspection (DPI) to identify and block popular circumven-
    tion tools based on the fingerprint of their TLS implementation.


    In response, many circumvention tools have attempted to
    mimic popular TLS implementations such as browsers, but this
    technique has several challenges. First, it is burdensome to keep
    up with the rapidly-changing browser TLS implementations, and
    know what fingerprints would be good candidates to mimic.
    Second, TLS implementations can be difficult to mimic correctly,
    as they offer many features that may not be supported by the
    relatively lightweight libraries used in typical circumvention tools.
    Finally, dependency changes and updates to the underlying li-
    braries can silently impact what an application’s TLS fingerprint
    looks like, making it difficult for tools to control.


    In this paper, we collect and analyze real-world TLS traffic
    from over 11.8 billion TLS connections over 9 months to identify
    a wide range of TLS client implementations actually used on
    the Internet. We use our data to analyze TLS implementations
    of several popular censorship circumvention tools, including
    Lantern, Psiphon, Signal, Outline, Tapdance, and Tor (Snowflake
    and meek). We find that the many of these tools use TLS
    configurations that are easily distinguishable from the real-world
    traffic they attempt to mimic, even when these tools have put
    effort into parroting popular TLS implementations.


    To address this problem, we have developed a library, uTLS,
    that enables tool maintainers to automatically mimic other pop-
    ular TLS implementations. Using our real-world traffic dataset,
    we observe many popular TLS implementations we are able to
    correctly mimic with uTLS, and we describe ways our tool can
    more flexibly adopt to the dynamic TLS ecosystem with minimal
    manual effort.

  21. SABRE: Protecting Bitcoin against Routing Attacks 2019 Bitcoin Blockchains NDSS ndss-symposium.org
    Maria Apostolaki and Gian Marti and Jan Müller and Laurent Vanbever

    Nowadays Internet routing attacks remain practi- cally effective as existing countermeasures either fail to provide protection guarantees or are not easily deployable. Blockchain systems are particularly vulnerable to such attacks as they rely on Internet-wide communications to reach consensus. In particular, Bitcoin—the most widely-used cryptocurrency—can be split in half by any AS-level adversary using BGP hijacking.


    In this paper, we present SABRE, a secure and scalable Bitcoin relay network which relays blocks worldwide through a set of connections that are resilient to routing attacks. SABRE runs alongside the existing peer-to-peer network and is easily deployable. As a critical system, SABRE design is highly resilient and can efficiently handle high bandwidth loads, including Denial of Service attacks.


    We built SABRE around two key technical insights. First, we leverage fundamental properties of inter-domain routing (BGP) policies to host relay nodes: (i) in networks that are inherently protected against routing attacks; and (ii) on paths that are economically-preferred by the majority of Bitcoin clients. These properties are generic and can be used to protect other Blockchain-based systems. Second, we leverage the fact that relaying blocks is communication-heavy, not computation-heavy. This enables us to offload most of the relay operations to programmable network hardware (using the P4 programming language). Thanks to this hardware/software co-design, SABRE nodes operate seamlessly under high load while mitigating the effects of malicious clients.


    We present a complete implementation of SABRE together with an extensive evaluation. Our results demonstrate that SABRE is effective at securing Bitcoin against routing attacks, even with deployments of as few as 6 nodes.

  22. MBeacon: Privacy-Preserving Beacons for DNA Methylation Data 2019 DataAnalysis Genomics NDSS Privacy ndss-symposium.org
    I. Hagestedt and Y. Zhang and M. Humbert and P. Berrang and H. Tang and X. Wang and M. Backes

    The advancement of molecular profiling techniques fuels biomedical research with a deluge of data. To facilitate data sharing, the Global Alliance for Genomics and Health established the Beacon system, a search engine designed to help researchers find datasets of interest. While the current Beacon system only supports genomic data, other types of biomedical data, such as DNA methylation, are also essential for advancing our understanding in the field. In this paper, we propose the first Beacon system for DNA methylation data sharing: MBeacon. As the current genomic Beacon is vulnerable to privacy attacks, such as membership inference, and DNA methylation data is highly sensitive, we take a privacy-by-design approach to construct MBeacon. First, we demonstrate the privacy threat, by proposing a membership inference attack tailored specifically to unprotected methylation Beacons. Our experimental results show that 100 queries are sufficient to achieve a successful attack with AUC (area under the ROC curve) above 0.9. To remedy this situation, we propose a novel differential privacy mechanism, namely SVT^2, which is the core component of MBeacon. Extensive experiments over multiple datasets show that SVT^2 can successfully mitigate membership privacy risks without significantly harming utility. We further implement a fully functional prototype of MBeacon which we make available to the research community.

  23. Fine-Grained and Controlled Rewriting in Blockchains: Chameleon-Hashing Gone Attribute-Based 2019 Blockchains NDSS ndss-symposium.org
    David Derler and Kai Samelin and Daniel Slamanig and Christoph Striecks

    Blockchain technologies recently received a considerable amount of attention. While the initial focus was mainly on the use of blockchains in the context of cryptocurrencies such as Bitcoin, application scenarios now go far beyond this. Most blockchains have the property that once some object, e.g., a block or a transaction, has been registered to be included into the blockchain, it is persisted and there are no means to modify it again. While this is an essential feature of most blockchain scenarios, it is still often desirable—at times it may be even legally required–to allow for breaking this immutability in a controlled way.


    Only recently, Ateniese et al. (EuroS&P 2017) proposed an elegant solution to this problem on the block level. Thereby, the authors replace standard hash functions with so-called chameleon-hashes (Krawczyk and Rabin, NDSS 2000). While their work seems to offer a suited solution to the problem of controlled re-writing of blockchains, their approach is too coarse-grained in that it only offers an all-or-nothing solution. We revisit this idea and introduce the novel concept of policy-based chameleon-hashes (PBCH). PBCHs generalize the notion of chameleon-hashes by giving the party computing a hash the ability to associate access policies to the generated hashes. Anyone who possesses enough privileges to satisfy the policy can then find arbitrary collisions for a given hash. We then apply this concept to transaction-level rewriting within blockchains, and thus support fine-grained and controlled modifiability of blockchain objects.


    Besides modeling PBCHs, we present a generic construction of PBCHs (using a strengthened version of chameleon-hashes with ephemeral trapdoors which we also introduce), rigorously prove its security, and instantiate it with efficient building blocks. We report first implementation results.

  24. maTLS: How to Make TLS middlebox-aware? 2019 NDSS TLS ndss-symposium.org
    Hyunwoo Lee and Zachary Smith and Junghwan Lim and Gyeongjae Choi and Selin Chun and Taejoong Chung and Ted "Taekyoung" Kwon

    Middleboxes (MBs) are widely deployed in order to enhance security and performance in networking. However, as the communications over the TLS become increasingly common, the end-to-end channel model of the TLS undermines the efficacy of MBs. Existing solutions, such as `split TLS’ that intercepts TLS sessions, often introduce significant security risks by installing a custom root certificate or sharing a private key. Many studies have confirmed the vulnerabilities of combining the TLS with MBs, which include certificate validation failures, unwanted content modification, and using obsolete ciphersuites. To address the above issues, we introduce an MB-aware TLS protocol, dubbed maTLS, that allows MBs to participate in the TLS in a visible and accountable fashion. Every participating MB now splits a session into two segments with its own security parameters in collaboration with the two endpoints. However, the session is still secure as the maTLS protocol is designed to achieve the authentication of MBs, the audit of MBs’ operations, and the verification of security parameters of segments. We carry out testbed-based experiments to show that maTLS achieves the above security goals with marginal overhead. We also prove the security model of maTLS by using Tamarin, a security verification tool.

  25. TLS-N: Non-repudiation over TLS Enabling Ubiquitous Content Signing 2018 NDSS TLS eprint.iacr.org
    Hubert Ritzdorf and Karl Wüst and Arthur Gervais and Guillaume Felley and Srdjan Capkun

    An internet user wanting to share observed content is typically restricted to primitive techniques such as screenshots, web caches or share button-like solutions. These acclaimed proofs, however, are either trivial to falsify or require trust in centralized entities (e.g., search engine caches).


    This motivates the need for a seamless and standardized internet-wide non-repudiation mechanism, allowing users to share data from news sources, social websites or financial data feeds in a provably secure manner.


    Additionally, blockchain oracles that enable data-rich smart contracts typically rely on a trusted third party (e.g., TLSNotary or Intel SGX). A decentralized method to transfer web-based content into a permissionless blockchain without additional trusted third party would allow for smart contract applications to flourish.


    In this work, we present TLS-N, the first TLS extension that provides secure non-repudiation and solves both of the mentioned challenges. TLS-N generates non-interactive proofs about the content of a TLS session that can be efficiently verified by third parties and blockchain based smart contracts. As such, TLS-N increases the accountability for content provided on the web and enables a practical and decentralized blockchain oracle for web content. TLS-N is compatible with TLS 1.3 and adds a minor overhead to a typical TLS session. When a proof is generated, parts of the TLS session (e.g., passwords, cookies) can be hidden for privacy reasons, while the remaining content can be verified.


    Practical demonstrations can be found at https://tls-n.org/.