Write-up/Crypto

[MeePwnCTF 2018] bazik

2018. 7. 25. 02:30

저번주에 하도 바빠서...(핑계지만??? 핑계다.)


MeePwnCTF를 끝내고 나서 다시 한번 문제를 살펴보는게 힘들었다...

그래서 이번 주말에 고향내려갔다가 조~~금 여유가 생겨서 다시 보게 되어서 이렇게 포스팅을 쓴다!



basic challenge라고 한다.


basic이라기에, 굉장히 쉬운 crypto 문제일 줄 알았지만;;

분석이 부족하였고, 포너블문제에 정신이 팔려있어서;; 끝나고 나서 writeup을 보고 다시한번 풀어보려고 한다.


문제서버가 아직도 열려있어서 다시 한번 풀어볼 수 있었다.


먼저 문제서버에 접속하면 아래와 같다.





Test the OTP를 선택하면

otp값과 encrypted dat와 그 decrypted dat인 평문을 주는데, 평문 형식은 "Your OTP for transaction #731337 in ABCXYZ Bank is XXXXXXXX" 형식이다.


그래서 평문이 조금씩 바뀌므로 Coppersmith’s attack 중 Stereotyped Messages Attack로 풀 수 있다.

관련 wrtieup은 여기에 있다.


Writeup : https://ctftime.org/task/6293


직접해보려다가 귀찮아서 포기하였다 ㅎㅎ;;

p4 팀은 Stereotyped Messages Attack으로 풀었고, PLUS팀은 e값이 작고 평문의 길이가 짧기때문에 암호문에 n을 계속 더하여 세제곱근이 나올때까지하여, 세제곱근이 나오면 정답이다! 라는 식으로 풀었다... 매우 브루트포싱...




sage 사용 : http://math3.skku.ac.kr/home/myriabreak/







저작자표시

'Write-up > Crypto' 카테고리의 다른 글

[ISITDTU 2018] Simple RSA Write-up  (0) 2018.07.30
[ISITDTU 2018] Baby Write-up  (0) 2018.07.30
[MeePwnCTF 2018] esor (easy)  (0) 2018.07.16
[MeePwnCTF 2018] esor (hard)  (0) 2018.07.16
[MeePwnCTF 2018] ezchallz  (0) 2018.07.16

[MeePwnCTF 2018] esor (easy)

2018. 7. 16. 20:10


Howdy, howdy ...


python소스가 하나 주어지고, nc를 통해 서버에 접속하면 encrypt된 data를 요청할 수 있다.



주어진 소스 파일은 아래와 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#!/usr/bin/python2
from Crypto.Cipher import AES
import hmac, hashlib
import os
import sys
 
menu = """Choose one:
1. encrypt data
2. decrypt data
3. quit
"""
 
class Unbuffered(object):
    def __init__(self, stream):
        self.stream = stream
    def write(self, data):
        self.stream.write(data)
        self.stream.flush()
    def __getattr__(self, attr):
        return getattr(self.stream, attr)
 
sys.stdout = Unbuffered(sys.stdout)
sys.stderr = None
 
encrypt_key = '\xff' * 32
secret = 'MeePwnCTF{#flag_here#}'
hmac_secret = ''
blocksize = 16
hmac_size = 20
 
def pad(msg):
    padlen = blocksize - (len(msg) % blocksize) - 1
    return os.urandom(padlen) + chr(padlen)
 
def unpad(msg):
    return msg[:-(ord(msg[-1]) + 1)]
 
def compute_hmac(msg):
    return hmac.new(hmac_secret, msg, digestmod=hashlib.sha1).digest()
 
def encrypt(prefix='', suffix=''):
    _enc = prefix + secret + suffix
    _enc+= compute_hmac(_enc)
    _enc+= pad(_enc)
    iv = os.urandom(16)
    _aes = AES.new(encrypt_key, AES.MODE_CBC, iv)
    return (iv + _aes.encrypt(_enc)).encode('hex')
 
def decrypt(data):
    data = data.decode('hex')
    try:
        iv = data[:blocksize]
        _aes = AES.new(encrypt_key, AES.MODE_CBC, iv)
        data = _aes.decrypt(data[blocksize:])
        data = unpad(data)
        plaintext = data[:-hmac_size]
        mac = data[-hmac_size:]
        if mac == compute_hmac(plaintext): 
            print(plaintext)
            return True
        else: return False
    except: return False
 
print """Welcome to our super secure enc/dec server. 
We use hmac, so, plz don't hack us (and you can't). Thanks."""
 
while True:
    choice = int(raw_input(menu))
    if choice == 1:
        _pre = raw_input('prefix: ')
        _suf = raw_input('suffix: ')
        print encrypt(prefix=_pre, suffix=_suf)
    elif choice == 2:
        _data = raw_input('data: ')
        if decrypt(_data):
            print 'OK'
        else:
            print 'KO'
    elif choice == 3:
        sys.exit(0)
    else:
        choice = int(raw_input(menu))
cs


encrypt함수는  _enc = prefix + secret + suffix 로 사용자로부터 입력받은 prefix와 suffix를 flag의 앞과 뒤에 붙여 암호화하게 된다.

AES.CBC모드로 암호화하기 때문에 iv값이 필요하게 된다.


뭐.. 분석을 하면 좀 길어진다. 그러나 실제 문제를 풀때는 분석이 필요없었다;;


출제자의 실수인지, 서버에서 사용하는 키값과 주어진 소스파일의 키값이 같았다.

즉 '\xff' * 32가 키값인것이다. 그래서 그냥 서버에서 주는 data값을 주어진 소스파일의 decrypt함수로 돌리면 flag가 나온다.


MeePwnCTF{pooDL3-this-is-la-vie-en-rose-P00dle!}


플래그 내용에 Poodle이란 단어가 들어가 있는데, Poople attack이라고 구글에 검색하면 아래와 같이 나온다.


The POODLE attack (which stands for "Padding Oracle On Downgraded Legacy Encryption") is a man-in-the-middle exploit which takes advantage of Internet and security software clients' fallback to SSL 3.0. 


원래는 이 POODLE attack을 통해 푸는 문제인것같다. 하지만 출제자의 실수로.... (대회가 끝난 시점인 현재 130명이나 풀었다...)

대회가 끝나고 다시 서버에서 주어진 data를 주어진 소스파일로 decrypt하려 했더니, 실패하였다.


아마 대회중간에 키 값이 잘못된걸 알아차리고 바꾼것같은데;; 운좋게 푼사람들은 몰라도... 못푼사람들은 ㅠㅠ


일단 대회당시에는 이렇게 풀수있었다.


다음 포스팅에서는 Poople attack으로 푸는 방법으로 다시 써보겠다.




저작자표시

'Write-up > Crypto' 카테고리의 다른 글

[ISITDTU 2018] Baby Write-up  (0) 2018.07.30
[MeePwnCTF 2018] bazik  (0) 2018.07.25
[MeePwnCTF 2018] esor (hard)  (0) 2018.07.16
[MeePwnCTF 2018] ezchallz  (0) 2018.07.16
[UIUCTF 2018] Hastad  (0) 2018.06.02

[MeePwnCTF 2018] esor (hard)

2018. 7. 16. 18:24



시간나면 쓰겠슴다.

저작자표시

'Write-up > Crypto' 카테고리의 다른 글

[MeePwnCTF 2018] bazik  (0) 2018.07.25
[MeePwnCTF 2018] esor (easy)  (0) 2018.07.16
[MeePwnCTF 2018] ezchallz  (0) 2018.07.16
[UIUCTF 2018] Hastad  (0) 2018.06.02
[Byte Bandits CTF 2018]R u Ronald Rivest?  (0) 2018.06.02

[MeePwnCTF 2018] ezchallz

2018. 7. 16. 16:49


ezchallz입니다. 주어진 url로 접속해보면 Free register라고 나오는데, LFI 취약점이 있습니다.



