plaidCTF 2013 "cyrpto" Writeup

Mon 22 April 2013 by Javex

A 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)
    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)
    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:


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:


Now we only need to transform it into a message (note that the script was named

>>> import client
>>> client.inttostr(45254887930239273167431232764821063317056202877996423494141119054532192953084223271331941921852046201353001849981)

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.