Information Security Practice and Experience

Frontmatter

Verification of Integrity and Secrecy Properties of a Biometric Authentication Protocol

Abstract

In this paper, we clarify and verify an established biometric authentication protocol. The selected protocol is intended to have three properties: effectiveness (integrity checks are carried out on all hardware before enabling transmission of biometric data), correctness (the user is satisfied that integrity checks have been executed correctly before transmission of biometric data occurs), and secrecy (unauthorized users cannot obtain biometric data by intercepting messages between the system’s hardware components). We analyse the clarified protocol using applied pi calculus and the ProVerif tool, and demonstrate that it satisfies the intended properties of the protocol. Moreover, this paper shows that the verification result between the naive interpretation and the clarified interpretation is different.

A. Salaiwarakul, M. D. Ryan

An On-Line Secure E-Passport Protocol

Abstract

The first generation e-passport standard is proven to be insecure and prone to various attacks. To strengthen, the European Union (EU) has proposed an Extended Access Control (EAC) mechanism for e-passports that intends to provide better security in protecting biometric information of the e-passport bearer. But, our analysis shows, the EU proposal fails to address many security and privacy issues that are paramount in implementing a strong security mechanism.

In this paper we propose an on-line authentication mechanism for electronic passports that addresses the weakness in existing implementations, of both The International Civil Aviation Organisation (ICAO) and EU. Our proposal utilises ICAO PKI implementation, thus requiring very little modifications to the existing infrastructure which is already well established.

Vijayakrishnan Pasupathinathan, Josef Pieprzyk, Huaxiong Wang

Secure Multi-Coupons for Federated Environments: Privacy-Preserving and Customer-Friendly

Abstract

A digital multi-coupon is similar to a paper-based booklet containing k coupons that can be purchased from one vendor and later redeemed at a vendor in exchange for services. Current schemes, offering privacy-protection and strong security properties such as unsplittability of multi-coupons, address business scenarios with a single vendor and multiple customers, and require customers to redeem coupons in some fixed order.

In this paper, we propose a multi-coupon scheme for federated environments that preserves the security and privacy properties of existing schemes, as well as their asymptotic communication and computation complexity. We define a generic formal security model and show that our scheme meets the formal requirements of this framework. Moreover, in contrast to previous solutions, we allow customers to redeem their coupons in an arbitrary order.

Frederik Armknecht, Alberto N. Escalante B., Hans Löhr, Mark Manulis, Ahmad-Reza Sadeghi

1-out-of-n Oblivious Signatures

Abstract

An oblivious signature with n keys (or messages) is a signature that the recipient can choose one of n keys (or messages) to get signed while the signer cannot find out on which key (or message) the recipient has got the signature. This kind of signature is firstly introduced by L. Chen in 1994. However, the previous reference does not crisply formalize the notion. Furthermore, the proposed constructions are less efficient in both communication and computation. In this paper, we first give formal definitions on the model of oblivious signatures. Then, based on the Schnorr signature, we propose our efficient oblivious signature scheme. A comparison result is also provided in this paper which shows that our scheme is more efficient than Chen’s schemes and those using a combination of a signature scheme and an oblivious transfer protocol.

Raylin Tso, Takeshi Okamoto, Eiji Okamoto

A Formal Study of the Privacy Concerns in Biometric-Based Remote Authentication Schemes

Abstract

With their increasing popularity in cryptosystems, biometrics have attracted more and more attention from the information security community. However, how to handle the relevant privacy concerns remains to be troublesome. In this paper, we propose a novel security model to formalize the privacy concerns in biometric-based remote authentication schemes. Our security model covers a number of practical privacy concerns such as identity privacy and transaction anonymity, which have not been formally considered in the literature. In addition, we propose a general biometric-based remote authentication scheme and prove its security in our security model.

Qiang Tang, Julien Bringer, Hervé Chabanne, David Pointcheval

Private Query on Encrypted Data in Multi-user Settings

Abstract

