rkm0959

main.pdf

I participated in SECCON 2020 Online CTF as a member of HangulSarang. We got 1st place :)

Hangul Day is also my birthday, so that's something I guess :D

The competition collided with ACM-ICPC quals, so I had to start solving at like 7PM. (4 hours late)

During that 4 hours, my teammate solved "This is RSA", which is solved using that each byte can be only 0x30 to 0x39. After that, we can compute solutions in $\pmod{2^k}$ and move upwards using recursion. It was the easiest crypto problem in this CTF, (and the solver wasn't me) so I think I don't need to explain further. The other four crypto problems were quite good, challenging, and very enjoyable, so I will describe my thought process as well. Huge thanks to the problem authors for creating these challenges. :D

koharu

The code screams "quadratic residue", and it's similar to bitcrypto in InterKosenCTF. (write-up in this blog)

The only difference is that we are not using large primes, but polynomials in $GF(p)[x]$. This is already weak. 

The reason is that we can easily factorize polynomials in $GF(p)$. We can ask Sage to do it for us :)

Now we can determine whether a given polynomial is a quadratic residue or not. Combine this to get the flag.

urara

Very concise problem. We are given $t, e, n$ and $(m+t)^e \pmod{n}$, and a point is double the point with [$x$-coordinate equal to $m$] [which lies on the elliptic curve $y^2 = x^3 + ax + b$]. I broke that sentence up into pieces because it's pretty long and confusing. So anyways, doing actually elliptic curve stuff seems nearly impossible with the lack of hints we have, and we have a huge hint in $(m+t)^e \pmod{n}$. If we have another polynomial equation about $m$ in $\mathbb{Z}_n[x]$, we can solve this problem using polynomial GCD. (Franklin-Reiter related message attack, like padrsa in InterKosen CTF) Of course, we do have another polynomial equation! Directly using the doubling formula, we have $$ (3m^2 + a)^2 - (2m + Q_x)(4(m^3 + am+b)) \equiv 0 \pmod{n}$$ which is the type of equation we want. Write polynomial GCD, and we can easily find $m$. Again, note that if we encounter a problem while performing standard Euclidean Algorithm, it's because the leading coefficient has a non-trivial GCD with $n$. In this case, we can just factorize $n$ to solve the problem. I was stuck in sharsable for so long before solving this one, so I got some energy from it :D 

For the implementation of polynomial GCD, refer to the write-up of the problem padrsa. 

sharsable

The code looks convoluted, but it can be compressed (without information loss) into the following results:

• $d_1, d_2$ are quite small, around $n^{0.16}$. 
• $e_1d_1 + e_2d_2 \equiv 1 \pmod{\phi(n)}$.
• We know $e_1, e_2, n$, but we can't use common modulus attack due to $\text{gcd}(e_1, e_2) = 11$.

I didn't even realize we could use common modulus attack here, but that was okay since it doesn't give us useful information anyway. The key clearly lies in the small $d_1, d_2$. At first, my thought was headed to the Wiener's Attack, which I think is justifiable because that attack works with small $d$ as well. Of course, it's hard (if not impossible) to use the continued fraction idea directly. After reading up on some generalizations of Wiener's Attacks, I thought this problem was related to the coppersmith attack. I tried weird stuff like 3-variable coppersmith but it all failed pretty badly. That led to me solving this problem the last out of the four I solved. The idea of the last problem helped me :)

