Search

MD5 is a one-way cryptographic function used in various fields for maintaining data integrity. The application of a Hash function can provide much protection and privacy and subsequently reduce data usage. Most users are familiar with validating electronic documents based on a Hash function, such as the MD5 algorithm and other hash functions, to demonstrate the data integrity. There are many weaknesses of the current MD5 algorithm, mainly its failures and weaknesses against varying types of attacks, such as brute force attacks, rainbow table attacks, and Christmas attacks. Therefore, the method proposed in this paper enhances the MD5 algorithm by adding a dynamic variable length and a high efficiency that simulates the highest security available. Whereas the logistic system was used to encode ribonucleic acid (RNA) by generating a random matrix based on a new key that was created using the initial permutation (IP) tables used in the data encryption stander (DES) with the linear-feedback shift register (LFSR), this work proposes several structures to improve the MD5 hash function. The experimental results demonstrate its high resistance to hackers while maintaining a suitable duration. This paper discusses the design of a confident hash algorithm. This algorithm has characteristics that enable it to succeed in the field of digital authentication and data integrity.

Recently, there has been a rise in impactful data breaches releasing billions of people’s online accounts and financial data into the public domain. The result is an increased importance of effective cybersecurity measures, especially regarding the storage of user passwords. Strong password storage security means that an actor cannot use the passwords in vectors such as credential-stuffing attacks despite having access to breached data. It will also limit user exposure to threats such as unauthorized account charges or account takeovers. This research evaluates the effectiveness of different password storage techniques. The storage techniques to be tested are: BCRYPT Hashing, SHA-256 Hashing, SHA-256 with Salt, and SHA-256 with MD5 Chaining. Following the National Institute of Standards and Technology (NIST) guidelines on password strength, both a weak and robust password will be passed through the stated techniques. Reversal of each of the results will be attempted using Rainbow Tables and dictionary attacks. The study results show that pairing a strong password that has not been exposed in a data breach with the BCRYPT hashing algorithm results in the most robust password security. However, SHA-256 hashing with a salt results in a very similar level of security while maintaining better performance. While plain SHA-256 hashing or chaining multiple hashing algorithms together is theoretically as secure, in practice, they are easily susceptible to simple attacks and thus should not be used in a production environment. Requiring strong password which have not been exposed in previous data breaches was also found to greatly increase security.

International audience; Cryptanalytic time-memory trade-offs (TMTOs) are techniques commonly used in computer security e.g., to crack passwords. However, TMTOs usually encounter in practice a bottleneck that is the time needed to perform the precomputation phase (preceding to the attack). We introduce in this paper a technique, called distributed filtration-computation, that significantly reduces the precomputation time without any negative impact the online phase. Experiments performed on large problems with a 128-core computer perfectly match the theoretical expectations. We construct a rainbow table for a space N=242 in approximately 8 h instead of 50 h for the usual way to generate a table. We also show that the efficiency of our technique is very close from the theoretical time lower bound.

Secure password storage is a vital aspect in systems based on password authentication, which is still the most widely used authentication technique, despite some security flaws. In this paper, we propose a password authentication framework that is designed for secure password storage and could be easily integrated into existing authentication systems. In our framework, first, the received plain password from a client is hashed through a cryptographic hash function (e.g., SHA-256). Then, the hashed password is converted into a negative password. Finally, the negative password is encrypted into an encrypted negative password (ENP) using a symmetric-key algorithm (e.g., AES), and multi-iteration encryption could be employed to further improve security. The cryptographic hash function and symmetric encryption make it difficult to crack passwords from ENPs. Moreover, there are lots of corresponding ENPs for a given plain password, which makes precomputation attacks (e.g., lookup table attack and rainbow table attack) infeasible. The algorithm complexity analyses and comparisons show that the ENP could resist lookup table attack and provide stronger password protection under dictionary attack. It is worth mentioning that the ENP does not introduce extra elements (e.g., salt); besides this, the ENP could still resist precomputation attacks. Most importantly, the ENP is the first password protection scheme that combines the cryptographic hash function, the negative password, and the symmetric-key algorithm, without the need for additional information except the plain password.

