Automated Turing Tests (ATTs), also known as human-in-the-loop techniques, were recently employed in a login protocol by Pinkas and Sander (2002) to protect against online password-guessing attacks. We present modifications providing a new history-based login protocol with ATTs, which uses failed-login counts. Analysis indicates that the new protocol offers opportunities for improved security and user friendliness (fewer ATTs to legitimate users) and greater flexibility (e.g., allowing protocol parameter customization for particular situations and users). We also note that the Pinkas--Sander and other protocols involving ATTs are susceptible to minor variations of well-known middle-person attacks. We discuss complementary techniques to address such attacks, and to augment the security of the original protocol.

This paper is a preliminary exploration of secure distributed human computation. We consider the general paradigm of using large-scale distributed computation to solve difficult problems, but where humans can act as agents and provide candidate solutions. We are especially motivated by problem classes that appear to be difficult for computers to solve effectively, but are easier for humans; e.g., image analysis, speech recognition, and natural language processing. This paradigm already seems to be employed in several real-world scenarios, but we are unaware of any formal and unified attempt to study it. Nonetheless, this concept spawns interesting research questions in algorithm design, human computer interfaces, and programming language / API design, distributed systems, and cryptography, among other fields. There are also interesting implications for Internet commerce and the B24b model. We describe this research area and suggest a basic framework for the design of such systems. We analyze security and reliability against malicious parties using standard probability theory tools. We then derive design principles using standard decision-theory concepts. Finally, we list extensions and open problems.

This paper defines a framework in which one can formalize a variety of authorization and policy issues that arise in access control of shared computing resources. Instantiations of the framework address such issues as privacy, recency, validity, and trust. The paper presents an efficient algorithm for solving all authorization problems in the framework; this approach yields new algorithms for a number of specific authorization problems.

No abstract available.

Integrity critical databases, such as financial information used in high-value decisions, are frequently published over the Internet. Publishers of such data must satisfy the integrity, authenticity, and non-repudiation requirements of clients. Providing this protection over public data networks is an expensive proposition. This is, in part, due to the difficulty of building and running secure systems. In practice, large systems can not be verified to be secure and are frequently penetrated. The negative consequences of a system intrusion at the publisher can be severe. The problem is further complicated by data and server replication to satisfy availability and scalability requirements. To our knowledge this work is the first of its kind to give general approaches for reducing the trust required of publishers of large databases. To do this, we separate the roles of data owner and data publisher. With a few digital signatures on the part of the owner and no trust required of a publisher, we give techniques based on Merkle hash trees that publishers can use to provide authenticity and non-repudiation of the answer to database queries posed by a client. This is done without requiring a key to be held in an on-line system, thus reducing the impact of system penetrations. By reducing the trust required of the publisher, our solution is a step towards the publication of large databases in a scalable manner.

When computationally intensive tasks have to be carried out on trusted, but limited platforms such as smart cards, it becomes necessary to compensate for the limited resources (memory, CPU speed) by off-loading implementations of data structures onto an available (but insecure, untrusted) fast coprocessor. However, data structures such as stacks, queues, RAMs, and hash tables can be corrupted (and made to behave incorrectly) by a potentially hostile implementation platform or by an adversary knowing or choosing data structure operations. The paper examines approaches that can detect violations of data structure invariants, while placing limited demands on the resources of the secure computing platform.

Distributed systems inherently involve dynamic changes to the value of security-relevant attributes such as the goodness of encryption keys, trustworthiness of participants, and synchronization between principals. Since concurrent knowledge is usually infeasible or impractical, it is often necessary for the participants of distributed protocols to determine and act on beliefs that may not be supported by the current state of the system. Policies for determining beliefs in such situations can range from extremely conservative, such as only believing statements if they are very recent, to extremely optimistic, such as believing all statements that are not yet known to be revoked. Such security policies often are heavily dependent on timing of received messages and on synchronization between principals. We present a logic for analyzing cryptographic protocols that has the capability to specify time and synchronization details. This capability considerably advances the scope of known techniques both for expressing practical authentication policies of protocol participants as constraints and for reasoning about protocol goals subject to these constraints.

XML is increasingly becoming the format of choice for information exchange, in critical areas such as government, finance, healthcare and law, where integrity is of the essence. As this trend grows, one can expect that documents (or collections thereof) may get quite large, and clients may wish to query for specific segments of these documents. In critical applications, clients must be assured that they are getting complete and correct answers to their queries. Existing methods for signing XML documents cannot be used to establish that an answer to a query is complete. A simple approach has a server processing queries and certifying answers by digitally signing them with an on-line private key; however, the server, and its on-line private key, would be vulnerable to external hacking and insider attacks. We propose a new approach to signing XML documents which allows untrusted servers to answer certain types of path queries and selection queries over XML documents without the need for trusted on-line signing keys. This approach enhances both the security and scalability of publishing information in XML format over the internet. In addition, it provides greater flexibility in authenticating parts of XML documents, in response to commercial or security policy considerations.

