# Presentation: 745442

## The Hash Function “Fugue”

- Shai Halevi
- William E. Hall
- Charanjit S. Jutla
- IBM T. J. Watson Research Center

## Broad Overview

- Maintains Large State (~1000 bits)
- Large Initial State
- Tougher to invert
- Large Final State
- Tougher to find collision
- Final Compression (to say, 256 bits)
- Lots of Crunching
- Tougher to find “properties”, invert, or find collision
- Uses ‘super’ AES-like rounds
*Focus of the Talk* : Collision Resistance

## Fugue-256

- Initial State (30 words)

- Process

- New State

- M1

- M_i

- Final Stage

- Hash Output (8 words)

- Iterate

-  State

***Fugue-256***

## Fugue-256

- Initial State (30 words)

- Process

- New State

- ΔM1

- ΔM_i

- Final Stage

- Δ = 0

- Iterate

-  State

***Fugue-256***

- State Δ = 0

**Notes:**
Shows Internal vs External Collisions

## Overview (contd.)

- Inspired by Grindahl [KRT07]
- Small incremental input rounds
- Long final stage.
- Attacked by Peyrin [P07] -Internal Collisions
- Fugue has a Proof Driven Design
- _Proves_ that Peyrin-style attacks do not work
- Proves bound on differential attacks assuming limits (extremely generous) on message modification.
- _Proves_ bound on finding External Collisions.
- Like AES, uses MDS codes
- but bigger MDS codes
- Does not need MD mode theorem

## Design Challenges

- Non-secret Key/ Un-keyed properties gives adversary “non-standard” approaches to enhance differential attacks
- Message Modification
- Neutral Bits, Neutral Differentials

## Good News

- The main “non-secret key” properties are about collisions
- Collision, TCR, 2nd Pre-image, Universal Hash
- The differential requires output difference to be zero, i.e. out = 0.
- Is it easy to prove something about such restricted differentials?
- Quandary: All good practical designs are based on permutations.

## Fugue-256

- Initial State (30 words)

- Process

- New State

- ΔM1

- ΔM_i

- Final Stage

- Δ = 0

- Iterate

-  State Δ  0

***Fugue-256***

- Invoke Coding Theory

**Notes:**
There is cross mixing in the two ladders of the final stage.
Also, the whole thing is repeated about twice.

## What’s in an elementary round?

- [Called SMIX in the paper]
- Works on 128 bits (just like AES)
- Arranged as 4 by 4 matrix (just like AES)
- Starts with S-box substitution (same as AES)
- Does linear mixing (more advanced than AES)

## AES Round

## AES Round

## Leads to MDS code over 16 bytes!

- Fugue elementary round “SMIX”

## Leads to MDS code over 16 bytes!

- Fugue elementary round “SMIX”

## Leads to MDS code over 16 bytes!

- At least 13 active S-Boxes

**2^{-6*13}**
**= 2^{-78}**

- Fugue elementary round “SMIX”

## FINAL STAGE

***FINAL STAGE***

- Rapid
- Mixing
- (G1)

- Differential
- Killer
- (G2)

- output

## External Collision Provable Bound

- _Assumption_: Differential Attacks
- Attacker controls difference, state itself is random
- Probabilities of different rounds are assumed independent.
- Consider 2 messages leading to two different states at *middle* of final stage
- After the rapid mixing
- Allow the adversary to force a difference D of its choice at this point.

## External Collision Provable Bound

- _Theorem_: For any state difference D  0, if the states at the start of G2 are chosen randomly then
- 		Pr[ Collision in 256 bit output  |  D ]
- 		      2-129
- Recall, assumes independence assumption

## Fugue-256

- Initial State (30 words)

- Process

- New State

- Final Stage

- Iterate

-  State

***Fugue-256***

- Process

- M1

- SMIX

- 

- M1

- Repeat once more

##                     | _{i-4} = D ]     2-168 

- Process

- State

- M, M’_i

-  State _i = 0

- Process

- State

- M, M’_i-1

- Process

- State

- M, M’_i-2

- Process

- Random States, but _{i-4} = D

- M, M’_i-3

- _ __Theorem__             _
- Pr [ M, M’ <i-3..i> :  _i =0
-                     | _{i-4} = D ]     2-168

- INTERNAL COLLISION PROVABLE BOUND

## Message Modification?

- Neutral Bits?
- How justified is random state?
- We do more advanced analysis, giving extremely generous “free message modification / all bits neutral ” allowance.
- Still can prove 2^{-128} bound.

## Performance (Fugue-256)

- 32 bit Intel Core 2 Duo (Linux)
- ANSI C  : 36 cycles/byte
- 64 bit Intel  Xeon (CygWin)
- ANSI C  : 28 cycles/byte
- 8-bit: as good as AES...similar advantages
- Decent state size :  120 bytes (1000 cycles/byte)
- Hardware: 90nm IBM Cu-8 technology
- 360 MB/sec (basic) to 1.8 GB/sec.

## Conclusion

- Proof-driven Design leads to best of both worlds:

- - Security 
-        - Performance 

## THE END

## Fugue is a Universal Hash Fn.

- Requirement:
- For all messages M1,M2,
-    Pr_k[ Fugue_k(M1) = Fugue_k(M2)] is low
- Key is 8 words (256 bits), placed in the right most 8 words of initial state.
- Assume (for now) same length.
- Wlog internal collision, otherwise messages irrelevant.

## Internal coll. at end of Round 0

- Number the rounds backwards
-  0, -1, -2,...
- For now, assume states at start of round –3 are random (but say, with some adversary determined  difference D).
- Then, we have already proven 2^{-168}.

## What about the random assump.

- Random but diff = D at start of round –3.
- That is allowing adversary to get an XOR-diff  D with probability 1 (on a random key)!
- So seems not that bad an assumption.
- But, is entropy depletion a problem?
- State starts with 8 word entropy.
- Each round adversary inserts a word (pair).

## Input State (30 words)

- Process

- Output State (O_S)

- M1

- SMIX

- 

- D

- Repeat once more

- I_S

- M1

- (D; O_S)  => ! (M1;IS)
- (D1,O_S) ->(M1; IS)
-     (D2,O_S) ->(M1; IS’) ?
- Nope!

## Input State (30 words)

- Output State (O_S) = 0

- X

- SMIX

- 

- D

- I_S

- M1

- (D1,O_S) ->(M1; IS)
-     (D2,O_S) ->(M1; IS’) ?

- M1

- X

- 

- SMIX

- 0

- All 4 words  non-zero

-  X non-zero

- All 4 words  non-zero

-  M1 non-zero

## Discarded Slides

## Desired Properties

- Keyed Properties
- Secret Key
- PRF (MAC)
- Non-Secret Key (Salted)
- Universal Hash, Extractor, Key Derivation
- Collision Resistance, TCR, Pre-image (1st / 2nd)
- Un-Keyed Versions
- Collision Resistance, Pre-image (1st /2nd)