Searchable encryption schemes allow users to perform keyword based searches on an encrypted database. Almost all existing such schemes only consider the scenario where a single user acts as both the data owner and the querier. However, most databases in practice do not just serve one user; instead, they support search and write operations by multiple users. In this paper, we systematically study searchable encryption in a practical multi-user setting. Our results include a set of security notions for multi-user searchable encryption as well as a construction which is provably secure under the newly introduced security notions.

Feng Bao, Robert H. Deng, Xuhua Ding, Yanjiang Yang

Towards Tamper Resistant Code Encryption: Practice and Experience

Abstract

In recent years, many have suggested to apply encryption in the domain of software protection against malicious hosts. However, little information seems to be available on the implementation aspects or cost of the different schemes. This paper tries to fill the gap by presenting our experience with several encryption techniques: bulk encryption, an on-demand decryption scheme, and a combination of both techniques. Our scheme offers maximal protection against both static and dynamic code analysis and tampering. We validate our techniques by applying them on several benchmark programs of the CPU2006 Test Suite. And finally, we propose a heuristic which trades off security versus performance, resulting in a decrease of the runtime overhead.

Jan Cappaert, Bart Preneel, Bertrand Anckaert, Matias Madou, Koen De Bosschere

A New Public Key Broadcast Encryption Using Boneh-Boyen-Goh’s HIBE Scheme

Abstract

We offer an alternative Public Key Broadcast Encryption (PKBE) scheme which is fully collusion-secure. Our construction is based on the method for generating private keys in the Boneh, Boyen and Goh’s hierarchical identity-based encryption scheme. Our scheme provides a trade-off between ciphertext size and public key size. With appropriate parametrization we achieve a PKBE scheme where both ciphertexts and private keys are sublinear size for any subset of receivers. Private keys shrink as revoked users increase, and public key size is more reduced than other PKBE schemes. We extend our scheme to obtain chosen ciphertext security by using hash-based method.

Jong Hwan Park, Dong Hoon Lee

RSA Moduli with a Predetermined Portion: Techniques and Applications

Abstract

This paper discusses methods for generating RSA moduli with a predetermined portion. Predetermining a portion enables to represent RSA moduli in a compressed way, which gives rise to reduced transmission- and storage requirements. The first method described in this paper achieves the compression rate of known methods but is fully compatible with the fastest prime generation algorithms available on constrained devices. This is useful for devising a key escrow mechanism when RSA keys are generated on-board by tamper-resistant devices like smart cards. The second method in this paper is a compression technique yielding a compression rate of about 2/3 instead of 1/2. This results in higher savings in both transmission and storage of RSA moduli. In a typical application, a 2048-bit RSA modulus can fit on only 86 bytes (instead of 256 bytes for the regular representation). Of independent interest, the methods for prescribing bits in RSA moduli can be used to reduce the computational burden in a variety of cryptosystems.

Marc Joye

Variants of the Distinguished Point Method for Cryptanalytic Time Memory Trade-Offs

Abstract

The time memory trade-off (TMTO) algorithm, first introduced by Hellman, is a method for quickly inverting a one-way function, using pre-computed tables. The distinguished point method (DP) is a technique that reduces the number of table lookups performed by Hellman’s algorithm.

In this paper we propose a new variant of the DP technique, named variable DP (VDP), having properties very different from DP. It has an effect on the amount of memory required to store the pre-computed tables. We also show how to combine variable chain length techniques like DP and VDP with a more recent trade-off algorithm called the rainbow table method.

Jin Hong, Kyung Chul Jeong, Eun Young Kwon, In-Sok Lee, Daegun Ma

Secure Cryptographic Precomputation with Insecure Memory

Abstract

We propose a solution that provides secure storage for cryptographic precomputation using insecure memory that is susceptible to eavesdropping and tampering. Specifically, we design a small tamper-resistant hardware module, the Queue Security Proxy (QSP), that situates transparently on the data-path between the processor and the insecure memory. Our analysis shows that our design is secure and flexible, and yet efficient and inexpensive. In particular, both the timing overhead and the hardware cost of our solution are independent of the storage size.

Patrick P. Tsang, Sean W. Smith

