# 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 :```gopackage 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### Conceptsfor the starter, let's understand what the server code does.
1. It takes a plain text named plain2. Creates a random key with a random length between 20 to 100 bytes3. Cycles through plain and key XOR ing them (repeating the key when needed) to create cipher4. 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+12. Create D = D1 D2 ... D276 such that Di = Ci ⊕ Ci+1 using two above-mentioned ciphers3. Calculate for every pair of adjacent characters in "xeroctf{" their xor and name it X.4. Search for X in D5. 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+1orCi = 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  
### ImplementationFirst, 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 ThreadPoolExecutorimport requestsimport 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+responseswith 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 base64import 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 D276for 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 D51for 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 Dfor 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]*277massage[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*_  > ^___^