Information Security

Due to the low entropy of human-memorable passwords, it is not easy to conduct password authenticated key agreement in a secure manner. Though there are many protocols achieving this goal, they may require a large amount of computation specifically in the augmented model which was contrived to resist server compromise. Our contribution in this paper is two fold. First, we propose a new practical password authenticated key agreement protocol that is efficient and generic in the augmented model. Our scheme is considered from the practical perspective (in terms of efficiency) and is provably secure under the Diffie-Hellman intractability assumptions in the random-oracle model. Our second contribution is more realistic and generic; a conceptually simple but novel password guessing attack which can be mounted on every three-pass password-based protocol unless care is taken in both the design and implementation phases. This is due to the server’s failure to synchronize multiple simultaneous requests. Experimental results and possible prevention methods are also discussed.

Password-authenticated key exchange protocols allow two entities who only share a human-memorable password to authenticate each other and agree on a large session key. Such protocols are attractive for their simplicity and convenience and have received much interest in the research community. In ISC’02, Zhu et al. [18] proposed an efficient password-authenticated key exchange protocol which is suitable to the imbalanced wireless network environment where a low-power client communicates with a powerful server. In ISC’03, Bao [1] pointed out that the password protocol of Zhu et al. is subject to off-line dictionary attack if entity’s identity is too short. Bao presented two kinds of dictionary attacks which can exclude two possible passwords in each protocol run. In this paper, we present a more efficient attack on the password protocol of Zhu et al.. In our attack, an adversary can exclude multiple possible passwords in each protocol run, regardless of whether entity’s identity is short or long. To thwart the attack, we provide further improvement on Zhu et al.’s password-authenticated key exchange protocol.

Secure group communication relies on secure and robust distribution of group keys. A stateless group key distribution scheme is an ideal candidate when the communication channel is unreliable. Several stateless group key distribution schemes have been proposed. However, these schemes require all users store a certain number of auxiliary keys. The number of such keys increases as the group size grows. As a result, it is quite challenging to use these schemes when the users in a relatively large group have memory constraints. Thus, it is desirable to develop new schemes that can reduce the memory requirement. This paper introduces two novel stateless group key revocation schemes named key-chain tree (KCT) and layered key-chain tree (LKCT), which combine one-way key chains with a logical key tree. These schemes reduce the user storage requirements by trading off it with communication and computation costs. Specifically, these schemes can revoke any R users from a user group of size N by sending a key update message with at most 4R keys, while only requiring each user to store 2log N keys.

Recently we showed how to justify a Dolev-Yao type model of cryptography as used in virtually all automated protocol provers under active attacks and in arbitrary protocol environments. The justification was done by defining an ideal system handling Dolev-Yao-style terms and a cryptographic realization with the same user interface, and by showing that the realization is as secure as the ideal system in the sense of reactive simulatability. This holds the standard model of cryptography and under standard assumptions of adaptively secure primitives. While treating a term algebra is the point of that paper, a natural question is whether the proof could be more modular, e.g., by using a low-level idealization of signature schemes similar to the treatment of encryption. We present a low-level ideal signature system that we tried to use as a lower layer in prior versions of the library proof. It may be of independent interest for cryptography because idealizing signature schemes has proved surprisingly error-prone. However, we also explain why using it makes the overall proof of the justification of the Dolev-Yao type model more complicated instead of simpler.We further present a technique, integrity idealization, for mechanically constructing composable low-level ideal systems for other cryptographic primitives that have “normal” cryptographic integrity definitions.

This paper describes a powerful attack on a verifiably committed signature scheme based on GPS and RSA proposed in Financial Cryptography 2001. Given any partial signature, the attacker can extract the corresponding full signature. The attack works provided the attacker previously obtained a full signature of a special form, which can be done simply by eavesdropping a very small number of full signatures. For example, with the originally recommended parameters choice, 66% of the signatures are of this form. As a consequence, two “fair” protocols using this primitive do not satisfy the fairness property. Of independent interest, our attack shows that special attention should be paid when building cryptographic protocols from GPS and RSA.

