Information Security and Cryptology - ICISC 2010

Mutual Information Analysis (MIA) is a side-channel attack introduced recently. It uses mutual information, a known information theory notion, as a side-channel distinguisher. Most previous attacks use parametric statistical tests and the attacker assumes that the distribution family of the targeted side-channel leakage information is known. On the contrary, MIA is a generic attack that assumes the least possible about the underlying hardware specifications. For example, an attacker should not have to guess a linear power model and combine it with a parametric test, like the Pearson correlation factor. Mutual information is considered to be very powerful however it is difficult to estimate. Results of MIA can therefore be unreliable and even bias. Several efficient parametric estimators of mutual information are proposed in the literature. They are obviously very efficient when the distribution is correctly guessed. However, we loose the original goal of MIA which is to assume the least possible about the attacked devices. Hence, nonparametric estimators of mutual information should be considered in more details and, in particular, their efficiency in the side-channel context. We review some of the most powerful nonparametric methods and compare their performance with state-of-the-art side-channel distinguishers.

Bias analysis is an important problem in cryptanalysis. When the critical bias can be expressed by the XOR of many terms, it is well-known that we can compute the bias of their sum by the famous Piling-up lemma assuming all the terms are independent. In this paper, we consider the terms of the sum are dependent and we study above bias problem. More precisely, let each term be a Boolean function of a variable over GF(2) ⁿ . We assume the distribution D of the XOR of k variables is known, each variable is uniformly distributed individually, and moreover, the XOR of k variables and (k − 1) variables all are independent. We give a simple expression for the bias of the sum of k Boolean functions. It takes time O(kn·2 ⁿ ) to compute the bias, while under the independence assumption, it takes time O(k·2 ⁿ ) to compute by Piling-up lemma. We further compare the general bias in our problem with the bias in the independent case. It is remarkable to note that the former can differ significantly from the latter. As application, we apply our results to cryptanalysis of two real examples, Bluetooth encryption standard E0 and Shannon cipher, which show a strongly biased and weakly biased D respectively. For E0, our analysis allows to make the best known key-recovery attack with precomputation, time and data complexities O(2³⁷). For Shannon cipher, our analysis verifies the validity of the estimated complexity O(2¹⁰⁷) of the previous distinguishing attack [5]. As comparison, we also studied a variant of Shannon cipher, which shows much stronger dependency within the internal states. We gave a distinguishing attack on the Shannon variant with reduced complexity O(2⁹³).

In this paper we investigate the differential properties of block ciphers in hash function modes of operation. First we show the impact of differential trails for block ciphers on collision attacks for various hash function constructions based on block ciphers. Further, we prove the lower bound for finding a pair that follows some truncated differential in case of a random permutation. Then we present open-key differential distinguishers for some well known round-reduced block ciphers.

HIGHT is a lightweight block cipher, proposed in CHES 2006 , and on the process of ISO/IEC 18033-3 standardization. It is a 32-round Feistel-like block cipher with 64-bit block and 128-bit key. In this paper, we present the first attack on the full HIGHT using related-key rectangle attack with 2^123.169 encryptions, 2^57.84 data, and 4 related keys. Our related-key rectangle attack is valid for 2¹²⁶ weak keys and this attack can be easily extended to an attack for the full key space faster than an exhaustive key searching using 4 related keys.

We observe that an “add-difference” of master keys is propagated to an add-difference of subkeys with probability 1, so we can find 3-round local collisions of HIGHT by considering an add-difference as a relation of keys. Exploiting these local collisions and “over-simplified” structure of key-schedule, we construct a new 15.5-round related-key differential trail with relatively high probability. We construct a 24-round related-key rectangle distinguisher with probability 2^− 117.68 from an 8.5-round and a 15.5-round related-key truncated differential trail with local collisions by applying the ladder switch technique, and then suggest an attack on full rounds of HIGHT with this distinguisher. Our result implies that HIGHT cannot be regarded as an instantiation of the ideal cipher used in some provably secure schemes.

