Prepared By: Parth Patel ( P11CO042 )
Guided By: Dr. D. C. Jinwala
Introduction Exhaustive Search Dictionary of Hash Martin Hellman's Cryptanalytic TMTO Why Called TMTO? Problems with Hellmans TMTO Improvements Rainbow Table Schema Improved Rainbow Table Protection Existing Implementation Conclusion
Given Encryption function E. Plaintext P0 and corresponding cipher text C0. Recovering a key K N is equivalent to inverting one-way function.
C0 = EP0(K) EP0-1(C0) = K
Problem : Find pre image of a given output of One-Way function H.
Given a hash Y find any corresponding X such
that Y=H(X) where H is one-way function.
Traditional attack: Brute Force
Always theoretical possible Needs exponential time to run Ex. MD-5 is 128 bit hash
Can we improve the time to recover Password?
Pre-calculate all hashes, store all
Store in sorted order Can crack hashes immediately Uses massive amounts of space
key aaaa10ba956cacf8861139efb9 bbbb6348157868b25c81aebfb9 cccc2c3b5aa76527deb882cf99 value software security zoo
If value column is ignored and 64-bit output of oneway function, the space required is 8*264 bytes (7 Exabyte).
In 1980 Hellman described an attack to inverse N values of a function[1] Needs N calculations before the attack Calculate N but store few to save storage Practically applicable when same Cryptanalysis have to be carried out many times.
One have Given a One-way function .
H: {VariableLengthStrings} -> {0,1}n
Define a Reduction function which reduces the output of H to input domain of H.
R: {0,1}n -> {VariableLengthStrings}
Now generate hash chain by applying function H and R successively .
So the chain looks like this
aaaaaa --H--> 5AE419F8 --R--> eyiygsl --H--> AC4B68E2 --R--> sgfnyd . --R--> keiget
Generate multiple chains with this schema but different initial points. Only Store starting point and ending point.
So the chain looks like this
aaaaaa --H--> 5AE419F8 --R--> eyiygsl --H--> AC4B68E2 --R--> sgfnyd . --R--> keiget
Generate multiple chains with this schema but different initial points. Only Store starting point and ending point.
Look up 7
h8
Not Found
Given the hash h8 find the pre image for that
Look up
10
R h7
Not Found
Given the hash h8 find the pre image for that
Look up
R h10
10
Found chain starting with 4
Given the hash h8 find the pre-image for that
Re-compute chain starting with 4 until h8 is encountered At each step keep track of last used preimage
Success Rate (Perfect table):
m = Chain Length n = Number Of Chains N = Total number of possible hash
Table Lookup is Costly Slow IO The reduction function can give the same password for two different hashes merges Even if you find an end in the table, you may not find the password in the chain false alarms
Distinguished point Method suggested by L. Rivest.[2] Continue to compute chain until a point which satisfy some predefined condition.
Ex: first/last 20 bits of hash is zero
So when running online attack do not lookup table after each reduce operation but only when predefined condition satisfied. Variable length chain. Helps to identify Merging chains.
Avoine suggested a method to reduce checkpoints[3] It defines set of positions in the chains to be checkpoints. The value of checkpoint function G is calculated for each checkpoint of each chain as shown.
During online attack for each check point we re-calculate value for G. When matching chain is found in table all the generated checkpoint values are compared with the check point values stored in table. If they differ at least for one checkpoint it is declared as false alarm.
In 2003 Oechslin introduced new way of table generation. Instead of using one reduction function a set of reduction function {R1,R2,R3 ..} . After each application of one-way function a reduction function from this set is used. Significant improvement in merging chains. If N reduction function is used then after any collision there is only 1/N probability of merging chain.
Source: Rainbow table - Wikipedia
Source: Rainbow table - Wikipedia
In 2009, V. L. Thing and H. M. Ying introduced new table structure.[5] This table structure improves upon memory requirements
Do not hash password directly. Use Salted Hash
saltedhash(password) = hash(password + salt) saltedhash(password) =hash(hash(password) + salt)
Key stretching
key = hash(password) for 1 to 65536 do key = hash(key + password)
Rtgen
Used to generate rainbow tables of various algo LM, NTLM, MD5, SHA, ORACLE Various implementation use this tables Sam Inside, Able & Cain
Ophcrack [13]
7.5 GB table size XP special (7.5GB) 96% Success Rate Used against LM hash Recover in less than 5 Minutes
DistrRTgen [8]
Distributed Table Generation Project. BOINC grid computing architecture. Tables can be downloaded free.
Security Research Lab [10]
GSM call Interception A5/1 encryption Algorithm. 2 TB of Hybrid Table.
Elcomsoft : Thunder tables
4 GB table. Used to crack RC4 algorithm in Office Files.
Brute force attack is not always practical as it takes too long table lookup attack usually takes too much amount of memory, sometimes beyond current technology reach. Time-Memory Trade-off attacks is another generic framework that can be applied to invert one-way function with opportunity to balance required time vs. memory.
