patience Writeup - Bugku CTF平台

Patience (RE, 769页)

这是一个 Haskell 逆向挑战。如果这还不让你感到害怕，那么可能意味着：

你是史上最厉害的 1338 pr0 xakep r3v3rse 工程师
你无法理解你将要目睹的恐怖程度。

无论如何，你都会获得一些真正的乐趣。事实上，我从未见过有人真正逆向（棘手的）Haskell 二进制文件——大多数挑战实际上是通过黑盒变通方法或其他侧信道攻击来解决的。这个任务也不例外——我们拿到了 .cmm 文件以及编译好的二进制文件。

CMM 文件是 GHC 后期中间语言的转储。这会让我们的工作变得轻松很多——我们不用逆向 Haskell 的 thunk 代码，所有东西都以纯文本形式保存……嗯，算是吧。

如何变懒

简单介绍一下函数式编程的美妙世界。Haskell 是一门惰性语言。但它可不是那种拖延症——所有事情都会尽可能地拖延，我是认真的。例如，考虑这个函数：

integersn = n : integers (n+1)

如果你不懂 Haskell，这在概念上等同于以下 Python 代码：

defintegers(n):return[n] + integers(n +1)

你觉得这段代码有什么问题吗？没错，这不是一个非常有用的函数——它会无限递归，或者干脆把所有可用的堆栈空间都占满，然后爆炸。不过在 Haskell 中却不是这样——你可以调用这个函数，取结果的前 100 个元素，然后得到非常有用的结果——Haskell 是惰性的，所以只会对必要的元素进行求值。

但这仍然不能解释 Haskell 到底有多懒。考虑：

foo(2+2)

这只是一个foo带参数的函数调用4。等等，错了，我骗你了。参数是2 + 2，它实际上直到需要时才会被求值。见鬼，你本来可以传递这个1 / 0参数，至少在实际求值参数之前不会发生任何不好的事情。

Reverse

那么，为什么要介绍呢？好吧，这是main函数在 dump 中的样子：

==================== Output Cmm ====================
[section""data" . :Main.main_closure"{
     :Main.main_closure:const:Main.main_info;const0;const0;const0;
 },
 :Main.main_entry()//  [R1]{ info_tbl: [(c3bb,
                       label: :Main.main_info
                       rep:HeapRepstatic{ Thunk })]
           stack_info: arg_space:8updfr_space: Just8}
     {offset
       c3bb:
           _01D::P64 = R1;if((Sp +8) -24< SpLim)gotoc3bc;elsegotoc3bd;
       c3bc:
           R1 = _01D::P64;
           call (stg_gc_enter_1)(R1) args:8, res:0, upd:8;
       c3bd:
           (_c3b8::I64) = call"ccall"arg hints:  [PtrHint,
                                                    PtrHint]  result hints:  [PtrHint] newCAF(BaseReg, _01D::P64);if(_c3b8::I64 ==0)gotoc3ba;elsegotoc3b9;
       c3ba:
           call (I64[_01D::P64])() args:8, res:0, upd:8;
       c3b9:
           I64[Sp -16] = stg_bh_upd_frame_info;
           I64[Sp -8] = _c3b8::I64;
           R2 = Main.main_closure;
           R1 = GHC.TopHandler.runMainIO_closure;
           Sp = Sp -16;
           call stg_ap_p_fast(R2, R1) args:24, res:0, upd:24;
     }
 }]

很漂亮，不是吗？这到底是怎么回事？其实什么也没有。这段代码的作用就是：

runMainIO(main_closure)

main_closure嗯，主函数的闭包在哪里？让我们深入挖掘一下——这里面到底是什么main_closure？

Main.main_entry()//  [R1]{ info_tbl: [(c3aW,
                      label: Main.main_info
                      rep:HeapRepstatic{ Thunk })]
          stack_info: arg_space:8updfr_space: Just8}
    {offset
      c3aW:
          _rFG::P64 = R1;if((Sp +8) -24< SpLim)gotoc3aX;elsegotoc3aY;
      c3aX:
          R1 = _rFG::P64;
          call (stg_gc_enter_1)(R1) args:8, res:0, upd:8;
      c3aY:
          (_c3aT::I64) = call"ccall"arg hints:  [PtrHint,
                                                   PtrHint]  result hints:  [PtrHint] newCAF(BaseReg, _rFG::P64);if(_c3aT::I64 ==0)gotoc3aV;elsegotoc3aU;
      c3aV:
          call (I64[_rFG::P64])() args:8, res:0, upd:8;
      c3aU:
          I64[Sp -16] = stg_bh_upd_frame_info;
          I64[Sp -8] = _c3aT::I64;
          R5 = sat_s2Rj_closure+1;
          R4 = sat_s2Rf_closure;
          R3 = GHC.Base.$fMonadIO_closure;
          R2 = Data.Foldable.$fFoldable[]_closure;
          R1 = Data.Foldable.forM__closure;
          Sp = Sp -16;
          call stg_ap_pppp_fast(R5,
                                R4,
                                R3,
                                R2,
                                R1) args:24, res:0, upd:24;
    }                                               
}

又有很多代码。同样，这相当于：

forM (s2Rj_closure) (s2Rf_closure)

因此，使用两个闭包来调用单个函数。

再次...