We begin by writing (note that this kind of manipulation is done in Wiener's Attack as well) $$e_1 d_1 + e_2 d_2 = k \phi(n) + 1 = k(n-p-q+1) + 1 \equiv -k(p+q-1) + 1 \pmod{n}$$ We may now note that $k$ is probably around $n^{0.16}$ as well, so the RHS is around $-n^{0.66}$ multiplied by some constant. 

Okay, so we want $d_1, d_2$ to be around $n^{0.16}$, and $e_1d_1 + e_2d_2 \pmod{n}$ to be around $-n^{0.66} \cdot c$ for some "reasonable" constant $c$. Let's first decide the range of $c$ we will look for. We can expect $k$ to be $0.4 \cdot n^{0.16}$ to $2 \cdot n^{0.16}$. We can expect $p+q$ to be $2 \cdot n^{0.5}$ to $3/\sqrt{2} \cdot n^{0.5}$. Combining, we can get something like $c \in [0.8, 4]$. Note that I'm using a lot of handwaving. Now we will fix $c$. 

The result? We have goal values for $d_1, d_2, e_1d_1 + e_2d_2 \pmod{n}$. Sounds like CVP to me now. 

Indeed, we can work this as a CVP with the lattice generated by $$ [e_1, 1, 0], \quad [e_2, 0, 1], \quad [n, 0, 0] $$ and making the result vector as close as possible to $$ [-c \cdot n^{0.66}, n^{0.16}, n^{0.16} ] $$ Here's a problem. The scale between the first column and the next two columns are off by $n^{0.5}$. If we run CVP now, it'll probably ignore the $n^{0.16}$ condition in order to get similar values for the first column. At least, that's what I thought :D 

Therefore, we rescale. We will work with the lattice generated by $$  [e_1, n^{0.5}, 0], \quad [e_2, 0, n^{0.5}], \quad [n, 0, 0] $$ and making our result vector as close as possible to $$ [-c \cdot n^{0.66}, n^{0.66}, n^{0.66} ] $$ which sounds more reasonable. If we run the CVP algorithm, (Babai's) we will have our candidate values for $d_1, d_2$. 

If correct, we will have that $e_1d_1 + e_2d_2 - 1$ is a product of $\phi(n)$, so we can finish easily. So, how do we find the right $c$ to use?

Simple. Just try a whole bunch of them. Refer to the code below for details.  

crypto01

@diff (pcw) noted that the order of the elliptic curve must be $(p+1)(q+1)$ since $p \equiv q \equiv 2 \pmod{3}$.

This is a cool fact that I didn't know, but it could be easily guessed by the definition of $d$ in the script. 

So, first things first : is this really a elliptic curve challenge? The answer : probably not?

I thought this for a few reasons - I thought the generation of $e$ was quite convoluted so there should be a weakness.

The elliptic curve part looked too clean to have a vulnerability, and it's not even over a field. Hard to do anything, really. 

Therefore, I decided to take a look at how the parameter generation behaves.

First, I look at the sizes of the values. It 's clear that $y$ is small, so $zbound$ and $z$ are also quite small compared to $x$.

This leads to the following suspicion, is $e = \lfloor (p+1)(q+1)y / x \rfloor$? Generating parameters on our own, we see that this is true with a very high probability. This means that we can ignore $zbound$ and $z$ completely now! This is a good progress indeed :) 

This simplifies a lot of things, and we have a good, clean equation to work with. Start with $$ xe  = (p+1)(q+1)y - r \equiv (p+q+1)y - r\pmod{n}$$ with $r < x \approx n^{0.4}$. With $y \approx n^{0.1}$, we see that $(p+q+1)y - r \approx n^{0.6}$. So $x \approx n^{0.4}$ satisfies $xe \pmod{n} < \approx n^{0.6}$. 

Heuristically speaking, there should be a fairly small number of $x$ that satisfy that condition! Can we find them though?

Turns out the answer is yes. I guess you can do this with lattices, but here's a method I learned from competitive programming. 

In fact, given $L, R, M, A$, we can find the minimum nonnegative integer $x$ such that $L \le Ax \pmod{M} \le R$. 

The method is not long, but I don't want to type it all out, so here's a link (scroll down to the end of the editorial)

Also, a problem using this algorithm appeared in NWRRC, (problem G) set by tourist. 

Since we know $e, n$, we can select some $CUT \approx n^{0.6}$ and find the minimum $x$ such that $1 \le ex \pmod{n} \le CUT$. Of course, we have to be cautious with constants when selecting $CUT$. It's not too hard, since we can always verify our value of $x$ by checking its primality and size. This concludes the recovery of $x$, which is a huge progress again! Now we try to recover $y$. 

To recover $y$, we use basic inequalities. Note the following two inequalities $$ y = \frac{xe+r}{(p+1)(q+1)} \ge \frac{xe}{n + 3 \sqrt{n/2} + 1}$$ $$ y = \frac{xe+r}{(p+1)(q+1)} \le \frac{xe + x-1}{n + 2\sqrt{n} + 1}$$ which gives us decent lower/upper bounds. Turns out that this is also perfect, as the two bounds are actually equal! This recovers $y$. 

With this information, we can now bound $p+q$. Simply use $$ p+q = \frac{xe+r}{y} - 1 \ge \frac{xe}{y} - 1 $$ $$ p+q  = \frac{xe+r}{y} -1 \le \frac{xe+x-1}{y} - 1$$ which gives us a good bound for $p+q$. Now we proceed as we did in l33tcrypt in DownUnderCTF and use quadratic formula to get a good bound for $p$. Note that $p > q$. If we analyze the two bounds, we see that this gives us about 200 MSBs of $p$. Now we are practically done. 

We already know 96 LSBs of $p$ via the hint. This adds up to 296 bits of information, so we only need to determine 216 bits of $p$. This can be easily done with coppersmith method, i.e. Sage's small_roots. This part is very straightforward. Now we calculate $p, q, d$ and eventually the masks. The conversion of masks to the actual flag was done by @ironore15. This concludes the problem :D

Also, maybe you can recover $x, y$ with continued fractions on $e/n$? Maybe. I didn't try it :P

UPD : Okay I tried it and it works easily. Why didn't I think about this lmao... This is a much easier way to solve. :)

Basically, from $e = \lfloor (p+1)(q+1)y / x \rfloor$, we can guess that $$ \frac{e}{n} \approx \frac{e}{(p+1)(q+1)} \approx \frac{y}{x}$$ so $y/x$ is a good approximation of $e/n$. Find all convergents of $e/n$, and find those that have primes as its numerator and denominator. 

This gives us $x, y$, so we can proceed with the coppersmith attack as above. Much easier :)

