روشی نوین در تجارت کردن زمان-حافظه برای بازیابی رمز عبور

As users become increasingly aware of the need to adopt strong password, it hinders the digital forensics investigations due to the password protection of potential evidence data. In this paper, we analyse and discuss existing password recovery methods, and identify the need for a more efficient and effective method to aid the digital forensics investigation process. We show that our new time-memory trade-off method is able to achieve up to a 50% reduction in terms of the storage requirement in comparison to the well-known rainbow table method while maintaining the same success rate. Even when taking into consideration the effect of collisions, we are able to demonstrate a significant increase (e.g. 13.28% to 19.14%, or up to 100% based on considering total plaintext–hash pairs generation) in terms of the success rate of recovery if the storage requirement and the computational complexity are to remain the same.

In Digital Forensics, the use of password protection presents a challenge for investigators while conducting examinations. While there exist methods to decode hashes to reveal passwords used to protect potential evidence, lengthier passwords with larger character sets have been encouraged to thwart password recovery. Awareness of the need to use stronger passwords and active adoption has rendered many existing password recovery tools inefficient or even ineffective. The more common methods of password recovery techniques are guessing, dictionary, brute force and more recently, using rainbow tables. The guessing method is attempting to crack passwords by trying “easy-to-remember” and common passwords like “password”, “1234”, etc. It can also be a password based on a user's personal information or a fuzzy index of words on the user's storage media. A statistical analysis of 28,000 passwords recently stolen from a popular U.S. website and posted on the Internet revealed that 16% took a first name as a password and 14% relied on “easy-to-remember” keyboard combinations (Yahoo News, 2009). Therefore, the guessing method can be quite effective in some cases where users are willing to compromise security for the sake of convenience. The dictionary attack method composes of loading a file of dictionary words into a password cracking tool to search for a match of their hash values with the stored one. Examples of some of these password cracking tools include Cain and Abel (Cain and Abel), John the Ripper (John The Ripper) and LCP (LCPSoft). In the brute force cryptanalytic attack, every possible combination of the password characters is attempted to perform a match comparison. It is an extremely time consuming process but the password will be recovered eventually if a long enough time is given. Cain and Abel, John the Ripper as well as LCP are able to conduct brute force attacks. In Hellman (1980), Hellman introduced a method which involves a trade-off between the computation time and storage space needed for performing recovery of a hash value to its plaintext form. It can be applied to retrieve Windows login passwords encrypted into LM or NTLM hashes (Todorov, 2007), as well as passwords in applications using the above-mentioned hash algorithms, such as the Adobe Acrobat. It can also be used to crack the encryption used in Microsoft Word and Excel documents. Passwords encrypted with hashing algorithms such as MD5 (Rivest, 1992), SHA-2 (National Institute of Standards and Technology (NIST), 2002) and RIPEMD-160 (Dobbertin et al., 1996) are also susceptible to this recovery method. In addition, this method is applicable to many searching tasks including the knapsack and discrete logarithm problems. In Oechslin (2003), Oechslin proposed a faster cryptanalytical time-memory trade-off method, which is an improvement over Hellman's method. Since then, this method has been widely used and implemented in many popular password recovery tools. The pre-computed tables that are generated in this method are known as the rainbow tables. The details of this method will be covered further in Section 2. There are currently numerous products of pre-computed rainbow tables in the market. The more prominent ones are RainbowCrack (Shuanglei) and Ophcrack (Objectif Sécurité). RainbowCrack is developed by S. Zhu. It is a direct implementation of Oechslin's method. Several patches have since been released to support more hash algorithms including MD5 and SHA-1 (National Institute of Standards and Technology (NIST), 1995), as well as to increase the character set size. Ophcrack is owned by Objectif Sécurité, a leading Swiss consulting company in the field of information systems. Ophcrack is also a direct implementation of Oechslin's method developed by Oechslin himself and C. Tissieres. However, Ophcrack can only process LM and NTLM hashes. AccessData ( AccessData) is another company adopting rainbow tables in their password recovery tools. In this paper, we present a new design of a time-memory trade-off pre-computed table structure. Comparison of our method is made against the rainbow table method (Oechslin, 2003), as it is the most efficient and effective password recovery method to-date. We demonstrate the improvement in effectiveness and performance, in terms of increased success rate in password recovery while maintaining the same amount of storage space and computational complexity. Our new method is shown to significantly increase the success rate by up to 100% for total plaintext–hash pairs comparison and 13.28% to 19.14% in a few example scenarios for distinct pairs comparison. Up to a 50% reduction in terms of storage requirement is achieved. This translates to about 1.35 TB storage conservation compared to the AccessData rainbow tables, which has an average size of 2.7 TB each (AccessData), while maintaining the same success rate. The rest of the paper is organised as follow. In Section 2, we present a detailed analysis and discussion on existing time-memory trade-off password recovery methods. We describe the rainbow table method in more details in Section 3. We present the design of our new method in Section 4. Analysis and performance evaluations are carried out in Section 5 to demonstrate the performance enhancement. Future work is described in Section 6. Conclusions follow in Section 7.

In this paper, we firstly identified the need for a better password recovery method due to the increasingly stronger passwords users are using. We proceeded to introduce the common but weaker techniques used, such as brute force and dictionary attacks. More efficient time-memory trade-off methods were then analysed and discussed. We concluded that the rainbow table method is to-date the most popular and efficient method to perform password recovery. However, with the improvement in the adoption of stronger passwords, the rainbow table method is facing increasing challenges as seen in the huge increase in the storage requirement for newer tables. This prompted us to perform an in-depth evaluation of the rainbow table method and propose a better method to solve the challenge. The novelty of the new method lies in the new chain generation process as well as the significant storage space conservation or successful recovery rate improvement brought about by this process. A better recovery rate is achieved if the storage space is maintained the same, or vice versa. Comparison of our method is made against the rainbow table method due to its well-known efficiency and effectiveness in password recovery. The new method is shown to significantly increase the success rate by up to 100% for total plaintext–hash pairs comparison and 13.28% to 19.14% in a few example scenarios for distinct pairs comparison. Up to a 50% reduction in terms of storage requirement is achieved if the success rate is maintained to be the same as the rainbow table method. Therefore, the newly proposed method shows very promising results due to its significant improvement over the existing methods, to aid in the process of digital forensics investigations, to uncover password-protected potential evidence.