# plaidCTF 2013 "cyrpto" Writeup

Mon 22 April 2013 by JavexA lot of the plaidCTF 2013 challenges were binary this year. Since I am more the Python guy, I looked for Python code to exploit. There were only very few of those and most of them weren't even about Python :-(

One of those challenges was "cyrpto". I don't know if it's intended or a typo but I will just use it since it was the official title. This is the challenge source code:

```
import random
# bleh, figuring out how to decrypt stuff is hard...
# good thing there's a service running at wherever the problem description says
ciphertext = (19139950631257094109974817512950844945236146526899325826152393111265339856332117664760030665587057736341341088217L, 698145134021698598302443232564752607941576857199606106641450906890460571956580687935633542046758257396595842622837937744732920113344374182219623260691576508226597259307160898152603847317630021751538L, 375)
pubkey = 914036124605072095896498645040317110444677693681625101303036515307269256964695517984683462742136579499746530214988587637694496516580350919995355407744891125814950650516684386468562425056693756001673L
def numbits(k):
if k == 1:
return 1
return int(math.ceil(math.log(k,2))) + (1 if k % 2 == 0 else 0)
def strtoint(s):
if len(s) == 0:
return 0
if len(s) == 1:
return ord(s[0])
return (ord(s[0]) << (8 * len(s[1:]))) | strtoint(s[1:])
def inttostr(s):
if s == 0:
return ""
c = chr(s & 0xFF)
return inttostr(s >> 8) + c
def encrypt(m, N):
L = numbits(m)
random.seed()
r = random.randint(2, N-1)
x = pow(r, 2, N)
y = x
l = 0
for k in range(0, L):
l = l << 1
l |= y & 1
y = pow(y, 2, N)
return (m ^ l, y, L)
```

As you can see there are three utility functions and an encryption function. Our
goal is to decrypt the `ciphertext` variable. First lets figure out how the
encryption works. The signature looks like this: `encrypt(m, N)` and looking
at the end of the function we see two things:

- There is a XOR operation on the message:
`m ^ l`. So thats most likely our ciphertext. - The variable
`N`is used as a modulus as can be seen in`pow(y, 2, N)`. So this**may**be our public key.

Additionally there was a decryption service running where you could connect. If you connect to it, it greets you with this message:

```
Send 1 to encrypt, 2 to decrypt, 3 to get pubkey:
```

Sending `1` leads to something like this:

```
m: 7
ciphertext: (1L, 383570276090565776871497996963276389087368959311873454618441023020446122143661875062362700669775526329053945008892060474398473720486014581315735747753055073608243808664051817203849707335530623749915L, 3)
```

Where we provide the value for `m`, e.g. `7` in this case and the service
returns a tuple with three elements as a ciphertext. We can also ask for the
decryption here:

```
c: 1
y: 383570276090565776871497996963276389087368959311873454618441023020446122143661875062362700669775526329053945008892060474398473720486014581315735747753055073608243808664051817203849707335530623749915
L: 3
Here you go!
```

As you see we get back the message again. Let's try the most obvious thing first: Let it decrypt the message:

```
c: 9139950631257094109974817512950844945236146526899325826152393111265339856332117664760030665587057736341341088217
y: 698145134021698598302443232564752607941576857199606106641450906890460571956580687935633542046758257396595842622837937744732920113344374182219623260691576508226597259307160898152603847317630021751538
L: 375
Nice try...
```

Well that would've been to easy, wouldn't it? Then let's figure out the
encryption process. We can verify that we can correctly encrypt messages by
executing `encrypt(message, pubkey)` where `pubkey` is already known
in the source and we choose the message. When we ask for its decryption we
get back our initial message so we know that encryption works this way.

I also tried to submit an empty (`0`) ciphertext with the given `y` and
`L` values.
I hoped the server would just spit out `c ^ l` which effictevly would have
given us `l`. But the server saw that and wouldn't let me. :-( Too bad.
It seems the server filters on the `y` part.

