Attacks.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "74cc7b74-172e-43f5-9563-3e5a1e175d53",
   "metadata": {},
   "source": [
    "# Cryptanalysis of TS-Hash"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "427a6ea8-e06c-4c70-ad7f-fba682b62709",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-11-26T12:19:15.491232Z",
     "iopub.status.busy": "2023-11-26T12:19:15.491051Z",
     "iopub.status.idle": "2023-11-26T12:19:16.030786Z",
     "shell.execute_reply": "2023-11-26T12:19:16.030399Z",
     "shell.execute_reply.started": "2023-11-26T12:19:15.491212Z"
    }
   },
   "outputs": [],
   "source": [
    "from sage.all import *\n",
    "import itertools\n",
    "import random\n",
    "\n",
    "from binteger import Bin\n",
    "\n",
    "from tshash import TSHash"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f37b3454-7910-4740-9f9f-d9f300fa5249",
   "metadata": {},
   "source": [
    "## Extended form"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "ae86dae0-cc43-4db2-b5ed-6969999a2adb",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-11-26T12:19:16.031806Z",
     "iopub.status.busy": "2023-11-26T12:19:16.031599Z",
     "iopub.status.idle": "2023-11-26T12:19:16.502010Z",
     "shell.execute_reply": "2023-11-26T12:19:16.501522Z",
     "shell.execute_reply.started": "2023-11-26T12:19:16.031792Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10100001101110001000110000010000010110000110000101010011110011011100110011010110010011001100100010111000001110101001011101111101\n",
      "10011011001010001100111110110000000000010111101010010010100000110111100010101001001100100110101110111111000110010000111010110101\n",
      "10000111101101111011000100111111110111011010110000100000101001001000110111100000111001111101011001101000001110110011110000001111\n",
      "11010010111001011110101111100110000110010101001010010101001010011100111110000110111100011110110010010100011111011010010110110000\n",
      "10001100111111000011011011010111111101010111001101010001000100101011001100100011110111011100011111010101001110000100010011011000\n",
      "11010010101001000010111111101010100110111100100100010110110011010111111111011101001000110001110010101110010010111000010010000001\n",
      "11010100011000110001111011100000000110000110111001111100110100010010011110111010000001000111010000110101010100010111000001111100\n",
      "10101011101011101011100001010110111100011011110011101010010000101011001100011010101001101111111000011011011000111110001000010001\n",
      "10110101100011100000000111100100001000010001111000100101010011101100110001000110001101011001101011111111011000011001000101100101\n",
      "10111011011010000000000111011001000100100101011010111101100110101101100101100110100111101011001100011000101001001101011110110011\n"
     ]
    }
   ],
   "source": [
    "for i in range(10):\n",
    "    T = TSHash(n=128)\n",
    "    print(T.p0_raw)\n",
    "    msg = Bin.random(300)\n",
    "    \n",
    "    emsg = T.extend(msg)\n",
    "    lp = T._last_pos\n",
    "    assert T.compress(emsg) == msg\n",
    "    assert T._last_pos == lp\n",
    "    \n",
    "    h1 = T.calc_raw(msg)\n",
    "    h2 = T.fromF(T.calc(msg))\n",
    "    h3 = T.fromF(T.calc_ext(emsg))\n",
    "    h4 = T.fromF(T.calc_ext_fast(emsg))\n",
    "    assert h1 == h2 == h3 == h4"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ac6ffc28-ba5d-482a-bcde-1a0189151936",
   "metadata": {},
   "source": [
    "## Algebraic expression"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "05f4b30a-4260-4c26-822c-18d484154b4d",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-11-26T12:19:16.502767Z",
     "iopub.status.busy": "2023-11-26T12:19:16.502572Z",
     "iopub.status.idle": "2023-11-26T12:19:19.939087Z",
     "shell.execute_reply": "2023-11-26T12:19:19.938657Z",
     "shell.execute_reply.started": "2023-11-26T12:19:16.502754Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "11000001001000001111001010100011110001110010010011100010011110110100100011101111011110011100000000010111110000000001100111110111\n",
      "11100111000100110010010001110111001000101100010011100011000110011101001000110011110001100011000010001100010100001111100101110110\n",
      "10010000010101000100100111100100100111100100001001000010011010001100011010000001110111101010111101000010110100100011010100000000\n",
      "11000011001110110100111100001011010001100100100111001110001100101110001010100011011111110110110010111000100011110101101000011100\n",
      "11110010011111101010011010010001100101110110111001100011100010000100011011000000011111101011010110111011110000110111001100111101\n",
      "11010010111010011110101110010110110011100001110011111111000100101000001011100110010000110000100110010010100010001010010101000001\n",
      "11001101001101001000011100011011110110001100101001001001010000111011100000110100001011100010000011011001101110110001000100110010\n",
      "11111111100010111011110000011111100110010011110011100101001000100000010000110000000010100101011111010101010011111110100000011010\n",
      "11000001100011010110011011011010001001101011001110111011011000000101011101101010110100001001101110111000011111110011110111010000\n",
      "10111001010001110000001010100011101010001111000011000110111010001100011111101000111010010001100100100110100111101011011111010111\n"
     ]
    }
   ],
   "source": [
    "for _ in range(10):\n",
    "    n = 64\n",
    "    T = TSHash(n=128)\n",
    "    print(T.p0_raw)\n",
    "\n",
    "    emsg = [None] + [randrange(2) for _ in range(50)]\n",
    "    for N in range(14):\n",
    "        res = 0\n",
    "        for I in Bin.iter(N):\n",
    "            I = sorted(i+1 for i in I.support)\n",
    "            if not I:\n",
    "                res += T.s0 * T.g**N\n",
    "            else:\n",
    "                # the monomial  prod(mi)\n",
    "                cur = prod(emsg[i] for i in I)\n",
    "\n",
    "                # field constant\n",
    "                cur *= T.h * T.g**(N - max(I))\n",
    "\n",
    "                # starting control bit\n",
    "                cur *= (T.alpha * T.s0 * T.g**(min(I)-1)).trace()\n",
    "\n",
    "                # monomial steps control bits\n",
    "                for ij1, ij in zip(I, I[1:]):\n",
    "                    cur *= (T.alpha * T.h * T.g**(ij-ij1-1)).trace()\n",
    "                \n",
    "                res += cur\n",
    "        assert res == T.calc_ext(emsg[1:1+N])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2ea63517-dcc3-4ec4-b7fb-e3a6cc3e178a",
   "metadata": {},
   "source": [
    "# ANF monomials"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "1c1b6804-4a70-48ce-9578-02cbeeea0762",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-11-26T12:19:19.939773Z",
     "iopub.status.busy": "2023-11-26T12:19:19.939595Z",
     "iopub.status.idle": "2023-11-26T12:19:39.953384Z",
     "shell.execute_reply": "2023-11-26T12:19:39.952828Z",
     "shell.execute_reply.started": "2023-11-26T12:19:19.939760Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "expected 57.6650390625\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/tmp/ipykernel_1311557/312387630.py:29: DeprecationWarning: the function is_Polynomial is deprecated; use isinstance(x, sage.structure.element.Polynomial) instead\n",
      "See https://github.com/sagemath/sage/issues/32709 for details.\n",
      "  for a in SBox2(y, m=32).anfs():\n",
      "/home/user/mambaforge/envs/sage/lib/python3.10/site-packages/cry/sbox2/sbox2.py:368: DeprecationWarning: the function is_Polynomial is deprecated; use isinstance(x, sage.structure.element.Polynomial) instead\n",
      "See https://github.com/sagemath/sage/issues/32709 for details.\n",
      "  return type(self)(mobius(self.tuple()), m=self.m)\n",
      "/home/user/mambaforge/envs/sage/lib/python3.10/site-packages/cry/sbox2/sbox2.py:440: DeprecationWarning: the function is_Polynomial is deprecated; use isinstance(x, sage.structure.element.Polynomial) instead\n",
      "See https://github.com/sagemath/sage/issues/32709 for details.\n",
      "  return type(self)(tt, m=1)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "avg 74.0 median 74\n",
      "avg 115.0 median 156\n",
      "avg 104.0 median 82\n",
      "avg 98.0 median 82\n",
      "avg 100.8 median 82\n",
      "avg 90.8 median 82\n",
      "avg 90.7 median 82\n",
      "avg 113.5 median 90\n",
      "avg 105.6 median 82\n",
      "avg 102.0 median 82\n",
      "avg 97.6 median 80\n",
      "avg 97.7 median 82\n",
      "avg 92.1 median 80\n",
      "avg 88.1 median 80\n",
      "avg 87.2 median 75\n",
      "avg 88.1 median 80\n",
      "avg 86.9 median 75\n",
      "avg 84.4 median 75\n",
      "avg 84.1 median 75\n",
      "avg 82.2 median 75\n",
      "avg 79.5 median 74\n",
      "avg 76.6 median 74\n",
      "avg 75.9 median 70\n",
      "avg 77.0 median 74\n",
      "avg 76.3 median 70\n",
      "avg 75.4 median 70\n",
      "avg 76.1 median 70\n",
      "avg 74.6 median 70\n",
      "avg 73.7 median 67\n",
      "avg 73.2 median 67\n",
      "avg 76.4 median 67\n",
      "avg 75.4 median 67\n",
      "avg 74.0 median 60\n",
      "avg 73.6 median 63\n",
      "avg 72.4 median 60\n",
      "avg 75.6 median 63\n",
      "avg 75.2 median 60\n",
      "avg 74.0 median 60\n",
      "avg 74.1 median 60\n",
      "avg 73.3 median 60\n",
      "avg 72.8 median 60\n",
      "avg 72.1 median 60\n",
      "avg 71.4 median 59\n",
      "avg 71.0 median 59\n",
      "avg 71.3 median 59\n",
      "avg 71.4 median 60\n",
      "avg 72.5 median 60\n",
      "avg 72.2 median 60\n",
      "avg 71.8 median 60\n",
      "avg 73.7 median 60\n",
      "avg 72.8 median 60\n",
      "avg 73.2 median 60\n",
      "avg 74.1 median 60\n",
      "avg 73.3 median 60\n",
      "avg 73.5 median 60\n",
      "avg 73.2 median 60\n",
      "avg 73.0 median 60\n",
      "avg 73.2 median 60\n",
      "avg 72.8 median 60\n",
      "avg 72.5 median 60\n",
      "avg 73.6 median 60\n",
      "avg 73.2 median 60\n",
      "avg 73.7 median 60\n",
      "avg 73.3 median 60\n",
      "avg 73.4 median 60\n",
      "avg 72.7 median 60\n",
      "avg 75.7 median 60\n",
      "avg 76.4 median 60\n",
      "avg 80.0 median 60\n",
      "avg 80.9 median 62\n",
      "avg 80.6 median 60\n",
      "avg 80.5 median 62\n",
      "avg 80.0 median 60\n",
      "avg 79.7 median 60\n",
      "avg 79.4 median 60\n",
      "avg 79.6 median 60\n",
      "avg 79.0 median 60\n",
      "avg 78.3 median 60\n",
      "avg 78.8 median 60\n",
      "avg 78.4 median 60\n",
      "avg 78.2 median 60\n",
      "avg 77.7 median 60\n",
      "avg 77.4 median 60\n",
      "avg 77.2 median 60\n",
      "avg 77.6 median 60\n",
      "avg 77.4 median 60\n",
      "avg 77.2 median 60\n",
      "avg 77.1 median 60\n",
      "avg 77.2 median 60\n",
      "avg 77.2 median 60\n",
      "avg 78.5 median 60\n",
      "avg 78.9 median 62\n",
      "avg 78.7 median 60\n",
      "avg 78.3 median 60\n",
      "avg 78.8 median 60\n",
      "avg 78.3 median 60\n",
      "avg 77.9 median 60\n",
      "avg 77.4 median 60\n",
      "avg 78.3 median 60\n",
      "avg 77.9 median 60\n"
     ]
    }
   ],
   "source": [
    "from cry.sbox2 import SBox2\n",
    "\n",
    "nb = 10\n",
    "\n",
    "print(\"expected\", 1.5**nb)\n",
    "\n",
    "nmonos = []\n",
    "\n",
    "for _ in range(100):\n",
    "    T = TSHash(n=32)\n",
    "    \n",
    "    y = []\n",
    "    for x in Bin.iter(nb):\n",
    "        x = Bin(x.tuple[::-1])\n",
    "        x = x.list[::-1]\n",
    "        xx = [x.pop()]\n",
    "        for i in range(1, 1000):\n",
    "            if not x:\n",
    "                break\n",
    "            xx += [0] * i\n",
    "            xx += [x.pop()]\n",
    "            \n",
    "        hh = T.fromF(T.calc_ext(xx))\n",
    "        y.append(hh)\n",
    "    #print(\"\".join(map(str, xx)))\n",
    "    \n",
    "    #print(\"degs\", SBox2(y).degrees())\n",
    "    monos = set()\n",
    "    for a in SBox2(y, m=32).anfs():\n",
    "        monos |= set(a.monomials())\n",
    "    #print(\"monos\", len(monos))\n",
    "    #print()\n",
    "    \n",
    "    # for a in SBox2(y).anfs()[:25]:\n",
    "    #     print(a)\n",
    "    nmonos.append(len(monos))\n",
    "    print(\"avg\", \"%.1f\" % (sum(nmonos)/len(nmonos)), \"median\", sorted(nmonos)[len(nmonos)//2])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "13a77bed-4ff1-4ae7-8b4a-52acc166b539",
   "metadata": {},
   "source": [
    "# High-probability differentials"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9354a579-c1e9-43d1-9707-d198e16d099b",
   "metadata": {},
   "source": [
    "## Last bit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "01051ef9-263f-4d74-a6fb-7df914c0292a",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-11-26T12:19:39.954117Z",
     "iopub.status.busy": "2023-11-26T12:19:39.953997Z",
     "iopub.status.idle": "2023-11-26T12:19:41.932141Z",
     "shell.execute_reply": "2023-11-26T12:19:41.931687Z",
     "shell.execute_reply.started": "2023-11-26T12:19:39.954107Z"
    }
   },
   "outputs": [],
   "source": [
    "for _ in range(100):\n",
    "    T = TSHash(n=128)\n",
    "    m1 = Bin.random(100)\n",
    "    m2 = m1 ^ 1\n",
    "    assert T.calc_raw(m1) == T.calc_raw(m2) ^ T.h_raw"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a9919f64-95b4-4ff9-9208-5ff7b83920e4",
   "metadata": {},
   "source": [
    "## 2nd-to-last"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "d63e4f08-2913-4661-af38-b316216f45bb",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-11-26T12:19:41.932742Z",
     "iopub.status.busy": "2023-11-26T12:19:41.932616Z",
     "iopub.status.idle": "2023-11-26T12:19:54.714845Z",
     "shell.execute_reply": "2023-11-26T12:19:54.714456Z",
     "shell.execute_reply.started": "2023-11-26T12:19:41.932730Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.498\n",
      "0.482\n",
      "0.483\n",
      "0.503\n",
      "0.513\n",
      "0.521\n",
      "0.521\n",
      "0.509\n",
      "0.517\n",
      "0.514\n",
      "Prob (%): 49.8 48.2 48.3 50.3 51.3 52.1 52.1 50.9 51.7 51.4\n",
      "Avg (%): 50.6\n"
     ]
    }
   ],
   "source": [
    "probs = []\n",
    "for _ in range(10):\n",
    "    while True:\n",
    "        T = TSHash(n=128)\n",
    "        if (T.alpha * T.h).trace() == 0:\n",
    "            break\n",
    "            \n",
    "    ngood = 0\n",
    "    for t in range(1000):\n",
    "        m1 = Bin.random(100)\n",
    "        m2 = m1 ^ 2\n",
    "        ngood += (T.calc_raw(m1) == T.calc_raw(m2) ^ T.fromF(T.h * T.g))\n",
    "    prob = ngood/1000\n",
    "    probs.append(prob)\n",
    "    print(prob)\n",
    "    assert 0.4 < prob < 0.6\n",
    "print(\"Prob (%):\", *[f\"{prob*100:.1f}\" for prob in probs])\n",
    "print(\"Avg (%):\", f\"{sum(probs)/len(probs)*100:.1f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dba58248-df5e-48c5-89c0-5fc7a2959761",
   "metadata": {},
   "source": [
    "## 3rd-to-last"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "093199e6-ca36-45cc-bca6-8b2cdc46110c",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-11-26T12:19:54.716380Z",
     "iopub.status.busy": "2023-11-26T12:19:54.716215Z",
     "iopub.status.idle": "2023-11-26T12:20:07.606433Z",
     "shell.execute_reply": "2023-11-26T12:20:07.605910Z",
     "shell.execute_reply.started": "2023-11-26T12:19:54.716368Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.244\n",
      "0.269\n",
      "0.255\n",
      "0.28\n",
      "0.233\n",
      "0.285\n",
      "0.271\n",
      "0.235\n",
      "0.266\n",
      "0.249\n",
      "Prob (%): 24.4 26.9 25.5 28.0 23.3 28.5 27.1 23.5 26.6 24.9\n",
      "Avg (%): 25.9\n"
     ]
    }
   ],
   "source": [
    "probs = []\n",
    "for _ in range(10):\n",
    "    while True:\n",
    "        T = TSHash(n=128)\n",
    "        if (T.alpha * T.h).trace() == (T.alpha * T.h * T.g).trace() == 0:\n",
    "            break\n",
    "    \n",
    "    #print(T.h_raw)\n",
    "    ngood = 0\n",
    "    for t in range(1000):\n",
    "        m1 = Bin.random(100)\n",
    "        m2 = m1 ^ 4\n",
    "        ngood += (T.calc_raw(m1) == T.calc_raw(m2) ^ T.fromF(T.h * T.g**2))\n",
    "    prob = ngood/1000\n",
    "    probs.append(prob)\n",
    "    print(prob)\n",
    "print(\"Prob (%):\", *[f\"{prob*100:.1f}\" for prob in probs])\n",
    "print(\"Avg (%):\", f\"{sum(probs)/len(probs)*100:.1f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b1c96cc8-4001-4995-a295-b08b32849add",
   "metadata": {},
   "source": [
    "# Generalized birthday"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "42fde304-9902-4c20-8d17-f513158f2639",
   "metadata": {},
   "source": [
    "## Target parameters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "52e74bba-8bf9-4b97-9ec6-219c8bdb8f41",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-11-26T12:20:07.607111Z",
     "iopub.status.busy": "2023-11-26T12:20:07.606966Z",
     "iopub.status.idle": "2023-11-26T12:20:07.623307Z",
     "shell.execute_reply": "2023-11-26T12:20:07.622918Z",
     "shell.execute_reply.started": "2023-11-26T12:20:07.607100Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "target aaaaaaaaaaaaaaaaaaaa\n"
     ]
    }
   ],
   "source": [
    "n = 80\n",
    "T = TSHash(n=n, seed=100)\n",
    "\n",
    "a = b\"\\xaa\" * (n//8)\n",
    "a = (Bin(a).int | 2**(n-1))  # the MSB has to be equal to 1 for the prev. state to be controlled\n",
    "target = T.toF(a)\n",
    "\n",
    "assert T.fromF((target-T.h)/T.g) & 1 == 1\n",
    "        \n",
    "print(\"target\", T.fromF(target).hex)\n",
    "#c0*g^(e1+e2+e3) + h*(g^(e2+e3) + g^e3 + 1) = target"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "91106286-bc59-4fe8-9881-7215d0d3c676",
   "metadata": {},
   "source": [
    "## Attack parameters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "19459c68-5c12-4290-9341-04e7a41b6d23",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-11-26T12:20:07.624099Z",
     "iopub.status.busy": "2023-11-26T12:20:07.623895Z",
     "iopub.status.idle": "2023-11-26T12:20:07.632327Z",
     "shell.execute_reply": "2023-11-26T12:20:07.631797Z",
     "shell.execute_reply.started": "2023-11-26T12:20:07.624081Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Attack parameters:\n",
      "  number of monomials: 16 = # merges = # final candidates to check\n",
      "  chunk size: 2097152 = cost of 1 merge operation =~ message length\n",
      "  bits: 20 filter per merge\n",
      "\n",
      "chunk size 2097152 21.0\n"
     ]
    }
   ],
   "source": [
    "levels = 4  # depth\n",
    "nchunks = 2**levels\n",
    "bits = (n + levels - 1) // levels\n",
    "chunk_size = int(2**(n / levels) * 2)\n",
    "\n",
    "print(\"Attack parameters:\")\n",
    "print(\"  number of monomials:\", 2**levels, \"= # merges = # final candidates to check\")\n",
    "print(\"  chunk size:\", chunk_size, \"= cost of 1 merge operation =~ message length\")\n",
    "print(\"  bits:\", bits, \"filter per merge\")\n",
    "print()\n",
    "\n",
    "emax = chunk_size\n",
    "tar = (target - T.s0 * T.g**emax ) / T.h - 1\n",
    "int_tar = T.fromF(tar)\n",
    "\n",
    "print(\"chunk size\", chunk_size, math.log(chunk_size, 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e819ae26-5a78-4ffe-bebf-a589e962a6b1",
   "metadata": {},
   "source": [
    "## Functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "4f5ff695-8dd1-4105-8734-29e3b972b45e",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-11-26T12:20:07.633380Z",
     "iopub.status.busy": "2023-11-26T12:20:07.633142Z",
     "iopub.status.idle": "2023-11-26T12:20:07.637738Z",
     "shell.execute_reply": "2023-11-26T12:20:07.637209Z",
     "shell.execute_reply.started": "2023-11-26T12:20:07.633365Z"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "def message_fit(T, emax, gpoly, add_emax=True):\n",
    "    \"\"\"Reconstruct message given list of iterations where P1 was added\"\"\"\n",
    "    gpoly = sorted(gpoly, reverse=True)\n",
    "    iters = [emax-e for e in gpoly]\n",
    "    if add_emax:\n",
    "        iters.append(emax)\n",
    "\n",
    "    v = T.s0_raw\n",
    "    itr = 0\n",
    "    ii = 0\n",
    "    msg = []\n",
    "    for ei in iters:\n",
    "        while itr < ei:\n",
    "            while v & 1 == 0:\n",
    "                v >>= 1\n",
    "                itr += 1\n",
    "            v >>= 1\n",
    "            v ^= T.p0_raw\n",
    "            itr += 1\n",
    "            msg.append(0)\n",
    "            \n",
    "        if itr != ei:\n",
    "            print(\"failed:\", itr, \">\", ei)\n",
    "            return\n",
    "    \n",
    "        msg[-1] = 1\n",
    "        v ^= T.p0_raw ^ T.p1_raw\n",
    "    return Bin(msg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "cd54c04a-a13c-44ae-8bbb-246cd5457503",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-11-26T12:20:07.638423Z",
     "iopub.status.busy": "2023-11-26T12:20:07.638285Z",
     "iopub.status.idle": "2023-11-26T12:20:07.643181Z",
     "shell.execute_reply": "2023-11-26T12:20:07.642769Z",
     "shell.execute_reply.started": "2023-11-26T12:20:07.638411Z"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "EFAIL = None\n",
    "def message_fit_check(T, emax, gpoly, debug=0):\n",
    "    \"\"\"Qucikly check possibility of a given list of iterations where MASK1 was added,\n",
    "    without reconstructing the message\"\"\"\n",
    "    global EFAIL\n",
    "    \n",
    "    gpoly = sorted(gpoly, reverse=True)\n",
    "    iters = [emax-e for e in gpoly]\n",
    "    iters.append(emax)\n",
    "    if debug:\n",
    "        print(iters)\n",
    "    v = T.s0\n",
    "    itr = 0\n",
    "    ii = 0\n",
    "    prev = 0\n",
    "    for eii, ei in enumerate(iters):\n",
    "        eadd = ei - prev\n",
    "        prev = ei\n",
    "        v = v*T.g**(eadd-1)\n",
    "        if T.tr(v) != 1:\n",
    "            EFAIL = eii\n",
    "            if debug:\n",
    "                print(\"failed at:\", eii, \"itr=\", ei, \"val\", fromF(v))\n",
    "            return False\n",
    "        v = v * T.g + T.h        \n",
    "    return True  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "bb7dd50f-7e27-45dc-a50c-ba03cc5c3876",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-11-26T12:20:07.643844Z",
     "iopub.status.busy": "2023-11-26T12:20:07.643704Z",
     "iopub.status.idle": "2023-11-26T12:20:07.650444Z",
     "shell.execute_reply": "2023-11-26T12:20:07.649781Z",
     "shell.execute_reply.started": "2023-11-26T12:20:07.643832Z"
    }
   },
   "outputs": [],
   "source": [
    "def merge(chunk1, chunk2, mask, target=0, limit=float(\"inf\"), debug=0):\n",
    "    \"\"\"Merge procedure for the Wagner's method.\"\"\"\n",
    "    ab = []\n",
    "    tab = {}\n",
    "    for bb, eb in chunk1:\n",
    "        key = bb & mask\n",
    "        if key not in tab:\n",
    "            tab[key] = []\n",
    "        tab[key].append((bb, eb))\n",
    "    \n",
    "    if debug:\n",
    "        cnt = Counter()\n",
    "        for bb, eb in chunk1:\n",
    "            key = bb & mask\n",
    "            cnt[key] += 1\n",
    "        print(\"distrib chunk1\", cnt.most_common(10))\n",
    "        cnt = Counter()\n",
    "        for bb, eb in chunk2:\n",
    "            key = bb & mask\n",
    "            cnt[key] += 1\n",
    "        print(\"distrib chunk2\", cnt.most_common(10))\n",
    "\n",
    "    for aa, ea in chunk2:\n",
    "        key = (aa ^ target) & mask\n",
    "        for bb, eb in tab.get(key, ()):\n",
    "            #assert (aa ^ bb) & mask == target & mask\n",
    "            if aa != bb and (chunk1 is not chunk2 or aa < bb):\n",
    "                ab.append((aa ^ bb, ea + eb))\n",
    "            #if len(ab) >= limit:\n",
    "#                return ab\n",
    "    shuffle(ab)\n",
    "    return ab[:limit]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ec74c28c-bac8-4253-8793-f03b3e6ed3a9",
   "metadata": {},
   "source": [
    "## Attack"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ace82a8d-b9cb-4b93-bff3-7185dae6e212",
   "metadata": {},
   "source": [
    "### Base list generation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "10d70bda-4bd0-4ec1-b663-a02c79424fb6",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-11-26T12:20:07.652042Z",
     "iopub.status.busy": "2023-11-26T12:20:07.651428Z",
     "iopub.status.idle": "2023-11-26T12:20:09.636761Z",
     "shell.execute_reply": "2023-11-26T12:20:09.636219Z",
     "shell.execute_reply.started": "2023-11-26T12:20:07.652017Z"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "val = Bin.unit(0, n).int\n",
    "e = 0\n",
    "chunk = []\n",
    "mask = Bin.full(bits).resize(n).int\n",
    "for j in range(chunk_size):\n",
    "    if len(chunk) < chunk_size:\n",
    "        chunk.append((val, (e,)))\n",
    "    if val & 1:\n",
    "        val >>= 1\n",
    "        val ^= T.p0_raw.int\n",
    "    else:\n",
    "        val >>= 1\n",
    "    e += 1\n",
    "chunk = chunk[2*n:]  # avoid basic zeroes (they are good but need handling)\n",
    "shuffle(chunk)\n",
    "len(chunk)\n",
    "assert T.toF(val) == T.g**chunk_size"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4405bb83-5537-4ddd-9d33-484a7d423fdf",
   "metadata": {},
   "source": [
    "### Merges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "ca55de0a-7d9a-4412-bcb4-0e199d05d2e3",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-11-26T12:20:09.637420Z",
     "iopub.status.busy": "2023-11-26T12:20:09.637287Z",
     "iopub.status.idle": "2023-11-26T12:21:51.837153Z",
     "shell.execute_reply": "2023-11-26T12:21:51.836590Z",
     "shell.execute_reply.started": "2023-11-26T12:20:09.637409Z"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "LEVEL 0 -> 1 / 4\n",
      "2096992 2096992 ->\n",
      "2097152 2096813\n",
      "LEVEL 1 -> 2 / 4\n",
      "2097152 2096813 ->\n",
      "2095001 2097152\n",
      "LEVEL 2 -> 3 / 4\n",
      "2095001 2097152 ->\n",
      "2092542 2097152\n",
      "LEVEL 3 -> 4 / 4\n",
      "2092542 2097152 ->\n",
      "2092542 2097152\n"
     ]
    }
   ],
   "source": [
    "z = chunk\n",
    "t = chunk\n",
    "for i in range(levels):\n",
    "    print(\"LEVEL\", i, \"->\", i+1, \"/\", levels)\n",
    "    print(len(z), len(t), \"->\")\n",
    "    mask = Bin.full(bits*(i+1)).resize(n).int\n",
    "    t = merge(t, z, mask, target=int_tar, limit=chunk_size)\n",
    "    if i != levels-1:\n",
    "        z = merge(z, z, mask, target=0, limit=chunk_size)\n",
    "    print(len(z), len(t))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8ab4c4e2-17e0-4f09-a404-0612c30bf235",
   "metadata": {},
   "source": [
    "### Candidate testing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "9c0c18b4-c925-4a0c-a700-b45d45b5fdf5",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-11-26T12:21:51.837850Z",
     "iopub.status.busy": "2023-11-26T12:21:51.837720Z",
     "iopub.status.idle": "2023-11-26T12:21:54.915550Z",
     "shell.execute_reply": "2023-11-26T12:21:54.915087Z",
     "shell.execute_reply.started": "2023-11-26T12:21:51.837838Z"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "good! 44808\n",
      "\n"
     ]
    }
   ],
   "source": [
    "for isol, (res, ids) in enumerate(t):\n",
    "    if message_fit_check(T, emax, ids):\n",
    "        print()\n",
    "        print(\"good!\", isol)\n",
    "        print()\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "925ca2ec-eb9d-41b8-bde6-ebcb9cbaa5fd",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-11-26T12:21:54.916258Z",
     "iopub.status.busy": "2023-11-26T12:21:54.916143Z",
     "iopub.status.idle": "2023-11-26T12:22:18.668971Z",
     "shell.execute_reply": "2023-11-26T12:22:18.668402Z",
     "shell.execute_reply.started": "2023-11-26T12:21:54.916248Z"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1049351"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "msg = message_fit(T, emax, t[isol][1])\n",
    "len(msg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "2c04159d-d9f5-4f4c-bc5f-a60cf21b9d36",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-11-26T12:22:18.669848Z",
     "iopub.status.busy": "2023-11-26T12:22:18.669650Z",
     "iopub.status.idle": "2023-11-26T12:22:18.742425Z",
     "shell.execute_reply": "2023-11-26T12:22:18.742130Z",
     "shell.execute_reply.started": "2023-11-26T12:22:18.669830Z"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(44810,\n",
       " 167928,\n",
       " 267593,\n",
       " 283893,\n",
       " 372291,\n",
       " 380101,\n",
       " 420588,\n",
       " 431687,\n",
       " 543158,\n",
       " 611284,\n",
       " 779121,\n",
       " 815516,\n",
       " 836280,\n",
       " 858023,\n",
       " 865300,\n",
       " 1047853,\n",
       " 1049350)"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "msg.support"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "f0839363-ef37-45c0-9681-88644ace0c10",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-11-26T12:22:18.743191Z",
     "iopub.status.busy": "2023-11-26T12:22:18.742939Z",
     "iopub.status.idle": "2023-11-26T12:22:18.834845Z",
     "shell.execute_reply": "2023-11-26T12:22:18.834358Z",
     "shell.execute_reply.started": "2023-11-26T12:22:18.743176Z"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "assert msg == sum(2**(msg.n-1-i) for i in msg.support)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "534f726b-ab95-4566-8f71-2b94cef9654a",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-11-26T12:22:18.835513Z",
     "iopub.status.busy": "2023-11-26T12:22:18.835394Z",
     "iopub.status.idle": "2023-11-26T12:22:24.795643Z",
     "shell.execute_reply": "2023-11-26T12:22:24.795234Z",
     "shell.execute_reply.started": "2023-11-26T12:22:18.835503Z"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'aaaaaaaaaaaaaaaaaaaa'"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "T.calc_raw(msg).hex"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3da9dcdb-8c9c-41cd-bd14-173de27a155e",
   "metadata": {},
   "source": [
    "# Linearization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "1a4ef579-21cf-470d-82f7-f1be3055580f",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-11-26T12:22:24.796296Z",
     "iopub.status.busy": "2023-11-26T12:22:24.796126Z",
     "iopub.status.idle": "2023-11-26T12:22:24.799385Z",
     "shell.execute_reply": "2023-11-26T12:22:24.799044Z",
     "shell.execute_reply.started": "2023-11-26T12:22:24.796282Z"
    }
   },
   "outputs": [],
   "source": [
    "from linearization import Linearization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "8b44e48f-a514-4f38-a185-74689ab328a4",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-11-26T12:22:24.799995Z",
     "iopub.status.busy": "2023-11-26T12:22:24.799853Z",
     "iopub.status.idle": "2023-11-26T12:22:26.635901Z",
     "shell.execute_reply": "2023-11-26T12:22:26.635422Z",
     "shell.execute_reply.started": "2023-11-26T12:22:24.799983Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "found s 255\n",
      "found l 8344\n"
     ]
    }
   ],
   "source": [
    "T = TSHash(n=80)\n",
    "L = Linearization(T)\n",
    "L.linearize_prefix(N=10)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "38219829-d910-4af7-9887-beb2f0d1de9b",
   "metadata": {},
   "source": [
    "Optional: display ANF (requires module `cry` in sage):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "792340af-62ff-47b4-87bf-debaa7090ae4",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-11-26T12:22:26.637661Z",
     "iopub.status.busy": "2023-11-26T12:22:26.637496Z",
     "iopub.status.idle": "2023-11-26T12:22:55.243733Z",
     "shell.execute_reply": "2023-11-26T12:22:55.243307Z",
     "shell.execute_reply.started": "2023-11-26T12:22:26.637650Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0000000000 80 -> 41\n",
      "0000000001 80 -> 38\n",
      "0000000010 80 -> 42\n",
      "0000000011 80 -> 39\n",
      "0000000100 80 -> 35\n",
      "0000000101 80 -> 48\n",
      "0000000110 80 -> 47\n",
      "0000000111 80 -> 36\n",
      "0000001000 80 -> 43\n",
      "0000001001 80 -> 43\n",
      "1\n",
      "x1 + x4 + x5 + x7 + x8 + x9 + 1\n",
      "x0 + x2 + x7\n",
      "x2 + x3 + x4 + x9\n",
      "x0 + x2 + x4 + x6 + x7 + 1\n",
      "x3 + x4 + x6 + x7 + x8 + 1\n",
      "x2 + x3 + x4 + x6 + x7 + x8 + x9\n",
      "x4 + x5 + x6\n",
      "x0 + x1 + x4 + x5 + x6 + x7 + 1\n",
      "x1 + x2 + x3 + x5 + x6 + x9 + 1\n",
      "...\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/tmp/ipykernel_1311557/3817303393.py:11: DeprecationWarning: the function is_Polynomial is deprecated; use isinstance(x, sage.structure.element.Polynomial) instead\n",
      "See https://github.com/sagemath/sage/issues/32709 for details.\n",
      "  anfs = SBox2(y).anfs()\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[1, x9, x8, x7, x6, x5, x4, x3, x2, x1, x0]"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from cry.sbox2 import SBox2\n",
    "\n",
    "y = []\n",
    "for x0 in Bin.iter(L.prefix_N):\n",
    "    emsg = L.eval_prefix_raw(x0)\n",
    "    msg = L.T.compress(emsg)\n",
    "    if x0 < 10:\n",
    "        print(x0, len(emsg), \"->\", len(msg))\n",
    "    y.append(emsg)\n",
    "\n",
    "anfs = SBox2(y).anfs()\n",
    "\n",
    "for a in anfs[:10]:\n",
    "    print(a)\n",
    "print(\"...\")\n",
    "\n",
    "monos = set()\n",
    "for a in anfs:\n",
    "    monos |= set(a.monomials())\n",
    "\n",
    "sorted(monos)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageConda",
   "language": "python",
   "name": "sageconda"
  },
  "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.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}