Classic_Blue_Note

Abex's crackme 2번 문제이다.

실행시키면 다음과 같은 창이 뜬다. 디자인이 비주얼 베이직 형태인데, 실제로 확인해본 결과 베이직으로 만들어진 언어였다.

처음에 아무 글자나 넣어서 시도해 본 결과, 틀린 시리얼이라는 창이 뜬다. 이름과 시리얼의 관계 또는 이름과 시리얼 자체를 찾아내는 것이 문제일 것이라고 예측하고, 디버깅을 시작하였다.

디버거를 통해 실행시켜 보았는데, 상태가 약간 복잡한 감이 있었다. step over를 통해 실행시켜 본 결과, 2번째 행에서 바로 프로그램이 실행되면서 별도의 디버깅이 진행되지 않았다.

그래서 해당 시스템 콜을 확인해 본 결과, 비주얼베이직에서 사용하는 api라고 한다. 해당 api는 ThuRTMain이라는 함수를 통해 메인 함수로 들어가고, 초기 세팅을 진행한 후 클릭에 따라 이벤트 기반으로 프로그램을 실행한다. 따라서 이벤트 핸들러 부분을 찾는게 필수적인데, Check 부분의 이벤트를 찾기 위해 "Nope, this serial is wrong"이라는 스트링을 기반으로 탐색을 진행했다.

 find string을 통해 해당 위치를 찾아본 결과, 00403476 부분에 해당 스트링이 존재했고, 해당 위치를 기반으로 위쪽으로 쭉 올라가 본 결과 함수가 시작하는 부분인 스택 프레임(PUSH EBP, MOV EBP ESP) 부분을 찾을 수 있었다. 해당 부분을 이벤트 핸들러라고 판단하였고, 이후 분석을 진행하였다.

쭉 분석을 진행한 결과 vbaVarTstEq라는 시스템 콜을 확인할 수 있었다. 해당 시스템 콜을 이용해서 나온 결과를 test연산한 뒤 flag 값을 저장해 두고, JE 연산을 수행하는 것을 확인할 수 있다. JE로 점프할 시 KEY가 틀렸다는 값 부분으로 점프하게 된다. 따라서, 해당 위치에서 점프를 수행하지 않도록 만들어 주는 방법이 존재한다.

그러나 필자는 해당 부분의 EAX, EDX 영역의 값을 확인해서 어떤 값을 서로 비교하는지 확인해 보는 방법으로 시리얼 넘버를 찾아보았다.

그 결과 AECDD2D9라는 값을 확인할 수 있었고, 해당 값이 곧 시리얼이었다.

시리얼 값이 생성되는 원리는 추후 추가 분석을 통해 수행해 볼 예정이다. 일단은 이정도로 클리어!

유명한 Abex's crackme 문제이다. crackme를 시작한 이유는 Pwnable을 시작하기 전, 어셈블리어에 대한 이해와 기본적인 리버싱에 대한 이해를 위해 시작했다. 시스템 콜, 스택 프레임, 어셈블리어 등 바이너리 디버깅을 통해서 얻을 수 있는 기본적인 내용에 대해 이해하고자 했다.

IDA와 같이 좋은 리버싱 도구들이 있지만, 최대한의 이해를 위해 가장 단순한 툴인 올리디버거만 사용하였다.

1번 문제 파일이다.

문제를 켜면 아래와 같은 창 하나가 반겨준다.

실행만 한번 시켜줘 봐도, 내부에서 분기문을 변경시켜 주거나, 조건을 만족시켜 주도록 프로그램을 변경해야 할 것 같다. 디버깅을 진행한다.

어셈블리 형태의 소스 코드이다. 코드 영역은 그렇게 길지 않아 분석이 쉬운 편이었다. 이중 중요한 부분은 중간의 00401026 부분의 분기문이다. JE는 바로 위의 CMP와 연동되어 움직이는데, CMP 연산을 진행하면 Zero Flag라는 레지스터의 부분이 0(거짓), 1(참)으로 변동되고, JE연산은 이 ZF를 확인해서 1이면 해당 위치로 점프하는 형식이다.

따라서 기존의 MessageBox가 아닌 다른 형태의 메시지박스를 얻기 위해서는  점프를 통해 0040103D로 가야 하고, 이를 위해서는 CMP EAX, ESI 부분이 True가 되어야 한다. 이를 위해 가장 간단한 방법으로, CMP의 operand를 변화시켰다.

이렇게 비교문을 변환해 주면, 우리가 원하는 메시지박스가 뜨는 것을 확인할 수 있다.

