Analysis of the use of Rainbow Tables to break hash Josef Horáleka,[footnoteRef:1], Filip Holíka, Oldřich Horákb, Lukáš Petrb and Vladimir Sobeslavc [1: Corresponding author. E-mail: josef.horalek@upce.cz] aDepartment of Information Technology, Faculty of Electrical Engineering and Informatics, University of Pardubice, Studentská 95, 532 10 Pardubice, Czech Republic bInstitute of System Engineering and Informatics, Faculty of Economics and Administration, University of Pardubice, Studentská 95, 532 10 Pardubice, Czech Republic cDepartment of Information Technologies, Faculty of Informatics and Management, University of Hradec Králové, Rokitanského 62, 500 03 Hradec Králové III, Czech Republic Abstract. This paper acquaints with a created application for generating Rainbow Tables and the results of testing Rainbow Tables, according to the length of the chosen chain. The paper presents a specialized application containing its own algorithms for reduction functions, changing the length of chain, generating Rainbow Tables and measuring the effectivity of the password search in detail. Within the executed tests, the dependence of Rainbow Tables size on the password length, the affection of the hash search by the size of the chosen chain and their links to collisions, which arise from the principle of using the reduction function, were observed. The results objectively describe the pros and cons of using Rainbow Tables and show the possibilities and restrictions for their effective usage. Keywords: Rainbow Tables, hash, MD5, efficiency testing, breaking hash Introduction Nowadays, with the dynamic evolution and extension of information technologies and its usage, the secrecy of information is emphasized. We can say that nowadays the leakage of sensitive information is a huge threat and it exposes the owner of the data to possible security risks. With the expansion of internet and the digital world, even a little mistake in an algorithm is a possibility for an attack and the attacker can operate with the data without a problem and he can spread this mistake over the network. Because of that, high requirements are imposed on cryptography, so the encryption system is reliable, theoretically indecipherable, adequately complicated, not too much memory demanding, unbreakable in real time, easy to implement and quick enough for encryption and decryption. There is a lot of requests and the computing power of today’s machines is still growing, so it is important to extend and develop new and superior algorithms, so we can avoid their breakage. The author in work [1, 2] mentions the procedures of password cracking and states some concepts associated with those issues. The work describes the methods of access to password cracking, he also states other approaches (methods), which can help with password cracking (frequency analysis, Markov model, etc.). This work also states the basic principle of Rainbow Tables and their access to password cracking. It also mentions some programs, which are used for password cracking or testing the overall security of the login system. It relies on several hash functions, however, their algorithm is not mentioned in the work. The work contains a considerable range of tools, methods and approaches to password cracking. In the publication [3, 4] the author deals with the use of probability in cracking user passwords. At the beginning he mentions the forms of saving user passwords in different branches (Unix, Windows, Wi-Fi, web sites, etc.). The author also mentions software used for password cracking. The key part of this work is the analysis of passwords in general (their length, used characters, etc.), he uses basic methods, such as frequency analysis, statistics of leaked password databases, Markov model, brute force and more. The work also mentions the use of Rainbow Tables for a dictionary attack in detail. The work also deals with the probability of cracking the user passwords. The whole text is statistically oriented, it tries to analyze the current situation and uses results and tables published on the internet (password lengths, used characters, occurrence frequency). The work [5] deals with IseCrack, which is a powerful implementation of Rainbow Tables, using the computing power of nVidia graphic cards. In the beginning, the author mentions the issue of passwords and hash functions (salt, one-way hash function). The key task of the work is to apply the calculations of big Rainbow Tables to the graphic card (GPU), which is faster than the processor (CPU). This allows a speed-up of password cracking and at the same time it allows to extend the use of Rainbow Tables for passwords with more characters. The author compares the implementation of the algorithm to CPU and GPU. In the publications [5, 6, 7] the authors deal with the hash function MD5. The publications describe the construction of MD5 in detail, but they also deal with the breaking of MD5, by searching for collisions. Other important publications in the area of cryptography are [8-12]. The theme of those papers is the issue of hash functions, principles of breaking the hash function MD5 [13, 14] and also the algorithm for electronic signatures. Rainbow tables Rainbow tables belongs into TMTO (Time-Memory Trade-Off) methods. These methods use memory in order to lower total time needed to find a correct password. The first concept of using recalculated tables was developed by Martin Hellman (Hellman’s table 1980), but his approach used only one reduction function. On the CRYPTO 2003 conference [20, 21], Philippe Oechslin published improved version of Hellman’s tables. This new method used higher number of reduction functions, which author labeled as rainbow – thus the name Rainbow tables. The publication also contained a practical example of breaking Windows password containing alphanumeric symbols with success rate of 99,9% using tables with size of 1,4GB. Rainbow tables are pre-calculated tables used for password search from hash imprint. The maximum size of a single table is limited (for all passwords from keyspace) in dependence on password length and number of characters which a password can contain. Searching and managing a single large table is also slower and more difficult. For these reasons, Rainbow tables are using multiple smaller tables. Multiple reduction functions in chain columns eliminates collisions of texts and hashs so, that the tables are smallest possible and does not contain any duplicates. [15 - 18] The biggest limit of rainbow tables is password length. If the password length is higher than 8 characters and is using characters [a-z, A-Z, 0-9], the number of possible combination is 218 340 105 584 896 ((26+26+10) * 628). In this example, real time generation of such a table is not possible and cracking the password in a given time fame cannot be achieved. Method is therefore suitable only for passwords with limited character length. [19] Another use cases where Rainbow tables are not usable are salted passwords (salt makes simple password more complex) and multiple usage of hash function or combination of several different hash functions, i.e. . In this case the attacker would have to modify generation mechanism of Rainbow tables and create special tables for this specific hash function. The main strengths of rainbow tables is a search speed. While brute force complexity is O(n), rainbow tables have complexity for a single table O(n) = (hash table search x chain length) and for a multiple tables O(n) = number of tables (hash table search x chain length). Usage of Rainbow tables Rainbow tables are used to break hash imprint of a password in order to discover it. This method can be used if an attacker has access to the database of passwords with passwords stored in hash form (not in plain text). Rainbow tables can then search for hash values and find the original password. This process is not trivial and it is only partially solved by Rainbow tables. In order to effectively use Rainbow tables, it is convenient to know certain characteristics of user’s password like its length. The password length can be often derived from system requirements or by watching user entering the password). If the password length is unknown, multiple combinations and search in multiple tables have to be used, making the attack much more time consuming. Another important prerequisite is knowledge of used hash function. If this is not available, multiple tables for different hash functions have to be used. In general, multiple techniques and tools have to be used to make a successful attack. Rainbow tables are a perfect technique to break user password if some knowledge about the password is available. Search in Rainbow tables can be parallelized, making it ideal for distributed systems. Many programs dealing with Rainbow tables can be found on the Internet. Some of the tables are free, but many have to be purchased. Usage of these tables will save time, because the tables do not have to be generated first. [22, 23] Rainbow tables structure A structure of Rainbow tables can look like the table 1. This table contains text and hash imprint. Hash is stored as a key value in order to make searching faster. If there are any collisions in hashs, reduction has to be executed in order to merge the collision rows and therefore to preserve only a single key value (otherwise there would be different text for the same hash value). While constructing Rainbow tables, allowed characters ([a-z], etc.) and hash function (MD5, SHA-1, etc.) have to be selected. The appropriate length of chain is also important as it influence the table size and speed of search algorithm. By selecting a proper reduction function, better results and lower number of collision can be achieved. Table 1 – Rainbow Table without end collision hash Text Hash aaaa 3c62c99bafbe3a81f16d36b592b66ae5 aaab 7991ef7c61d85c505adb63b70553b0ce aaac ef834a79dc0ac78e355859ec4f698d0b aaad 3bb75d8a8effe7c5e18aC6670a3c3346 Problem definition and analysis The use of Rainbow Tables for password cracking from a known hash is a basic operation, but it is time consuming and computationally demanding. For the effective use of Rainbow Tables it is important to verify some basic parameters and bonds, which can significantly affect the effective use of this tool. The first tested parameter is the dependence of the Rainbow Tables generation time, time for the reduction function, and the size of the final table on the length of the password. Another key parameter, which was measured and tested is the average time to find a password depending on the chain length and the size of the Rainbow Table depending on cha-in. It was also necessary to check the coverage of the whole key-space with a pre-chosen probability of 80% on the length of chain. This should allow the reduction of the size of the generated Rainbow Tables, generation time and the password search effectively. The last examined parameter was the dependence of the number of collisions on the length of chain. To check the behavior of Rainbow Tables mentioned above, a testing application was developed, it is introduced below, including its own design of the reduction function and the search logic, which is introduced further in detail. Application for testing To test the effectiveness of password cracking using Rainbow Tables, an application, which allows to search for the real password by using the fingerprint, was developed. The application searches for the password using the Brute force algorithm at the same time. The application was written in the C# language and the .NET Framework 4.5 environment. Created application has those functional parts, which allow its effective use: Generating a table of restricted size of the password – 6 characters, A-Z Searching for the password by the hash value Measuring the table generation time Searching for the password using the Brute force algorithm The possibility of finding the password in a finite time (or inform the user, that the password was not found) Visualization of the Rainbow Tables method MD5 hash function It is important to keep the Rainbow Table in the appropriate data structure, which is able to search quickly by the key value. A hash table (dictionary) was selected for the application, hash was selected as a key and a list of strings as a value. Because of the collisions of final hash it was not possible to use any of the strings and while designing the reduction function for the creation of chain the function was designed to be different for each column, so any similarities are avoided. The chain itself was designed as a chain of hash function and reduction function. Individual chain values are saved into a list of strings, or to a pair hash – text, which is then inserted into the dictionary of the Rainbow Table. Chain As a Chain we call a string of texts, where the chain starts by t0 and by a gradual transition using a hash function and a reduction function it ends by h2, the length of a chain like that three (Count(rj) + 1) – see Eq. (1). (1) Chains are used to build and to search (reconstruct) the wanted password in Rainbow Tables. The Rainbow Table by itself does not contain the whole chain intentionally. The length of chain (the number of reduction functions + 1) affects Rainbow Tables while generating tables. If we chose a chain that is too long, more computing power will be needed to create the chain and thereby the total table generation time will grow. Because of the reduction function, which is not injective, the number of collisions will grow. That will appear thanks to the reduction of duplicated rows in Rainbow Tables, which will reduce the size of the tables on the hard drive. The search time in Rainbow Tables will increase, because the search in width is used. If a small length of chain is chosen, we will need less computing power to build the Rainbow tables, however, the size of the tables on the hard drive will increase and the speed of finding the password in the Rainbow Tables will increase as well. Chain can be presented as a linear list, which will hold the text values t0, h0, t1, h1…hn. A static class Chain is defined within the program, it contains two static methods TokenToChain and TokenToShortChain. Those methods are quite similar. TokenToChain recieves a string text and an integer ChainLength as an input. The value Text determines the first value of the chain string t0, the input value ChainLength determines the length of the chain: public static class Chain { public static List TokenToChain (string text, int ChainLength) { List chain=new List (); string hash=string.Empty; for (int i=0; i <= ChainLength; i++) { hash=HashMD5.Text2Hash(text); chain.Add(text); chain.Add(hash); text=RFunction.Hash2Text(hash, i, text.Length); } return chain; } } The reduction function The reduction function is a mathematical function, which is used to transfer from the hash set to the set of all texts. For its denomination, it will be used rj(hi), i=0…n, j=0…m, or the Eq. (2): (2) This function is not injective, two models can have an identical image, which causes collisions and it is surjective, each image has its own model. Therefore, it has similar properties to the hash function. The problem is, that collisions occur more frequently than they occur in a hash function, because it is an output to a smaller set. Output from the hash set to the text set is problematic, the probability of a collision is a lot higher and there is no universal design for a reduction function. To eliminate multiple collisions, it has to be used more reduction functions, different for each column. From the properties of the output it is obvious that the design of this function is nontrivial. Therefore it is important to analyze each step. Selecting integers from hash fingerprints The first option is the selection of the integers from the hash fingerprint. If there is a hash: 3c62c99bafbe3a81f16d36b592b66ae5, the integers 362993811636592665 are selected, and the first 4 digits are converted to ASCII characters: 3629 → dgcj A reduction function designed like this only returns a limited number of ASCII characters (one digit = 0-9 ASCII characters). There is 26 characters [a-z], therefore it needs more digits to get all the characters. For example if the 8 digits 36299381 is processed in pairs, it finds out the remainder in the division by 26 (modulo symbol %) and it get a number 0-25, as it can be seen in the example: r 3c62c99bafbe3a81f16d36b592b66ae5 → kxpx 36%26 = 10 → k 29%26 = 23 → x 93%26 = 15 → p 81%26 = 23 → x This procedure will create a reduction function, which converts the hash to a text value. The selection of integers from the hash fingerprints can be problematic. If we want to create more reduction functions, for example a different one for every column of the chain, we will soon come to the end of the set of numerals and the number of numerals will be exhausted. Selecting hexadecimal values from hash fingerprints Another possibility is the selection of hexadecimal values from the hash fingerprint. It is a hash with size of 128 bits usually written by 32 hexadecimal numbers, i.e. 3c62c99bafbe3a81f16d36b592b66ae5. The hexadecimal number can be used for the conversion to an ASCII character, and this feature can be used for the reduction. First, a hexadecimal number is converted to a decimal number and then to a character: r 3c62c99bafbe3a81f16d36b592b66ae5 → iutz (3c)16 = (60)10, 60%26 = 8 → i (62)16 = (98)10, 98%26 = 20 → u (c9)16 = (201)10, 201%26 = 19 → t (9b)16 = (155)10, 155%26 = 25 → z This is how to get the output . More reduction functions The reduction of multiple collisions with repetition (one reduction function) is solved by using more reduction functions. For each column of the chain a different reduction function is used. Thus increasing the power of Rainbow Tables, however, not all the collisions will be removed. If it is planned to implement more reduction functions (rj), each reduction function can be implemented separately (r1, r2, r3 … rn) or used just one reduction function, and then been used a transformation based on an index shift. The method of index shift is very simple, basically only one reduction function is used, but for each column of the chain its index is used and a shift is performed. The principle of this method is shown in this example, where a hash reduction function r0, and then r1 are used: r0 3c62c99bafbe3a81f16d36b592b66ae5 → iutz (3c)16 = (60)10, 60%26 = 8 → i (62)16 = (98)10, 98%26 = 20 → u (c9)16 = (201)10, 201%26 = 19 → t (9b)16 = (155)10, 155%26 = 25 → z This is how to get the output . 3c62c99bafbe3a81f16d36b592b66ae5 → qsxar1 (c6)16 = (198)10, 198%26 = 16 → q (2c)16 = (44)10, 44%26 = 18 → s (99)16 = (153)10, 153%26 = 23 → x (ba)16 = (186)10, 186%26 = 0 → a This is how to get the output , however this process is restricted, because if the chain length is large, it moves to the end of hash. In this case it has to perform some kind of transposition of the index and then it can be chosen a hexadecimal number by transposition. Collisions and their elimination For a proper understanding of the whole issue of Rainbow Tables it is important to realize, that it cannot be find all of the password combinations and their hash in Rainbow Tables, but that they contain text and hash. The text marks how the chain starts and hash marks how the chain ends, the remaining information from chain is reduced, therefore disposed. While searching, it can be rebuild the chain retrospectively. With this reduction it can be lower the memory demands and then save the computer’s hard drive space. When only one reduction function is used and if there is a match in one part of the chain, collisions repeat and there are multiple matching values. However, if it is used multiple reduction functions (for example a different one for each column of the chain), it eliminates that and there will be no matches. However, if the collisions occur in the same column it will not be possible to eliminate the matches. Based on the reduction function principles and their use for eliminating collisions presented above, the method CollisionReduction was implemented in the application. It is an important function ensuring the removal of hash collisions between two Rainbow Tables. The function is based on the passage through the whole table partlyRT1, in which it is searched for a match in the other Rainbow Table partlyRT2. If it finds a match, it adds values to the given keys into emphpartlyRT1 and it takes out the collision row from the partlyRT2 table. If removed all of the collisions, it can save the tables using the Write method. Before this reduction, the Rainbow Table is roughly the same size, CollisionReduction reduces the size of the Rainbow Table and removes the collision, to the final size. public static void CollisionReduction (Dictionary > partlyRT1, string name1, Dictionary > partlyRT2, string name2, string path) { foreach (var kpv in partlyRT1) { if (partlyRT2.ContainsKey(kpv.Key)) { kpv.Value.AddRange(partlyRT2 [kpv.Key]); partlyRT2.Remove(kpv.Key); } } RainbowTable.Write(partlyRT1,name1,path); RainbowTable.Write(partlyRT2,name2,path); } Rainbow Table Rainbow Table presents a one table of the Rainbow Tables. Ideally it should have just one big table instead of more tables, however, with a higher number of characters and with a longer password, this process would be untenable due to the memory demands. Due to the occurrence of the final hash collisions it does not store just the hash and text, but it stores the hash and a list of texts. The existence of the final hash collisions can be dealt with when inserting a row to the Rainbow Table. Tables generated like this can contain matching data. In the reduction algorithm it can go through and compare all the tables. This will reduce the size of the tables on the hard drive and it makes the search for the hash by the key value easier. Within the application the RainbowTables class encapsulates the RainbowTable class and it allows to work with more tables as if they formed a whole. It contains similar methods (FindPassword, CollisionReduction) as the RainbowTable class, but unlike the class, it works across all tables. It also allows to access the information about times (generating tables, password search and the reduction time), it also allows the window application to access the chain list and Rainbow Table to render into the form RainbowTablesForm. The method CreateRainbowTables creates individual Rainbow Tables and the multi-thread creation was used to accelerate the process. User oriented class RainbowTablesForm, has the task of rendering a graphical user interface, making the controls accessible and enabling the use of the RainbowTables class. Password search by final hash To find a password by the hash value it loads one table to the memory and searches by the hash key. If it does not find the hash value, it performs a reduction and applies a hash function. It get a new hash, which will be searched for in the table again. This process is applied until it finds a match. The process can be exemplified by the chain length = 3 and a simplified table: Rainbow Table: Chain: It identifies the wanted hash as hh and it will assume, that hh=h0. It searches for the hh hash in the Rainbow Table. If it finds it, it get the chain value (chain list in case of a collision), which contains the password. If the hash is not found in the Rainbow Table, it has to perform a reduction and apply a hash function. If it uses just one reduction function, the process is easier. In this step, we do not know on which position of the chain is the wanted hash located (or in which column, it could be in the first column or the second one), but we know that the hash is not located in the third column. For the option, that it is in the second column, it performs a reduction r1 and convert to hash again, it declares it as . It searches for this hash in the Rainbow Table again. If it does not find the hash in the previous step, it has to choose another option and that is that the hash is located in the first column. It performs a recudction r0 and convert the result to hash, it repeates this step with the reduction function r1. It get a hash, which it declares as , it searches for it in the Rainbow Table (it found a match ) If it finds the wanted hash in the Rainbow Table, it get the chain, which contains our password. It knows the chain and the column, in which the hash is located, now it can perform a reconstruction of the chain, and search for the hh hash on the position of the column. If the chain contains the hash, it returns a password, which is located before the hash value (if it presents the chain as a list for example). If it finds a match after n steps (n = the length of chain), it has to load another Rainbow Table and repeat this process. If it searches in one table, the number of steps required for the password search is . Based on the presented principles a method FindPassword, which searches for a password by the hash chain in the Rainbow Table, was implemented. How the process of search works, is explained in a short example: Search for a password by hash: 77CC7F Table 2 – Shortened reduced Rainbow Table Hash Text 3c62c9 aaaa, ouwc, yusk 7991ef aaab, hmpp, saum, vbvx ef834a aaac, amrv, eopt, ilim 3bb75d aaad, hnzb, jgqp, lgmq, ndzy, spkn, ulnz Search the Rainbow Table by hash value. If it finds the hash, it continues to the step no.3, otherwise to the step no.4 Convert the hash to text by using a reduction function and then convert to hash again; go back to the step no.2 with the new hash value (the maximum number of times this process is performed equals the length of chain): text: puwr, hash: 584C19 text: kcyl, hash: 48950E text: uhtc, hash: 3BB75D If find the hash (3BB75D) in the Rainbow Table, it means that the password is located in a chain from the list of values (aaad, hnzb, jgqp, lgmq, ndzy, spkn), it continues to the step no.5. Go through the list of values linearly and we create a chain for each one, it searches for the original hash (77CC7F) in the chain; if find it, it returns the password at a given index (indexHash – 1). The found chain is: public string FindPassword o (string hash) { string token = hash; string password = string .Empty; string h1 = string .Empty; List tokeny; for (int i = 0; i <= ChainLenght; i++) { h1 = hash; int index = ChainLenght - i; for (int j = index; j tokeny, int index, string hash) { List chain; for (int i = 0; i < tokeny.Count; i++) { chain = Chain.TokenToChain(tokeny[i], this.ChainLenght, this.NumberOfChar); if (chain.Contains(hash)) { this.ChainFound = chain; if (chain[(index _2)+1] == hash) { return chain[index _2]; } } } return string.Empty; } Testing results Testing was conducted in various iterations to get a relevant result. Simultaneously the methods of generating were optimized, so the application for generating Rainbow Tables is executable on common PCs and the result was generated in real time. For the final testing, tables were generated to the maximum password length of six characters and passwords composed of characters [a-z] using the chain with length of 4. The chain length was chosen with regard to the possibility of visualizing the chain. For this selected range it can be generated the Rainbow Tables in approximately 15 minutes. Generating Rainbow Tables for 6 characters took approximately 3 hours and the reduction took about 5 hours. All calculations were performed on a PC with an AMD Phenom II X6 1100T processor and 16GB of RAM. A comprehensive overview of generation times, reduction times and the size of finalized tables for the password length of 2 to 6 and the chain length of 5 are stated in the following Tab. 3: Table 3 – Information on generating tables Password length 2 3 4 5 6 Generation time [s] 0,249 1,497 12,08 327,946 11420,35 Reduction time [s] 2,644 6,404 19,304 558,084 18441,93 Size of tables 104kB 312kB 6,73MB 167MB 4GB A detailed test was done within the testing, its goal was to compare the password search by using Rainbow Tables and by using the Brute force algorithm. The test was performed on a set of 2000 passwords, a sample with the final times in milliseconds is presented in the Tab. 4. The Brute force algorithm tests all the combinations linearly, until it finds a match. This algorithm, as expected, is faster than the Rain-bow Tables, if the password is composed from the characters on the beginning of the alphabet. Rainbow Tables, on the other side, generates tables also sequentially, but because we do not save the whole chain, just the beginning and the final hash, even the search of the aaa password is directed (if there is a table, containing a chain with the aaa string, in the memory, it has to search for the chain in the table by hash value and reconstruct the password). The test shows, that the Rainbow Tables algorithm can be 10 times faster than the Brute force algorithm. An important parameter for Rainbow Tables is the chain length. The choice of this parameter is not given and it depends on the user’s choice. For the shown measurement a chain length of 4 was chosen, however, in practice a greater length is often chosen. The longer the chain is, the tables take up less disk space of the computer, but at the same time, the number of collisions grows and the search time grows as well. Ideally it would be best to have a minimal chain length, so the search is faster. However, those tables would take so much disk space. Assuming that the Rainbow Table for all the combinations would not fit in the memory, we have to split the table into multiple smaller tables. By doing so, the number of disc operations for uploading the table into memory will grow. Finding the optimal chain length was also a goal of the performed tests. Table 4 – Time in ms search Rainbow Tables and Brute Force No. Password Brute force Rainbow tables Brute force / Rainbow tables 1 aa 0 1 0,0 2 aaa 0 2 0,0 3 aaaa 0 59 0,0 4 aaaaa 0 1 715 0,0 5 aaaaaa 0 21 984 0,0 6 bac 7 7 1,0 7 back 210 98 2,1 8 backu 4 802 3 042 1,6 9 Backup 117 646 116 054 1,0 10 coff 479 61 7,9 11 coffe 11 836 4 332 2,7 12 coffee 291 497 174 758 1,7 13 ho 2 2 1,0 14 hos 65 4 16,3 15 host 1 325 128 10,4 16 hostk 31 662 5 401 5,9 17 hostka 870 911 87 666 9,9 18 my 2 5 0,4 19 myp 103 10 10,3 20 mypa 2 137 358 6,0 21 mypas 55 209 3 080 17,9 22 mypass 1 485 137 36 598 40,6 23 sh 3 2 1,5 24 sha 104 3 34,7 25 shad 2 944 457 6,4 26 shado 76 957 4 523 17,0 27 shadow 2 094 713 311 318 6,7 28 zz 10 11 0,9 29 Zzz 172 7 24,6 30 Zzzz 4 234 56 75,6 31 zzzzz 111 231 2 843 39,1 32 zzzzzz 3 001 050 158 819 18,9 Average 254 842,70 26 731,96 10,89 To find the optimal chain length it was searched for a value, when the password search time was minimal with the longest chain. A similar test to the test for comparing the Rainbow Tables and Brute force algorithms was created. Individual Rainbow Tables for different chain lengths, with the password length (2 - 4) were created. The selected sets of passwords were searched for in the Rainbow Tables with different chain lengths. As a parameter for the measurement the time of each search was chosen, from which was counted the average time of one password search. By this measurement was watched how the average search time in Rainbow Tables grow with a different chain length. The time to generate tables grows with a greater chain length, because more operations are performed by the hash function and the reduction function while creating the chain. On the other side, the space that the tables take up, decreases with a greater chain length, because there are more collision rows in one table. In the Fig. 1 the chart, presenting the influence of the chain length parameter on the password search, is presented. Fig. 1 – Dependence on the chain length of the average time to find the password At the end of the test, in which observed the chain lengths and average password search time, it was compared the sizes of generated Rainbow Tables. In the Fig. 2 is a chart, displaying the change of the size of Rainbow Tables on the hard drive, depending on the chain length is presented. This reduction of the Rainbow Tables’ size is caused by the reduction of the final chains, with a greater chain lengths more collisions occur, while generating the whole key-space. Fig. 2. – The size of Rainbow Tables in dependence on the length of chain From the previous tests there is a hypothesis, that if we increase the chain length, it will not have to generate all of the combinations of input strings (aaa – zzz), it was generated just a part (e.g. aaa - tzz) and with a pre-required probability (e.g. 80%) all passwords can be found in the tables. This thought was tested on the created application and the selected results are shown in Fig. 3. Sub-combinations for each letter separately, i.e. aaa-azz = 1, baa-bzz = 2, to zaa-zzz = 26. Therefore a total of 26 sub-sets was generated and it was observed the probability of covering the whole key-space. Fig. 3 – Change the probability of a chain length Another logically observed parameter was the number of collisions in chain. From the measurement results it can be concluded, that with the change of the chain length it could gain the percentual coverage of the space of combinations sooner and therefore it will not be necessary to generate a chain for each input combination, thus lowering the requirements on the disc capacity. An important finding of the per-formed tests is, that with the growing chain length collisions multiply. This grow of collisions is faster than the growing of the probability, as seen in Fig. 4. Fig. 4 – The number of collisions versus length of chain For this reason the hypothesis, that for the generation time optimization and the Rainbow Table size optimization for a probabilistic cover of the whole key-space it is possible to use the growth of the chain length, was denied. If it has to choose an optimal chain length parameter, it is necessary to take all the measured values into account (probability, errors, the size on the hard disk, password search time), but it also has to consider the power of the computer, on which the Rainbow Tables are generated or the password is searched. All those parameters will affect the choice of the optimal chain length. Conclusion Generating Rainbow Tables takes some time, but if the tables are generated and targeted directly for a specific case, it is possible to optimize this time and in comparison with the Brute force method, this time is relevant. Today’s procedures can count tables within tens of minutes and if the computing power of the graphic card is used, this time is significantly reduced. The only problem occurs in the disk space needed to save the finalized tables. If the tables are generated for long passwords, which contain the whole key-space including the national characters, the size of Rainbow Tables can grow to a size of terabytes (TB). In that case the space available on ordinary PCs will not be enough and to crack a password like this, it will be necessary to use servers with the appropriate data storage. A problem can also occur in terms of time: in huge tables the password search may not be solved with the appropriate speed and the obtained information may not be actual. There is an option of using a pre-generated table, which is possible to download or use a knowledgebase obtained from the exploration of the rising methods of social engineering and thereby optimize the generated combinations without any request to cover the whole key-space. The last option is to use distributed Rainbow Tables (online cracking), in which we can get the wanted result relatively easily, thanks to the distributed calculations. Acknowledgment This work and contribution is supported by the project of the student grant competition of the University of Pardubice, Faculty of Electrical Engineering and Informatics, Security Smart Grid Networks and Cloud Computing, and the student grant competition of the University of Pardubice, Faculty of Economics and Administration, Economic and Social Development in Private and Public Sector. References P. Tasevski, Password Attacks and Generation Strategies. Tartu University, 2011. Master of Science in Cyber Security. Tartu University, Faculty of Mathematics and Computer Sciences. P. Su, C. Shang and Q. Shen. A hierarchical fuzzy cluster ensemble approach and its application to big data clustering. Journal of Intelligent & Fuzzy Systems. 2015, 28(6), 2409-2421. DOI: 10.3233/IFS-141518. ISSN 10641246. C.M. Weir, Using Probabilistic Techniques To Aid In Password Cracking Attacks. Electronic Theses, Treatises and Dissertations. Florida State University, 2010. S.R. Ratna, R. Ravi and B. Shekhar. An intelligent approach based on neuro-fuzzy detachment scheme for preventing jamming attack in wireless networks. Journal of Intelligent & Fuzzy Systems. 2015, 28(2), 809-820. DOI: 10.3233/IFS-141363. ISSN 1064-1246. R.E. Graves, High performance password cracking by implementing rainbow tables on nVidia graphics cards (IseCrack). Master of Science. Iowa State University, 2008. National Institute of Standards and Technology, Secure Hash Standard: FIPS PUB 180-2. T. Niknam, B. Bagheri, M.M. Bonehkhater, and B.B. Firouzi. A new teaching-learning-based optimization algorithm for distribution system state estimation. Journal of Intelligent & Fuzzy Systems. 2015, 29(2), 791-801. DOI: 10.3233/IFS-141579. ISSN 10641246. P. Oechslin, Making a Faster Cryptanalytic Time-Memory Trade-Off [online], p. 617 [cit. 2016-05-11], DOI: 10.1007/978-3-540-45146-4_36, http://link.springer.com/10.1007/978-3-540-45146-4_36 S. Marechal, Advances in Password Cracking. Journal in Computer Virology [online], 2008, 4(1), p. 73-81 [cit. 2016-05-11], DOI: 10.1007/s11416-007-0064-y, ISSN 1772-9890. J.-C. Guo, D. Fan, H.-Y. Che, Y.-N. Duan, H.-S. Wang, and D.-W. Zhang. An approach to network security evaluation of computer network information system with triangular fuzzy information. Journal of Intelligent & Fuzzy Systems. 2015, 28(5), 2029-2035. DOI: 10.3233/IFS-141458. ISSN 10641246. Y. Wang, X. Peng and J. Bian. Study on the security of information system authentication scheme based on the fuzzy number intuitionistic fuzzy information. Journal of Intelligent & Fuzzy Systems. 2015, 28(5), 2225-2232. DOI: 10.3233/IFS-141504. ISSN 10641246. Y. Zeng, R. Xiao. A networked approach to dynamic analysis of social system vulnerability. Journal of Intelligent & Fuzzy Systems. 2015, 28(1), 189-197. DOI: 10.3233/IFS-141289. ISSN 1064-1246. K. Theocharoulis, I. Papaefstathiou and C. Manifavas, Implementing Rainbow Tables in High-End FPGAs for Super-Fast Password Cracking, International Conference on Field Programmable Logic and Applications, IEEE, 2010, pp. 145-150, DOI: 10.1109/FPL.2010.120, ISBN 978-1-4244-7842-2. A. Khazaei, M. Ghasemzadeh and V. Derhami. An automatic method for CVSS score prediction using vulnerabilities description. Journal of Intelligent & Fuzzy Systems. 2015, 30(1), 89-96. DOI: 10.3233/IFS-151733. ISSN 10641246. M. Kalenderi, D. Pnevmatikatos, I. Papaefstathiou a C. Manifavas, Breaking the GSM A5/1 Cryptography Algorithm with Rainbow Tables and High-End FPGAS, In: 22nd International Conference on Field Programmable Logic and Applications (FPL) [online], IEEE, 2012, pp. 747-753 [cit. 2016-05-11], DOI: 10.1109/FPL.2012.6339146, ISBN 978-1-4673-2256-0. P. Boothroyd and X.N. Phạm, Socioeconomic Renovation in Viet-Nam: The Origin, Evolution, and Impact Of Doi Moi, DOI: 10.1016/J.DIIN.2009.06.002. N. Rathore, I. Chana. Job migration with fault tolerance based QoS scheduling using hash table functionality in social Grid computing. Journal of Intelligent & Fuzzy Systems. 2014, 6(27), 2821-2833. DOI: 10.3233/IFS-141243. ISSN 1064-1246. Y. Zhang, Research on the computer network security evaluation based on the DHFHCG operator with dual hesitant fuzzy information. Journal of Intelligent & Fuzzy Systems. 2015, 28(1), 199-204. DOI: 10.3233/IFS-141290. ISSN 1064-1246. B.H. Bloom, Space/Time Trade-offs in Hash Coding with Allowable Errors, Communications of the ACM [online], 13(7), pp. 422-426 [cit. 2016-05-11], DOI: 10.1145/362686.362692, ISSN 00010782. P. Oechslin, Making a Faster Cryptanalytic Time-Memory Trade-Off. Laboratoire de Securite et de Cryptographie (LASEC) [online] 2003. [cit. 2016-07-05]. Available from: http://lasec.epfl.ch/~oechslin/publications/crypto03.pdf. P. Tasevski: Password Attacks and Generation Strategies. Tartu University, 2011. Master of Science in Cyber Security. Tartu University, Faculty of Mathematics and Computer Sciences. [online]. [cit. 2016-07-05]. Available from: http://home.cyber.ee/ahtbu/CDS2011/PredragTasevskiSlides.pdf. Ch. Weir, Using Probabilistic Techniques to Aid in Password Cracking Attacks. Electronic Theses, Treatises and Dissertations. Florida State University, 2010. [online]. [cit. 2016-07-05]. Available from: http://diginole.lib.fsu.edu/etd/1213. P. Yuen, Practical cryptology and Web security. New York: Pearson Education LTD, 2006. p. cm. ISBN 03-212-6333-2. length of chain 5 0 0 0 0 0.01 0.01 0.03 0.04 7.0000000000000007E-2 0.1 0.14000000000000001 0.19 0.25 0.32 0.39 0.46 0.53 0.6 0.66 0.72 0.78 0.83 0.88 0.92 0.96 1 length of chain 31 0 0 0.01 0.02 0.04 0.08 0.14000000000000001 0.22 0.31 0.41 0.5 0.59 0.66 0.72 0.77 0.81 0.83 0.86 0.88 0.9 0.92 0.93 0.95 0.96 0.98 1 Keyspace Probability length of chain 5 0 0 0 3 18 59 269 654 1716 3843 8045 15413 27757 47470 76790 118328 176007 251413 348193 469069 616386 793388 999067 1238743 1513971 1827904 length of chain 31 0 0 25 222 814 3013 10287 26454 61027 122487 223590 373794 583104 862293 1218869 1663749 2207759 2861619 36369 44 4548257 5609661 6836565 8241947 9844531 11660585 13709280 length of chain 2 2 32 162 512 1247 2584 4777 8134 12951 19602 28447 39806 54070 71365 92016 116029 143150 173471 206329 240842 276852 312725 350439 387176 423172 456976 length of chain 11 0 0 0 30 109 387 1428 3629 9016 19530 38959 71147 121255 194800 296044 429770 601659 814393 1072592 1381605 1745726 2170680 2658428 3217301 3852047 4569760 Keyspace The number of collisions 6.7 5.3 4.5999999999999996 4.2 3.8 3.6 3.4 3.4 3.2 3.2 3 3 2.9 2.9 2.9 2.9 2.8 2.8 2.8 2.8 2.8 2.7 2.7 2.6 2.6 2.6 2.6 2.5 2.5 2.5 2.5 2.5 2.5 2.5 2.5 2.5 2.5 2.4 2.4 Chain length Size MB image1.png