Apple's file-sharing service AirDrop leaks phone numbers and email addresses by exchanging vulnerable hash values of the user's own contact identifiers during the authentication handshake with nearby devices. In a paper presented at USENIX Security'21, we theoretically describe two attacks to exploit these vulnerabilities and propose "PrivateDrop" as a privacy-preserving drop-in replacement for Apple's AirDrop protocol based on private set intersection. In this demo, we show how these vulnerabilities are efficiently exploitable via Wi-Fi and physical proximity to a target. Privacy and security implications include the possibility of conducting advanced spear phishing attacks or deploying multiple "collector" devices in order to build databases that map contact identifiers to specific locations. For our proof-of-concept, we leverage a custom rainbow table construction to reverse SHA-256 hashes of phone numbers in a matter of milliseconds. We discuss the trade-off between success rate and storage requirements of the rainbow table and, after following responsible disclosure with Apple, we publish our proof-of-concept implementation as "AirCollect" on GitHub.

In this paper, we give a fast decryption method of Excel document encrypted by RC4 algorithm. Through a detailed analysis of document storage structure and encryption process, we illustrate the inner principle of key generation and data encryption in the block by block manner. We present an efficient way of recovering the intermediate key by using rainbow table attack, which can be directly applied to decrypt the Excel document. The advantage of our method is that the decryption time of one document is no longer affected by the password length and complexity. In our practical test, it has achieved the decryption of Excel encrypted documents in an average of 3 minutes on a common personal computer, which greatly improves decryption efficiency of encrypted documents compared with the current dictionary and brute force attack methods of recovering document password.

Passwords are barriers that protect unauthorized users from accessing personal information in any application. Protecting passwords is one of the challenging tasks in today's world. Currently, a combination of Username/Password used for authentication for a large number of applications. Malicious users might try to steal/misuse the user's data for unethical purposes. To prevent passwords from stealing, developers prefer to use one-way hash functions. One-way hash functions are theoretically irreversible functions that take as an input variable size text and output fixed-sized text. In reality, hash functions are not collision-resistant. Therefore it is recommended to use passwords and randomly generated text called salt to generate hash values and prevent rainbow tables and dictionary attacks. Passwords are hashed at the client-side and sent across the public channel/network. A salt is a randomly generated alphanumeric text used to concatenate with a password to generate a random hash value. This paper demonstrates how the random generation of salt is dependent on passwords and how hash values are dependent on salt. Further, analysis of the behaviour of passwords and hash values using various tools like Wireshark, Ettercap, and Hydra are presented in the paper.

This paper represents a new approach to rainbow tables, a method of password recovery that was originally developed by Martin E. Hellman and then improved by P. Oechslin, so most of its implementations use Oechslin’s modification. An improvement represented in this work mostly lies in the reduction function, which uses character statistics to generate more "human-like" passwords. Though it generates passwords 5 to 10 times slower than reduction function, which uses direct dependency between hash bytes and the inserted characters, it significantly increases common efficiency in memory (8 to 30 times less memory needed to store these tables) and successful "human-like" passwords recovery probability, while these tables are generated by the same time as tables with the use of "random" reduction function.

This paper proposes the implementation of high speed rainbow table generation using Keccak hashing algorithm with the integrated development environment CUDA for GPU in the heterogeneous GPU+CPU system. Utilizing the GPU’s powerful capacity, the algorithm greatly improves the performance of rainbow chain generation by dispatching the pre-computation of rainbow chain to each GPU thread. The table generation speed on GPU+CPU system and CPU was compared by the configuration of chain length and number of chains in this paper. In addition, the password coverage rate of table generated by the proposed reduction function was evaluated.The speed-up of pre-computation on GPU GeForce GTX 1080 outperforms that on CPU Xeon E5-1620 v4 3.5GHz by 239 times when the chain length is 200.

Researchers and experts had developed numerous hash-based password authentication schemes. Inappropriately, most of them are susceptible to different attacks. This study centers on the process of performing cryptanalysis on the developed Head and Tail (HT) technique for hashing passwords. The research tested the HT technique in terms of its capacity to resist a dictionary attack, rainbow tables attack, and brute-force attack. To test the strength of the HT technique, HashCat, John the Ripper, RainbowCrack, and online cracking systems from crackstation.net and hashkiller.co.uk were used as tools for cracking. After the experiment, the result shows that the cracking tools failed to crack the HT technique. Further tests showed that generating a password-hash value pair or lookup table for MD5-HT and SHA1-HT is 16 times slower than standard MD5 and SHA1. Thus, the Head and Tail (HT) technique is a secured method for hashing passwords.

