International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Gene Tsudik

Publications

Year
Venue
Title
2011
PKC
2010
ASIACRYPT
2010
EPRINT
Secure Code Update for Embedded Devices via Proofs of Secure Erasure
Daniele Perito Gene Tsudik
Remote attestation is the process of verifying internal state of a remote embedded device. It is an important component of many security protocols and applications. Although techniques assisted by specialized secure hardware are effective, they not yet viable for low-cost embedded devices. One notable alternative is software-based attestation which is both less costly and more efficient. However, recent results identified weaknesses in some proposed methods, thus showing that security of remote software attestation remains a challenge. Inspired by these developments, this paper explores a different approach that relies neither on secure hardware nor on tight timing constraints. By taking advantage of the bounded memory/storage model of low-cost embedded devices and assuming a small amount of read-only memory (ROM), our uses a new primitive -- Proofs of Secure Erasure (PoSE-s). We show that, even though our PoSE-based approach is effective and provably secure, it is not cheap. However, it is particularly well-suited and practical for two other related tasks: secure code update and secure memory/storage erasure. We consider several flavors of PoSE-based protocols and demonstrate their feasibility in the context of existing commodity embedded devices.
2010
EPRINT
(If) Size Matters: Size-Hiding Private Set Intersection
Modern society is increasingly dependent on, and fearful of, the availability of electronic information. There are numerous examples of situations where sensitive data must be – sometimes reluctantly – shared between two or more entities without mutual trust. As often happens, the research community has foreseen the need for mechanisms to enable limited (privacy-preserving) sharing of sensitive information and a number of effective (if not always efficient) solutions have been proposed. Among them, Private Set Intersection techniques are particularly appealing for scenarios where two parties wish to compute an intersection of their respective sets of items without revealing to each other any other information. Thus far, ”any other information” has been interpreted to mean any information about items not in the intersection. In this paper, we motivate the need for Private Set Intersection with stronger privacy properties that include hiding of the set size held by one of the two entities (Client). This new and important privacy feature turns out to be attainable at relative low additional cost. We illustrate a pair of concrete SHI-PSI (Size-Hiding Private Set Intersection) protocols that offer a trade-off between stronger privacy and better efficiency. Both protocols are provably secure under very standard cryptographic assumptions. We demonstrate their practicality via experimental results obtained from a prototype implementation. We also consider size-hiding in a group PSI setting and construct a Group SHI-PSI extension that incurs surprisingly low overhead.
2009
EPRINT
Reducing RFID Reader Load with the Meet-in-the-Middle Strategy
In almost any RFID system, a reader needs to identify, and optionally authenticate, a multitude of tags. If each tag has a unique secret, identification and authentication are trivial, however, the reader (or a back-end server) needs to perform a brute-force search for each tag-reader interaction. In this paper, we suggest a simple, efficient and secure technique that reduces reader computation to $O(\sqrt N \cdot \log N)$. Our technique is based on the well-known ``meet-in-the-middle'' strategy used in the past to attack certain symmetric ciphers.
2008
EPRINT
Scalable and Efficient Provable Data Possession
Storage outsourcing is a rising trend which prompts a number of interesting security issues, many of which have been extensively investigated in the past. However, Provable Data Possession (PDP) is a topic that has only recently appeared in the research literature. The main issue is how to frequently, efficiently and securely verify that a storage server is faithfully storing its client’s (potentially very large) outsourced data. The storage server is assumed to be untrusted in terms of both security and reliability. (In other words, it might maliciously or accidentally erase hosted data; it might also relegate it to slow or off-line storage.) The problem is exacerbated by the client being a small computing device with limited resources. Prior work has addressed this problem using either public key cryptography or requiring the client to outsource its data in encrypted form. In this paper, we construct a highly efficient and provably secure PDP technique based entirely on symmetric key cryptography, while not requiring any bulk encryption. Also, in contrast with its predecessors, our PDP technique allows outsourcing of dynamic data, i.e, it efficiently supports operations, such as block modification, deletion and append.
2008
EPRINT
DISH: Distributed Self-Healing in Unattended Sensor Networks
Di Ma Gene Tsudik
Unattended wireless sensor networks (UWSNs) operating in hostile environments face the risk of compromise. % by a mobile adversary. Unable to off-load collected data to a sink or some other trusted external entity, sensors must protect themselves by attempting to mitigate potential compromise and safeguarding their data. In this paper, we focus on techniques that allow unattended sensors to recover from intrusions by soliciting help from peer sensors. We define a realistic adversarial model and show how certain simple defense methods can result in sensors re-gaining secrecy and authenticity of collected data, despite adversary's efforts to the contrary. We present an extensive analysis and a set of simulation results that support our observations and demonstrate the effectiveness of proposed techniques.
2008
EPRINT
A New Approach to Secure Logging
Di Ma Gene Tsudik
The need for secure logging is well-understood by the security professionals, including both researchers and practitioners. The ability to efficiently verify all (or some) log entries is important to any application employing secure logging techniques. In this paper, we begin by examining state-of-the-art in secure logging and identify some problems inherent to systems based on trusted third-party servers. We then propose a different approach to secure logging based upon recently developed Forward-Secure Sequential Aggregate (FssAgg) authentication techniques. Our approach offers both space-efficiency and provable security. We illustrate two concrete schemes -- one private-verifiable and one public-verifiable -- that offer practical secure logging without any reliance on on-line trusted third parties or secure hardware. We also investigate the concept of immutability in the context of forward secure sequential aggregate authentication to provide finer grained verification. Finally, we report on some experience with a prototype built upon a popular code version control system.
2008
EPRINT
Survival in the Wild: Robust Group Key Agreement in Wide-Area Networks
Jihye Kim Gene Tsudik
Group key agreement (GKA) allows a set of players to establish a shared secret and thus bootstrap secure group communication. GKA is very useful in many types of peer group scenarios and applications. Since all GKA protocols involve multiple rounds, robustness to player failures is important and desirable. A robust group key agreement (RGKA) protocol runs to completion even if some players fail during protocol execution. Previous work yielded constant-round RGKA protocols suitable for the LAN setting, assuming players are homogeneous, failure probability is uniform and player failures are independent. However, in a more general widearea network (WAN) environment, heterogeneous hardware/software and communication facilities can cause wide variations in failure probability among players. Moreover, congestion and communication equipment failures can result in correlated failures among subsets of GKA players. In this paper, we construct the first RGKA protocol that supports players with different failure probabilities, spread across any LAN/WAN combination, while also allowing for correlated failures among subgroups of players. The proposed protocol is efficient (2 rounds) and provably secure. We evaluate its robustness and performance both analytically and via simulations.
2008
EPRINT
Playing Hide-and-Seek with a Focused Mobile Adversary: Maximizing Data Survival in Unattended Sensor Networks
Some sensor network settings involve disconnected or unattended operation with periodic visits by a mobile sink. An unattended sensor network operating in a hostile environment can collect data that represents a high-value target for the adversary. Since an unattended sensor can not immediately off-load sensed data to a safe external entity (such as a sink), the adversary can easily mount a focused attack aiming to erase or modify target data. To maximize chances of data survival, sensors must collaboratively attempt to mislead the adversary and hide the location, the origin and the contents of collected data. In this paper, we focus on applications of well-known security techniques to maximize chances of data survival in unattended sensor networks, where sensed data can not be off-loaded to a sink in real time. Our investigation yields some interesting insights and surprising results. The highlights of our work are: (1) thorough exploration of the data survival challenge, (2) exploration of the design space for possible solutions, (3) construction of several practical and effective techniques, and (4) their evaluation.
2008
EPRINT
Maximizing data survival in Unattended Wireless Sensor Networks against a focused mobile adversary
Some sensor network settings involve disconnected or unattended operation with periodic visits by a mobile sink. An unattended sensor network operating in a hostile environment can collect data that represents a high-value target for the adversary. Since an unattended sensor can not immediately off-load sensed data to a safe external entity (such as a sink), the adversary can easily mount a focused attack aiming to erase or modify target data. To maximize chances of data survival, sensors must collaboratively attempt to mislead the adversary and hide the location, the origin and the contents of collected data. In this paper, we focus on applications of well-known security techniques to maximize chances of data survival in unattended sensor networks, where sensed data can not be off-loaded to a sink in real time. Our investigation yields some interesting insights and surprising results. The highlights of our work are: (1) thorough exploration of the data survival challenge, (2) exploration of the design space for possible solutions, (3) construction of several practical and effective techniques, and (4) their evaluation.
2007
EPRINT
Forward-Secure Sequential Aggregate Authentication
Di Ma Gene Tsudik
Wireless sensors are employed in a wide range of applications. One common feature of most sensor settings is the need to communicate sensed data to some collection point or sink. This communication can be direct (to a mobile collector) or indirect -- via other sensors towards a remote sink. In either case, a sensor might not be able to communicate to a sink at will. Instead it collects data and waits (for a potentially long time) for a signal to upload accumulated data directly. In a hostile setting, a sensor may be compromised and its post-compromise data can be manipulated. One important issue is Forward Security -- how to ensure that pre-compromise data cannot be manipulated? Since a typical sensor is limited in storage and communication facilities, another issue is how to minimize resource consumption due to accumulated data. It turns out that current techniques are insufficient to address both challenges. To this end, we explore the notion of Forward-Secure Sequential Aggregate (FssAgg) Authentication Schemes. We consider FssAgg authentication schemes in the contexts of both conventional and public key cryptography and construct a FssAgg MAC scheme and a FssAgg signature scheme, each suitable under different assumptions. This work represents the initial investigation of Forward-Secure Aggregation and, although the proposed schemes are not optimal, it opens a new direction for follow-on research.
2007
EPRINT
HAPADEP: Human Asisted Pure Audio Device Pairing
The number and diversity of electronic gadgets has been steadily increasing and they are becoming indispensable to more and more professionals and non-professionals alike. At the same time, there has been fairly little progress in secure pairing of such devices. The pairing challenge revolves around establishing on-the-fly secure communication without any trusted (on- or off-line) third parties between devices that have no prior association. The main security issue is the danger of so-called Man-in-the-Middle (MiTM) attacks, whereby an adversary impersonates one of the devices by inserting itself into the pairing protocol. One basic approach to countering these MiTM attacks is to involve the user in the pairing process. Therein lies the usability challenge since it is natural to minimize user burden. Previous research yielded some interesting secure pairing techniques, some of which ask too much of the human user, while others assume availability of specialized equipment (e.g., wires, photo or video cameras) on devices. Furthermore, all prior methods assumed the existence of a common digital (humanimperceptible) communication medium, such as Infrared, 802.11 or Bluetooth. In this paper we introduce a very simple technique called HAPADEP (Human-Assisted Pure Audio Device Pairing). It places very little burden on the human user and requires no common means of electronic communication. Instead, HAPADEP uses the audio channel to exchange both data and verification information among devices. It makes secure pairing possible even if devices are equipped only with a microphone and a speaker. Despite its simplicity, a number of interesting issues arise in the design of HAPADEP. We discuss design and implementation highlights as well as usability features and limitations.
2007
EPRINT
BEDA: Button-Enabled Device Pairing
Secure initial pairing of electronic gadgets is a challenging problem, especially considering lack of any common security infrastructure. The main security issue is the threat of so-called Man-in-the-Middle (MiTM) attacks, whereby an attacker inserts itself into the pairing protocol by impersonating one of the legitimate parties. A number of interesting techniques have been proposed, all of which involve the user in the pairing process. However, they are inapplicable to many common scenarios where devices to-be-paired do not possess required interfaces, such as displays, speakers, cameras or microphones. In this paper, we introduce BEDA (Button-Enabled Device Association), a protocol suite for secure pairing devices with minimal user interfaces. The most common and minimal interface available on wide variety of devices is a single button. BEDA protocols can accommodate pairing scenarios where one (or even both) devices only have a single button as their "user interface". Our usability study demonstrates that BEDA protocols involve very little human burden and are quite suitable for ordinary users.
2006
EPRINT
Remarks on "Analysis of One Popular Group Signature Scheme'' in Asiacrypt 2006
In \cite{Cao}, a putative framing ``attack'' against the ACJT group signature scheme \cite{ACJT00} is presented. This note shows that the attack framework considered in \cite{Cao} is \emph{invalid}. As we clearly illustrate, there is \textbf{no security weakness} in the ACJT group signature scheme as long as all the detailed specifications in \cite{ACJT00} are being followed.
2006
EPRINT
A Family of Dunces: Trivial RFID Identification and Authentication Protocols
Gene Tsudik
Security and privacy in RFID systems is an important and active research area. A number of challenges arise due to the extremely limited computational, storage and communication abilities of a typical RFID tag. This paper describes a step-by-step construction of a family of simple protocols for inexpensive untraceable identification and authentication of RFID tags. This work is aimed primarily at RFID tags that are capable of performing a small number of inexpensive conventional (as opposed to public key) cryptographic operations. It also represents the first result geared for so-called {\em batch mode} of RFID scanning whereby the identification (and/or authentication) of tags is delayed. Proposed protocols involve minimal interaction between a tag and a reader and place very low computational burden on the tag. Notably, they also impose low computational load on back-end servers.
2006
EPRINT
Simple and Flexible Private Revocation Checking
John Solis Gene Tsudik
Digital certificates signed by trusted certification authorities (CAs) are used for multiple purposes, most commonly for secure binding of public keys to names and other attributes of their owners. Although a certificate usually includes an expiration time, it is not uncommon that a certificate needs to be revoked prematurely. For this reason, whenever a client (user or program) needs to assert the validity of another party’s certificate, it performs revocation checking. There are many revocation techniques varying in both the operational model and underlying data structures. One common feature is that a client typically contacts an on-line third party (trusted, untrusted or semi-trusted), identifies the certificate of interest and obtains some form of a proof of either revocation or validity (non-revocation) for the certificate in question. While useful, revocation checking can leak potentially sensitive information. In particular, third parties of dubious trustworthiness discover two things: (1) the identity of the party posing the query, as well as (2) the target of the query. The former can be easily remedied with techniques such as onion routing or anonymous web browsing. Whereas, hiding the target of the query is not as obvious. Arguably, a more important loss of privacy results from the third party’s ability to tie the source of the revocation check with the query’s target. (Since, most likely, the two are about to communicate.) This paper is concerned with the problem of privacy in revocation checking and its contribution is two-fold: it identifies and explores the loss of privacy inherent in current revocation checking, and, it constructs a simple, efficient and flexible privacy-preserving component for one well-known revocation method.
2006
EPRINT
On Security of Sovereign Joins
Einar Mykletun Gene Tsudik
The goal of a sovereign join operation is to compute a query across independent database relations such that nothing beyond the join results is revealed. Each relation involved in a sovereign join is owned by a distinct entity and the party posing the query is distinct from the relation owners; it is not permitted to access the original relations. One notable recent research result proposed a secure technique for executing sovereign joins. It entails data owners sending their relations to an independent database service provider which executes a sovereign join with the aid of a tamper-resistant secure coprocessor. This achieves the goal of preventing information leakage during query execution. However, as we show in this paper, the proposed technique is actually insecure as it fails to prevent an attacker from learning the query results. We also suggest some measures to remedy the security problems.
2005
EPRINT
Flexible Framework for Secret Handshakes (Multi-Party Anonymous and Un-observable Authentication)
Gene Tsudik Shouhuai Xu
In the society increasingly concerned with the erosion of privacy, privacy-preserving techniques are becoming very important. This motivates research in cryptographic techniques offering built-in privacy. A secret handshake is a protocol whereby participants establish a secure, anonymous and unobservable communication channel only if they are members of the same group. This type of ``private" authentication is a valuable tool in the arsenal of privacy-preserving cryptographic techniques. Prior research focused on 2-party secret handshakes with one-time credentials. This paper breaks new ground on two accounts: (1) it shows how to obtain secure and efficient secret handshakes with reusable credentials, and (2) it represents the first treatment of group (or {\em multi-party}) secret handshakes, thus providing a natural extension to the secret handshake technology. An interesting new issue encountered in multi-party secret handshakes is the need to ensure that all parties are indeed distinct. (This is a real challenge since the parties cannot expose their identities.) We tackle this and other challenging issues in constructing GCD -- a flexible framework for secret handshakes. The proposed framework lends itself to many practical instantiations and offers several novel and appealing features such as self-distinction and strong anonymity with reusable credentials. In addition to describing the motivation and step-by-step construction of the framework, this paper provides a thorough security analysis and illustrates two concrete framework instantiations.
2005
EPRINT
Revisiting Oblivious Signature-Based Envelopes
Samad Nasserian Gene Tsudik
Secure, anonymous and unobservable communication is becoming increasingly important due to the gradual erosion of privacy in many aspects of everyday life. This prompts the need for various anonymity- and privacy-enhancing techniques, e.g., group signatures, anonymous e-cash and secret handshakes. In this paper, we investigate an interesting and practical cryptographic construct Oblivious Signature-Based Envelopes (OS-BEs) recently introduced in [15]. OSBEs are very useful in anonymous communication since they allow a sender to communicate information to a receiver such that the receiver s rights (or roles) are unknown to the sender. At the same time, a receiver can obtain the information only if it is authorized to access it. This makes OSBEs a natural fit for anonymity-oriented and privacy-preserving applications, such as Automated Trust Negotiation and Oblivious Subscriptions. Previous results yielded three OSBE constructs: one based on RSA and two based on Identity-Based Encryption (IBE). Our work focuses on the ElGamal signature family: we succeed in constructing practical and secure OSBE schemes for several well-known signature schemes, including: Schnorr, Nyberg-Rueppel, ElGamal and DSA. As experiments with the prototype implementation il-lustrate, our schemes are more efficient than previous techniques. Furthermore, we show that some OSBE schemes, despite offering affiliation privacy for the receiver, introduce no additional cost over schemes that do not offer this feature.
2005
EPRINT
DSAC: An Approach to Ensure Integrity of Outsourced Databases using Signature Aggregation and Chaining
Maithili Narasimha Gene Tsudik
Database outsourcing is an important emerging trend which involves data owners delegating their data management needs to an external service provider. In this model, a service provider hosts clients' databases and offers mechanisms to create, store, update and access (query) outsourced databases. Since a service provider is almost never fully trusted, security and privacy of outsourced data are important concerns. A core security requirement is the integrity and authenticity of outsourced databases. Whenever someone queries a hosted database, the results must be demonstrably authentic (with respect to the actual data owner) to ensure that the data has not been tampered with. Furthermore, the results must carry a proof of completeness which will allow the querier to verify that the server has not omitted any valid tuples that match the query predicate. Notable prior research (\cite{DpGmMcSs00, McNgDpGmKwSs02, PanTan04}) focused on so-called \textit{Authenticated Data Structures}. Another prior approach involved the use of special digital signature schemes. In this paper, we extend the state-of-the-art to provide both authenticity and completeness guarantees of query replies. Our work also analyzes the new approach for various base query types and compares the new approach with Authenticated Data Structures.\footnote{We also point out some possible security flaws in the approach suggested in the recent work of \cite{PanTan04}.}
2005
EPRINT
Loud and Clear: Human-Verifiable Authentication Based on Audio
Secure pairing of electronic devices that lack any previous association is a challenging problem which has been considered in many contexts and in various flavors. In this paper, we investigate an alternative and complementary approach--the use of the audio channel for human-assisted authentication of previously un-associated devices. We develop and evaluate a system we call Loud-and-Clear (L&C) which places very little demand on the human user. L&C involves the use of a text-to-speech (TTS) engine for vocalizing a robust-sounding and syntactically-correct (English-like) sentence derived from the hash of a device's public key. By coupling vocalization on one device with the display of the same information on another device, we demonstrate that L&C is suitable for secure device pairing (e.g., key exchange) and similar tasks. We also describe several common use cases, provide some performance data for our prototype implementation and discuss the security properties of L&C.
2004
ASIACRYPT
2004
EPRINT
Signature Bouquets: Immutability for Aggregated/Condensed Signatures
Database outsourcing is a popular industry trend which involves organizations delegating their data management needs to an external service provider. In this model, a service provider hosts its clients? databases and offers mechanisms for clients to create, store, update and access (query) their databases. Since a service provider is almost never fully trusted, security and privacy of outsourced data are important concerns. This paper focuses on integrity and authenticity issues in outsourced databases. Whenever someone queries a hosted database, the returned results must be demonstrably authentic: the querier needs to establish ? in an efficient manner ? that both integrity and authenticity (with respect to the actual data owner) are assured. To this end, some recent work examined two relevant signature schemes: one based on a condensed variant of batch RSA and the other ? on aggregated signature scheme by Boneh, et al. In this paper, we introduce the notion of immutability for aggregated signature schemes. Immutability refers to the difficulty of computing new valid aggregated signatures from a set of other aggregated signatures. This is an important feature, particularly for outsourced databases, as lack thereof would enable a frequent querier to eventually amass enough aggregated signatures to answer other (un-posed) queries, thus becoming a de facto service provider. Since the schemes considered in [19] do not offer immutability, we propose several practical methods to achieve it.
2004
EPRINT
Secret Handshakes from CA-Oblivious Encryption
Secret handshake protocols were recently introduced by Balfanz et al. [IEEE, Oakland 2003] to allow members of the same group to authenticate each other *secretly*, in the sense that someone who is not a group member cannot tell, by engaging some party in the handshake protocol, whether that party is a member of the group. On the other hand, any two parties who are members of the same group will recognize each other as members. Thus, secret handshakes can be used in any scenario where group members need to identify each other without revealing their group affiliations to outsiders. The secret handshake protocol of Balfanz et al. relies on a Bilinear Diffie-Hellman assumption (in ROM) on certain elliptic curves. We show how to build secret handshake protocols secure under more standard cryptographic assumption of Computational Diffie Hellman(CDH), using a novel tool of CA-oblivious public key encryption, which is an encryption scheme s.t. neither the public key nor the ciphertext reveal any information about the Certification Authority (CA) which certified the public key. We construct such CA-oblivious encryption, and hence a handshake scheme, based on CDH (in ROM). The new scheme takes 3 communication rounds like the scheme of Balfanz et al., but it is about twice cheaper computationally, and it relies on a weaker computational assumption.
2003
ASIACRYPT
2003
EPRINT
Accumulating Composites and Improved Group Signing
Gene Tsudik Shouhuai Xu
Constructing practical and provably secure group signature schemes has been a very active research topic in recent years. A group signature can be viewed as a digital signature with certain extra properties. Notably, anyone can verify that a signature is generated by a legitimate group member, while the actual signer can only be identified (and linked) by a designated entity called a group manager. Currently, the most efficient group signature scheme available is due to Camenisch and Lysyanskaya \cite{CL02}. It is obtained by integrating a novel dynamic accumulator with the scheme by Ateniese, et al. \cite{ACJT00}. In this paper, we construct a dynamic accumulator that accumulates \emph{composites}, as opposed to previous accumulators that accumulated \emph{primes}. We also present an efficient method for proving knowledge of factorization of a committed value. Based on these (and other) techniques we design a novel provably secure group signature scheme. It operates in the \emph{common auxiliary string} model and offers two important benefits: 1) the {\sf Join} process is very efficient: a new member computes only a single exponentiation, and 2) the (unoptimized) cost of generating a group signature is 17 exponentiations which is appreciably less than the state-of-the-art.
2002
EPRINT
Tree-based Group Key Agreement
Secure and reliable group communication is an active area of research. Its popularity is caused by the growing importance of group-oriented and collaborative applications. The central research challenge is secure and efficient group key management. While centralized methods are often appropriate for key distribution in large multicast-style groups, many collaborative group settings require distributed key agreement techniques. This work investigates a novel group key agreement approach which blends so-called key trees with Diffie-Hellman key exchange. It yields a secure protocol suite (TGDH) that is both simple and fault-tolerant. Moreover, the efficiency of TGDH appreciably surpasses that of prior art.
2001
EPRINT
Quasi-Efficient Revocation of Group Signatures
A group signature scheme allows any group member to sign on behalf of the group in an anonymous and unlinkable fashion. In the event of a dispute, a designated trusted entity can reveal the identity of the signer. Group signatures are claimed to have many useful applications such as voting and electronic cash. A number of group signature schemes have been proposed to-date. However, in order for the whole group signature concept to become practical and credible, the problem of secure and efficient group member revocation must be addressed. In this paper, we construct a new revocation method for group signatures based on the signature scheme by Ateniese et al. at Crypto 2000. This new method represents an advance in the state-of-the-art since the only revocation schemes proposed thus far are either: 1) based on implicit revocation and the use of fixed time periods, or 2) require the signature size to be linear in the number of revoked members. Our method, in contrast, does not rely on time periods, offers constant-length signatures and constant work for the signer.
2000
CRYPTO

Program Committees

PKC 2009 (Program chair)