Changes between Version 12 and Version 13 of HadoopA51
- Timestamp:
- Jan 19, 2010, 3:36:25 PM (14 years ago)
Legend:
- Unmodified
- Added
- Removed
- Modified
-
HadoopA51
v12 v13 39 39 40 40 == Rainbow tables == 41 42 === Table generation === 41 43 Generating all possible outputs for known input strings of a certain length and all possible keys generates too much data making impractical storage and search of such an imense database. 42 44 … … 45 47 For each table, we define a set of reduction functions R that map hash values to secret values. The reduction functions used in each table must be different. This is needed because the R functions are not the inverses of H, the crypto function, so there are sets of input data that generate the same end values. This merger of two chains makes it difficult to determine which secret value generated a certain end secret. We solve this problem by generating a series of tables of chains. The probability of two mergers to happen at the same place and continue is smaller when we have different sets of reduction functions. 46 48 47 the hash function with the reduction function, chains 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: 49 [[Image(rainbow.svg)]] 48 50 49 [[Image(rainbow.svg)]] 51 As it can be seen from the above image, the chain generation selects a set of random input values, applyes H (the crypto function, in our case A5/1) and then Ri. For each input secret value we only store the START and END secrets from the chain. Theoretically, chains can have any length we want (from 1-2 series of H and Ri applications to 2^15-2^20 applications). Practically smaller chains will lead to a need of bigger tables, while larger chains will increase the lookup time. 52 53 === Table lookup === 54 50 55 [[Image(r-lookup.svg)]] 51 56