At present, the MD5 algorithm in network security of got to a wide range of applications in many respects, but in be used actually face being hit by a "rainbow table" library of security risks, this design adopts the method of "salt", based on the proposed encryption definitely added to the random Numbers to reduce the risk. This article first introduces the principle and the risk for the MD5 algorithm and puts forward the theoretical basis to solve the problem, and then describes the improvement to solve the problem of the MD5 algorithm in FPGA to realize the overall architecture, analyses the function of each module, finally gives the Altera corporation based on series of the Cyclone II device DE2 system board the implementation of the results. Through the experimental results can be seen that the MD5 algorithm based on FPGA implementation has high processing speed and less resource usage, and based on FPGA and "salt" of plaintext processing can effectively reduce the use of the risk of "rainbow table" bump library, has certain practical value 1

User authentication is necessary to provide services on an application system and the Internet. Various authentication methods are used such as ID/PW, biometric, and OTP authentications. One of the popular authentications is ID/PW authentication. As an inputted password is transferred by one-way hash function and then stored in DB, it is difficult for the DB administrator to figure out the password inputted by the user. However, when DB is leaked, and there is the time to decode, the password can be hacked. The time and cost to decode the original message from the hash value corresponding a short password decrease. Therefore, if the password is short, then attacking cost is low, and password crack possibility is high. In the case where an attacker utilizes pre-computing rainbow tables, and the hash value of short passwords is leaked, the password that the user inputted can be cracked. In this research, to block rainbow table attacks, when the user generates a short password, by adding additional messages of identification information of a system or the user and extending the length of the password, we try to resolve the vulnerability of short passwords. By proposing a model to minimize the length of the password and the authority accordingly in mobile devices on which inputting passwords is not easy, we take security into consideration. Our proposal model is strong against rainbow table attack and provides efficient password system to users. It contributes to resolving password vulnerability and upgrades mobile users’ convenience in typing passwords.

Tento dokument seznamuje s vytvořenou aplikaci pro generovani Rainbow tabulek a výsledky testů s využitim Rainbow tables podle delky zvoleneho řetězce. Přispěvek prezentuje specializovanou aplikaci obsahujici vlastni algoritmy pro funkce redukce, změnu delky řetězce, generovani Rainbow tables a detailni měřeni efektivity při vyhledavani hesla. V ramci testů je dale popsana zavislost velikosti rainbow tables na delce hesla, ovlivněni hash vyhledavani podle velikosti zvoleneho řetězce a propojeni s kolizemi, ktere vyvstavaji z principu využiti redukcni funkce. Výsledky objektivně popisuji výhody a nevýhody využiti Rainbow tables a ukazuji možnosti a omezeni pro jejich efektivni využiti.

The password recovery of popular encryption applications has great practical significance not only for the circumstance of retrieving forgotten password but also for assisting law enforcement officers to implement data forensics. In this paper, we propose an improved password recovery method based on rainbow table attack which enables the recovery feasibility of long human chosen passwords. We combine advantage of dictionary generator and rainbow table to produce an efficient and smart approach of cracking long and complicated passwords. We present the detailed attack process and algorithms of this novel cracking method including dictionary generator specification, transform rules configuration as well as the design of kernel functions in rainbow table attack. Finally, we also provide a practical test and relevant analysis of password recovery result.

In this paper, we describe the new method of data encryption/decryption with selectable block and key length and hash function. The block size directly improves the efficiency but also impacts on memory complexity of the presented solution. The choice of hash function length results in computational complexity and complicates attacks using rainbow tables. The algorithm is a modification of SP (Substitution-Permutation) concept with the use of static S-blocks and dynamically indexed block permutation. In further step, usage of chosen operational modes of the method (ECB, CBC, CTR) is presented. In the article there is the example with all the algorithm parameters i.e. input and output data, key value, hash function type and set of all method internal states. The efficiency of the solution was experimentally examined and compared with the most popular bock cipher algorithms e.g. AES, Serpent, BlowFish, TwoFish. The obtained initial results indicate that the new method can be dedicated especially for systems with high security requirements. The paper conclusions contain propositions of algorithm implementation optimizations and further research.

Hash algorithms have been widely used for cryptography. It has been impossible to decrypt the ciphertexts generated through hash algorithms, as an operation that damages the original text is performed. However, various methods of attack occurred over time after the algorithm was developed. The vulnerability of SHA1 (an old hash algorithm) has been revealed, and there has been a great deal of data available for dictionary attacks. Although the industry has been gradually refraining from using SHA1, it remains in use in some existing systems for various reasons. For example, when problems resulting from service interruption or mass update are critical, updating the encryption algorithm can be a burden. In this study, we aim to increase the complexity of ciphertexts by postprocessing hash ciphertext. For that, image salting techniques are used using two-dimensional array masking. This will allow the use of hash ciphertexts with increased complexity in some devices that are forced to use old hash algorithms for various reasons.

