rkm0959

오늘 남았던 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.

impECCable

So we have to forge a signature. Let's try that by finding the private key $d$. 

Let's take a look at the signature scheme. $x$, while unknown, is always fixed for each signature.

$h$ is a hash of the message, so we know this value too. We are also given $r_1, r_2, s$ as a result of the signature.

So let's take a look at the last equation $s \equiv k_1^{-1} \cdot (hr_1 - dr_2) \pmod{n}$. 

We already know $r_1, r_2, s, h$, so the unknowns are $k_1$ and $d$. Note that $d$ is also always fixed.

Also, note that $k_1 = small \cdot 2^{25} + x$, where $small$ is around $2^{340}$, far less than $n$.

Taking this into account, we can rewrite our equation as follows: $$ k_1 s \equiv hr_1 - dr_2 \pmod{n}$$ $$ (small \cdot 2^{25} + x) s \equiv hr_1 - dr_2 \pmod{n}$$ $$ - 2^{-25}s^{-1} r_2 d + 2^{-25}s^{-1} hr_1 \equiv small + x \cdot 2^{-25} \pmod{n}$$ This starts to look like a hidden number problem! But the $x$ variable seems like a problem. 

It doesn't matter, since there are 10 such equations, and we can subtract two of them to get 9 (or more?) equations without $x$. 

Now it resolves into solving $A_i x + B_i \equiv small \pmod{n}$ for some known $A_i, B_i$. I'm sure there are many ways to solve this, but the method I enjoy is to use LLL + Babai's Closest Vector Algorithm. Check the implementation below. For details, ask in comments :)

LSB || MSB Calculation Game

This is yet another LCG breaking with lattices :) Basically we are given 20 LSB and 20 MSB of each number.

We can such number as $2^{180} \cdot a_i + 2^{20} \cdot small + b_i$, where $a_i, b_i$ are known and $small$ is around $2^{160}$. 

We know $a$, but we do not know $c$. Denote the 0th number as $x$. Then our next numbers will be $ax+c$, $a^2x+(a+1)c$, $\cdots$ $, a^n x + (a^{n-1} + \cdots + 1)c$. Therefore, our goal here is to solve the set of equations $$ a^k x + (a^{k-1} + \cdots + 1) c \equiv 2^{180} a_k + 2^{20} \cdot small + b_k \pmod{m} $$ $$ 2^{-20} a^k x + 2^{-20}(a^{k-1} + \cdots + 1) c - 2^{-20}(2^{180} a_k + b_k) \equiv small \pmod{m}$$ for each $k$. This is yet another hidden number problem, so we can set up a similar procedure as the above problem. However, the bounds are kinda tight, so we have to optimize a little bit. Refer to the following code, and leave comments if there are parts you don't understand. 

l337crypt

We assume that $p<q$ in the following analysis. It's easy to see that it doesn't matter.

First, the obvious part. Since $x$ is a quadratic non-residue modulo $p$ and $q$, we easily see that the appended value in the ciphertext is a quadratic residue modulo $n$ if and only if $b=1$. This can be determined with legendre symbols if we know the factorization of $n$.

The only hint here is the bounds on $D(\sqrt{p} + \sqrt{q})$. With this bound, we can easily manipulate the inequalities to get a bound on $p+q$, so eventually a bound on $q$ using quadratic equations and the knowledge of $n$.

Now this is a good time to use coppersmith's attack. Assume that we derived $L \le q \le R$. 

Set $f(x) = x + L$, set a bound $X = R - L$, then perform sage's small_roots() algorithm.

However, like rbtree wrote in the coppersmith attack tutorial (Korean, check the blog) we need to carefully select $\beta$ and $\epsilon$. 

We are working with $q$, so $\beta = 0.5$ is fine. Doing some calculations, we see that $n$ is around 2674 bits and $R-L$ is around 600 bits. 

We do some math and find $\epsilon = 0.02$ to be sufficient. This provides a slow, yet guaranteed solution in sage. Full code is below. 

참가팀들 중 2번째로 올솔브를 찍어서 해피엔딩으로 끝냈다. 나는 Crypto 문제를 맡았고 결과적으로 5문제를 풀었다.

Ciphertexts

$n_1, n_2$를 알고 있으니 $r$을 얻을 수 있다. $m^{e_2} \pmod{r}$도 알고 있으니 여기서 $m \pmod{r}$을 알 수 있다.

또한, $m^{e_1} \pmod{n_1}$과 $m^{e_2} \pmod{n_1}$을 알고 있으니, $e_1d_1 + e_2d_2 = 1$인 $d_1, d_2$를 찾아서 $m \pmod{n_1}$도 구할 수 있다. 

이제 중국인의 나머지 정리로 두 정보를 합치면 flag를 얻는다. 수식 잘 가지고 노는 문제 :)

No Pressure

사실 거의 비슷한 문제가 CryptoHack에 있어서 풀이를 쓰기가 조금 애매하긴 하다 ㅋㅋ