Canetti and Rabin recently proposed a universally composable ideal functionality $\mathcal{F}_{\rm SIG}$ for digital signatures. We show that this functionality cannot be securely realized by any signature scheme, thereby disproving their result that any signature scheme that is existentially unforgeable under adaptive chosen-message attack is a secure realization.Next, an improved signature functionality is presented. We show that our improved functionality can be securely realized by precisely those signature schemes that are secure against existential forgery under adaptive chosen-message attacks.

Broadcast encryption schemes allow a center to transmit encrypted data over a broadcast channel to a large number of users such that only a select subset of privileged users can decrypt it. In this paper, we analyze how RSA accumulators can be used as a tool in this area. First, we describe a technique for achieving full key derivability given any broadcast encryption scheme in the general subset-cover framework [16]. Second, we show that Asano’s Broadcast Encryption scheme [5], can be viewed as a special-case instantiation of our general technique. Third, we use our technique to develop a new stateless-receiver broadcast encryption scheme that is a direct improvement on Asano’s scheme with respect to communication complexity, amount of tamper-resistant storage needed, and key derivation costs. Fourth, we derive a new lower bound that characterizes the tradeoffs inherent in broadcast encryption schemes which use our key derivability technique.

Chameleon signatures are based on well established hash-and-sign paradigm, where a chameleon hash function is used to compute the cryptographic message digest. Chameleon signatures simultaneously provide the properties of non-repudiation and non-transferability for the signed message, i.e., the designated recipient is capable of verifying the validity of the signature, but cannot disclose the contents of the signed information to convince any third party without the signer’s consent.One disadvantage of the initial chameleon signatures is that signature forgery results in the signer recovering the recipient’s trapdoor information, i.e., private key. Therefore, the signer can use this information to deny other signatures given to the recipient. This creates a strong disincentive for the recipient to forge signatures, partially undermining the concept of non-transferability. In this paper, we first propose a novel chameleon hashing scheme in the gap Diffie-Hellman group to solve the problem of key exposure. We can prove that the recipient’s trapdoor information will never be compromised under the assumption of Computation Diffie-Hellman Problem (CDHP) is intractable. Moreover, we use the proposed chameleon hashing scheme to design a chameleon signature scheme.

Recently, the radix-3 representation of integers is used for the efficient implementation of pairing based cryptosystems. In this paper, we propose non-adjacent form of radix-r representation (rNAF) and efficient algorithms for generating rNAF. The number of non-trivial digits is (r–2)(r+1)/2 and its average density of non-zero digit is asymptotically (r–1)/(2r–1). For r=3, the non-trivial digits are { ± 2, ± 4} and the non-zero density is 0.4. We then investigate the width-w version of rNAF for the general radix-r representation, which is a natural extension of the width-w NAF. Finally we compare the proposed algorithms with the generalized NAF (gNAF) discussed by Joye and Yen. The proposed scheme requires a larger table but its non-zero density is smaller even for large radix. We explain that gNAF is a simple degeneration of rNAF — we can consider that rNAF is a canonical form for the radix-r representation. Therefore, rNAF is a good alternative to gNAF.

We consider how related-key attacks can be mounted on the IBM 4758 cryptoprocessor, and also show that its EDEx multiple mode is far less secure than one could believe. As few as about 232 known plaintexts and related-key known ciphertexts in the first case, and 234 chosen ciphertexts in the second case are required to mount key-recovery attacks. These results show that seemingly academic attacks seriously need to be taken into consideration when it comes to real-life implementations.

Signcryption is a new cryptographic primitive that performs signing and encryption simultaneously, at a cost significantly lower than that required by the traditional signature-then-encryption approach. In this paper, we present a security analysis of two such schemes: the Huang-Chang convertible signcryption scheme [12], and the Kwak-Moon group signcryption scheme [13]. Our results show that both schemes are insecure. Specifically, the Huang-Chang scheme fails to provide confidentiality, while the Kwak-Moon scheme does not satisfy the properties of unforgeability, coalition-resistance, and traceability.