We propose preimage attacks against PKC98-Hash and HAS-V. PKC98-Hash is a 160-bit hash function proposed at PKC 1998, and HAS-V, a hash function proposed at SAC 2000, can produce hash values of 128 + 32k (k = 0,1,…,6) bits. These hash functions adopt the Merkle-Damgård and Davies-Meyer constructions. One unique characteristic of these hash functions is that their step functions are not injective with a fixed message. We utilize this property to mount preimage attacks against these hash functions. Note that these attacks can work for an arbitrary number of steps. The best proposed attacks generate preimages of PKC98-Hash and HAS-V-320 in 2⁹⁶ and 2²⁵⁶ compression function computations with negligible memory, respectively. This is the first preimage attack against the full PKC98-Hash function.

Our results show that, at the highest security level of the protocol (security parameter= 256), inferring a nonce is feasible with the probability of 0.99 by eavesdropping(observing) about 90 runs of the protocol. Finding a nonce enables a passive attacker to recover all five secret keys of the protocol. To do so, we propose a three-phase probabilistic approach in this paper. Our attack recovers the secret keys with a probability that increases by accessing more protocol runs. We also show that tracing a tag using this protocol is also possible even with less runs of the protocol.

Let N = pq be RSA modulus where primes p and q are of the same bit-length. If \(|\rho q - p| = N^{\frac{1}{4}+\gamma}\) where ρ is a known constant satisfying 1 ≤ ρ ≤ 2 and the constant γ satisfies \(0< \gamma< \frac{1}{4}\), we show the factorization attack on N and weak key attack against RSA modulus N. We present algorithms to find the factorization of N in time O(N ^γ + ε ) by some square root attacks, such as the baby-step giant-step method and a more sophisticated square root attack. Using similar techniques of Blömer and May (PKC 2004), we present a weak key attack and find new weak keys over the work of Maitra and Sarkar (ISC 2008).

In a group signature scheme, group members are able to sign messages on behalf of the group. Moreover, resulting signatures are anonymous and unlinkable for every verifier except for a given authority. In this paper, we mainly focus on one of the most secure and efficient group signature scheme, namely XSGS proposed by Delerablée and Pointcheval at Vietcrypt 2006. We show that it can efficiently be implemented in a sensor node or an RFID tag, even if it requires 13 elliptic curve point multiplications, 2 modular exponentiations and one pairing evaluation to produce a group signature. This is done by securely outsourcing part of the computation to an untrusted powerful intermediary. The result is that XSGS can be executed in the MICAz (8-bit 7.37MHz ATmega128 microprocessor) and the TelosB (16-bit 4MHz MSP430 processor) sensor nodes in less than 200 ms.

This paper proposes a new lightweight 256-bit hash function Lesamnta-LW with claimed security levels of at least 2¹²⁰ with respect to collision, preimage, and second preimage attacks. We adopt the Merkle-Damgård domain extension; the compression function is constructed from a dedicated AES-based block cipher using the LW1 mode, for which a security reduction can be proven. In terms of lightweight implementations, Lesamnta-LW offers a competitive advantage over other 256-bit hash functions. Our size-optimized hardware implementation of Lesamnta-LW requires only 8.24 Kgates on 90 nm technology. Our software implementation of Lesamnta-LW requires only 50 bytes of RAM and runs fast on short messages on 8-bit CPUs.

Pairings in elliptic curve cryptography are functions which map a pair of elliptic curve points to a non-zero element of a finite field. In recent years, many useful cryptographic protocols based on pairings have been proposed. The fast implementations of pairings have become a subject of active research areas in cryptology.

In this paper, we give the geometric interpretation of the group law on Hessian curves. Furthermore, we propose the first algorithm for computing the Tate pairing on elliptic curves in Hessian form. Analysis indicates that it is faster than all algorithms of Tate pairing computation known so far for Weierstrass and Edwards curves excepted for the very special elliptic curves with a ₄ = 0, a ₆ = b ².

The DECT Standard Cipher (DSC) is a proprietary stream cipher used for enciphering payload of DECT transmissions such as cordless telephone calls. The algorithm was kept secret, but a team of cryptologists reverse-engineered it and published a way to reduce the key space when enough known keystreams are available [4]. The attack consists of two phases: At first, the keystreams are analyzed to build up an underdetermined linear equation system. In the second phase, a brute-force attack is performed where the equation system limits the number of potentially valid keys. In this paper, we present an improved variant of the first phase of the attack as well as an optimized FPGA implementation of the second phase, which can be used with our improved variant or with the original attack. Our improvement to the first phase of the attack is able to more than double the success probability of the attack, depending of the number of available keystreams. Our FPGA implementation of the second phase of the attack is currently the most cost-efficient way to execute the second phase of the attack.

