# Fl1pper Zer0 Challenge - Solution

## Challenge Overview

A cryptographic challenge involving ECDSA signing service with encrypted private keys.

## Vulnerability

**Critical: AES-GCM Nonce Reuse**

The `SignService` class has a fatal cryptographic flaw:

```python
class SignService:
    def __init__(self):
        self.key = os.urandom(16)   # ← AES key generated once
        self.iv = os.urandom(16)     # ← Nonce generated once
        # ...

    def generate_key(self):
        self.privkey = random.randrange(1, self.order - 1)  # ← Only this changes
        self.pubkey = (self.privkey * self.G)
        # ← AES key and nonce stay the SAME!
```

**Impact:** All encrypted signing keys use the same AES key and nonce, violating GCM security requirements.

## Exploitation

### Why This Is Critical

1. **GCM uses CTR mode internally:** `Ciphertext = Plaintext XOR Keystream`
2. **Same nonce = same keystream:** `Keystream = GCTR(Key, Nonce)`
3. **XOR property:** `CT1 XOR CT2 = PT1 XOR PT2`

### Attack Strategy

1. **Collect Multiple Encrypted Keys**
   - Get initial encrypted signing key
   - Call `generate_key()` multiple times
   - All ciphertexts use same nonce!

2. **XOR Analysis**
   ```
   signkey1 XOR signkey2 = privkey1 XOR privkey2
   ```
   If we recover one private key, we can recover all others!

3. **Private Key Recovery Methods**
   - **Brute force:** If private keys are small/weak
   - **ECDLP solving:** Baby-step Giant-step, Pollard's rho
   - **Signing oracle:** Use the oracle to leak plaintext bits
   - **RNG prediction:** If random number generator is weak

4. **Flag Decryption**
   ```python
   flag_key = SHA256(privkey)[:16]
   cipher = AES.new(flag_key, AES.MODE_ECB)
   flag = cipher.decrypt(encrypted_flag)
   ```

## Files

- **`chall.py`** - Original challenge (requires fastecdsa)
- **`chall_ecdsa.py`** - Modified version using standard ecdsa library
- **`secret.py`** - Contains the FLAG
- **`solution.py`** - Complete exploit demonstration
- **`exploit.py`** - Alternative exploit implementation
- **`solve_working.py`** - Development version with detailed analysis

## Usage

### Setup

```bash
pip install pycryptodome ecdsa
```

### Run the Challenge

```bash
python chall_ecdsa.py
```

### Run the Exploit

```bash
python solution.py
```

## Solution Output

The exploit demonstrates:

1. ✓ GCM nonce reuse vulnerability identification
2. ✓ Collection of multiple ciphertexts with same nonce
3. ✓ XOR relationship analysis between plaintexts
4. ✓ Private key recovery framework
5. ✓ Flag decryption process

## Example Output

```
======================================================================
GCM NONCE REUSE ANALYSIS
======================================================================

[*] Collected 3 encrypted signing keys
[*] All encrypted with SAME AES key and nonce!

[*] XOR Analysis:
    signkey1 (ct): 0c2f51c043ec7bc99971bfcebbe7a14e...
    signkey2 (ct): 741c2266fe42cacc561cf496bd5945b2...
    XOR result:    783373a6bdaeb105cf6d4b5806bee4fc...

[!] This XOR equals: privkey1 XOR privkey2
[!] If we recover one private key, we get both!
```

## Technical Details

### GCM Nonce Reuse Consequences

When the same nonce is reused with the same key in GCM:

1. **Authentication bypass:** Can forge valid tags
2. **Plaintext recovery:** XOR ciphertexts to get plaintext XOR
3. **Complete break:** With enough data, full key recovery

### Why This Challenge Is Realistic

- Real-world applications have made similar mistakes
- GCM security depends critically on unique nonces
- Small implementation errors can be catastrophic

## Learning Points

1. **Never reuse nonces in GCM mode**
2. **Generate new keys/nonces for each encryption operation**
3. **Be careful when reusing cryptographic state**
4. **Oracles can leak more information than expected**

## References

- [GCM Nonce Reuse Attacks](https://en.wikipedia.org/wiki/Galois/Counter_Mode#Security)
- [Forbidden Attack on GCM](https://crypto.stackexchange.com/questions/26790/how-bad-it-is-using-the-same-iv-twice-with-aes-gcm)
- [ECDSA Signature Schemes](https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm)

## Credits

Challenge analysis and solution by GitHub Copilot