MD5CRK

<h2 id="complexity">Complexity</h2>
<p>The expected time to find a collision is not equal to 
  
    
      
        
          2
          
            N
          
        
      
    
    {\displaystyle 2^{N}}
  
 where 
  
    
      
        N
      
    
    {\displaystyle N}
  
 is the number of bits in the digest output.  It is in fact 
  
    
      
        
          
            2
            
              N
            
          
          !
        
        
          (
          
            2
            
              N
            
          
          −
          K
          )
          !
          ×
          
            
              
                2
                
                  N
                
              
            
            
              K
            
          
        
      
    
    {\displaystyle 2^{N}! \over {(2^{N}-K)!\times {2^{N}}^{K}}}
  
, where 
  
    
      
        K
      
    
    {\displaystyle K}
  
 is the number of function outputs collected.
</p><p>For this project, the probability of success after 
  
    
      
        K
      
    
    {\displaystyle K}
  
 MD5 computations can be approximated by: 
  
    
      
        
          1
        
        
          1
          −
          
            e
            
              
                
                  K
                  ×
                  (
                  1
                  −
                  K
                  )
                
                
                  2
                  
                    N
                    +
                    1
                  
                
              
            
          
        
      
    
    {\displaystyle 1 \over {1-e^{K\times (1-K) \over 2^{N+1}}}}
  
.
</p><p>The expected number of computations required to produce a collision in the 128-bit MD5 message digest function is thus: 
  
    
      
        
          1.17741
          ×
          
            2
            
              N
              
                /
              
              2
            
          
        
        =
        
          1.17741
          ×
          
            2
            
              64
            
          
        
      
    
    {\displaystyle {1.17741\times 2^{N/2}}={1.17741\times 2^{64}}}

</p><p>To give some perspective to this, using Virginia Tech's <a href="/facts/System_X_(supercomputer)/lXqKsMzC">System X</a> with a maximum performance of 12.25 Teraflops, it would take approximately 
  
    
      
        
          2.17
          ×
          
            10
            
              19
            
          
          
            /
          
          12.25
          ×
          
            10
            
              12
            
          
          ≈
          1
          ,
          770
          ,
          000
        
      
    
    {\displaystyle {2.17\times 10^{19}/12.25\times 10^{12}\approx 1,770,000}}
  
 seconds or about 3 weeks.  Or for commodity processors at 2 gigaflops it would take 6,000 machines approximately the same amount of time.
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/List_of_volunteer_computing_projects/aQu3s9vG">List of volunteer computing projects</a></li>
<li><a href="/facts/Brute_force_attack/TXl8pkfb">Brute force attack</a></li></ul>

<h3>Further reading</h3>
<ul><li><a href="/facts/Paul_C._van_Oorschot/zHRUkK4P">Paul C. van Oorschot</a>; Michael J. Wiener. <a href="http://www.scs.carleton.ca/~paulv/papers/acmccs94.pdf"><i>Parallel Collision Search with Application to Hash Functions and Discrete Logarithms</i></a> (PDF). ACM Conference on Computer and Communications Security 1994. pp. 210–218.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Xiaoyun Wang; Dengguo Feng; Xuejia Lai; Hongbo Yu (17 August 2004). "Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD". Cryptology ePrint Archive. <a href="https://eprint.iacr.org/2004/199" target="_blank">https://eprint.iacr.org/2004/199</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>"Popular, Yet Obsolete, Banking Algorithm Broken". CertainKey News (Press release). 17 February 2005. Archived from the original on 13 May 2011. <a href="https://web.archive.org/web/20110513090927/http://www.certainkey.com/news/?13" target="_blank">https://web.archive.org/web/20110513090927/http://www.certainkey.com/news/?13</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
</ol>

MD5CRK open-in-new

MD5CRK