We develop a new, custom-built hardware for emulating contactless smartcards compliant to ISO 14443. The device is based on a modern low-cost microcontroller and can support basically all relevant (cryptographic) protocols used by contactless smartcards today, e.g., those based on AES or Triple-DES. As a proof of concept, we present a full emulation of Mifare Classic cards on the basis of our highly optimized implementation of the stream cipher Crypto1. The implementation enables the creation of exact clones of such cards, including the UID. We furthermore reverse-engineered the protocol of DESFire EV1 and realize the first emulation of DESFire and DESFire EV1 cards in the literature. We practically demonstrate the capabilities of our emulator by spoofing several real-world systems, e.g., creating a contactless payment card which allows an attacker to set the stored credit balance as desired and hence make an infinite amount of payments.

Address space randomization is believed to be a strong defense against memory error exploits. Many code and data objects in a potentially vulnerable program and the system could be randomized, including those on the stack and heap, base address of code, order of functions, PLT, GOT, etc. Randomizing these code and data objects is believed to be effective in obfuscating the addresses in memory to obscure locations of code and data objects. However, attacking techniques have advanced since the introduction of address space randomization. In particular, return-oriented programming has made attacks without injected code much more powerful than what they were before. Keeping this new attacking technique in mind, in this paper, we revisit address space randomization and analyze the effectiveness of randomizing various code and data objects.

We show that randomizing certain code and data objects has become much less effective. Typically, randomizing the base and order of functions in shared libraries and randomizing the location and order of entries in PLT and GOT do not introduce significant difficulty to attacks using return-oriented programming. We propose a more general version of such attacks than what was introduced before, and point out weaknesses of a previously proposed fix. We argue that address space randomization was introduced without considering such attacks and a simple fix probably does not exist.

Spyware – malicious software that passively collects users’ information without their knowledge – is a prevalent threat. After a spyware program has collected and possibly analyzed enough data, it usually transmits such information back to its author. In this paper, we build a system to detect such malicious behaving software, based on our prior work on detecting crimeware. Our system is specifically designed to fit with thin-client computing, which is popular in some corporate environments. We provide implementation details, as well as experimental results that demonstrate the scalability and effectiveness of our system.

Proposed in response to the growing number of passwords users have to memorize, password managers allow to store one’s credentials, either on a third-party server (online password manager), or on a portable device (portable password manager) such as a mobile phone or a USB key. In this paper, we present a comparative usability study of three popular password managers: an online manager (LastPass), a phone manager (KeePassMobile) and a USB manager (Roboform2Go). Our study provides valuable insights on average users’ perception of security and usability of the three password management approaches. We find, contrary to our intuition, that users overall prefer the two portable managers over the online manager, despite the better usability of the latter. Also, surprisingly, our non-technical pool of users shows a strong inclination towards the phone manager. These findings can generally be credited to the fact that the users were not comfortable giving control of their passwords to an online entity and preferred to manage their passwords themselves on their own portable devices. Our results prompt the need for research on developing user-friendly and secure phone managers, owing to the ubiquity of mobile phones.

Network signaling and control mechanisms are critical to coordinate such diverse defense capabilities as honeypots and honeynets, host-based defenses, and online patching systems, any one of which might issue an actionable alert and provide security-critical data. Despite considerable work in exploring the trust requirements of such defenses and in addressing the distribution speed of alerts, little work has gone into identifying how the underlying transport systems behave under adversarial scenarios.

In this paper, we evaluate the reliability and performance trade-offs for a variety of control channel mechanisms that are suitable for coordinating large-scale collaborative defenses when under attack. Our results show that the performance and reliability characteristics change drastically when one evaluates the systems under attack by a sophisticated and targeted adversary. Based on our evaluation, we explore available design choices to reinforce the reliability of the control channel mechanisms. To that end, we propose ways to construct a control scheme to improve network coverage without imposing additional overhead.

