myria's place

조금 늦게 올리게되는 MeePwnCTF 2018 Qual에 나왔던 Old School이란 문제이다.

RSA에 익숙해졌다고 생각했는데, 당시 전혀 접근하지 못한 문제였는데; CTF가 끝나고 다른 팀의 Writeup을 보고 공부하였으나

결국 직접 소스코드를 짜보진 못하고 개념만 정리해서 블로그에 올렸었다.. (그것도 몇줄안되지만)

다시 한번 보자면, 이 문제는 Fermat's factorization attack에 관한 문제이다.

이 공격의 요점은 이렇다. 

N = p * q 인 N이 주어질때, p/q가 1에 근사하다면 Fermat's factorization으로 공격하여 p, q 값을 구할 수 있다.

내가 이 Plot Twist 문제의 롸업을 안올렸다니...

오랜만에 MT19937 Mersenne Twister RNG 에 관해서 다시 접하게되어서 저번에 noxCTF에 나왔던 관련 문제 롸업이나 보자! 하고 왔는데

내가 안올려놨었다 ㅡㅡ;;

나름 문제풀려고 고민고민하다가 검색을 통해서 관련 개념을 알게되서 푼 문제라서 롸업 올려놧을줄 알았는데;;

어찌됫든 기억난 김에 이렇게 써본다.

문제는 아래와 같은 파일이 하나 주어진다.

서버에 접속하면 키를 입력해달라고 하고, 올바른 키를 입력하면 플래그를 뿌려준다.

잘못된 키를 입력하면 틀렸다면서 방금 쓰인 암호화 key를 출력해주고, key는 새로 설정된다. 

여기서 r = random.Random()가 쓰이고 아래 함수를 통해 key를 획득하게 된다.

Python의 random은 메르센 트위스터로 되어있어, 624개의 난수만 뽑아낸다면 다음 난수를 예측할 수 있다.

그러므로 624번 틀려서 key값을 알아내어 다음 값을 알아내는 것이 가능하다.

여기서 Mersenne Twister Crack 소스를 짜면 아주 멋지겠지만... 이미 구현되어있는것들이 많으니.. 그것들을 가져와 사용하겠다.

https://github.com/tna0y/Python-random-module-cracker

설명도 아주 잘되어있다.

그냥 적혀있는대로 쓰면된다.

아래는 필자가 작성한 공격코드이다.

이 CTF에서 XOR 암호가 2개 나왔는데, 하나는 키 길이가 주어졌다. (키길이는 9였다)

암호문이 충분히 길었기에 alphabet scoring 방식으로 풀었는데...

나머지 하나가 풀기에 상당히 까다롭게 나왔다.

secret 파일과 flag 파일, 그리고 이를 암호화한 python 소스코드가 주어진다.

secret_plaintext 파일과 flag_plaintext 파일을 읽어 둘 중 긴 길이만큼 랜덤한 key를 만들어내고, 이와 xor하여 secret과 flag파일을 만들어낸다.

언듯보기에는 XOR암호가 OTP에 쓰여 깰 수 있을 것 같지않다.

하지만 동일한 XOR키스트림을 두 파일에 썻기때문에

ciphertext1 = key ^ flag ciphertext2 = key ^ secret

ciphertext2 ^ ciphertext1 = key ^ secret ^ key ^ flag = secret ^ flag

