LCTF 2017 WP II

拿去当壁纸吧朋友

平时隐写玩的多的师傅们看到论文能意识到这个是busysteg,不多说。真·签到题。

大部分师傅在搭建openCV环境上面有一点障碍, 可以在这里看看我怎么在Ubuntu 16.04 x64搭建的:

https://github.com/skyel1u/my-pc-env/blob/master/my-pc-env.md#open-cv

编译busysteg的代码,直接使用就好了:

#include <opencv2/core/core.hpp>
#include <opencv2/highgui/highgui.hpp>
#include <opencv2/imgproc/imgproc.hpp>
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace cv;
using namespace std;

char* progpath;

void usage() {
  cerr << "Usage: \n";
  cerr << "  " << progpath << " h <image path> <data path> <output image path>\n";
  cerr << "  " << progpath << " x <image path> <output data path>\n";
}

void fatalerror(const char* error) {
  cerr << "ERROR: " << error << endl;
  usage();
  exit(1);
}

void info(const char* msg) {
  cerr << "[+] " << msg << endl;
}

void hide_data(char* inimg, char* indata, char* outimg);
void extract_data(char *inimg, char* outdata);

int main( int argc, char** argv ) {
  progpath = argv[0];
  if ( argc < 2 ) {
    fatalerror("No arguments passed");
  }
  if ( argv[1][1] != '\0' ) {
    fatalerror("Operation must be a single letter");
  }
  if ( argv[1][0] == 'h' ) {
    if ( argc != 5 ) {
      fatalerror("Wrong number of parameters for [h]ide operation");
    }
    hide_data(argv[2], argv[3], argv[4]);
  } else if ( argv[1][0] == 'x' ) {
    if ( argc != 4 ) {
      fatalerror("Wrong number of parameters for e[x]tract operation");
    }
    extract_data(argv[2], argv[3]);
  } else {
    fatalerror("Unknown operation");
  }
  return 0;
}

Mat calc_energy(Mat img) {
  Mat orig;
  Mat shifted;
  Mat diff;
  Mat res;

  bitwise_and(img, 0xF0, img);

  copyMakeBorder(img, orig, 1, 1, 1, 1, BORDER_REPLICATE);

  res = Mat::zeros(orig.size(), orig.type());

  int top[8] = {1,0,0,0,1,2,2,2};
  int left[8] = {2,2,1,0,0,0,1,2};
  for ( int i = 0 ; i < 8 ; i++ ) {
    copyMakeBorder(img, shifted, top[i], 2-top[i], left[i], 2-left[i], BORDER_REPLICATE);
    absdiff(orig, shifted, diff);
    res = max(res, diff);
  }

  return res(Rect(1, 1, img.cols, img.rows)); // x, y, width, height
}

typedef pair<pair<uchar, int>, pair<int, pair<int, int> > > Energy;

inline Energy _energy(int r, int c, int ch, uchar v) {
  int nonce = ch * ch * 10666589 + r * r + c * c + 2239; // to "uniformly" distribute data
  return make_pair(make_pair(v, nonce), make_pair(ch, make_pair(c, r)));
}

inline int _energy_r(const Energy &e) { return e.second.second.second; }
inline int _energy_c(const Energy &e) { return e.second.second.first; }
inline int _energy_ch(const Energy &e) { return e.second.first; }
inline int _energy_v(const Energy &e) { return e.first.first; }

vector<Energy> energy_order(Mat img) {
  /* Returns a vector in decreasing order of energy. */

  Mat energy = calc_energy(img.clone());

  info("Calculated energies");

  vector<Energy> energylist;

  for ( int r = 0 ; r < img.rows ; r++ ) {
    for ( int c = 0 ; c < img.cols ; c++ ) {
      const Vec3b vals = energy.at<Vec3b>(r,c);
      for ( int ch = 0 ; ch < 3 ; ch++ ) {
    uchar v = vals[ch];
    if ( v > 0 ) {
      energylist.push_back(_energy(r,c,ch,v));
    }
      }
    }
  }

  sort(energylist.begin(), energylist.end());
  reverse(energylist.begin(), energylist.end());

  return energylist;
}

