Search

Password recovery of RAR encrypted file is an important problem in computer forensics. It is difficult to deal with this problem by the traditional methods such as guess, dictionary, rainbow table and brute force. We give a new method based on parallel random search. The new method use a parallel stochastic approach on word selection in the dictionary attack. It can greatly improve the success rate of password recovery. And the experiment shows that the new approach is effective in the password recovery of RAR file.

Introduced by Hellman, Time-Memory Trade-Off (TMTO) attacks offer a generic technique to reverse one-way functions, where one can trade off time and memory costs and which are especially effective against stream ciphers. Hellman’s original idea has seen many different improvements, notably the Distinguished Points attack and the Rainbow Table attack. The trade-off curves of these approaches have been compared in literature, but never leading to a satisfying conclusion. A new TMTO attack was devised for the A5/1 cipher used in GSM, which combines both distinguished points and rainbow tables, which we refer to as the Kraken attack. This paper compares these four approaches by looking at concrete costs of these attacks instead of comparing their trade-off curves. We found that when multiple samples are available the Distinguished Points attack has the lowest costs. The Kraken attack is an alternative to save more disk space at the expense of attack time.

Time memory tradeoff algorithms are tools for inverting one-way functions, and they are often used to recover passwords from unsalted password hashes. There are many publicly known tradeoff algorithms, and the rainbow tradeoff is widely believed to be the best algorithm. This work provides an accurate complexity analysis of the non-perfect table version of the fuzzy rainbow tradeoff algorithm, which has not yet received much attention. It is shown that, when the pre-computation cost and the online efficiency are both taken into consideration, the non-perfect fuzzy rainbow tradeoff is preferable to the original rainbow tradeoff in many situations.

We propose an efficient attack to recover the passwords, used to authenticate the peer by EAP-MD5, in the IEEE 802.1X network. First, we recover the length of the used password through a method called length recovery attack by on-line queries. Second, we crack the known length password using a rainbow table pre-computed with a fixed challenge, which can be done efficiently with great probability through off-line computations. This kind of attack can also be implemented successfully even if the underlying hash function MD5 is replaced with SHA-1 or even SHA-512.

In this paper, we present a rigorous evaluation of Thing and Ying's attack (TY attack) [11] along with practical implementations. We find that the cryptanalysis time of their attack is too high to be practical. We also propose a more general time memory trade-off by combining the distinguished points strategy with TY attack. Both theoretical analysis and experimental results show that our new design can save about 53.7% cryptanalysis time compared to TY attack and can reduce about 35.2% storage requirement compared to the original rainbow attack.

As users become increasingly aware of the need to adopt strong password, it brings challenges to digital forensics investigators due to the password protection of potential evidentiary data. On the other hand, due to human nature and their tendency to select memorable passwords, which compromises security for convenience, users may select strong passwords by considering a permutation of dictionary words. In this paper, we discuss the existing password recovery methods and briefly present our previous work on the design of a time-memory tradeoff pre-computed table (Enhanced Rainbow Table) for efficient random password recovery. We then propose the design of an Enhanced Dictionary Based Rainbow Table to integrate the construction of dictionary based permutated passwords and common passwords within the Enhanced Rainbow Table, to incorporate the two promising password recovery approaches. We then present the analysis of the proposed method.

Recently, Jeong-Won-Kim proposed a hash-based strong-password authentication protocol and claimed that the protocol is secure against guessing attack, stolen-verifier attack, replay attack, and impersonation attack. However, we show that their protocol has two vulnerabilities, password guessing attack and authentication answer guessing attack. Furthermore, we present a secure hash-based password authentication protocol using smartcards to cope with the vulnerabilities. Security analysis shows that our protocol provides better security properties than the other related authentication protocols with the similar computational complexity with others.

