> 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/rsa/18.-timing-attacks.md).

# Timing Attacks on RSA

A timing attack recovers secret information by measuring:

```
How long operations take
```

Instead of breaking math directly, it exploits:

```
Implementation leaks through time differences
```

Goal:

```
Recover private key (d) or plaintext (M)
```

***

## 2. Where Timing Leaks Come From

RSA decryption:

```
M = C^d mod n
```

This is computed using **modular exponentiation**, typically:

```
Square-and-Multiply algorithm
```

***

## 3. Core Idea

The algorithm behaves differently depending on bits of `d`.

For each bit:

```
If bit = 1 → extra multiplication
If bit = 0 → no multiplication
```

So:

```
Execution time depends on bits of d
```

***

## 4. Example (Square-and-Multiply)

```python
def modexp(C, d, n):
    result = 1
    for bit in bin(d)[2:]:
        result = (result * result) % n  # square
        if bit == '1':
            result = (result * C) % n  # extra multiply
    return result
```

***

## 5. Leakage

```
Bit = 1 → slower
Bit = 0 → faster
```

If attacker can measure time precisely:

```
They can reconstruct d bit-by-bit
```

***

## 6. Attack Strategy

1. Send many ciphertexts
2. Measure decryption time
3. Analyze timing differences
4. Infer bits of `d`

***

## 7. Real Insight

Timing differences are small, so attacker:

```
Uses statistics over many samples
```

Example:

```
Average timing when bit=1 > bit=0
```

***

## 8. Types of Timing Attacks

### 1. Simple Timing Attack

```
Direct time measurement
```

### 2. Differential Timing

```
Compare many inputs statistically
```

### 3. Remote Timing

```
Over network (harder but possible)
```

***

## 9. Classic Vulnerability

Unoptimized RSA:

```
Branches based on secret bits
```

Example:

```
if bit == 1:
    multiply
```

This creates:

```
Observable timing differences
```

***

## 10. Why This Breaks RSA

Because:

```
Private key operations are not constant-time
```

Even tiny leaks:

```
→ accumulate over many queries
→ reveal full key
```

***

## 11. Real-World Impact

Timing attacks have affected:

```
Smartcards
SSL/TLS implementations
Cryptographic libraries
```

***

## 12. Countermeasures

### 1. Constant-Time Algorithms

```
Do same operations regardless of bits
```

Example:

```
Always multiply (dummy operations if needed)
```

***

### 2. Blinding

```
Randomize input before decryption
```

```
C' = C · r^e mod n
```

Then:

```
Remove randomness after decryption
```

***

### 3. Noise Injection

```
Add random delays
```

(Not perfect, but helps)

## 13. Important Concept

```
Timing attacks ≠ breaking math
Timing attacks = breaking implementation
```

## 14. When to Recognize in CTF

Look for:

```
Remote service
Time differences in responses
Hints like:
"fast/slow"
"timing"
```

## 15. Summary

```
Measure execution time
→ detect bit-dependent behavior
→ recover secret key
```

## Final Wrap-Up

You’ve now covered **all major RSA attack classes**:

```
Factoring-based
Low exponent
CRT / broadcast
Related messages
Small roots (Coppersmith)
Oracle attacks
Implementation attacks
```


---

# 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/rsa/18.-timing-attacks.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.