Securing Peer-to-Peer Distributions for Mobile Devices

Abstract

Peer-to-peer (P2P) architectures offer a flexible and user-friendly way to distribute digital content (e.g., sharing, rental, or superdistribution). However, the parties involved have different interests (e.g., user privacy vs. license enforcement) that should be reflected in the P2P security architecture.

We identify characteristic P2P scenarios and demonstrate how these can be realized by applying a few basic licensing operations. We present a security architecture to realize these basic license operations (i) in a generalized fashion and (ii) employing the ARM TrustZone technology, which is popular for embedded systems. Lastly, we extend existing superdistribution schemes for offline application, allowing a mobile peer to access superdistributed content without the need to first contact the actual licensor.

André Osterhues, Ahmad-Reza Sadeghi, Marko Wolf, Christian Stüble, N. Asokan

Unified Rate Limiting in Broadband Access Networks for Defeating Internet Worms and DDoS Attacks

Abstract

Internet worms and DDoS attacks are considered the two most menacing attacks on today’s Internet. The traditional wisdom is that they are different beasts, and they should be dealt with independently. In this paper, however, we show that a unified rate limiting algorithm is possible, which effectively works on both Internet worms and DDoS attacks. The unified approach leads to higher worm traffic reduction performance than that of existing rate limiting schemes geared toward worm mitigation, in addition to the added advantage of dropping most DDoS attack packets. In our experiments with attack traffics generated by attacking tools, the unified rate limiting scheme drops 80.7% worm packets and 93% DDoS packets, while 69.2% worms and 3.4% DDoS packets are dropped at maximum by previous worm scan rate limiting schemes. Also, the proposed scheme requires less computing resources, and has higher accuracy for dropping attack packets but not dropping legitimate packets.

Keun Park, Dongwon Seo, Jaewon Yoo, Heejo Lee, Hyogon Kim

Combating Spam and Denial-of-Service Attacks with Trusted Puzzle Solvers

Abstract

Cryptographic puzzles can be used to mitigate spam and denial-of-service (DoS) attacks, as well as to implement timed-release cryptography. However, existing crypto puzzles are impractical because: (1) solving them wastes computing resources and/or human time, (2) the time it takes to solve them can vary dramatically across computing platforms, and/or (3) applications become non-interoperable due to competition for resources when solving them.

We propose the use of Trusted Computing in constructing crypto puzzles. Our puzzle constructions have none of the drawbacks above and only require each client machine to be equipped with a small tamper-resistant Trusted Puzzle Solver (TPS), which may be realized using the prevalent Trusted Platform Module (TPM) with minimal modifications.

Patrick P. Tsang, Sean W. Smith

PROBE: A Process Behavior-Based Host Intrusion Prevention System

Abstract

Attacks using vulnerabilities are considered nowadays a severe threat. Thus, a host needs a device that monitors system activities for malicious behaviors and blocks those activities to protect itself. In this paper, we introduce PROcess BEhavior (PROBE), which monitors processes running on a host to identify abnormal process behaviors. PROBE makes a process tree using only process creation relationship, and then it measures each edge weight to determine whether the invocation of each child process causes an abnormal behavior. PROBE has low processing overhead when compared with existing intrusion detections which use sequences of system calls. In the evaluation on a representative set of critical security vulnerabilities, PROBE shows desirable and practical intrusion prevention capabilities estimating that only 5% false-positive and 5% false-negative. Therefore, PROBE is a heuristic approach that can also detect unknown attacks, and it is not only light-weight but also accurate.

Minjin Kwon, Kyoochang Jeong, Heejo Lee

Towards the World-Wide Quantum Network

Abstract

QKD networks are of much interest due to their capacity of providing extremely high security keys to network participants. Most QKD network studies so far focus on trusted models where all the network nodes are assumed to be perfectly secured. This restricts QKD networks to be small. In this paper, we first develop a novel model dedicated to large-scale QKD networks, some of whose nodes could be eavesdropped secretely. Then, we investigate the key transmission problem in the new model by an approach based on percolation theory and stochastic routing. Analyses show that under computable conditions large-scale QKD networks could protect secret keys with an extremely high probability. Simulations validate our results.