Nowadays, due to the rapid growth of the mobile users, personalization and recommender systems have gained popularity. The recommender systems serve the personalized information to the users according to user preferences or interests and their profiles. Tourism is an industry which had adopted the use of new technologies. Recently, mobile tourism has come into spotlight. Due to the rapid growing of user needs in mobile tourism domain, we concentrated on to gives the personalized recommendation based on multi-agent technology in tourism domain to serve the mobile users [7]. The objective of this paper is to build a secure personalized recommendation system. Attackers can affect the prediction of the recommender system by injecting a number of biased profiles. In this paper, we consider detecting or preventing the profile injection (also called shilling attacks) by using significant weighting and trust weighting that complements to our proposed RPCF Algorithm.

In order to protect AES software running on untrusted platforms, Chow et al. (2002) designed a white-box implementation. However, Billet et al. (2004) showed that the secret key can be extracted with a time complexity of 2³⁰. In this paper, we present an improved white-box implementation of AES. We use dual ciphers to modify the state and key representations in each round as well as two of the four classical AES operations, SubBytes and MixColumns. We show that, with 61200 possible dual ciphers the complexity of Billet et al. attack is raised to 2⁹¹. Interestingly, our white-box implementation does not require more memory space than that of Chow et al. implementation.

In cryptography, secure channels enable the confidential and authenticated message exchange between authorized users. A generic approach of constructing such channels is by combining an encryption primitive with an authentication primitive (MAC). In this work, we introduce the design of a new cryptographic primitive to be used in the construction of secure channels. Instead of using general purpose MACs, we propose the employment of special purpose MACs, named “\(\mathcal{E}\)-MACs”. The main motive behind this work is the observation that, since the message must be both encrypted and authenticated, there can be a redundancy in the computations performed by the two primitives. If this turned out to be the case, removing such redundancy will improve the efficiency of the overall construction. In addition, computations performed by the encryption algorithm can be further utilized to improve the security of the authentication algorithm. In this work, we show how \(\mathcal{E}\)-MACs can be designed to reduce the amount of computations required by standard MACs based on universal hash functions, and show how \(\mathcal{E}\)-MACs can be secured against key-recovery attacks.

In FSE 2010, Rønjom and Cid put forward a nonlinear equivalence for Boolean functions and demonstrated that many cryptographic properties are not invariant among functions within the same equivalence class by providing some special examples. Their paper presented the idea and many problems were left open.

In this paper, we investigate equivalence of Boolean functions more deeply using a new method and discuss the number of Boolean functions in each equivalence class. We investigate further the cryptographic properties including algebraic immunity, algebraic degree and nonlinearity of equivalence classes, and deduce tight bounds on them. We find that there are many equivalence classes of Boolean functions with optimum algebraic immunity, optimum algebraic degree and a good nonlinearity. Moreover, we discuss how to construct equivalence classes with desired properties and show that it is possible to construct practical Boolean functions such that their equivalence classes have guaranteed cryptographic properties.

Secure message transmission (SMT) is a two-party protocol between a sender and a receiver over a network in which the sender and the receiver are connected by n disjoint channels and t out of n channels can be controlled by an adaptive adversary with unlimited computational resources. If a public discussion channel is available to the sender and the receiver to communicate with each other then a secure and reliable communication is possible even when n ≥ t + 1. The round complexity is one of the important measures for the efficiency for SMT. In this paper, we revisit the optimality and the impossibility for SMT with public discussion and discuss the limitation of SMT with the “unidirectional” public channel, where either the sender or the receiver can invoke the public channel, and show that the “bidirectional” public channel is necessary for SMT.

In a distributed oblivious transfer (DOT) the sender is replaced with m servers, and the receiver must contact k (k ≤ m) of these servers to learn the secret of her choice. Naor and Pinkas introduced the first unconditionally secure DOT for a sender holding two secrets. Blundo, D’Arco, Santis, and Stinson generalized Naor and Pinkas’s protocol, in the case that the sender holds n secrets, in the first so-called (k, m)-DOT-\(\binom{n}{1}\) protocol. Such a protocol should be secure against a coalition of less than k parties. However, Blundo et al. have shown that this level of security is impossible to achieve in one-round polynomial-based constructions.

