Be myself :: '전체' 카테고리의 글 목록

달력

092017  이전 다음

  •  
  •  
  •  
  •  
  •  
  • 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

간단한 dp문제이다. 길이가 N일떄 마지막 숫자를 하나의 상태로 두고 이차원 배열로 만들어서 상태dp로 풀어준다. 그래서 결과 값은 dp[N][i] (i는 0~9까지)값을 모두 더한 값이 되겠다.

코드도 단순하다.


#include <stdio.h>
#include <iostream>
using namespace std;

int dp[1001][10];
int main()
{
	int N;
	int ans = 0;
	scanf("%d", &N);
	dp[1][0] = 1;
	for (int i = 1; i <= 9; i++)
	{
		dp[1][i] = 1;
	}
	
	for (int i = 2; i <= N; i++)
	{
		for (int j = 0; j <= 9; j++)
		{
			for (int k = j; k >= 0; k--)
			{
				dp[i][j] +=  (dp[i-1][k]) % 10007;
			}
		}
	}
	
	for (int i = 0; i <= 9; i++)
	{
		ans += (dp[N][i]) % 10007;
	}
	printf("%d\n", ans % 10007);
	return 0;
}
신고

'Algorithm' 카테고리의 다른 글

[baekjoon 11057]오르막 수  (0) 2017.08.12
[baekjoon 11727] 2*n타일링2  (0) 2017.08.11
Posted by flack3r

간단하게 상태dp로 풀어줍니다.

n일 때, 하나의 칸의 상태는 총 4가지 입니다.  1) 비어있는 경우 , 2) 위에 칸이 채워진 경우 3) 아래 칸이 채워진 경우 4) 모두 채워진 경우

규칙을 찾으면 다음과 같습니다. (n일떄 n-1은 모두 채워야 합니다. 왜냐하면 사용 가능한 타일이 2*1, 2*2 뿐이기 때문에 n-1을 모두 채우지 않으면 n+1에서 채울 수가 없습니다.)

위와 같이 규칙을 찾을 수 있습니다. 위를 토대로 코드를 짜면 다음과 같습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

int dp[1001][4] = { 0, };
int main()
{
	int N;
	scanf("%d", &N);
	dp[1][0] = 1;
	dp[1][1] = 1;
	dp[1][2] = 1;
	dp[1][3] = 1;
	
	for (int i = 2; i <= N; i++)
	{
		dp[i][0] = dp[i - 1][3] % 10007;
		dp[i][1] = dp[i - 1][2] % 10007;
		dp[i][2] = dp[i - 1][1] % 10007;
		dp[i][3] = ((dp[i - 1][0] * 2) % 10007 + dp[i - 1][3]) % 10007;
	}

	printf("%d\n", dp[N][3] % 10007);
	return 0;
}

신고

'Algorithm' 카테고리의 다른 글

[baekjoon 11057]오르막 수  (0) 2017.08.12
[baekjoon 11727] 2*n타일링2  (0) 2017.08.11
Posted by flack3r

Recently i am interested in crypto. so I enjoyed this challenge a lot.

Look at the problem below

enc27.py

If you look at enc27.py, you can see it's xor encryption. and 24 byte block padding.

png file is encrypted with key( original_png ^ key ) And as you know, A xor A = 0. so if we know original_png. then we can find key. I checked png sample files and file signature to figure out key. and enc27.py is padding 24 bit message block and xoring with key i guess key length is 24. So if I xor between png file signature and encrypted png,  it would reveals padding value..

Do it.

import itertools

def xoring(m1,m2):
	return ''.join(chr(ord(a)^ord(b)) for a,b in zip(m1,m2))

def decrypt(enc, key):
	key = itertools.cycle(key)
	dec = ''.join(chr(ord(a) ^ ord(b)) for a,b in zip(key,enc))
	return dec
	
def main():
	f = open("BITSCTFfullhd.png","r")
	f2 = open("tmp.png","wb")
	buf = f.read()

	#png signature
	png = "\x89\x50\x4E\x47\x0D\x0A\x1A\x0A\x00"
	
	key = xoring(buf[:9],png)	
	#unkown key
	key += "A"*(24-9)

	dec = decrypt(buf,key)
	f2.write(dec)

	f.close()
	f2.close()
		

if __name__ == '__main__':
	main()


