루니프의 짤막보안강의 루니프의 짤막보안강의

[2021/08/26][짤막한 이야기 - K진 트리] “K진 트리(K-ary Tree)”란 일반적인 트리를 생각하면 된다. 정확한 정의는 “자식 노드가 최대 K개인 트리”를 의미한다. “이진 트리(Binary Tree)”는 K진 트리에서 K=2인 경우의 특수한 형태인 것이다. 이진 트리에서 자식 노드가 0개, 1개인 경우도 있는 것처럼, K진 트리에서도 반드시 자식 노드의 수가 K개는 아니라는 점을 유의(최대 K개이다.)하여야 한다. 2개이던 자식 노드를 K개로 늘리는 것 뿐이기 때문에 트리 자료구조의 구현 자체는 크게 달라지지 않는다. 그러나 K진 트리에서의 순회나 분석 방법은 이진 트리에서의 순회나 분석 방법과 전혀 다르기 때문에 시간 복잡도도 크게 늘어나게 된다. 여담이지만 K진 트리에서 K=1인 ..

[2021/08/25][짤막한 이야기 - 핀툴(함수반환값 변조)] 이전 포스트에서의 GetDriveTypeA의 반환값에 대하여 더 이야기해보자. GetDriveTypeA API는 하드디스크에 해당하는 레터(C:\)를 인자값으로 입력받을 경우 “3”을 반환값으로 출력하고, CD-ROM에 해당하는 레터(D:\, 혹은 다른 영문자, 컴퓨터 기종에 따라 CD-ROM이 없을 수도 있음)를 인자값으로 입력받을 경우 “5”를 반환값으로 출력한다. 앞선 포스트에서의 소스코드에 딱 한줄만 더 추가하면 GetDriveTypeA API의 반환값을 “3”에서 “5”로 변조할 수 있다. 매우 간단하지 않은가? 해당 포스트의 소스코드를 이용하여 “핀툴 적용”을 수행한다면 AbexCrackMe#1의 크랙이 수행된다. Windows..

[2021/08/24][짤막한 이야기 - 핀툴(함수반환값)] 핀툴은 프로그램을 분석하는데에도 유용하지만 이의 기능성을 변조하고 크랙하는데에도 탁월하다. 대표적으로 특정 시점에서의 "레지스터/메모리/함수인자값/함수반환값" 등을 매우 쉽게 변조할 수 있다. 그림의 어셈블리어는 매우 유명한 AbexCrackMe의 첫번째 타입의 일부이며, 이를 크랙할 수 있는 첫번째 방법은 타 블로그에서도 쉽게 확인할 수 있다. 알고있는가? 아벡스크랙미#1은 최소 7가지 이상의 방법으로 크랙할 수 있다는 것을. 그 중 하나는 GetDriveTypeA API의 함수반환값(Function Return Value)을 변조하는 것이다. 반환값을 출력하여 확인하는 핀툴 코드는 그림에 함께 작성되어 있다. EAX 레지스터에 "3"이 저장..

[2021/08/22][짤막한 이야기 - 이진 트리] “이진 트리(Binary Tree)”는 자료구조의 한 형태로 트리의 특수한 형태이다. 사각형, 직사각형, 정사각형이 포함관계인 것처럼, 이진 트리도 트리와 포함관계이다. 정확히는 그래프, 트리, 이진 트리로 생각할 수 있다. 트리는 그래프 중에서도 순환이 없고 내향 간선(Inner-Direction Edge)이 1개인 특수한 형태의 그래프이다. 또한 이진 트리는 트리 중에서도 자식 노드가 최대 2개만 존재하는 특수한 형태의 트리이다. 이진 트리는 자료구조 중에서도 특히 중요하게 여겨지는데, 앞선 포스트의 “이진 탐색(Binary Search)”처럼 해당 자료구조를 사용하면 분석에 소요되는 시간이 매우 짧기 때문이다. 정확히는 순회에 소요되는 시간이 일..