문제 이름에서도 나오듯이 compression이 적용되었다는 것을 활용하는 문제이다. 

대충 직관적으로 넣어준 메시지와 flag의 공통 prefix가 크다면 압축이 더 많이 되어 ciphertext의 길이가 작다는 것이다.

flag가 'KosenCTF{' 으로 시작된다는 것은 알고 있으니, 여기에 문자를 하나씩 추가해보며 작은 ciphertext를 찾는 것을 반복하면 된다.

BitCrypto

뭔가 길게 생겼는데 코드부터 대충 해석해보자.

• KeyGen: 소수 $p, q$를 고르고 $n = pq$라 한자. $z$는 $p, q$ 모두에 대해 이차비잉여이다.
• 이 과정에서 public key는 $n, z$이며, private key는 $p, q$이다.
• Encryption: 메시지를 이진법으로 쓰고 $0$을 위해서는 이차잉여, $1$을 위해서는 이차비잉여를 추가한다.
• Decryption: 르장드르 기호를 직접 계산하여 주어진 값에서 $0$, $1$을 복원한다.
• 목표: 플래그 내놓으라는 저 문장이 복호화 결과가 되도록하는 암호문을 만들라는 것이다.
• 단, 암호문의 각 정수는 모두 서로 달라야 하며, 음수면 안된다.
• 쿼리를 날릴 수도 있는데 문제를 날로 먹을 수는 없고 쿼리의 길이에도 제한이 있다.

이러면 문제가 풀렸다. 사실 encryption을 못하는 이유는 그냥 우리가 $n$도 모르고 $z$도 몰라서다.

그런데 애초에 $n, z$을 몰라도 $\pmod{n}$에 대한 이차잉여/비이차잉여를 만드는 것은 쉽다. 

• 이차잉여: 그냥 제곱수를 하나 보내주면 된다.
• 비이차잉여: 정수 하나를 잡고 비이차잉여라고 기도하자. 이 값에 제곱수를 곱하면 된다.
• 비이차잉여를 뽑을 확률은 든든하게 높으니까 별로 기도하지 않아도 된다.

PadRSA

뭔가 패딩이 있고 정신이 나갈 것 같다. 우선 주어진 코드부터 분석해보자.

• $e$를 고른 뒤, flag의 ciphertext를 얻거나 임의의 메시지에 대한 ciphertext를 얻을 수 있다.
• 하지만 한 번 사용한 $e$의 값은 다시 사용할 수가 없다.
• 랜덤한 패딩처럼 생긴 뭔가를 쓰는데 사실 nonce의 값을 대놓고 알려줬다.
• nonce 값을 안다는 것은 $r$을 구하기만 하면 그 뒤의 $r$ 값을 싹 다 구할 수 있다는 것이다.
• $r$이 8 바이트인데 8 비트라고 생각해서 브루트포스하면 되는 줄 알았다 ㅋㅋ

$r$을 구해보자. 사실 $r$이 64 비트라는 점은 꽤 치명적인데, $r^3 < n$을 강제하기 때문이다.

그러니까 사실 빈 메시지와 $e=3$을 보내고 암호화 하라고 부탁하면 얘가 알아서 $r$을 갖다 바친다.

이제 $r$을 알았으니 문제를 풀 수 있다. $e=4, 5, 6, 7$에 대해서 flag의 암호문을 달라고 하자.

우리는 각 암호화 과정에서 사용된 $r, nonce$의 값을 전부 알고 있다. 그러니 우리가 얻은 정보는 사실상 $$ ( (r[0]|nonce) \cdot 2^{l(x) + 64} + 2^{64} \cdot x + r)^e \equiv c \pmod{n}$$ 형태로 쓸 수 있다. 여기서 $l(x)$는 flag의 길이이며, $x$는 flag 자체이다. 이는 결국 $x$가 여러 차수 낮은 $\mathbb{Z}_n$ 위의 다항식의 공통근임을 의미한다.

그러니 저 다항식들의 GCD를 구하면 된다. $l(x)$의 값을 모르지만 이 정도는 brute-force가 가능하다.

Sage에서 $\mathbb{Z}_n$ 위 다항식의 GCD를 지원하지 않는 것 같은데, 그냥 직접 구현하면 된다.

예전에 쓴 RSA 논문리딩에서 언급했듯이, 유클리드 호제법 과정이 망한다면 그때 $n$의 약수를 하나 얻을 수 있고, 이 경우에는 문제가 바로 풀린다.

첫 부분은 Python으로, 두 번째 부분은 Sage로 작성하였다.

pwntools를 살면서 처음 써봐서 통신 부분 코드가 지나치게 더럽고, 그래서 여기서는 생략했다.

Part 1 : $r$ 값 복원하고 $e=4,5,6,7$에 대한 flag의 ciphertext 얻기

아래 코드에서 kthp는 그냥 이분탐색으로 $k$th root를 구하는 코드이다.