# CNS Homework2
### 1. Super cookie
**(1)** It is a web security mechanism that can protect the website against man-in-the-middle-attack and protocol downgrade attacks. It will prevent any communications from being sent over HTTP to the specified domain and will instead send all communications over HTTPS.
**How does it work?**
A server implements an HSTS policy by supplying a header over an HTTPS connection which is `Strict-Transport-Security`. Once this header is returned, the browser will not make an HTTP request to the site no matter how hard you try and instead it’ll use HTTPS protocol.
**(2)** I will give an example of how to contruct a persistent cross-Site identifier (aka. super cookie).
**On the initial web site visit:**
* random number is assigned to the visitor, for example `0x13`(10011 in binary)
* The tracker script then makes subresource requests to a tracker-controlled domain over https, one request per active bit in the tracking identifier.
* https://bit0.example.com
* https://bit1.example.com
* https://bit4.example.com
* The server responds to each HTTPS request with an HSTS response header, which caches the tracking value in the web browser.
* Now we are guaranteed to load the HTTPS version of bit0.example.com, bit1.example.com, and bit4.example.com, even if the load is attempted over HTTP.
**On subsequent website visits:**
* The tracker script loads 5 invisible pixels over **HTTP** that represent the bits in the binary number.
* Since some of those bits (bit0.example.com, bit1.example.com, and bit4.example.com in our example) were loaded with HSTS, they will automatically be redirected to **HTTPS**.
* The tracking server transmits one image when they are requested over **HTTP**, and a different image when requested over **HTTPS**.
* The tracking script recognizes the different images, turns those into zero (HTTP) and one (HTTPS) bits in the number, and your unique binary value is recreated and you are tracked!
**(3)** Observe that tracking sites constructing long URL’s encoding the digits in various levels of the domain name. For example
```
https://a.a.a.a.a.a.a.a.a.a.a.a.a.example.com
https://a.a.a.a.a.a.a.a.a.a.a.a.example.com
https://a.a.a.a.a.a.a.a.a.a.a.example.com
https://a.a.a.a.a.a.a.a.a.a.example.com
https://a.a.a.a.a.a.a.a.a.example.com
etc
```
Or using large number of sibling domain names, for example:
```
https://bit00.example.com
https://bit01.example.com
...etc
https://bit64.example.com
```
Hence we can revised our network stack to only permit HSTS state to be set for the loaded hostname or the Top Level Domain + 1 (TLD+1).
By doing this, tracker can't set the HSTS across large numbers of different bits efficiently.
---
### 2. BGP
**(1)** The attacker might annouce an longer prefix, for example `10.10.220.0/24`. Since route selection always matches the longest prefix, all the traffic to AS 1000 will now be redirected to AS 999.
**(2)**
**(a)** {10.10.220.0/23, {AS 2, AS 1, AS 1000}}
**(b)** As mention above, routing selection always matched the longest prefix, hence the ip prefix of the spurious BGP update should be `10.10.220.0/23` which is one bit longer. But in order to preserve one path to the victim, attacker must prepend AS 2, 1, and 100 to the ASPATH.
For AS 3, 4, and 5, when they receive this BGP update, since they are not in the ASPATH they'll update there routing information that if the destination of packet is under `10.10.220.0/23`, it should be forward to attacker.
For AS 2, 1, and 100, when they receive this BGP update, since thet are in the ASPATH they will NOT update its routing information. Hence preserve the path to victim (AS 1000).
**(c)**
Obviously the advantage is the attacker can intercept most of the traffic (traffic that initial from AS 3, 4 and 5) to the AS 1000
---
### 3. PIN Authetication
There is an vulnerability to man-in-the-middle-attack, the adversary can authenticate with server and client without knowning the share key $K$ and $PIN$
I will give an demonstration of the attack, here is some setup.
Suppose the server ($S$) and client ($C$) share a secret key $K_1, K_2$ and password $PIN$, the adversary ($E$) now want the authenticate with server and client without knowning $K1, K_2$ and $PIN$. Now $C$ want to connect with $S$ and $E$ can intercept all the traffic between them.
$$
S->E:HMAC_{k_1}(RS_1 || PIN_1) \\
S->E:HMAC_{k_1}(RS_2 || PIN_2) \\
E->C:HMAC_{k_1}(RS_1 || PIN_1) RED \\
E->C:HMAC_{k_1}(RS_2 || PIN_2) RED \\
C->E:HMAC_{k_1}(RC_1 || PIN_1) RED \\
C->E:HMAC_{k_1}(RC_2 || PIN_2) RED \\
E->S:HMAC_{k_1}(RC_1 || PIN_1) \\
E->S:HMAC_{k_1}(RC_2 || PIN_2) \\
C->E:E_{k_2} (RC_1) RED \\
E->S:E_{k_2} (RC_1) \\
S->E:E_{k_2} (RS_1) \\
E->C:E_{k_2} (RS_1) RED \\
C->E:E_{k_2} (RC_2) RED \\
E->S:E_{k_2} (RC_1) \\
S->E:E_{k_2} (RS_2) \\
S->C:E_{k_2} (RS_2) RED
$$
Now the adversary successfully autheticate with server and client simultaneously.
---
### 4. Can't beat CBC
**(a)** In this problem we are given a pair of plaintext and ciphertext in hex encoding
```
plaintext = 'QQ Homework is too hard, how2decrypt QQ'
ciphertext = '607ef7554afb5af90ac486cdb221ef2c17517d6d5ecf8272a2e38884d5f4fc1c121f8592a2aa151f3980ae108e8e49ee'
```
and an oracle that can decrypt anything for you. Note that the length of ciphertext are $48$ bytes, $3$ blocks long, we denote as $c_1, c_2, c_3$ respectively.
The vulnerability is that it use the $key$ as $IV$ in AES CBC mode, which means the $key$ and $IV$ are the same.
In order to recover $IV$, we make a fake ciphertext $C' = c_3 || c_2 || c_3$ where $||$ means concatination. When we give $C'$ to the oracle for decryption, it will perform the following operation:
$$P_1 = D(c_3, key) \oplus IV \\
P_2 = D(c_2, key) \oplus c_3 \\
P_3 = D(c_3, key) \oplus c_2$$
Now if we perform $P_1 \oplus P_3 \oplus c_2$, we will recover the $IV$, since
$$
\begin{aligned} P_1 \oplus P_3 \oplus c_2 &= D(c_3, key) \oplus IV \oplus D(c_3, key) \oplus c_2 \oplus c_2 \\
&= IV
\end{aligned}
$$
In this problem $IV$ is the flag we are looking for, hence the flag is **BALSN{IV=KEY=GG}**
---
**(b)** We are given an oracle that will told you the padding of your plaintext after decryption is correct or not. Hence it's obvious that we should perform **padding oracle attack**.
Everytime we connect to the service, we'll get an encrypted flag which is $80$ bytes, $5$ blocks, long and an random $IV$. And we need to hand in $IV$ and ciphertext to oracle for decryption.
The idea of padding oracle is that if we have two ciphertext block $c_0, c_1$ and its corresponding plaintext blocks are $p_0, p_1$, we modify $c_0$ and make use of the oracle to recover $p_1$.
Just gave modified $c_0$ as $IV$ and $c_1$ as ciphertext to padding oracle and start guessing each byte of $p_1$ according to the respond of oracle.
The above method work for every blocks except for first block. If we want to recover first plaintext block we need to modify $IV$ instead of any ciphertext block.
After recover every plaintext block, we get the flag:
**BALSN{1T_15_V3RY_FUN_T0_533_TH3_FL4G_4PP34R_0N3_BY_0N3_R1GHT_XD}**
---
**(c)** In this problems the service will ask for two messages $m_1$ and $m_2$, then generate MAC of $m_1 + flag + m_2$ and encrypt $m_1 + flag + m_2$ with MAC as suffix.
$$digest = HMAC(m_1 + flag + m_2) \\
ciphertext = E(m_1 + flag + m_2 + digest)$$
Note that this service is not using **PKC57** method for padding, it use following method for padding
```
def pad(data, N=16):
last = N - (len(data) % N) - 1
data += os.urandom(last)
data += chr(last)
return data
```
No matter what the content of the padding bytes is, as long as the **last byte** must specify **padding size** which is vulnerable.
I will give an example to show how to recover first block of encrypted flag.
We will let
```
m1 = aaaaaaaaaaaaaaa
m2 = a
```
then ciphertext will contain 8 blocks.
```
1 block = IV
2 block = 'aaaaaaaaaaaaaaa' + F[0][0]
3 block = F[0][1:] + F[1][0]
4 block = F[1][1:] + F[2][0]
5 block = F[2][1:] + F[3][0]
6 block = F[3][1:] + 'a'
7 block = HMAC
8 block = padding block
```
Now we replace 7 block to ffffffffffffffffffffffffffffffff{xx} where {xx} is the byte we need to brute force, and append block 2 to the end of this block chain. Then the ciphertext blocks become
```
1 block = IV
2 block = 'aaaaaaaaaaaaaaa' + F[0][0]
3 block = F[0][1:] + F[1][0]
4 block = F[1][1:] + F[2][0]
5 block = F[2][1:] + F[3][0]
6 block = F[3][1:] + 'a'
7 block = HMAC
8 block = 'ffffffffffffffffffffffffffffffff{xx}'
9 block = 'aaaaaaaaaaaaaaa' + F[0][0]
```
Now number 9 block will be decrypted as padding block, by decryption of AES in CBC mode.
$$\begin{aligned} Pad[-1] &= D(block \space 9, key)[-1] \oplus block \space 8[-1] \\
&= D(block \space 9, key)[-1] \oplus xx\end{aligned}$$
where $Pad$ is the padding block after decryption. What if $Pad[-1] = 31$? If this is the case the server will return authenticate successful because block 8 and 9 will be seen as padding block and will be elinimate after unpad.
Hence we can brute force to find which value of xx will give use authenticate successful, after know the value of xx then we know
$$D(block \space 9, key)[-1] = 31 \oplus xx $$
After knowing this value we can back to the first block of decrytion.
$$\begin{aligned}
P[-1] &= D(block \space 2, key) \oplus IV[-1] \\
&= D(block \space 9, key) \oplus IV[-1] \\
&= 31 \oplus xx \oplus IV[-1]
\end{aligned}$$
where we successfully recover the last byte of 2 block, which is first byte of the flag.
Repeat this procedure we can recover all byte of flag:
**BALSN{N33D_B3TT3R_P4DD1NG_M3TH0D_T0_PR3V3NT_P00DL3_4TT4CK_SSLv3}**
---
### 5. Man-in-The-Middle-Attack
The server has 3 very small passwords, integer from 1 to 20. For each password a **Diffie-Hellman** key exchange is done, however the generator depends on password which is known as SPEKE protocol.
From wiki of SPEKE protocol, it says that the password should be large. Hence the server is vulnerable since it use very small password.
We can establish two connections to server and perform not only **man-in-the-middle attack** but also **reflection attack**.
Suppose two servers, server1 and server2, we make connections with choose two random number $a$ and $b$ respectively. In each round server1 will return $g^a$ and server2 will return $g^b$, now we send $g^a$ to server 2 and $g^b$ to server 1 then both server will have same share key $g^{ab}$.
We recover the password one by one, let's says we want to recover first password (first round). We guess a random password $p'$ and compute the generator $g'$ of DH key exchange with respect to this $p'$ and send this $g$ to both server. Then the server will compute the share keys $g'^a$ and $g'^b$ respectively which they have already send to us. The order round will perform reflection attack as shown above.
After three rounds, we will have two encrypted flag $F_a$ and $F_b$ which are different. Note that they are different because of the first round which result in two different share key, second and third round will yield same shared key as metion above. Now we can compute
$$F_a \oplus g'^a \\
F_b \oplus g'^b$$
If they are the same imply that the password we guess if correct.
Now we can brute force to figure out the password in each round.
After having all three passwords, $p_1, p_2, p_3$. We connect to the server and send $g_1, g_2, g_3$ in each round where $g_1, g_2, g_3$ are generators with respect to $p_1, p_2, p_3$. The server will have three shared key $g_1^a, g_2^a, g_3^a$ which already send to us. After receiving the encrypted flag we can decrypted it to get the flag since we have all the shared key.
**BALSN{Wow_you_are_really_in_the_middle}**
---
### 6. Cloudburst
In this problem we are asked to find the real ip of `the-real-reason-to-not-use-sigkill.csie.org` which use `140.112.31.96` as its proxy. There are many way to expose the origin ip as state in the [paper](https://securitee.org/files/cloudpiercer_ccs2015.pdf). First thing came into my mind is the DNS record, but as the problem state, DNS record has already been updated.
Notice that the web site `https:// the-real-reason-to-not-use-sigkill.csie.org:10130/` is using **HTTPS**, it's reasonable to assume that the origin and this web site is also using the **HTTPS** protocol. So my next goal is to get the certificate of certain ip range and see whether there is a clue to find out the origin ip address.
As state in the problem, origin is locate at CSIE building and listening on port 443. Hence I go to [here](https://www.csie.ntu.edu.tw/~ta221/Page.htm) to get the public ip range of the CSIE building. Basically, the ip range of CSIE is under 140.112.28.0/22 and 140.112.90.0/23.
I use [zmap](https://github.com/zmap/zmap) to scan above subnets on port 443, it will give me the ip addresses that are listen on port 443.
`sudo zmap -p 443 140.112.28.0/22`
`sudo zmap -p 443 140.112.90.0/23`
Next, I collect all of the certificates of these address and print its subject. Unfortunately, all the certificates in subnet 140.112.28.0/22 gave no clue about the origin ip address but the other one 140.112.90.0/23 does. As shown in the below figure, we can guarantee that the origin ip address is **140.112.91.250**.
Type `https://140.112.91.250` in the browser and get the flag:
**BALSN{what_a_C1oudPiercer}**
---
### 7. One-time Wallet
Our goal in this problem is to crack the random number generator `random.getrandbits()`
Briefly, `random.getrandbits` is a **pseudorandom number generator (PRNG)**, implementing with **Mersenne Twister algorithm**. Mersenne Twister algorithm contain $624$ states, each state represent a 32-bits number which means each state can generate a 32-bit random number.
```
tmp = state[idx]
tmp ^= (tmp >> 11)
tmp ^= (tmp << 7) & 0x9d2c5680
tmp ^= (tmp << 15) & 0xefc60000
tmp ^= (tmp >> 18)
randomNumber = tmp
```
When all of the 624 states are used, it will generate new 624 states for next round of random number generation:
```
for i in range(624):
y = (state[i] & 0x80000000) + (state[(i + 1) % 624] & 0x7fffffff)
next = y >> 1
next ^= state[(i + 397) % 624]
if ((y & 1L) == 1L):
next ^= 0x9908b0df
state[i] = next
```
So first thing we need to do is get 624 outputs of `getrandbits` and compute its corresponding states reversly. In this problem the server will give us 100 BitCoin wallet, each wallet contain one address and one password. Address is 3 consecutive output of `getrandbits` and concatenate together, password is 5 consecutive output of `getrandbits` and concatenate together. So each wallet will contain 8 consecutive output of `getrandbits`, which imply when we have 78 wallet we will have all the 624 states.
After having all the 624 states, we can apply above algorithm to recompute the new states and we can predict the output of `getrandbits`. So it's easy to predict the password of 101 wallet and get the flag:
**BALSN{R3tir3_4t_tw3nty}**
---
### 8. TLS Certificate
In this problem we are asked to sign a certificate with Balsn's root certificate and its private key which are all given to us, and the certificate information need to be identical to NTU CSIE certificate but the issuer should be Balsn.
First thing we need to do is to get the certificate from `https://www.csie.ntu.edu.tw`, this step is easy since we can use Firefox browser to export the certificate.
Next, we use the python OpenSSL package to make the certificate request and sign it with Balsn's private key.
Since we have the certificate of CSIE website, we can get the subject of that certificate and assign to my own certificate request. When signing my certificate request, set the issuer to Balsn and use the private key of Balsn to sign it and we are done. Send the created certificate to the server and get the flag:
**BALSN{t1s_ChAiN_0f_7ru5t}**
Sign in with Wallet
Connect another wallet