Key derivation functions are commonly used within many cryptographic schemes in order to distribute the entropy contained in an uneven way in a long stream of bits into a string that can be used directly as a symmetric key or as a seed for a pseudo-random number generator, or to convert short strings such as passwords into symmetric keys. This paper examines the common key derivation function constructions and shows that most of these have some concerning properties. In some situations, the use of these key derivation functions may actually limit the security that would otherwise be obtained. A new construction is also provided which seems to have better properties and an intuitive justification for its security is given.

Traditional secure database systems rely on preventive controls and are very limited in surviving malicious attacks because of intrusion detection deficiencies. ITDB, a Intrusion Tolerant Database prototype system, has been proposed, which can detect intrusions, repair the damage caused by intrusions in a timely manner. In this paper, we evaluate ITDB using TPC-C benchmark. The performance measurements show that ITDB system is cost-effective within reasonable False Alarm Rate and Detection Latency ranges. Our experiment results also indicate that ITDB can achieve good survivability without being seriously affected by various intrusion detection deficiencies. It can provide essential database services in the presence of attacks, and maintain the desired essential (security) properties such as integrity and performance.

Misuse Detection systems identify evidence of attacks by searching for patterns of known attacks (signatures). A main problem in this context is the modeling and specification of attack signatures. A couple of languages are proposed in the literature, which differ in the aspects of signatures that can be described. Some aspects that can be specified in one language cannot be expressed in another. In this paper we present a model for the semantics of attack signatures that systematically enumerates the different aspects that characterize attack signatures. The presented model represents a kind of a checklist for the development of a signature specification language or for the comparison of existing signature specification languages.

On a local network, security is always taken into consideration. When plain text data is being sent onto the network, it can be easily stolen by any network user. Stealing data from the network is called sniffing. By sniffing the network, a user can gain access into confidential documents and cause intrusion into anyone’s privacy. Many 0freely distributed software on the Internet provides this functionality. Despite the easiness of sniffing, sniffers are usually difficult to detect, since they do not interfere with the network traffic at all. System administrators are facing difficulties to detect and deal with this type of attack. Several antisniffers programs can be used to detect sniffers. However, sniffers are becoming very advanced so that current antisniffers are unable to detect them.This paper explains a new technique used by SupCom AntiSniffer, a tool that can effectively scan sniffers on an Ethernet network. The proposed technique uses three phases to detect the sniffing hosts in an Ethernet network. In the first phase, the ARP caches of the sniffing hosts are corrupted. In the second phase, TCP SYN request connections packets are sent to each host in the network using fake IP and MAC source addresses. Finally, by analyzing the responses of the hosts, all hosts running sniffers are detected. Four anti-sniffers, PMD [18], PromiScan [17], L0pht AntiSniff [19] and SupCom anti-sniffer, are tested and the evaluation results show that SupCom AntiSniffer succeeded to detect more sniffing hosts than the other antisniffers.

The ICAT statistics over the past few years have shown at least one out of every five CVE and CVE candidate vulnerabilities have been due to buffer overflows. This constitutes a significant portion of today’s computer related security concerns. In this paper we introduce a novel method for detecting stack smashing and buffer overflow attacks. Our runtime method extracts return addresses from the program call stack and uses these return addresses to extract their corresponding invoked addresses from memory. We demonstrate how these return and invoked addresses can be represented as a directed weighted graph and used in the detection of stack smashing attacks. We introduce the concept of a Greedy Hamiltonian Call Path and show how the lack of such a path can be used to detect stack-smashing attacks.

Current multi-tiered Web-based applications are very often characterized by the use of a database system. Database systems are thus not any longer confined to well-protected environments. In this paper, we focus on a specific type of attack, known as query flood. Under such an attack, a subject, or a colluding set of subjects, floods the database with a very large number of requests thus making the database unable to serve, with adequate response time, requests from honest subjects. The approach we propose is based on modeling access profiles and using these profiles to detect unusual behaviors in the subjects accessing the database. Our approach supports varying granularities in that one can build a single profile for the entire database or build specialized profiles for each table in the database. We employ our techniques both in misuse and anomaly detection settings. An evaluation of the proposed approach has been carried out and some preliminary experimental results are reported.

