[BalsnCTF2020] babyrev

주어진 zip파일 해제해보면 JVM 클래프 파일이 몇개 있었고, 이것들을 디컴파일해서 Scala로 짜여진 걸 발견했다. 그러고 주어진 코드를 약간 간단히 만들어 보았다.

object babyrev {
    def anon(a:Stream[Int], What:Seq[Seq[Int]]): Stream[Int] = {
        return a.sum #:: anon(a.flatMap(What), What)
    }

    def Main(args:Array[String]): Uint = {
        var What = Seq{Seq{0, 1, 2, 3}, Seq{0}, Seq{0}, Seq{0}}
        this.broken = anon(Stream({0}), What);
    }

    def Run() = {
        var a = ...
        var b = BigInt(broken.apply(60107) % Math.pow(2, 62)).toByteArray()
        var flag = ObjectRef.create("")
        0.to(a.length).forEach(i => {
            flag[i] = (char)(byte)(a[i] ^ b[i % b.length])
        })
            
        println("The flag is BALSN{" + flag + "}")
    }
}

Main 함수를 보면, a 배열은 ...로 초기화했고, b 배열은 broken.apply(60107) % pow(2, 62) 값으로 초기화되었다.

그리고 bitwise-xor은 a와 b에서 작동되고 flag를 만들어낸다고 한다. 

Broken에서는, Seq가 파라미터로 flatMap에 통과되는 것이 이상해보인다. 그래도 일단 Scastie에서 실행했다.

 

이렇게 나온 b.apply의 각 출력값들은

def anon(a:Stream[Int], What:Seq[Seq[Int]]): Stream[Int] = {
    return a.sum #:: anon(a.flatMap(What), What)
}

b.apply(1)
b.apply(2)
b.apply(3)
b.apply(4)
b.apply(5)
b.apply(6)
b.apply(7)
b.apply(8)
b.apply(9)
...

이렇게 나와야한다.

6
6
24
42
114
240
582
1302
3048
6954
...

 

그러면, 우리는 각 항을 3으로 반복적으로 나누어 패턴을 찾고 그 차이를 계산하여 새로운 시퀀스를 얻을 수 있다.

By obeservation, there is a sequence S = <a_n> = {1, 1, 4, 7, 19, 40, ...} and we are able to write down its recursive formula

더 살펴보면, S = <a_n> = {1, 1, 4, 7, 19, 40, ...} 이런식으로 이루어 지는 것을 알 수 있고, 이를 이용해 재귀 공식을 이용해 문제를 풀 수 있을 것 같다.

• a[n] = a[n-1] + 3 * a[n-2]
• a[1] = 1
• a[2] = 1

=> f(x) = 6 * a[x]

 

해결 코드를 python으로 짤 수 있다. 

S = [1]*70000

def f(x): return 6 * S[x]

for i in range(3, 60110):
    S[i] = S[i-1] + 3*S[i-2]

a = [71, 20, -82, 84, -45, -4, 25, -122, 77, 63, -107, 13, -111, -43, 43, -42, 96, 38, -88, 20, -67, -40, 79, -108, 77, 8, -75, 80, -45, -69, 25, -116, 117, 106, -36, 69, -67, -35, 79, -114, 113, 36, -112, 87, -67, -2, 19, -67, 80, 42, -111, 23, -116, -55, 40, -92, 77, 121, -51, 86, -46, -85, 93]
b = (f(60107) % 2**62).to_bytes(length=8, byteorder='big')

for i in range(len(a)):
    print(chr((a[i] ^ b[i % len(b)]) & 0xFF), end="")

출처: github.com/10secTW/ctf-writeup/blob/master/2020/BalsnCTF/babyrev/babyrev_en.md

10secTW/ctf-writeup