Formal methods have been successfully applied to exceedingly abstract system specifications to verify high level security properties such as authentication, key exchange, and fail-safe revocation. Furthermore, considerable research exists on evaluating particular ciphers and secure hash functions used to implement high level security properties. However, verifying that less abstract system specifications satisfy low level security properties has been largely impractical. This is evidenced by innumerable system vulnerabilities where high level properties are not attained due to failed assumptions of low level properties. This paper presents ongoing work on investigating known pairs and chosen text using the NRL Protocol Analyzer. We give a formal characterization of known and chosen pairs, and translate it to necessary and sufficiency conditions in the NRL Protocol Analyzer model. It is the first work the authors are aware of automatically discovering known-pair and chosen-text attacks. We describe the use of the analyzer to rediscover attacks, to find new variants of attacks on an early version of the ESP protocol, and to show how our experience in using it has led us to refine our model. This was the first use of the Analyzer to model protocols at such a low level of abstraction.

The market for software components is growing, driven on the "demand side" by the need for rapid deployment of highly functional products and, on the "supply side", by distributed object standards. As components and component vendors proliferate, there is naturally a growing concern about quality and the effectiveness of testing processes. White-box testing, particularly the use of coverage criteria, Is a widely used method for measuring the "thoroughness" of testing efforts. High levels of test coverage are used as indicators of good quality control procedures. Software vendors who can demonstrate high levels of test coverage have a credible claim to high quality. However, verifying such claims involves knowledge of the source code, test cases, build procedures, etc. In applications where reliability and quality are critical, it would be desirable to verify test coverage claims without forcing vendors to give up valuable technical secrets. In this paper, we explore cryptographic techniques that can be used to verify such claims. Our techniques have certain limitations, which we discuss in this paper. However, vendors who have done the hard work of developing high levels of test coverage can use these techniques (for a modest additional cost) to provide credible evidence of high coverage, while simultaneously reducing disclosure of intellectual property.

Authentication using a path of trusted intermediaries, each able to authenicate the next in the path, is a well-known technique for authenicating entities in a large-scale system. Recent work has extended this technique to include multiple paths in an effort to bolster authentication, but the success of this approach may be unclear in the face of intersecting paths, ambiguities in the meaning of certificates, and interdependencies in the use of different keys. Thus, several authors have proposed metrics to evaluate the confidence afforded by a set of paths. In this paper we develop a set of guiding principles for the design of such metrics. We motivate our principles by showing how previous approaches failed with respect to these principles and what the consequences to authentication might be. We then propose a new metric that appears to meet our principles, and so to be a satisfactory metric of authenticaiton.

We present a protocol for unlinkable serial transactions suitable for a variety of network-based subscription services. It is the first protocol to use cryptographic blinding to enable subscription services. The protocol prevents the service from tracking the behavior of its customers, while protecting the service vendor from abuse due to simultaneous or cloned use by a single subscriber. Our basic protocol structure and recovery protocol are robust against failure in protocol termination. We evaluate the security of the basic protocol and extend the basic protocol to include auditing, which further deters subscription sharing. We describe other applications of unlinkable serial transactions for pay-per-use trans subscription, third-party subscription management, multivendor coupons, proof of group membership, and voting.

How do we decide if it is safe to run a given piece of software on our machine? Software used to arrive in shrink-wrapped packages from known vendors. But increasingly, software of unknown provenance arrives over the internet as applets or agents. Running such software risks serious harm to the hosting machine. Risks include serious damage to the system and loss of private information. Decisions about hosting such software are preferably made with good knowledge of the software product itself, and of the software process used to build it. We use the term Trusted Software Engineering to describe tools and techniques for constructing safe software artifacts in a manner designed to inspire trust in potential hosts. Existing approaches have considered issues such as schedule, cost and efficiency; we argue that the traditionally software engineering issues of configuration management and intellectual property protection are also of vital concern. Existing approaches (e.g., Java) to this problem have used static type checking, run-time environments, formal proofs and/or cryptographic signatures; we propose the use of trusted hardware in combination with a key management infrastructure as an additional, complementary technique for trusted software engineering, which offers some attractive features.

When computationally intensive tasks have to be carried out on trusted, but limited, platforms such as smart cards, it becomes necessary to compensate for the limited resources (memory, CPU speed) by off-loading implementations of data structures on to an available (but insecure, untrusted) fast co-processor. However, data structures such as stacks, queues, RAMs and hash tables can be corrupted (and made to behave incorrectly) by a potentially hostile implementation platform or by an adversary knowing or choosing data structure operations. This paper examines approaches that can detect violations of data structure invariants, while placing limited demands on the resources of the secure computing platform.

Authentication using a path of trusted intermediaries, each able to authenticate the next in the path, is a well-known technique for authenticating channels in a large distributed system. In this paper, we explore the use of multiple paths to redundantly authenticate a channel and focus on two notions of path independence-disjoint paths and connective paths-that seem to increase assurance in the authentication. We give evidence that there are no efficient algorithms for locating maximum sets of paths with these independence properties and propose several approximation algorithms for these problems. We also describe a service we have deployed, called PathServer, that makes use of our algorithms to find such sets of paths to support authentication in PGP applications.