we know 9 bytes key. And first 9 byte from each 24 byte of block was decrypted. You can see that "\x13" is repeated 4 times. Yeah~ padding value is "\x13". "\x13"*(15)^enc[-15:] would reveal left key values.

import itertools

def xoring(m1,m2):
	return ''.join(chr(ord(a)^ord(b)) for a,b in zip(m1,m2))

def decrypt(enc, key):
	key = itertools.cycle(key)
	dec = ''.join(chr(ord(a) ^ ord(b)) for a,b in zip(key,enc))
	return dec
	
def main():
	f = open("BITSCTFfullhd.png","r")
	f2 = open("tmp.png","wb")
	buf = f.read()

	#png signature
	png = "\x89\x50\x4E\x47\x0D\x0A\x1A\x0A\x00"
	
	key = xoring(buf[:9],png)	
	key += xoring(buf[-15:], "\x13"*15)

	dec = decrypt(buf,key)
	f2.write(dec)

	f.close()
	f2.close()
		

if __name__ == '__main__':
	main()

flag is BITSCTF{p_en_gee}

신고

'crypto' 카테고리의 다른 글

[BCTF 2017]Beginner's luck (crypto 40)  (0) 2017.02.05
[picoctf 2015]Repeated XOR  (4) 2015.11.20
확장된 유클리드  (0) 2015.05.07
암호 공격방법  (0) 2015.04.25
[펌]python hashlib  (0) 2015.03.21
전반적인 암호화  (0) 2015.02.26
Posted by flack3r

[pwnable.kr]asm

2017.01.08 19:33

보호되어 있는 글입니다.
내용을 보시려면 비밀번호를 입력하세요.

[pwnable.kr]unlink

2017.01.08 12:43

보호되어 있는 글입니다.
내용을 보시려면 비밀번호를 입력하세요.

[pwnable.kr]sudoku

2016.07.15 20:12

보호되어 있는 글입니다.
내용을 보시려면 비밀번호를 입력하세요.

StudyAid

project 2016.02.13 01:53


StudyAid.zip

그냥 심심풀이로 간간히 만든 프로그램. 



끄면 위와 같이 tray로 감 ㅋㅋ


네이버 켈린더를 웹뷰로 띄어주는 화면. 앱처럼 만들고 싶어서 그냥 웹뷰로 만들어봄




공부할꺼 선택하고 시간설정후 타이머 동작. 시간 끝나면 총 공부시간 xml로 저장됨. 설정전에 블로그와 연동해야하는기능이 존재(블로그 포스팅으로 총 공부시간 xml형태로 저장함. 그 후 그 포스팅을 읽어서 총 공부시간 load함)


저거랑 원래는 Winhttp.dll 에서 WinHttpConnect  같은거 후킹해서 사이트 차단기능까지 만드려 했으나.. 크롬에서 동작하지 않아서(나중에 리버싱해서 뭘 후킹해야 하는지 알아내야 겠다) 장난감 만드는건 여기서 마무리..


혹시나(그럴 사람은 없겠지만) 사용하실분은 설명서 필요하시면 댓글 달아주세요 ㅋㅋ


*소스코드 : https://github.com/flack3r/StudyAid



신고

'project' 카테고리의 다른 글

StudyAid  (2) 2016.02.13
Posted by flack3r


hypercomputer.tar.gz


PinTutorial.pdf

깔끔하게 보고 싶으신 분들은 위 pdf파일을 받아주시길..

제일 간단하게 프로그램의 Instruction을 추적하는 Pintool을 만들어 보겠다. Pintool을 만든다는 것은 Pin의 플러그인을 만든다는 느낌으로 만들면 된다. Pin은 JIT의 형태로 생각하면 된다. 자세한 것은 매뉴얼을 참고하자.

[1] instruction 추적하기

일단 타겟 프로그램을 다음과 같이 작성한다.

패스워드를 입력받고 0x31337이면 cong를 출력하는 프로그램이다. 다음과 같이 Main부분의 instruction만을 뽑아오도록 간단한 핀툴을 만든다.

#include <stdio.h>
#include <iostream>
#include "pin.H"
 
using namespace std;
 
#define START 0x4005FD
#define END 0x40065F
INT32 Usage()
{
         PIN_ERROR("this pintool print a trace of memory address\n");
         return -1;
}
 
