1331:. When stretching is used, the salt, password, and some intermediate hash values are run through the underlying hash function multiple times to increase the computation time required to hash each password. For instance, MD5-Crypt uses a 1000 iteration loop that repeatedly feeds the salt, password, and current intermediate hash value back into the underlying MD5 hash function. The user's password hash is the concatenation of the salt value (which is not secret) and the final hash. The extra time is not noticeable to users because they have to wait only a fraction of a second each time they log in. On the other hand, stretching reduces the effectiveness of brute-force attacks in proportion to the number of iterations because it reduces the number of attempts an attacker can perform in a given time frame. This principle is applied in MD5-Crypt and in bcrypt. It also greatly increases the time needed to build a precomputed table, but in the absence of salt, this needs only be done once.
968:(produce the same value), they will merge and consequently the table will not cover as many passwords despite having paid the same computational cost to generate. Because previous chains are not stored in their entirety, this is impossible to detect efficiently. For example, if the third value in chain 3 matches the second value in chain 7, the two chains will cover almost the same sequence of values, but their final values will not be the same. The hash function H is unlikely to produce collisions as it is usually considered an important security feature not to do so, but the reduction function R, because of its need to correctly cover the likely plaintexts, cannot be
130:
976:
used for likely plaintexts, not the entire space of possible passwords. In effect R shepherds the results of prior hash calculations back to likely plaintexts but this benefit comes with the drawback that R likely won't produce every possible plaintext in the class the attacker wishes to check denying certainty to the attacker that no passwords came from their chosen class. Also it can be difficult to design the function R to match the expected distribution of plaintexts.
142:
reduction function in each column. When colors are used to represent the reduction functions, a rainbow appears in the rainbow table. Figure 2 of
Oechslin's paper contains a black-and-white graphic that illustrates how these sections are related. For his presentation at the Crypto 2003 conference, Oechslin added color to the graphic in order to make the rainbow association more clear. The enhanced graphic that was presented at the conference is shown in the illustration.
1097:
2967:
1338:, extends the key with a random salt, but then (unlike in key stretching) securely deletes the salt. This forces both the attacker and legitimate users to perform a brute-force search for the salt value. Although the paper that introduced key stretching referred to this earlier technique and intentionally chose a different name, the term "key strengthening" is now often (arguably incorrectly) used to refer to key stretching.
419:
45:, usually for cracking password hashes. Passwords are typically stored not in plain text form, but as hash values. If such a database of hashed passwords falls into the hands of attackers, they can use a precomputed rainbow table to recover the plaintext passwords. A common defense against this attack is to compute the hashes using a
1349:, an older hash algorithm used by Microsoft, are publicly available. LM hash is particularly vulnerable because passwords longer than 7 characters are broken into two sections, each of which is hashed separately. Choosing a password that is fifteen characters or longer guarantees that an LM hash will not be generated.
924:
734:
1342:
passwords, such as adding a number or special character. Because of the sizable investment in computing processing, rainbow tables beyond fourteen places in length are not yet common. So, choosing a password that is longer than fourteen characters may force an attacker to resort to brute-force methods.
1341:
Rainbow tables and other precomputation attacks do not work against passwords that contain symbols outside the range presupposed, or that are longer than those precomputed by the attacker. However, tables can be generated that take into account common ways in which users attempt to choose more secure
1102:
Rainbow tables use a refined algorithm with a different reduction function for each "link" in a chain, so that when there is a hash collision in two or more chains, the chains will not merge as long as the collision doesn't occur at the same position in each chain. This increases the probability of a
975:
Other difficulties result from the importance of choosing the correct function for R. Picking R to be the identity is little better than a brute force approach. Only when the attacker has a good idea of likely plaintexts will they be able to choose a function R that makes sure time and space are only
960:
The table content does not depend on the hash value to be inverted. It is created once and then repeatedly used for the lookups unmodified. Increasing the length of the chain decreases the size of the table. However, it also increases the time required to perform lookups, and this is the time-memory
141:
was first used in
Oechslin's initial paper. The term refers to the way different reduction functions are used to increase the success rate of the attack. The original method by Hellman uses many small tables with a different reduction function each. Rainbow tables are much bigger and use a different
1299:
The salt value is not secret and may be generated at random and stored with the password hash. A large salt value prevents precomputation attacks, including rainbow tables, by ensuring that each user's password is hashed uniquely. This means that two users with the same password will have different
1324:—have salts of 128 bits. These larger salt values make precomputation attacks against these systems infeasible for almost any length of a password. Even if the attacker could generate a million tables per second, they would still need billions of years to generate tables for all possible salts.
94:
When a user enters a password for authentication, a hash is computed for it and then compared to the stored hash for that user. Authentication fails if the two hashes do not match; moreover, authentication would equally fail if a hashed value were entered as a password, since the authentication
1035:
Although rainbow tables have to follow more chains, they make up for this by having fewer tables: simple hash chain tables cannot grow beyond a certain size without rapidly becoming inefficient due to merging chains; to deal with this, they maintain multiple tables, and each lookup must search
219:
1002:: consequently, the final values in these chain will be identical. A final postprocessing pass can sort the chains in the table and remove any "duplicate" chains that have the same final values as other chains. New chains are then generated to fill out the table. These chains are not
91:. Since passwords stored as plaintext are easily stolen if database access is compromised, databases typically store hashes instead. Thus, no one – including the authentication system – can learn a password merely by looking at the value stored in the database.
1300:
password hashes (assuming different salts are used). In order to succeed, an attacker needs to precompute tables for each possible salt value. The salt must be large enough, otherwise an attacker can make a table for each salt value. For older
458:
by applying R, then H, then R, and so on. If at any point a value matches one of the endpoints in the table, the corresponding starting point allows to recreate the complete chain. There's a high chance that this chain will contain the value
772:
1032:; and so on until the last chain, which applies all the reduction functions, alternating with H. This creates a new way of producing a false alarm: an incorrect "guess" of the position of the hash value may needlessly evaluate a chain.
579:
556:
1143:
In the simple case where the reduction function and the hash function have no collision, given a complete rainbow table (one that makes sure to find the corresponding password given any hash) the size of the password set
414:{\displaystyle {\color {Red}{\mathtt {aaaaaa}}}\,{\xrightarrow{}}\,{\mathtt {281DAF40}}\,{\xrightarrow{}}\,{\mathtt {sgfnyd}}\,{\xrightarrow{}}\,{\mathtt {920ECF10}}\,{\xrightarrow{}}\,{\color {Violet}{\mathtt {kiebgt}}}}
1103:
correct crack for a given table size, at the cost of squaring the number of steps required per lookup, as the lookup routine now also needs to iterate through the index of the first reduction function used in the chain.
213:
of alternating passwords and hash values are formed. For example, if P were the set of lowercase alphabetic 6-character passwords, and hash values were 32 bits long, a chain might look like this:
961:
trade-off of the rainbow table. In a simple case of one-item chains, the lookup is very fast, but the table is very big. Once chains get longer, the lookup slows, but the table size goes down.
201:
R that maps hash values back into values in P. Note, however, that the reduction function is not actually an inverse of the hash function, but rather a different function with a swapped
1053:
Starting from the hash ("re3xes") in the image below, one computes the last reduction used in the table and checks whether the password appears in the last column of the table (step 1).
1894:
1063:
Note: If this new test fails again, one continues with 3 reductions, 4 reductions, etc. until the password is found. If no chain contains the password, then the attack has failed.
1250:
1385:) and is also unsalted, which makes it one of the most popularly generated tables. Rainbow tables have seen reduced usage as of 2020 as salting is more common and GPU-based
447:. In the example chain above, "aaaaaa" would be the starting point and "kiebgt" would be the endpoint, and none of the other passwords (or the hash values) would be stored.
1009:
Using sequences of reduction functions changes how lookup is done: because the hash value of interest may be found at any location in the chain, it's necessary to generate
919:{\displaystyle {\mathtt {FB107E70}}\,{\xrightarrow{}}\,{\mathtt {bvtdll}}\,{\xrightarrow{}}\,{\mathtt {0EE80890}}\,{\xrightarrow{}}\,{\color {Violet}{\mathtt {kiebgt}}}}
113:) may be used to try to invert a hash function, they can become infeasible when the set of possible passwords is large enough. An alternative to brute-force is to use
729:{\displaystyle {\color {Red}{\mathtt {aaaaaa}}}\,{\xrightarrow{}}\,{\mathtt {281DAF40}}\,{\xrightarrow{}}\,{\mathtt {sgfnyd}}\,{\xrightarrow{}}\,{\mathtt {920ECF10}}}
1197:
480:
2947:
2777:
197:
is the size of an output of H, which is prohibitive for large |P|. Hash chains are a technique for decreasing this space requirement. The idea is to define a
1304:
which used a 12-bit salt this would require 4096 tables, a significant increase in cost for the attacker, but not impractical with terabyte hard drives. The
64:
which calculates a hash on every attempt, but more processing time and less storage than a simple table that stores the hash of every possible password.
53:" to each password before hashing it, with different passwords receiving different salts, which are stored in plain text along with the hash.
2630:
2550:
98:
To learn a password from a hash is to find a string which, when input into the hash function, creates that same hash. This is the same as
1938:
1967:
1128:
program was later developed that can generate and use rainbow tables for a variety of character sets and hashing algorithms, including
157:
Given a password hash function H and a finite set of passwords P, the goal is to precompute a data structure that, given any output
1876:
1259:| ≃ 3×10) would be easily tractable with a personal computer while the 16-character lowercase alphanumeric passwords case (|
1060:
doesn't appear in the table), one computes a chain with the two last reductions (these two reductions are represented at step 2)
3005:
2566:
1838:
1756:
1611:
1472:
1083:
At this point (step 4), one generates a chain and compares at each iteration the hash with the target hash. We find the hash
1813:
3010:
1072:
appears at the end of the chain and in the table), the password is retrieved at the beginning of the chain that produces
2327:
988:
with ordinary hash chains by replacing the single reduction function R with a sequence of related reduction functions R
2494:
2623:
1773:"How to prevent Windows from storing a LAN manager hash of your password in Active Directory and local SAM databases"
1740:
1454:
1660:
1110:
tables can crack only MD5 hashes. The theory of this technique was invented by
Philippe Oechslin as a fast form of
1931:
1417:
424:
The only requirement for the reduction function is to be able to return a "plain text" value in a specific size.
2995:
2826:
2535:
2020:
1972:
17:
2322:
1729:
2616:
2540:
1006:(they may overlap briefly) but they will not merge, drastically reducing the overall number of collisions.
2942:
2897:
2710:
2309:
1951:
1947:
1205:
42:
1573:
1013:
different chains. The first chain assumes the hash value is in the last hash position and just applies R
67:
Rainbow tables were invented by
Philippe Oechslin as an application of an earlier, simpler algorithm by
3000:
2821:
1924:
1717:
1321:
129:
2937:
2205:
1822:
2010:
1680:
1512:
2927:
2917:
2772:
2545:
2381:
2080:
2075:
2922:
2912:
2715:
2675:
2668:
2658:
2653:
2468:
2288:
1111:
57:
46:
2663:
2576:
1962:
1675:
1507:
1389:
have become more practical. However, rainbow tables are available for eight and nine character
1275:. For example, consider a password hash that is generated using the following function (where "
2970:
2816:
2762:
2591:
2241:
2195:
2085:
2043:
2028:
1443:
1019:; the next chain assumes the hash value is in the second-to-last hash position and applies R
758:
merges with a chain having a different starting point. For example, the chain of hash value
2932:
2856:
2261:
2165:
2115:
2090:
1309:
1166:
969:
551:{\displaystyle {\mathtt {920ECF10}}\,{\xrightarrow{}}\,{\color {Violet}{\mathtt {kiebgt}}}}
202:
1635:
1492:
8:
2695:
2586:
2463:
2412:
2351:
2251:
2170:
2130:
2110:
1272:
106:
50:
1812:
Oechslin, Philippe (2003-08-17). "Making a Faster
Cryptanalytic Time-Memory Trade-Off".
1036:
through each table. Rainbow tables can achieve similar performance with tables that are
2801:
2785:
2732:
2520:
2504:
2453:
2038:
1844:
1533:
1407:
1305:
110:
88:
61:
2861:
2851:
2722:
2397:
1899:
1834:
1752:
1689:
1607:
1525:
1468:
1386:
1118:
1115:
1848:
1631:
209:
of the hash function. By alternating the hash function with the reduction function,
2796:
2484:
2438:
2200:
1826:
1744:
1685:
1661:"A simple scheme to make passwords based on one-way functions much harder to crack"
1517:
1458:
99:
1537:
2499:
2448:
2443:
2231:
1946:
1889:
1852:
1830:
1725:
1463:
957:
with no good matches, then the password was never produced in any of the chains.
998:. In this way, for two chains to collide and merge they must hit the same value
2871:
2791:
2752:
2700:
2685:
2489:
2217:
1721:
1552:"LASEC - Security and Cryptography Laboratory: Dr Philippe Oechslin - Research"
1328:
985:
964:
Simple hash chains have several flaws. Most serious if at any point two chains
454:
to invert (find the corresponding password for), compute a chain starting with
186:
80:
68:
117:
tables. Rainbow tables are a special kind of such table that overcome certain
2989:
2952:
2907:
2866:
2846:
2742:
2705:
2680:
2581:
1884:
1529:
1521:
1280:
1106:
Rainbow tables are specific to the hash function they were created for e.g.,
565:" is one of the endpoints in our table, the corresponding starting password "
2160:
439:
the first and last password in each chain. The first password is called the
2902:
2747:
2737:
2727:
2690:
2639:
1627:
1369:
use hashes with salts, though many applications use just a hash (typically
1125:
38:
463:, and if so, the immediately preceding value in the chain is the password
2881:
2571:
2417:
2346:
2342:
1772:
1693:
1643:
Proceedings of the FREENIX Track: 1999 USENIX Annual
Technical Conference
1551:
1271:
A rainbow table is ineffective against one-way hashes that include large
35:
1096:
2841:
2811:
2806:
2767:
1748:
1656:
1412:
151:
1160:
needed to find a password matching a given hash are directly related:
886:
851:
810:
703:
662:
624:
518:
381:
343:
302:
264:
2831:
2246:
2125:
1776:
1301:
877:
842:
801:
694:
653:
615:
509:
372:
334:
293:
255:
84:
2033:
1790:
2876:
2836:
2525:
2422:
2407:
2402:
2392:
2356:
2276:
2190:
2070:
1152:
that had been needed to compute the table, the length of the table
1121:
941:
because this value is not contained in the chain. This is called a
206:
2361:
2317:
2095:
1374:
1346:
1129:
60:: they use less computer processing time and more storage than a
1080:
at the beginning of the corresponding chain stored in the table.
2757:
2530:
2271:
2266:
2236:
2226:
2185:
2180:
2175:
2155:
2150:
2120:
2105:
2065:
1903:
1588:
1556:
Faculté I&C - School of
Computer and Communication Sciences
1327:
Another technique that helps prevent precomputation attacks is
1373:) with no salt. The Microsoft Windows NT/2000 family uses the
2256:
2145:
2100:
2048:
2005:
2000:
1994:
1362:
1313:
1255:
Thus the 8-character lowercase alphanumeric passwords case (|
1137:
929:
The chain generated by the corresponding starting password "
2371:
2366:
2337:
2332:
2296:
1402:
1390:
1378:
1358:
1091:) one step earlier in the chain: the attack is successful.
743:" (or a different password that has the same hash value).
2140:
2135:
1988:
1382:
1370:
1366:
1317:
1133:
1107:
1716:
193:) bits of space, where |P| is the size of the set P and
949:
is extended looking for another match. If the chain of
150:
For hash chains other than what is mentioned here, see
2778:
Cryptographically secure pseudorandom number generator
1601:
945:. In this case, the match is ignored and the chain of
1821:. Lecture Notes in Computer Science. Vol. 2729.
1444:"Making a Faster Cryptanalytic Time-Memory Trade-Off"
1208:
1169:
775:
582:
483:
222:
1908:
1040:times larger, allowing them to perform a factor of
161:of the hash function, can either locate an element
133:
Rainbow Table illustration presented at Crypto 2003
1574:"Password Protection for Modern Operating Systems"
1295:saltedhash(password) = hash(hash(password) + salt)
1244:
1191:
918:
728:
550:
413:
1266:
1087:in the chain, and the password that produced it (
937:is reached. The search will end without reaching
474:, its chain can be computed by first applying R:
427:To generate the table, we choose a random set of
2987:
984:Rainbow tables effectively solve the problem of
177:in P. The simplest way to do this is compute H(
1626:
754:; it may so happen that the chain starting at
2624:
1932:
1486:
1484:
1287:saltedhash(password) = hash(password + salt)
431:from P, compute chains of some fixed length
114:
56:Rainbow tables are a practical example of a
1567:
1565:
1357:Nearly all distributions and variations of
2631:
2617:
1939:
1925:
1710:
1481:
1437:
1435:
1433:
883:
879:
848:
844:
807:
803:
700:
696:
659:
655:
621:
617:
515:
511:
378:
374:
340:
336:
299:
295:
261:
257:
185:in P, but then storing the table requires
145:
1730:"Secure applications of low-entropy keys"
1679:
1571:
1511:
1462:
1263:| ≃ 10) would be completely intractable.
889:
871:
854:
836:
813:
795:
706:
688:
665:
647:
627:
609:
521:
503:
384:
366:
346:
328:
305:
287:
267:
249:
1893:) is being considered for deletion. See
1811:
1645:. Monterey, CA, USA: USENIX Association.
1602:Ferguson, Neils; Bruce Schneier (2003).
1562:
1441:
128:
1791:"A Case for Modern Rainbow Table Usage"
1606:. Indianapolis: John Wiley & Sons.
1500:IEEE Transactions on Information Theory
1493:"A cryptanalytic time-memory trade-off"
1490:
1430:
14:
2988:
1797:. Positron Security. 26 February 2021.
1655:
1345:Specific intensive efforts focused on
746:Note however that this chain does not
2612:
1920:
1620:
909:
906:
903:
900:
897:
894:
891:
866:
863:
860:
857:
831:
828:
825:
822:
819:
816:
790:
787:
784:
781:
778:
721:
718:
715:
712:
709:
683:
680:
677:
674:
671:
668:
642:
639:
636:
633:
630:
602:
599:
596:
593:
590:
587:
584:
541:
538:
535:
532:
529:
526:
523:
498:
495:
492:
489:
486:
404:
401:
398:
395:
392:
389:
386:
361:
358:
355:
352:
349:
323:
320:
317:
314:
311:
308:
282:
279:
276:
273:
270:
242:
239:
236:
233:
230:
227:
224:
173:, or determine that there is no such
1815:Advances in Cryptology - CRYPTO 2003
1636:"A Future-Adaptable Password Scheme"
1457:. Vol. 2729. pp. 617–630.
1451:Advances in Cryptology - CRYPTO 2003
95:system would hash it a second time.
1879:The original rainbow table research
1825:, USA: Springer. pp. 617–630.
1245:{\displaystyle t={\frac {|P|}{2L}}}
569:" allows to follow its chain until
118:
24:
1877:Ophcrack page by Philippe Oechslin
1068:If this test is positive (step 3,
25:
3022:
1897:to help reach a consensus. ›
1870:
979:
83:, passwords are stored either as
2966:
2965:
2638:
1334:An alternative approach, called
1095:
1783:
1743:. Vol. 1396. p. 121.
1572:Alexander, Steven (June 2004).
443:and the last one is called the
2827:Information-theoretic security
2536:NIST hash function competition
1765:
1649:
1595:
1544:
1352:
1267:Defense against rainbow tables
1227:
1219:
1185:
1177:
1114:, which he implemented in the
13:
1:
1882:
1805:
74:
41:for caching the outputs of a
3006:Cryptographic hash functions
2541:Password Hashing Competition
1952:message authentication codes
1948:Cryptographic hash functions
1831:10.1007/978-3-540-45146-4_36
1690:10.1016/0167-4048(96)00003-X
1464:10.1007/978-3-540-45146-4_36
1418:Pollard's kangaroo algorithm
470:For example, given the hash
124:
7:
2943:Message authentication code
2898:Cryptographic hash function
2711:Cryptographic hash function
2495:Merkle–Damgård construction
1396:
43:cryptographic hash function
10:
3027:
3011:Hash-based data structures
2822:Harvest now, decrypt later
1047:
149:
2961:
2938:Post-quantum cryptography
2890:
2646:
2608:
2559:
2513:
2477:
2431:
2380:
2308:
2285:
2214:
2058:
2019:
1981:
1958:
1916:
1912:
1823:Santa Barbara, California
1381:hashing method (based on
933:" is then followed until
27:Password cracking dataset
2928:Quantum key distribution
2918:Authenticated encryption
2773:Random number generation
2289:key derivation functions
1895:templates for discussion
1668:Computers & Security
1522:10.1109/TIT.1980.1056220
1423:
953:gets extended to length
450:Now, given a hash value
435:for each one, and store
2923:Public-key cryptography
2913:Symmetric-key algorithm
2716:Key derivation function
2676:Cryptographic primitive
2669:Authentication protocol
2659:Outline of cryptography
2654:History of cryptography
2567:Hash-based cryptography
2469:Length extension attack
750:contain the hash value
739:Thus, the password is "
146:Precomputed hash chains
47:key derivation function
2664:Cryptographic protocol
2577:Message authentication
1604:Practical Cryptography
1246:
1193:
920:
887:
852:
811:
730:
704:
663:
625:
552:
519:
415:
382:
344:
303:
265:
134:
119:technical difficulties
115:precomputed hash chain
2996:Cryptographic attacks
2817:End-to-end encryption
2763:Cryptojacking malware
1795:rainbowcrackalack.com
1442:Oechslin, P. (2003).
1247:
1194:
1192:{\displaystyle T=|P|}
1156:and the average time
1000:on the same iteration
921:
873:
838:
797:
731:
690:
649:
611:
553:
505:
416:
368:
330:
289:
251:
132:
2933:Quantum cryptography
2857:Trusted timestamping
1779:. 24 September 2021.
1737:Information Security
1491:Hellman, M. (1980).
1206:
1167:
1124:. The more powerful
1112:time/memory tradeoff
773:
580:
481:
220:
2696:Cryptographic nonce
2464:Side-channel attack
1387:brute force attacks
1056:If the test fails (
970:collision resistant
885:
850:
809:
702:
661:
623:
517:
380:
342:
301:
263:
107:brute-force attacks
102:the hash function.
58:space–time tradeoff
2802:Subliminal channel
2786:Pseudorandom noise
2733:Key (cryptography)
2521:CAESAR Competition
2505:HAIFA construction
2454:Brute-force attack
1749:10.1007/BFb0030415
1408:Brute-force attack
1242:
1189:
916:
914:
726:
607:
548:
546:
411:
409:
247:
199:reduction function
135:
111:dictionary attacks
62:brute-force attack
3001:Search algorithms
2983:
2982:
2979:
2978:
2862:Key-based routing
2852:Trapdoor function
2723:Digital signature
2604:
2603:
2600:
2599:
2398:ChaCha20-Poly1305
2215:Password hashing/
1840:978-3-540-40674-7
1758:978-3-540-64382-1
1613:978-0-471-22357-3
1474:978-3-540-40674-7
1336:key strengthening
1240:
429:initial passwords
165:in P such that H(
16:(Redirected from
3018:
2969:
2968:
2797:Insecure channel
2633:
2626:
2619:
2610:
2609:
2485:Avalanche effect
2439:Collision attack
1982:Common functions
1941:
1934:
1927:
1918:
1917:
1914:
1913:
1910:
1909:
1866:
1864:
1863:
1857:
1851:. Archived from
1820:
1799:
1798:
1787:
1781:
1780:
1769:
1763:
1762:
1734:
1714:
1708:
1707:
1705:
1704:
1698:
1692:. Archived from
1683:
1665:
1653:
1647:
1646:
1640:
1634:(June 6, 1999).
1624:
1618:
1617:
1599:
1593:
1592:
1578:
1569:
1560:
1559:
1548:
1542:
1541:
1515:
1497:
1488:
1479:
1478:
1466:
1448:
1439:
1312:methods—used in
1296:
1288:
1278:
1251:
1249:
1248:
1243:
1241:
1239:
1231:
1230:
1222:
1216:
1198:
1196:
1195:
1190:
1188:
1180:
1119:password cracker
1099:
1026:, then H, then R
940:
936:
932:
925:
923:
922:
917:
915:
913:
912:
888:
884:
870:
869:
853:
849:
835:
834:
812:
808:
794:
793:
765:
762:, also leads to
761:
742:
735:
733:
732:
727:
725:
724:
705:
701:
687:
686:
664:
660:
646:
645:
626:
622:
608:
606:
605:
572:
568:
564:
557:
555:
554:
549:
547:
545:
544:
520:
516:
502:
501:
473:
420:
418:
417:
412:
410:
408:
407:
383:
379:
365:
364:
345:
341:
327:
326:
304:
300:
286:
285:
266:
262:
248:
246:
245:
21:
3026:
3025:
3021:
3020:
3019:
3017:
3016:
3015:
2986:
2985:
2984:
2975:
2957:
2886:
2642:
2637:
2596:
2555:
2514:Standardization
2509:
2500:Sponge function
2473:
2449:Birthday attack
2444:Preimage attack
2427:
2383:
2376:
2304:
2287:
2286:General purpose
2281:
2216:
2210:
2059:Other functions
2054:
2021:SHA-3 finalists
2015:
1977:
1954:
1945:
1898:
1873:
1861:
1859:
1855:
1841:
1818:
1808:
1803:
1802:
1789:
1788:
1784:
1771:
1770:
1766:
1759:
1732:
1715:
1711:
1702:
1700:
1696:
1681:10.1.1.102.2597
1663:
1654:
1650:
1638:
1632:Mazières, David
1625:
1621:
1614:
1600:
1596:
1576:
1570:
1563:
1550:
1549:
1545:
1513:10.1.1.120.2463
1495:
1489:
1482:
1475:
1446:
1440:
1431:
1426:
1399:
1355:
1294:
1286:
1276:
1269:
1232:
1226:
1218:
1217:
1215:
1207:
1204:
1203:
1184:
1176:
1168:
1165:
1164:
1076:. Here we find
1050:
1044:fewer lookups.
1031:
1025:
1018:
997:
991:
982:
938:
934:
930:
893:
892:
890:
878:
872:
856:
855:
843:
837:
815:
814:
802:
796:
777:
776:
774:
771:
770:
763:
759:
740:
708:
707:
695:
689:
667:
666:
654:
648:
629:
628:
616:
610:
586:
585:
583:
581:
578:
577:
570:
566:
562:
525:
524:
522:
510:
504:
485:
484:
482:
479:
478:
471:
388:
387:
385:
373:
367:
348:
347:
335:
329:
307:
306:
294:
288:
269:
268:
256:
250:
226:
225:
223:
221:
218:
217:
155:
148:
127:
77:
28:
23:
22:
15:
12:
11:
5:
3024:
3014:
3013:
3008:
3003:
2998:
2981:
2980:
2977:
2976:
2974:
2973:
2962:
2959:
2958:
2956:
2955:
2950:
2948:Random numbers
2945:
2940:
2935:
2930:
2925:
2920:
2915:
2910:
2905:
2900:
2894:
2892:
2888:
2887:
2885:
2884:
2879:
2874:
2872:Garlic routing
2869:
2864:
2859:
2854:
2849:
2844:
2839:
2834:
2829:
2824:
2819:
2814:
2809:
2804:
2799:
2794:
2792:Secure channel
2789:
2783:
2782:
2781:
2770:
2765:
2760:
2755:
2753:Key stretching
2750:
2745:
2740:
2735:
2730:
2725:
2720:
2719:
2718:
2713:
2703:
2701:Cryptovirology
2698:
2693:
2688:
2686:Cryptocurrency
2683:
2678:
2673:
2672:
2671:
2661:
2656:
2650:
2648:
2644:
2643:
2636:
2635:
2628:
2621:
2613:
2606:
2605:
2602:
2601:
2598:
2597:
2595:
2594:
2589:
2584:
2579:
2574:
2569:
2563:
2561:
2557:
2556:
2554:
2553:
2548:
2543:
2538:
2533:
2528:
2523:
2517:
2515:
2511:
2510:
2508:
2507:
2502:
2497:
2492:
2490:Hash collision
2487:
2481:
2479:
2475:
2474:
2472:
2471:
2466:
2461:
2456:
2451:
2446:
2441:
2435:
2433:
2429:
2428:
2426:
2425:
2420:
2415:
2410:
2405:
2400:
2395:
2389:
2387:
2378:
2377:
2375:
2374:
2369:
2364:
2359:
2354:
2349:
2340:
2335:
2330:
2325:
2320:
2314:
2312:
2306:
2305:
2303:
2302:
2299:
2293:
2291:
2283:
2282:
2280:
2279:
2274:
2269:
2264:
2259:
2254:
2249:
2244:
2239:
2234:
2229:
2223:
2221:
2218:key stretching
2212:
2211:
2209:
2208:
2203:
2198:
2193:
2188:
2183:
2178:
2173:
2168:
2163:
2158:
2153:
2148:
2143:
2138:
2133:
2128:
2123:
2118:
2113:
2108:
2103:
2098:
2093:
2088:
2083:
2078:
2073:
2068:
2062:
2060:
2056:
2055:
2053:
2052:
2046:
2041:
2036:
2031:
2025:
2023:
2017:
2016:
2014:
2013:
2008:
2003:
1998:
1992:
1985:
1983:
1979:
1978:
1976:
1975:
1970:
1965:
1959:
1956:
1955:
1944:
1943:
1936:
1929:
1921:
1907:
1906:
1880:
1872:
1871:External links
1869:
1868:
1867:
1839:
1807:
1804:
1801:
1800:
1782:
1764:
1757:
1709:
1674:(2): 171–176.
1648:
1619:
1612:
1594:
1561:
1543:
1506:(4): 401–406.
1480:
1473:
1428:
1427:
1425:
1422:
1421:
1420:
1415:
1410:
1405:
1398:
1395:
1379:NT LAN Manager
1354:
1351:
1329:key stretching
1302:Unix passwords
1268:
1265:
1253:
1252:
1238:
1235:
1229:
1225:
1221:
1214:
1211:
1200:
1199:
1187:
1183:
1179:
1175:
1172:
1093:
1092:
1081:
1066:
1065:
1064:
1054:
1049:
1046:
1027:
1020:
1014:
1004:collision-free
993:
989:
981:
980:Rainbow tables
978:
927:
926:
911:
908:
905:
902:
899:
896:
882:
876:
868:
865:
862:
859:
847:
841:
833:
830:
827:
824:
821:
818:
806:
800:
792:
789:
786:
783:
780:
737:
736:
723:
720:
717:
714:
711:
699:
693:
685:
682:
679:
676:
673:
670:
658:
652:
644:
641:
638:
635:
632:
620:
614:
604:
601:
598:
595:
592:
589:
559:
558:
543:
540:
537:
534:
531:
528:
514:
508:
500:
497:
494:
491:
488:
467:that we seek.
441:starting point
422:
421:
406:
403:
400:
397:
394:
391:
377:
371:
363:
360:
357:
354:
351:
339:
333:
325:
322:
319:
316:
313:
310:
298:
292:
284:
281:
278:
275:
272:
260:
254:
244:
241:
238:
235:
232:
229:
147:
144:
139:rainbow tables
126:
123:
81:authentication
76:
73:
69:Martin Hellman
26:
18:Rainbow tables
9:
6:
4:
3:
2:
3023:
3012:
3009:
3007:
3004:
3002:
2999:
2997:
2994:
2993:
2991:
2972:
2964:
2963:
2960:
2954:
2953:Steganography
2951:
2949:
2946:
2944:
2941:
2939:
2936:
2934:
2931:
2929:
2926:
2924:
2921:
2919:
2916:
2914:
2911:
2909:
2908:Stream cipher
2906:
2904:
2901:
2899:
2896:
2895:
2893:
2889:
2883:
2880:
2878:
2875:
2873:
2870:
2868:
2867:Onion routing
2865:
2863:
2860:
2858:
2855:
2853:
2850:
2848:
2847:Shared secret
2845:
2843:
2840:
2838:
2835:
2833:
2830:
2828:
2825:
2823:
2820:
2818:
2815:
2813:
2810:
2808:
2805:
2803:
2800:
2798:
2795:
2793:
2790:
2787:
2784:
2779:
2776:
2775:
2774:
2771:
2769:
2766:
2764:
2761:
2759:
2756:
2754:
2751:
2749:
2746:
2744:
2743:Key generator
2741:
2739:
2736:
2734:
2731:
2729:
2726:
2724:
2721:
2717:
2714:
2712:
2709:
2708:
2707:
2706:Hash function
2704:
2702:
2699:
2697:
2694:
2692:
2689:
2687:
2684:
2682:
2681:Cryptanalysis
2679:
2677:
2674:
2670:
2667:
2666:
2665:
2662:
2660:
2657:
2655:
2652:
2651:
2649:
2645:
2641:
2634:
2629:
2627:
2622:
2620:
2615:
2614:
2611:
2607:
2593:
2590:
2588:
2585:
2583:
2582:Proof of work
2580:
2578:
2575:
2573:
2570:
2568:
2565:
2564:
2562:
2558:
2552:
2549:
2547:
2544:
2542:
2539:
2537:
2534:
2532:
2529:
2527:
2524:
2522:
2519:
2518:
2516:
2512:
2506:
2503:
2501:
2498:
2496:
2493:
2491:
2488:
2486:
2483:
2482:
2480:
2476:
2470:
2467:
2465:
2462:
2460:
2459:Rainbow table
2457:
2455:
2452:
2450:
2447:
2445:
2442:
2440:
2437:
2436:
2434:
2430:
2424:
2421:
2419:
2416:
2414:
2411:
2409:
2406:
2404:
2401:
2399:
2396:
2394:
2391:
2390:
2388:
2385:
2382:Authenticated
2379:
2373:
2370:
2368:
2365:
2363:
2360:
2358:
2355:
2353:
2350:
2348:
2344:
2341:
2339:
2336:
2334:
2331:
2329:
2326:
2324:
2321:
2319:
2316:
2315:
2313:
2311:
2310:MAC functions
2307:
2300:
2298:
2295:
2294:
2292:
2290:
2284:
2278:
2275:
2273:
2270:
2268:
2265:
2263:
2260:
2258:
2255:
2253:
2250:
2248:
2245:
2243:
2240:
2238:
2235:
2233:
2230:
2228:
2225:
2224:
2222:
2219:
2213:
2207:
2204:
2202:
2199:
2197:
2194:
2192:
2189:
2187:
2184:
2182:
2179:
2177:
2174:
2172:
2169:
2167:
2164:
2162:
2159:
2157:
2154:
2152:
2149:
2147:
2144:
2142:
2139:
2137:
2134:
2132:
2129:
2127:
2124:
2122:
2119:
2117:
2114:
2112:
2109:
2107:
2104:
2102:
2099:
2097:
2094:
2092:
2089:
2087:
2084:
2082:
2079:
2077:
2074:
2072:
2069:
2067:
2064:
2063:
2061:
2057:
2050:
2047:
2045:
2042:
2040:
2037:
2035:
2032:
2030:
2027:
2026:
2024:
2022:
2018:
2012:
2009:
2007:
2004:
2002:
1999:
1997:(compromised)
1996:
1993:
1991:(compromised)
1990:
1987:
1986:
1984:
1980:
1974:
1973:Known attacks
1971:
1969:
1966:
1964:
1961:
1960:
1957:
1953:
1949:
1942:
1937:
1935:
1930:
1928:
1923:
1922:
1919:
1915:
1911:
1905:
1901:
1896:
1892:
1891:
1886:
1881:
1878:
1875:
1874:
1858:on 2020-09-26
1854:
1850:
1846:
1842:
1836:
1832:
1828:
1824:
1817:
1816:
1810:
1809:
1796:
1792:
1786:
1778:
1774:
1768:
1760:
1754:
1750:
1746:
1742:
1738:
1731:
1727:
1723:
1719:
1713:
1699:on 2016-05-06
1695:
1691:
1687:
1682:
1677:
1673:
1669:
1662:
1658:
1652:
1644:
1637:
1633:
1629:
1628:Provos, Niels
1623:
1615:
1609:
1605:
1598:
1590:
1586:
1582:
1575:
1568:
1566:
1558:. March 2004.
1557:
1553:
1547:
1539:
1535:
1531:
1527:
1523:
1519:
1514:
1509:
1505:
1501:
1494:
1487:
1485:
1476:
1470:
1465:
1460:
1456:
1452:
1445:
1438:
1436:
1434:
1429:
1419:
1416:
1414:
1411:
1409:
1406:
1404:
1401:
1400:
1394:
1392:
1388:
1384:
1380:
1376:
1372:
1368:
1364:
1360:
1350:
1348:
1343:
1339:
1337:
1332:
1330:
1325:
1323:
1319:
1315:
1311:
1307:
1303:
1297:
1292:
1289:
1284:
1282:
1281:concatenation
1274:
1264:
1262:
1258:
1236:
1233:
1223:
1212:
1209:
1202:
1201:
1181:
1173:
1170:
1163:
1162:
1161:
1159:
1155:
1151:
1147:
1141:
1139:
1135:
1131:
1127:
1123:
1120:
1117:
1113:
1109:
1104:
1100:
1098:
1090:
1086:
1082:
1079:
1075:
1071:
1067:
1062:
1061:
1059:
1055:
1052:
1051:
1045:
1043:
1039:
1033:
1030:
1023:
1017:
1012:
1007:
1005:
1001:
996:
987:
977:
973:
971:
967:
962:
958:
956:
952:
948:
944:
880:
874:
845:
839:
804:
798:
769:
768:
767:
757:
753:
749:
744:
697:
691:
656:
650:
618:
612:
576:
575:
574:
512:
506:
477:
476:
475:
468:
466:
462:
457:
453:
448:
446:
442:
438:
434:
430:
425:
375:
369:
337:
331:
296:
290:
258:
252:
216:
215:
214:
212:
208:
204:
200:
196:
192:
188:
184:
180:
176:
172:
168:
164:
160:
153:
143:
140:
131:
122:
120:
116:
112:
108:
103:
101:
96:
92:
90:
86:
82:
72:
70:
65:
63:
59:
54:
52:
49:that adds a "
48:
44:
40:
37:
33:
32:rainbow table
19:
2903:Block cipher
2748:Key schedule
2738:Key exchange
2728:Kleptography
2691:Cryptosystem
2640:Cryptography
2458:
1900:Cryptography
1888:
1860:. Retrieved
1853:the original
1814:
1794:
1785:
1767:
1736:
1724:; Hall, C.;
1722:Schneier, B.
1712:
1701:. Retrieved
1694:the original
1671:
1667:
1651:
1642:
1622:
1603:
1597:
1591:Association.
1584:
1580:
1555:
1546:
1503:
1499:
1450:
1356:
1344:
1340:
1335:
1333:
1326:
1320:Unixes, and
1298:
1293:
1290:
1285:
1270:
1260:
1256:
1254:
1157:
1153:
1149:
1148:|, the time
1145:
1142:
1126:RainbowCrack
1105:
1101:
1094:
1088:
1084:
1077:
1073:
1069:
1057:
1041:
1037:
1034:
1028:
1021:
1015:
1010:
1008:
1003:
999:
994:
983:
974:
965:
963:
959:
954:
950:
946:
942:
928:
755:
751:
747:
745:
738:
573:is reached:
560:
469:
464:
460:
455:
451:
449:
444:
440:
436:
432:
428:
426:
423:
210:
198:
194:
190:
182:
178:
174:
170:
166:
162:
158:
156:
138:
136:
104:
97:
93:
78:
66:
55:
31:
29:
2891:Mathematics
2882:Mix network
2572:Merkle tree
2560:Utilization
2546:NSA Suite B
1883:‹ The
1393:passwords.
1375:LAN Manager
1353:Common uses
1283:operator):
943:false alarm
36:precomputed
2990:Categories
2842:Ciphertext
2812:Decryption
2807:Encryption
2768:Ransomware
2384:encryption
2161:RadioGatún
1968:Comparison
1862:2019-03-13
1806:References
1726:Wagner, D.
1718:Kelsey, J.
1703:2015-08-28
1657:Manber, U.
1413:DistrRTgen
1306:SHA2-crypt
986:collisions
181:) for all
152:hash chain
75:Background
2832:Plaintext
2301:KDF1/KDF2
2220:functions
2206:Whirlpool
1777:Microsoft
1676:CiteSeerX
1530:0018-9448
1508:CiteSeerX
1279:" is the
992:through R
137:The term
125:Etymology
100:inverting
85:plaintext
79:For user
2971:Category
2877:Kademlia
2837:Codetext
2780:(CSPRNG)
2526:CRYPTREC
2357:Poly1305
2277:yescrypt
2191:Streebog
2071:CubeHash
2051:(winner)
1885:template
1849:16086595
1728:(1998).
1659:(1996).
1397:See also
1122:Ophcrack
939:FB107E70
935:FB107E70
875:→
840:→
799:→
760:FB107E70
692:→
651:→
613:→
571:920ECF10
507:→
472:920ECF10
445:endpoint
370:→
332:→
291:→
253:→
207:codomain
2647:General
2432:Attacks
2362:SipHash
2318:CBC-MAC
2252:LM hash
2232:Balloon
2096:HAS-160
1887:below (
1347:LM hash
1322:Solaris
1130:LM hash
1116:Windows
1089:culture
1074:linux23
1070:linux23
1048:Example
966:collide
561:Since "
105:Though
2758:Keygen
2592:Pepper
2531:NESSIE
2478:Design
2272:scrypt
2267:PBKDF2
2242:Catena
2237:bcrypt
2227:Argon2
2186:Snefru
2181:Shabal
2176:SWIFFT
2156:RIPEMD
2151:N-hash
2126:MASH-2
2121:MASH-1
2106:Kupyna
2066:BLAKE3
2049:Keccak
2034:Grøstl
2011:BLAKE2
1904:Curlie
1890:Curlie
1847:
1837:
1755:
1678:
1610:
1589:USENIX
1538:552536
1536:
1528:
1510:
1471:
1365:, and
1310:bcrypt
1136:, and
1085:re3xes
1078:passwd
931:aaaaaa
764:kiebgt
748:always
741:sgfnyd
567:aaaaaa
563:kiebgt
211:chains
203:domain
109:(e.g.
89:hashes
2788:(PRN)
2386:modes
2262:Makwa
2257:Lyra2
2247:crypt
2196:Tiger
2146:MDC-2
2101:HAVAL
2086:Fugue
2044:Skein
2029:BLAKE
2006:SHA-3
2001:SHA-2
1995:SHA-1
1856:(PDF)
1845:S2CID
1819:(PDF)
1733:(PDF)
1697:(PDF)
1664:(PDF)
1639:(PDF)
1587:(3).
1581:Login
1577:(PDF)
1534:S2CID
1496:(PDF)
1447:(PDF)
1424:Notes
1363:Linux
1314:Linux
1273:salts
1138:SHA-1
1058:rambo
867:80890
39:table
34:is a
2587:Salt
2551:CNSA
2418:IAPM
2372:VMAC
2367:UMAC
2352:PMAC
2347:CMAC
2343:OMAC
2338:NMAC
2333:HMAC
2328:GMAC
2297:HKDF
2166:SIMD
2116:Lane
2091:GOST
2076:ECOH
1963:List
1950:and
1835:ISBN
1753:ISBN
1741:LNCS
1608:ISBN
1526:ISSN
1469:ISBN
1455:LNCS
1403:A5/1
1391:NTLM
1377:and
1359:Unix
1308:and
437:only
205:and
189:(|P|
169:) =
51:salt
2423:OCB
2413:GCM
2408:EAX
2403:CWC
2393:CCM
2323:DAA
2201:VSH
2171:SM3
2141:MD6
2136:MD4
2131:MD2
2111:LSH
2081:FSB
1989:MD5
1902:at
1827:doi
1745:doi
1686:doi
1518:doi
1459:doi
1383:MD4
1371:MD5
1367:BSD
1318:BSD
1291:Or
1134:MD5
1108:MD5
785:107
710:920
631:281
487:920
350:920
271:281
121:.
87:or
2992::
2039:JH
1843:.
1833:.
1793:.
1775:.
1751:.
1739:.
1735:.
1720:;
1684:.
1672:15
1670:.
1666:.
1641:.
1630:;
1585:29
1583:.
1579:.
1564:^
1554:.
1532:.
1524:.
1516:.
1504:26
1502:.
1498:.
1483:^
1467:.
1453:.
1449:.
1432:^
1361:,
1316:,
1140:.
1132:,
1024:−1
972:.
791:70
766::
722:10
643:40
499:10
362:10
283:40
71:.
30:A
2632:e
2625:t
2618:v
2345:/
1940:e
1933:t
1926:v
1865:.
1829::
1761:.
1747::
1706:.
1688::
1616:.
1540:.
1520::
1477:.
1461::
1277:+
1261:P
1257:P
1237:L
1234:2
1228:|
1224:P
1220:|
1213:=
1210:t
1186:|
1182:P
1178:|
1174:=
1171:T
1158:t
1154:L
1150:T
1146:P
1144:|
1042:k
1038:k
1029:k
1022:k
1016:k
1011:k
995:k
990:1
955:k
951:h
947:h
910:t
907:g
904:b
901:e
898:i
895:k
881:R
864:E
861:E
858:0
846:H
832:l
829:l
826:d
823:t
820:v
817:b
805:R
788:E
782:B
779:F
756:h
752:h
719:F
716:C
713:E
698:H
684:d
681:y
678:n
675:f
672:g
669:s
657:R
640:F
637:A
634:D
619:H
603:a
600:a
597:a
594:a
591:a
588:a
542:t
539:g
536:b
533:e
530:i
527:k
513:R
496:F
493:C
490:E
465:p
461:h
456:h
452:h
433:k
405:t
402:g
399:b
396:e
393:i
390:k
376:R
359:F
356:C
353:E
338:H
324:d
321:y
318:n
315:f
312:g
309:s
297:R
280:F
277:A
274:D
259:H
243:a
240:a
237:a
234:a
231:a
228:a
195:n
191:n
187:Θ
183:p
179:p
175:p
171:h
167:p
163:p
159:h
154:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