Quoc-Cuong Le, Patrick Bellot, Akim Demaille

Synthesising Monitors from High-Level Policies for the Safe Execution of Untrusted Software

Abstract

Preventing malware from causing damage to its host system has become a topic of increasing importance over the past decade, as the frequency and impact of malware infections have continued to rise. Most existing approaches to malware defence cannot guarantee complete protection against the threats posed. Execution monitors can be used to defend against malware: they enable a target program’s execution to be analysed and can prevent any deviation from its intended behaviour, recovering from such deviations where necessary. They are, however, difficult for the end-user to define or modify.

This paper describes a high-level policy language in which users can express a priori judgments about program behavior, which are compiled into execution monitors. We show how this approach can defend against previously unseen malware and software vulnerability exploits.

Andrew Brown, Mark Ryan

Mediator-Free Secure Policy Interoperation of Exclusively-Trusted Multiple Domains

Abstract

The current schemes for security policy interoperation in multi-domain environments are based on a centralized mediator, where the mediator may be a bottleneck for maintaining the policies and mediating cross-domain resource access control. In this paper, we present a mediator-free scheme for secure policy interoperation. In our scheme, policy interoperation is performed by the individual domains, for which, a distributed multi-domain policy model is proposed, and distributed algorithms are given to create such cross-domain policies. Specially, the policies are distributed to each domain, and we ensure that the policies are consistent and each domain keeps the complete policies it shall know.

Xingang Wang, Dengguo Feng, Zhen Xu, Honggang Hu

Privacy of Recent RFID Authentication Protocols

Abstract

Privacy is a major concern in RFID systems, especially with widespread deployment of wireless-enabled interconnected personal devices e.g. PDAs and mobile phones, credit cards, e-passports, even clothing and tires. An RFID authentication protocol should not only allow a legitimate reader to authenticate a tag but it should also protect the privacy of the tag against unauthorized tracing: an adversary should not be able to get any useful information about the tag for tracking or discovering the tag’s identity. In this paper, we analyze the privacy of some recently proposed RFID authentication protocols (2006 and 2007) and show attacks on them that compromise their privacy. Our attacks consider the simplest adversaries that do not corrupt nor open the tags. We describe our attacks against a general untraceability model; from experience we view this endeavour as a good practice to keep in mind when designing and analyzing security protocols.

Khaled Ouafi, Raphael C. -W. Phan

A New Hash-Based RFID Mutual Authentication Protocol Providing Enhanced User Privacy Protection

Abstract

The recently proposed Radio Frequency Identification (RFID) authentication protocol based on a hashing function can be divided into two types according to the type of information used for authentication between a reader and a tag: either a value fixed or one updated dynamically in a tag. In this study we classify the RFID authentication protocol into a static ID-based and a dynamic-ID based protocol and then analyze their respective strengths and weaknesses and the previous protocols in the static/dynamic ID-based perspectives. Also, we define four security requirements that must be considered in designing the RFID authentication protocol including mutual authentication, confidentiality, indistinguishability and forward security. Based on these requirements, we suggest a secure and efficient mutual authentication protocol. The proposed protocol is a dynamic ID-based mutual authentication protocol designed to meet requirements of both indistinguishability and forward security by ensuring the unlinkability of tag responses among sessions. Thus, the protocol can provide more strengthened user privacy compared to previous protocols and recognizes a tag efficiently in terms of the operation quantity of tags and database.

Jihwan Lim, Heekuck Oh, Sangjin Kim

An Efficient Countermeasure against Side Channel Attacks for Pairing Computation

Abstract

