# Pwn2Win2020 CTF Writeups
- [Omni_Crypto](#omnicrypto)  - Category : Crypto  - Files : [enc.py](Omni_Crypto/enc.py), [output.txt](Omni_Crypto/output.txt)  - Points : 246  - Solves : 32  - solution code : [omni_crypto_solve.sage](Omni_Crypto/omni_crypto_solve.sage)- [Load_qKeys](#lost_qkeys)  - Category : Crypto  - Files : [server-model.py](Lost_qkeys/server-model.py)  - Points : 246  - Solves : 32  - solution code : [lost_qkeys_solve.py](Lost_qkeys/lost_qkeys_solve.py)
---
#  Omni_Crypto challenge writeup [Crypto]
In this challenge, we were given the [enc.py](https://github.com/S3v3ru5/CTF-writeups/blob/master/Pwn2Win2020/Omni_Crypto/enc.py) and [output.txt](https://github.com/S3v3ru5/CTF-writeups/blob/master/Pwn2Win2020/Omni_Crypto/output.txt) files.`enc.py` implements rsa algorithm with primes of 1024 bits generated using the below function.```pythondef getPrimes(size):    half = random.randint(16, size // 2 - 8)    rand = random.randint(8, half - 1)    sizes = [rand, half, size - half - rand]
    while True:        p, q = 0, 0        for s in sizes:            p <<= s            q <<= s            chunk = random.getrandbits(s)            p += chunk             if s == sizes[1]:                chunk = random.getrandbits(s)            q += chunk        p |= 2**(size - 1) | 2**(size - 2) | 1        q |= 2**(size - 1) | 2**(size - 2) | 1        if gmpy2.is_prime(p) and gmpy2.is_prime(q):            return p, q````getPrimes(size)` function first generates three random numbers assume them as `[s1, s2, s3](sizes list in line 4)` with `s1 + s2 + s3 = size` andfew constraints.Then the function generates `primes p and q` such that lower `s3 bits` of `p` & `q` are equal and also upper `s1 bits` of `p` & `q` are equal.Assume, ```p = (pa1 << (s2 + s3)) + (pa2 << s3) + pa3q = (pa1 << (s2 + s3)) + (qa2 << s3) + pa3````pa1, pa2, pa3` are of sizes `s1, s2, s3` bits and upper, middle, lower bits of prime p respectively.`qa2` is same as `pa2` but for prime `q`.
`N` in terms of `pa1, pa2, pa3, qa2` obtained by multiplying above equations is
`N = pa3**2 + ((pa3*qa2) << s3) + ((pa3*pa1) << (s2 + s3)) + ((pa2*pa3) << s3) + ((pa2*qa2) << (2*s3)) + ((pa2*pa1) << (s2 + 2*s3)) + ((pa1*pa3) << (s2 + s3)) + ((pa1*qa2) << (s3 + s2 + s3)) + ((pa1**2) << (2*(s2 + s3)))`
The lower `s3` bits of `N` come from the lower `s3` bits of `pa3**2`.==> `N % 2**s3 = pa3**2 % 2**s3`
so, if we are able to calculate the `square root` of `N % 2**s3 modulo 2**s3`, then we will get the original value of `pa3` as it is less than `2**s3`.[This thread](https://projecteuler.chat/viewtopic.php?t=3506) discuss the algorithm to calculate `square root` modulo `powers of 2`.Discussed algorithm works for the given challenge `N` and we can obtain the value of `pa3`.
For the value of `pa1`, the upper bits of the `N` is approximately equal to `pa1**2`.so, taking the approximate `square root` of `N >> (2*(s2 + s3))` gives the value of `pa1`.
As, we can calculate the values of `pa1` and `pa3`, we can use the `coppersmith attack` to calculate one of the primes.```pythonP.<x> = PolynomialRing(Zmod(N))f = pa1*(2**(s2 + s3)) + x*(2**s3) + pa3f = f.monic()roots = f.small_roots(beta = 0.5)```One problem is that we don't know the values of `s2` and `s3`. so, we have to check all the possible values and factor `N`.
After trying all the possible values for `s2` and `s3`, I could not factor `N` because of a small but bad mistake that I realisedafter trying another approach which only works for half of the cases.
Another approach which doesn't depend on `coppersmith attack` works only if `s2 < s3` is 
As `N` can be written as `N = pa3**2 + ((pa3*qa2) << s3) + ((pa3*pa1) << (s2 + s3)) + ((pa2*pa3) << s3) + ((pa2*qa2) << (2*s3)) + ((pa2*pa1) << (s2 + 2*s3)) + ((pa1*pa3) << (s2 + s3)) + ((pa1*qa2) << (s3 + s2 + s3)) + ((pa1**2) << (2*(s2 + s3)))`
and as we know the values of `pa1` and `pa3`, we can remove all the terms which depend only on `pa1` and `pa3` which leaves us with value equal toremN = ((pa1*qa2 + pa1*pa2) << (s2 + 2*s3)) + ((pa2*qa2) << (2*s3)) + ((pa3*qa2 + pa3*pa2) << s3)	   = ((pa1*(qa2 + pa2)) << (s2 + 2*s3)) + ((pa2*qa2) << (2*s3)) + ((pa3*(qa2 + pa2)) << s3)we can find the `sum` of `qa2` and `pa2` modulo `2**s3` using `remN`.```remN % 2**s3 = pa3*(qa2 + pa2) % 2**s3(qa2 + pa2) % 2**s3 = (remN % 2**s3)*inverse(pa3, 2**s3) % 2**s3```if `s2 < s3` then `(qa2 + pa2) % 2**s3 = qa2 + pa2`.
Now, using the `pa1`, `pa3`, `qa2 + pa2` and `remN`, we can calculate the value of `qa2*pa2`.
And given the sum and product of `pa2` & `qa2` we can calculate the values of `pa2` & `qa2` by finding the roots `quadratic equation` `x**2 + b*x + c` with `b = -(qa2 + pa2)` and `c = qa2*pa2`.
This approach is faster but only works for half of the cases and it doesn't work for the challenge `N`.
I realised my mistake that I did while trying `coppersmith attack` which is : when using `small_roots` method I only specified the `beta` parameter and leave out `X (upper bound of root)` parameter for the method to decide.
So, after trying the `coppersmith attack` with all the parameters, it found the root.
Decrypting the ciphertext gives us the flag,
FLAG :: `Here is the message: CTF-BR{w3_n33d_more_resources_for_th3_0mni_pr0j3ct}\n`
solution code :: [omni_crypto_solve.sage](https://github.com/S3v3ru5/CTF-writeups/blob/master/Pwn2Win2020/Omni_Crypto/omni_crypto_solve.sage)
---
# Lost_qKeys crypto challenge writeup
In this challenge, we were given with [server-model.py](https://github.com/S3v3ru5/CTF-writeups/blob/master/Pwn2Win2020/Lost_qkeys/server-model.py) file and an netcat connection.The `server-model.py` basically constructs a `quantum circuit` based on a `password`(taken from the user), `Key`(generated using  `os.urandom()`) and `flag`.It executes the circuit one time and measures the state of qubits and it gives the measured values to user.`server-model.py` uses [qiskit framework](https://qiskit.org/) to simulate the circuit.
The program flow of the `server-model.py` is quite simple
First it asks for a `password` with a prompt passwd: and thenit passes the `password` to below method
```python    def send_qubits(self, msg, dest):        qbit_config = self.decode(msg)        q = qiskit.QuantumRegister(9*len(qbit_config))        circ = qiskit.QuantumCircuit(q)        for j, c in enumerate(qbit_config):            if c=='1':                circ.x(q[9*j]) circ.cx(q[9*j],q[9*j+3]) circ.cx(q[9*j],q[9*j+6])            circ.h(q[9*j])            circ.h(q[9*j+3])            circ.h(q[9*j+6]) circ.cx(q[9*j],q[9*j+1]) circ.cx(q[9*j],q[9*j+2]) circ.cx(q[9*j+3],q[9*j+4]) circ.cx(q[9*j+3],q[9*j+5]) circ.cx(q[9*j+6],q[9*j+7]) circ.cx(q[9*j+6],q[9*j+8])    return quantum_channel(circ, dest)  ```msg parameter is the `password` in the above method.The `password` is converted to a `bit-string` of `nbits`(padded if necessary).nbits is equal to 8*len(flag) which in our case is 520.The method creates a `Quantum register` with `9*nbits qubits`.It divides all the `qubits` into `groups of size 9` and takes each group of 9 qubits and sets state of `first qubit in the group to the corresponding bit of password` and then applies same operations on every group of `qubits`.Then the method passes control to the following method.```python    def read_qubits(self, circ):        self.received_qubits = circ.qubits        for i in range(0, len(self.received_qubits), 9): circ.cx(self.received_qubits[i], self.received_qubits[i+1]) circ.cx(self.received_qubits[i], self.received_qubits[i+2])            circ.ccx(self.received_qubits[i+1], self.received_qubits[i+2], self.received_qubits[i])            circ.h(self.received_qubits[i]) circ.cx(self.received_qubits[i+3], self.received_qubits[i+4]) circ.cx(self.received_qubits[i+3], self.received_qubits[i+5])            circ.ccx(self.received_qubits[i+4], self.received_qubits[i+5], self.received_qubits[i+3])            circ.h(self.received_qubits[i+3]) circ.cx(self.received_qubits[i+6], self.received_qubits[i+7]) circ.cx(self.received_qubits[i+6], self.received_qubits[i+8])            circ.ccx(self.received_qubits[i+7], self.received_qubits[i+8], self.received_qubits[i+6])            circ.h(self.received_qubits[i+6]) circ.cx(self.received_qubits[i], self.received_qubits[i+3]) circ.cx(self.received_qubits[i], self.received_qubits[i+6])            circ.ccx(self.received_qubits[i+3], self.received_qubits[i+6], self.received_qubits[i])
        circ = self.encrypt_flag(circ)        self.decrypt_flag(circ)```This method also takes each `group of 9 qubits` and does similar operations an each group and passes control to the `encrypt_flag` method.```python    def encrypt_flag(self, circ):        self.qbuffer = qiskit.QuantumRegister(self.nbits)        circ.add_register(self.qbuffer)
        for i, c in enumerate(self.encoded_flag):            if c=='1':                circ.x(self.qbuffer[i])
        for i in range(len(self.key)):            if self.key[i]=='1':                circ.h(self.qbuffer[i])        return circ```This is where `flag` comes into play.The method creates an additional `QuantumRegister` with size `nbits`.In order to understand the solution and the above code we need to have a small understanding of the operations done in all the mentioned functions.
According to [Qiskit docs](https://qiskit.org/documentation/tutorials/circuits/3_summary_of_quantum_operations.html) and [wikipedia page on Quantum gates](https://en.wikipedia.org/wiki/Quantum_logic_gate)```- All the qubits have default state 0 at the time of intialisation in qiskit framework.- circ.h(qi) represents a Hadamard(H) gate which acts on a single qubit and after this operation there's an equal probability to measure the state of the qubit as 0 or 1.- circ.x(qi) represents Pauli-X gate which acts on a single qubit and is quantum equivalent of Classical NOT gate i.e flips the state of qubit.- circ.cx(qc, qi) is a Controlled NOT gate, if the qubit qc results in state 1 when measured then Pauli-X(Classical NOT) gate is applied on the qubit qi.- circ.ch(qc, qi) is a Controlled Hadamard gate, if the qubit qc results in state 1 then Hadamard(H) gate is applied on qubit qi.- circ.ccx(qc1, qc2, qi) represents Toffoli(CCNOT) gate, if the first two qubits qc1 & qc2 are in state 1 then Pauli-X(Classical NOT) gate is applied on the third qubit qi.```Coming back to `encrypt_flag` method, as it created the nbits number of qubits.It assigns each bit of `flag` to `qubit state` i.e if flag bit is 1, then qubit is flipped as qubit is intially in state 0 flipping results in state 1.
After flipping necessary qubits accordingly, it adds the `Key` i.e it iterates over `Key bits`.And if `key bit is 1` then it passes corresponding `flag qubit` into `Hadamard gate` which results in the bit being in state 0 or 1 equally likely. `flag qubits` are not involved in any of the operation if the corresponding `Key bit` is 0.
And this is where the `main flaw` is, ```For an nth flag qubit the probability that corresponding key bit is 1 is 1/2probability that Hadamard gate flips the qubit is 1/2.so, given a nth flag qubit the probability that it flips is (1/2)*(1/2) = 1/4.if we take measurements for a noticable number of times then there will be a bias towards the correct bit.```We can use the above observation to calculate the entire `flag`.
Even though the following method is called after `encrypt_flag` method which adds some operations to the circuit, it `doesn't change the result` much.```python    def decrypt_flag(self, circ):        for i in range(self.nbits): circ.ch(self.received_qubits[9*i], self.qbuffer[i])
        output = qiskit.ClassicalRegister(self.nbits)        circ.add_register(output)        circ.measure(self.qbuffer, output)
        bk = qiskit.Aer.get_backend('qasm_simulator')        job = qiskit.execute(circ, bk, shots=1)        res = job.result()        if not res.success:            raise MemoryError('You should use a real quantum computer...')        res = res.get_counts(circ)        self.res = [self.encode(int(k,2)) for k in res.keys()]```This function adds `Controlled Hadamard gate` to the `flag qubits` whose `control qubits` are taken from the previously created qubits(created based on the user `password`) and measures the state of flag qubits into output Classical Register and gives the output.
The reason that I think this `addition of Controlled Hadamard gates doesn't change` much because it only applies on the `flag qubits` when `control qubit is 1` and if we see the operations(in methods `send_qubits` and `read_qubits`) which result in the control qubits and using description of the gates we can assume that the probability of control qubit being in state 1 is very less after the operations.
solution code :: [lost_qkeys_solve.py](https://github.com/S3v3ru5/CTF-writeups/blob/master/Pwn2Win2020/Lost_qkeys/lost_qkeys_solve.py)
`FLAG :: _#__CTF-BR{_1s_th4t_HoW_u_1mPl3meNt_@_QUantUm_0ne_t1m3_paD_???}_\\` 