==================== Cmm produced bynewcodegen ====================
[section""data" . sat_s2Rf_closure"{
     sat_s2Rf_closure:constsat_s2Rf_info;const0;const0;const0;
 },
 sat_s2Rf_entry()//  [R1]{ info_tbl: [(c3aH,
                       label: sat_s2Rf_info
                       rep:HeapRepstatic{ Thunk })]
           stack_info: arg_space:8updfr_space: Just8}
     {offset
       c3aH:
           _s2Rf::P64 = R1;gotoc3aC;
       c3aC:if((old +0) - <highSp> < SpLim)gotoc3aI;elsegotoc3aJ;
       c3aI:
           R1 = _s2Rf::P64;
           call (stg_gc_enter_1)(R1) args:8, res:0, upd:8;
       c3aJ:
           (_c3aE::I64) = call"ccall"arg hints:  [PtrHint,
                                                    PtrHint]  result hints:  [PtrHint] newCAF(BaseReg, _s2Rf::P64);if(_c3aE::I64 ==0)gotoc3aG;elsegotoc3aF;
       c3aG:
           call (I64[_s2Rf::P64])() args:8, res:0, upd:8;
       c3aF:
           I64[(old +24)] = stg_bh_upd_frame_info;
           I64[(old +16)] = _c3aE::I64;
           R3 = Main.flags_closure+2;
           R2 = Main.idx'_closure+1;
           R1 = GHC.Base.map_closure;
           call stg_ap_pp_fast(R3, R2, R1) args: 24, res: 0, upd: 24;
     }
 }]

这基本上意味着（闭包名称由我命名）：

map(idx_closure) (flags_closure)

因此，再次，单个函数调用，带有闭包参数和大量垃圾。

我就不多说细节了——当你知道会发生什么（即大量的 thunk）时，逆向是相当简单的（除非你需要很多耐心）。

这是逆向后的代码，应该与原代码非常相似：

module Main where

import Data.Bits
import Data.Char
import Control.Monad
import System.IO
import Data.Function.Memoizes0="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!#$%&'\"()*+,-./:;<=>?@[\\]^_`{|}~"s1 ="1vI{e[8Td]-nQ.7O\"bl(jq@<0Vy&Z3~\\ps,aD^;BN9JUoh|CE2_6!G'rHuf>$S%MxgzKY4`c+WXA5F)mR}#PtL?*=i/:wk"s2 ="Bp}i{XU%f$DR\\0<Lx=o\"Sl`bz)-e62|&JqFT!(C5yh;@u*.WaZ#Qv,?cr8wEm4_t19PH:j]>[NVMn7YGkK'^/~OIdsA+3g"s3 ="_r+#yh[Y)S8aXJwV&jv\"o=I(6>pg,f-M]qbN4'EDKF\\t<3G%|$csPQm}~0@R;uU2z9iWB./HCk!{:Od^ZT7`Anl1e5L*x?"data Index = Index Int Int

f :: Int -> [Char]
f0=s0f arg = s1 ++ f (subtract1arg) ++ s2 ++ f (subtract1arg) ++ s3

idx :: Index -> Char
idx (Index i j) = (f i !! j)

flags = [Index039,
     Index5282,
     Index616240,
     Index9162889,
     Index14523151,
     Index175536393,
     Index7616133142712,
     Index8799122076774,
     Index8656370998818,
     Index983512169334,
     Index9023316222630,
     Index940220517998,
     Index9509206287754,
     Index5656439741488,
     Index9020254692819,
     Index5337505473338,
     Index786066985734,
     Index5342343561367,
     Index7797237439774,
     Index6145303374550,
     Index5842469397741,
     Index6262125811292,
     Index8861285489743,
     Index9917203482576,
     Index621065894981,
     Index5807160395306,
     Index6950411117612,
     Index9261130413308,
     Index6224532384558,
     Index5304107223978,
     Index6533292707045,
     Index8303284494291,
     Index9948119890013,
     Index8254430252526,
     Index8249142828351,
     Index8799452127715,
     Index6071491307991,
     Index8803154654024,
     Index9328181393976,
     Index6253103923077,
     Index7886450071326,
     Index7721342235485,
     Index6802429438438,
     Index6391504612462,
     Index530023633538,
     Index9418315942207,
     Index9873228342978,
     Index6361510000394,
     Index5816485654100,
     Index8533347840847,
     Index9931517634651,
     Index8209122749414,
     Index9873484029647,
     Index9346273221045]

main =doforM_(mapidx flags) $ \i ->doputChar i
    hFlush stdout

对于它生成的巨大二进制文件来说，代码并不多，是吗？

问题很简单——idx函数很慢。但我们可以让它更快。我懒得用我常用的语言（python）重写所有内容，所以我干脆idx用 Haskell 实现了更快的版本：

fsize' :: Int -> Integer
fsize'0= fromIntegral $ length s0fsize' i = 2 * fsize (i - 1) + 3 * fsize 0

fsize :: Int -> Integer
fsize = memoize fsize'idx' :: Index -> Char
idx'(Index i j) =ifi ==0thens0!! jelseiffromIntegral j < fsize0thens1 !! jelseiffromIntegral j < fsize1thenidx' $ Index (i - 1) (j - fromInteger fsize0)
    else if fromIntegral j < fsize2 then s2 !! (j - fromInteger fsize1)
    else if fromIntegral j < fsize3 then idx'$ Index (i -1) (j - fromInteger fsize2)elses3 !! (j - fromInteger fsize3)
    where fsize0= fsize0fsize1 = fsize0+ fsize (i -1)
          fsize2 = fsize1 + fsize0fsize3 = fsize2 + fsize (i -1)

基本上就是这样 - 运行逆向版本后，几秒钟内就会生成正确的标志：

N1CTF{did_cmm_helped?1109ef6af4b2c6fc274ddc16ff8365d1}

PS：是的，确实如此。以上内容来自CTFtime

patience

如何变懒

Reverse

作者：s1sub3ny

2

0

相关WriteUP

2018网鼎杯3-babyre

EasyXor

EasyReverse

[NUAACTF-2017] [Reverse]robots解法

2018-网鼎杯-advance