Cryptanalytic time memory tradeoff algorithms are tools for quickly inverting one-way functions and many consider the rainbow table method to be the most efficient tradeoff algorithm. However, it was recently announced, mostly based on experiments, that the parallelization of the perfect distinguished point tradeoff algorithm brings about an algorithm that is 50% more efficient than the perfect rainbow table method. Motivated by this claim, we provide an accurate theoretic analysis of the parallel version of the non-perfect distinguished point tradeoff algorithm. Performance differences between different tradeoff algorithms are usually not very large, but even these small differences can be crucial in practice. So we take care not to ignore the side effects of false alarms while analyzing the online time complexity of the parallel distinguished point tradeoff algorithm. Our complexity results are used to compare the parallel non-perfect distinguished point tradeoff against the non-perfect rainbow table method. The two algorithms are compared under identical success rate requirements and the pre-computation efforts are taken into account. Contrary to our anticipation, we find that the rainbow table method is superior in typical situations, even though the parallelization did have a positive effect on the efficiency of the distinguished point tradeoff algorithm.

Password recovery tools are often used in digital forensic investigations to obtain the passwords that are used by suspects to encrypt potential evidentiary data. This paper presents a new method for deterministically generating and efficiently storing password recovery tables. The method, which involves the virtual expansion of rainbow tables, achieves improvements of 16.92% to 28.15% in the password recovery success rate compared with the original rainbow table method. Experimental results indicate that the improvements are achieved with the same computational complexity and storage requirements as the original rainbow table method.

Every time it is more often to audit the communications in companies to verify their right operation and to check that there is no illegal activity. The main problem is that the tools of audit are inefficient when communications are encrypted.

Hash chains have been used as OTP generators. Lamport hashes have an intensive computation cost and a chain length restriction. A solution for signature chains addressed this by involving public key techniques, which increased the average computation cost. Although a later idea reduced the user computation by sharing it with the host, it couldn’t overcome the length limitation. The scheme proposed by Chefranov to eliminate the length restriction had a deficiency in the communication cost overhead. We here present an algorithm that overcomes all of these shortcomings by involving two different nested hash chains: one dedicated to seed updating and the other used for OTP production. Our algorithm provides forward and non-restricted OTP generation. We propose a random challenge–response operation mode. We analyze our proposal from the viewpoint of security and performance compared with the other algorithms.

Human memory is not perfect --- people constantly memorize new facts and forget old ones. One example is forgetting a password, a common problem raised at IT help desks. We present several protocols that allow a user to automatically recover a password from a server using partial knowledge of the password. These protocols can be easily adapted to the personal entropy setting [7], where a user can recover a password only if he can answer a large enough subset of personal questions. We introduce client-server password recovery methods, in which the recovery data are stored at the server, and the recovery procedures are integrated into the login procedures. These methods apply to two of the most common types of password based authentication systems. The security of these solutions is significantly better than the security of presently proposed password recovery schemes. For our protocols we propose a variation of threshold encryption [5, 8, 16] that might be of independent interest.

Hashing or encrypting a key or a password is a vital part in most network security protocols. The most practical generic attack on such schemes is a time memory trade-off attack. Such an attack inverts any one-way function using a trade-off between memory and execution time. Existing techniques include the Hellman attack and the rainbow attack, where the latter uses different reduction functions ("colours") within a table. This work investigates the possibility of reusing colours, i.e., repeating the reduction functions, in the rainbow attack. We show how this outperforms the Hellman and the rainbow attack in a model of fixed resources. We try to characterize exactly when this improvement appears and in such a case the choice of an optimal number of colours.

In this paper we present new attack techniques to analyze the structure of hash functions that are not based on the classical Merkle-Damgard construction. We extend the herding attack to concatenated hashes, and to certain hash functions that process each message block several times. Using this technique, we show a second preimage attack on the folklore "hash-twice" construction which process two concatenated copies of the message. We follow with showing how to apply the herding attack to tree hashes. Finally, we present a new type of attack -- the trojan message attack, which allows for producing second preimages of unknown messages (from a small known space) when they are appended with a fixed suffix.

