Information and Communications Security

Certified email is a system which enables a sender to prove a receiver’s receipt of email. Such a system can be used for applications related to electronic commerce on the Internet. This paper considers a situation where a sender or a receiver wants to change his/her mind due to the change of mail content value (e.g., stock, auction, gambling) during the transaction. We point out that no traditional certified email systems have been designed for such a case, thus one of the participants can be at a disadvantage. To avoid this problem, we propose an evenhanded certified email system in which each participant can change his/her choice, either cancel or finish the transaction, at any time during the transaction.

The notion of identity based cryptosystem was introduced by Shamir in 1984, and has attracted much interest since it eliminates the need of certificates and simplify the key management. In this paper, we propose an optimistic fair exchange protocol for identity-based signatures. A semi-trust third party (

ttp

) is still involved in our protocol to ensure fairness. However, there is no need for registrations between users and

ttp

, and no zero-knowledge proof is needed to provide verifiability. The proposed optimistic fair exchange protocol is much concise and efficient, and can be shown to be secure in the random model with a tight security reduction.

We design and analyze a simple optimistic fair non-repudia- tion protocol. Our protocol is considerably simpler and more efficient than current proposals, due mainly to the avoidance of using session labels. We model-check both safety and liveness properties. The safety properties are verified using a standard intruder, and the liveness properties using an intruder that respects the resilient communication channels assumption. Finally, to provide further confidence in the protocol, several vulnerabilities on weaker versions of our protocol are exposed.

As a value-added service for standard email systems, a certified email scheme allows a sender to deliver a message to a receiver in a

fair

way in the sense that either the sender obtains a receipt from the receiver and the receiver accesses the content of the email simultaneously, or neither party gets the expected item. In this paper, we first point out some weaknesses in several existing schemes. Then, we present two generic optimistic certified email schemes with transparent TTP. Our schemes are not only fair, but also support timeliness in two flavors: one scheme supports weak timeliness but with stateless TTP, while the other guarantees (strong) timeliness though only supports weak stateless TTP. Technical discussion and comparison are provide to show that our schemes are both secure and efficient, compared with the-state-of-art in this field.

A forward secure blind signature scheme was proposed by Duc, Cheon and Kim, in ICICS 2003. The security of the scheme was proved to be equivalent to the strong RSA assumption in the random oracle model. In this paper we present an attack to the scheme by forging valid signatures with public keys only. The attack is so efficient that forging a valid signature needs less computation than legally generating a signature, even considering only the user side. Our result implies that the security proof of the scheme must be invalid. Furthermore we point out the fault of the proof and explain why it invalidates the proof.

In a paper recently published in ICALP 2005, Lipmaa, Wang and Bao identified a new essential security property, non-delegatability, of designated verifier signature (DVS) schemes. Briefly, in a non-delegatable DVS scheme, neither a signer nor a designated verifier can delegate the signing rights to any third party

T

without revealing their secret keys. We show that the Susilo-Zhang-Mu identity-based strong DVS scheme, Ng-Susilo-Mu universal designated multi verifier signature scheme, the Laguillaumie-Vergnaud multi-DVS scheme and the Zhang-Furukawa-Imai universal DVS scheme are delegatable. Together with the results of Lipmaa, Wang and Bao, our results show that most of the previously proposed DVS schemes are delegatable. However, the Laguillaumie-Vergnaud and Zhang-Furukawa-Imai schemes may still be secure in practice, since there the only party who can delegate signing is the designated verifier, who may not have motivation to do so. We finish the paper with some discussion on whether the non-delegatability notion of Lipmaa, Wang and Bao is appropriate.

In e-government or e-tax payment systems, appropriate alterations on digitally signed documents are required to hide personal information, namely privacy. Standard digital signature schemes do not allow such alternations on the signed documents since there is no means to distinguish appropriate alternations from inappropriate forgeries. The

sanitizable signature scheme

is a possible solution for such systems in which sanitizings of partial information are possible, after a signature is signed on the original (unsanitized) document. However, in previously proposed schemes, since sanitizers are anonymous, verifiers cannot identify sanitizers, and thus dishonest sanitizings are possible. This paper proposes a new sanitizable signature scheme “PIATS” in which partial information can be sanitized. Moreover, verifiers can identify sanitizers and thus dishonest sanitizings are eliminated.