The task of function inversion is central to cryptanalysis: breaking block ciphers, forging signatures, and cracking password hashes are all special cases of the function-inversion problem. In 1980, Hellman showed that it is possible to invert a random function \(f{:}\,[N] \rightarrow [N]\) in time \(T = \widetilde{O}(N^{2/3})\) given only \(S = \widetilde{O}(N^{2/3})\) bits of precomputed advice about f. Hellman’s algorithm is the basis for the popular “Rainbow Tables” technique (Oechslin 2003), which achieves the same asymptotic cost and is widely used in practical cryptanalysis.

[ES] El acceso a los sistemas informáticos está desde siempre ligado a la utilización de palabras de paso o passwords. Por motivos de seguridad, los passwords se han almacenado de forma oculta en los sistemas, siendo habitualmente el resultado de la aplicación de una función resumen -o hash- sobre el password. Dichas funciones resumen tienen una gran relevancia para el mantenimiento seguro de los passwords. También son invertibles, con una probabilidad de colisión inversamente proporcional de forma exponencial al número de bits del resumen. Una aproximación para encontrar dichas colisiones se basa en la construcción de las denominadas tablas del arco iris, que emplean una aproximación time-memory trade-off (TMTO), mostrándose eficientes a la hora de encontrar colisiones y posibilitando el acceso no autorizado a los sistemas., [CA] L’accés al sistemes informàtics ha estat des-de sempre lligat a l’ús de paraules de pas o passwords. Per motius de seguretat, els passwords son emmagatzemats de forma oculta als sistemes, seguint habitualment el resultat de l’aplicació d’una funció resum -o hash- sobre el password. Aquestes funcions resum tenen una gran rellevància a l’hora de mantindre els passwords segurament. També son invertibles, amb una probabilitat de col·lisió inversament proporcional exponencialment al nombre de bits del resum. Una aproximació per a encontrar dites col·lisions son les denominades taules rainbow, que fan ús d’una aproximació time-memory trade-off (TMTO), mostrant-se eficients a l’hora d’encontrar col·lisions i possibilitant l’accés no autoritzat als sistemes., [EN] Access to computer systems has always been tied to the use of passwords. For security reasons, passwords are stored in an occult manner, being usually the result of a hash function on the password. Said hash functions are highly relevant for safe-keeping passwords. They are also reversible, having a collision probability inversely proportional exponentially to the number of bits in the hash. An approximation for finding such collisions is based in the generation of the so called rainbow tables, which make use of a time-memory trade-off (TMTO), showing efficiency when looking for those collisions and allowing unauthorised access to the systems.

Despite being one of the most crucial parts of online transactions, the most used authentication system, the username and password system, has shown to be weaker than ever. With the increase of processing power within computers, offline password attacks such as dictionary attacks, rainbow tables, and hash tables have become more effective against divulging account information from stolen databases. This has led to alternative solutions being proposed, such as logging in with a social media account or password managers, which do not replace the password entirely. Graphical alternatives have previously proposed, but none of them have become widely used. In a previous paper we proposed our own alternative called “Grid Authentication”, which would allow users to authenticate using a sequence of clicks on a colored Grid, shown to be resistant against offline password attacks. Now we have implemented and tested Grid Authentication’s memorability and recorded user sentiment data. Participants logged in using a newly created password, an 8-character password randomly generated for them, as well as used Grid Authentication scheme for three days each, once per day. We found that overall, Grid Authentication’s memorability was like a user chosen password, and far superior to the randomly generated 8-character password. We also observed that user’s overall sentiment towards Grid Authentication increased significantly after three days of regular use. Despite this, while sentiment over the system was overall positive, users perceived that they remembered the password more easily, perhaps given hints as to why alternative authentication types have not become widely used.

Graphical password can be used as an alternative to text based (alphanumeric) password in which users click on images to set their passwords. Text based password uses username and password. So recalling of password is necessary which may be a difficult one. Images are generally easier to be remembered than text and in Graphical password; user can set images as their password. Therefore graphical password has been proposed by many researchers as an alternative to text based password Graphical passwords can be applied to workstation, web log-in applications, ATM machines, mobile devices etc. This paper presents implementation of Cued click point (CCP) graphical password which uses circular tolerance. Then it is found that CCP with circular tolerance is better as compared to CCP with rectangular tolerance.