void write_into(Mat &img, vector<Energy> pts, char *buf, int size) {
  int written = 0;
  char val;
  int count = 0;
  for ( vector<Energy>::iterator it = pts.begin() ;
    it != pts.end() && written != size ;
    it++, count++ ) {
    uchar data;
    if ( count % 2 == 0 ) {
      val = buf[written];
      data = (val & 0xf0) / 0x10;
    } else {
      data = (val & 0x0f);
      written += 1;
    }

    Energy &e = *it;
    Vec3b &vals = img.at<Vec3b>(_energy_r(e), _energy_c(e));
    uchar &v = vals[_energy_ch(e)];
    v = (0xf0 & v) + data;
  }

  if ( written != size ) {
    fatalerror("Could not write all bytes");
  }
}

void read_from(Mat &img, vector<Energy> pts, char* buf, int size) {
  int read = 0;

  int count = 0;
  char val = 0;

  for ( vector<Energy>::iterator it = pts.begin() ;
    it != pts.end() && read != size ;
    it++, count++ ) {
    Energy &e = *it;
    const Vec3b val = img.at<Vec3b>(_energy_r(e), _energy_c(e));
    const uchar v = val[_energy_ch(e)];
    const uchar data = 0x0f & v;
    char out;
    if ( count % 2 == 0 ) {
      out = data * 0x10;
    } else {
      out += data;
      buf[read++] = out;
    }
  }

  if ( read != size ) {
    fatalerror("Wrong size");
  }
}

bool is_valid_image_path(char *path) {
  int l = strlen(path);
  return strcmp(path + l - 4, ".bmp") == 0 ||
    strcmp(path + l - 4, ".png") == 0;
}

void hide_data(char* inimg, char* indata, char* outimg) {
  if ( !is_valid_image_path(outimg) ) {
    fatalerror("Output path must be either have .png or .bmp as extension.");
  }

  Mat img = imread(inimg, CV_LOAD_IMAGE_COLOR);
  if ( ! img.data ) {
    fatalerror("Could not load image. Please check path.");
  }
  info("Loaded image");

  ifstream fin(indata, ios_base::binary);
  if ( ! fin.good() ) {
    fatalerror("Could not read data from file. Please check path.");
  }
  char_traits<char>::pos_type fstart = fin.tellg();
  fin.seekg(0, ios_base::end);
  long int fsize = (long int) (fin.tellg() - fstart);
  fin.seekg(0, ios_base::beg);
  char *buf = new char[fsize + 16];
  memcpy(buf, "BUSYSTEG", 8);
  memcpy(buf + 8, &fsize, 8);
  fin.read(buf + 16, fsize);
  fin.close();
  info("Read data");

  vector<Energy> pts = energy_order(img);
  info("Found energy ordering");

  write_into(img, pts, buf, fsize + 16);
  info("Updated pixel values");

  imwrite(outimg, img);
  info("Finished writing image");

  delete[] buf;
}

void extract_data(char *inimg, char* outdata) {
  Mat img = imread(inimg, CV_LOAD_IMAGE_COLOR);
  if ( ! img.data ) {
    fatalerror("Could not load image. Please check path.");
  }
  info("Loaded image");

  vector<Energy> pts = energy_order(img);
  info("Found energy ordering");

  char header[16];
  read_from(img, pts, header, 16);
  if ( memcmp(header, "BUSYSTEG", 8) != 0 ) {
    fatalerror("Not a busysteg encoded image");
  }

  long int fsize;
  memcpy(&fsize, header+8, 8);
  info("Found data length");

  char *buf = new char[fsize + 16];
  read_from(img, pts, buf, fsize + 16);
  info("Loaded data from pixels");

  ofstream fout(outdata, ios_base::binary);
  fout.write(buf + 16, fsize);
  fout.close();
  info("Finished writing data");

  delete [] buf;
}

CMakeLists.txt:

cmake_minimum_required(VERSION 2.8)
project( busysteg )
find_package( OpenCV REQUIRED )
add_executable( busysteg busysteg )
target_link_libraries( busysteg ${OpenCV_LIBS} )

使用cmake编译,运行即可得flag:

$ ./busySteg x final.png out                                                                 
[+] Loaded image
[+] Calculated energies
[+] Found energy ordering
[+] Found data length
[+] Loaded data from pixels
[+] Finished writing data
$ cat out                                                                                   
lctf{4a7cb5e3c532f01c45e4213804ff1704}