A new cryptographic protocol —ciphertext comparison— can compare two ciphertexts without revealing the two encrypted messages. Correctness of the comparison can be publicly verified. This technique provides an efficient and publicly verifiable solution to the famous millionaire problem. It is the first solution to the millionaire problem to output a precise result (the two messages are equal or which is larger). Privacy in this new solution is achieved with an overwhelmingly large probability and strong enough in practice.

Private itemset support counting (PISC) is a basic building block of various privacy-preserving data mining algorithms. Briefly, in PISC, Client wants to know the support of her itemset in Server’s database with the usual privacy guarantees. First, we show that if the number of attributes is small, then a communication-efficient PISC protocol can be constructed from a communication-efficient oblivious transfer protocol. The converse is also true: any communication-efficient PISC protocol gives rise to a communication-efficient oblivious transfer protocol. Second, for the general case, we propose a computationally efficient PISC protocol with linear communication in the size of the database. Third, we show how to further reduce the communication by using various tradeoffs and random sampling techniques.

We show how to visualize an oblivious transfer and a commitment scheme with a method similar to that used in a visual secret sharing scheme. We call them a visual oblivious transfer and a visual commitment scheme, respectively. Data are images printed on transparencies, and the operation for obtaining information is only overlaying each of the transparencies over each other. Hence, it is easy for non-expert users to execute them. The visual oblivious transfer and the visual commitment scheme proposed in this paper are based on the trusted initializer model.

Many security properties of cryptographic protocols can be expressed by using information flow policies as non-interference. But, in general it is very difficult to design a system without interference. For that, many works try to weak the standard definition of the non-interference. For instance, in [21] Mullins defines the admissible interference as an interference that admits flow information only through a dowgrader. Thus, we present in this paper a type system that try to detect process that allow interference. Then, if we can type a process we can say that is free interference. Also, we extend the type system of process with another type system based on a standard message algebra used in the literature of cryptographic protocols. So, we define the theoric characterization, prove the correctness of our type system and present an illustration of our result.

Since 2002, variants of two tweakable block cipher modes of operation, CMC and EME, have been presented by Halevi and Rogaway that are suitable for encryption of disk sectors. In this paper, we show that the security bounds given in their proofs are tight, and hence complement the security proofs of the designers. In particular, we show how to distinguish the CMC, EME, EME

 + 

and EME

*

modes from random tweakable permutations with negligible effort and 2

n

/2

chosen plaintexts, where

n

is the block size in bits. Further, we point out that both modes leak secret information via side-channel attacks (timing and power) due to the data-dependent internal multiplication operation.

In this paper, we cryptanalyze the compression functions of MD4, MD5 and 4-, 5-pass HAVAL in encryption mode. We exploit the recently proposed related-key rectangle and boomerang techniques to show non-randomness of MD4, MD5 and 4-, 5-pass HAVAL and to distinguish them from a randomly chosen cipher. The attacks are highly practical and have been confirmed by our experiments.

In ACISP ’00, Wu

et al.

proposed attacks to break the Polynomial Authentication and Signature Scheme (PASS), in particular, they are able to generate valid authentication transcripts and digital signatures without knowing the private key and any previous transcripts/ signatures. They showed that PASS can be broken with around 2

38.3

trials. In this paper, we analyze the security of the improved versions of PASS; viz. PASS II and MiniPASS, and extend the Wu

et al.

’s attacks to PASS II and MiniPASS to break them. Furthermore, we discuss why and how these schemes are broken from the view point of the structure of cryptosystems and point out the fundamental weakness behind.

We discuss side channel leakage from modular reduction for NIST recommended domain parameters. FIPS 186-2 has 5 recommended prime fields. These primes have a special form which is referred to as generalized Mersenne prime. These special form primes facilitate especially efficient implementation. A typical implementation of efficient modular reduction with such primes includes extra reduction. The extra reduction in modular reduction can constitute an information channel on the secret exponent. Several researchers have produced unified code for elliptic point addition and doubling in order to avoid a simple power analysis (SPA). However, Walter showed that SPA still be possible if Montgomery multiplication with extra reduction is implemented within the unified code. In this paper we show SPA on the modular reduction with NIST recommended primes, combining with the unified code for elliptic point operations. As Walter stated, our results also indicate that even if the unified codes are implemented for elliptic point operations, underlying field operations should be implemented in constant time. The unified approach in itself cannot be a countermeasure for side channel attacks.