The paper proposes an XML-based approach for a controlled distribution of documents, that must be subject to distributed and collaborative updates. In particular, the approach we propose allows one to attach a flow policy to a document, that partially or totally specifies the list of subjects that have to receive the document. Flow policies associated with documents can be dynamically changed during document transmission. Such modifications are regulated by a set of modification control rules, specified according to a model that we present in this paper. A key feature of the proposed solution is that a subject, upon receiving a document can also locally verify the correctness of the path and of the modification operations possibly performed over it, without interacting with other parties. In the paper, besides presenting the language to specify flow policies and modification control rules, we describe the suite of protocols we have developed to perform the above-mentioned checks on document paths.

We present a model of access control which provides fine-grained data-dependent control, can express permissions about permissions, can express delegation, and can describe systems which avoid the root-bottleneck problem. We present a language for describing goals of agents; these goals are typically to read or write the values of some resources. We describe a decision procedure which determines whether a given coalition of agents has the means (possibly indirectly) to achieve its goal. We argue that this question is decidable in the situation of the potential intruders acting in parallel with legitimate users and taking whatever temporary opportunities the actions of the legitimate users present. Our technique can also be used to synthesise finite access control systems, from an appropriately formulated logical theory describing a high-level policy.

We present dharma, a distributed high assurance reference monitor that is generated mechanically by the formal methods tool PVS from a verified specification of its key algorithms. dharma supports policies that allow delegation of access rights, as well as structured, distributed names. To test dharma, we use it as the core reference monitor behind a web server that serves files over SSL connections. Our measurements show that formally verified high assurance access control systems are practical.

We suggest a scheme to cryptographically support role based access control (RBAC) in large organizations where user roles change frequently. To achieve this, we propose a secure method to manage role keys and we extend a recent pairing-based mediated identity-based cryptographic scheme to allow the enforcement of possession of multiple roles to access certain documents. We also design an architecture and a set of algorithms which cryptographically enforce RBAC and allow for role addition, revocation, and delegation. Finally, we briefly discuss the space requirements and security of our scheme.

We outline the linguistic problem of word-sense ambiguity and demonstrate its relevance to current computer security applications in the context of Human Interactive Proofs (HIPs). Such proofs enable a machine to automatically determine whether it is interacting with another machine or a human. HIPs were recently proposed to fight abuse of web services, denial-of-service attacks and spam. We describe the construction of an HIP that relies solely on natural language and draws its security from the problem of word-sense ambiguity, i.e., the linguistic phenomenon that a word can have different meanings dependent on the context it is used in.

CAPTCHAs are tests that distinguish humans from software robots in an online environment [3,14,7]. We propose and implement three CAPTCHAs based on naming images, distinguishing images, and identifying an anomalous image out of a set. Novel contributions include proposals for two new CAPTCHAs, the first user study on image recognition CAPTCHAs, and a new metric for evaluating CAPTCHAs.

In key-insulated cryptography, there are many private keys with different indexes and a single, fixed public key. When the trust model includes multiple Certification Authorities (CAs), it can be used to shorten the verification path and mitigate the damage caused by the compromise of a CA’s private key. Existing work requires that the total number of CAs be fixed and that a trusted keystore store all private keys. This paper presents a hierarchical key-insulated signature scheme, called HKI, which converts existing key-insulated methods to a hierarchical scheme. Our scheme allows the system to repeatedly generate a new private key for a new CA and also provides two important features, namely a shortened verification path and mitigated damage. By basing our approach on a general key-insulated scheme, we have made it possible to take advantage of any future improvements in computation complexity, key length, or robustness in current key-insulated methods.

