{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exercise 2: CTF\n",
    "\n",
    "<div class=\"alert alert-warning\">\n",
    "<b>CTF Flags: </b>UUlm Capture the Flag Dashboard<br />\n",
    "<p><a href=\"https://blocksec.pythonanywhere.com\">Blocksec CTF</a></p>\n",
    "</div>\n",
    "\n",
    "Containing 3 Challenges\n",
    "\n",
    "\n",
    "## Requirements\n",
    "**Prog. Lang.:**\n",
    "* Python 3\n",
    "\n",
    "**Python libraries:**\n",
    "* blockcypher\n",
    "* binascii\n",
    "* mnemonic\n",
    "* bip-utils\n",
    "* hashlib\n",
    "* ecdsa\n",
    "\n",
    "**Tools:**\n",
    "* A web browser\n",
    "* IDE that supports Jupyter Notebooks (e.g. VSCode)\n",
    "* https://live.blockcypher.com (block explorer)\n",
    "* https://iancoleman.io/bip39/ (mnemonic code converter)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### CTF 1. Unlocking a bitcoin transaction — 100\n",
    "\n",
    "We are given the Bitcoin testnet transaction hash:\n",
    "[23c9470a2269cf6430569afdd3e2e8f35f633b6cdbc34107ddbab932c4146ba3](https://blockstream.info/testnet/tx/23c9470a2269cf6430569afdd3e2e8f35f633b6cdbc34107ddbab932c4146ba3)\n",
    "* Goal: We want to know **how to spent this tBTC output**.\n",
    "* Hint: The unlocking script (scriptSig) can be find in 8 Byte of HEX and can be converted to Cleartext ASCII.\n",
    "\n",
    "Hints:\n",
    "1. Find the SCRIPTPUBKEY that locks the output value\n",
    "2. Understand how the input must look like, to unlock this locking script.\n",
    "3. Find a way and search for hints to unlock the transaction with the (scriptSig)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "helloworld\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "Helpful functions for the challenge.\n",
    "# Alternative https://www.rapidtables.com/convert/number/hex-to-ascii.html\n",
    "\"\"\"\n",
    "import binascii\n",
    "\n",
    "hex_string = \"68656C6C6F776F726C64\"\n",
    "decoded_string = binascii.unhexlify(hex_string).decode('utf-8')\n",
    "print(decoded_string)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### CTF 2. Dark Net Money — 200\n",
    "\n",
    "You are given the following mnemonic phrase:\n",
    "```\n",
    "play fever bullet unlock error palm insect pottery tower torch memory liquid\n",
    "```\n",
    "\n",
    "Your task is to find how much tBTC this wallet holds unspent.\n",
    "\n",
    "**Hint**: The correct derivation path follows the classic BIP44 scheme. You need to find the receiving address of the first account at a specific index.\n",
    "\n",
    "Use the mnemonic phrase on a well-known BIP39 tool.\n",
    "\n",
    "This could be helpful:\n",
    "1. You need to select Bitcoin Testnet as the coin type.\n",
    "2. The derivation path is m/44'/1'/0'/0/137. [Documentation](https://learnmeabitcoin.com/technical/keys/hd-wallets/derivation-paths/#:~:text=A%20derivation%20path%20provides%20the,more%20children%2C%20and%20so%20on.).\n",
    "\n",
    "\n",
    "For the developers:\n",
    "\n",
    "```python\n",
    "from mnemonic import Mnemonic\n",
    "from bip_utils import Bip39SeedGenerator, Bip44, Bip44Coins, Bip44Changes\n",
    "````\n",
    "\n",
    "Alternatively for the tool users:\n",
    "* [Mnemonic Code Converter](https://iancoleman.io/bip39/).\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### CTF 3. ECDSA Nonce Reuse - 200\n",
    "\n",
    "In this challenge, you are given two ECDSA signatures that have reused the same nonce. Your task is to recover the private key used to generate these signatures. This is a classic cryptographic vulnerability that occurs when the same nonce is used in multiple ECDSA signatures.\n",
    "\n",
    "```\n",
    "r: 0x5d66e837a35ddc34be6fb126a3ec37153ff4767ff63cbfbbb32c04a795680491\n",
    "```\n",
    "```\n",
    "s1: 0x1a53499a4aafb33d59ed9a4c5fcc92c5850dcb23d208de40a909357f6fa2c12c\n",
    "```\n",
    "```\n",
    "message1: \"what up defcon\"\n",
    "```\n",
    "```\n",
    "s2: 0xd67006bc8b7375e236e11154d576eed0fc8539c3bba566f696e9a5340bb92bee\n",
    "```\n",
    "```\n",
    "message2: \"uh oh this isn't good\"\n",
    "```\n",
    "```\n",
    "n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141\n",
    "```\n",
    "\n",
    "\n",
    "* s1 and s2 are the signature parameters.\n",
    "* h1 and h2 are the message digests.\n",
    "* r is the same nonce for both signatures due to nonce reuse.\n",
    "* n is the order of the elliptic curve group.\n",
    "\n",
    "Task: \n",
    "* Use the Python script for performing a ECDSA Nonce Reuse and recover the private key using the provided information and hints.\n",
    "\n",
    "Once the private key is recovered, we as a attacker can use it to sign new transactions, effectively allowing them to transfer Bitcoin from the compromised wallet to our own addresses. This can lead to unauthorized spending of the victim's Bitcoin.\n",
    "\n",
    "Hint:\n",
    "* $ d_A = \\left( \\frac{s_2 \\cdot h_1 - s_1 \\cdot h_2}{r \\cdot (s_1 - s_2)} \\right) \\mod n $. With this equation an attacker can obtain two different ECDSA signatures that reused the same nonce, they can use this equation to recover the private key $ d_A $. This allows the attacker to potentially forge signatures or decrypt messages that were intended to be secure."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The original equation is:\n",
    "\n",
    "$$\n",
    "d_A = \\left( \\frac{s_2 \\cdot h_1 - s_1 \\cdot h_2}{r \\cdot (s_1 - s_2)} \\right) \\mod n\n",
    "$$\n",
    "\n",
    "\n",
    "To express the denominator of the fraction as an inverse modulo equation, we need to find the modular inverse of $ (s_1 - s_2) \\pmod{n} $. The modular inverse of $ (s_1 - s_2) $ is a value $ k $ such that:\n",
    "\n",
    "$$\n",
    "k \\cdot (s_1 - s_2) \\equiv 1 \\pmod{n}\n",
    "$$\n",
    "\n",
    "\n",
    "This can be written as:\n",
    "\n",
    "$$\n",
    "k = (s_1 - s_2)^{-1} \\pmod{n}\n",
    "$$\n",
    "\n",
    "\n",
    "So, the original equation can be rewritten using the modular inverse as:\n",
    "\n",
    "$$\n",
    "d_A = \\left( (s_2 \\cdot h_1 - s_1 \\cdot h_2) \\cdot (r \\cdot (s_1 - s_2))^{-1} \\right) \\mod n\n",
    "$$\n",
    "\n",
    "\n",
    "Where:\n",
    "\n",
    "$$\n",
    "(r \\cdot (s_1 - s_2))^{-1} \\pmod{n}\n",
    "$$\n",
    "\n",
    "\n",
    "is the modular inverse of $ ( r \\cdot (s_1 - s_2) ) \\pmod{n} $."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from hashlib import sha256\n",
    "from ecdsa import SECP256k1, SigningKey\n",
    "from ecdsa.util import sigdecode_string\n",
    "from ecdsa.numbertheory import inverse_mod\n",
    "\n",
    "def hash_message(message):\n",
    "    \"\"\"Hash the message using SHA-256.\"\"\"\n",
    "    message = 0\n",
    "\n",
    "    assert len(\"{0:b}\".format(message)) == 255, f\"Expected binary length of 255, but got {len(\"{0:b}\".format(message))}\" # Helpful assertion\n",
    "    return None\n",
    "\n",
    "def recover_private_key(h1, h2, s1, s2, r1, r2, n):\n",
    "    \"\"\"Recover the private key via nonce reuse.\n",
    "\n",
    "    Recover the private key from two different signatures\n",
    "    that use the same random nonce `k` during signature\n",
    "    generation. Note that if the same `k` is used in two\n",
    "    signatures, this implies that the secp256k1 32-byte\n",
    "    signature parameter `r` is identical.\n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "        h1: int\n",
    "            The 32-byte message digest of the message `m1`.\n",
    "        h2: int\n",
    "            The 32-byte message digest of the message `m2`.\n",
    "        s1: int\n",
    "            The secp256k1 32-byte signature parameter `s1`.\n",
    "        s2: int\n",
    "            The secp256k1 32-byte signature parameter `s2`.\n",
    "        r1: int\n",
    "            The secp256k1 32-byte signature parameter `r1`.\n",
    "        r2: int\n",
    "            The secp256k1 32-byte signature parameter `r2`.\n",
    "        n:  int\n",
    "            The 32-byte integer order of G (part of the public key).\n",
    "\n",
    "    Returns\n",
    "    -------\n",
    "        pk: int\n",
    "            Return a 32-byte private key.\n",
    "\n",
    "    \"\"\"\n",
    "    assert r1 == r2, \"No ECDSA nonce reuse detected.\"\n",
    "    return None\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    # Provided values\n",
    "    r = 0x5d66e837a35ddc34be6fb126a3ec37153ff4767ff63cbfbbb32c04a795680491\n",
    "    signature1 = 0x1a53499a4aafb33d59ed9a4c5fcc92c5850dcb23d208de40a909357f6fa2c12c\n",
    "    signature2 = 0xd67006bc8b7375e236e11154d576eed0fc8539c3bba566f696e9a5340bb92bee\n",
    "    n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141\n",
    "\n",
    "    # Messages\n",
    "    message1 = \"what up defcon\"\n",
    "    message2 = \"uh oh this isn't good\"\n",
    "\n",
    "    # Step 1: Hash the messages\n",
    "    z1 = hash_message(message1)\n",
    "    z2 = hash_message(message2)\n",
    "\n",
    "    # Step 2: Solve for the private key\n",
    "    recovered_private_key = recover_private_key(z1, z2, signature1, signature2, r, r, n)\n",
    "\n",
    "    print(f\"Recovered private key: {recovered_private_key}\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "venv",
   "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.12.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}