Android

最简单

env

1. teamtoken,message,金额
2. 每队初始金钱1k

思路

1. 无加固,只有JNI_OnLoad函数里对APK签名做了验证,修改之后调试即可;
2. 先submit做请求,然后pay进行支付;
3. 首先encode得到teamtoken,实际上就是做了一次md5;
4. 客户端先传参数到server,然后server sign=md5传回。split处理服务器传回的sign过的params string(message=xxx&order=x&teamtoken=xxx&sign=xxx)
5. app再次求md5,得到signagain post到server,server验证sign和sianagain是否相同。

漏洞点

1. 取变量值是直接取split之后vector的固定位置,造成覆盖;
2. server第二次checksign未check金额是否为正,因此此时可以修改post参数值进行充值;(需要覆盖sign值,自己md5求sign进行篡改。)

Crypto

写在前面

双线性对

两道题目中没有用到双线性对其他复杂的性质与困难问题,只用到了最基本的一条性质:

e(g^a, h^b) == e(g, h)^(a*b)

Charm

看到许多人卡在安装charm上,略有些惊讶……

pip install charm-crypto

如果没有安装依赖,是无法直接用pip安装charm的。 charm的文档中描述了charm的依赖包,以及如何手动编译安装。

官方文档

crypto1

0X00. 题目原文

#!/usr/bin/env python3
from charm.toolbox.pairinggroup  import *
from Crypto.Util.number import long_to_bytes, bytes_to_long, inverse
from urllib import parse, request

logo = """
_|          _|_|_|  _|_|_|_|_|  _|_|_|_|  
_|        _|            _|      _|        
_|        _|            _|      _|_|_|    
_|        _|            _|      _|        
_|_|_|_|    _|_|_|      _|      _|        



  _|_|      _|      _|  _|_|_|_|_|  
_|    _|  _|  _|  _|_|          _|
    _|    _|  _|    _|        _|
  _|      _|  _|    _|      _|
_|_|_|_|    _|      _|    _|
"""

def sign(message, G, k, g, h, S):
    d = ***************************************
        
    message = bytes(message, 'UTF-8')
    message = bytes_to_long(message)

    if message == 0:
        message = G.random(ZR)

    mid = S**k
    mid = G.serialize(mid)
    mid = bytes_to_long(mid)
    P = G.pair_prod(g**mid, h**(message + d*k))
    
    return G.serialize(P)
    

def check_token(token, name):
    url = 'http://lctf.pwnhub.cn/api/ucenter/teams/'+token+'/verify/'
    req = request.Request(url=url)
    try:
        res = request.urlopen(req)
        if res.code == 200:
            return True
    except :
        pass

    return False    
           

def main():
    print(logo)

    S = ************************************************
    R0 = ***********************************************
    R1 = ************************************************
    R2 = ***********************************************

    S1 = S + R0
    S2 = S + R0*2

    G = PairingGroup('SS512')
    g = b'1:HniHI3b/eK111pzcIdKZKJCK9S7QiL5xItmJ9iTvEaGGEVuM4hGc2cMRqhNwsV29BN/QpqhopD+2XgUaTdQMqQA='
    h = b'2:OGpVSq03JR4dWKsDZ+6DBJ6Qwy2E4jaNA6HsWJZNP1vhHe2wYjLUvw990iouBG8XQVEbKr+uLNc3k9n4JDAJOgA='
    g = G.deserialize(g)
    h = G.deserialize(h)

    token_str = input("token:>>")
    name = input("team name:>>")
    if not check_token(token_str, name):
        return 0
    else:
        try:
            token = bytes(token_str,'UTF-8')
            token = bytes_to_long(token)
        except :
            return 0
    
    if token%2 ==1:
        point = G.pair_prod(g**token, h**R1) * G.pair_prod(g**S1, h)
    else:
        point = G.pair_prod(g**token, h**R2) * G.pair_prod(g**S2, h)
    print(G.serialize(point))

    S = G.pair_prod(g,h)**S
    k = G.serialize(S)
    k = bytes_to_long(k)
    
    message = input('message to sign:>>')
    if "show me flag" in message:
        return 0
    else:
        signed = sign(message, G, k, g, h, S)
        print(signed)
    
    signed_from_challenger = input('sign of "show me flag":>>')
    if str(sign('show me flag', G, k, g, h, S)) == signed_from_challenger:
        with open('./flag') as target:
            print(target.read())