Users in a distributed system establish webs of trust by issuing and exchanging certificates amont themselves. This approach does not require a central, trusted keyserver. The distributed web of trust, however, is susceptible to attack by malicious users, who may issue false certificates. In this work, we propose a method for generating certificate recommendations. These recommendations guide the users in creating webs of trust that are highly robust to attacks. To accomplish this we propose a heuristic method of graph augmentation for the certificate graph, and show experimentally that it is close to optimal. We also investigate the impact of user preferences and non-compliance with these recommendations, and demonstrate that our method helps identify malicious users if there are any.

We study the security challenges faced by the mobile agent paradigm, where code travels and performs computations on remote hosts in an autonomous manner. We define universally composable security for mobile agent computation that is geared toward a complex networking environment where arbitrary protocol instances may be executing concurrently. Our definition provides security for all the participants in the mobile agent system: the originator as well as the hosts. Finally, under the assumption of a universally composable threshold cryptosystem, we present universally composable, multi-agent protocols with provable security against either static, semi-honest or static, malicious adversaries, according to our definition, where in the latter case we need to provide access to a common reference string.

Security problems in micro-mobility are mostly related to trust establishment between mobile nodes and middle-boxes, i.e. mobile anchor points. In this paper, we present a secure micro-mobility architecture that scales well between administrative domains, which are already using different kind of network access authentication techniques. The trust between the mobile nodes and middle boxes is established using one-way hash chains and a technique known as secret splitting. Our protocol protects the middle-boxes from traffic re-direction and related Denial-of-Service attacks. The hierarchical scheme supports signaling optimization and secure fast hand-offs. The implementation and simulation results are based on an enhanced version of Host Identity Protocol (HIP). To our knowledge, our micro-mobility protocol is the first one-and-half round-trip protocol that establishes simultaneously a trust relationship between a mobile node and an anchor point, and updates address bindings at the anchor point and at a peer node in a secure way.

We formalize the notion of shared-key signatures, which makes it possible to anonymously sign any message with verification by a shared common public key. Unlike group signatures, shared-key signatures require no group manager or other third party to help the group members to generate signing keys. Also unlike ring signatures, shared-key signatures have no special structure such as a ring and the signing and verification procedures are the same as those of the ordinary signatures. In addition, they can be easily transformed into interactive authentication protocols while the ring signatures cannot. A concrete construction of such signatures is proposed based on Weak Dependence Problem (WDP). Since WDP is NP-complete and many researchers believe that NPC problems are intractable even in the quantum computation model, our scheme may be used to sign the documents requiring a longer-term validity with anonymity.

This paper presents a novel method that can be used to prevent online identity theft and thereby ensure secure online transactions. In particular, the method combats online identity theft mechanisms that capture information on the computer before the information is encrypted. The key feature of this method is the use of secure network smart cards to establish secure connections between the smart card and remote Internet nodes. Using this end-to-end secure connection, one can securely exchange confidential information between the smart card and a trusted remote server. Any intermediate node, including the host computer to which the smart card is connected, cannot compromise this secure connection.

We consider unlinkability of communication problem: given n users, each sending a message to some destination, encode and route the messages so that an adversary analyzing the traffic in the communication network cannot link the senders with the recipients. A solution should have a small communication overhead, that is, the number of additional messages should be kept low.David Chaum introduced idea of mixes for solving this problem. His approach was developed further by Simon and Rackoff, and implemented later as the onion protocol. Even if the onion protocol is widely regarded as secure and used in practice, formal arguments supporting this claim are rare and far from being complete. On top of that, in certain scenarios very simple tricks suffice to break security without breaking the cryptographic primitives. It turns out that one source of difficulties in analyzing the onion protocol’s security is the adversary model. In a recent work, Berman, Fiat and Ta-Shma develop a new and more realistic model in which only a constant fraction of communication lines can be accessed by an adversary, the number of messages does not need to be high and the preferences of the users are taken into account. For this model they prove that with high probability a good level of unlinkability is obtained after $\mathcal{O}(\log^4 n)$ steps of the onion protocol where n is the number of messages sent.In this paper we improve these results: we show that the same level of unlinkability (expressed as variation distance between certain probability distributions) is obtained with high probability already after $\mathcal{O}(\log n)$ steps of the onion protocol. Asymptotically, this is the best result possible, since obviously Ω(log n) steps are necessary. On top of that, our analysis is much simpler. It is based on path coupling technique designed for showing rapid mixing of Markov chains.

