20187054
Bit-Free Collision: Application to APOP Attack
This paper proposes a new variant of collisions on hash functions named bit-free collision , which can be applied to reduce the number of chosen challenges in password recovery attacks on hash-based challenge and response protocols, such as APOP (Authentication Post Office Protocol). In all previous APOP attacks, the attacker needs to impersonate the server and to send poisoned chosen challenges to the user. Impersonating the server takes a risk that the user may find out he is being attacked. Hence, it is important for the attacker to reduce the number of impersonation in order to lower the probability that the attack will be detected. To achieve this, reducing the number of chosen challenges is necessary. This paper is the first approach to improve previous APOP attacks based on this observation to our best knowledge. With t -bit-free collisions presented in this paper, the number of chosen challenges to recover each password character can be reduced by approximately a factor of 2 t . Though our attack utilizing t -bit-free collisions needs higher offline complexity than previous attacks, the offline computation can be finished in practical time if the attacker can obtain reasonable computation power. In this research, we generate 1-bit-free collisions on MD5 practically. As a result, the number of challenges for password recovery attacks on real APOP is approximately half reduced. Of independent interest, we apply the bit-free-collision attack on a simpler hash function MD4, and show that 3-bit-free collisions can be generated practically.
14024123
Visual Secret Sharing Schemes for Multiple Secret Images Allowing the Rotation of Shares
In this paper, a method is proposed to construct a visual secret sharing (VSS) scheme for multiple secret images in which each share can be rotated with 180 degrees in decryption. The proposed VSS scheme can encrypt more number of secret images compared with the normal VSS schemes. Furthermore, the proposed technique can be applied to the VSS scheme that allows to turn over some shares in decryption. From the theoretical point of view, it is interesting to note that such VSS schemes cannot be obtained from so-called basis matrices straightforwardly.
37423199
How to Confirm Cryptosystems Security: The Original Merkle-Damgård Is Still Alive!
At Crypto 2005, Coron et al. showed that Merkle-Damgard hash function (MDHF) with a fixed input length random oracle is not indifferentiable from a random oracle RO due to the extension attack. Namely MDHF does not behave like RO. This result implies that there exists some cryptosystem secure in the RO model but insecure under MDHF. However, this does not imply that no cryptosystem is secure under MDHF. This fact motivates us to establish a criteria methodology for confirming cryptosystems security under MDHF. 
 
In this paper, we confirm cryptosystems security by using the following approach: 1 Find a variant, $\widetilde{\mathsf{RO}}$, of RO which leaks the information needed to realize the extension attack. 
 1 Prove that MDHF is indifferentiable from $\widetilde{\mathsf{RO}}$. 
 1 Prove cryptosystems security in the $\widetilde{\mathsf{RO}}$ model. 
 From the indifferentiability framework, a cryptosystem secure in the $\widetilde{\mathsf{RO}}$ model is also secure under MDHF. Thus we concentrate on finding $\widetilde{\mathsf{RO}}$, which is weaker than RO. 
 