LFI(Local File Inclusion) 취약점은 웹 브라우저를 통해 서버에 파일을 포함시키는 과정입니다.

이 취약점은 인클루드할 페이지 경로가 적절히 필터링되지 않았고 디렉토리 변경 명령어들의 삽입을 허용했을때 일어납니다.

대부분의 LFI 취약점은 URL을 통해 이뤄지는데 이는 보통 개발자가 GET Method 사용을 선호하기 때문입니다. 


그래서 php://filter을 이용해서 php://filter/convert.base64-encode/resource=파일이름 를 page=뒤에 붙여서 보내면 해당 파일을 추출해낼 수 있습니다.

 

http://206.189.92.209/ezchallz/?page=php://filter/read=convert.base64-encode/resource=index


추출된 파일의 내용은 아래와 같습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
<html>
<a href="index.php">Homepage</a>
<a href="?page=register">Free register</a></li>
 
<?php
if(isset($_GET["page"]) && !empty($_GET["page"])) {
    $page = $_GET["page"];
    if(strpos(strtolower($page), 'secret') !== false) {
        die('No no no!');
    }
//    else if(strpos($page, 'php') !== false) {
 //       die("N0 n0 n0!");
//    }
    else {
        include($page . '.php');
    }
}
?>
</html>
 
cs


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
<html>
<?php
error_reporting(0);
 
function gendirandshowflag($username) {
    include('secret.php');
    $dname = "";
    $intro = "";
    $_username = md5($username, $raw_output = TRUE);
    for($i = 0; $i<strlen($salt); $i++) {
        $dname.= chr(ord($salt[$i]) ^ ord($_username[$i]));
    };
    $dname = "users/" . bin2hex($dname);
    echo 'You have successfully register as ' . $username . '!\n';
    if ($_username === hex2bin('21232f297a57a5a743894a0e4a801fc3')) {
        $intro = "Here is your flag:" . $flag;
    }
    else {
        $intro = "Here is your flag, but I'm not sure ?쨺: \nMeePwnCTF{" . md5(random_bytes(16) . $username) . "}";
    }
    mkdir($dname);
    file_put_contents($dname . '/flag.php', $intro);
    header("Location: ". $dname . "/flag.php");
}
 
if (isset($_POST['username'])) {
    if ($_POST['username'] === 'admin') {
        die('Username is not allowed!');
    }
    else {
        gendirandshowflag($_POST['username']);
    }
}
?>
 
        <form action="?page=register" method="POST">
        <input type="text" name="username"><br>
        <input type="submit" value="Register">
        </form>
</html>
 
 
cs


유저명의 md5와 secret_salt의 값과 XOR한 값으로 폴더를 생성하고, 그 안에는 가짜 flag를 보여주는 flag.php가 있습니다.

단순히 md5값과 salt값을 xor한것이므로 역으로 salt값을 구할 수 있습니다.


salt값을 구하여 admin의 md5값과 xor한 값을 폴더로하여 들어가면 올바른 flag를 구할 수 있습니다.


md5 encrypt : https://www.md5online.org/


XOR하기 위해 예전에 cryptopals 문제풀때 사용했던 python code를 그대로 사용했습니다. https://github.com/wotmd/cryptopals/blob/master/set1/02_Fixed_XOR.py


Regiser sherlock is : aa415a493257a95092efead786d5aea1

MD5 hash for sherlock is : 1bea3a3d4bc3be1149a75b33fb8d82bc


so Secret Salt is : b1ab607479941741db48b1e47d582c1d


MD5 hash for admin is : 21232f297a57a5a743894a0e4a801fc3

Regiser admin is : 90884f5d03c3b2e698c1fbea37d833de




접속하면 위와같이 플래그를 얻을 수 있습니다.




저작자표시

'Write-up > Crypto' 카테고리의 다른 글

[MeePwnCTF 2018] esor (easy)  (0) 2018.07.16
[MeePwnCTF 2018] esor (hard)  (0) 2018.07.16
[UIUCTF 2018] Hastad  (0) 2018.06.02
[Byte Bandits CTF 2018]R u Ronald Rivest?  (0) 2018.06.02
[Plaid CTF 2018] macsh - 125  (0) 2018.05.07

[UIUCTF 2018] Hastad

2018. 6. 2. 21:08

Hastad ● Crypto ● 200 Points



sorry wrong chat라고 하고..


ciphertexts.txt 와 moduli.txt가 주어진다.


일단 한번 보자.



이게 ciphertexts.txt이고 아래가 moduli.txt이다.



RSA암호화로 ciphertexts.txt를 보낸것이라 생각한다. 여기서 e=3이라고 하는데...


e값이 매우 작고 평문이 길이가 짧을 경우, n(=p*q)값이 매우 크기때문에.. 암호화된 평문 C=P^e(% n) 에서 n이 너무커서 C가 모듈러 연산에 몇번 걸리지 않는 경우가 있다. 이 경우 C값을 그냥 e 거듭제곱근을 구해서 평문을 복호화해 낼 수가 있다고 한다. 그래서 일단 e제곱근한 값이 나오나 보기로 했다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
c_list = [0x10652cdfaa86ddbee1409ac7ac327a0c848081ee6e3b110867085f1074755785b0a5a6a2343b791695c3e91fdb370d5b26be3b6d2fc449c7788bbb1ab67ddc361b4115010618e39c883449b757fc1624369b440236ee65, 0x10652cdfaa8c9ef24fc044b5fed749888632ad132bd412f22d9d905e6ffd27b288c22884b24fe130d83aaab9c2dc6e942418dff89d2b66a66e40900db9456813d70eb63d0c38697f89ff387969d3d40163376416270965, 0x10652cdfaa8ab16290cf92bacf31b23d6a0ea95c2ebd6eb8afe4f038d852a7f17e98f965f299b4d00126611d403c5208a145157ed1d71079fc558eaa888e993360fac35c7a816ad183190867b1b7580a2677cd6871aa65, 0x10652cdfaa86ddbee1409ac7ac327a0c848081ee6e3b110867085f1074755785b0a5a6a2343b791695c3e91fdb370d5b26be3b6d2fc449c7788bbb1ab67ddc361b4115010618e39c883449b757fc1624369b440236ee65, 0x10652cdfaa875a9ac01e472ea5896c1d460410508b9a7c723b5ba904fb5b64d68a1e96254ba04b08c92d51f1fe6c3d6bb426e1ee8c61c8a6ff1eeab9e07f51d8057f2f0c54b27c7006539f7148484ff26a02e4cb1d3165, 0x10652cdfaa8c9ef24fc044b5fed749888632ad132bd412f22d9d905e6ffd27b288c22884b24fe130d83aaab9c2dc6e942418dff89d2b66a66e40900db9456813d70eb63d0c38697f89ff387969d3d40163376416270965, 0x10652cdfaa875a9ac01e472ea5896c1d460410508b9a7c723b5ba904fb5b64d68a1e96254ba04b08c92d51f1fe6c3d6bb426e1ee8c61c8a6ff1eeab9e07f51d8057f2f0c54b27c7006539f7148484ff26a02e4cb1d3165, 0x10652cdfaa8210601d22f4a15aa380233420f9ee9a276d3ac8e05cfc4f6f515f78331e8e74484e8533221e88f78671dd08622e78233e458978a35036680d1c5caaba2fa3bce3b914ad48501a276d6a88adc16db282e065, 0x10652cdfaa8ab16290cf92bacf31b23d6a0ea95c2ebd6eb8afe4f038d852a7f17e98f965f299b4d00126611d403c5208a145157ed1d71079fc558eaa888e993360fac35c7a816ad183190867b1b7580a2677cd6871aa65, 0x10652cdfaa8c2701b8bb7c11fc3218cc2d97cd4707f6de55637bc093f474d231b4d4fe8635261b8e4f772d0e51a25f8e713777a137be6f04e0d28ddd6ec0b852aaf357d33e08aed23e034fcd1ced38542fbeb5aa0eee65, 0x10652cdfaa8210601d22f4a15aa380233420f9ee9a276d3ac8e05cfc4f6f515f78331e8e74484e8533221e88f78671dd08622e78233e458978a35036680d1c5caaba2fa3bce3b914ad48501a276d6a88adc16db282e065, 0x10652cdfaa8c9ef24fc044b5fed749888632ad132bd412f22d9d905e6ffd27b288c22884b24fe130d83aaab9c2dc6e942418dff89d2b66a66e40900db9456813d70eb63d0c38697f89ff387969d3d40163376416270965, 0x10652cdfaa8ab162128a955a58d3b780f2656800796eb70c345c56d7b8523d614ef4ca920471f56493c83ca48500033a0c0b31988ca6e66a76e0ed559b38616688941558b127260cdf70261822929efa0aa6b6d79d1665, 0x10652cdfaa8ab162128a955a58d3b780f2656800796eb70c345c56d7b8523d614ef4ca920471f56493c83ca48500033a0c0b31988ca6e66a76e0ed559b38616688941558b127260cdf70261822929efa0aa6b6d79d1665, 0x10652cdfaa8c2701b8bb7c11fc3218cc2d97cd4707f6de55637bc093f474d231b4d4fe8635261b8e4f772d0e51a25f8e713777a137be6f04e0d28ddd6ec0b852aaf357d33e08aed23e034fcd1ced38542fbeb5aa0eee65]
 
 
e = 3.00
 
