본문 바로가기

CTF

UTCTF - Writeups

I participated in UTCTF as a team Hyp3rFlow and achieved 18th place. Usually, I felt like I was always get along with hard-working team members, but this time - I think I solved enough, so I'm going to post a write-up of problems that I solved. Please understand that grammar can be awkward because it's my first time writing in English.

이번 UTCTF에 팀 Hyp3rFlow로 참가해서 18등을 했습니다. 일반적으로는 팀원들이 잘 해 주어서 좀 묻어가는 느낌이 없지 않아 있었는데 이번에는 그래도 1인분은 한 것 같아서 제가 푼 문제들에 대한 Writeup을 올리려고 합니다. rkm0959님은 이 글을 읽고 계시다면 뒤로가기를 눌러 주세요.

Small P Problems

It's a very simple Diffie-Hellman problem. The number is small, so you can calculate shared secret directly.

진짜 쉬운 디피 헬만 문제입니다. 숫자가 작으니 shared secret은 직접 계산해줘도 됩니다.

utflag{53919}

Illegal Prime

The Illegal Prime refers to a case in which the prime itself contains dangerous information, as shown by the link provided in the problem. Therefore, if you print a given number in bytes, you can see that the suffix is full of NULL bytes except for a last byte. If you delete the suffix, you can get the flag by xor remaining part with ciphertext, noting that the front remaining part is the same length as the given ciphertext.

Illegal Prime은 문제에서 제공되는 링크에서 알 수 있듯이, 소수 자체가 위험한 정보를 담고 있는 경우를 말합니다. 따라서 주어진 소수를 bytes 형식으로 출력해 보면 마지막 한 자리를 제외한 suffix가 NULL bytes로 가득한 것을 알 수 있습니다. 이를 지우면 앞쪽에 남은 부분이 주어진 ciphertext와 길이가 같다는 점에 주목해 둘을 xor해서 플래그를 얻을 수 있습니다.

utflag{pr1m3_cr1m3s*__*!!!}

Prove No Knowledge

The program requires 256 zero-knowledge proofs. If the program was functioning normally, it requires g^r and randomly requires either r or (x+r) mod p-1 to resolve the problem with only 1/2 chance per round. If you repeat this 256 times, the program can verify with a very high probability that the executor knows x or not. In this case, however, the problem that is required is not random. Since the program requires alternating r and (x+r) mod p-1, you can set y as g^r, even if r is unknown, to satisfy g^x(y) * g^r = g^b when b=0.

프로그램은 256번의 영지식 증명(Zero-knowledge Proof)를 요구합니다. 프로그램이 정상적으로 동작했다면 g^r을 요구한 뒤 무작위로 r 또는 (x+r) mod p-1 중 하나를 요구해 라운드 당 1/2 확률로만 문제를 해결할 수 있게 합니다. 이를 256번 반복하면 프로그램은 실행자가 x를 알고 있는지 그렇지 않은지를 매우 높은 확률로 검증할 수 있습니다. 그러나 이 경우에는 요구하는 문제가 무작위가 아닙니다. 프로그램은 번갈아가면서 r과 (x+r) mod p-1을 요구하기 때문에 r을 모르더라도 제공되는 y의 잉여역수를 g^r로 둠으로서 b=0 일때 g^x(y) * g^r = g^b를 만족하도록 할 수 있습니다.

utflag{questions_not_random}

Sleeves

Nothing-up-my-sleeve number is written in the description, and the number is also small. Assuming that the backdoor is hidden in the Dual EC DRBG provided as the NSA did, using a little bit of guessing and background knowledge, you can also find P = Q * 173 as the discrete_log implementation on the sage. This RNG does not simply return the hash value of the actual state made using Q, but removes the next 1 byte, so you only need to backtrack that part to find the correct flag.

Nothing-up-my-sleeve number를 쓰고 있다고 디스크립션에 나와 있고, 숫자도 작게 주었다고 했습니다. 약간의 게싱과 배경 지식을 이용해 NSA가 했던 대로 제공된 Dual EC DRBG에 백도어가 숨겨져 있을 것이라 가정하면, sage의 discrete_log 구현체로도 P = Q * 173임을 찾을 수 있습니다. 이 RNG는 실제 만들어진 state를 Q를 이용해 해시한 값을 단순히 반환하는 게 아니라 뒤 1바이트를 없애서 제공하므로 그 부분만 백트래킹해서 올바른 플래그가 나오는 것을 찾으면 됩니다.

utflag{numbers_up_my_sl33v3_l0l}

Matrices

It's a problem of using the structure of the very unfamiliar group-based-cryptography Anshel–Anshel–Goldfeld key exchange. The problem is that a1 and a2 are very small to make a and a bar, so it seems that it is impossible to make a bar with a few operations. This is actually true. It should be noted here that the inverse of a1 and a2 are both themselves. After finding this fact, you can see that a1 and a2 must not appear in a series in A's product sequence. Therefore, we can guess that a2^t1 * ((a1 * a2) ^i) * a1^t2 (0=t1,t2=1) is A, and by binary searching manually, we can find out that t1=t2=0 and i = 313. In fact, when calculating K, the inverse of a1 and a2 is themselves, so you don't have to care if eps_1 and eps_2 are positive or negative, so you can just use b bar. If you calculate all of them and add them up, the flag will come out.