[2021/08/20][짤막한 이야기 - 콜라츠 추측] “콜라츠 추측(Collatz Conjecture)”이란, 추측이라는 글자에서 알 수 있듯이 현재까지 풀리지 않은 난제이다. 개념은 간단하다. 1) 특정 수 N이 1이라면 이 알고리즘은 종료된다. (C(1) = Exit) 2) 특정 수 N이 (1이 아닌) 홀수라면 3을 곱한 후 1을 더한다. (C(N) = 3N + 1) 3) 특정 수 N이 짝수라면 2를 나눈다. (C(N) = N / 2) 이 과정을 반복하면 유한번의 재귀를 통하여 1에 도달한다는 것이 콜라츠 추측이다. 이 추측은 아직 1로 도달하지 않는 반례가 나오지 않았기 때문에 지속적으로 반례를 찾고있으며, 반대로 항상 이것이 성립한다는 증명도 되지 않았기 때문에 난제로 불리우고 있다. 암호학에서..

[2021/08/19][짤막한 이야기 - 소수판별법] 이번 포스트에서는 “알고리즘”에서도 “암호학”에서도 매우 중요한 “소수판별법”에 대한 이야기를 하고자 한다. 가장 간단한 소수판별법은 검사대상 X를 X 미만의 숫자로 모두 나누어 보는 것이다. 즉, 103719521이 소수인지 판별하기 위해서는 2 ~ 103719520 까지 나눠 보는 것으로 시간 복잡도는 O(X)이 될 것이다. “RSA 2048”이라는 단어를 들어본 적이 있는가? 대표적인 비대칭키 암호알고리즘으로 이 때 2048은 RSA 암호알고리즘에 사용되어야 하는 공개키 N이 2048비트라는 의미이다. 공개키 N은 비밀키 P와 Q의 곱이며, P와 Q는 각각 1024비트의 소수이다. 즉, X가 두 개의 2^1024이기 때문에 랜덤한 두 수의 소수판..

[2021/08/18][짤막한 이야기 - 메모이제이션] 당신이 “알고리즘”에 전혀 관심이 없더라도 “피보나치 수열”을 한번쯤은 들어본 적이 있을 것이다. 피보나치 수열은 첫째 및 둘째 항(F1 & F2)이 1이며 셋째 항(F3)부터는 앞의 두 항의 합(F2 + F1)으로 구성되는 수열이다. 이를 점화식으로 표현하면 “F(i) = F(i-1) + F(i-2)”가 될 것인데, 간단하게 생각하면 “재귀 함수(Recursive Function)”로 구현할 수 있을 것 같다. 그런데 피보나치 수열은 매우 비효율적이다. 왜냐하면 F(7)을 구하기 위하여 F(3)을 구하는 횟수가 5번이나 되기 때문이다. 즉, “중복되는 부분 문제(Overlapping Sub Problem)”가 너무 많기 때문에 F(N)을 단순하게 ..

[2021/08/17][짤막한 이야기 - 핀툴 적용] 이전 포스트에서 생성한 핀툴을 이용하면 프로그램의 구조를 분석할 수 있다. 핀툴을 적용하기 위해서는 직접 생성한 핀툴(DLL) 이외에도 몇가지 준비물이 더 필요하며, 이는 그림에서의 위치(bin 폴더)에서 획득할 수 있다. 핀툴과 준비물, 그리고 분석 대상 프로그램을 모두 동일한 폴더에 넣은 후, 커맨드라인을 이용하여 명령어를 입력한다. “pin.exe -t [PinTool.DLL] -- [TargetProgram.exe]” 위 명령어는 [PinTool.DLL]을 이용하여 [TargetProgram.exe]를 분석하는 가장 기본적인 명령어이다. “pin.exe”는 위에서 언급한 준비물 중 하나이며, Pin이라는 가상머신 내에서 TargetProgram..