문제

programmers.co.kr/learn/courses/30/lessons/42885

풀이

해당 문제도 풀이 과정 자체는 떠올리기가 쉬운 편이다. 하지만 속도를 최적화하는 과정에서 오래 걸린 문제였다.

조건을 생각해 보면, 2명까지만 탑승이 가능하고, 가능한 한 적은 숫자의 보트를 보내는 것이 목표이다. 따라서 무게를 최대한 한계에 맞춰서 태워 보내는 것이 중요하다.

그래서 해당 조건을 만족하기 위해 필연적으로 탐색을 진행해야 한다. 하지만 이 탐색 과정에서, 연산을 최소한으로 사용하는 것이 목표이다.

필자는 다음과 같은 방식으로 그리디 알고리즘을 적용했다.

1. 사람을 무게 오름차순으로 배열한다.
2. 사람 배열을 순환하면서 자기 자신과 바로 앞 위치의 값을 더하면 한계보다 클 경우, 바로 멈춘다.
3. 그게 아닐 경우, rightidx라는 값을 이용한다. 이를 통해 뒤쪽 가장 큰 값부터 차례대로 자기 자신의 값과 더해서 한계보다 크지 않을 경우, 뒤쪽의 값을 리스트에서 빼내고, 이후의 반복은 빼낸 값 바로 앞의 값부터 다시 앞쪽으로 쭉 반복한다.

3번과 같이 반복하는 이유는, 소팅을 진행했기 때문에 맨 앞에는 가장 작은 값, 맨 뒤에는 가장 큰 값이 배치되게 된다. 첫번째 순환을 생각해 보자, 이때 맨 앞의 값과 맨 뒤의 값부터 차례로 앞쪽으로 가면서 비교하게 되는데, 두개의 합이 한계보다 큰 경우 그 다음 값으로 넘어가는 식으로 순환이 진행된다. 그러다 합이 한계값보다 크지 않을 경우, 해당 값을 빼낸 뒤 그 다음 순환에서는 앞쪽은 두번째 값, 뒤쪽은 빼낸 값의 바로 앞쪽 값부터 음의 방향으로 비교한다. 왜냐하면 첫번째 값보다 두번째 값이 무조건 크거나 같기 때문에, 빼낸 값보다 양의 방향에 있는 값은 굳이 비교할 필요도 없이 한계값보다 커지기 때문이다. 이러한 방식으로 앞쪽, 뒤쪽으로 포인터를 사용하였고, 이 역시 투포인터를 사용하여 값을 구하는 편이 pop연산을 사용하는 것보다 속도가 빠르지만, pop연산을 사용해서 코드가 간결해졌고, 문제가 해결되었기 때문에 이 방식을 사용하였다.

마지막에 전체에 대한 순환이 끝나면 전체 리스트의 길이를 구하는 것으로 답안을 구해주면 된다.

코드

def solution(people, limit):
    people.sort()
    rightidx = len(people)
    
    for i in range(len(people)):
        if people[i] + people[i+1] > limit:
            break
            
        while True:
            rightidx -= 1
            
            if people[i] + people[rightidx] <= limit:
                people.pop(rightidx)
                break
                
    answer = len(people)
    
    return answer

문제

programmers.co.kr/learn/courses/30/lessons/42883

풀이

조건을 간단하게 정리해 보면, 전체 숫자에서 몇 개의 숫자를 빼서 가장 큰 숫자를 만드는 게 관건이다. 그래서 필자는 우선 전체에서 숫자를 빼내는 것보다는, 전체 중 숫자들을 골라내서 가져오는 것이 알고리즘 구상에 더 용이하다고 판단하였다.

그래서 처음에 choose라는 전체 길이에서 k값만큼을 뺀, 선택해야 하는 숫자의 개수를 이용하였고, choose가 0이 되면 빠져나올 수 있도록 알고리즘을 작성하였다.

이후 반복 과정에서의 아이디어는, 뒤쪽 숫자를 모두 선택한다고 가정했을 때, 앞쪽에서 가장 큰 숫자를 고를 때가 가장 큰 값이 된다는 점이다. 이후 앞쪽에서 숫자를 고르면, 그 숫자 이후로 다시 반복을 진행하면 된다. 그러다가 고른 숫자가 앞쪽에서 맨 뒤 숫자일 경우, 그 이후의 숫자들을 모두 선택한다고 판단하면 된다. 또한 시간을 줄이기 위해, 큰 값을 선택할 때 숫자가 9가 나오는 경우에는 그 뒤쪽을 확인할 필요가 없기 때문에 바로 넘어가는 방식으로 시간을 줄여 주었다.