Pairing-based cryptosystems have been widely researched, and several efficient hardware implementations of pairings have also been proposed. However, side channel attacks (SCAs) are serious attacks on hardware implementations. Whelan et al. pointed out that pairings except the η _T pairing might not be vulnerable against SCAs by setting the secret point to the first parameter [25]. This paper deals with SCAs for the η _T pairing over \({\mathbb F}_{3^n}\). To our knowledge, the randomized-projective-coordinate method has the smallest overhead among all countermeasures against SCAs for the η _T pairing. The cost of that overhead is 3nM, where M is the cost of a multiplication in \({\mathbb F}_{3^n}\). In this paper, we propose another countermeasure based on random value additions (x _p  + λ) and (y _p  + λ), where P = (x _p ,y _p ) is the input point, and λ is a random value in \({\mathbb F}_{3^n}\). The countermeasure using the random value addition was relatively slow in the case of the scalar multiplication of elliptic curve cryptosystems. However, in the case of the η _T pairing, we can construct an efficient countermeasure due to the form of the function \(g_P(x,y) = y_p^3y -(x_p^3+x-1)^2\) for a point P = (x _p ,y _p ). The overhead of our proposed scheme is just 0.5nM, which is a reduction of more than 75% compared with the randomized-projective-coordinate method.

Masaaki Shirase, Tsuyoshi Takagi, Eiji Okamoto

Efficient Arithmetic on Subfield Elliptic Curves over Small Finite Fields of Odd Characteristic

Abstract

In elliptic curve cryptosystems, scalar multiplications performed on the curves have much effect on the efficiency of the schemes, and many efficient methods have been proposed. In particular, recoding methods of the scalars play an important role in the performance of the algorithm used. For integer radices, the non-adjacent form (NAF) [21] and its generalizations (e.g., the generalized non-adjacent form (GNAF) [6] and the radix-r non-adjacent form (rNAF) [28]) have been proposed for minimizing the non-zero densities in the representations of the scalars. On the other hand, for subfield elliptic curves, the Frobenius expansions of the scalars can be used for improving efficiency [25]. Unfortunately, there are only a few methods apply the techniques of NAF or its analogue to the Frobenius expansion, namely τ-adic NAF techniques on Koblitz curves [16,27,3] and hyperelliptic Koblitz curves [10]. In this paper, we try to combine these techniques, namely recoding methods for reducing non-zero density and the Frobenius expansion, and propose two new efficient recoding methods of scalars on more general family of subfield elliptic curves in odd characteristic. We also prove that the non-zero densities for the new methods are same as those for the original GNAF and rNAF. As a result, the speed of the proposed methods improve between 8% and 50% over that for the Frobenius expansion method.

Keisuke Hakuta, Hisayoshi Sato, Tsuyoshi Takagi

Secure Computation of the Vector Dominance Problem

Abstract

Suppose two parties, holding vectors A = (a ₁,a ₂,...,a _n ) and B = (b ₁,b ₂,...,b _n ) respectively, wish to know whether a _i  > b _i for all i, without disclosing any private input. This problem is called the vector dominance problem, and is closely related to the well-studied problem for securely comparing two numbers (Yao’s millionaires problem). In this paper, we propose several protocols for this problem, which improve upon existing protocols on round complexity or communication/computation complexity.

Jin Yuan, Qingsong Ye, Huaxiong Wang, Josef Pieprzyk

Rational Secret Sharing with Repeated Games

Abstract

This paper introduces the Repeated Rational Secret Sharing problem. We borrow the notion of rational secret sharing from Halpern and Teague[1], where players prefer to get the secret than not to get the secret and with lower preference, prefer that as few of the other players get the secret. We introduce the concept of repeated games in the rational secret sharing problem for the first time, which enables the possibility of a deterministic protocol for solving this problem. This is the first approach in this direction to the best of our knowledge. We extend the results for the mixed model (synchronous) where at most t players can be malicious. We also propose the first asynchronous protocol for rational secret sharing.

Shaik Maleka, Amjed Shareef, C. Pandu Rangan

Distributed Private Matching and Set Operations

Abstract