The next step now would be to figure out **how** decryption actually works.
However, this seems to be hard problem on its own: I think they might use
some RSA like stuff but as stated in the comment at the beginning: There is
a service for decryption so let's try a different route: *Can we trick the
server into decrypting the message for us?* Let's take a close look at how
the algorithm operates:

```
def encrypt(m, N):
L = numbits(m)
random.seed()
r = random.randint(2, N-1)
x = pow(r, 2, N)
y = x
l = 0
for k in range(0, L):
l = l << 1
l |= y & 1
y = pow(y, 2, N)
return (m ^ l, y, L)
```

The length depends on the message and since the message is only XORed, we can always compute the length ourselves. Note that the length still makes sense to avoid loosing leading zeroes.

Next we see that there is a random nonce being generated. It is modified and
set to `x` and then to `y`. This seems like a bit redundancy so lets cut that
short:

```
y = random.randint(2, N-1)
```

Note that while it changes the semantics, the logic is unaffected which is all
we need right now. Next we look at the loop. Here is where the real important
stuff happens. It is only three lines and it very important to understand them.
The first line `l = l << 1` shifts `l` by one bit. Since it is `0` at the
beginning, it remains `0` for now. Then comes `l |= y & 1`. Two things
happen here: First `y & 1` is computed, then it is ORed to `l`.

**This is important**: The expression `y & 1` does something very simple:
It chops of any leading bytes, effectively leaving only the last bit. What is
the last bit? Well it says whether the number was even or not. Nothing more.
So `l` is effectively a bitstring saying `even, not even, even, ...`.

As a last step, `y = pow(y, 2, N)` is executed. While `2` is a small
value, `y` is too large to pull the square root (known RSA weakness).
What we need to keep in mind here are three things:

`y`changes on every iteration- We get the last value of
`y`in the output - We can produce new
`y`values that follow (but not go backwards)

Look again at the loop. What would happen if `m` was one bit larger? The
`y` that we recieved would be used in the next iteration. And its last
bit would be appended to `l`. And we know that bit. We could easily
calculate the next step here. What happens if we do? We get a new ciphertext
that the server doesn't know. And most importantly, we get a new `y`. I
said above the server filters on it, so now he cannot anymore. So how can we
use that to trick the server into decrypting?

First of all think like this: Pretend the server is encrypting one bit more.
It would use the `y` that we know and check its last bit. Since `y` is
even, the last bit is `0`. Now imagine that the ciphertext we got would have
had a trailing `0` as well. What would that yield? A `0` in the ciphertext.
Lets do it: `c << 1`. Now we also need a new `y` that would get calculated
at the end of that loop. This is what we **would** recieve if another iteration
would have been performed. So we have

- A new
`y` - The ciphertext shifted by 1, so it now has space for the last bit of the message
- A new length (
`375 + 1 = 376`)

We can now ask the server for decryption on that message. It answers with:

```
90509775860478546334862465529642126634112405755992846988282238109064385906168446542663883843704092402706003699962
```

Bear with me, this might not be the original answer, I didn't write it down.
Remember that we shifted `c`, so we now have to shift `m` back.
This gives us:

```
45254887930239273167431232764821063317056202877996423494141119054532192953084223271331941921852046201353001849981
```

Now we only need to transform it into a message (note that the script was named
`client.py`):

```
>>> import client
>>> client.inttostr(45254887930239273167431232764821063317056202877996423494141119054532192953084223271331941921852046201353001849981)
KEY{Cyprus_keylength(cm)_STILL_BEST_KEY_FORMAT}
```

And there's the flag. The flag itself actually only is
`Cyprus_keylength(cm)_STILL_BEST_KEY_FORMAT`. And that's it. I found it pretty
hard to explain this relatively simple trick so if you have any questions,
please let me know in the comments.

I personally liked this challenge. You had to think around the corner and it took me several hours to figure out what the trick here was. You can actually get stuck very long trying to figure out a way how to decrypt before noticing that you don't need to know.