UPD : The continued fraction solution is indeed the intended sol. I guess it could be proved using the given bounds :)

UPD : So apparently this thing had a name, KMOV cryptosystem. didn't know that :P

오늘 남았던 2문제를 해결하여 올솔브를 했습니다. 2문제 다 쫄아서 못 건드리고 있었는데 펜 굴리니까 생각보다 무난하게 풀리네요 :) 

여기서 접근한 새로운 정보들이 많으니 공부 좀 해야겠습니다. 그래도 올솔하니까 후련하네요 ㅋㅋ 

I participated in TWCTF 2020 as a member of the team D0G$. We got 1st place!

easy hash

I tried to do something but then @yoshiking sensei solved it. :D

sqrt

I had good fun solving this problem, so I'll write my thought process as well. 

This honestly looks like a perfect code, but the key line that left a question mark for me was line 35. 

$ord(m)$ is incredibly small, so maybe we can bypass the entire discrete logarithm?

To think further in this direction, we need some knowledge on $p-1$. I first checked if $q$ was prime - it was not.

Then I checked the factors of $q$ - I could brute force small primes, but I just went to FactorDB. Why not?

I found out that $3, 5, 19$ were factors of $q$, which was quite surprising to me.

I thought StrongPrimes generated a prime of a form $2 \cdot q + 1$ where $q$ is a prime. Oops?

Anyways, since $3 \cdot 5 \cdot 19$ was pretty large, so it seems this should be fine.

Discrete Logarithm calculation is hard, but calculation modulo a small prime is easy by Pohlig-Hellman style thinking.

Can we abuse this? Well, given the signature data we can calculate the logarithm of the $ord(m)$ modulo $3 \cdot 5 \cdot 19$.

So if we precompute all logarithms of 0 to 255 modulo $3 \cdot 5 \cdot 19$, we can find the "candidates" for each letter.

I did this, but found there are multiple solutions. I tried to fix this by working with $5710354319$, which is another prime divisor.

I thought this should also work using sage's BSGS and stuff, but it was way too slow.

I posted my partial result (candidates) on discord and asked for guesswork/recovery, then @yoshiking found the solution.

XOR and shift encryptor

So basically what we have to do is efficiently "advance" the RNG large amount of times. 

The given RNG state transition can be regarded as a linear transformation over the $64^2$ bits in the state.

Therefore, we can model this by matrix multiplication, where the size of the matrix is $64^2$. 

Using binary exponentiation, we can get our random numbers relatively quickly.

I had thought of this but believed this would be way too slow, but @theoldmoon0602 wrote a beautiful code in sage and managed to find the flag. The code took about 30 minutes ~ 1 hour to run, according to the solver. 

The below code, by @theoldmoon0602, derives the key sequence. 

Also, for the write-up written by the actual solver @theoldmoon0602, check here.

circular

Basically, we have to find $x, y$ such that $x^2 + ky^2 \equiv HASH \pmod{n}$. 

We know $k, HASH, n$, but not the factorization of $n$. This seemed to be very difficult. 

First few ideas of mine included the Brahmagupta's Identity and Pell's Equation. 

I tried to work on Pell's Equation + continued fractions, but it failed as well.

After a while, @ironore15 notified us that this scheme has a name - OSS signature.

I was quite surprised because I didn't think this would be an actual scheme in the literature.

Anyways, after a bit of googling I was able to find a paper that describes the attack.

The rest was relatively straightforward implementation. I was glad to see one of my ideas used in the attack.

I played DownUnderCTF as a member of Defenit, and solved all cryptography problems. 

rot-i

The problem seems to imply a variant of rotation cipher. Now, it's reasonable to guess that "Mbz cjzg kv IAJBO" is actually "The flag is DUCTF". We subtract the alphabet order of each text to find that the "amount of rotation" changes by 1 each time. 

I changed all letters into lowercase, cleaned up some parts of the string, and wrote the following code.

babyrsa