Motivated by the need of private set operations in a distributed environment, we extend the two-party private matching problem proposed by Freedman, Nissim and Pinkas (FNP) at Eurocrypt’04 to the distributed setting. By using a secret sharing scheme, we provide a distributed solution of the FNP private matching called the distributed private matching. In our distributed private matching scheme, we use a polynomial to represent one party’s dataset as in FNP and then distribute the polynomial to multiple servers. We extend our solution to the distributed set intersection and the cardinality of the intersection, and further we show how to apply the distributed private matching in order to compute distributed subset relation. Our work extends the primitives of private matching and set intersection by Freedman et al. Our distributed construction might be of great value when the dataset is outsourced and its privacy is the main concern. In such cases, our distributed solutions keep the utility of those set operations while the dataset privacy is not compromised. Comparing with previous works, we achieve a more efficient solution in terms of computation. All protocols constructed in this paper are provably secure against a semi-honest adversary under the Decisional Diffie-Hellman assumption.

Qingsong Ye, Huaxiong Wang, Josef Pieprzyk

Computational Soundness of Non-Malleable Commitments

Abstract

This paper aims to find a proper security notion for commitment schemes to give a sound computational interpretation of symbolic commitments. We introduce an indistinguishability based security definition of commitment schemes that is equivalent to non-malleability with respect to commitment. Then, we give a construction using tag-based encryption and one-time signatures that is provably secure assuming the existence of trapdoor permutations. Finally, we apply this new machinery to give a sound interpretation of symbolic commitments in the Dolev-Yao model while considering active adversaries.

David Galindo, Flavio D. Garcia, Peter van Rossum

Square Attack on Reduced-Round Zodiac Cipher

Abstract

Zodiac is a block cipher with 128-bit blocks and designed for the Korean firm SoftForum in 2000. This paper discusses the security of Zodiac against the Square attack. We first construct two 8-round distinguishers to build a basic Square attack against the reduced 9-round Zodiac with 128-bit keys, and then extend this attack to 12, 13, 14, and 15-round Zodiac, which finds their round keys with the complexities 2^92.3, 2^124.8, 2^157.2, and 2^189.5, respectively. Moreover, our attack can find the round keys of the full 16-round Zodiac with 256-bit keys with a complexity of 2^221.7 which is better than the exhaustive search and in this attack we just need 2^16.5 chosen plaintexts. This result shows that the Square attack is not only applicable to Square-like ciphers but also to ciphers with Feistel structure once more.

Wen Ji, Lei Hu

Analysis of Zipper as a Hash Function

Abstract

At CRYPTO 2005, Coron etc. proposed several modified methods to make the usual hash functions based on MD method indifferentiable from random oracles. However, the compression functions used in Coron’s schemes are supposed to be random oracles. This assumption is too strong. To achieve Coron’s goal in the real world, Liskov proposed Zipper structure and implemented a new scheme indifferentiable from random oracle based on this structure. Unlike Coron’s schemes, the indifferentiability of Liskov’s scheme does not depend on strong compression functions and insecure compression functions can be used to implement Liskov’s scheme. In this paper, we show that the security of Liskov’s scheme is not ideal as a hash function. We also analyze those Zipper schemes whose compression functions are insecure PGV compression functions instead of Liskov’s weak compression functions, and we find that some insecure PGV compression functions whose security is stronger than Liskov’s weak compression function cannot be used to build indifferentiable and collision-resistant Zipper schemes.

Pin Lin, Wenling Wu, Chuankun Wu, Tian Qiu

On the Importance of the Key Separation Principle for Different Modes of Operation

Abstract

The key separation principle for different modes of operation of the block ciphers is a cryptographic folklore wisdom that states: One should always use distinct keys for distinct algorithms and distinct modes of operation. If this principle is violated, then there are generic attacks that can recover the whole or a part of the encrypted messages. By the advent of software packages and libraries that offer some or all modes of operation of block ciphers, the violation of this principle is really possible in practice. We show that under the same key, OFB mode of operation is a special case of the CBC mode of operation, and that if CBC and CTR modes of operation are interchangeably used under the same secret key - then the security of the encryption process is seriously weakened. Moreover in the chosen plaintext attack scenario with interchanged use of CBC and OFB mode under the same key, we give a concrete list of openssl commands that can extract the complete plaintext without knowing the secret key.

Danilo Gligoroski, Suzana Andova, Svein Johan Knapskog

Backmatter