official/不可加密的异世界/unencryptable-exp.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "6da3bacf",
   "metadata": {},
   "source": [
    "# 不可加密的异世界\n",
    "## 题解\n",
    "\n",
    "这题的出题的思路就是通过一些小trick使得加密后的密文与明文相同。\n",
    "\n",
    "前面两道题的预期解都是利用CBC模式下的IV的冗余，不需要任何爆破，就可以指定任意一个密文分组的值为我们预期的值，详情参考下一节“**CBC模式指定任意密文分组**”。\n",
    "\n",
    "最后一问，题目已经很明显地用了两个密码学上已经破解的算法，所有也很容易往DES和CRC想到这两个点：crc类哈希都是可逆的以及DES的弱密钥；DES也就是为了第三问加进来的，AES是目前最流行的对称加密体制，没有任何已知的有效攻击；而DES是存在诸多问题的，差分攻击、彩虹表、弱密钥等等。而最后一问我们是要求**加密两次**恢复到原明文，这比加密一次恢复到原明文的条件更弱，因此只要使用DES的弱密钥（在Feistel结构下可以直接用弱密钥作为加密过程的密钥实现解密过程，不需要逆序使用子密钥），就可以两次加密（实际上等价于加密+解密）恢复明文。由于crc哈希是可逆的（见下下节），我们就可以直接把一个DES弱密钥当哈希逆向得到我们的消息，提交该消息即可。\n",
    "\n",
    "完整exp见最后一节。\n",
    "\n",
    "\n",
    "\n",
    "## CBC模式指定任意密文分组\n",
    "\n",
    "CBC模式的字节反转攻击算是CTF中老生常谈的考点了，这里也是稍微利用了一下CBC的模式特征：\n",
    "![image.png](./CBC_encryption.svg.png)\n",
    "\n",
    "如果在CBC分组加密模式下，我们可以选择IV并且已知Key的值的话，那么IV这16个字节的冗余可以转移到任意一个密文分组：也就是说我们可以任意指定一个密文分组的值，从而反推出所有密文分组的值以及IV的值。特别地，当明文长度就是一个分组时，我们可以控制整个密文的值。原理如下, 假设我们指定密文分组 $C_i$ 为原来的明文 $m_i$：\n",
    "\n",
    "- $C_{i}$之后的密文：按CBC模式加密即可，初始IV就是$C_i$, 密钥为Key（这部分按标准CBC加密即可）。\n",
    "- $C_{i}$之前的密文：$C_{i-1} = Dec(C_i) \\oplus M_i$，以此类推，直到IV的值确定。\n",
    "\n",
    "第一问根据提示，我们只要控制明文长度不超过16字节即可，因此随便输入单个字母，然后往前面推一步，就得到了IV值，第二问就是第一问的一个拓展，我们每次指定一个分组加密后为明文即可，主要的攻击代码写出来如下：\n",
    "\n",
    "```python\n",
    "from Crypto.Util.number import *\n",
    "from Crypto.Cipher import AES\n",
    "import os\n",
    "\n",
    "block_size=16\n",
    "key_size=16\n",
    "\n",
    "def pad(msg:bytes,block_size = 16):\n",
    "    n = AES.block_size - len(msg) % AES.block_size\n",
    "    return msg + bytes([n]) * n\n",
    "\n",
    "def unpad(msg, block_size = 16):\n",
    "    return msg[: -msg[-1]]\n",
    "\n",
    "def xor(b1:bytes, b2:bytes):\n",
    "    return bytes([x ^^ y for x, y in zip(b1, b2)])\n",
    "\n",
    "def split_block(text:bytes):\n",
    "    assert len(text)%block_size==0,'Invalid length'\n",
    "    return [text[i*block_size:(i+1)*block_size] for i in range(len(text)//block_size)]\n",
    "\n",
    "def AES_CBC_chosen_ciphertext(AES_key:bytes,plaintext:bytes,chosen_ciphertext:bytes,pos=None):\n",
    "    # pos = None the iv will be set as chosen ciphertext\n",
    "    # pos = -1 : the last block will be set as ciphertext\n",
    "    # pos = i : the ith (from 0) block will be set as ciphertext    \n",
    "    if pos==None:\n",
    "        iv=chosen_ciphertext\n",
    "        aes_cbc=AES.new(AES_key,AES.MODE_CBC,iv)\n",
    "        return iv,aes_cbc.encrypt(msg)\n",
    "    \n",
    "    iv=os.urandom(block_size)\n",
    "    aes_cbc=AES.new(AES_key,AES.MODE_CBC,iv)\n",
    "    aes_ecb=AES.new(AES_key,AES.MODE_ECB)\n",
    "    cipher=aes_cbc.encrypt(msg)\n",
    "    msg_blocks=split_block(msg)\n",
    "    cipher_blocks=split_block(cipher)\n",
    "    cipher_blocks[pos]=chosen_ciphertext\n",
    "    \n",
    "    for i in range(pos-1,-1,-1):\n",
    "        cipher_blocks[i]=xor(aes_ecb.decrypt(cipher_blocks[i+1]),msg_blocks[i+1])\n",
    "    \n",
    "    iv=xor(aes_ecb.decrypt(cipher_blocks[0]),msg_blocks[0])\n",
    "    \n",
    "    for i in range(pos+1,len(cipher_blocks)):\n",
    "        cipher_blocks[i]=aes_ecb.encrypt(xor(cipher_blocks[i-1],msg_blocks[i]))\n",
    "    \n",
    "    return iv, b\"\".join(cipher_blocks)\n",
    "```\n",
    "\n",
    "\n",
    "\n",
    "## 逆CRC128哈希\n",
    "\n",
    "Hacker Game之前也出过`crc128`类似的题：[HakcerGame2020中间人](https://github.com/USTC-Hackergame/hackergame2020-writeups/tree/master/official/%E4%B8%AD%E9%97%B4%E4%BA%BA)，更进一步可以找到TCTF的这道题：[fixed ponit](https://hxp.io/blog/51/0CTF-Quals-2019-fixed-point-writeup/)。无一例外，它们都利用了crc128的仿射函数性质：Affine Function in $GF(2^{128})$，其中TCFT这题的writeup还介绍了基于多项式的crc的表示方式，这个方式也可以直接求逆，这里介绍另外一种用矩阵的方式写出crc的表达式。crc仿射函数最容易验证的性质就是：$crc(\\Delta \\oplus a)\\oplus crc(\\Delta \\oplus  b) = const\\quad  \\forall \\Delta$. 也就是说只要两个明文的差分是一样的，那么它们crc哈希后的差分就是一个固定值。这个固定值是可以写出来的，定义$\\_crc(x) = crc(x) \\oplus crc(0^l)$，其中$0^l$代表与x等长的`\"\\x00\"`字节流。对于任意**等长的输入**就有:\n",
    "$$\n",
    "\\_crc(\\Delta \\oplus a)\\oplus \\_crc(\\Delta \\oplus  b) = \\_crc(a \\oplus b)\\\\\n",
    "Generally \\implies \\forall x_i, n \\quad \\oplus_1^n \\_crc(x_i) =  \\_crc(\\oplus_1^n x_i) \\tag{1}\n",
    "$$\n",
    "其中$\\oplus$等价于$GF(2)^{k}(\\forall k \\in Z)$上的加法，所以（1）式在$GF(2)$上可记为：\n",
    "$$\n",
    "\\forall x_i \\in GF(2)^l, l \\in Z ,n \\in Z\\quad \\sum\\limits_1^{n} \\_crc(x_i) =  \\_crc(\\sum\\limits_1^{n} x_i)  \\quad + \\ defined \\ in \\ GF(2)^k\\tag{2}\n",
    "$$\n",
    "有了这个性质，对于$GF(2)$上的128维的向量空间，取一组基底如下：$v_i = (0,..,1,...,0)$ ，第i个位置为1其余均为0的标准正交基，$i \\in \\{1,2,3,...,128\\}$，我们记这一组标准正交基的_crc哈希值的对应的向量为，$V_i =\\_crc(v_i) \\quad i \\in \\{1,2,3,...,128\\}$，用$V_i$构建一个在$GF(2)$上的128×128的矩阵：\n",
    "$$\n",
    "let \\quad M^T = \\begin{bmatrix} \n",
    "V_1 \\\\\n",
    "V_2 \\\\\n",
    "...\\\\\n",
    "V_{128}\n",
    "\\end{bmatrix} ,  \n",
    "\\forall \\vec x =(x_1,...,x_n) \\in GF(2)^{128}\\\\\n",
    "\\implies\n",
    "\\ x*M^T \n",
    "= \\sum\\limits_{i=0}^{128} x_iV_i \n",
    "= \\_crc(\\sum\\limits_{i=0}^{128}x_i*v_i)\n",
    "= \\_crc(x)\n",
    "= crc(x) + crc(0^{128}) \\quad in \\ GF(2)^{128}\n",
    "$$\n",
    "从上面我们就得到了**定长**为128比特的输入做crc哈希时在$GF(2)$上的等价矩阵表示（Affine Function）（其他长度的输入换一下矩阵M和$crc(0^l)$的值即可）,  为了和代码保持一致，我们把$M^T$再转置回来：\n",
    "$$\n",
    "crc(x) = x*M^T + crc(0^{128}) \\implies \n",
    "crc(x)^T = M*x^T + C \\quad where \\ C =   crc(0^{128})^T\n",
    "\\tag{3}\n",
    "$$\n",
    "有了上面的矩阵表示，给定crc128的值，求它对应的一个明文，只需要解一个在GF(2)上的方程组即可$x^T = M^{-1}*(crc(x)^T+C)$，这样我们就实现了一个完整的`crc_128_reverse`函数，这是最基础版本的推导，但是解决这题就够用了。一个简单的sage demo如下：\n",
    "\n",
    "```python\n",
    "def crc128(data, poly=0x883ddfe55bba9af41f47bd6e0b0d8f8f):\n",
    "    crc = (1 << 128) - 1\n",
    "    for b in data:\n",
    "        crc ^^= b\n",
    "        for _ in range(8):\n",
    "            crc = (crc >> 1) ^^ (poly & -(crc & 1))\n",
    "    return crc ^^ ((1 << 128) - 1)\n",
    "\n",
    "def equivalent_affine_crc(crc = crc128, crc_bits = 128, target_bytes = 16):\n",
    "    zero_crc = crc(target_bytes*b\"\\x00\")\n",
    "    target_bits = 8 * target_bytes\n",
    "    v2n = lambda v: int(''.join(map(str, v)), 2)\n",
    "    n2v = lambda n: vector(GF(2), bin(n)[2:].zfill(crc_bits))\n",
    "    # n2v_t = lambda n: vector(GF(2), bin(n)[2:].zfill(target_bits))\n",
    "    Affine_Matrix = []\n",
    "    for i in range(target_bits):\n",
    "        v = vector(GF(2), (j == i for j in range(target_bits)))\n",
    "        value = crc(long_to_bytes(v2n(v),target_bytes)) ^^ zero_crc\n",
    "        Affine_Matrix.append(n2v(value))\n",
    "    # crc affine function: crc_128(x) = M*x+ C\n",
    "    return matrix(GF(2),Affine_Matrix).transpose(), n2v(zero_crc)\n",
    "\n",
    "def crc_128_reverse(crc_value):\n",
    "    M , C = equivalent_affine_crc()\n",
    "    # crc affine function: crc_128(x) = M*x+ C\n",
    "    v2n = lambda v: int(''.join(map(str, v)), 2)\n",
    "    n2v = lambda n: vector(GF(2), bin(n)[2:].zfill(128))\n",
    "    res = M.solve_right(n2v(crc_value)+C)\n",
    "    return long_to_bytes(v2n(res),16)\n",
    "```\n",
    "\n",
    "## EXP"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "a61cdc05",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[x] Opening connection to 202.38.93.111 on port 10110\n",
      "[x] Opening connection to 202.38.93.111 on port 10110: Trying 202.38.93.111\n",
      "[+] Opening connection to 202.38.93.111 on port 10110: Done\n",
      "b'Well done\\n'\n",
      "b'flag{You_will_meet_a_softhearted_God_in_this_autumn_4415f15d79}\\n'\n",
      "b'Well done\\n'\n",
      "b'flag{Softhearted_God_is_a_ghost_always_on_call_885c944a39}\\n'\n",
      "b'What a miracle!\\n'\n",
      "b'flag{Harsh_God_also_releases_sunlight_in_winter_44c7ec2cfb}\\n'\n"
     ]
    }
   ],
   "source": [
    "# unencryptable world\n",
    "from pwn import *\n",
    "from Crypto.Util.number import *\n",
    "from Crypto.Cipher import AES\n",
    "import os\n",
    "\n",
    "block_size = 16\n",
    "key_size = 16\n",
    "\n",
    "\n",
    "def pad(msg: bytes, block_size=16):\n",
    "    n = AES.block_size - len(msg) % AES.block_size\n",
    "    return msg + bytes([n]) * n\n",
    "\n",
    "\n",
    "def unpad(msg, block_size=16):\n",
    "    return msg[: -msg[-1]]\n",
    "\n",
    "\n",
    "def xor(b1: bytes, b2: bytes):\n",
    "    return bytes([x ^^ y for x, y in zip(b1, b2)])\n",
    "\n",
    "\n",
    "def split_block(text: bytes):\n",
    "    assert len(text) % block_size == 0, 'Invalid length'\n",
    "    return [text[i*block_size:(i+1)*block_size] for i in range(len(text)//block_size)]\n",
    "\n",
    "\n",
    "def AES_CBC_chosen_ciphertext(AES_key: bytes, plaintext: bytes, chosen_ciphertext: bytes, pos=None):\n",
    "    # pos = None the iv will be set as chosen ciphertext\n",
    "    # pos = -1 : the last block will be set as ciphertext\n",
    "    # pos = i : the ith (from 0) block will be set as ciphertext\n",
    "\n",
    "    msg = pad(plaintext)\n",
    "    assert pos == None or pos*block_size < len(msg), 'Pos out of bounds'\n",
    "\n",
    "    aes_ecb = AES.new(AES_key, AES.MODE_ECB)\n",
    "    cipher = b\"\\x00\"*len(msg)\n",
    "    msg_blocks = split_block(msg)\n",
    "    cipher_blocks = split_block(cipher)\n",
    "    cipher_blocks[pos] = chosen_ciphertext\n",
    "\n",
    "    for i in range(pos-1, -1, -1):\n",
    "        cipher_blocks[i] = xor(aes_ecb.decrypt(\n",
    "            cipher_blocks[i+1]), msg_blocks[i+1])\n",
    "\n",
    "    iv = xor(aes_ecb.decrypt(cipher_blocks[0]), msg_blocks[0])\n",
    "\n",
    "    for i in range(pos+1, len(cipher_blocks)):\n",
    "        cipher_blocks[i] = aes_ecb.encrypt(\n",
    "            xor(cipher_blocks[i-1], msg_blocks[i]))\n",
    "\n",
    "    return iv, b\"\".join(cipher_blocks)\n",
    "\n",
    "\n",
    "def crc128(data, poly=0x883ddfe55bba9af41f47bd6e0b0d8f8f):\n",
    "    crc = (1 << 128) - 1\n",
    "    for b in data:\n",
    "        crc ^^= b\n",
    "        for _ in range(8):\n",
    "            crc = (crc >> 1) ^^ (poly & -(crc & 1))\n",
    "    return crc ^^ ((1 << 128) - 1)\n",
    "\n",
    "\n",
    "def equivalent_affine_crc(crc=crc128, crc_bits=128, target_bytes=16):\n",
    "    zero_crc = crc(target_bytes*b\"\\x00\")\n",
    "    target_bits = 8 * target_bytes\n",
    "    def v2n(v): return int(''.join(map(str, v)), 2)\n",
    "    def n2v(n): return vector(GF(2), bin(n)[2:].zfill(crc_bits))\n",
    "    # n2v_t = lambda n: vector(GF(2), bin(n)[2:].zfill(target_bits))\n",
    "    Affine_Matrix = []\n",
    "    for i in range(target_bits):\n",
    "        v = vector(GF(2), (j == i for j in range(target_bits)))\n",
    "        value = crc(long_to_bytes(v2n(v), target_bytes)) ^^ zero_crc\n",
    "        Affine_Matrix.append(n2v(value))\n",
    "    # crc affine function: crc_128(x) = M*x+ C\n",
    "    return matrix(GF(2), Affine_Matrix).transpose(), n2v(zero_crc)\n",
    "\n",
    "\n",
    "def crc_128_reverse(crc_value):\n",
    "    M, C = equivalent_affine_crc()\n",
    "    # crc affine function: crc_128(x) = M*x+ C\n",
    "    def v2n(v): return int(''.join(map(str, v)), 2)\n",
    "    def n2v(n): return vector(GF(2), bin(n)[2:].zfill(128))\n",
    "    res = M.solve_right(n2v(crc_value)+C)\n",
    "    return long_to_bytes(v2n(res), 16)\n",
    "\n",
    "\n",
    "io = remote(\"202.38.93.111\", 10110)\n",
    "token = \"819:MEQCIF5Ohbnr1w9u3xhZE6fM8qZjDjbi7BgIa0ammpOdASt6AiBaFF4YoiOD1eYhB+dP8wrcqYJTF8MIplFGIO3Y29Xffw==\"\n",
    "io.sendlineafter(b\"Please input your token: \", token.encode())\n",
    "\n",
    "# solve chall 1\n",
    "\n",
    "\n",
    "def solve1():\n",
    "    io.sendlineafter(b\"> choice: \", b\"1\")\n",
    "    io.sendlineafter(b\"> name: \", b\"1\")\n",
    "    io.sendlineafter(b\"> algo: \", b\"AES\")\n",
    "    io.sendlineafter(b\"> mode: \", b\"CBC\")\n",
    "    # from Crypto.Util.Padding import pad,unpad\n",
    "    your_pass = pad((\"1\" + \"Open the door!\").encode())\n",
    "    key = os.urandom(16)\n",
    "    iv, magic_cipher = AES_CBC_chosen_ciphertext(\n",
    "        key, your_pass, your_pass, int(0))\n",
    "    aes = AES.new(key, AES.MODE_CBC, iv)\n",
    "    io.sendlineafter(b\"> hex keys: \", (key+iv).hex().encode())\n",
    "    print(io.recvline())\n",
    "    print(io.recvline())\n",
    "\n",
    "\n",
    "def solve2():\n",
    "    io.sendlineafter(b\"> choice: \", b\"2\")\n",
    "    io.sendlineafter(b\"> name: \", b\"1\")\n",
    "    io.sendlineafter(b\"> algo: \", b\"AES\")\n",
    "    io.sendlineafter(b\"> mode: \", b\"CBC\")\n",
    "    msg = bytes.fromhex(io.recvline().decode().split(\":\")[-1].strip())\n",
    "    key = os.urandom(16)\n",
    "    block_size = 16\n",
    "    for pos in range(0, len(pad(msg))//block_size-1):\n",
    "        choose_cipher = msg[pos*block_size:(pos+1)*block_size]\n",
    "        iv, magic_cipher = AES_CBC_chosen_ciphertext(\n",
    "            key, msg, choose_cipher, int(pos))\n",
    "        io.sendlineafter(b\"> hex keys: \", (key+iv).hex().encode())\n",
    "    print(io.recvline())\n",
    "    print(io.recvline())\n",
    "\n",
    "\n",
    "def solve3():\n",
    "    io.sendlineafter(b\"> choice: \", b\"3\")\n",
    "    io.sendlineafter(b\"> name: \", b\"1\")\n",
    "    io.sendlineafter(b\"> algo: \", b\"DES\")\n",
    "    io.sendlineafter(b\"> mode: \", b\"ECB\")\n",
    "    target_crc32_hash = b\"\\x01\"*16\n",
    "    msg = crc_128_reverse(ZZ(bytes_to_long(target_crc32_hash)))\n",
    "    assert crc128(msg) == bytes_to_long(target_crc32_hash)\n",
    "    io.sendlineafter(b\"(at least 16 bytes): \", msg.hex().encode())\n",
    "    print(io.recvline())\n",
    "    print(io.recvline())\n",
    "\n",
    "\n",
    "solve1()\n",
    "solve2()\n",
    "solve3()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.5",
   "language": "sage",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}