Authenticating the source of a message in a large distributed system can be difficult due to the lack of a single authority that can tell for whom a channel speaks.This has led many to propose the use of a path of authorities, each able to authenticate the next in the path, such that the first in the path can be authenticated by the message recipient and the last can authenticate the message source.In this paper we suggest the use of multiple paths to provide redundant confirmation of the message source, and focus on two related notions of path independence that seem to bolster authentication.We formalize the problems of locating maximum sets of paths with these independence properties in a graph-theoretic framework, give evidence that they are not polynomial-time solvable, and propose approximation algorithms for these problems.We also introduce PathServer for PGP, a service for fmding sets of such paths to support authentication in PGP applications.

Service providers hosting software on servers at the request of content providers need assurance that the hosted software has no undesirable properties. This problem applies to browsers which host applets, networked software which can host software agents, etc. The hosted software's properties are currently verified by testing and/or verification processes by the hosting computer. This increases cost, causes delay, and leads to difficulties in version control. By furnishing content providers with a physically secure computing device with an embedded certified private key, such properties can be verified and/or enforced by the secure computing device at the content provider's site; the secure device can verify such properties, statically whenever possible, and by inserting checks into the executable binary when necessary. The resulting binary is attested by a trusted signature, and can be hosted with confidence. The position paper is a preliminary report that outlines scientific and engineering goals in this project.

Authentication using a path of trusted intermediaries, each able to authenticate the next one in the path, is a well-known technique for authenticating entities in a large-scale system. Recent work has extended this technique to include multiple paths in an effort to bolster authentication, but the success of this approach may be unclear in the face of intersecting paths, ambiguities in the meaning of certificates, and interdependencies in the use of different keys. Several authors have thus proposed metrics to evaluate the confidence afforded by a set of paths. In this paper, we develop a set of guiding principles for the design of such metrics. We motivate our principles by showing how previous approaches fail with respect to them and what the consequences to authentication might be. We then propose a direction for constructing metrics that come closer to meeting our principles and thus, we believe, to being satisfactory metrics for authentication.

Distributed systems inherently involve dynamic changes to the value of security attributes such as the goodness of encryption keys.Since concurrent knowledge is usually infeasible or impractical, it is often necessary for the participants of distributed protocols to determine and act on beliefs that may not be supported by the current state of the system.Policies for determining beliefs in such situations can range from extremely conservative, such as only believing statements if they are very recent, to extremely optimistic, such as believing all statements that are not yet known to be revoked.Such security policies often are heavily dependent on timing of received messages and on synchronization between principals.We present a. logic for analyzing cryptographic protocols that has the capability to specify time and synchronization details.This capability considerably advances the scope of known techniques for both expressing practical authentication policies of protocol participants as constraints, and for reasoning about protocol goals subject to these constraints.In the course of reasoning about protocol goals, one is able to deduce requirements for trust between protocol participants, synchronization between protocol participants, and timeliness of message contents.Our logic is flexible, and can support a wide range of security policies.The ability to reason about the conjunction of individual participant policies and protocols will be especially important as public and private key infrastructures are deployed and new and unanticipated policies are put into use.

A general method is described for formally specifying and reasoning about distributed systems with any desired degree of immediacy for revoking authentication. To effect revocation, 'authenticating entities' impose freshness constraints on credentials or authenticated statements made by trusted intermediaries. If fresh statements are not presented, then the authentication is questionable. Freshness constraints are derived from initial policy assumptions and authentic statements made by trusted intermediaries. By adjusting freshness constraints, the delay for certain revocation can be arbitrarily bounded. We illustrate how the inclusion of freshness policies within certificates enables the design of a secure and highly available revocation service. We illustrate the application of the method and new techniques in an example.>

The authors present a design method for message integrity protection. They illustrate the use of the method by designing large classes of message types whose integrity is provably preserved and by applying the method to the symmetric key option of the privacy-enhanced electronic mail protocol to help discover and eliminate an integrity vulnerability. The method is independent of the specific encryption system and checksum/digest functions used. It expresses desirable requirements for message integrity protection in terms of abstract encryption and checksum/digest properties, and relates these properties to the message type representation, and lifetime of the protocol run and keys used. The use of the method is illustrated by the design of a large class of message types whose integrity is provably preserved in the face of active intruder attacks. In particular, the method is used to help discover and eliminate a vulnerability in the symmetric-key option of the privacy-enhanced electronic mail (PEM) protocol for the internet.>

An operational model for message integrity in cryptographic protocols is presented, message integrity requirements are discussed, and message structures that satisfy those requirements are suggested. A message splicing/decomposition invariant of the cipher block chaining (CBC) mode of encryption is derived and used to identify heretofore-unknown vulnerabilities of well-known protocols. The suggested message structures remove these vulnerabilities relying only on the use of weak one-way functions.>

The authors discuss the virtues and limitations of several logics for cryptographic protocols focusing primarily on the logics of authentication. They emphasize the scope limitations of these logics rather than their virtues because: (1) their virtues to be better understood and accepted than their limitations; and (2) they hope to stimulate further research that will expand their scope.>