if __name__ == '__main__':
    main()

0X01. 思路

  • 从下往上找可以看到,想要获得flag就需要提供sign('show me flag', ...)。
  • 再往上看,这个服务能提供所有不包含'show me flag'子串的字符串M对应的sign(M)。显然这里是一个选择明文攻击(CPA)。
  • 检查函数sign,发现sign中未引入随机量,据此判断sign没有CPA安全性。
  • 分析sign,在选择明文攻击中攻破sign。

0x02. 攻破sign

def sign(message, G, k, g, h, S):
    d = ************************************************
        
    message = bytes(message, 'UTF-8')
    message = bytes_to_long(message)

    if message == 0:
        message = G.random(ZR)

    mid = S**k
    mid = G.serialize(mid)
    mid = bytes_to_long(mid)
    P = G.pair_prod(g**mid, h**(message + d*k))
    
    return G.serialize(P)

读读sign,发现这是对ECDSA的拙劣模仿。

sign(M, ...)返回的结果是这样的:

e(g^(S^k), h^(M + d*k))

其中,S, k, d 三个值现在都不知道;g, h 已知;M可以自由控制但是不能为空,也不能包含子串'show me flag'。

化简一下sign(M, ...)返回的结果:

e(g, h) ^ (S^k * M + S^k * d * k)

一个直观的思路

  • 选择M1, M2,保证 bytes_to_long(M1) - bytes_to_long(M2) = t,t为任意常数
  • 请求 s1 = sign(M1, ...) ; s2 = sign(M2, ...)
  • 选择 M',保证 bytes_to_long(M') + k = bytes_to_long('show me flag')
  • 请求 s' = sign(M', ...)
  • 计算:
s = s' * (s1 / s2) 
  = (e(g, h) ^ (S^k * M' + S^k * d * k)) * ((e(g, h) ^ (S^k * M1 + S^k * d * k)) / (e(g, h) ^ (S^k * M2 + S^k * d * k)))
  = e(g, h) ^ (S^k * (M' + M1 - M2) + S^k * d * k)
  = e(g, h) ^ (S^k * (M' + k) + S^k * d * k)
  = e(g, h) ^ (S^k * M + S^k * d * k)
   = sign('show me flag', ...)
  

至此crypto1的解计算完成。提交时看看题目给出代码中的判断部分注意提交格式。

crypto2

0X00. 题目原文

#!/usr/bin/env python3
from charm.toolbox.pairinggroup  import *
from Crypto.Util.number import long_to_bytes, bytes_to_long, inverse
from urllib import parse, request

logo = """
_|          _|_|_|  _|_|_|_|_|  _|_|_|_|  
_|        _|            _|      _|        
_|        _|            _|      _|_|_|    
_|        _|            _|      _|        
_|_|_|_|    _|_|_|      _|      _|        



  _|_|      _|      _|  _|_|_|_|_|  
_|    _|  _|  _|  _|_|          _|
    _|    _|  _|    _|        _|
  _|      _|  _|    _|      _|
_|_|_|_|    _|      _|    _|
"""

def sign(message, G, k, g, h, S):
    d = ********************************************
        
    message = bytes(message, 'UTF-8')
    message = bytes_to_long(message)

    if message == 0:
        message = G.random(ZR)

    mid = S**k
    mid = G.serialize(mid)
    mid = bytes_to_long(mid)
    P = G.pair_prod(g**mid, h**(message + d*k))
    
    return G.serialize(P)
    

def check_token(token, name):
    url = 'http://lctf.pwnhub.cn/api/ucenter/teams/'+token+'/verify/'
    req = request.Request(url=url)
    try:
        res = request.urlopen(req)
        if res.code == 200:
            return True
    except :
        pass

    return False    
           

def main():
    print(logo)

    S = ***********************************************
    R0 = ************************************************
    R1 = ************************************************
    R2 = ************************************************

    S1 = S + R0
    S2 = S + R0*2

    G = PairingGroup('SS512')
    g = b'1:HniHI3b/eK111pzcIdKZKJCK9S7QiL5xItmJ9iTvEaGGEVuM4hGc2cMRqhNwsV29BN/QpqhopD+2XgUaTdQMqQA='
    h = b'2:OGpVSq03JR4dWKsDZ+6DBJ6Qwy2E4jaNA6HsWJZNP1vhHe2wYjLUvw990iouBG8XQVEbKr+uLNc3k9n4JDAJOgA='
    g = G.deserialize(g)
    h = G.deserialize(h)

    token_str = input("token:>>")
    name = input("team name:>>")
    if not check_token(token_str, name):
        return 0
    else:
        try:
            token = bytes(token_str,'UTF-8')
            token = bytes_to_long(token)
        except :
            return 0
    
    if token%2 ==1:
        point = G.pair_prod(g**token, h**R1) * G.pair_prod(g**S1, h)
    else:
        point = G.pair_prod(g**token, h**R2) * G.pair_prod(g**S2, h)
    print(G.serialize(point))

    S = G.pair_prod(g,h)**S
    k = G.serialize(S)
    k = bytes_to_long(k)
    
    message = 'abcd'
    signed = sign(message, G, k, g, h, S)
    print('signed of "abcd":>>', signed)
    
    signed_from_challenger = input('sign of "show me flag":>>')
    if str(sign('show me flag', G, k, g, h, S)) == signed_from_challenger:
        with open('./flag2') as target:
            print(target.read())

if __name__ == '__main__':
    main()

0X01. 思路

比赛结束前三小时crypto2放出了hint:“这不止是一道crypto题目,它还是一道……”

两道题目只有几行代码不同,crypto2中不允许用户提交自己的字符串。只会返回sign('abcd', ...)。无法选择明文了,允许输入的地方只有三个:token,队名,和最后的变量 signed_from_challenger。其中‘队名’这个变量是打酱油的,丝毫用处都没有。(此处偷偷谴责一下写token校验api的兄台 :-P)

读完代码后应该可以意识到crypto2里sign函数也几乎是打酱油的,全程只有可能执行sign('abcd')与sign('show me flag')。

那么问题肯定出在前面那一坨代码上了。

读一下前面的代码,意识到前面的代码其实是在双线性对映射出的那个群中一点e(g, h)的指数上实现了一个两层递归的 shamir门限方案。这个shamir树型结构也是CP-ABE(Cipher Policy - Attributes Based Encryption)的基础结构。

图示:

5a12706de4b0143a78b4a9d4.png

题目中如下代码实现了这颗树。

if token%2 ==1:
    point = G.pair_prod(g**token, h**R1) * G.pair_prod(g**S1, h)
else:
    point = G.pair_prod(g**token, h**R2) * G.pair_prod(g**S2, h)
print(G.serialize(point))

在实际代码中,奇数选手将得到 e(g, h)^(tokenR1 + S1);偶数选手将得到 e(g, h)^(tokenR2 + S2)。从更靠前的代码可以看到S1,S2的来源:已知S1,S2时,它们组成了一个简单的二元一次方程组。如果想要恢复出sign函数输入中的S和k,就需要先拿到S,或者拿到S的一些特征,比如说e(g, h)^S。

S1 = S + R0
S2 = S + R0*2

对于S,如果只知道S1,或者只知道S2,是无法解出S的。毕竟“K元一次方程需要至少K个一组才可能有解,否则一定有无穷多解”。

对于选手能直接得到的 e(g, h)^(token*R1 + S1) ,有两个未知量R1,S1,在只有一个token时也是有无穷多解的。因此需要两个奇数token,两个偶数token才有可能恢复出S(这里对应给出的hint:它不只是一道crypto题目,它还是一道社工题)。在实际操作中,我们只能恢复到e(g, h)^S,不过这已经足够我们求出'show me flag'的sign啦。

因为我们只能得到'abcd'的sign,即 e(g^(S^k), h^('abcd' + d*k))
(注:此处代码前,S被赋值成了e(g, h)^S,详情见题目原文)
在我们能得到S = e(g, h)^S,且可以根据S求得k时,我们就可以给任意消息做签名了。

0X02. writeUp.py

from charm.toolbox.pairinggroup import *
from Crypto.Util.number import bytes_to_long, inverse

def main():
    G = PairingGroup('SS512')
    g = b'1:HniHI3b/eK111pzcIdKZKJCK9S7QiL5xItmJ9iTvEaGGEVuM4hGc2cMRqhNwsV29BN/QpqhopD+2XgUaTdQMqQA='
    h = b'2:OGpVSq03JR4dWKsDZ+6DBJ6Qwy2E4jaNA6HsWJZNP1vhHe2wYjLUvw990iouBG8XQVEbKr+uLNc3k9n4JDAJOgA='

    # 4 different token. 2 even 2 odd
    t1 = bytes_to_long(b'4795968fe0bf73a1e39e6fec844dee01')
    S1 = b'3:cOlYveeItjU4ZHh8B58RjWUYJwdtFi/FXzqtd2GnnqEMJ9AFKzNjV90eUoPDLkinkWsdmbYTJxFTq5bvucwVHE98Uvw2laNvrsCFY9Mw766YdEPAtj7smBt/tIDl+u1mORufxZX8Q31F3dJjnzEoYhlxRZ9e9JFVtK7nW2Di6Iw='
    t2 = bytes_to_long(b'f11ca9db1f547b71a1b9592659553814')
    S2 = b'3:NjqqiCxaQtlFS1FEsSD+jmuO9Z0srysMi4K1nVCg2yAxJRjX62PPMSbY5JAa+Y4Ap25p9+u1EZ05f1RSwOXyZiIAZoDoS0crKDHRLJtE40aswcnPaf1JklMGBOGLdBUOZ3+nknLRDLACyBFnTW8y6FnHzLICGruBHisLhschvHM='
    t3 = bytes_to_long(b'97fddec1d9e630075803fc67d4220b05')
    S3 = b'3:GYcIbust8E1tcYZghIgC4x6YhrAyJUvy0lHHUxfvIOD7S/ann03RFrhO4qKb0jQ4vcU7pHJPv9Q+WDDPV/mAcH224dIfSyGcv91adl0tuhS6z0Fr4tBz03YUFUcGvAvi7bHvjnywwAjkTe1ZmMybyUnc9bMTPUxIZ3kli2b3PRs='
    t4 = bytes_to_long(b'adafcd958bbe176dd9cc96ef3aaa6438')
    S4 = b'3:R7Zhznj9aRtEv9ifZfLf9aqt4PSZzrMCSXuxkwZDdLEC2pqRPC1dWtP41BLR0UbbZVbTyOuojif9HYVuDu7oFSMTtj3zUxwXUW2x5sCYnkY3MOhSKM9JJxzAktSF0H2rIVvw4iBhQoh6Ecy3qRYfjZSha4Bc729DXHbYx0sMxd4='

    # SS512's order. get from G.order()
    order = 730750818665451621361119245571504901405976559617

    #init
    g = G.deserialize(g)
    h = G.deserialize(h)
    S1 = G.deserialize(S1)
    S2 = G.deserialize(S2)
    S3 = G.deserialize(S3)
    S4 = G.deserialize(S4)

    #compute x**S1
    t_S1 = ((S1**t3)/(S3**t1))**inverse((t3-t1), G.order())
    print(t_S1)

    #compute x**S2
    t_S2 = ((S2**t4)/(S4**t2))**inverse((t4-t2), G.order())
    print(t_S2)

    #compute x**S
    t = (t_S1*t_S1)/t_S2
    print(t)

    #compute k
    k = G.serialize(t)
    k = bytes_to_long(k)

    #compute mid
    mid = t**k
    mid = G.serialize(mid)
    mid = bytes_to_long(mid)

    #compute sign
    signed = b'3:loZKMHi9WWkS46zTQyidX5546U2Sg/JLnNi18X2KRklZdJSth4Kyj5FPg0J8sVpc9hyClgIo2P8xOGsRK6Zxc2AW6euFkyaOUWI9ZmYp2AhE0kcOypR4vASF9vWYtNqj0qlsExtMThSUtS53HYHCczbxcxA2Vcr/tkFagicyU30='
    signed = G.deserialize(signed)
    message = bytes_to_long(b'abcd')
    signed = signed/(G.pair_prod(g, h)**(mid*message))
    
    message = bytes_to_long(b'show me flag')
    signed = signed*(G.pair_prod(g, h)**(mid*message))
    print(str(G.serialize(signed)))


if __name__ == '__main__':
    main()
tagged by none  

Comment Closed.

© 2014 ::L Team::