void printip(void* ip)
{
         printf("address: %p\n",ip);
}
 
void Instruction(INS ins, VOID* v)
{
         long int a = (long int)INS_Address(ins);
         if(START<=a && a<=END)
         {
                 printf("Instruction \n");
                 INS_InsertCall(ins,IPOINT_BEFORE, (AFUNPTR)printip, IARG_INST_PTR, IARG_END);
         }
}
 
void Fini(INT32 code, VOID *v)
{
         cout << "Fini code: " << code << endl;
}
 
int main(int argc,char* argv[])
{
         if(PIN_Init(argc,argv))
                 return Usage();
 
         INS_AddInstrumentFunction(Instruction,0);
         PIN_AddFiniFunction(Fini,0);
 
         PIN_StartProgram();
         return 0;
}

}

코드에 대해 설명하자면 main에서 INS_AddInstrumentFunction 함수로 각 instruction이 실행될 때 실행되는 코드를 등록한다. Instruction함수를 보면 INS_Address로 각각 instruction이 실행될 때의 주소 값을 구해 main함수 내의 instruction의 주소 값만 뽑아온다. 또 각 instruction에 대해 INS_InsertCall을 이용해 instruction이 실행되기 전에 호출되는 callback 함수를 등록한다. 여기선 printip을 등록한다 printip에 넘어가는 인자는 IARG_INST_PTR이라는 인자가 넘어가는데 매뉴얼을 참고해 보면 이건 instruction의 주소 값이다.

다음과 같이 make.rules를 변경하고 make로 컴파일해서 돌려보자.

필자는 hyper.cpp이라는 이름으로 저 소스코드를 저장하였고 따라서 위와 같이 make 룰을 변경하였다. 그 다음 make를 통해 컴파일 하자.

그리고 다음과 같이 실행시키자.(root로 실행하여야 한다.)

이것과 ida로 본 instruction을 하나하나 비교해보자

위의 결과를 비교한 결과 내릴 수 있는 결론은 다음과 같다. 0x4005fd~400611까지 한 묶음, 0x40061B~0x400627까지 한 묶음, 0x400631~0x400639까지 한 묶음…[즉 BBL단위로 묶음] 이런 식으로 routine이 분기되기 전까지 Instruction함수가 호출되고 분기되고 난 후 INS_InsertCall() 으로 등록한 printip함수가 모조리 호출된다.

[2] 비밀번호 맞추기

위와 같이 instruction의 Opcode가 CMP이면 해당 오퍼렌드의 두번 째 비교 값을 가져와서 뿌려준다. 결과는 다음과 같다.

 

#include <stdio.h>
#include <iostream>
#include "pin.H"
 
using namespace std;
 
#define START 0x4005FD
#define END 0x40065F
INT32 Usage()
{
         PIN_ERROR("this pintool print a trace of memory address\n");
         return -1;
}
 
void Instruction(INS ins, VOID* v)
{
         long int a = (long int)INS_Address(ins);
         if(START<=a && a<=END)
         {
                 if(INS_Opcode(ins) == XED_ICLASS_CMP )
                 {
                          UINT64 value = INS_OperandImmediate(ins,1);
                          printf("value is 0x%lx \n",value);
                 }
                 
         }
}
 
void Fini(INT32 code, VOID *v)
{
         cout << "Fini code: " << code << endl;
}
 
int main(int argc,char* argv[])
{
         // Pin initiate
         if(PIN_Init(argc,argv))
                 return Usage();
 
         INS_AddInstrumentFunction(Instruction,0);
         PIN_AddFiniFunction(Fini,0);
 
         PIN_StartProgram();
         return 0;
}

 

[3] [2013 Plaid ctf] hypercomputer-1(bin 100)

문제 파일을 열어보면 다음과 같다.

hello함수에서 배너를 출력하고 CalcResult에서 원래 문자열을 조작해서 flag를 만들어 둔다. CalcResult나 다른 함수들을 리버싱 하면 알겠지만 쓸대없이 usleep과 많은 while문,for문을 만나게 된다. 따라서 핀툴로 이러한 루틴을 다 없애주면 flag를 줄것이다 J 아래의 코드는 그 조작을 한 핀툴을 작성한 것.

#include "pin.H"
#include <iostream>
#include <fstream>
#include <unistd.h>
 
int new_usleep(useconds_t usec)
{
         return 0;
}
 