We propose the Traceable Random Oracle (TRO) which leaks enough information to permit the extension attack. By using TRO, we can easily confirm the security of OAEP and variants of OAEP. However, there are several practical cryptosystems whose security cannot be confirmed by TRO (e.g. RSA-KEM). This is because TRO leaks information that is irrelevant to the extension attack. Therefore, we propose another $\widetilde{\mathsf{RO}}$, the Extension Attack Simulatable Random Oracle, ERO, that leaks just the information needed for the extension attack. Fortunately, ERO is necessary and sufficient to confirm the security of cryptosystems under MDHF. This means that the security of any cryptosystem under MDHF is equivalent to that under the ERO model. We prove that RSA-KEM is secure in the ERO model.
16195917
New Key-Recovery Attacks on HMAC/NMAC-MD4 and NMAC-MD5
At Crypto '07, Fouque, Leurent and Nguyen presented full key-recovery attacks on HMAC/NMAC-MD4 and NMAC-MD5, by extending the partial key-recovery attacks of Contini and Yin from Asiacrypt '06. Such attacks are based on collision attacks on the underlying hash function, and the most expensive stage is the recovery of the socalled outer key. In this paper, we show that the outer key can be recovered with near-collisions instead of collisions: near-collisions can be easier to find and can disclose more information. This improves the complexity of the FLN attack on HMAC/NMAC-MD4: the number of MAC queries decreases from 288 to 272, and the number of MD4 computations decreases from 295 to 277. We also improved the total complexity of the related-key attack on NMAC-MD5. Moreover, our attack on NMAC- MD5 can partially recover the outer key without the knowledge of the inner key, which might be of independent interest.
31093950
Extended Password Recovery Attacks against APOP, SIP, and Digest Authentication
In this paper, we propose password recovery attacks against challenge-response authentication protocols. Our attacks use a message difference for a MD5 collision attack proposed in IEICE 2008. First, we show how to efficiently find a message pair that collides with the above message difference. Second, we show that a password used in authenticated post office protocol (APOP) can be recovered practically. We also show that the password recovery attack can be applied to a session initiation protocol (SIP) and digest authentication. Our attack can recover up to the first 31 password characters in a short time and up to the first 60 characters faster than the naive search method. We have implemented our attack and confirmed that 31 characters can be successfully recovered.
10157835
New Message Differences for Collision Attacks on MD4 and MD5
In 2005, collision resistance of several hash functions was broken by Wang et al. The strategy of determining message differences is the most important part of collision attacks against hash functions. So far, many researchers have tried to analyze Wang et al.'s method and proposed improved collision attacks. Although several researches proposed improved attacks, all improved results so far were based on the same message differences proposed by Wang et al. In this paper, we propose new message differences for collision attacks on MD4 and MD5. Our message differences of MD4 can generate a collision with complexity of less than two MD4 computations, which is faster than the original Wang et al.'s attack, and moreover, than the all previous attacks. This is the first result that improves the complexity of collision attack by using different message differences from Wang et al.'s. Regarding MD5, so far, no other message difference from Wang et al.'s is known. Therefore, study for constructing method of other message differences on MD5 should be interesting. Our message differences of MD5 generates a collision with complexity of 242 MD5 computations, which is slower than the latest best attack. However, since our attack needs only 1 bit difference, it has some advantages in terms of message freedom of collision messages.
14386113
P2P Recommendation Trust Model
Security trust model is an important research topic for the P2P application. This paper firstly analyzes the existing P2P network security trust models, and then puts forward a new P2P recommendation trust model based on the network of social relationships. The model provides different types of services to show the userpsilas interest in different areas, and gives recommendation based on the interested area. Feedback mechanism and punishment mechanism have been used to improve the model. The simulation shows that the model can truly evaluate entity behavior and effectively isolated from malicious nodes.
17142699
Feature Selection with Kernel Class Separability
Classification can often benefit from efficient feature selection. However, the presence of linearly nonseparable data, quick response requirement, small sample problem and noisy features makes the feature selection quite challenging. In this work, a class separability criterion is developed in a high-dimensional kernel space, and feature selection is performed by the maximization of this criterion. To make this feature selection approach work, the issues of automatic kernel parameter tuning, the numerical stability, and the regularization for multi-parameter optimization are addressed. Theoretical analysis uncovers the relationship of this criterion to the radius-margin bound of the SVMs, the KFDA, and the kernel alignment criterion, providing more insight on using this criterion for feature selection. This criterion is applied to a variety of selection modes with different search strategies. Extensive experimental study demonstrates its efficiency in delivering fast and robust feature selection.
14600536
An Approach to Provisioning E-Commerce Applications with Commercial Components
Component-based development is a trend towards building e-commerce applications. However, commercial components are rarely used during the development. The reason is that existing approaches to selecting and composing components suffer from the problem that the components retrieved usually do not exactly fit with other components in the system being developed. While formal methods can be used to describe and check semantic characteristics to better match components, there are practical limitations which restrict their adoption. We have proposed a framework to support a semantic description and selection of components. We used Simple Component Interface Language (SCIL) to describe user requirements and pre-built components from the current component sources. Specifications in SCIL can be translated to a variety of models including those that have a formal basis. In this paper, we perform a case study of searching commercial components for a generic e-commerce application. We specify the commercial components in SCIL and use two specific tools: jMocha and Alloy Analyser to identify the correct components that suit a particular task
18692029
A CCI-Feedback-Aided Scheduling Technique for MU-MIMO
Imperfect channel state information (CSI) at the transmitter is one of the major challenges that the downlink multiuser multiple-input-multiple-output (MU-MIMO) technology faces in real applications. It will lead to increased co- channel interference (CCI) among users and deteriorate the capacity of MU-MIMO seriously, especially at high signal-to- noise-ratios (SNRs). In this paper, we propose an advanced MU-MIMO scheduling technique to improve the capacity of MU-MIMO in the case of imperfect CSI at the transmitter (CSIT). The rational behind the proposed scheme is the observation that the CCI level increases with the number of users simultaneously supported in MU-MIMO transmission. Thus, decreasing the number of simultaneous users can reduce CCI and sometimes even increase the sum capacity. Motivated by this observation, we design a CCI-feedback-aided scheduling technique, which adaptively adjusts the number of simultaneous users based on the CCI measurement at the user side. Simulation results have shown that considerable capacity gain can be achieved by the proposed scheduling technique at the cost of only one bit additional feedback per user and marginal complexity increase at both the transmitter and user side.
11142145
An Optimal Design Method for De-synchronous Circuit Based on Control Graph
De-synchronous is a very useful method to design asynchronous circuit automatically from synchronous description of circuits. This paper introduces an optimal design method based on Control Graph which is an abstract model of the de-synchronous circuit. The main purpose of this optimal design method is to reduce the extra overhead in the area of the de-synchronous circuit. The optimization algorithm takes the performance evaluation function based on the Control Graph of the de-synchronous circuit as its heuristic function. The performance evaluation function presented in this paper is a linear programming problem. In the end of this paper, the optimal method is applied to a set of benchmark circuits. The number of the local controllers in these circuits is markedly reduced by 54%, and the number of C-elements that is required to construct the handshake circuitry between local controllers is also reduced by 76.3%. So the entire area of the circuit is sharply reduced. Because this design method is directed by the performance evaluation function of the circuit, there is no penalty in performance of the de-synchronous circuit.