The extra information we have here is $s$. Since $n-p-q = \phi(n) - 1$, we see that $s$ is the modular inverse of $557p - 127q$ $\pmod{n}$. Therefore, we may recover $557p-127q \equiv s^{-1} \pmod{n}$ with Extended Euclidean algorithm. Since $557p - 127q$ is between $0$ and $n$, we can just recover $557p-127q$. Since we already know $n = pq$, we can just solve a quadratic equation. I did it with a binary search.

Extra Cool Block Chaining

Let's first consider what the encryption function is actually doing. Given a plaintext $P_1 P_2 \cdots P_n$, we are basically doing $C_i = E_K(P_i) \oplus C_{i-1}$ for each $i$, then XORing the $IV$ to all ciphertexts before returning. In other words, we are just sending $IV \oplus E_K(P_1), IV \oplus E_K(P_1) \oplus E_K(P_2)$, $\cdots , IV \oplus E_K(P_1) \oplus \cdots \oplus E_K(P_n)$. 

Now what we can do is ask for an encryption of a single block, and a decryption of a single block. 

Say we want to find $P_k$. To do so, we need to ask for a decryption of $IV \oplus E_K(P_k)$. How do we find that? 

Note that this is trivial for $k=1$. Assume $k \ge 2$. Now, by XORing the two consecutive results of the output, we can easily get $E_K(P_k)$. Therefore, we need to find a way to get $IV$. This looks like a time for encryption oracle. 

Note that if $P_1 = P_2$, our second output will be $IV \oplus E_K(P_1) \oplus E_K(P_2) = IV$. 

We want to use this to our benefit, but we can only ask for one block! It's okay, because we can abuse the padding. 

By asking for the encryption of b'\x10' * 16, we can make our padded plaintext of the form $P_1 P_1$. 

This enables us to get $IV$, and we can decrypt each block as we want. I did this manually, so code below is not perfect.

ceebc

We are given a signature of an known example message, and we have to forge a signature of a desired message.

The signature is given by $E_{K, IV}^{CBC} (P) || IV$ which is just $E_{K}^{ECB} (P \oplus IV) || IV$.

So we have $IV$, $E_{K}^{ECB}(P_{ex} \oplus IV)$, and $P_{ex}$. We want to forge a signature of $P_{flag}$. 

To do so, calculate $IV'$ such that $P_{ex} \oplus IV = P_{flag} \oplus IV'$. This can be easily done.

Then simply send $P_{K}^{ECB} (P_{ex} \oplus IV) || IV'$ as a signature. It's clear that this works. 

Hex Shift Cipher

It's simple to see that the 'add' function is just XOR. We will brute force the key by backtracking. 

Basically, with the known parts of the plaintext, we have pieces of information like $key(key^{-1}(m_i) \oplus s) = c_i$. 

If $key^{-1}(m_i)$ are known, then we can figure out $key^{-1}(c_i)$ and vice-versa.

If this information is contradictory to the previous assumption of our key, we can stop the backtracking.

If we have no idea on $key^{-1}(m_i)$ and $key^{-1}(c_i)$, we can brute force what their value will be. 

If we have the complete key, it's straightforward to decrypt the given output. Select those that can be cleanly decrypted.

Also, now we can obviously see what the "linear algebra solution" is. Seems like a lot of work to be honest...

My code seems to have a few buggy pieces, but it got the job done so I didn't bother to fix it.

Cosmic Rays

Let's analyze the encryption process first. Given the padded message $P_1 P_2 \cdots P_n$, we see that $C_i = E_K(P_i \oplus C_{i-1})$, and the $i$th output block is $O_i = C_i \oplus P_{i-1}$. Since the key bytes and the latter parts of the output are quite known, we will start by figuring them all out. There are five unknowns in the hex data of the key and the final block (32 hex digits) of the output. We brute-force all $2^{20}$ combinations. How do we verify correctness? Since $C_n = O_n \oplus P_{n-1} = E_K(P_n \oplus C_{n-1})$, we see that $O_{n-1} = C_{n-1} \oplus P_{n-2} = D_K(O_n \oplus P_{n-1}) \oplus P_n \oplus P_{n-2}$. We know partial outputs of $O_{n-1}$, so we compare the known values of $O_{n-1}$ and $D_K(O_n \oplus P_{n-1}) \oplus P_n \oplus P_{n-2}$. Turns out that this is enough to uniquely determine all five unknowns. 

Now that we know all plaintext data, key, and the final block of output, we can use the above formula to completely decide the output value. Now we can work on finding $P_0$ and $C_0$. We may find $C_2 = O_2 \oplus P_1$. Then $C_1 = D_K(C_2) \oplus P_2$, $C_0 = D_K(C_1) \oplus P_1$. Now to find $P_0$, we use $P_0 = O_1 \oplus C_1$. This solves the problem. Unfortunately, my code is a bit dirty. You can still see all the key ideas.