# CSAW CTF 2021 (Qualifiers) - Forgery

"Forgery" is a crypto challenge in CSAW CTF 2021 Qualifiers. You can download the challenge file here.

## Details

To solve the challenge, we would need to forge a signature that says "Cisco", "Felicity" or "both". Upon closer inspection, the signature scheme is the ElGamal signature scheme. The main giveaway is how signatures are verified:

```
pow(g, m, p) == (pow(y, r, p) * pow(r, s, p)) % p
gm =? yr rs mod p
```

Notice that the message `m`

is verified, not its hash digest! This is key because it essentially allow the attacker to forge valid signatures on random messages. Why? That's because we could "choose" a `r`

and `s`

value and reverse them to find the corresponding message `m`

. We could do the following:

- randomly select
`e`

from 2 to`p-1`

- compute
`r = gey mod p`

Now, `gm = yr (gey)s = yrgesys mod p`

. If `ys = y-r mod p`

, then `gm = ges mod p`

. We do not need information on the secret key `x`

to compute both `r`

and `s`

!

So, to forge the signature, one would compute `s = -r mod (p-1)`

, which causes `ys = y-r mod p`

. We have to `mod (p-1)`

instead of `p`

because `s`

and `r`

are used as integers rather than as group elements. Finally, compute the message of the signature, `m = es mod (p-1)`

.

```
def eforge(p, g, y):
while True:
e = randint(2, p-1) # select random v
r = (pow(g, e, p) * pow(y, 1, p)) % (p) # r = g^e . y mod p
s = (-r) % (p-1) # s = -r mod p-1
m = e*s % (p-1)
return m, r, s
```

But wait! we can't control `m`

! How are we suppose to include "Cisco", "Felicity" or "both" in it? Now that we can forge existential signatures `(m, r, s)`

, we could also forge arbitrary signatures using Bleichenbacher's attack if and only if the verifier accepts a `r > p`

. Unfortunately, that's not the case for this challenge due to the following check:

```
if any([x <= 0 or x >= p-1 for x in [m,r,s]]):
return False
```

However, there is one subtle problem about how the challenge "accepts" our answers. The first check it does it by running this conditional:

`if b'Felicity' not in answer_bytes and b'Cisco' not in answer_bytes and b'both' not in answer_bytes: `

Notice, it doesn't check if `answer_bytes`

is **EXACTLY** the strings that we should forge. It merely checks if the strings are part of the `answer_bytes`

. This opens a possibility of simply adding our answer to the random signature, in hopes that the verifier "verifies" the signature part while disregarding the strings that we append/prepend. One peculiar line in the verification function confirms this possibility:

```
MASK = 2**1024 - 1
m = int(answer, 16) & MASK
```

Nice! This means that the lower 1024 bits of the answer is preserved, while any bits above 1024 bits, or 128-bytes are disregarded during verification. To solve the challenge, we would simply do the following:

```
m0, r0, s0 = eforge(p, g, y)
# append our target
forged = m0.to_bytes((m0.bit_length() + 7) // 8, 'big')
forged = b'both\x00\x00\x00\x00' + forged
ah = forged.hex()
```

Then, we send `ah`

, `r0`

and `s0`

through the netcat connection and get the flag.