void Image(IMG img, void *v)
{
         for(SYM sym = IMG_RegsymHead(img); SYM_Valid(sym); sym = SYM_Next(sym))
         {
                 string funcname = PIN_UndecorateSymbolName(SYM_Name(sym),UNDECORATION_NAME_ONLY);
                 if(funcname      == "usleep")
                 {
                          RTN rtn = RTN_FindByAddress(IMG_LowAddress(img)+SYM_Value(sym));
                          if(RTN_Valid(rtn))
                          {
                                   RTN_Open(rtn);
                                   RTN_Replace(rtn, (AFUNPTR) &new_usleep);
                                   RTN_Close(rtn);
                          }
                 }
         }
}
 
void xor_rax(CONTEXT *ctx)
{
         PIN_SetContextReg(ctx, REG_RAX,0);
}
 
void mov_rax_rdx(CONTEXT* ctx)
{
         ADDRINT rdx = PIN_GetContextReg(ctx, REG_RDX);
         PIN_SetContextReg(ctx, REG_RAX, rdx);
}
 
void delete_insns(BBL bbl)
{
         for(INS ins = BBL_InsHead(bbl); INS_Valid(ins); ins = INS_Next(ins))
         {
                 INS_Delete(ins);
         }
}
 
VOID Trace(TRACE trace, VOID *v)
{
    for (BBL bbl = TRACE_BblHead(trace); BBL_Valid(bbl); bbl = BBL_Next(bbl)) {
        if(BBL_NumIns(bbl) == 2) {
            INS ins1 = BBL_InsHead(bbl);
            INS ins2 = INS_Next(ins1);
            if(INS_Disassemble(ins1) == "sub rax, 0x1" && INS_IsBranch(ins2) &&
                    INS_DirectBranchOrCallTargetAddress(ins2) == BBL_Address(bbl)) {
                BBL_InsertCall(bbl, IPOINT_BEFORE, (AFUNPTR) &xor_rax,
                    IARG_CONTEXT, IARG_END);
                delete_insns(bbl);
            }
        }
        else if(BBL_NumIns(bbl) == 3) {
            INS ins1 = BBL_InsHead(bbl);
            INS ins2 = INS_Next(ins1);
            INS ins3 = INS_Next(ins2);
            if(INS_Disassemble(ins1) == "sub rax, 0x1" && INS_IsNop(ins2) &&
                    INS_DirectBranchOrCallTargetAddress(ins3) == BBL_Address(bbl)) {
                BBL_InsertCall(bbl, IPOINT_BEFORE, (AFUNPTR) &xor_rax, IARG_CONTEXT,
                    IARG_END);
                delete_insns(bbl);
            }
            else if(INS_Disassemble(ins1) == "add rax, 0x1" &&
                    INS_Disassemble(ins2) == "cmp rax, rdx" &&
                    INS_DirectBranchOrCallTargetAddress(ins3) == BBL_Address(bbl)) {
                BBL_InsertCall(bbl, IPOINT_BEFORE, (AFUNPTR) &mov_rax_rdx, 
                    IARG_CONTEXT,IARG_END);
                delete_insns(bbl);
            }
        }
    }
}
 
int main(int argc, char* argv[])
{
         if(PIN_Init(argc,argv))
         {
                 return 0;
         }
 
         PIN_InitSymbols();
 
         IMG_AddInstrumentFunction(Image,0);
         TRACE_AddInstrumentFunction(Trace,0);
 
         PIN_StartProgram();
         return 0;}

}

실행하면 다음과 같다.

이 문제의 설명은 다음의 원문에 잘 설명되어 있다: https://eindbazen.net/2013/04/pctf-2013-hypercomputer-1-bin-100/



신고

'Analysis' 카테고리의 다른 글

PinTool을 이용한 Instruction 추적하기, 간단한 ctf 풀이  (0) 2016.01.30
Pin 기본 API살펴보기  (0) 2015.08.07
[smt solver]z3py 튜토리얼  (0) 2015.08.06
Pin tool 기본세팅  (1) 2015.07.17
Posted by flack3r

보호되어 있는 글입니다.
내용을 보시려면 비밀번호를 입력하세요.

[pwnable.kr]rsa_calculator

2016.01.26 00:01

보호되어 있는 글입니다.
내용을 보시려면 비밀번호를 입력하세요.