Environmentally Keyed Malware

Posted on by

Our paper (with Jeremy Blackthorne, Ben Kaiser, and Bulent Yener) on how malware authenticates was  published at Latincrypt 2017.  Abstract below:

Abstract: Malware needs to execute on a target machine while simultaneously keeping its payload confidential from a malware analyst. Standard encryption can be used to ensure the confidentiality, but it does not address the problem of hiding the key. Any analyst can find the decryption key if it is stored in the malware or derived in plain view.

One approach is to derive the key from a part of the environment which changes when the analyst is present. Such malware derives a key from the environment and encrypts its true functionality under this key.

In this paper, we present a formal framework for environmental authentication. We formalize the interaction between malware and analyst in three settings: 1) blind: in which the analyst does not have access to the target environment, 2) basic: where the analyst can load a single analysis toolkit on an effected target, and 3) resettable: where the analyst can create multiple copies of an infected environment. We show necessary and sufficient conditions for malware security in the blind and basic games and show that even under mild conditions, the analyst can always win in the resettable scenario.

Catching MPC Cheaters

Posted on by

Our paper (with Rob Cunningham and Sophia Yakoubov) on augmenting security of MPC will be published at ICITS 2017.  Abstract below:

Abstract: Secure multi-party computation (MPC) protocols do not completely prevent malicious parties from cheating and disrupting the computation. A coalition of malicious parties can repeatedly cause the computation to abort or provide an input that does not correspond to reality. We augment MPC with three new properties to discourage cheating. First is a strengthening of identifiable abort, called completely identifiable abort, where all parties who do not follow the protocol will be identified as cheaters by each honest party, even if there are more cheaters than honest parties. The second is completely identifiable auditability, which means that a third party can, given the computation output and its additive share decomposition, determine whether the computation was performed correctly (and who cheated if it was not) by looking at a transcript of the computation.  The third is openability, which means that a distinguished coalition of parties can recover the MPC inputs in the extreme setting when the parties are discovered to have lied about their inputs (e.g. by a real-world event contradicting the output of the MPC).

We construct the first (efficient) MPC protocol achieving these properties.  Our scheme is built on the SPDZ protocol (Damgard et al., Crypto 2012), which leverages an offline (computation-independent) pre-processing phase to speed up the online computation. Our protocol is optimistic: it has the same communication and computation complexity in the online phase as SPDZ when no parties cheat. If cheating does occur, each honest party performs only local computation to identify cheaters.

Our main technical tool is a new locally identifiable secret sharing scheme (as defined by Ishai, Ostrovsky, and Zikas (TCC 2012)) which we call commitment enhanced secret sharing, or CESS. Each CESS share contains an additive share (as in SPDZ), and additionally includes linearly homomorphic commitments to every additive share. Each CESS share also contains the decommitment value for the commitment to the corresponding additive share. These commitments enable local identification during reconstruction; by the binding property of the commitment scheme, no party should be able to convince any other party of the validity of an altered additive share.  CESS enables MPC with completely identifiable abort; all parties whose claimed output shares do not match their output share commitments are identified as cheaters.

The work of Baum, Damgard, and Orlandi (SCN 2014) introduces the concept of auditability, which allows a third party to verify that the computation was executed correctly, but not to identify the cheaters if it was not.  We enable the third party to identify the cheaters by augmenting the scheme of Baum, Damg{\aa}rd, and Orlandi with CESS. We add openability through the use of verifiable encryption and specialized zero-knowledge proofs.

SoK: Cryptographically Protected Database Search

Posted on by

Excited to announce that our paper on protected database search will be appear at 2017 IEEE Security and Privacy.

Joint work with Mayank Varia, Arkady Yerukhimovich, Emily Shen, Ariel Hamlin, Vijay Gadepally, Richard Shay, John, Darby Mitchell, and Robert K. Cunningham

Abstract:

Protected database search systems cryptographically isolate the roles of reading from, writing to, and administering the database. This separation limits unnecessary administrator access and protects data in the case of system breaches. Since protected search was introduced in 2000, the area has grown rapidly; systems are offered by academia, start-ups, and established companies.

However, there is no best protected search system or set of techniques. Design of such systems is a balancing act between security, functionality, performance, and usability. This challenge is made more difficult by ongoing database specialization, as some users will want the functionality of SQL, NoSQL, or NewSQL databases. This database evolution will continue, and the protected search community should be able to quickly provide functionality consistent with newly invented databases.

At the same time, the community must accurately and clearly characterize the tradeoffs between different approaches. To address these challenges, we provide the following contributions:

1) An identification of the important primitive operations across database paradigms. We find there are a small number of \emph{base} operations that can be used and combined to support a large number of database paradigms.

2) An evaluation of the current state of protected search systems in implementing these base operations. This evaluation describes the main approaches and tradeoffs for each base operation. Furthermore, it puts protected search in the context of unprotected search, identifying key gaps in functionality.

3) An analysis of attacks against protected search for different base queries.

4) A roadmap and tools for transforming a protected search system into a protected database, including an open-source performance evaluation platform and initial user opinions of protected search.

Public Key Cryptography with Noisy Private Keys

Posted on by

New Paper: Public Key Cryptography with Noisy Private Keys

Abstract: Passwords bootstrap symmetric and asymmetric cryptography, tying keys to an individual user. Biometrics are intended to strengthen this tie. Unfortunately, biometrics exhibit noise between repeated readings. Fuzzy extractors (Dodis et al., Eurocrypt 2004) derive stable symmetric keys from noisy sources.

We ask if it is also possible for noisy sources to directly replace private keys in asymmetric cryptosystems. We propose a new primitive called public-key cryptosystems with noisy keys. Such a cryptosystem functions when the private key varies according to some metric. An intuitive solution is to combine a fuzzy extractor with a public key cryptosystem. Unfortunately, fuzzy extractors need static helper information to account for noise. This helper information creates fundamental limitations on the resulting cryptosytems.

To overcome these limitations, we directly construct public-key encryption and digital signature algorithms with noisy keys. The core of our constructions is a computational version of the fuzzy vault (Juels and Sudan, Designs, Codes, and Cryptography 2006). Security of our schemes is based on graded encoding schemes (Garg et al., Eurocrypt 2013, Garg et al., TCC 2016). Importantly, our public-key encryption algorithm is based on a weaker model of grading encoding. If functional encryption or indistinguishable obfuscation exist in this weaker model, they also exist in the standard model.

In addition, we use the computational fuzzy vault to construct the first reusable fuzzy extractor (Boyen, CCS 2004) supporting a linear fraction of errors.

Joint work with Charles Herder, Marten van Dijk, and Srinivas Devadas