notebooks/ecdsa-is-weird.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# ECDSA is Weird\n",
    "\n",
    "This notebook demonstrates some unexpected properties of ECDSA signatures. This notebook was heavily inspired by [SalusaSecondus's \"Crypto Gotchas\"](https://github.com/SalusaSecondus/CryptoGotchas/blob/master/README.md).\n",
    "\n",
    "## ECDSA implementation using NIST P-256\n",
    "\n",
    "This notebook uses the NIST P-256 curve for demonstration, so we'll need to define that curve and it's base point first. This first block of code may be opaque. An annotated version is in its own [notebook](https://github.com/kelbyludwig/notebooks/blob/master/p-256.ipynb)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "p256 = 115792089210356248762697446949407573530086143415290314195533631308867097853951 \n",
    "a256 = p256 - 3 \n",
    "b256 = 41058363725152142129326129780047268409114441015993725554835256314039467401291 \n",
    "gx = 48439561293906451759052585252797914202762949526041747995844080717082404635286\n",
    "gy = 36134250956749795798585127919587881956611106672985015071877198253568414405109\n",
    "qq = 115792089210356248762697446949407573529996955224135760342422259061068512044369\n",
    "\n",
    "FF = GF(p256) \n",
    "EC = EllipticCurve([FF(a256), FF(b256)]) \n",
    "EC.set_order(qq) \n",
    "\n",
    "# base point\n",
    "G = EC(FF(gx), FF(gy))\n",
    "\n",
    "# finite field of GF(qq) where qq is the order of the group G\n",
    "Fq = GF(qq)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we have a base point, we can define some functions that make up ECDSA signing and verification."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from hashlib import sha256\n",
    "\n",
    "def sha256_hasher(m):\n",
    "    \"\"\"Hash a message and map it to an Integer\n",
    "    \"\"\"\n",
    "    s = sha256()\n",
    "    s.update(m)\n",
    "    digest = s.hexdigest()\n",
    "    return Integer(digest, 16)\n",
    "\n",
    "def generate_keypair(k=None):\n",
    "    \"\"\"Generate a keypair. If k is provided, use it as the private scalar.\n",
    "    \"\"\"\n",
    "    if k is None:\n",
    "        # a random private scalar, generated using a unsafe RNG \n",
    "        # for simplicity\n",
    "        k = randint(1, qq)\n",
    "    return k, k*G\n",
    "\n",
    "def sign(private_key, message, k=None, hasher=sha256_hasher):\n",
    "    \"\"\"Sign `message` with the specified private key.\n",
    "    \n",
    "    `message` is hashed and mapped to a group element\n",
    "    as part of signing. The default implementation of \n",
    "    is sha256_hasher.\n",
    "    \"\"\"\n",
    "    # a per-signature random scalar\n",
    "    if k is None:\n",
    "        k = randint(1, qq)\n",
    "    # a per-signature random point\n",
    "    x, _ = (k*G).xy()\n",
    "    # map various values to GF(qq) where qq is the order of\n",
    "    # group generated by G.\n",
    "    r = Fq(x)\n",
    "    k = Fq(k)\n",
    "    z = Fq(hasher(message))\n",
    "    pkq = Fq(private_key)\n",
    "    # compute the s value of the signature, in GF(qq)\n",
    "    s = k^-1 * (z + r * pkq)\n",
    "    return (r, s)\n",
    "\n",
    "def verify(public_key, message, r, s, hasher=sha256_hasher):\n",
    "    \"\"\"Verify a signature (`r`,`s`) over `message` with the\n",
    "    specified public key.\n",
    "    \n",
    "    `message` is hashed and mapped to a group element as part\n",
    "    of verification. The default implementation is sha256_hasher.\n",
    "    Verification must use the same hasher as `sign` in order to\n",
    "    produce correct results.\n",
    "    \"\"\"\n",
    "    # map the message to a element in GF(qq)\n",
    "    z = Fq(hasher(message))\n",
    "    # invert s in GF(qq)\n",
    "    sinv = s^-1\n",
    "    # compute intermediate verification scalars\n",
    "    u1 = z*sinv\n",
    "    u2 = r*sinv\n",
    "    # extract x, y values from point addition and scaling\n",
    "    x, _ = (Integer(u1)*G + Integer(u2)*public_key).xy()\n",
    "    return Fq(x) == r"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we have these functions, we can do a basic signing and verification roundtrip to check that we have done everything correctly."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "no problem!\n"
     ]
    }
   ],
   "source": [
    "# generate a keypair\n",
    "private, public = generate_keypair(13)\n",
    "\n",
    "# sign a message with our private key\n",
    "message = \"a message to sign!\"\n",
    "r, s = sign(private, message)\n",
    "\n",
    "# verify the signature is correct!\n",
    "assert verify(public, message, r, s), \"Signature was invalid!\"\n",
    "\n",
    "# verify incorrect signatures are invalid!\n",
    "_, new_public = generate_keypair(7)\n",
    "assert not verify(new_public, message, r, s), \"Invalid signature was valid!\"\n",
    "print(\"no problem!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With that out of the way we can start with the first weird property.\n",
    "\n",
    "## Signature malleability\n",
    "\n",
    "ECDSA signatures are malleable. Given a valid signature `(r, s)`, one can create a second valid signature by negating the `s` value. This is demonstrated below.\n",
    "\n",
    "This is not the only way in which signatures are malleable. Since ECDSA signatures are pairs of numbers, their encoding maybe maellable. Encodings of these pairs *should* only have one representation but some implementations may be more permissive. For example, the integer 2 may be encoded as the byte string `\\x02` or `\\x00\\x02`. [Project Wycheproof has great set of test vectors](https://github.com/google/wycheproof/blob/master/java/com/google/security/wycheproof/testcases/EcdsaTest.java) that looks for implementations that accept multiple encodings as valid."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "no problem!\n"
     ]
    }
   ],
   "source": [
    "# generate a random keypair\n",
    "private, public = generate_keypair()\n",
    "\n",
    "# sign a message with our private key\n",
    "message = \"a test of malleable signatures\"\n",
    "r, s = sign(private, message)\n",
    "\n",
    "# verify the signature is correct\n",
    "assert verify(public, message, r, s), \"Signature was invalid!\"\n",
    "\n",
    "# negate s and the signature will still be valid!\n",
    "assert verify(public, message, r, -s), \"Negated s signature was invalid!\"\n",
    "print(\"no problem!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Duplicate signatures\n",
    "\n",
    "The paper [\"Flaws in Applying Proof Methodologies to Signature Schemes\"](https://www.researchgate.net/publication/221355164_Flaws_in_Applying_Proof_Methodologies_to_Signature_Schemes) describes an interesting property of ECDSA which the author's call \"Duplicate Signatures\".\n",
    "\n",
    "Duplicate signatures are signatures that are the exact same for multiple distinct messages. It is trivial to generate a keypair that has valid duplicate signatures for chosen messages!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "no problem!\n"
     ]
    }
   ],
   "source": [
    "def create_duplicate_signatures_keypair(m1, m2):\n",
    "    \"\"\"Generates a keypair and signature given two messages `m1` and `m2`.\n",
    "    \n",
    "    The generated keypair will be valid. The generated (`r`, `s`) values are\n",
    "    a valid signature on both `m1` and `m2` for the generated public key.\n",
    "    \"\"\"\n",
    "    # generate a random scalar\n",
    "    k = randint(1, qq)\n",
    "    # get a random point's x value\n",
    "    x, _ = (k*G).xy()\n",
    "    # map values to GF(qq)\n",
    "    r = Fq(x)\n",
    "    k = Fq(k)\n",
    "    h1 = Fq(sha256_hasher(m1))\n",
    "    h2 = Fq(sha256_hasher(m2))\n",
    "    # generate a private scalar using specific values derived\n",
    "    # from the input messages and the random scalar\n",
    "    private_scalar = -(h1 + h2) / (2*r)\n",
    "    # generate a signature value for both messages\n",
    "    s = k^-1 * (h1 + private_scalar*r)\n",
    "    private_scalar = Integer(private_scalar)\n",
    "    return private_scalar, private_scalar*G, r, s\n",
    "\n",
    "\n",
    "private, public, r, s = create_duplicate_signatures_keypair(\"foo\", \"bar\")\n",
    "# verify the duplicate signature property\n",
    "assert verify(public, \"foo\", r, s)\n",
    "assert verify(public, \"bar\", r, s)\n",
    "\n",
    "# generate another signature to test the keypair being otherwise valid\n",
    "r2, s2 = sign(private, \"baz\")\n",
    "assert verify(public, \"baz\", r2, s2)\n",
    "\n",
    "print(\"no problem!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Creating a valid signatures without knowledge of a message\n",
    "\n",
    "Suppose I'm using a signature verification interface that accepts a hashed value instead of a message. That is, instead of a function like `verify` below, I use a function like `direct_verify`:\n",
    "\n",
    "```python\n",
    "def verify(public_key, message, r, s):\n",
    "    digest = hash(message)\n",
    "    # verification using digest\n",
    "    # ....\n",
    "    \n",
    "def direct_verify(public_key, digest, r, s):\n",
    "    # i trust you provided me a trustworthy digest\n",
    "    # verification using digest\n",
    "    # ....\n",
    "```\n",
    "\n",
    "As a signature verifier, if I trust digests without knowing the corresponding message, an attacker can generate valid signatures for any public key. In this case, the attacker doesn't necessarily know the corresponding *message* to the digest but a sufficiently trusting (or faulty) verifier may not recognize that.\n",
    "\n",
    "This trick was used by some person in an attempt to convince people that they invented Bitcoin. This great [\"Faketoshi\" application](https://albacore.io/faketoshi) demonstrates that you too can trick people into believing you invented Bitcoin!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "no problem!\n"
     ]
    }
   ],
   "source": [
    "def direct_verify(public, digest, r, s):\n",
    "    \"\"\"Verifies a signature given an already hashed message digest as an Integer\n",
    "    \"\"\"\n",
    "    direct_hasher = lambda x: x\n",
    "    return verify(public, digest, r, s, hasher=direct_hasher)\n",
    "\n",
    "def generate_signature_for_public_key(public_key):\n",
    "    \"\"\"Given any public key, this create a signature for a random digest.\n",
    "    \n",
    "    The corresponding message to the generated digest is unknown.\n",
    "    \"\"\"\n",
    "    # generate random scalars\n",
    "    a = randint(1, qq)\n",
    "    b = randint(1, qq)\n",
    "    # generate a random point using the above \n",
    "    # scalars and the target public key\n",
    "    R = a*G + b*public_key\n",
    "    x, _ = R.xy()\n",
    "    # map values to GF(qq)\n",
    "    a = Fq(a)\n",
    "    b = Fq(b)\n",
    "    # compute the signature values\n",
    "    r = Fq(x)\n",
    "    s = r / b\n",
    "    # compute the digest value\n",
    "    z = r * (a/b)\n",
    "    return Integer(z), r, s\n",
    "\n",
    "# generate a new keypair\n",
    "private, public = generate_keypair()\n",
    "\n",
    "# generate a signature and digest using only knowledge of the public key!\n",
    "digest, r, s = generate_signature_for_public_key(public)\n",
    "\n",
    "# verify the signature validates when the digest is used directly\n",
    "assert direct_verify(public, digest, r, s)\n",
    "print(\"no problem!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Knowledge of k for a given signature leaks the private key\n",
    "\n",
    "If the random `k` value used during signature generation is ever known, an attacker with that value can recover the private key used to sign that message."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "no problem!\n"
     ]
    }
   ],
   "source": [
    "def recover_private_scalar(message, r, s, k, hasher=sha256_hasher):\n",
    "    h = Fq(hasher(message))\n",
    "    k = Fq(k)\n",
    "    return (s*k - h) / r\n",
    "\n",
    "# generate a keypair\n",
    "private, public = generate_keypair()\n",
    "\n",
    "message = \"i used a bad k!\"\n",
    "# fix a k value\n",
    "fixed_k = 1337\n",
    "\n",
    "# generate a signature with known k value\n",
    "r, s = sign(private, message, k=fixed_k)\n",
    "\n",
    "# confirm the signature is valid\n",
    "assert verify(public, message, r, s), \"Signature was invalid!\"\n",
    "\n",
    "# recover private scalar given known k\n",
    "recovered_private = recover_private_scalar(message, r, s, fixed_k)\n",
    "assert recovered_private == private, \"Recovered private scalar was wrong\"\n",
    "\n",
    "print(\"no problem!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Repeating k values for two distinct messages leaks the private key\n",
    "\n",
    "If a signer repeats a `k` value for two distinct messages `k` can be recovered. This, as was just shown, leaks the private key."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "no problem!\n"
     ]
    }
   ],
   "source": [
    "def recover_private_scalar_from_repeated_k(m1, r1, s1, m2, r2, s2, hasher=sha256_hasher):\n",
    "    \"\"\"Recovers the private scalar given two signatures over distinct \n",
    "    messages with repeating k values.\n",
    "    \"\"\"\n",
    "    # Note that a repeat k value can be detected by colliding r values\n",
    "    assert r1 == r2\n",
    "    h1 = Fq(hasher(m1))\n",
    "    h2 = Fq(hasher(m2))\n",
    "    # recover k\n",
    "    k = (h1 - h2) / (s1 - s2)\n",
    "    # recover private key from k\n",
    "    return recover_private_scalar(m1, r1, s1, k, hasher=hasher)\n",
    "\n",
    "# generate a keypair\n",
    "private, public = generate_keypair()\n",
    "\n",
    "# generate two messages and a fixed nonce\n",
    "m1 = \"message one with k\"\n",
    "m2 = \"message two with k\"\n",
    "fixed_k = 0xcafe\n",
    "\n",
    "# generate signatures with fixed k value\n",
    "r1, s1 = sign(private, m1, k=fixed_k)\n",
    "r2, s2 = sign(private, m2, k=fixed_k)\n",
    "\n",
    "# confirm the signatures are valid\n",
    "assert verify(public, m1, r1, s1), \"Signature one was invalid!\"\n",
    "assert verify(public, m2, r2, s2), \"Signature two was invalid!\"\n",
    "\n",
    "# recover private scalar given known k\n",
    "recovered_private = recover_private_scalar_from_repeated_k(m1, r1, s1, m2, r2, s2)\n",
    "assert recovered_private == private, \"Recovered private scalar was wrong\"\n",
    "\n",
    "print(\"no problem!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## More?\n",
    "\n",
    "There are some other fun ECDSA properties worth exploring but they are probably best covered in their own notebook.\n",
    "\n",
    "* Duplicate signature key selection from Koblitz's and Menezes' [\"Another Look at Security Definitions\"](https://eprint.iacr.org/2011/343.pdf)\n",
    "\n",
    "* Private key recovery against a signer using biased `k` values as described in Nguyen's [\"The insecurity of the elliptic curve digital signature algorithm with partially known nonces\"](https://dl.acm.org/citation.cfm?id=937385)\n",
    "\n",
    "Both of these are covered in [Set 8 of Cryptopals](https://cryptopals.com/sets/8)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 8.1",
   "language": "",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}