Password based authentication shows its vulnerability against inversion attack model in which adversary obtains plaintext password from its corresponding hashed value. To cope up with such attack, honeyword based authentication technique is introduced. In this technique, along with the original password of user, some dummy passwords or honeywords are also stored. Although this technique is good enough to address the aforementioned security breach, but use of additional storage to store the honeywords is still an overhead associated with such approach. In this paper, we have proposed few directions to minimize the storage cost of some of the existing honeyword generation approaches. We have even found that in some cases no additional storage overhead is required. A comparative analysis at the end also shows that the proposed techniques are able to raise some of the security features compared to existing honeyword generation approaches.

The purpose of this case study analysis is to examine a non-traditional method of identifying weak passwords within a large hospital organization. The process of using rainbow tables to crack passwords/ensure password compliance is discussed and specific examples are provided within this paper. This process emphasizes the notion that network security-related problems tend to be organization-specific and require creative approaches. The goal is to establish a practical use for rainbow tables within an organization as a means of enhancing network security.

PixCaptcha as graphical password is done by cropping the image from the selected image according to the hints and paste it in the appropriate place. Even though the graphical passwords are the best replacement to overcome the limitations of the alpha numeric passwords, the encrypted graphical password's database is cracked by the hacker with the Rainbow table attack. Rainbow tables make password cracking much faster than earlier methods, such as brute-force cracking and dictionary attacks. Here a strong encryption algorithm is applied before storing the password in the database. Gaussian Elimination Technique is applied and Cleaves encryption is a new encryption scheme that provides strong resilience against Rainbow table attacks. This paper is presented with implementation of PixCaptcha as Graphical password, Gaussian Elimination Technique and Cleaves encryption algorithm which is applied to useful real-world scenario such as password protection. Further, it facilitates the high security by increasing the complexity of password guessing and cracking attacks.

The encryption of WPA & WPA2 is the present and security protection for the wireless LAN. With the vigorous development of parallel computing (GPU), the speed of cryptanalysis is rising up and getting more popular which causes the great threat to the Wi-Fi security. It is time-consuming for the wireless passwords analysis for the huge total combinations of 9563 max. Now, it is the turning point that the leap progress of GPU makes the Wi-Fi cryptanalysis much more efficient than before. In this research, we proposed a much faster speed (270,000 PMKs/s) compared to those in years, and the speed of computing PMKs/s is the major crucial factor and base for the mainstream of wireless passwords attacks, such as brute force, dictionary, time-memory trade-off (rainbow attack), and the generations of dictionary files.

As a penetration tester, you will often encounter words like hash, password, and encryption; cracking a hash value is a separate category of ethical hacking, and it belongs to the Password Attacks submenu in the Applications menu of Kali Linux. If you want to dig deep, you can enter the world of cryptography, which I will discuss in the next chapter. There are also many good password-cracking tools available in Kali Linux. You will also learn how to use a few of them.

Many people own Android mobile phones. Various sources indicate that Android mobile has exceeded iOS (Apple iPhone) in overall world sales for a few years. A user enabled security such as the pattern lock may be a stumbling block when it comes to forensically examining the device. There are other forms of security for Androids, each potentially causing the same issue, preventing forensic tools from reading the stored user data. The gesture pattern, however, is still largely, one of the most popular enabled security measures set by the user. Tools that can bypass the gesture pattern, and in turn decode the acquisition, often utilize built-in scripts to construct the pattern in an easy format for the examiner to understand. Having a basic understanding of how the gesture pattern is stored, and how it could be manually decoded, can assist in validation, testimony, and overall understanding of the automated parsing of this value.

At its heart, a password cracking attack is a modeling problem. An attacker makes guesses about a user’s password until they guess correctly or they give up. While the defender may limit the number of guesses an attacker is allowed, a password’s strength often depends on how hard it is for an attacker to model and reproduce the way in which a user created their password. If humans were effective at practicing unique habits or generating and remembering random values, cracking passwords would be a near impossible task. That is not the case, though. A vast majority of people still follow common patterns, from capitalizing the first letter of their password to putting numbers at the end. While people have remained mostly the same, the password security field has undergone major changes in an ongoing arms race between the attackers and defenders. The goal of this chapter is to highlight the current state of password cracking techniques, as well as discuss some of the cutting edge approaches that may become more prevalent in the near future.