The concept of concurrent signatures allows two entities to produce two signatures in such a way that, the signer of each signature is ambiguous from a third party’s point of view until the release of a secret, known as the

keystone

. Once the keystone is released, both signatures become binding to their respective signers concurrently. Previous concurrent signature schemes use the concept of ring signatures in their construction. Ring signatures identify the ring and thus concurrent signatures constructed from ring signature are related and linkable. We propose a new concurrent signature scheme which is independent of the ring signature concept. Our concurrent signatures are anonymous. The ordinary signatures obtained from our concurrent signature protocol are unlinkable and do not reveal which concurrent signature transaction has occurred. The price we pay is our concurrent signatures are

asymmetric

in the sense that the initial signature and subsequent signatures are not of the same construction.

The notion of concurrent signatures was recently introduced by Chen, Kudla and Paterson. In concurrent signature schemes, two entities can produce two signatures that are

not

binding, until an extra piece of information (namely the

keystone

) is released by one of the parties. Subsequently, it was noted that the concurrent signature scheme proposed in the seminal paper cannot provide perfect ambiguity. Then, the notion of

perfect

concurrent signatures was introduced. In this paper, we define the notion of

identity-based(or ID-based)

perfectconcurrent

signatureschemes

. We provide the

first

generic construction of (ID-based) perfect concurrent signature schemes from ring signature schemes. Using the proposed framework, we give two concrete ID-based perfect concurrent signature schemes based on two major paradigms of ID-based ring signature schemes. Security proofs are based on the random oracle model.

The contribution of this paper has two folds. In the first fold, we propose a generic construction of sequential aggregate signatures from families of certificated trapdoor one-way permutations. We show that our construction is provably secure in the random oracle model assuming that the underlying homomorphic permutations are trapdoor one-way. Compared to Lysyanskaya et al’s generic construction that is constructed from a trapdoor one-way permutation family working over the same domain [16], our scheme works over independent trapdoor one-way permutation domains. The flexible choice of the underlying permutation domains benefits our scheme to its applications in the real world where individual user may choose its working domain independently. In the second fold, we instantiate our generic construction with RSA so that the RSA moduli in our scheme can be chosen independently by individual user and thus the moduli is not required to be of the same length. Consequently, our proposed instantiation is the first scheme based on the RSA problem that works for any moduli – this is the most significant feature of our scheme different from the best results constructed from the RSA problem (say, Kawauchi et al’s scheme [14], and Lysyanskaya et al’s scheme [16]).

Stateful Inspection has become a classical technology for network firewall. Existing session table architectures of Stateful Inspection firewalls cause high time cost of timeout processing. A new architecture is proposed. The new architecture divides a session entry into two separate parts, and designs different data structures for each other. On the base of multi-queue architecture, dynamical timeouts according to available resource improve securities of protected hosts against SYN flood attack. Experimental results show that the new architecture can work well in Gigabit Ethernet network.

In this paper, the characteristics of Client/Server interaction behaviors under normal web access and typical DoS/DDoS attack are analyzed. A simple local rate-limiting method called Behavior-based Ingress Rate-limiting (BIR) mechanism is proposed, by which the client-end host’s inbound and outbound traffics are monitored. Bursts of the traffics are suppressed by a local transmission delay mechanism. The principle and implementation are described. Simulations are performed to validate its efficacy. Finally, the approach’s potential and limitations are also discussed.

Detecting and identifying port scans is important for tracking malicious activities at early stage. The previous work mainly focuses on detecting individual scanners, while cares little about their common scan patterns that may imply important security threats against network. In this paper we propose a

scan vector model

, in which a scanner is represented by a vector that combines different scan features online, such as target ports and scan rate. A center-based clustering algorithm is then used to partition the scan vectors into groups, and provide a condense view of the major scan patterns by a succinct summary of the groups. The experiment on traffic data gathered from two subnets in our campus network shows that our method can accurately identify the major scan patterns without being biased by heavy hitters, meanwhile, possessing simplicity and low computation cost.