처음에는 pop 연산을 이용하여 프로그램을 진행했는데, pop 연산 자체가 O(n)의 시간 복잡도를 갖기 때문에, 시간 초과가 자주 일어났다. 그래서 이 시간 초과를 해결하기 위해 startidx와 endidx를 통해 투포인터 알고리즘을 적용하였다. 반복을 idx를 이용해 주고, 앞쪽 값들의 시작점과 끝점을 각각 포인팅하여 문자열의 슬라이싱 없이도 순환할 수 있도록 적용하였다.

해당 알고리즘 문제에서는 알고리즘 구상 단계에서 k를 이용해서 단순히 빼내는 것이 아니라 유효한 숫자들을 골라내는 방식으로 반대로 생각하는 것, 시간 관련해서는 pop을 사용하지 않고 투포인터를 사용하여 시간을 줄이는 것, 그리고 9가 나오는 경우 뒤쪽을 확인할 필요 없이 바로 넘어간느 방식으로 시간을 줄이는 것이 주요했다.

코드

def solution(number, k):
    answer = ''
    startidx = 0
    endidx = 0
    choose = len(number) - k
    
    while True:
        idx = -1
        endidx = len(number)-1 - (choose-1)
        
        if endidx < startidx or choose == 0:
            break
            
        elif startidx == endidx:
            answer += number[startidx:]
            break
            
        maxval = -1
        
        for i in number[startidx:endidx+1]:
            if maxval < int(i):
                maxval = int(i)
                
            if maxval == 9:
                break
                
        idx = number[startidx:endidx+1].find(str(maxval))
        answer += str(maxval)
        startidx += idx+1
        choose -= 1
        
    return answer

원본 기사

www.boannews.com/media/view.asp?idx=95751

최근 클라우드가 각광받으면서 각종 서비스 또한 클라우드에 넣어 있는 형식인 SaaS(Software as a Service)가 많이 사용되고 있다. 이는 기존에 기업이 인프라 또는 플랫폼으로 클라우드를 사용했던 것과 달리, 소프트웨어를 빌려 주는 형식으로 제공하는 것을 의미한다. 기사에서는 SaaS 방식의 운영을 "인터넷으로 쇼핑몰을 만들어 운영하고 싶은데, 관련 지식과 운영인력이 없다면, 쇼핑몰 구축부터 서버나 네트워크 등은 물론 관리까지 모두 서비스 형태(구입하는 것이 아닌 사용료를 내고 빌리는 형식)으로 사용하는 것" 이라고 말하고 있다.

이처럼 SaaS 방식의 확대는 기술이나 인력 등에 한계가 있는 중소기업에서 환영받고 있으며, 이는 보안 분야에도 역시 사용되고 있다. 안랩은 '안랩 오피스 시큐리티'라는 보안관리 솔루션을 SaaS 형식으로 출시하였고, 모비젠은 클라우드 기반 빅데이터 솔루션인 "IRIS SaaS"를 선보였으며, 포티넷과 아톤 역시 SaaS 형식의 서비스를 확장해나가고 있다. 단순히 클라우드에서의 SaaS뿐만 아니라, 소프트웨어 자체를 제공하는 형식으로 발전해나가는 것이다.

그러나 기사에서도 말했듯이, SaaS 방식을 통해 손쉽게 서비스를 사용할 수 있다는 것은, 범죄자들 역시 SaaS 방식을 이용하여 범죄를 저지를 수 있다는 점이다. 대표적인 것으로는 기사에서 언급한 RaaS(Ransomeware as a Service)가 있는데, 범죄조직이 랜섬웨어를 만든 뒤 이를 다른 범죄자들에게 대여하는 방식이다. 이 대표적인 것으로는 갠드크랩 랜섬웨어가 있다고 언급하고 있는데, 이후에도 소디노키비나 포보스, 다르마 등의 서비스형 랜섬웨어들이 존재했다.

이러한 서비스형 소프트웨어들의 발전은, 결국 추상화가 관건이다. 기사에서는 상용화된 소프트웨어들이 사용자가 더 쉽고 편리하게 사용할 수 있도록 성장해 나가면서 범죄도 같은 길을 걷는다고 언급하고 있지만, 이는 결국 추상화된 외부 구조만을 통해 범죄자가 사용하는 것이고, 내부 구조까지는 파악하기 어렵다는 것을 의미한다. 하지만 내부 구조를 파악할 수 있다면, 그리고 그 업무를 수행할 수 있는 인력이 보안 업계에 존재한다면, 유사한 소프트웨어 서비스들은 모두 파훼할 수 있다는 점과 일맥상통한다.

