# Halftimepad
## problem overview

For the problem, we were given a [URL](https://halftimepad.roboepics.com) (which doesn't work now). and upon visiting the given URL every time you were served a random 372 characters long base64 encoded string. like the one below:

```
FsRyye6r+qsximg9d3NtqkjZXZvh6rXXrHSXjNejOYYLhdgxF6260opAp8E3lxYdzDqLd87uur+rMc8uPXt3Z6dV1yOH4PDq16xzl4CSsTaYW5ydcAvu69qAGfOQPYxdGYI33zCiraDxrTHLejwwHGurSZJ3hvqjs4XlYduMkPB4kx6b0nIT+vXf1A6n3zqQUyOTKsJzzb6u+5Ury2h+ZzhrqxqEP47k86mYmirowKitUsVVx9x/A7zi3pAT84Y9mhYIzX7Icca6pvG/Jop6J3dlI7pejyPP6KOqnrFz24jXsjGfW4TSYwKyhNSPQLrSO4tfEsl+wmrb7qrxpTbNZm4USSmJVJgzz8X2pZzvWL2zqI8HtQ==
```
And also a link to the leaked server-side code that is responsible for the gibberish we are given.

Server-side code is :
```go
package main

import (
"crypto/rand"
"encoding/base64"
)

var (
plain []byte
)

func HalfTimePath() []byte {
l := randInt(20, 100)
key := make([]byte, l)
_, err := rand.Read(key)
if err != nil {
panic(err)
}

cycle := make([]byte, len(plain))
for i := range cycle {
cycle[i] = key[i%l]
}

cipher := make([]byte, len(plain))
for i := range cipher {
cipher[i] = cycle[i] ^ plain[i]
}

b64 := base64.StdEncoding.EncodeToString(cipher)
return []byte(b64)
}

func randInt(a, b int) int {
buf := make([]byte, 1)
_, err := rand.Read(buf)
if err != nil {
panic(err)
}
return int(buf[0])%(b-a+1) + a
}
```
We also know that the plain text includes the string `xeroctf{`
note: I'm also providing 2500 of the server responses for anybody who is interested to solve the problem for themselves. [responses.json](https://drive.google.com/file/d/1YfAeIADFnYTfzdfw1N9HWXBhwYR9QhTe/view?usp=sharing)

## Solution
### Concepts
for the starter, let's understand what the server code does.

1. It takes a plain text named plain
2. Creates a random key with a random length between 20 to 100 bytes
3. Cycles through plain and key XOR ing them (repeating the key when needed) to create cipher
4. Returns the byte array cipher

By decoding one of the responses we can see that it is a 277 length long byte array. so in another word, we can rewrite the plain and an example key length 20 as:

plain = P1 P2 P3 ... P277
key20 = K1 K2 .... K20

and what we have right now is:

cipher = C1 C2 C3 ... C277
which is :
C1 = P1 ⊕ K1
C2 = P2 ⊕ K2
...
C21 = P21 ⊕ K1
and so on.


The big idea to realize is if we know a given cipher is XORed by a key with a length of 20, we can also reach the following conclusion:
C1 ⊕ C21 = (P1 ⊕ K1) ⊕ (P21 ⊕ K1) = (P1 ⊕ P21) ⊕(K1 ⊕ K1) = P1 ⊕ P21
The important thing about `C1 ⊕ C21 = P1 ⊕ P21` is the fact that it is independent of the key, so it is a constant throughout all the ciphers with a key length of 20
This property is useful for two things:
1. To find the key length of a given cipher.
2. Getting rid of the randomness in cipher by removing keys.

The first part is quite trivial, if we have a large number of ciphers we can just loop through them and find a pair that produces the same xor value in a specific interval, then We know the key length for both of the cipher are that interval.
The second part is a little bit harder. It consists of the following steps.
1. Find two ciphers with adjacent key lengths, like lengths L and L+1
2. Create D = D1 D2 ... D276 such that Di = Ci ⊕ Ci+1 using two above-mentioned ciphers
3. Calculate for every pair of adjacent characters in "xeroctf{" their xor and name it X.
4. Search for X in D
5. After finding where the 'x' of "xeroctf" in the entirety of plain text (or P for short) is, fill in the rest of the characters by the formula shown bellow

```
Ci = Di ⊕ Ci+1
or
Ci = Di-1 ⊕ Ci-1
```

It is also quite easy to create D from the previous conclusion, `C1 ⊕ C(L+1) =P1 ⊕ P(L+1)` for a key with a length of L
by using ciphers with a key length of L, we can have `P2 ⊕ P(L+2)`, and with length, L+1 we have `P1 ⊕ P(L+2)`
taking the XOR of these two we are left with `P1 ⊕ P2`, we can repeat the process for the rest of the cipher and achieve sequence D

### Implementation
First, let's make a whole lot of requests to the server and save the responses in python pickle format to use later
p.s : The only reason I'm using pickle is the convince of not having to convert a list into a string and then do it in reverse

**get_responses.py**
```
from concurrent.futures import ThreadPoolExecutor
import requests
import pickle

def get_resoponse():
r=requests.get("https://halftimepad.roboepics.com")
return r.text

with ThreadPoolExecutor() as executer:
responses=[executer.submit(get_resoponse) for _ in range(1000)]

with open("responses.p","rb") as f:
old_responses=pickle.load(f)

responses=[r.result() for r in responses]
responses=old_responses+responses
with open("responses.p","wb") as f:
pickle.dump(responses,f)
```
The only third-party library used is requests, which is an easier way of making HTTP requests using python, also I'm using concurrent.futures to make requests concurrently, to make it take less time.

In the second step, we loop through all the ciphers to find their key length. for some strange reason there were no ciphers with lengths 20 to 33, and only keys with lengths 51 and up existed consecutively in the responses I captured, so, in the end, I just kept the ones with length 51 and above, although only saving ciphers with length 51 and 52 would have sufficed, considering that we are only going to use those.

**distance.py**
```
import base64
import pickle

with open("responses.p","rb") as f:
responses=pickle.load(f)

all_distances={i:[] for i in range(20,101)}

all_ciphers=[]
for response in responses:
cipher=base64.standard_b64decode(response)
all_ciphers.append(cipher)

print(len(all_ciphers))

# finding the key length for all ciphers #
for i in range(len(all_ciphers)):
found=False
for j in range(len(all_ciphers)):
if i!=j:
cipher1=all_ciphers[i]
cipher2=all_ciphers[j]
for k in range(20,101):
found2=True
for l in range(len(cipher1)-k):
found2=found2 and ((cipher1[l]^cipher1[l+k]) == (cipher2[l]^cipher2[l+k]))
if not found2:break
if found2:
all_distances[k].append(cipher1)
found=True
break
if found:break
##########################################

single_distances={i:all_distances[i][0] for i in range(51,101)}
for k in all_distances.items():
print("key length",k[0],f"has {len(k[1])} entry",)

with open("distance.p","wb") as f:
pickle.dump(single_distances,f)
```

The only thing remaining is to find the plain text.
**plain.py**
```
import pickle

with open("distance.p","rb") as f:
distance:dict=pickle.load(f)

cipher51=distance[51]
cipher52=distance[52]

search="xeroctf"
pattern=[]

# making the xor fo 'xeroctf' to search in
for i in range(len(search)-1):
pattern.append(ord(search[i]) ^ ord(search[i+1]))

# it is the same sequence as D in the concepts part
massage_transition_xor=[None]*276

# calculating D52 to D276
for i in range(225):
a=cipher51[i]^cipher51[i+51]
b=cipher52[i]^cipher52[i+52]
c=a^b
massage_transition_xor[i+51]=c

# calculating D1 to D51
for i in range(51):
a=cipher52[i]^cipher52[i+52]
b=cipher51[i+1]^cipher51[i+52]
c=a^b
massage_transition_xor[i]=c

# searching 'xeroctf' trough D
for ind,val in enumerate(massage_transition_xor[:-6]):
if massage_transition_xor[ind:ind+6]==pattern:
index=ind
break

# massage is going to end up being the plain text.
massage=[None]*277
massage[index]="x"

##### finding Plain text #####
for i in range(index,276):
massage[i+1]=chr(ord(massage[i])^massage_transition_xor[i])

for i in range(index,0,-1):
massage[i-1]=chr(ord(massage[i])^massage_transition_xor[i-1])
##############################

print("".join(massage))
```
And in the end, we are treated with the following answer:
> Hola dear friends.
> this is a sample p14in t3xt and if u are readin this, it means u already broke it.
> congrats.
> here is ur flag xeroctf{d0nt-use_1timepad_haf1y.he!shampoo_-\_-\_}
> ...and lets try to continue this text a little bit more.
> ok i think its enough!
> _*Good Luck*_
> ^___^