Modeling and analysis of information system vulnerabilities helps us to predict possible attacks to networks using the network configuration and vulnerabilities information. As a fact, exploiting most of vulnerabilities result in access rights alteration. In this paper, we propose a new vulnerability analysis method based on the Take-Grant protection model. We extend the initial Take-Grant model to address the notion of vulnerabilities and introduce the vulnerabilities rewriting rules to specify how the protection state of the system can be changed by exploiting vulnerabilities. Our analysis is based on a bounded polynomial algorithm, which generates the closure of the Take-Grant graph regarding vulnerabilities. The closure helps to verify whether any subject can obtain an access right over an object. The application of our results have been examined in a case study which reveals how an attacker can gain an unauthorized access right by exploiting chain of vulnerabilities.

Efficiently protecting the privacy of multi-recipient emails is not as trivial as it seems. The approach proposed by S/MIME is to concatenate all ciphertexts. However, it suffers from poor scalability due to its linear computation and communication cost. In this paper, we propose a new practical and secure scheme, called

multiplex encryption

. By combining the ideas of identity-based mediated RSA and re-encryption mix network, our framework only requires constant computation and communication cost to encrypt a multi-recipient email.

In a secure multicast communication environment, only valid members belong to the multicast group could decrypt the data. In many previous researches, there is one “group key” shared by all group members. However, this incurs the so-called “1 affects n problem,” that is, an action of one member affects the whole group. We believe this is the source of scalability problems. Moreover, from the administrative perspective, it is desired to confine the impacts of changing membership events in a local area. In this paper, we propose a new secure multicast architecture without using a group key. We exploit a cryptographic primitive “proxy encryption.” It allows routers to convert a ciphertext encrypted under a key to a ciphertext encrypted under another key, without revealing the secret key and the plaintext. By giving proper keys to intermediate routers, routers could provide separation between subgroups. Therefore the goals of scalability and containment are achieved.

This paper revisits the important problem of sending a message “into the future” in such a way that no communication is needed between the server and other entities. This problem was recently re-investigated by Blake and Chan who showed a scalable non-interactive solution without considering a formal security model. We fill this gap by introducing a new stringent model tailored to the non-interactive setting. We then propose a new construction fitting our model and we show that it is more efficient than the recent non-interactive proposal (for which we also give a security proof in our model). We then explain how to provide our scheme and the one of Blake and Chan with an additional security property that strengthens the anonymity of receivers.

In this paper we analyse the security of two authenticated group key agreement schemes based on the group key agreement protocol of Burmester and Desmedt. One scheme was proposed by Burmester and Desmedt, and uses a separate authentication scheme to achieve authentication among the participants. We show that this scheme suffers from a number of security vulnerabilities. The other scheme was generated using the general protocol compiler of Katz and Yung. We show that in some circumstances, even if key confirmation is implemented, this scheme still suffers from insider attacks (which are not covered by the security model used by Katz and Yung).

In 2004, Wu-Hsu proposed an efficient identification scheme preserving anonymity. However, Yang et al. showed that Wu-Hsu’s scheme has a serious weakness, by which the service provider can learn the secret token of the user who requests services. To overcome this limitation, they further proposed a scheme to attain the same set of objectives as the previous works. Nevertheless, the two schemes still have other serious weaknesses. Accordingly, the current paper demonstrates the vulnerability of the two schemes. Furthermore, we present a method to avoid attack.

In 2005, Lee et al. proposed an ID-based 2-party key agreement protocol between users whose private keys were issued by independent PKGs that do not share any system parameters. This work was the first kind that assumes completely independent multiple PKG environment. However, Lee et al. protocol has a flaw that allows attackers to impersonate others without knowing their private keys. In this paper, we propose a modification to the protocol of Lee et al. that prevents impersonation attacks. We also show a simple technique that can improve the efficiency of tripartite key agreement protocol of Lee et al. We also provide analysis of the security and efficiency of the proposed protocols.