결국 이에 대한 대책 마련에 있어서, 범죄가 쉬워진 만큼, 더 쉽게 검거가 가능해져야 한다는 의미이다. 하지만 국내는 개발과 보안의 비대칭성으로 인해 대책을 빠르게 찾아낼 수 있을지에 대한 의문이 든다. 기사에서 언급한 것과 같이, 중고나라 안전결제 사기를 검색하면 상당한 숫자의 관련 글들을 확인할 수 있다. 그리고 기사에서 언급한 제보에 따르면, 가짜 안전거래 사이트를 만들어 호스팅하는 업체도 있다고 언급하고 있다. 이러한 상황에서, 보안에 대한 약간의 투자만 이루어진다면 이러한 사이트를 찾아내는 것은 어렵지 않을 것으로 보인다.

추가적인 문제로, 기사에서 언급한 것처럼 이를 이용한 범죄가 늘더라도 범죄를 위해 소프트웨어를 만든 이들은 잡기가 어려워진다는 문제가 존재한다. 또한 우리나라의 경우 악성코드의 유포 행위만 처벌하고 있고, 제작 행위는 별도로 정보통신망법에서 다루고 있지 않다. 1차적으로 잡는 것도 문제일 뿐더러, 잡은 뒤에 어떤 범죄로 처벌할지도 미지수라는 것이다. 따라서 이러한 서비스형 사이버범죄에 대한 전문적인 수사와 함께 처벌을 강화해야 할 필요가 있다.

문제

programmers.co.kr/learn/courses/30/lessons/42860

풀이

속을 많이 썩인 문제였다. 해당 문제도 조건이 다양한 문제로, 문제에 제시되어 있긴 하지만, 조건이 다양하면 그리디를 사용해 보면 좋다는 생각을 갖고, 조건을 정리하면서, 세 가지 경우 중 최솟값을 구하면 된다는 생각이 들었다.

1. 조이스틱으로 오른쪽으로 쭉 가는 경우
2. 조이스틱으로 왼쪽으로 쭉 가는 경우
3. 조이스틱으로 오른쪽으로 가다가 왼쪽으로 가는 경우

해당 3가지 경우를 제외하고는 없기 때문에, 셋 중 최소인 값을 구해주면 좌우로 이동하는 횟수가 계산된다.

그리고, 위아래로 움직여야 하는 경우를 계산해야 하는데, 위아래로 움직이는 경우는 각 문자마다 위로 움직이는 경우, 아래로 움직이는 경우 중 작은 값을 이용하면 된다. 해당 값을 계산하기 위해, 알파벳 문자열을 선언한 뒤, 해당 인덱스까지 가기 위해 위로 눌러야하는 횟수와 아래로 눌러야 하는 횟수를 계산하여 둘 중 작은 값을 더해주었다.

해당 문제는 좌우로 움직이는 경우의 수 중 3번째 경우를 고려하지 않고 풀이를 진행하면서 막혔었는데, 갔다가 다시 오는 경우도 있다는 것을 판단하는 게 조금 어려울 수 있다. 하지만 해당 경우를 파악한다면 금방 풀 수 있는 문제로, 갔다 오는 경우 A가 가장 많은 위치에서 전진하는 방향을 돌려야 하기 때문에, A가 가장 많은 위치를 찾아서 돌려 주었다.

코드

def solution(name):
    answer = 0
    alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    
    for i in name:
        answer += min(alphabet.index(i), 26-alphabet.index(i))
        
    mov1 = len(name.rstrip("A")) - 1    # 앞으로만 가는경우
    mov2 = len(name.lstrip("A"))        # 뒤로만 가는경우
    
    idx = 0
    n = 1
    while True:
        tmp = name.find("A"*n)
        if tmp == -1:
            break
        idx = tmp
        n += 1                      # A가 가장 많은 곳 위치 찾기
        
    mov3 = 1000000000000
    
    if idx != 0 and idx != len(name.rstrip("A"))-1:
        # A가 가장 많은 곳이 맨앞 또는 맨 뒤쪽인 경우 배제
        mov3 = (idx-1)*2 + len(name) - (idx + n - 1)    
        # A가 가장 많은 곳을 기준으로 갔다가 돌아오는 경우
        
    answer += min(mov1, mov2, mov3)
    
    return answer