We propose practical password recovery attacks against two challenge-response authentication protocols using MD4. When a response is computed as MD4(Password||Challenge), passwords up to 12 characters are practically recovered. To recover up to 8 characters, we need 16 times the amount of eavesdropping and 16 times the number of queries, and the off-line complexity is less than 235 MD4 computations. To recover up to 12 characters, we need 210 times the amount of eavesdropping and 210 times the number of queries, and the off-line complexity is less than 240 MD4 computations.When a response is computed as MD4(Password||Challenge||Password), passwords up to 8 characters are practically recovered by 28 times the amount of eavesdropping and 28 times the number of queries, and the off-line complexity is less than 239 MD4 computations. Our approach is similar to the "Impossible differential attack", which was originally proposed for recovering the block cipher key. Good impossible differentials for hash functions are achieved by using local collision. This indicates that the presence of one practical local collision can damage the security of protocols.

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.

Biometrics-based user authentication has several advantages over traditional password-based systems for standalone authentication applications such as home networks. This is also true for new authentication architectures known as crypto-biometricsystems, where cryptography and biometrics are merged to achieve high security and user convenience at the same time. Recently, a cryptographic construct, called fuzzy vault, has been proposed for crypto-biometric systems. In this paper, we propose an approach to provide both the automatic alignment of fingerprint data and higher security by using a 3D geometric hash table. Based on the experimental results, we confirm that the proposed approach of using the 3D geometric hash table with the idea of the fuzzy vaultcan perform the fingerprint verification securely even with one thousand chaff data included.

We propose a way to increase the usability of password authentication systems by compensating for transposition and substitution errors. We show how to correct for these errors with low false positive rates (i.e., low probability that an arbitrary string will be accepted as the password for authentication). Thus our techniques increase usability with provably little loss of security. In particular, we propose applying a single password-corrective hash function to each entered password attempt. The key property of the hash function is that two strings differing by a single data entry error be likely to be hashed to the same key, while more substantially differing strings are hashed to different keys. We develop precise analytical formulae for the precision/recall tradeoffs for a variety of corrective hash functions. We evaluate these methods at parameter values reflecting common classes of keys/passwords. Finally, we evaluate these schemes using a popular crack-list (dictionary) of 680,000 common words. We show that we can correct for all user transposition errors while reducing the computational cost of a crack attack by only 13%.

This paper presents a hardware architecture for UNIX password cracking using Hellman’s time-memory trade-off; it is the first hardware design for a key search machine based on the rainbow variant proposed by Oechslin. The implementation target is the Berkeley BEE2 FPGA platform which can run at 400 million password calculations/second. Our design targets passwords of length 48 bits (out of 56). This means that with one BEE2 module the precomputation for one salt takes about 8 days, resulting in a storage of 56 Gigabyte. For the precomputation of all salts in one year we would need 92 BEE2 modules. Recovering an individual password requires a few minutes on a Virtex-4 FPGA.

Time/memory trade-off (TMTO) attacks require the generation of a sequence of functions which are obtained as minor modifications of a one-way function to be inverted. We carefully examine the requirements for such function generation. A counter based method is used to generate the functions for the rainbow method. We show that there are functions for which the counter method fails. This is similar to the example given by Fiat and Naor for the Hellman TMTO. Our main contribution is to suggest the use of LFSR sequences for function generation to be used in the rainbow TMTO. Properties of LFSR sequences such as long period, pseudorandomness properties and efficient forward and backward generation make such sequences useful for the intended application. One specific advantage is that it is not possible to a priori construct a Fiat-Naor type example for the LFSR based rainbow method.

