> For the complete documentation index, see [llms.txt](https://alham-rizvi.gitbook.io/alhamrizvi/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://alham-rizvi.gitbook.io/alhamrizvi/cryptography/hashing/19.-compression-functions.md).

# 19. Compression Functions

### 1. What a Compression Function Is

At the core of most hash functions lies a component called the **compression function**.

It takes:

```
(previous_state, message_block) → new_state
```

* Input: fixed-size block + current state
* Output: new fixed-size state

***

### 2. Why It’s Called “Compression”

It “compresses”:

```
large input → fixed-size output
```

Example:

* Input block: 512 bits
* State: 256 bits
* Output: 256 bits

So information is continuously reduced and mixed.

***

### 3. Role in Hash Functions

In **Merkle–Damgård**, the compression function is used like this:

```
H1 = f(H0, M1)
H2 = f(H1, M2)
H3 = f(H2, M3)
...
```

So:

> compression function = the actual “work” of hashing

***

### 4. What It Must Achieve

A good compression function must provide:

#### 1. Diffusion

Small change in input → large change in output

```
1 bit change → many bits flipped
```

***

#### 2. Confusion

Output should hide relationship with input

***

#### 3. Non-linearity

Prevent easy mathematical analysis

***

### 5. Internal Operations

Most compression functions use:

* XOR
* bit rotations
* modular addition
* substitution tables (S-boxes)

***

### 6. Example (Simplified SHA-256 Style)

```
state = state + f(state, block)
```

Where `f` includes:

* mixing
* rotations
* constants

***

### 7. Block Processing Flow

```
block → mix with state → transform → new state
```

This repeats for all blocks.

***

### 8. Why It’s Critical

If compression function is weak:

* collisions become easy
* hash becomes insecure

***

### 9. Real-World Failures

#### MD5

* Weak compression design
* collisions found

***

#### SHA-1

* Structural weaknesses
* practical collisions exist

***

#### SHA-2

* Strong compression function
* no practical break

***

### 10. Mathematical Intuition

Compression function acts like:

```
state = F(state ⊕ block)
```

Repeated mixing ensures:

* no simple reverse
* no predictable pattern

***

### 11. Why It’s Hard to Attack Directly

Because:

* highly non-linear
* many rounds
* complex bit mixing

So attackers usually target:

* structure (like length extension)
* misuse (like bad protocol design)

***

### 12. Relation to Block Ciphers

Some hashes (like Whirlpool) use:

```
block cipher-like compression
```

Others (like SHA-2):

* use custom-designed functions

***

### 13. Compression vs Permutation (Important)

| Feature     | Compression | Permutation   |
| ----------- | ----------- | ------------- |
| Used in     | SHA-2       | SHA-3         |
| Input size  | bigger      | same as state |
| Output size | smaller     | same size     |
| Key idea    | reduce      | shuffle       |

***

### 14. CTF Mindset

You usually don’t:

* break compression directly

Instead:

* exploit structure
* misuse
* weak inputs

***

### 15. Key Insight

Compression function is:

> the engine that mixes everything together

If it’s strong → hash is strong If it’s weak → everything breaks

***

### 16. Visual Intuition

```
state + block → [mixing engine] → new state
```

Repeat until all blocks processed.

***

### 17. Final Summary

Compression function:

* mixes input with state
* reduces data size
* provides security properties
* is core of hash algorithm

***

### 🔥 Core Takeaway

If you understand compression:

```
you understand how hashes actually transform data internally
```

***

### 🧠 Big Picture (You Completed Core Hash Internals)

You now understand:

```
Merkle–Damgård → chaining structure
Sponge         → modern design
Padding        → input formatting + attack surface
Compression    → core mixing engine
```

***

#### What comes next (important)

Now you’re ready for:

👉 **Hash Attacks (real exploitation)**

* Length extension (practical)
* Collision attacks
* Rainbow tables
* Hash misuse bugs


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://alham-rizvi.gitbook.io/alhamrizvi/cryptography/hashing/19.-compression-functions.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.