python-rsa verify BB'06.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import hashlib\n",
    "import rsa\n",
    "import binascii\n",
    "import os\n",
    "from gmpy2 import mpz, iroot, powmod, mul, t_mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def to_bytes(n):\n",
    "    \"\"\" Return a bytes representation of a int \"\"\"\n",
    "    return n.to_bytes((n.bit_length() // 8) + 1, byteorder='big')\n",
    "\n",
    "def from_bytes(b):\n",
    "    \"\"\" Makes a int from a bytestring \"\"\"\n",
    "    return int.from_bytes(b, byteorder='big')\n",
    "\n",
    "def get_bit(n, b):\n",
    "    \"\"\" Returns the b-th rightmost bit of n \"\"\"\n",
    "    return ((1 << b) & n) >> b\n",
    "\n",
    "def set_bit(n, b, x):\n",
    "    \"\"\" Returns n with the b-th rightmost bit set to x \"\"\"\n",
    "    if x == 0: return ~(1 << b) & n\n",
    "    if x == 1: return (1 << b) | n\n",
    "\n",
    "def cube_root(n):\n",
    "    return int(iroot(mpz(n), 3)[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "message = \"Ciao, mamma!!\".encode(\"ASCII\")\n",
    "message_hash = hashlib.sha256(message).digest()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "ASN1_blob = rsa.pkcs1.HASH_ASN1['SHA-256']\n",
    "suffix = b'\\x00' + ASN1_blob + message_hash"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "b'003031300d060960864801650304020105000420a39ddaae64be645e43d483713135d6fad7c25d2956abab8d9a3dfdcd2b1b821b'"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "binascii.hexlify(suffix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "52"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(suffix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "suffix[-1]&0x01 == 1 # easy suffix computation works only with odd target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "sig_suffix = 1\n",
    "for b in range(len(suffix)*8):\n",
    "    if get_bit(sig_suffix ** 3, b) != get_bit(from_bytes(suffix), b):\n",
    "        sig_suffix = set_bit(sig_suffix, b, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "to_bytes(sig_suffix ** 3).endswith(suffix) # BOOM"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1248"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(to_bytes(sig_suffix ** 3)) * 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "while True:\n",
    "    prefix = b'\\x00\\x01' + os.urandom(2048//8 - 2)\n",
    "    sig_prefix = to_bytes(cube_root(from_bytes(prefix)))[:-len(suffix)] + b'\\x00' * len(suffix)\n",
    "    sig = sig_prefix[:-len(suffix)] + to_bytes(sig_suffix)\n",
    "    if b'\\x00' not in to_bytes(from_bytes(sig) ** 3)[:-len(suffix)]: break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "to_bytes(from_bytes(sig) ** 3).endswith(suffix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "to_bytes(from_bytes(sig) ** 3).startswith(b'\\x01')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(to_bytes(from_bytes(sig) ** 3)) == 2048//8 - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b'\\x00' not in to_bytes(from_bytes(sig) ** 3)[:-len(suffix)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "b'2b82e655c7c20ca36597c05904639fa53c476beee7822e1e03eb5d3c5128bc947c7dc53e33e453b32c69e3caf4eb3e472ff0dfc29d65126b4f1eddd4a64bbd63ce192752903fee1fff985a48f1048993f91732a603'"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "binascii.hexlify(sig)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "b'0141c9316c11defc55ef833ac67f78eb3ac191f5a69da2ea1d2e5f8e718fdc495cc68eb6576cce7d81e42eb717f37a122b709bbe476f5750df909fec2c3c1316787a3c7327a9ed9930ebbce8f5eb9f5155dc73d2f776fd085ea3cd85da8c2c01e5c79ae07cce8e615419d5e718dd4d34ce8cfccc7f6e167c756ad99cc13e3145151c69c76c2d14a5bb40a1bd9f6e095739f9963c042e76f4027ca49757e635b508f4efae58bcb9cc537e8237bb9d1ef35440b72cfc682dee97e2e8ed3e22a0c17ee80e78054c36a76f65e9003031300d060960864801650304020105000420a39ddaae64be645e43d483713135d6fad7c25d2956abab8d9a3dfdcd2b1b821b'"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "binascii.hexlify(to_bytes(from_bytes(sig) ** 3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "key = rsa.newkeys(2048)[0]\n",
    "key.e = 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rsa.verify(message, sig, key)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "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.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}