for idx, c in enumerate(c_list):
    c_list[idx]=c**(1.00/e)
    print("%x " % c_list[idx])
 
 
for c in c_list:
    #c = c**(1.00/e)
    c=format(int(c), 'x')
    print("%s " % (c.decode("hex")))
 
cs


이런 파이썬 코드를 짜서... 출력해보았다.


코드는 해당 ciphertexts.txt의 값들을 각각 세제곱근한 값을 hex값으로 두고, 이를 decode해 평문으로 출력하는 것이다.



위와 같이 출력되었고... 666c61677b757000000000000000000000000000000000000000000000 와 flag{up 를 볼때...


모듈러연산에 걸려 평문값이 짤려 손실된것으로 보인다.



....


아닛.... 엄청난걸 찾았다. 위키백과 굿

https://en.wikipedia.org/wiki/Coppersmith%27s_attack#RSA_basics


위 url을 통해 들어가보면 Håstad's broadcast attack라고 있다.

한번 자세히 알아보자. 

Hastad's Broadcast Attack 
Coppersmith 정리를 이용한 첫 번째 응용으로써, Hastad가 제안했던 알고리즘을 개선한 내용을 알아본다. Bob은 평문 M을 암호화해서 P1,P2,…,Pk 라고 하는 여러 group에게 동시 에 전송하려 한다고 가정하자. 각 group은 각기 RSA 공개키 를 갖고 있다. 그리고 평문M이 모든 Ni보다 작다고 하자. 이런 상황에서 Oscar는 Bob이 모르게 이들의 통신을 도청할 수 있고, k개의 암호문을 가로 챌 수 있다. 편의상, 모든 공개키 ei가 3이라고 하자. 이 경우, k≥3이면, 0scar는 암호문으로부터 평문 M을 복호화 할 수 있다. 즉, Oscar가 세 개의 암호문 C1,C2,C3를 얻었다고 하자. 여기서, C1=M3 modN1, C2=M3 modN2, C3=M3 modN3 이다. 그리고, Oscar가 Ni를 소인수 분해하지 못하게 하기 위해, 서로 다른 i, j 에 대해 gcd(Ni,Nj)=1라고 가정할 수 있다. 그러면, CRT을 이용해, C'=M3 modN1N2N3을 만족하는 Z N1N2N3의 원소 C'를 구할 수 있다. 가정에서 M이 모든 Ni보다 작다고 했기 때문에 M3 < N1N2N3이고 따라서 C'=M3 이 성립한다. 따라서, Oscar는 C'의 삼제곱근을 실수에서 연산하 면, M을 얻을 수 있다. 일반적으로, 모든 공개키(public exponent) ei가 같다고 하고 "k≥ei" 이기만 하면 Oscar는 평문 M을 복호화할 수 있다. 이 공격법은 공개키 e가 작은 경우에 한한다. 하지만, 이 공격법에 미미하게 대응해선 안 된다. 예를 들어, Bob이 평문 M을 암호 화하기 전에, "덧붙이기" 과정을 취할 수 있다. 즉, |M|=m 이라 하면, Bob은 Pi에게 Mi=i2m +M을 암호화해서 전달한다. 그러면, Oscar는 서로 다른 평문에 대안 암호문을 얻기 때문에, 위에서 살펴본 공격법을 취할 수가 없을 것 같다. 하지만, 위와 같은 선형 덧붙이기 과정이 안전하지 못함을 Hastad는 보였다. 더욱이, 그는 덧붙이기 과정으로서, 평문을 입력 으로 하는 고정된 다항식 연산을 취하는 것도 위의 공격방법을 막을 수 없음을 증명했다. 다음은 Hastad의 결과보다 강한 내용(stronger version)이다.

여기서 CRT는  Chinese Remainder Theorem, 로 중국인의 나머지 정리이다.

요약하자면 동일한 메세지를 여러 명에게 동시에 전송할때, 평문 M이 모든 Ni보다 작고, ei가 충분히 작고 알고있는 암호문 k가 k>=ei이면 중국인의 나머지정리(CRT)를 이용해 C를 구할수 있고 이 C의 e제곱근이 바로 평문이다.

먼저 이 문제가 hastad's Broadcast Attack으로 공격할수 있는지 살펴보자.

먼저 e=3으로 작은 값이고, ciphertexts.txt에 같은 flag를 암호화한 암호문 여려개와 moduli.txt에 N이 3개가 주어졌다. (이 3개의 N은 서로 서로수일것이다.)
암호문을 3개 이상얻었으므로 중국인의 나머지 정리를 이용해서 C = M^3 mod N1N2N3을 만족하는 C를 구해보자.

.................

이거 가지고 7시간 삽질을 했는데... 결국 안됐다 ㅡㅡ;; 아나

가장 큰 문제는  C = M^3 mod N1N2N3을 만족하는 C를 구햇는데 이 C의 세제곱근을 못구해서 엄청 헤매다가;;

import gmpy를 통해 해결하였다. 그런데 이게 안구해져서 ㅁㄴㅇㄹ 화가 나려하는데;; 아래와 같은 문제점을 발견해서 풀었다.

------------------------------------------------------------------------------------------------------------------------------


세제곱근을 구할때 보통 r = (c **(1.0/3.0)) 과 같이 구한다. 하지만 큰 수 c를 여기에 쓸 경우 이렇게 쓰면 정확하지 않다...

그래서  flag가  666c61677b757000000000000000000000000000000000000000000000 와 flag{up  이렇게 짤려나오는거였다.
문제에서 일부러 저렇게 준게 아니고 python에서 계산을 못해서 짤려나온거다 ㅡㅡ;;

해결법은 gmpy 모듈을 쓰는것이다.

import gmpy를 하면 result, bool = gmpy.root( num, k)를 쓸수가 있는데; 
이게 num를 k제곱근한 값을 result에 저장하고 bool에 성공여부를 0과 1로 저장한다.

이걸 이용해서 위 코드를 다시 짜면...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import gmpy
 
c_list = [0x10652cdfaa86ddbee1409ac7ac327a0c848081ee6e3b110867085f1074755785b0a5a6a2343b791695c3e91fdb370d5b26be3b6d2fc449c7788bbb1ab67ddc361b4115010618e39c883449b757fc1624369b440236ee65, 0x10652cdfaa8c9ef24fc044b5fed749888632ad132bd412f22d9d905e6ffd27b288c22884b24fe130d83aaab9c2dc6e942418dff89d2b66a66e40900db9456813d70eb63d0c38697f89ff387969d3d40163376416270965, 0x10652cdfaa8ab16290cf92bacf31b23d6a0ea95c2ebd6eb8afe4f038d852a7f17e98f965f299b4d00126611d403c5208a145157ed1d71079fc558eaa888e993360fac35c7a816ad183190867b1b7580a2677cd6871aa65, 0x10652cdfaa86ddbee1409ac7ac327a0c848081ee6e3b110867085f1074755785b0a5a6a2343b791695c3e91fdb370d5b26be3b6d2fc449c7788bbb1ab67ddc361b4115010618e39c883449b757fc1624369b440236ee65, 0x10652cdfaa875a9ac01e472ea5896c1d460410508b9a7c723b5ba904fb5b64d68a1e96254ba04b08c92d51f1fe6c3d6bb426e1ee8c61c8a6ff1eeab9e07f51d8057f2f0c54b27c7006539f7148484ff26a02e4cb1d3165, 0x10652cdfaa8c9ef24fc044b5fed749888632ad132bd412f22d9d905e6ffd27b288c22884b24fe130d83aaab9c2dc6e942418dff89d2b66a66e40900db9456813d70eb63d0c38697f89ff387969d3d40163376416270965, 0x10652cdfaa875a9ac01e472ea5896c1d460410508b9a7c723b5ba904fb5b64d68a1e96254ba04b08c92d51f1fe6c3d6bb426e1ee8c61c8a6ff1eeab9e07f51d8057f2f0c54b27c7006539f7148484ff26a02e4cb1d3165, 0x10652cdfaa8210601d22f4a15aa380233420f9ee9a276d3ac8e05cfc4f6f515f78331e8e74484e8533221e88f78671dd08622e78233e458978a35036680d1c5caaba2fa3bce3b914ad48501a276d6a88adc16db282e065, 0x10652cdfaa8ab16290cf92bacf31b23d6a0ea95c2ebd6eb8afe4f038d852a7f17e98f965f299b4d00126611d403c5208a145157ed1d71079fc558eaa888e993360fac35c7a816ad183190867b1b7580a2677cd6871aa65, 0x10652cdfaa8c2701b8bb7c11fc3218cc2d97cd4707f6de55637bc093f474d231b4d4fe8635261b8e4f772d0e51a25f8e713777a137be6f04e0d28ddd6ec0b852aaf357d33e08aed23e034fcd1ced38542fbeb5aa0eee65, 0x10652cdfaa8210601d22f4a15aa380233420f9ee9a276d3ac8e05cfc4f6f515f78331e8e74484e8533221e88f78671dd08622e78233e458978a35036680d1c5caaba2fa3bce3b914ad48501a276d6a88adc16db282e065, 0x10652cdfaa8c9ef24fc044b5fed749888632ad132bd412f22d9d905e6ffd27b288c22884b24fe130d83aaab9c2dc6e942418dff89d2b66a66e40900db9456813d70eb63d0c38697f89ff387969d3d40163376416270965, 0x10652cdfaa8ab162128a955a58d3b780f2656800796eb70c345c56d7b8523d614ef4ca920471f56493c83ca48500033a0c0b31988ca6e66a76e0ed559b38616688941558b127260cdf70261822929efa0aa6b6d79d1665, 0x10652cdfaa8ab162128a955a58d3b780f2656800796eb70c345c56d7b8523d614ef4ca920471f56493c83ca48500033a0c0b31988ca6e66a76e0ed559b38616688941558b127260cdf70261822929efa0aa6b6d79d1665, 0x10652cdfaa8c2701b8bb7c11fc3218cc2d97cd4707f6de55637bc093f474d231b4d4fe8635261b8e4f772d0e51a25f8e713777a137be6f04e0d28ddd6ec0b852aaf357d33e08aed23e034fcd1ced38542fbeb5aa0eee65]
 
 
e = 3.00
 
for idx, c in enumerate(c_list):
    c_list[idx], perfect = gmpy.root(c, 3)
    print("%x %d " % (c_list[idx], perfect))
 
 
for c in c_list:
    #c = c**(1.00/e)
    c=format(int(c), 'x')
    print("%s " % (c.decode("hex")))
 
 
cs

이렇게 되고 결과는 아래와 같다.


하... 이렇게 잘나오는걸 삽질을 그렇게 하다니 ㅡㅡ;


다른사람들의 Writeup - 추가
이분들은 그냥 정석대로 Hastad Broadcast Attack을 하셨다. 
암호문이 15개주어졌으니 15개를 3개씩 가능한 모든 조합으로 브루트포싱으로 공격을 시도하면 그 중 계산이 맞아 떨어지는것이 있고, 이것으로 플래그가 구해진다. (물론 나도 가능한 모든 조합으로 공격해보았다. 하지만 실패 ㅡㅡ; 분명 어딘가 실수가 있었겠지...)

이때 사용한 파이썬 모듈이 itertools인데 알아두면 좋을 것 같다. (참고사이트: http://hamait.tistory.com/803)
itertools이 가지고있는 함수들의 목록 및 기능은 여기서 보면 좋다.(https://docs.python.org/2/library/itertools.html)

Iterator

Arguments

Results

product()

p, q, … [repeat=1]

cartesian product, equivalent to a nested for-loop

permutations()

p[, r]

r-length tuples, all possible orderings, no repeated elements

 





특히 이 permutations()라는 것이 좋다.. 가능한 모든 순열을 구해준다.

Other WriteUP



저작자표시

'Write-up > Crypto' 카테고리의 다른 글

[MeePwnCTF 2018] esor (hard)  (0) 2018.07.16
[MeePwnCTF 2018] ezchallz  (0) 2018.07.16
[Byte Bandits CTF 2018]R u Ronald Rivest?  (0) 2018.06.02
[Plaid CTF 2018] macsh - 125  (0) 2018.05.07
[0ctf 2017] integrity - 75p  (0) 2018.05.02

[Byte Bandits CTF 2018]R u Ronald Rivest?

2018. 6. 2. 21:03

[Crypto]R u Ronald Rivest? 70p



문제이름은 Are you Ronald Rivest?이다. Ronald Rivest가 누구지? 하고 검색해보았다.


RSA 암호 체계를 발명하신 분이다. 왠지 문제와 엄청 관계있을것같다.


이제 문제에서 주어진 파일을 보자.


text.txt 파일과 lol_pub.pem 파일이 주어진다. 

이 pem포맷파일은 문제이름에 나오는 RSA창시자 이름을 볼 때 RSA 공개키파일로 추측된다.

각각을 살펴보면 아래와 같다.


------------------------------------------------------------------------------------------------------------------------

PEM(Privacy-enhanced Electronic Mail)


여기서 준 lol_pub.pem 파일은 이름에서 유추해볼때 public_key파일이라는 것과 파일을 열어봤을때 첫줄과 마지막에 보이는 PUBLIC KEY로 이 파일이 공개키파일임을 알 수 있다.

RSA에서 쓰이는 공개키는 숫자인데, base64로 인코딩된 듯한 문자와 위아래로 텍스트 문자열(-----public ----)이 들어가 있다.

이러한 형태를 띄고 있는 파일은 PEM(Privacy Enhanced Mail) 포맷 파일로, 공개키를 암호화한 파일이다.


openssl을 이용해 개인키 및 공개키를 생성하면 위와 같은 파일을 자주 볼 수 있다.



비교해보기 위해 임의로 mykey.pem을 생성해보았다.


같은 형식인 걸 알 수 있었다.


그럼 openssl로 분석해볼까.. -noout -text 옵션으로 PEM 인코딩된 인증서를 파싱해서 정보를 출력해보겟다.



n = 225bit이고 e=65537인것을 알 수 있다. 

n을 좀 더 숫자로 표현해서 보고 싶다면 방법이 있다. ( https://stackoverflow.com/questions/3116907/rsa-get-exponent-and-modulus-given-a-public-key )


PUBKEY=`grep -v -- ----- lol_pub.pem | tr -d '\n'`  
echo $PUBKEY | base64 -d | openssl asn1parse -inform DER -i


환경변수로 문자열을 파싱하고 base64 디코딩해 openssl을 통해 정보를 읽는다.



n이랑 e가 BIT STRING, offset 17에 들어있ㄷ. -strparse을 추가해서 파싱해주자.

아니면 그냥 openssl rsa -in pubkey.pem -pubin -text -modulus 로만 해줘도 잘나온다 (2018.12.07 추가)




n=0x013269DC2680BC64277889DC6A101ED6F13DD07498F13A4818474C2069

(32269109513264378873151120068074444086989044741418671122338798116969)

e=0x10001 (65537)


n을 찾았다!!


이제 소인수 분해를 하면 되겠다. 이 때 좋은 사이트가 있다는 것을 알았다.


FatorDB : http://factordb.com/    


이 사이트에 넣으면 만약 DB에 이미 소인수분해한 값이 있다면 그대로 알려준다. 매우 좋은 사이트다...!!



오옹... 감사합니다...


p,q = 1796360473659570891671495336244551, 17963604736595708916714953362445519


이제 p,q를 구했으니 개인키 d를 구하면 되겠다. 이 때 좋은 툴 rsatool 이 있다. 이걸 활용하자.

아 그놈의 gmpy... 다른 서버로 가야겠다.



n =

13269dc2680bc64277889dc6a101ed6f13dd07498f13a4818474c2069


e = 65537 (0x10001)


d = 24628356329157132106384879910356205355957782278135706168828095323773

(0xe9dc37c53f2e09f6c21dde172931a8e35ec454f10fb39c15a38f5e7d)


p = 1796360473659570891671495336244551 (0x589141bcf7bfd38312fcb363b547)


q = 17963604736595708916714953362445519 (0x375ac9161ad7e431ebddf01e514cf)


구할건 다 구했다.


text.txt에 있는 값들이 base64인코딩되있으니 디코딩해주자.


echo "AGRPJtAkcHxM5h9RiMMECc9KdKeXRuVvP5XlgsI=" | base64 -d | openssl rsautl -keyform PEM -inkey private.pem -decrypt

echo "AAqhlINL/9sBf80jq9qgdHO+yXR1O0zyljGDzCo=" | base64 -d | openssl rsautl -keyform PEM -inkey private.pem -decrypt

echo "AIV/vkErNAGt0j37090nxhiwwQyjtXcDugLTKDE=" | base64 -d | openssl rsautl -keyform PEM -inkey private.pem -decrypt


뭐가 출력되는지 보자



좀 엉망이지만... 순서를 조금 정리해보자.


flag{u  

_n00b}

n0_10ng3r


flag{un0_10ng3r_n00b} 인것 같다... 굿!

저작자표시

'Write-up > Crypto' 카테고리의 다른 글

[MeePwnCTF 2018] ezchallz  (0) 2018.07.16
[UIUCTF 2018] Hastad  (0) 2018.06.02
[Plaid CTF 2018] macsh - 125  (0) 2018.05.07
[0ctf 2017] integrity - 75p  (0) 2018.05.02
[Byte Bandits CTF 2018] R u Ronald Rivest? 70p  (0) 2018.04.27

[Plaid CTF 2018] macsh - 125

2018. 5. 7. 10:05


 

fmac.py

macsh.py


PCTF의 125점짜리 Crypto문제이다. nc macsh.chal.pwning.xxx 64791 로 접속하면

사용자로부터 무언가를 입력받는다. 일단 아무거나 입력해보면 그냥 죽어버린다.



주어진 소스를 통해 서버에서 무슨 일을 하고 있는지 알 수 있다.

fmac.py는 keygen과 AES암호화로 암호하시키는 코드이고 macsh.py가 서버에서 정말로 하는 일이다. 코드를 보자


  • macsh.py

1
2
3
4
5
6
7
8
9
10
11
while True:
    print("|$|> ", end='', flush=True)
    mac, cmdline = input().split('<|>')
    cmd, *args = cmdline.split()
    if cmd not in commands:
        print("macsh: {}: command not found".format(cmd))
        continue
    if cmd == "tag" or bytes.hex(fmac(k0, k1, encode(cmdline))) == mac:
        eval(cmd)(*args)
    else:
        print("macsh: bad tag")
cs


사용자로부터 입력을 받아 <|>를 기준으로 mac과 cmdline으로 나누어준다.

그 후 cmdline을 또 공백을 기준으로 나누어 cmd와 args로 나눈다.

    mac, cmdline = input().split('<|>')
    cmd, *args = cmdline.split()


그 후 cmd가 commands에 포함되어 있는지 검사한다. commands에는 아래 명령들이 포함되어있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
commands = [
    "echo",
    "tag"
]
 
privileged = {
    "pwd",
    "cd",
    "ls",
    "cat"
}
 
commands.extend(privileged)
cs


즉 우리는 cmd값으로 echo, tag, pwd, cd, ls, cat 을 사용할 수 있다.

여기 cmd를 eval을 통해 argv값을 너헝 실행해주는데, 조건이 있다.


    if cmd == "tag" or bytes.hex(fmac(k0, k1, encode(cmdline))) == mac:
        eval(cmd)(*args)


1. cmd == "tag"

2. crypt(cmdline) == mac


여기서 cmd가 tag이면 항상 tag를 실행하므로 두번째조건인 mac과 cmdline를 암호화한 것이 같으면 cmd를 원하는대로 설정해서 사용할 수 있을 것이다.


그럼 tag가 무엇을 해주느냐?


1
2
3
4
5
6
def tag(cmd, *args):
    if cmd not in privileged:
        cmdline = encode(" ".join([cmd] + list(args)))
        print(bytes.hex(fmac(k0, k1, cmdline)))
    else:
        print("macsh: tag: Permission denied")
cs


cmd가 echo이거나 tag일때만 실행되어 tag뒷부분을 cmdline으로 해서 fmac으로 암호화해서 돌려준다.

그러므로 아래와 같이 하면 echo가 실행되는 것을 알 수 있다.



tag echo AAAA

-> bytes.hex(fmac(k0, k1, "echo AAAA"))


이제 fmac의 암호화부분을 살펴보자.

1
2
3
4
5
6
7
def f(k0, i):
    return to_block(rot(to_int(k0), i % (8 * N)))
 
def fmac(k0, k1, m):
    C = AES.new(k1, AES.MODE_ECB)
    bs = [C.encrypt(xor(b, f(k0, i))) for i,b in enumerate(to_blocks(m))]
    return reduce(xor, bs, b"\x00" * N)
cs


암호화는 m을 블록으로 나누어 각 블록을 순서대로 암호화한다. 

이 때 key를 블록의 index만큼 rotation해서 암호화를 진행하고 암호화된 m의 블록들을 모두 xor하여 그 값을 반환한다. 


key가 계속 로테이션하면서 변하지만 rot(to_int(k0), i % (8 * N))이므로 (N=16)

1번째 블록과 129번째 블록은 키가 같게 된다. 이걸 이용해서 이제 문제를 풀 수가 있다.


  1. Enc(BLOCK_A | MyCommand | len(BLOCK_A | MyCommand) | padding)

  2. Enc(tagCommand | len(tagCommand) | padding)

  3. Enc(BLOCK_A | tagCommand | len(BLOCK_A | tagCommand) | padding)

참고로 블록들은 뒤에 입력에 들어간 cmdline의 길이를 붙이고 padding은 PKCS#7으로 된다.

이제 저 1,2,3을 tag명령을 통해 구하여 XOR하게 되면, 먼저 1^3이 되서 len부터 뒷부분이 모두 없어지고

그 후 2와 xor되서 tagCommand도 없어져 Enc(BLOCK_A | MyCommand | len(MyCommand) | padding) 를 얻게 된다.


아래를 공격코드이다.


  • xor3.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import binascii
import string
import sys
import os
 
def encode(cmdline):
    return cmdline.encode('utf-8')
 
def xor(x, y):
    return bytes([xe ^ ye for xe,ye in zip(x,y)])
    
def xor3(x,y,z):
    x=binascii.unhexlify(encode(x))
    y=binascii.unhexlify(encode(y))
    z=binascii.unhexlify(encode(z))
    res = xor(bytes(x),bytes(y))
    res = xor(bytes(res),bytes(z))
    return res
 
x=sys.argv[1]
y=sys.argv[2]
z=sys.argv[3]
 
res = xor3(x,y,z)
print(str(binascii.hexlify(res))[2:-1])
 
 
cs

  • hand_attack.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#!/usr/bin/env python
from pwn import *
import binascii
import string
import sys
import os
from subprocess import Popen, PIPE
 
conn = remote('macsh.chal.pwning.xxx', 64791)
 
BLOCK_A = "tag "+"A"*124
BLOCK_A = BLOCK_A*128
 
pwd ="/home/macsh"
flag = "flag.txt"
 
BLOCK_COMMAND=["pwd","ls /home/macsh", "cat flag.txt"]
 
for BLOCK_B in BLOCK_COMMAND:
    PAD = "A"*len(BLOCK_B)
    ##########  step.1
    print(conn.recvuntil('|$|>'))
    l="asdf<|>tag "+BLOCK_A+BLOCK_B
    conn.sendline(l)
 
    x1 = conn.recvline().strip()
    #print(x1)
    ##########  step.2
    print(conn.recvuntil('|$|>'))
    l="asdf<|>tag "+PAD
    conn.sendline(l)
 
    x2 = conn.recvline().strip()
    #print(x2)
    ##########  step.3
    print(conn.recvuntil('|$|>'))
    l="asdf<|>tag "+BLOCK_A+PAD
    conn.sendline(l)
 
    x3=conn.recvline().strip()
    command = "python3 xor.py "+x1+" "+x2+" "+x3
    popen = Popen(command, shell=True, stdout=PIPE)
    output, error = popen.communicate()
 
    output=output.strip()
    l=output+"<|>"+BLOCK_B
    print(l)
    conn.sendline(l)
    print(conn.recvline())
 
conn.interactive()
cs



PCTF{fmac_is_busted_use_PMAC_instead}


대회가 다 끝난 시점에 스샷을 찍었다. 풀었을 때 대략 40명가량이었는데 대회가 끝났을 쯤엔 100명이 넘어가 있었다...








저작자표시

'Write-up > Crypto' 카테고리의 다른 글

[UIUCTF 2018] Hastad  (0) 2018.06.02
[Byte Bandits CTF 2018]R u Ronald Rivest?  (0) 2018.06.02
[0ctf 2017] integrity - 75p  (0) 2018.05.02
[Byte Bandits CTF 2018] R u Ronald Rivest? 70p  (0) 2018.04.27
[UIUCTF 2018] xoracle (250)  (0) 2018.04.18

[0ctf 2017] integrity - 75p

2018. 5. 2. 00:06

0ctf quals 2017 : integrity

Category: Crypto Points: 75 Solves: Description:

Just a simple scheme.

nc 202.120.7.217 8221

integrity_f2ed28d6534491b42c922e7d21f59495.zip


문제가 괜찮아서 writeup을 써본다.


문제코드는 아래와 같다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#!/usr/bin/python -u
 
from Crypto.Cipher import AES
from hashlib import md5
from Crypto import Random
from signal import alarm
 
BS = 16
pad = lambda s: s + (BS - len(s) % BS) * chr(BS - len(s) % BS) 
unpad = lambda s : s[0:-ord(s[-1])]
 
 
class Scheme:
    def __init__(self,key):
        self.key = key
 
    def encrypt(self,raw):
        raw = pad(raw)
        raw = md5(raw).digest() + raw
 
        iv = Random.new().read(BS)
        cipher = AES.new(self.key,AES.MODE_CBC,iv)
 
        return ( iv + cipher.encrypt(raw) ).encode("hex")
 
    def decrypt(self,enc):
        enc = enc.decode("hex")
 
        iv = enc[:BS]
        enc = enc[BS:]
 
        cipher = AES.new(self.key,AES.MODE_CBC,iv)
        blob = cipher.decrypt(enc)
 
        checksum = blob[:BS]
        data = blob[BS:]
 
        if md5(data).digest() == checksum:
            return unpad(data)
        else:
            return
 
key = Random.new().read(BS)
scheme = Scheme(key)
 
flag = open("flag",'r').readline()
alarm(30)
 
print "Welcome to 0CTF encryption service!"
while True:
    print "Please [r]egister or [l]ogin"
    cmd = raw_input()
 
    if not cmd:
        break
 
    if cmd[0]=='r' :
        name = raw_input().strip()
 
        if(len(name) > 32):
            print "username too long!"
            break
        if pad(name) == pad("admin"):
            print "You cannot use this name!"
            break
        else:
            print "Here is your secret:"
            print scheme.encrypt(name)
 
 
    elif cmd[0]=='l':
        data = raw_input().strip()
        name = scheme.decrypt(data)
 
        if name == "admin":
            print "Welcome admin!"
            print flag
        else:
            print "Welcome %s!" % name
    else:
        print "Unknown cmd!"
        break
 
 
 
cs


AES로 암호화하는데 CBC모드를 이용한다. CBC모드란?


CBC모드는 랜덤하게 생성된 IV으로 첫 블록을 암호화시킨 암호문을 다음 블록의 암호화에 사용한다. 


CBC encryption.svg

CBC decryption.svg

If the first block has index 1, the mathematical formula for CBC encryption is

while the mathematical formula for CBC decryption is



그런데 여기 문제에서는 secret값의 IV || encrypted형식이고 encrypted는 md5(pad(username)) || pad(username)이다.


CBC모드는 IV로 블록을 암호화한 암호문을 다음 블록을 암호화하는데 쓰이므로, IV를 떼어낸 encrypted만 보내면 encrypted의 첫 블록을 IV로 사용하여 나머지 블록들은 모두 복호화가 될 것 이다.


우리가 이 값 md5(pad("admin")).digest() || admin을 username으로 보내면 


IV || enc(real md5) || enc(admin md5) || enc(admin).  이렇게 값이 돌아올 것이다. 


+---------+------------------------+--------------------+---------------+
|   IV    | Enc(md5(admin)||admin) |   Enc(md5(admin))  |   Enc(admin)  |
+---------+------------------------+--------------------+---------------+


md5가 128bit이고 암호화 블록사이즈를 128bit로 해서 이런 암호문을 얻을 수 있는 것이다.


여기서 우리가 필요한 값은 admin을 복호화시키는 것 뿐이므로 IV와 첫암호화블록 C1을 빼버린 값을 보낸다면


Enc(md5(admin))값이 IV로 들어가서 Enc(admin)을 복호화하여 admin만 남게 될 것이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from pwn import *
from hashlib import md5
 
BS = 16
pad = lambda s: s + (BS - len(s) % BS) * chr(BS - len(s) % BS) 
unpad = lambda s : s[0:-ord(s[-1])]
 
 
name = md5(pad("admin")).digest() + "admin"
 
r = remote("202.120.7.217", 8221)
 
r.sendlineafter("or [l]ogin\n", "r")
r.sendline(name)
r.recvuntil("secret:\n")
secret = r.recvline().strip()
 
r.sendlineafter("or [l]ogin\n", "l")
r.sendline(secret[32:])
r.interactive()
cs



저작자표시

'Write-up > Crypto' 카테고리의 다른 글

[Byte Bandits CTF 2018]R u Ronald Rivest?  (0) 2018.06.02
[Plaid CTF 2018] macsh - 125  (0) 2018.05.07
[Byte Bandits CTF 2018] R u Ronald Rivest? 70p  (0) 2018.04.27
[UIUCTF 2018] xoracle (250)  (0) 2018.04.18
[TyokoWesterns] My Simple Cipher[75]  (0) 2017.09.02

[Byte Bandits CTF 2018] R u Ronald Rivest? 70p

2018. 4. 27. 18:59

출처는 내 블로그...


여기서 따로 떼어내가져와보았다.


ByteBanditsCTF 2018 전체 writeup



[Crypto]R u Ronald Rivest? 70p



문제이름은 Are you Ronald Rivest?이다. Ronald Rivest가 누구지? 하고 검색해보았다.


RSA 암호 체계를 발명하신 분이다. 왠지 문제와 엄청 관계있을것같다.


이제 문제에서 주어진 파일을 보자.


text.txt 파일과 lol_pub.pem 파일이 주어진다. 

이 pem포맷파일은 문제이름에 나오는 RSA창시자 이름을 볼 때 RSA 공개키파일로 추측된다.

각각을 살펴보면 아래와 같다.


------------------------------------------------------------------------------------------------------------------------

PEM(Privacy-enhanced Electronic Mail)


여기서 준 lol_pub.pem 파일은 이름에서 유추해볼때 public_key파일이라는 것과 파일을 열어봤을때 첫줄과 마지막에 보이는 PUBLIC KEY로 이 파일이 공개키파일임을 알 수 있다.

RSA에서 쓰이는 공개키는 숫자인데, base64로 인코딩된 듯한 문자와 위아래로 텍스트 문자열(-----public ----)이 들어가 있다.

이러한 형태를 띄고 있는 파일은 PEM(Privacy Enhanced Mail) 포맷 파일로, 공개키를 암호화한 파일이다.


openssl을 이용해 개인키 및 공개키를 생성하면 위와 같은 파일을 자주 볼 수 있다.



비교해보기 위해 임의로 mykey.pem을 생성해보았다.


같은 형식인 걸 알 수 있었다.


그럼 openssl로 분석해볼까.. -noout -text 옵션으로 PEM 인코딩된 인증서를 파싱해서 정보를 출력해보겟다.



n = 225bit이고 e=65537인것을 알 수 있다. 

n을 좀 더 숫자로 표현해서 보고 싶다면 방법이 있다. ( https://stackoverflow.com/questions/3116907/rsa-get-exponent-and-modulus-given-a-public-key )


PUBKEY=`grep -v -- ----- lol_pub.pem | tr -d '\n'`  
echo $PUBKEY | base64 -d | openssl asn1parse -inform DER -i


환경변수로 문자열을 파싱하고 base64 디코딩해 openssl을 통해 정보를 읽는다.



n이랑 e가 BIT STRING, offset 17에 들어있ㄷ. -strparse을 추가해서 파싱해주자.



n=0x013269DC2680BC64277889DC6A101ED6F13DD07498F13A4818474C2069

(32269109513264378873151120068074444086989044741418671122338798116969)

e=0x10001 (65537)


n을 찾았다!!


이제 소인수 분해를 하면 되겠다. 이 때 좋은 사이트가 있다는 것을 알았다.


FatorDB : http://factordb.com/    


이 사이트에 넣으면 만약 DB에 이미 소인수분해한 값이 있다면 그대로 알려준다. 매우 좋은 사이트다...!!



오옹... 감사합니다...


p,q = 1796360473659570891671495336244551, 17963604736595708916714953362445519


이제 p,q를 구했으니 개인키 d를 구하면 되겠다. 이 때 좋은 툴 rsatool 이 있다. 이걸 활용하자.

아 그놈의 gmpy... 다른 서버로 가야겠다.



n =

13269dc2680bc64277889dc6a101ed6f13dd07498f13a4818474c2069


e = 65537 (0x10001)


d = 24628356329157132106384879910356205355957782278135706168828095323773

(0xe9dc37c53f2e09f6c21dde172931a8e35ec454f10fb39c15a38f5e7d)


p = 1796360473659570891671495336244551 (0x589141bcf7bfd38312fcb363b547)


q = 17963604736595708916714953362445519 (0x375ac9161ad7e431ebddf01e514cf)


구할건 다 구했다.


text.txt에 있는 값들이 base64인코딩되있으니 디코딩해주자.


echo "AGRPJtAkcHxM5h9RiMMECc9KdKeXRuVvP5XlgsI=" | base64 -d | openssl rsautl -keyform PEM -inkey private.pem -decrypt

echo "AAqhlINL/9sBf80jq9qgdHO+yXR1O0zyljGDzCo=" | base64 -d | openssl rsautl -keyform PEM -inkey private.pem -decrypt

echo "AIV/vkErNAGt0j37090nxhiwwQyjtXcDugLTKDE=" | base64 -d | openssl rsautl -keyform PEM -inkey private.pem -decrypt


뭐가 출력되는지 보자



좀 엉망이지만... 순서를 조금 정리해보자.


flag{u  

_n00b}

n0_10ng3r


flag{un0_10ng3r_n00b} 인것 같다... 굿!

저작자표시

'Write-up > Crypto' 카테고리의 다른 글

[Plaid CTF 2018] macsh - 125  (0) 2018.05.07
[0ctf 2017] integrity - 75p  (0) 2018.05.02
[UIUCTF 2018] xoracle (250)  (0) 2018.04.18
[TyokoWesterns] My Simple Cipher[75]  (0) 2017.09.02
[anstromCTF 2017] Knock Knock  (0) 2017.04.25

[UIUCTF 2018] xoracle (250)

2018. 4. 18. 19:35

이번 UIUCTF에서 못다푼 xoracle을 이번에 다시 한번 풀어보기로 했다.


이미 서버가 닫혀버렸으므로 가상서버에서 구축하여서 다시 풀어보기로 하였다.

(서버구축에 관한 내용은 이쪽 참고)


참고로 파이썬은 이렇게 추가해줘야한다.


service xoracle
{
          disable         = no
          flags           = REUSE
          socket_type     = stream
          protocol        = tcp
          wait            = no
          user            = sherlock
          server          = /usr/bin/python3
          server_args     = /home/sherlock/workstation/2018_CTF/UIUCTF/xoracle/xoracle.py
}
 
cs

xoracle ● Crypto ● 250 Points


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#!/usr/bin/env python3
from random import randint
from base64 import b64encode
 
def xor(data, key):
    out = b''
    for n in range(len(data)):
        out += bytes([data[n] ^ key[n % len(key)]])
    return out
 
def randkey():
    key = b''
    for n in range(randint(128, 255)):
        key += bytes([randint(0, 255)])
    return key
 
if __name__ == "__main__":
    with open('flag', 'rb') as f:
        data = f.read()
    print(b64encode(xor(data, randkey())).decode("utf-8"))
cs




두사람 writeup에 차이가 나는 이유를 알았다.


writeup1에서는 주어진 암호문의 해독한 길이를 1536으로 보았다. (실제로 서버에서 1536의 길이만 받은것같다.)[각주:1]


writeup2에서는 주어진 암호문을 해독하여 나온 길이를 2039로 본다.(나도 복호화한 결과 길이가 2039였다.)


그래서 결과적으로 w1과 w2에서 서로 조금씩 다른 파일들을 해독하였고... w2에 있는 분이 더 정확한 파일을 얻게된것이다.


나는 w1의 것을 w2의 2039를 받는것으로 해서 writeup을 재구성해보겠다.


먼저 이론을 다시 한번 정리하면 아래와 같다.


Solution

  1.  먼저 키를 모르고 암호문인 C만 알고 있을 때, 여기서 키만 남기고 이 키의 길이를 어떻게 정의하느냐를 알아야한다.

nc를 통해서 받게 되는 암호문 C를 base64로 복호화해보면 길이가 2039인것을 알 수 있다. 그리고 중요한 키 K의 길이는 128~255의 범위에 있고 만약 우리가 같은 길이를 가진 키 k1과 k2가 반복되어 얻어진 OTP인 K1와 K2로 암호화된 C1, C2를 가지고 있다면 키 길이를 유추할 수 가 있다.(키값은 서로 다르다, 같은것은 길이 뿐)



K1 XOR K2 은 2039길이를 가지고 있고, 이 안에는 128-255 의 길이를 가지는 k1 XOR k2가 반복되어지고 있을 것이다.

그러므로 우리는 다음 파이썬 코드를 가지고 키길이가 각각 128-255인 암호문을 128개 얻을 수 있다.


from base64 import b64decode
from socket import socket
 
ADDR = 'localhost', 7777
KEY_LEN = 128
 
def get_msg():
    while True:
        with socket() as s:
            s.connect(ADDR)
            msg = b64decode(s.recv(3000))
        if len(msg) == 2039:
            return msg
 
def xor_bytetrings(a, b):
    return bytes((x^y for x,y in zip(a,b)))
 
def find_msgs():
    msgs ={get_msg()}
    needed = set(range(128))
 
    while needed:
        print(len(msgs), needed)
        new_msg = get_msg()
        for msg in list(msgs):
            xor_key = xor_bytetrings(new_msg, msg)
            good_part, last_part = xor_key[:KEY_LEN], xor_key[KEY_LEN:]
 
            if good_part in last_part:
                i = last_part.index(good_part)
                print('\t', i)
                if i in needed:
                    yield (i+KEY_LEN, new_msg)
                    needed -= {i}
                    msgs -= {msg}
                    continue
        msgs.add(new_msg)
 
if __name__ == "__main__":
### STEP 1. find key_length and Save
    for i, text in find_msgs():
        with open('key_{0:0>3}_c'.format(i), 'wb') as f:
            f.write(text)
 
# yeild : http://kkamikoon.tistory.com/90  , https://dojang.io/mod/page/view.php?id=1119
 
 
cs


  1. 자 이제 우리는 암호문 C와 그 암호화에 쓰인 키 K의 길이를 알고 있다. 키 길이를 len이라고 할 때 암호문 C를 len길이씩 짤라서 n개의 블록과 M을 len으로 나눈 n개의 블록 다음과 같이 표시 할 수 있다.


그리고 이 연산 c1 xor c2를 통해 키 K를 암호문에서 제거하여 평문 m블록의 연산으로만 바꿀수 있다. 이것이 키 길이를 알 때, 바로 암호문의 자신들끼리 곱하여 암호문에서 키를 소거하는 방법이다.

  1. 이제 키 길이가 서로 1차이가 나는 암호문 C1 과 C2 를 가져오자. 이 들의 키를 각각 K1,K2  [|K1-K2|=1이다.  여기서 기억할 것은 우리가 XOR할 것은 M의 블록이란 것이다.
키 길이가 3인 C1과 키 길이가 4인 C2가 있다. 
c11 xor c12 = m11 xor m12 
c21 xor c22 = m21 xor m22 인것을 잊지말자.


위와 같이 계산되는 것이다! 키 길이가 1다른 것을 이용하여

M[1]^M[4]인 부분을 키길이가 3인 H1에서 가져오고, M[0]^M[4]인 부분을 키길이가 4인 H2에서 가져와

그 둘의 XOR결과로 M[0]^M[1]을 구할 수 있는 것이다. 

이 계산을 키 길이 128인 C1을 base로 두고 키길이가 각각 1,2,3,4,5씩 차이나는 C들을 가져와 위와 같은 계산을 하면 우리는 결국   M[0] XOR M[i] for all i in [1,128] 을 계산할 수 있다. (M[1]~M[127])

  1. 이제 첫 평문 바이트 M[0]를 BruteForce를 통해 나머지 M[1]~M[127]을 구할 수 있고, 이 값을 이용해 키 길이가 128인 암호문과 XOR을 통해 128길이 키 K를 복구하여 평문메세지를 복호화할 수 있다.

import os
 
KEY_LEN = 128
FILE_LEN = 2039
 
def xor_bytetrings(a, b):
    return bytes((x^y for x,y in zip(a,b)))
 
def key2039_gen(key):
    key = key*(FILE_LEN // KEY_LEN)
    key += key[:FILE_LEN % KEY_LEN]
    return key
    
if __name__ == "__main__":
### STEP 2. Xor M1, M2 AND Genearte M[0]^M[i] (i=range(1,128)
    res = [0]
    with open('key_128_c', 'rb') as f: 
        original = f.read()
    
    for i in range(1,128):
        idx=i+KEY_LEN
        with open('key_{0:0>3}_c'.format(idx), 'rb') as f: 
            shifted = f.read()
        
        or_blocks = [original[KEY_LEN*x:KEY_LEN*(x+1)] for x in range(0,2)]
        sh_blocks = [shifted[(KEY_LEN+i)*x:(KEY_LEN+i)*(x+1)] for x in range(0,2)]
 
        H1 = xor_bytetrings(*or_blocks)
        H2 = xor_bytetrings(*sh_blocks)
 
        res.append(H1[i] ^ H2[0])
 
### STEP 3. Bruteforce M[0]
    for m0 in range(256):
        msg_first = [m0^x for x in res]
        key = xor_bytetrings(msg_first, original)
        key = key2039_gen(key);
        
        flag = xor_bytetrings(key, original)
        with open('flag_{0:0>3}'.format(m0), 'wb') as f:
            f.write(flag)
 
### STEP 4. file operation AND Find Real FLAG!
    for m0 in range(256):
        os.system('file flag_{0:0>3} | grep -v ": data"'.format(m0))
 
 
 
 
cs

위 코드를 실행하면 아래와 같이 나온다.


flag_number에서 number은 M[0], 즉 첫바이트를 저값으로 하였을 때 나온 키값으로 복호화했을 때

파일 시그니처로 이렇다는 것이다.


만일 flag가 텍스트 파일이라면 아래와 같이 나온다.


sherlock@ubuntu:~/workstation/2018_CTF/UIUCTF/xoracle/my_writeup$ echo "hello world" > test
sherlock@ubuntu:~/workstation/2018_CTF/UIUCTF/xoracle/my_writeup$ file test
test: ASCII text
cs

여기서 file 명령어를 통해 분석해본 결과로서 flag는 텍스트 파일이 아닌것같다.
가장 가능성있어보이는 것으로는 Zip archive data이나, 일단 한번 헥스값으로 비교해보겠다.


다른 파일들은 다 쓰레기값인것 같지만 flag_080은 뭔가 제대로된 파일헤더가 보인다. PK가 보이니 압축파일이겠고 또 f.bmp라는 문구도 보인다.


한번 unzip해보겠다.



CRC값이 다르다고 오류가 뜨긴하지만 성공적으로 f.bmp가 추출된것을 볼 수 있다.




성공~~ 굿... 굉장히 좋은 문제였다고 생각한다. 물론 CTF 당일에 풀었다면 정말 좋았겠지만..ㅠ


flag.zip



  1. writeup1에서 풀이해주신분이 실수하신게 있다. 소스를 확인해보니 서버로 부터 recv(2<<10)를 하는데, 서버가 주는 문자열은 2800자 정도된다. 물론 그 문자열이 base64인코딩되어있어 이를 디코딩하게 되면 2039자가 나온다. 아마 여기서 헷갈리셔서 2<<10=2048자만 받으신거같다. 그래서 서버가 주는 문자열 2800자중에 2048만 받아가게 되어 파일크기가 1536이 된것같다. [본문으로]
저작자표시

'Write-up > Crypto' 카테고리의 다른 글

[0ctf 2017] integrity - 75p  (0) 2018.05.02
[Byte Bandits CTF 2018] R u Ronald Rivest? 70p  (0) 2018.04.27
[TyokoWesterns] My Simple Cipher[75]  (0) 2017.09.02
[anstromCTF 2017] Knock Knock  (0) 2017.04.25
[anstromCTF 2017] Descriptions  (2) 2017.04.25

+ Recent posts

티스토리툴바