Traditional password-based authentication and key-ex-change protocols suffer from the simple fact that a single server stores the sensitive user password. In practice, when such a server is compromised, a large number of user passwords, (usually password hashes) are exposed at once. A natural solution involves splitting password between two or more servers. This work formally models the basic security requirement for two-server password authentication protocols, and in this framework provides concrete security proofs for two protocols. The first protocol considered [7] appeared at USENIX'03, but contained no security proof. For this protocol, we provide a concrete reduction to the computational Diffie-Hellman problem in the random oracle model. Next we present a second protocol, based on the same hard problem, but which is simpler, and has an easier, tighter reduction proof.

Password authentication (PA) is a general and well-known technique to authenticate a user who is trying to establish a connection in distributed web services. The main idea of PA is to remove complex information from users so that they can log on servers only with a human-memorable password at anywhere. So far, many papers have been proposed to set up security requirements and improve the efficiency of PA. Most papers consider practical attacks such as password guessing, impersonation and server compromise which occur frequently in the real world. However, they missed an important and critical risk. A revealed password of a user from a server may affect other servers because most people tend to use a same password on different servers. This enables anyone who obtains a password to easily log onto other servers. In this paper, we first introduce a new notion, called “password pocket” which randomizes user’s password even if he/she types a same password on different servers. When our password pocket is used, an exposed password does not affect other servers any more. The cost of a password pocket is extremely low since it needs to store only one random number securely.

There exist practical bit-parallel algorithms for several types of pair-wise string processing, such as longest common subsequence computation or approximate string matching. The bit-parallel algorithms typically use a size-σ table of match bit-vectors, where the bits in the vector for a character λ identify the positions where the character λ occurs in one of the processed strings, and σ is the alphabet size. The time or space cost of computing the match table is not prohibitive with reasonably small alphabets such as ASCII text. However, for example in the case of general Unicode text the possible numerical code range of the characters is roughly one million. This makes using a simple table impractical. In this paper we evaluate three different schemes for overcoming this problem. First we propose to replace the character code table by a character code automaton. Then we compare this method with two other schemes: using a hash table, and the binary-search based solution proposed by Wu, Manber and Myers [25]. We find that the best choice is to use either the automaton-based method or a hash table.

A password-based key derivation function (KDF) – a function that derives cryptographic keys from a password – is necessary in many security applications. Like any password-based schemes, such KDFs are subject to key search attacks (often called dictionary attacks). Salt and iteration count are used in practice to significantly increase the workload of such attacks. These techniques have also been specified in widely adopted industry standards such as PKCS and IETF. Despite the importance and wide-spread usage, there has been no formal security analysis on existing constructions. In this paper, we propose a general security framework for password-based KDFs and introduce two security definitions each capturing a different attacking scenario. We study the most commonly used construction H(c)(p||s) and prove that the iteration count c, when fixed, does have an effect of stretching the password p by log2c bits. We then analyze the two standardized KDFs in PKCS#5. We show that both are secure if the adversary cannot influence the parameters but subject to attacks otherwise. Finally, we propose a new password-based KDF that is provably secure even when the adversary has full control of the parameters.

Flow state tables are an essential component for improving the performance of packet classification in network security and traffic management. Generally, a hash table is used to store the state of each flow due to its fast lookup speed. However, hash table collisions can severely reduce the effectiveness of packet classification using a flow state table. In this paper, we propose three schemes to reduce hash collisions by exploiting the locality in traffic. Our experiments show that all our proposed schemes perform better than the standard practice of hashing with overflow chains. More importantly, our move and insert to front scheme is insensitive to the hash table size.

A password-based protocol for authenticated key exchange must provide security against attacks using low entropy of a memorable password. We propose a new password-based protocol for authenticated key exchange, EPA (Efficient Password-based protocol for Authenticated key exchange), which has smaller computational and communicational workloads than previously proposed protocols with the same security requirements. EPA is an asymmetric model in which each client has a password and the server has a password file. While the server's password file is compromised, the client's password is not directly exposed. However, if the adversary mounts an additional dictionary attack, he can obtain the client's password. By using a modified amplified password file, we construct EPA+, which is secure against dictionary attack and server impersonation even if the server's password file is compromised.