Information stored in XML documents should be protected from unauthorized access. In military or other highly secure environments, mandatory access control (MAC) policy should be enforced on the sensitive information. If we use XML documents to store or exchange information in these environments, we should also enforce MAC policy on these XML documents. In this paper, we discussed a method to enforce fine-grained MAC policy on XML documents. The model of XML document is extended to contain the security information – label. Three kinds of labels are defined to determine the labels of the nodes in XML documents. Security view of XML document under MAC policy is proposed in this paper. The operations on XML documents will be redirected to the security views which contain the proper nodes under MAC policy. Validity of the security views is also described. Four kinds of operations on XML documents are discussed in details to explain how to enforce mandatory access control. The problem of polyinstantiation caused by these operations is also discussed. At last the architecture of enforcing MAC policy on XML documents is presented.

In this paper, we propose to enforce network access control in Mobile Ad Hoc Networks (MANETs) using cryptographic techniques. In the proposed approach, packets are authenticated by means of a network-wide symmetric (session) key. Because nodes are mobile and communication paths may change rapidly, timely distribution of new session keys is challenging (particularly if keys change frequently). Nodes wishing to communicate may therefore hold different session keys, which must somehow be synchronized. We present a fully distributed key synchronization method based on stateless group key distribution, and localized packet retransmission. If nodes A and B wish to communicate securely over a path

P

, all nodes on this path must synchronize keys with their immediately adjacent neighbors in the path. Any node which is unable to synchronize keys will not be allowed to forward packets. Simulations and a functioning prototype demonstrate the proposed system is practical and effective.

Software that covertly monitors user actions, also known as

spyware,

has become a first-level security threat due to its ubiquity and the difficulty of detecting and removing it. Such software may be inadvertently installed by a user that is casually browsing the web, or may be purposely installed by an attacker or even the owner of a system. This is particularly problematic in the case of utility computing, early manifestations of which are Internet cafes and thin-client computing. Traditional trusted computing approaches offer a partial solution to this by significantly increasing the size of the trusted computing base (TCB) to include the operating system and other software.

We examine the problem of protecting a user accessing specific services in such an environment. We focus on secure video broadcasts and remote desktop access when using any convenient, and often untrusted, terminal as two example applications. We posit that, at least for such applications, the TCB can be confined to a suitably modified graphics processing unit (GPU). Specifically, to prevent spyware on untrusted clients from accessing the user’s data, we restrict the boundary of trust to the client’s GPU by moving image decryption into GPUs. This allows us to leverage existing capabilities as opposed to designing a new component from scratch. We discuss the applicability of GPU-based decryption in the two scenarios. We identify limitations due to current GPU capabilities and propose straightforward modifications to GPUs that will allow the realization of our approach.

We propose a communication-efficient authentication scheme to authenticate query results disseminated by untrusted data publishing servers. In our scheme, signatures of multiple tuples in the result set are aggregated into one and thus the communication overhead incurred by the signature keeps constant. Next attr-MHTs (tuple based Merkle Hash Tree) are built to further reduce the communication overhead incurred by auxiliary authentication information (AAI). Besides the property of communication-efficiency, our scheme also supports dynamic SET operations (UNION, INTERSECTION) and dynamic JOIN with immunity to reordering attack.

Multimedia community is moving from monolithic applications to more flexible and scalable integrated solutions. Stream authentication is more complex since a stream may consist of multiple sources and be transcoded by intermediate proxies. In this paper, we propose a multi-source stream authentication (

mSSA

) framework based on MPEG-4 stream format. We describe the overall authentication architecture and elaborate the encoding, hashing, signing, amortizing and verifying methods used in the basic scheme. Further on, we utilize advanced cryptographic primitives-aggregate signature schemes, to reduce the signatures’ size and improve the performance. We illustrate the scheme and discuss the extensions. Our analysis shows that the scheme is secure and efficient.

Secure socket layer (SSL) is the most popular protocol to secure Internet communications. Since SSL handshake requires a large amount of computational resource, batch RSA was proposed to speedup SSL session initialization. However, the batch method is impractical since it requires a multiple of certificates. In this paper, we overcome this problem without modifying SSL protocol. To select the optimal batching parameters in terms of performance of server and durable waiting time of the client, we model the connection request with M/D/1 queue. We validate the solutions of the analytical model through simulation.