Though there are intensive researches on off-line electronic cash (e-cash), the current computer network infrastructure sufficiently accepts on-line e-cash. The on-line means that the payment protocol involves with the bank, and the off-line means no involvement. For customers’ privacy, the e-cash system should satisfy unlinkability, i.e., any pair of payments is unlinkable w.r.t. the sameness of the payer. In addition, for the convenience, exact payments, i.e., the payments with arbitrary amounts, should be also able to performed. In an existing off-line system with unlinkable exact payments, the customers need massive computations. On the other hand, an existing on-line system does not satisfy the efficiency and the perfect unlinkability simultaneously. This paper proposes an on-line system, where the efficiency and the perfect unlinkability are achieved simultaneously.

Today, the Internet and digital technologies lead to illegal reproduction and spread of digital content. Since a copy of digital content is identical with the original, it is difficult to protect the copyright of its creator. In addition, P2P applications like Napster, Gnutella, KaZaA, and so on have accelerated the illegal sharing of digital content. Moreover, a user in P2P can not only be the reader of content, but also the creator and the writer of content. But current technologies like digital watermarking and digital right management does not meet these characteristics, because of their weaknesses such as the allowance of unauthorized viewing in digital watermarking and targeting only the unmodifiable content in digital right management.In this paper, we propose a framework for copyright protection of digital content in a P2P environment. We present a framework where anyone can create and modify a digital content and has the copyright of his contribution with maintaining the copyrights of previously participated contributors. The proposed framework is compared with previous related works such as digital watermarking, XML security, and digital right management.

Digitalization of content is both a blessing and a curse. While it allows for efficient transmission and consumption, the ease of copying and sharing digital content has resulted in rampant piracy. Digital Rights Management (DRM) has emerged as a multidisciplinary measure to protect the copyright of content owners and to facilitate the consumption of digital content. In this paper, we survey the technological aspects of DRM. We present a discussion of DRM definitions, formulate a general DRM model and specify its various DRM components. We also evaluated emerging trends such as the use of P2P in DRM and DRM for personal access control, some noteworthy issues such as content reuse and granularity, as well as citing some future directions such as frequent content key upgrades.

A software birthmark is a unique characteristic of a program that can be used as a software theft detection technique. In this paper we present and empirically evaluate a novel birthmarking technique — Whole Program Path Birthmarking — which uniquely identifies a program based on a complete control flow trace of its execution. To evaluate the strength of the proposed technique we examine two important properties: credibility and tolerance against program transformations such as optimization and obfuscation. Our evaluation demonstrates that, for the detection of theft of an entire program, Whole Program Path birthmarks are more resilient to attack than previously proposed techniques. In addition, we illustrate several instances where a birthmark can be used to identify program theft even when an embedded watermark was destroyed by program transformation.

Use cases are widely used for functional requirements elicitation. However, security non-functional requirements are often neglected in this requirements analysis process. As systems become increasingly complex current means of analysis will probably prove ineffective. In the safety domain a variety of effective analysis techniques have emerged over many years. Since the safety and security domains share many similarities, various authors have suggested that safety techniques might usefully find application in security. This paper takes one such technique, HAZOP, and applies it to one widely used functional requirement elicitation component, UML use cases, in order to provide systematic analysis of potential security issues at the start of system development.

Code obfuscations are semantics-preserving code transformations used to protect a program from reverse engineering. There is generally no expectation of complete, long-term, protection. Rather, there is a trade-off between the protection afforded by an obfuscation (i.e. the amount of resources an adversary has to expend to overcome the layer of confusion added by the transformation) and the resulting performance overhead.In this paper we examine the problems that arise when constructing an Obfuscation Executive. This is the main loop in charge of a) selecting the part of the application to be obfuscated next, b) choosing the best transformation to apply to this part, c) evaluating how much confusion and overhead has been added to the application, and d) deciding when the obfuscation process should terminate.