DP Info

Recently I've been working on creating a real world comparison of HT, DP, rainbow DP, VDP, rainbow VDP, chained DP, rainbow chained DP, chained rainbow DP, RT, and perfect RT. So I've been working on optimal configurations for DPs. It is in your best interest to set a min and max chain length for a given average chain length. You want a low max chain length since this deceases prework which can be less than average chain length per table and deceases false alarm checking because there is a lower chance that you get a DP. The function of prework as max chain length increases is like a step function where each step increases but jumps lower than the previous max it peaks when min chain length is 0 then decreases to the average chain length. Also the percentage of table lookups is a step function only it decreases and jumps up at all the same step points. A DP work factor of around 6.5x will probably take the same amount of time as a perfect rainbow table to generate. Although this DP table will more than likely not be as good as a perfect rainbow table.

Here are the charts for a DP with an average chain length of 2048. A DP work factor of around 6.5x has a max chain length of 2360. Notice at a max chain length of 5718 there is an interesting point in all the charts. This is where min chain length is clipped at 1. These charts vary a little with different average chain lengths. The charts to the left are scaled to show detail for the first 450 max chain lengths. The charts to the right are scaled to show the rest of the max chain lengths. The last two charts are scaled to show data that got clipped in earlier charts.

This is to illustrate the steps, green is increased and red is decreased compared to the previous max chain length for pre-work, table lookups, and DP work factor. Note that the first few for table lookups are almost exactly the same and thus are not colored. DP work factor looks a little weird but is correct the last decrease shown below is 0.941% but the following increases only 0.136% with each one increasing 0.032% to 0.036%.