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
1338:, deploys two salts, one public and one secret, but then (unlike in key stretching) securely deletes the secret salt. This forces both the attacker and legitimate users to perform a brute-force search for the secret salt value. The secret salt size is chosen so that the brute force search is imperceptible to the legitimate user. However, it makes the rainbow dictionary needed by the attacker much larger. 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.
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:
2965:
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).
2945:
2775:
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:
2613:
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
2533:
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
1921:
1950:
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.
3003:
1838:
1756:
1611:
1472:
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
3008:
2477:
1128:
program was later developed that can generate and use rainbow tables for a variety of character sets and hashing algorithms, including
2310:
2606:
1740:
1454:
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)
1914:
1417:
129:
2993:
2824:
2755:
2518:
2003:
1955:
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:
2305:
1072:
appears at the end of the chain and in the table), the password is retrieved at the beginning of the chain that produces
2599:
2523:
988:
with ordinary hash chains by replacing the single reduction function R with a sequence of related reduction functions R
2940:
2895:
2698:
2292:
1934:
1930:
42:
1773:"How to prevent Windows from storing a LAN manager hash of your password in Active Directory and local SAM databases"
1660:
2998:
2819:
1907:
1717:
1321:
1110:
tables can crack only MD5 hashes. The theory of this technique was invented by
Philippe Oechslin as a fast form of
2935:
2549:
2188:
1822:
424:
The only requirement for the reduction function is to be able to return a "plain text" value in a specific size.
2925:
2915:
2770:
2528:
2364:
2063:
2058:
1111:
57:
2920:
2910:
2703:
2663:
2656:
2641:
2636:
2451:
2271:
1729:
46:
1006:(they may overlap briefly) but they will not merge, drastically reducing the overall number of collisions.
2708:
2651:
2559:
1945:
1675:
1507:
1205:
2968:
2814:
2760:
2574:
2224:
2178:
2068:
2026:
2011:
1993:
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
2930:
2854:
2244:
2148:
2098:
2073:
969:
202:
1680:
1512:
2683:
2569:
2446:
2395:
2334:
2153:
2113:
2093:
1272:
106:
50:
2799:
2783:
2725:
2503:
2487:
2436:
2021:
1844:
1533:
1407:
110:
88:
61:
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 "
2859:
2849:
2715:
2380:
1834:
1752:
1631:
1607:
1525:
1468:
1386:
1118:
1115:
2794:
2646:
2467:
2421:
2183:
1826:
1744:
1685:
1517:
1458:
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
99:
1166:
551:{\displaystyle {\mathtt {920ECF10}}\,{\xrightarrow{}}\,{\color {Violet}{\mathtt {kiebgt}}}}
2482:
2431:
2426:
2214:
1725:
1635:
1492:
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
2869:
2789:
2745:
2688:
2673:
2472:
2200:
1721:
1328:
985:
186:
80:
68:
1096:
2987:
2950:
2905:
2864:
2844:
2735:
2693:
2668:
2564:
2143:
1882:
1689:
1280:
1848:
209:
of the hash function. By alternating the hash function with the reduction function,
2900:
2740:
2730:
2720:
2678:
2622:
1661:"A simple scheme to make passwords based on one-way functions much harder to crack"
1627:
1125:
38:
1537:
1852:
1830:
1463:
957:
with no good matches, then the password was never produced in any of the chains.
2879:
2554:
2400:
2329:
2325:
2234:
998:. In this way, for two chains to collide and merge they must hit the same value
35:
1552:"LASEC - Security and Cryptography Laboratory: Dr Philippe Oechslin - Research"
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
2839:
2809:
2804:
2765:
1656:
1412:
151:
117:
tables. Rainbow tables are a special kind of such table that overcome certain
1529:
1521:
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 "
17:
2829:
2229:
1776:
1309:
1305:
1301:
439:
the first and last password in each chain. The first password is called the
84:
2016:
1369:
use hashes with salts, though many applications use just a hash (typically
463:, and if so, the immediately preceding value in the chain is the password
2874:
2834:
2508:
2405:
2390:
2385:
2375:
2339:
2259:
2173:
2053:
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
1121:
206:
2344:
2300:
2078:
1748:
1374:
1346:
1129:
1160:
needed to find a password matching a given hash are directly related:
886:
851:
810:
703:
662:
624:
518:
381:
343:
302:
264:
2750:
2513:
2254:
2249:
2219:
2209:
2168:
2163:
2158:
2138:
2133:
2108:
2103:
2088:
2048:
1886:
1588:
877:
842:
801:
694:
653:
615:
509:
372:
334:
293:
255:
1790:
1152:
that had been needed to compute the table, the length of the table
941:
because this value is not contained in the chain. This is called a
2239:
2128:
2083:
2031:
1988:
1983:
1977:
1362:
1313:
1137:
128:
60:: they use less computer processing time and more storage than a
2354:
2349:
2320:
2315:
2279:
1402:
1390:
1378:
1358:
1080:
at the beginning of the corresponding chain stored in the table.
2595:
1903:
1556:
Faculté I&C - School of
Computer and Communication Sciences
1327:
Another technique that helps prevent precomputation attacks is
2123:
2118:
1971:
1382:
1373:) with no salt. The Microsoft Windows NT/2000 family uses the
1370:
1366:
1317:
1133:
1107:
1255:
Thus the 8-character lowercase alphanumeric passwords case (|
929:
The chain generated by the corresponding starting password "
1091:) one step earlier in the chain: the attack is successful.
743:" (or a different password that has the same hash value).
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
2776:
Cryptographically secure pseudorandom number generator
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:
1891:
2888:
2629:
2542:
2496:
2460:
2414:
2363:
2291:
2268:
2197:
2041:
2002:
1964:
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:
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
984:Rainbow tables effectively solve the problem of
177:in P. The simplest way to do this is compute H(
754:; it may so happen that the chain starting at
2607:
1915:
1486:
1484:
8:
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
2614:
2600:
2592:
1922:
1908:
1900:
1896:
1892:
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
1730:"Secure applications of low-entropy keys"
1679:
1511:
1462:
1263:| ≃ 10) would be completely intractable.
1226:
1218:
1215:
1207:
1184:
1176:
1168:
893:
892:
890:
889:
878:
872:
871:
856:
855:
854:
843:
837:
836:
815:
814:
813:
802:
796:
795:
777:
776:
774:
708:
707:
706:
695:
689:
688:
667:
666:
665:
654:
648:
647:
629:
628:
627:
616:
610:
609:
586:
585:
583:
581:
525:
524:
522:
521:
510:
504:
503:
485:
484:
482:
388:
387:
385:
384:
373:
367:
366:
348:
347:
346:
335:
329:
328:
307:
306:
305:
294:
288:
287:
269:
268:
267:
256:
250:
249:
226:
225:
223:
221:
1645:. Monterey, CA, USA: USENIX Association.
1602:Ferguson, Neils; Bruce Schneier (2003).
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"
1429:
1797:. Positron Security. 26 February 2021.
1345:Specific intensive efforts focused on
746:Note however that this chain does not
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
7:
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:
1877:Ophcrack page by Philippe Oechslin
1068:If this test is positive (step 3,
25:
83:, passwords are stored either as
2964:
2963:
1334:An alternative approach, called
1095:
1743:. Vol. 1396. p. 121.
1572:Alexander, Steven (June 2004).
443:and the last one is called the
2825:Information-theoretic security
2519:NIST hash function competition
1267:Defense against rainbow tables
1227:
1219:
1185:
1177:
1114:, which he implemented in the
1:
41:for caching the outputs of a
3004:Cryptographic hash functions
2524:Password Hashing Competition
1935:message authentication codes
1931: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
2941:Message authentication code
2896:Cryptographic hash function
2699:Cryptographic hash function
2478:Merkle–Damgård construction
43:cryptographic hash function
3025:
3009:Hash-based data structures
2820:Harvest now, decrypt later
149:
2959:
2936:Post-quantum cryptography
2591:
1941:
1899:
1895:
1823:Santa Barbara, California
1381:hashing method (based on
933:" is then followed until
27:Password cracking dataset
2926:Quantum key distribution
2916:Authenticated encryption
2771:Random number generation
2272:key derivation functions
1668:Computers & Security
1522:10.1109/TIT.1980.1056220
953:gets extended to length
450:Now, given a hash value
435:for each one, and store
2921:Public-key cryptography
2911:Symmetric-key algorithm
2704:Key derivation function
2664:Cryptographic primitive
2657:Authentication protocol
2642:Outline of cryptography
2637:History of cryptography
2550:Hash-based cryptography
2452:Length extension attack
750:contain the hash value
739:Thus, the password is "
146:Precomputed hash chains
47:key derivation function
2709:Secure Hash Algorithms
2652:Cryptographic protocol
2560: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
2994:Cryptographic attacks
2815:End-to-end encryption
2761: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:
2931:Quantum cryptography
2855: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:
2684:Cryptographic nonce
2447: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
2800:Subliminal channel
2784:Pseudorandom noise
2726:Key (cryptography)
2504:CAESAR Competition
2488:HAIFA construction
2437: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
2999:Search algorithms
2981:
2980:
2977:
2976:
2860:Key-based routing
2850:Trapdoor function
2716:Digital signature
2587:
2586:
2583:
2582:
2381:ChaCha20-Poly1305
2198: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
3016:
2967:
2966:
2795:Insecure channel
2647:Classical cipher
2616:
2609:
2602:
2593:
2468:Avalanche effect
2422:Collision attack
1965:Common functions
1924:
1917:
1910:
1901:
1897:
1893:
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:
3024:
3023:
3019:
3018:
3017:
3015:
3014:
3013:
2984:
2983:
2982:
2973:
2955:
2884:
2625:
2620:
2579:
2538:
2497:Standardization
2492:
2483:Sponge function
2456:
2432:Birthday attack
2427:Preimage attack
2410:
2366:
2359:
2287:
2270:
2269:General purpose
2264:
2199:
2193:
2042:Other functions
2037:
2004:SHA-3 finalists
1998:
1960:
1937:
1928:
1873:
1861:
1859:
1855:
1841:
1818:
1811:
1808:
1803:
1802:
1789:
1788:
1784:
1771:
1770:
1766:
1759:
1732:
1716:
1715:
1711:
1702:
1700:
1696:
1681:10.1.1.102.2597
1663:
1655:
1654:
1650:
1638:
1632:Mazières, David
1626:
1625:
1621:
1614:
1601:
1600:
1596:
1576:
1571:
1570:
1563:
1550:
1549:
1545:
1513:10.1.1.120.2463
1495:
1490:
1489:
1482:
1475:
1446:
1441:
1440:
1431:
1426:
1399:
1355:
1294:
1286:
1276:
1269:
1232:
1217:
1204:
1203:
1165:
1164:
1076:. Here we find
1050:
1044:fewer lookups.
1031:
1025:
1018:
997:
991:
982:
938:
934:
930:
771:
770:
763:
759:
740:
578:
577:
570:
566:
562:
479:
478:
471:
218:
217:
155:
148:
127:
77:
28:
23:
22:
15:
12:
11:
5:
3022:
3020:
3012:
3011:
3006:
3001:
2996:
2986:
2985:
2979:
2978:
2975:
2974:
2972:
2971:
2960:
2957:
2956:
2954:
2953:
2948:
2946:Random numbers
2943:
2938:
2933:
2928:
2923:
2918:
2913:
2908:
2903:
2898:
2892:
2890:
2886:
2885:
2883:
2882:
2877:
2872:
2870:Garlic routing
2867:
2862:
2857:
2852:
2847:
2842:
2837:
2832:
2827:
2822:
2817:
2812:
2807:
2802:
2797:
2792:
2790:Secure channel
2787:
2781:
2780:
2779:
2768:
2763:
2758:
2753:
2748:
2746:Key stretching
2743:
2738:
2733:
2728:
2723:
2718:
2713:
2712:
2711:
2706:
2701:
2691:
2689:Cryptovirology
2686:
2681:
2676:
2674:Cryptocurrency
2671:
2666:
2661:
2660:
2659:
2649:
2644:
2639:
2633:
2631:
2627:
2626:
2621:
2619:
2618:
2611:
2604:
2596:
2589:
2588:
2585:
2584:
2581:
2580:
2578:
2577:
2572:
2567:
2562:
2557:
2552:
2546:
2544:
2540:
2539:
2537:
2536:
2531:
2526:
2521:
2516:
2511:
2506:
2500:
2498:
2494:
2493:
2491:
2490:
2485:
2480:
2475:
2473:Hash collision
2470:
2464:
2462:
2458:
2457:
2455:
2454:
2449:
2444:
2439:
2434:
2429:
2424:
2418:
2416:
2412:
2411:
2409:
2408:
2403:
2398:
2393:
2388:
2383:
2378:
2372:
2370:
2361:
2360:
2358:
2357:
2352:
2347:
2342:
2337:
2332:
2323:
2318:
2313:
2308:
2303:
2297:
2295:
2289:
2288:
2286:
2285:
2282:
2276:
2274:
2266:
2265:
2263:
2262:
2257:
2252:
2247:
2242:
2237:
2232:
2227:
2222:
2217:
2212:
2206:
2204:
2201:key stretching
2195:
2194:
2192:
2191:
2186:
2181:
2176:
2171:
2166:
2161:
2156:
2151:
2146:
2141:
2136:
2131:
2126:
2121:
2116:
2111:
2106:
2101:
2096:
2091:
2086:
2081:
2076:
2071:
2066:
2061:
2056:
2051:
2045:
2043:
2039:
2038:
2036:
2035:
2029:
2024:
2019:
2014:
2008:
2006:
2000:
1999:
1997:
1996:
1991:
1986:
1981:
1975:
1968:
1966:
1962:
1961:
1959:
1958:
1953:
1948:
1942:
1939:
1938:
1929:
1927:
1926:
1919:
1912:
1904:
1890:
1889:
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:
24:
14:
13:
10:
9:
6:
4:
3:
2:
3021:
3010:
3007:
3005:
3002:
3000:
2997:
2995:
2992:
2991:
2989:
2970:
2962:
2961:
2958:
2952:
2951:Steganography
2949:
2947:
2944:
2942:
2939:
2937:
2934:
2932:
2929:
2927:
2924:
2922:
2919:
2917:
2914:
2912:
2909:
2907:
2906:Stream cipher
2904:
2902:
2899:
2897:
2894:
2893:
2891:
2887:
2881:
2878:
2876:
2873:
2871:
2868:
2866:
2865:Onion routing
2863:
2861:
2858:
2856:
2853:
2851:
2848:
2846:
2845:Shared secret
2843:
2841:
2838:
2836:
2833:
2831:
2828:
2826:
2823:
2821:
2818:
2816:
2813:
2811:
2808:
2806:
2803:
2801:
2798:
2796:
2793:
2791:
2788:
2785:
2782:
2777:
2774:
2773:
2772:
2769:
2767:
2764:
2762:
2759:
2757:
2754:
2752:
2749:
2747:
2744:
2742:
2739:
2737:
2736:Key generator
2734:
2732:
2729:
2727:
2724:
2722:
2719:
2717:
2714:
2710:
2707:
2705:
2702:
2700:
2697:
2696:
2695:
2694:Hash function
2692:
2690:
2687:
2685:
2682:
2680:
2677:
2675:
2672:
2670:
2669:Cryptanalysis
2667:
2665:
2662:
2658:
2655:
2654:
2653:
2650:
2648:
2645:
2643:
2640:
2638:
2635:
2634:
2632:
2628:
2624:
2617:
2612:
2610:
2605:
2603:
2598:
2597:
2594:
2590:
2576:
2573:
2571:
2568:
2566:
2565:Proof of work
2563:
2561:
2558:
2556:
2553:
2551:
2548:
2547:
2545:
2541:
2535:
2532:
2530:
2527:
2525:
2522:
2520:
2517:
2515:
2512:
2510:
2507:
2505:
2502:
2501:
2499:
2495:
2489:
2486:
2484:
2481:
2479:
2476:
2474:
2471:
2469:
2466:
2465:
2463:
2459:
2453:
2450:
2448:
2445:
2443:
2442:Rainbow table
2440:
2438:
2435:
2433:
2430:
2428:
2425:
2423:
2420:
2419:
2417:
2413:
2407:
2404:
2402:
2399:
2397:
2394:
2392:
2389:
2387:
2384:
2382:
2379:
2377:
2374:
2373:
2371:
2368:
2365:Authenticated
2362:
2356:
2353:
2351:
2348:
2346:
2343:
2341:
2338:
2336:
2333:
2331:
2327:
2324:
2322:
2319:
2317:
2314:
2312:
2309:
2307:
2304:
2302:
2299:
2298:
2296:
2294:
2293:MAC functions
2290:
2283:
2281:
2278:
2277:
2275:
2273:
2267:
2261:
2258:
2256:
2253:
2251:
2248:
2246:
2243:
2241:
2238:
2236:
2233:
2231:
2228:
2226:
2223:
2221:
2218:
2216:
2213:
2211:
2208:
2207:
2205:
2202:
2196:
2190:
2187:
2185:
2182:
2180:
2177:
2175:
2172:
2170:
2167:
2165:
2162:
2160:
2157:
2155:
2152:
2150:
2147:
2145:
2142:
2140:
2137:
2135:
2132:
2130:
2127:
2125:
2122:
2120:
2117:
2115:
2112:
2110:
2107:
2105:
2102:
2100:
2097:
2095:
2092:
2090:
2087:
2085:
2082:
2080:
2077:
2075:
2072:
2070:
2067:
2065:
2062:
2060:
2057:
2055:
2052:
2050:
2047:
2046:
2044:
2040:
2033:
2030:
2028:
2025:
2023:
2020:
2018:
2015:
2013:
2010:
2009:
2007:
2005:
2001:
1995:
1992:
1990:
1987:
1985:
1982:
1980:(compromised)
1979:
1976:
1974:(compromised)
1973:
1970:
1969:
1967:
1963:
1957:
1956:Known attacks
1954:
1952:
1949:
1947:
1944:
1943:
1940:
1936:
1932:
1925:
1920:
1918:
1913:
1911:
1906:
1905:
1902:
1898:
1894:
1888:
1884:
1881:
1878:
1875:
1874:
1870:
1858:on 2020-09-26
1854:
1850:
1846:
1842:
1836:
1832:
1828:
1824:
1817:
1816:
1810:
1809:
1805:
1796:
1792:
1786:
1783:
1778:
1774:
1768:
1765:
1760:
1754:
1750:
1746:
1742:
1738:
1731:
1727:
1723:
1719:
1713:
1710:
1699:on 2016-05-06
1695:
1691:
1687:
1682:
1677:
1673:
1669:
1662:
1658:
1652:
1649:
1644:
1637:
1633:
1629:
1628:Provos, Niels
1623:
1620:
1615:
1609:
1605:
1598:
1595:
1590:
1586:
1582:
1575:
1568:
1566:
1562:
1558:. March 2004.
1557:
1553:
1547:
1544:
1539:
1535:
1531:
1527:
1523:
1519:
1514:
1509:
1505:
1501:
1494:
1487:
1485:
1481:
1476:
1470:
1465:
1460:
1456:
1452:
1445:
1438:
1436:
1434:
1430:
1423:
1419:
1416:
1414:
1411:
1409:
1406:
1404:
1401:
1400:
1396:
1394:
1392:
1388:
1384:
1380:
1376:
1372:
1368:
1364:
1360:
1352:
1350:
1348:
1343:
1339:
1337:
1332:
1330:
1325:
1323:
1319:
1315:
1311:
1307:
1303:
1297:
1292:
1289:
1284:
1282:
1281:concatenation
1274:
1266:
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:
1047:
1045:
1043:
1039:
1033:
1030:
1023:
1017:
1012:
1007:
1005:
1001:
996:
987:
979:
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:
145:
143:
140:
131:
124:
122:
120:
116:
112:
108:
103:
101:
96:
92:
90:
86:
82:
74:
72:
70:
65:
63:
59:
54:
52:
49:that adds a "
48:
44:
40:
37:
33:
32:rainbow table
19:
18:Rainbow Table
2901:Block cipher
2741:Key schedule
2731:Key exchange
2721:Kleptography
2679:Cryptosystem
2623:Cryptography
2441:
1883:Cryptography
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:
2889:Mathematics
2880:Mix network
2555:Merkle tree
2543:Utilization
2529:NSA Suite B
1393:passwords.
1375:LAN Manager
1353:Common uses
1283:operator):
943:false alarm
36:precomputed
2988:Categories
2840:Ciphertext
2810:Decryption
2805:Encryption
2766:Ransomware
2367:encryption
2144:RadioGatún
1951: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
2830:Plaintext
2284:KDF1/KDF2
2203:functions
2189: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
2969:Category
2875:Kademlia
2835:Codetext
2778:(CSPRNG)
2756:Machines
2509:CRYPTREC
2340:Poly1305
2260:yescrypt
2174:Streebog
2054:CubeHash
2034:(winner)
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
2630:General
2415:Attacks
2345:SipHash
2301:CBC-MAC
2235:LM hash
2215:Balloon
2079:HAS-160
1347:LM hash
1322:Solaris
1130:LM hash
1116:Windows
1089:culture
1074:linux23
1070:linux23
1048:Example
966:collide
561:Since "
105:Though
2751:Keygen
2575:Pepper
2514:NESSIE
2461:Design
2255:scrypt
2250:PBKDF2
2225:Catena
2220:bcrypt
2210:Argon2
2169:Snefru
2164:Shabal
2159:SWIFFT
2139:RIPEMD
2134:N-hash
2109:MASH-2
2104:MASH-1
2089:Kupyna
2049:BLAKE3
2032:Keccak
2017:Grøstl
1994:BLAKE2
1887: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
2786:(PRN)
2369:modes
2245:Makwa
2240:Lyra2
2230:crypt
2179:Tiger
2129:MDC-2
2084:HAVAL
2069:Fugue
2027:Skein
2012:BLAKE
1989:SHA-3
1984:SHA-2
1978: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
2570:Salt
2534:CNSA
2401:IAPM
2355:VMAC
2350:UMAC
2335:PMAC
2330:CMAC
2326:OMAC
2321:NMAC
2316:HMAC
2311:GMAC
2280:HKDF
2149:SIMD
2099:Lane
2074:GOST
2059:ECOH
1946:List
1933: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
2406:OCB
2396:GCM
2391:EAX
2386:CWC
2376:CCM
2306:DAA
2184:VSH
2154:SM3
2124:MD6
2119:MD4
2114:MD2
2094:LSH
2064:FSB
1972:MD5
1885: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
2990::
2022: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
2615:e
2608:t
2601:v
2328:/
1923:e
1916:t
1909: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.
