# PRetty stroNG - InCTF Internationals 2019

Intended solution of PRetty stroNG challenge from InCTF Internationals 2019

tl;dr

• Recover sample outputs from PRNG
• reverse wrapper function
• find seed from outputs
• get the flag

Challenge Points: 1000
Challenge Solves: 1
Challenge Author: v3ct0r

## Introduction

You are given this challenge file and a service which hosts this.

As you can see that there are 4 options, lets see what they do.

1. It justs encrypt random messages with the elgamal Encryption
2. Encrypts the flag using key and iv derived from the
3. Decrypts the message encrypted in 1.
4. Exits from service

## Writeup

At first look there doesn’t seem any use for the 1st and 3rd option. But we’ll get to that part. First what we need is a few samples of the output generated by the PRNG, thats where the option 1 comes into play. If you look at the function Encryption_Box you will see that we have used the PRNG to generate the random ephemeral key (y). But how do we get it.

The only way to get that is to solve the DLP. Lets try out various attacks. First lets examine the prime. After factoring the order of the group i.e. p-1 you will see that it has many factors. This gives way for us to use pohlig hellman, and soon enough it works. Now lets move on to the next step.

Seems that the actual value is passed inside the wrapped function, i.e. the value of we got by solving DLP is the output of the wrapper function. So lets reverse the function. And by reverse I mean literally reverse, what the function left_right does is that it reverses the bits of its inputs (it may add some bits at the end but input can be easily recovered by ignoring the other bits). The rest is easy. Now that you have got the values what to do now.

The PRNG we used here is a well known random generator called Xoroshiro128+. But it had a vulnerability that you can predict the seed using few outputs. There are few resources available to know more about them. After we get the seed its only a matter of time to get the key with which the flag was encrypted.

Here is the exploit script.

Running this script will give us: inctf{PRNG_n0t_t00_57r0ng_4_y0u}

In case of any query, feedback or suggestion, feel free to comment or reach me out on Twitter!