Cybersecurity has become one of the largest growing fields in computer science and the technology industry. Faulty security has cost the global economy immense losses. Oftentimes, the pitfall in such financial loss is due to the security of passwords. Companies and regular people alike do not do enough to enforce strict password guidelines like the NIST (National Institute of Standard Technology) recommends. When big security breaches happen, thousands to millions of passwords can be exposed and stored into files, meaning people are susceptible to dictionary and rainbow table attacks. Those are only two examples of attacks that are used to crack passwords. In this paper, we will be going over three open-source password managers, each chosen for their own uniqueness. Our results will conclude on the overall security of each password manager using a list of established attacks and development of new potential attacks on such software. Additionally, we will compare our research with the limited research already conducted on password managers. Finally, we will provide some general guidelines of how to develop a better and more secure password manager.

Rainbow table is the well-known cryptanalytic method for searching the encryption key or the plaintext. The user can precompute several lookup tables in order to increase the success probability. These tables can be distributed to multiprocessor or parallel machines for decreasing the makespan. Searching problem using the Rainbow table differs from the others traditional problem. The problem can only be solved on some node. However, if the problem can't be solved on current node, it must be re-executed on the other node. Thus, using FCFS algorithm is not the proper solution. We proposed the fuzzy scheduling for the parallel key searching problem, using Rainbow table. The algorithm is implemented and evaluated by Cloudsim. The result shows the proposed method reduces the makespan from the traditional FCFS.

A novel optical image encryption system is proposed using password key based on phase retrieval algorithm (PRA). In the encryption process, a shared image is taken as a symmetric key and the plaintext is encoded into the phase-only mask based on the iterative PRA. The linear relationship between the plaintext and ciphertext is broken using the password key, which can resist the known plaintext attack. The symmetric key and the retrieved phase are imported into the input plane and Fourier plane of 4f system during the decryption, respectively, so as to obtain the plaintext on the CCD. Finally, we analyse the key space of the password key, and the results show that the proposed scheme can resist a brute force attack due to the flexibility of the password key.

WOS: 000359984600009 It is a common mistake of application developers to store user passwords within databases as plaintext or only as their unsalted hash values. Many real-life successful hacking attempts that enabled attackers to get unauthorized access to sensitive database entries including user passwords have been experienced in the past. Seizing password hashes, attackers perform brute-force, dictionary, or rainbow-table attacks to reveal plaintext passwords from their hashes. Dictionary attacks are very fast for cracking hashes but their success rate is not sufficient. In this paper, we propose a novel method for improving dictionary attacks. Our method exploits several password patterns that are commonly preferred by users when trying to choose a complex and strong password. In order to analyze and show success rates of our developed method, we performed cracking tests on real-life leaked password hashes using both a traditional dictionary and our pattern-based dictionary. We observed that our pattern-based method is superior for cracking password hashes.

The performances of three major time memory tradeoff algorithms were compared in a recent paper. The algorithms considered there were the classical Hellman tradeoff and the non-perfect table versions of the distinguished point method and the rainbow table method. This paper adds the perfect table versions of the distinguished point method and the rainbow table method to the list, so that all the major tradeoff algorithms may now be compared against each other. Even though there are existing claims as to the superiority of one tradeoff algorithm over another algorithm, the algorithm performance comparisons provided by the current work and the recent paper mentioned above are of higher practical value. We provide comparisons of algorithms at parameters that achieve a common success rate of inversion and which take both the cost of pre-computation and the efficiency of the online phase into account. The comparisons are based on the average case execution behaviors rather than the worst case situations, and non-negligible details such as the effects of false alarms and various storage optimization techniques are no longer ignored. A large portion of this paper is allocated to analyzing the execution behavior of the perfect table distinguished point method. In particular, we obtain a closed-form formula for the average length of chains associated with a perfect distinguished point table.

Accessing and searching in a sequence of numbers are fundamental operations in computing that are encountered in a wide range of applications. One of the applications of the problem is cryptanalytic time-memory tradeoff which is aimed at a one-way function. A rainbow table, which is a common method for the time-memory tradeoff, contains elements from an input domain of a hash function that are normally sorted integers. In this paper, we present a practical indexing method for a monotonically increasing static sequence of numbers where the access and search queries can be addressed efficiently in terms of both time and space complexity. For a sequence of n numbers from a universe U = {0, ..., m ? 1}, our data structure requires n lg(m/n) + O(n) bits with constant average running time for both access and search queries. We also give an analysis of the time and space complexities of the data structure, supported by experiments with rainbow tables.