Fugue (hash function)

<h2 id="supermix">SuperMix</h2>
<p>The 224 and 256 bit variants of Fugue work with a state which can be represented in 4 by 30 matrix of unsigned bytes, whereas the 384 and 512 bit variants work with a 4 by 36 byte matrix. Operations can be performed in-place on this state.
</p><p>The core of the algorithm, known as the "SuperMix transformation", takes 4×4 matrix as input and returns a new 4x4 matrix. The input to SuperMix is simply the first four columns of the current 30-column state and the output is used to replace this same state area (i.e. SuperMix affects only the 4x4 matrix at the head of the state).
</p><p>The SuperMix function can be defined as:
</p><p>
  
    
      
        
          SuperMix
        
        (
        U
        )
        =
        
          ROL
        
        
          (
          
            M
            ⋅
            U
            +
            
              
                (
                
                  
                    
                      
                        ∑
                        
                          j
                          ≠
                          0
                        
                      
                      
                        U
                        
                          j
                        
                        
                          i
                        
                      
                    
                    
                      0
                    
                    
                      0
                    
                    
                      0
                    
                  
                  
                    
                      0
                    
                    
                      
                        ∑
                        
                          j
                          ≠
                          1
                        
                      
                      
                        U
                        
                          j
                        
                        
                          i
                        
                      
                    
                    
                      0
                    
                    
                      0
                    
                  
                  
                    
                      0
                    
                    
                      0
                    
                    
                      
                        ∑
                        
                          j
                          ≠
                          2
                        
                      
                      
                        U
                        
                          j
                        
                        
                          i
                        
                      
                    
                    
                      0
                    
                  
                  
                    
                      0
                    
                    
                      0
                    
                    
                      0
                    
                    
                      
                        ∑
                        
                          j
                          ≠
                          3
                        
                      
                      
                        U
                        
                          j
                        
                        
                          i
                        
                      
                    
                  
                
                )
              
            
            ⋅
            
              M
              
                T
              
            
          
          )
        
      
    
    {\displaystyle {\text{SuperMix}}(U)={\text{ROL}}\left(M\cdot U+{\begin{pmatrix}\sum _{j\neq 0}U_{j}^{i}&0&0&0\\0&\sum _{j\neq 1}U_{j}^{i}&0&0\\0&0&\sum _{j\neq 2}U_{j}^{i}&0\\0&0&0&\sum _{j\neq 3}U_{j}^{i}\end{pmatrix}}\cdot M^{T}\right)}

</p><p>where:
</p>

M
        =
        
          
            (
            
              
                
                  1
                
                
                  4
                
                
                  7
                
                
                  1
                
              
              
                
                  1
                
                
                  1
                
                
                  4
                
                
                  7
                
              
              
                
                  7
                
                
                  1
                
                
                  1
                
                
                  4
                
              
              
                
                  4
                
                
                  7
                
                
                  1
                
                
                  1
                
              
            
            )
          
        
      
    
    {\displaystyle M={\begin{pmatrix}1&4&7&1\\1&1&4&7\\7&1&1&4\\4&7&1&1\end{pmatrix}}}
  
;

U
      
    
    {\displaystyle U}
  
 is a 4x4 matrix of bytes (i.e. the matrix after the S-box substitution of the input); and

M
          
            T
          
        
      
    
    {\displaystyle M^{T}}
  
 is the transpose of M.
<p>The transformation 
  
    
      
        R
        O
        L
      
    
    {\displaystyle ROL}
  
 takes a 4x4 matrix, and rotates the 
  
    
      
        i
      
    
    {\displaystyle i}
  
-th row to the left by 
  
    
      
        i
      
    
    {\displaystyle i}
  
 bytes, i.e.
</p>

ROL
        
        (
        W
        
          )
          
            j
          
          
            i
          
        
        =
        
          W
          
            j
            −
            i
            
              
              (
              mod
              
              4
              )
            
          
          
            i
          
        
      
    
    {\displaystyle {\text{ROL}}(W)_{j}^{i}=W_{j-i{\pmod {4}}}^{i}}

<h2 id="fugue-20">Fugue 2.0</h2>
<p>Fugue 2.0 is a tweak of original Fugue, which runs at about twice the speed of Fugue for 256-bit output. The designers claim advanced proofs of resistance to differential collision attacks for this improved version.
A complete specification can be found at the link below.
</p>
<h2 id="external-links">External links</h2>
<ul><li><a href="https://archive.today/20130126071924/http://researcher.ibm.com/view_project.php?id=3253">The Hash Function Fugue</a></li></ul>

Fugue (hash function) open-in-new

Fugue (hash function)