We present two provably secure and efficient schemes for performing conjunctive keyword searches over symmetrically encrypted data. Our first scheme is based on Shamir Secret Sharing and provides the most efficient search technique in this context to date. Although the size of its trapdoors is linear in the number of documents being searched, we empirically show that this overhead remains reasonable in practice. Nonetheless, to address this limitation we provide an alternative based on bilinear pairings that yields constant size trapdoors. This latter construction is not only asymptotically more efficient than previous secure conjunctive keyword search schemes in the symmetric setting, but incurs significantly less storage overhead. Additionally, unlike most previous work, our constructions are proven secure in the standard model.

This paper discusses the modification of a robust digital audio watermarking scheme to allow the disclosure of the embedding and detection algorithms. The chosen scheme uses MPEG 1 Layer 3 compression to determine the position of the mark bits in the frequency domain. The marking positions would be exposed if the original embedding algorithm was disclosed. In fact, it is shown that even if an attacker did not know the exact tuning parameters used for embedding, he or she could still produce an approximate superset of the marking frequencies from only a marked copy and successfully attack the file. To avoid this problem, a secret key is introduced in the embedding and detection processes. The secret key includes the seed of a pseudo-random number generator which is used to compute the exact marking positions. The modification is then analysed in terms of capacity, imperceptibility, robustness and security. The experiments show that the modified scheme preserves most of the properties of the original one, such as robustness against MP3 compression for the most frequently used bit rates, and does introduce additional security as the mark is more difficult to erase when the embedding and detection algorithms are disclosed.

A reversible watermarking algorithm with large capacity has been developed by applying the difference expansion of a generalized integer transform. In this algorithm, a watermark signal is inserted in the LSB of the difference values among pixels. In this paper, we apply the prediction errors calculated by a predictor in JPEG-LS for embedding a watermark signal, which contributes to increase the amount of embedded information with less degradation. As one of the drawbacks discovered in the above conventional method is a large size of the embedded location map introduced to make it reversible, we decrease the large size of the location map by vectorization, and then modify the composition of the map using the local characteristic in order to enhance the performance of JBIG2.

This paper presents PCAV (Parallel Coordinates Attack Visualizer), a real-time visualization system for detecting large-scale Internet attacks including Internet worms, DDoS attacks and network scanning activities. PCAV displays network traffic on the plane of parallel coordinates using the source IP address, destination IP address, destination port and the average packet length in a flow. These four values are used to draw each flow as a connected line on the plane and surprisingly a group of lines forms a particular shape in case of attack. Thus, a simple but novel way of displaying traffic reveals ongoing attacks. From the fact that numerous types of attacks form a specific pattern of graphs, we have developed nine signatures and their detection mechanism using an efficient hashing algorithm. Using the graphical signatures, PCAV can quickly detect new attacks and enables network administrators to instantly recognize and respond to the attacks. Another strength of PCAV comes from handling flows instead of packets. Per-flow visualization greatly reduces the processing time and further provides compatibility with legacy routers which export flow information such as NetFlow in Cisco routers. We have demonstrated the effectiveness of PCAV using real attack traffics.

Packet filtering in a firewall is one of the useful tools for network security. Packet filtering examines network packet and decides whether to accept, or deny it and this decision is determined by a packet filtering configuration developed by the network administrator. An administrator may find hard to understand and maintain a configuration, and this burden will furthermore be increased to find anomalies between two configurations, especially when the size of filters in a configuration increased. This difficulty may leave the administrator with less confidence that the configurations are correctly and completely implemented. This paper presents a system with SIERRA (A systolic filter sieve array) which can detect the anomalies between two configurations. It provides three functions, side-effects analysis function, equality judgment function, and composition analysis function. Experimental results show that the proposed system is suitable for small network and configurations with large number of filters.

There is a growing security concern on the increasing number of databases that are accessible through the Internet because a variety of attacks do succeed to fool the existed database protection mechanisms in many applications. Defense-in-depth strategies like intrusion prevention is urgently needed for database security. Most of research on intrusion prevention focuses on preventing attacks on operating systems and computer networks. Few efforts have been put on database intrusion prevention. Design and implementation of a database intrusion prevention system D_DIPS is presented. The goal of D_DIPS is to detect attacks caused by malicious transactions and cancel them timely before they succeed. The D_DIPS prototype shows D_DIPS can detect and stop attacks of malicious transaction in real time with low false alarm rate.