위 공식이 성립한다. 즉 secret ^ flag 를 획득 할 수 있다. 그리고 우리는 flag 포맷을 알고있고, 그 포맷이 TUCTF{ 로 구성되어있다는 것을 알고있다.

그러므로 위 secret ^ flag에서 TUCTF{ 가 들어갈 부분과 secret부분을 얻을 수 있을것이다...

물론 여기서부터는 거의 secret과 flag의 추측을 통해서 문제풀이가 이루어진다..

이에 적절한 파이썬 스크립트가 있어서 사용해보았다.

cribdrag 라고 DEF CON 21에서 발표된 예측 가능한 키와 XOR암호문에 대한 cribdrag 공격을 수행하기위한 스크립트라고한다.

아래와 같은 경우 사용할 수 있다.

* 키가 재사용되는 일회성 원타임패드 (두 개의 암호문을 XOR하여 사용)

* 키가 재상용된 모든 스트림 암호 (위와 동일)

* 단일 문자 XOR암호

* 복수 문자 XOR암호

그래서 이를 이용해서 문제를 풀어볼 수 있다.

먼저 flag와 secret의 앞부분을 동일한 크기만큼 가져와서 xorstrings.py를 이용해 xor하여 랜덤한 키부분은 제거해준다.

이제, 그걸 cribdrag.py에 넣고... 예측되는 message를 입력하여 계속 예측해나가면 된다.

예를 들어 TUCTF{를 입력하면 가능한 출력가능한 문자열을 출력해주는데

여기서 teal m이 가장 유력해보이므로 42를 선택해주면 된다.

이런식으로 커맨드라인에서 계속해서 추측해나가면 된다.

이것말고도 단일XOR암호나 다중XOR암호에서도 쓰일 수 있어서... 꽤나 편리하다. 나중에 또 써먹어야지

디피-헬만 문제입니다.

최근했던 CTF에 이와 같은 문제가 나와서 비슷한 유형의 다른 CTF 문제를 가져와 풀어보겠습니다.

디피-헬만(Diffie–Hellman)에서의 키교환 문제이다. 문제에서 flag값은 비밀키인 g^(ab) mod p 의 값이다.

g값도 안주어진다는 점에서 꽤 어려워보이는 문제이나. p값이 작아 소인수분해가 되기 때문에 이를 이용하여 문제를 풀 수 잇다.

factorDB에서 소인수분해를 해서 가져와보았다.

A와 B와 p가 공약수를 가지는 것을 알 수 있습니다. 

공약수는 k = 17 * 19^3 * 37 · 47^4 와 같습니다.

그렇다면 이제 아래와 같이 나타낼 수 있습니다.

자... 이제 단순화되었으니 g^ab가 될 후보들은 구하면...

위와 같이 사이클이 반복됨을 알 수 있습니다. 즉 6개의 값들중 하나가 비밀키입니다.

여기선 421049228295820이 비밀키였습니다.

*같은 유형의 다른문제

p : 739626899866411020995105608928036598669313466029070991080755558690

g^a mod p : 711179711410010597110678470123112114105109101951029799116111114125

g^b mod p : 256024696107603814959844249244320361077839276702370727681800001085

p = 2 * 5 * 13 * 1804529 * 6726547 * 468719798853001437040762632814600786193829912273851

A =  5^3 * 1804529 * 6726547 * 468719798853001437040762632814600786193829912273851

B = 3^2 * 5 * 1804529 * 6726547 * 468719798853001437040762632814600786193829912273851

k = 5  *  1804529 * 6726547 * 468719798853001437040762632814600786193829912273851

p = 26k

A= 25k

B = 9k

(g^a) mod 26k = 25k  = -k mod 26k

(g^a)^b = A^b = mod 26k = (-k)^b mod 26k

CTF{711179711410010597110678470123112114105109101951029799116111114125}

Diffie-Hellman 문제다.

풀수있었는데, 500점이나 되는 점수에 못풀줄 알았다 ㄷㄷ;

뭐;; 디피헬만은 공부부터 제대로 해야하는게 맞긴하다.

저번에도 디피헬만 문제를 한번 봐서 sage코드로 정리된게 몇개 있다.

이번것도 쉽게 풀린다.

이게 가지고있는 소스중 하나..

이게 이번것

얼마전에 서울하이유스호스텔에서 있었던 HackingCamp 18th에 참여하였었는데요. 그 때 내부 CTF에서 나왔던 Crypto문제(Easy CAESC)가 인상깊어서 비슷한 문제가 없을까 하고 찾던 중에 알게된 문제입니다. CSAW Quals 2017에서 나왔던 BabyCrypt란 문제인데요 ㅎㅎ Baby란 이름이 붙었음에도 350점이라는 높은 점수를 들고있기에 한번 풀어보도록 하겠습니다!

baby_crypt The cookie is input + flag AES ECB encrypted with the sha256 of the flag as the key.

nc crypto.chal.csaw.io 1578

먼저 문제를 살펴보면 이 baby_crypt가 무엇을 하는지 알려줍니다. cookie를 뱉어내는데, 이것이 input + flag의 형태로 되어있고 AES ECB 모드로 flag의 sha256해시값을 키로하여 암호화되어나온다는 것을 알 수 있습니다.

여기서 AES의 키 값으로 flag의 sha256해시값을 사용했으니까 "AES의 키값을 알아내야하나?"하시는 분들이 있을 수도 있는데, 설령 키 값을 알아낸다고 해도 단방향 해시값이기 때문에 다시 이를 평문으로 되돌릴수는 없습니다. (물론 키 값을 알아내는 것부터가 안됩니다만 ㅎ)

그럼 어떻게 해야하느냐? 문제에서 암호화해서 주어지는 값! input + flag에서 뒤의 flag값을 취하면 되는 것입니다!! 그런데 문제를 풀기전에 이 문제의 서버는 이미 닫힌지 아~~주 오래되었기 때문에, 저 문제를 풀기위해 문제를 직접 구현할 필요가 있습니다.(...)

그래서 직접 구현하였습니다! 핫ㅋ

#!/usr/bin/env python
from Crypto.Cipher import AES
import hashlib
import sys

flag = open("flag", "r").read().strip()

AES_KEY = hashlib.sha256(flag).hexdigest().decode("hex")[:16]
BLOCK_SIZE  = 16

pad = lambda s: s + (BLOCK_SIZE - len(s) % BLOCK_SIZE) * chr(BLOCK_SIZE - len(s) % BLOCK_SIZE)

def GetCookie(input):
	cipher = AES.new(AES_KEY, AES.MODE_ECB)
	input = pad(input + flag)
	print("Your Cookie is: " + cipher.encrypt(input).encode("hex"))

while(True):
	print("Enter you username (no whitespace) : "),
	sys.stdout.flush()
	input = raw_input()
	GetCookie(input)

이제 위 소스파일을 이용해 문제를 풀어봅시다!

먼저 대부분의 블록암호 문제에서 블록암호 모드를 사용하여 암호화된 암호문에 대한 공격은 아래와 같이 진행됩니다.

1. 암호모드 특정(Mode Detection: ECB, CBC, CTR 등)
2. 블록사이즈 구하기(Block size)
3. 공격 (1~2에 구한 것을 기반으로 하여)

하지만 이 문제에선 이미 1번에 해당하는 암호 모드를 알려주었기 때문에 저희는 2번부터 시작하면 됩니다.

이제 이 암호모드에서 사용하는 블록사이즈를 구해야합니다. 여기서 블록사이즈란, 블록암호에서는 데이터를 암호화할때 블록단위로 나누어 암호화를 하게게되는데 이 때 블록을 어느크기만큼 나누어 암호화할지 알려주는 것이 바로 블록사이즈입니다.

그러므로 평문을 암호화하기 위해서는 평문의 길이를 Block_SIZE로 맞추어줄 필요가 있고, 이를 위해 패딩을 하게 됩니다. AES블록암호화에서는 보통 PKCS#7 패딩방식을 이용하는데, 이 문제에서 패딩이 어떻게 이뤄지는냐는 중요하지않으므로 그림 하나로 설명을 대체하겠습니다. 자세한 설명은 위키피디아에서 보실수 있습니다.

자 이제 블록암호에서 암호화를 할 때 평문크기를 블록크기에 맞게 패딩을 한다는 사실을 알았으니, 문제 소스를 실행하여 한글자씩 문자를 보내봅시다.

abcdefghijklmo를 보냈을 때와 abcdefghijklmop를 보냈을 때 받은 암호문의 길이가 갑자기 증가하게 되고 우리는 이를 통해 Block_SIZE를 유추할 수 있습니다. 아래 python코드를 통해 실제 블록크기가 얼마가 되는지 구할 수 있습니다. (여기서 encryption_oracle(plain)함수가 평문에 대한 암호문을 받아오는 함수입니다.)

def find_block_size(encryption_oracle):
	pre_cp = encryption_oracle("")
	p = "A"
	while(True):
		cp = encryption_oracle(p)
		size = len(cp)-len(pre_cp)
		if size != 0:
			return size
		p+="A"

Block_SIZE : 16

자 이제 블록크기를 구했으니, 실제 공격만 하면 됩니다. 하지만 그 전에 ECB모드가 어떻게 동작되는지 알아보도록 하겠습니다.

ECB Mode

• 가장 단순한 모드로 평문을 블록단위로 나누어 순차적으로 암호화 하는 구조
• 같은 평문 -> 같은 암호문

암호화과정은 위와 같습니다. 여기서 보시면 아시겠지만, ECB모드는 동일 평문이 항상 동일 암호문으로 암호화되는 것을 알 수 있는데, 대부분이 사람들이 ECB모드를 설명할 때 나오는 펭귄 사진을 가져와보도록하겠습니다.

이렇게 ECB Mode로 암호화할 경우, 평문이 항상 같은 암호문으로 1:1 대칭되기때문에 그림의 윤곽이 드러나는 것을 알 수 있습니다. 이제 이 ECB Mode의 특성을 이용해서 문제를 풀어보겠습니다.

문제에서 주어진 암호화는 아래와 같이 이루어집니다.

저희가 username을 입력하면 그 값뒤에 FLAG가 붙어 암호화되는 방식입니다. 즉, 최종적으로는 아래와 같은 데이터가 암호화 오라클에 들어가게됩니다.

예를 들어 FLAG의 길이가 20이고, username으로 "AAAA..."로 10글자가 들어갔다면 블록사이즈인 16에 맞춰줘야하기때문에 PADDING이 2개붙어서 data가 들어가게 되고 암호화되어 출력되게됩니다.

여기서 저희가 제어할 수 있는 부분은 username부분입니다. data : 16bytes(1) | 16bytes(2) | 16 bytes(3)

여기서 저희가 Block_SIZE인 16보다 작은 15바이트를 "AAAAAAAAAAAAAAA"로 입력하게 된다면 FLAG의 마지막 한바이트를 가져올 수 있게 되고, 저희는 (1)블록의 처음 15바이트를 알고있으므로 (1)블록의 16번째 바이트에 대하여 255가지 암호문을 만들어 비교함으로써 마지막 한바이트를 알 수 있습니다.

계획은 이제 아래와 같습니다.

1. 블록크기보다 1바이트 작은 입력블록을 만든다.

(예: 블록크기가 8인 경우 "AAAAAAA"로 지정).

2. 마지막 바이트를 바꿔가며 마지막 바이트에 대한 블록암호의 사전을 만든다.

(예: “AAAAAAAA”, “AAAAAAAB”, “AAAAAAAC” 의 암호문 블록 사전)

3. 1번에서 만든 입력블록(1바이트작은)을 input_str에 넣어 나온 암호문을 사전에서 찾는다. 이게 FLAG의 첫 번째 바이트

4. 위 과정을 반복하여 FLAG의 바이트를 하나씩 찾는다.

#!/usr/bin/env python
from pwn import *
import string

conn = process(["python", "BabyCrypto.py"])

def encryption_oracle(plain):
	conn.recvuntil("Enter you username (no whitespace) : ")
	conn.sendline(plain)
	conn.recvuntil("Your Cookie is: ")
	enc = conn.recvline().strip()
	return enc.decode("hex")

def find_block_size(encryption_oracle):
	pre_cp = encryption_oracle("")
	p = "A"
	while(True):
		cp = encryption_oracle(p)
		size = len(cp)-len(pre_cp)
		if size != 0:
			return size
		p+="A"

def get_next_byte(encryption_oracle, known_suffix, block_size):
	dic = {}
	feed = "\x00"*(block_size-1-(len(known_suffix)%block_size))

	pt = ''
	#for i in range(0,256):
	for i in range(0x20,0x80):
		pt += feed + known_suffix + chr(i)
	ct = encryption_oracle(pt)[:len(pt)]
	for i in range(0x20,0x80):
		idx = (i-0x20)*(len(feed + known_suffix)+1)
		ct_one = ct[idx:idx+len(feed + known_suffix)+1]
		dic[ct_one]=chr(i)

	ct = encryption_oracle(feed)[:len(feed + known_suffix)+1]
	if ct in dic:
		return dic[ct]
	else:
		return ""

BLOCK_SIZE = find_block_size(encryption_oracle)
secret = ""

print("BLOCK_SIZE : %d "  %  BLOCK_SIZE)

while(True):
	one_byte = get_next_byte(encryption_oracle, secret, BLOCK_SIZE)
	if one_byte == "":
		break
	secret += one_byte
	print(secret)
print("result : "+secret)

서버가 이미 닫혔으므로, python pwntools를 사용하여 로컬에서 공격하는 코드이다. 위 파이썬 익스코드를 실행하면 로컬환경에 있는 flag를 획득할 수 있다.

*후기

한번 풀었던 유형의 문제였지만, Writeup을 써보고, 다시 한번 정리해보고 싶어서 작성해보았다. 문제는 AES-ECB모드에 대한 이해와 BLOCK_SIZE로 암호화되는 블록암호의 특성을 대한 지식을 필요로 하기때문에 블록암호에 대해 공부하고 있다면 풀어보면 좋은 문제라고 생각한다.

hackon ctf 2018에 나왔던 RSA 문제이다.

딱 봐도 e가 큰게 wiener attack이다!! 라고 생각했는데... 내가 가진 공격소스코드로는 풀리지않아서 굉장히 답답했는데;;

대회가 끝나고 난 후 다른사람들 writeup을 보니

잉... 나만 빼고 다들 wiener attack을 잘해서 풀었다 ㅡㅡ;

역시 이미 존재하는 툴이나 소스코드를 잘 활용해야하는 것인가...

문제는 아래와 같다.

푸는 법은 wiener attack!!

여기에 있는 소스코드를 참고하여 문제를 풀었다.

(https://github.com/MxRy/rsa-attacks/blob/master/wiener-attack.py)

아니면 RShack을 이용해서 풀어도 좋다.

이 툴 좋네...

XOR문제입니다.

많은 사람들이 풀었기때문에 100점까지 낮아졌습니다 ㅠ;;

아니... 어떻게 이걸 더 많이 푼거지 ;;

다른 암호들이 훨씬 빨리 풀리는데 ...

아무튼!

문제는 아래와 같습니다.

키 값도 주고, 문제도 단순합니다. 홀수번째 블록암호가 거꾸로 XOR되기때문에 이를 유의해서 풀면 보통 XOR암호문제와 다를게 없습니다.

그래서 조금 어려운 문제가 아닌가싶었는데;;

대부분이 Bruteforcing으로 잘풀었습니다.(flag형식이 지정되어있기때문에...)

하지만 저는 hamming_distance와  Alphabet score를 이용해서 풀어보았습니다.

먼저 hamming_distance 측정을 통해 평문이 알파벳과 숫자로 구성된 문자열이란 것을 알 수 있습니다.

그래서 Alphabet score를 매기는 방식으로 코드를 짜서 풀었습니다. CTF에 나오는 플래그 형식이 완전히 알파벳이 아니라서 조금 변형시키긴했지만~

그래도 잘 돌아갑니당..ㅎㅎ

관련개념은 추후에 블로그에 올리겠습니다.

그럼 이 글도 조금은 수정되겠져

문제입니다. 정말 심플합니다. modinv()함수까지 다 짜주어서 그냥 p,p1,p2,p3만 구하면 문제를 풀 수 있습니다.

물론 그게 어렸기 때문에 고생하는 거지만요 ㅠㅠ

그래서 저는 저걸 못구해서 끙끙거렸는데;;

이걸 같이 CTF하는 팀원님이 구해주셨습니다(대단해...!! rls1004님 감사합니당...)

저는 이걸 p를 gmpy.root(N/1000000,4)로 해서 잡아놓고 1씩 올리거나 내리면서 계산햇는데;; ㅠㅠ

알고리즘 공부를 더 해야할거같습니다 ㅠㅠ

대회가 끝나고 다른분들 writeup을 보니 이진탐색도 사용하더군엽.. 

p를 N/1000000의 4제곱근 근처로 잡은 이유는 문제코드가 아래와 같아서 입니다.

즉... N=p*(p*10+a)*(p*100+b)*(p*1000+c) 일테니..

대충 p^4 * 1000000 + A 일겁니다. 그러므로 .root(N/1000000,4)로 잡아놓고 풀었습니다.

참고로 python 모듈이 없다면, sage로도 가능!

http://math3.skku.ac.kr/home/myriabreak/7/

CTF가 끝나고 한 번 풀어본다.

CTF 기간 중에는 팀원님이 아주 빠르게 풀어주셨다...

나는 RSA문제에 막혀서 ㅠㅠㅠ

아직 서버가 살아있어서 nc로 접속하면 아래와 같이 사용자로 부터 숫자입력을 받고, 뭔가를 출력해준다.

소스파일도 주어졌으므로 먼저 소스파일을 보자.

사용자로부터 Number를 입력받은 후

number와 flag를 or하여, 그 값을 sha512해시값으로 해서 출력해준다.

이 flag의 값은 변하지않고, 사용자는 Number를 써서 flag과 or한 결과값을 계속 얻을 수 있으므로 0과 flag를 OR한 값과 다른 bit들을 비교하여 공격하면된다. 

즉 bit flipping하여 1bit씩 브루트포싱하는 것이다.

성공