BehindTheScene/RSAPublicKeyParamsUBoot/rsa_public_key_params_uboot.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# RSA Signature verification in U-Boot\n",
    "\n",
    "<img src=\"secure_boot_in_uboot.png\" alt=\"Verified boot in U-Boot\" width=\"800\"/>\n",
    "\n",
    "U-Boot's new verified boot feature provides a mechanism for verifying images while still allowing them to be upgraded. Kernel image is loaded into memory by U-Boot and can be verified in U-Boot.\n",
    "\n",
    "U-Boot provided utility functions to verify the signature. Currently U-Boot supports RSA signature verification encrypted on SHA1 / SHA256 message digests.\n",
    "\n",
    "U-Boot has the infrastructure to verify kernel image in FIT format. If the kernel image is in legacy format, a simple wrapper can be written to verify its signature."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# RSA sign and verify using OpenSSL\n",
    "\n",
    "Signature creation and verification can be performed using OpenSSL. OpenSSL uses public and private key files to validate and generate the signature respectively. However in case of U-Boot OpenSSL is not available and hence the verification is done using few parameters generated from public key. Read RSA sign and verify using Openssl : Behind the scene for more details."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Generating RSA private key, 512 bit long modulus\n",
      ".......+++++++++++++++++++++++++++\n",
      "....+++++++++++++++++++++++++++\n",
      "e is 65537 (0x10001)\n",
      "writing RSA key\n",
      "Verified OK\n"
     ]
    }
   ],
   "source": [
    "# Create a file containing all lower case alphabets\n",
    "!echo abcdefghijklmnopqrstuvwxyz > myfile.txt\n",
    "\n",
    "# Generate 512 bit Private key\n",
    "!openssl genrsa -out myprivate.pem 512\n",
    "\n",
    "# Separate the public part from the Private key file.\n",
    "!openssl rsa -in myprivate.pem -pubout > mypublic.pem\n",
    "\n",
    "# Sign the file using sha1 digest and PKCS1 padding scheme\n",
    "!openssl dgst -sha1 -sign myprivate.pem -out sha1.sign myfile.txt\n",
    "\n",
    "# Verify the signature of file\n",
    "!openssl dgst -sha1 -verify mypublic.pem -signature sha1.sign myfile.txt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# View the public key details\n",
    "\n",
    "Public key pem file is in base64 format and can be printed. [Read RSA public key : Behind the scene](https://medium.com/@bn121rajesh/understanding-rsa-public-key-70d900b1033c) for more details. Modulus and public exponent are encoded in to the public key."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Public-Key: (512 bit)\r\n",
      "Modulus:\r\n",
      "    00:ec:20:80:b1:08:94:3c:35:68:0f:78:4f:62:e4:\r\n",
      "    a8:f3:18:ad:46:28:f5:80:4b:b5:3a:dd:3a:76:76:\r\n",
      "    10:31:e7:cc:d1:5f:0a:3c:c7:93:61:c3:5b:a5:55:\r\n",
      "    8c:67:2d:9f:ce:80:8f:29:38:bd:e5:8a:78:15:f7:\r\n",
      "    71:8e:b2:a4:91\r\n",
      "Exponent: 65537 (0x10001)\r\n"
     ]
    }
   ],
   "source": [
    "# Get modulus and public exponent from public key\n",
    "!openssl rsa -pubin -inform PEM -text -noout < mypublic.pem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# U-Boot RSA public key parameters\n",
    "\n",
    "Signature verification in U-Boot is performed using the below parameters. All these parameters are available or generated from RSA public key. Read [signature.txt](http://git.denx.de/?p=u-boot.git;a=blob;f=doc/uImage.FIT/signature.txt;h=a7657226794baefd61f33448bbcad074a473f4b9;hb=refs/heads/master) for more details\n",
    "\n",
    "- **rsa,num-bits:** Number of key bits (e.g. 2048)\n",
    "\n",
    "- **rsa,modulus:** Modulus (N) as a big-endian multi-word integer\n",
    "\n",
    "- **rsa,exponent:** Public exponent (E) as a 64 bit unsigned integer\n",
    "\n",
    "- **rsa,r-squared:** $(2^{NumBits})^2$ as a big-endian multi-word integer\n",
    "\n",
    "- **rsa,n0-inverse:** $ \\left(\\frac{-1}{modulus[0]}\\right) \\% 2^{32}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## rsa,num-bits\n",
    "\n",
    "Number of key bits can be obtained directly from public key."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Public-Key: (512 bit)\r\n"
     ]
    }
   ],
   "source": [
    "# Get the key length in bits\n",
    "!openssl rsa -pubin -inform PEM -text -noout < mypublic.pem | head -1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## rsa,modulus\n",
    "\n",
    "Modulus (N) is obtained directly from public key, but must be converted into big endian words so that it can be used by U-Boot utility functions.\n",
    "\n",
    "Below utility function converts integer into big endian words"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def big_endian_words(val):\n",
    "    \"\"\"Convert integer into big endian words\"\"\"\n",
    "    # Convert val to hex\n",
    "    str_val = hex(val)[2:]\n",
    "\n",
    "    # Split the string into bytes\n",
    "    str_bytes = [str_val[i : i + 2] for i in range(0, len(str_val), 2)]\n",
    "\n",
    "    # Group bytes into group os 4 bytes\n",
    "    sets = [str_bytes[i : i + 4] for i in range(0, len(str_bytes), 4)]\n",
    "\n",
    "    # Reverse the bytes in each group (BIG endian)\n",
    "    list(map(list.reverse, sets))\n",
    "\n",
    "    # Join bytes in each group (WORD)\n",
    "    sets = list(map(''.join, sets))\n",
    "\n",
    "    # Convert to upper case\n",
    "    sets = list(map(str.upper, sets))\n",
    "\n",
    "    # Append '0x' to the word \n",
    "    sets = list(map('0x'.__add__, sets))\n",
    "    \n",
    "    return sets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Convert modulus into big endian word array. These words can be hardcoded in a file in u-boot or can be hard coded in device tree. (If kernel image is in FIT format"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['    00:ec:20:80:b1:08:94:3c:35:68:0f:78:4f:62:e4:',\n",
       " '    a8:f3:18:ad:46:28:f5:80:4b:b5:3a:dd:3a:76:76:',\n",
       " '    10:31:e7:cc:d1:5f:0a:3c:c7:93:61:c3:5b:a5:55:',\n",
       " '    8c:67:2d:9f:ce:80:8f:29:38:bd:e5:8a:78:15:f7:',\n",
       " '    71:8e:b2:a4:91']"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Get the modulus from public key\n",
    "modulus = !openssl rsa -pubin -inform PEM -text -noout < mypublic.pem | grep -v \"Exponent\\|Public\\|Modulus\"\n",
    "modulus"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['0xB18020EC', '0x353C9408', '0x4F780F68', '0xF3A8E462', '0x2846AD18', '0xB54B80F5', '0x763ADD3A', '0xE7311076', '0x0A5FD1CC', '0x6193C73C', '0x55A55BC3', '0x9F2D678C', '0x298F80CE', '0x8AE5BD38', '0x71F71578', '0x91A4B28E']\n"
     ]
    }
   ],
   "source": [
    "# Remove new lines, spaces and :\n",
    "mod = ''.join(modulus).replace('\\n', '').replace(' ', '').replace(':', '')\n",
    "\n",
    "# Convert modulus to integer\n",
    "mod_int = int(mod, 16)\n",
    "\n",
    "# Print the modulus in words\n",
    "print(big_endian_words(mod_int))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## rsa,exponent\n",
    "\n",
    "Public exponent (E) is obtained directly from public key. U-boot supports public exponent up to 64 bits.\n",
    "However public exponent is usually a default value (65537)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Exponent: 65537 (0x10001)\r\n"
     ]
    }
   ],
   "source": [
    "# Get the public exponent\n",
    "!openssl rsa -pubin -inform PEM -text -noout < mypublic.pem | tail -1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## rsa,r-squared\n",
    "\n",
    "R-Squared value is obtained from num-bits as below.\n",
    "\n",
    "$$\n",
    "RSquared = (2^{NumBits})^2\n",
    "$$\n",
    "\n",
    "R-Squared value is also represented in big endian word format. So we use the same procedure as in modulus"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "512"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Get the num bits from public key\n",
    "numbits = !openssl rsa -pubin -inform PEM -text -noout < mypublic.pem | head -1 | grep -Eo \"\\d+\"\n",
    "\n",
    "# Convert num_bits to integer\n",
    "num_bits = int(numbits[0])\n",
    "num_bits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['0x7A9286B3', '0xAFCFA072', '0xBA0F5A99', '0xFD494F91', '0x775BEEC7', '0xB8883A54', '0xF54A8DE5', '0x63150FF0', '0xE1D4189E', '0x36806001', '0x052C013D', '0x02019DEE', '0x2BD25E44', '0x60694872', '0x38AE42A6', '0x4E9F0330']\n"
     ]
    }
   ],
   "source": [
    "# Print the R-Squared in big endian words\n",
    "print(big_endian_words((2 ** num_bits) ** 2 % mod_int))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## rsa,n0-inverse\n",
    "\n",
    "n0-inverse is the negative multiplicative inverse of modulus in $2^{32}$ modulo.\n",
    "\n",
    "$$\n",
    "n0inverse = \\left(\\frac{-1}{modulus[0]}\\right) \\% 2^{32}\n",
    "$$\n",
    "\n",
    "n0inverse is the solution to the equation:\n",
    "\n",
    "$$\n",
    "(modulus * n0inverse) \\% 2^{32} = -1\n",
    "$$\n",
    "\n",
    "n0inverse is the integral solution for this diophantine equation:\n",
    "\n",
    "$$\n",
    "modulus * n0inverse = 2^{32} * k - 1\n",
    "$$\n",
    "\n",
    "\n",
    "Wolfram Alpha website provides solution to equations. Copy and paste the diophantine equation in [Wolfram Alpha website](https://www.wolframalpha.com) to get integral solutions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4294967296*t_0 + 745694095"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Diophantine equations can be solved using sympy package.\n",
    "import sympy\n",
    "from sympy.solvers.diophantine import diop_solve\n",
    "inv, k = sympy.symbols('inv k')\n",
    "\n",
    "# modulus[0] is the least significat word (in modulo 2**32)\n",
    "eq = diop_solve((mod_int & 0xFFFFFFFF) * inv - (2 ** 32) * k + 1)\n",
    "eq[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "745694095"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# solutions for n0inverse\n",
    "e = eq[0]\n",
    "m = e.as_coefficients_dict()[list(e.free_symbols)[0]]\n",
    "c = e.as_coefficients_dict()[1]\n",
    "n0inverse = (m + c) % m\n",
    "n0inverse"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# References\n",
    "\n",
    "1. [Verified Boot (From pacific simplicity)](https://pacificsimplicity.ca/blog/verified-boot-–-introduction-u-boot’s-secure-boot)\n",
    "1. [Verified Boot (From U-Boot)](http://git.denx.de/?p=u-boot.git;a=blob;f=doc/uImage.FIT/verified-boot.txt;h=41c9fa9e09f97d047f980a31fcdbad5cd74d0db2;hb=refs/heads/master)\n",
    "1. [Solving Diophantine (From Sympy)](https://docs.sympy.org/latest/modules/solvers/diophantine.html)\n",
    "1. [Solving Diophantine (From WolFramAlpha)](https://www.wolframalpha.com)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}