rkm0959

I participated in N1CTF as a member of Super Guesser. 4th Place :)

We solved all crypto problems, and it was a great collaboration of me and rbtree. 

The explanation will be very brief, because I don't have a lot of free time on my hands :( :(

VSS

The vulnerability lies in the use of "getrandbits" - it's implemented using MT19937. This PRNG is known to be predictable after 624 output values are known. Also, if you try to generate a QR code with a sample flag, we can see that the first few rows of the generated output are all white. With this fact, we can retrieve the first few thousand bits generated, and we can predict the following bits generated by MT19937. Therefore, we can recover the original QR code. This solution (and code itself) is due to rbtree. 

FlagBot

This problem was solved by me, so I can give you a brief look inside my brain.

• You can't really do anything with AES-CBC in this challenge
• You can't really do anything with SHA256 anywhere
• That means that we have to break the DH style shared secret generation
• The secret key is reused every time, so that's the vulnerability
• The curve generation only checks the existence of large primes, so small primes can exist

At this point, the solution was straightforward. For each small prime $p$ that divides the order of the elliptic curve used, we can find the value of the secret key $\pmod{p}$ by using Pohlig-Hellman approach. Combining these with CRT, we can recover $d$ since it is at most $2^{255}$. 

Since we do need to deal with primes of size around $10^{12}$, Baby-Step-Giant-Step is required. Just use Sage.

The below code finds all the shared secrets. The remaining parts of the problem are straightforward.

curve

We struggled greatly on this challenge, despite finding the solution quite immediately. Here's the process.

• $E$ is a large elliptic curve over a prime field, not supersingular
• We select two points $G_1, G_2$ on the curve, and play a sort of Decisional Diffie-Hellman game.
• Let's just fix $G = G_1 = G_2$ and see what we can do!
• If the order of $G$ is small, say $t$ - we can recover $a_0, a_1 \pmod{t}$ easily. 
• Therefore, we can directly calculate $a_0a_1G$ as well!
• Check if this is equal to the third point given. If so, check $b=0$ and otherwise check $b=1$.

• If $b=0$ was chosen, this will give the correct answer with probability 1
• If $b=1$ was chosen, we fail if $c \equiv a_0 a_1 \pmod{t}$, so we succeed with probability $1-1/t$
• We do $30$ rounds, so $t$ shouldn't be too small (we want, say, $t> 50$)
• Obviously we do need to solve the discrete logarithm on a group of order $t$, so we want small $t$

This leads to the following goal.

• Find an elliptic curve that satisfies the server's desired conditions, with the order of the curve having a prime between $50$ and $400$

I think I took about 5 minutes until here, but the journey towards the flag for several reasons.

• First, my initial code used random $p, a, b$, generate the curve, find the order, then check for small primes.
• Seems good right? However, I tried to find $G$ using E.gens()[0] * (Order // small_prime)
• This obviously takes infinite time, and my computer was on the verge of dying because of it
• I realized the problem and replaced it by generating any point with Tonelli-Shanks and multiplying it by Order // small_prime

So I thought I was done here. After sending the parameters, I realized that I was not done here. Why?

• The server calculates the order of the elliptic curve as well
• While order calculation is done in polynomial time, it's still slow with 512 bit curve parameters
• Therefore, the server times out, and I can't solve the problem

So I thought I was done here, in a different meaning. After solving the remaining challs, I tried the following.

• Simply try the curves of the form $y^2 = x^3 + b$.

This worked, as the order calculation was done much faster. The challenge was solved.

The parameter finding and solution finding was done by me, and the programming was done by rbtree.

I learned a lot from solving this problem :) I'm still inexperienced, lots of studying to do... 

BabyProof

The key here is that $x$ is quite small compared to $2^{256}$, and $v$ is selected in $[1, x]$. 

Given the printed parameters, we can directly obtain the value of $c$ as well. We see that $$ cx \equiv v - r \pmod{q}, \quad 1 \le v \le x $$ Since $x$'s bit length is $247$, we get $1 \le v \le 2^{247}$ and can write something like $$ cx \pmod{q} \approx -r + 2^{246} \pmod{q} $$ This is an instance of Hidden Number Problem, so just gather a lot of these information and solve it.

easyRSA?

Looking at the problem, we see that we need to do the following

• Factorize $N$ using the vulnerable random prime generator, and recover the array "linear"
• Solve the instance of LWE by using the fact that secret vector (the flag) is small as well

We first focus on the first part. I actually thought about coppersmith method, but I couldn't get it to work.

I already have an experience in wasting time with coppersmith approach, (sharsable) so I stopped attempting.

rbtree noted that there is a polynomial $f$ with small coefficients, degree 8, and $f(3^{66}) \equiv 0 \pmod{N}$.

This is because for each $p, q$, there's a degree 4 polynomial with small coefficients that vanishes at $3^{66}$ modulo that prime.

If we multiply the two degree 4 polynomials, we arrive at the described polynomial of degree 8.

He then suggested using a lattice to find this polynomial. This was an excellent idea!

Since we want a small-coefficient-linear-combination of $3^{66 \cdot 0}, 3^{66 \cdot 1}, \cdots , 3^{66 \cdot 8}$ that vanishes to zero, we must use scaling, as I did in sharsable. Check the code for technical details. As I do usually, I used Babai's closest vector algorithm. We can expect $f$ to be factorized into two polynomials of degree 4. By calculating each polynomial at $3^{66}$ and taking GCDs, we can retrieve $p, q$. This completes Part 1. 

For Part 2, we need to solve the LWE problem. This is hard in general, but we know that the secret vector is small as well. 

Of course, LWE problem can be modeled as CVP problem, and we use the "secret vector is small" fact here as well.

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.