In this paper, we show that if communication is allowed amongst the servers, we are able to construct an unconditionally secure, polynomial-based (k, m)-DOT-\(\binom{n}{1}\) protocol with the highest level of security. More precisely, in our construction, a receiver who contacts k servers and corrupt up to k − 1 servers (not necessarily from the set of the contacted servers) cannot learn more than one secret.

Rational secret sharing protocols in both the two-party and multi-party settings are proposed. These protocols are built in standard communication networks and with unconditional security. Namely, the protocols run over standard point-to-point networks without requiring physical assumptions or simultaneous channels, and even a computationally unbounded player cannot gain more than ε by deviating from the protocol. More precisely, for the 2-out-of-2 protocol the ε is a negligible function in the size of the secret, which is caused by the information-theoretic MACs used for authentication. The t-out-of-n protocol is (t − 1)-resilient and the ε is exponentially small in the number of participants. Although secret recovery cannot be guaranteed in this setting, a participant can at least reduce the Shannon entropy of the secret to less than 1 after the protocol. When the secret-domain is large, every rational player has great incentive to participate in the protocol.

In this paper, we present oblivious transfer with complex attribute-based access control policies. The protocol allows a database server to directly enforce “and” and “or” access control policies \((c_{1_1}\wedge c_{1_2}\wedge \dots c_{1_{n_1}})\vee (c_{2_1}\wedge c_{2_2}\wedge \dots c_{2_{n_2}})\vee \dots \vee (c_{t_1}\wedge c_{t_2}\wedge \dots c_{t_{n_t}})\) on each message in a database without duplication of the message as in Camenisch et al.’s AC-OT. To realize this protocol, we present the blind attribute-based encryption (ABE) scheme as a building block. Combining the blind ABE with a credential signature scheme, a generic construction for the oblivious transfer with complicated access control is presented. We also give a concrete scheme for the construction in which the policy is provided by an access tree which is represented by a formula involving \(``and(\wedge)"\) and \(``or(\vee)"\) boolean operators.

Security-aware embedded devices which are likely to operate in hostile environments need protection against physical attacks. For the RSA public-key algorithm, protected versions of the Montgomery powering ladder have gained popularity as countermeasures for such attacks.

In this paper, we present a general fault attack against RSA implementations which use the Montgomery powering ladder. In a first step, we discuss under which realistic fault assumptions our observation can be used to attack basic implementations. In a second step, we extend our attack to a scenario, where the message is blinded at the beginning of the exponentiation algorithm. To the best of our knowledge this is the first fault attack on a blinded Montgomery powering ladder.

Side Channel Analysis (SCA) are of great concern since they have shown their efficiency in retrieving sensitive information from secure devices. In this paper we introduce First Principal Components Analysis (FPCA) which consists in evaluating the relevance of a partitioning using the projection on the first principal directions as a distinguisher. Indeed, FPCA is a novel application of the Principal Component Analysis (PCA). In SCA like Template attacks, PCA has been previously used as a pre-processing tool. The originality of FPCA is to use PCA no more as a preprocessing tool but as a distinguisher. We conducted all our experiments in real life context, using a recently introduced practice-oriented SCA evaluation framework. We show that FPCA is more performant than first-order SCA (DoM, DPA, CPA) when performed on unprotected DES architecture. Moreover, we outline that FPCA is still efficient on masked DES implementation, and show how it outperforms Variance Power Analysis (VPA) which is a known successful attack on such countermeasures.

This paper proposes differential fault analysis, which is a well-known type of fault analysis, on a stream cipher MUGI, which uses two kinds of update functions of an intermediate state. MUGI was proposed by Hitachi, Ltd. in 2002 and it is specified as ISO/IEC 18033-4 for keystream generation. Fault analysis is a side-channel attack that uses the faulty output obtained by inducing faults into secure devices. To the best knowledge of the authors, this is the first paper that proposes applying fault analysis to MUGI. The proposed attack uses the relation between two kinds of the update functions that are mutually dependent. As a result, our attack can recover a 128-bit secret key using 12.54 pairs of correct and faulty outputs on average within 1 sec.