굉장히 생소한 군론 암호 Anshel–Anshel–Goldfeld key exchange의 구조를 이용하는 문제입니다. 문제가 되는 점은, a과 a bar을 주는데 a1과 a2가 매우 작아서 도저히 몇 번의 연산으로는 a bar을 만들 수 없을 것처럼 보인다는 점입니다. 이는 실제로 사실입니다. 여기서 주목해야 할 점은, a1와 a2의 inverse가 둘 다 자기 자신이라는 점입니다. 이 사실을 찾고 나면 A의 product sequence에서 a1과 a2는 반드시 2개가 연속으로 나오면 안 된다는 사실을 알 수 있습니다. 따라서 a2^t1 * ((a1 * a2) ^ i) * a1^t2 (0<=t1,t2<=1) 꼴로 A가 나온다는 사실을 추측해볼 수 있고, 손으로 이분탐색하면 t1=t2=0이고 i = 313이라는 사실을 알 수 있습니다. 실제로 K를 계산할 때는 a1과 a2의 inverse가 자기 자신이므로 eps_1과 eps_2가 양수인지 음수인지는 별로 개의치 않아도 되고, 그래서 그냥 b bar을 그대로 사용해도 됩니다. 모두 계산해서 더하면 플래그가 나옵니다.

utflag{5091516004081093828853602728090002831320924432285723/470309961960219268643390156023504640000}

Farmers Only

The problem gives you some strange text file without explanation. The description told you to HMAC the <bytes of sequence # || bytes of bit>, so let's do what problem said. Since the output value in the text file is 16 bytes, the hash function used is likely MD5, which is true. You must have a key to perform HMAC. The problem gives a file named dh-for-hmac, which is small enough to calculate the shared secret directly. By implementing HMAC (I found out after the competition that the library existed), the key is shared secret, and the message is calculated for each sequence number as told, and only one of the two bits given is correct. Since the total number of sequences is a multiple of 8, you can encode them in bytes.

뭔가 이상한 텍스트 파일을 설명 없이 던져 줍니다. <bytes of sequence # || bytes of bit> 을 HMAC하라고 했으니 하라는 대로 해 봅시다. 텍스트 파일에서 준 출력값이 16바이트이니 사용한 해시 함수는 MD5일 확률이 높고, 실제로 그렇습니다. HMAC을 하려면 key가 있어야 합니다. 문제에서 dh-for-hmac이라는 파일을 주는데, 크기가 작으니 직접 shared secret을 계산할 수 있습니다. 직접 HMAC을 구현해서(라이브러리가 있는 것을 대회 끝나고 알았습니다) key는 shared secret로, 메세지는 하라는 대로 각 sequence 번호마다 계산해보면 주어지는 비트 두 개 중 하나만 맞음을 알 수 있습니다. 그 후 sequence의 총 개수가 8의 배수이므로 바이트로 인코딩하면 됩니다.

utflag{cream_of_the_crop_29074}

Virtual Machine Monitor UWU

Few people solved this problem, and I feel good to be one of them. The first time you see a problem, you're embarrassed by literally no information is given(although additional information is given as a hint, it doesn't really help you solve it). First of all, there seems to be not much information to get by watching target.csv, so let's try to get information by opening lab.csv. The order of the operators does not seem to be very meaningful because the proportion of the operators used is almost constant, but you can separate them by operator and then try to find something in common. There's nothing in common that you can see directly, but if you use tools like Excel to color the numbers moderately, you can see too clearly that they are associated with vectors by each operator (see picture below). Using this, let's make vectors representing each operator by averaging vectors. Then, by comparing each vector in target.csv to the best vectors (I calculated it as the sum of the absolute differences), you can solve the problem with a simple algorithmic inverse operation since operators shown as p d / m p d.

이 문제를 푼 사람이 얼마 없었는데, 그 중 하나에 끼게 되어 기분이 좋습니다. 문제를 처음 보면 정말 아무것도 없는 정보에 당황하게 됩니다(힌트로 추가 정보가 주어지긴 했지만, 문제를 해결하는 데는 별로 도움이 안 됩니다). 일단 target.csv를 보고 얻을 수 있는 정보는 별로 없어 보이므로 lab.csv를 열어 정보를 얻으려고 노력해봅시다. 사용한 연산자의 비율이 거의 일정하므로 연산자의 순서가 별로 의미있는 것 같지는 않지만, 연산자 별로 분리한 다음 공통점을 찾으려고 노력해볼 수는 있습니다. 직접적으로 보이는 공통점은 없지만 엑셀 같은 툴을 이용해서 수에 적당히 색을 칠해보면, 너무 명확하게 연산자별로 벡터에 연관성이 있는 것을 알 수 있습니다(아래 사진 참조). 이를 이용해 각 연산자별로 벡터의 평균을 내서 각 연산자를 대표하는 벡터를 만듭시다. 그 후 target.csv의 각 벡터를 모범 벡터들과 비교해(저는 절댓값 차의 합으로 계산했습니다) 연산으로 변환하면, 연산이 p d / m p d 중 하나인 꼴로 나타나므로 간단한 알고리즘 역연산을 통해 문제를 해결할 수 있습니다.

100101010011101000100010111101001001100001101001010010001011011111