Skip to content

Instantly share code, notes, and snippets.

@nuvious

nuvious/HTB-TwoForOne-Walkthrough.ipynb

Last active February 11, 2024 08:11
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save nuvious/71e621075f6c4ef3ba0bb4380306fce9 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save nuvious/71e621075f6c4ef3ba0bb4380306fce9 to your computer and use it in GitHub Desktop.
Download ZIP
Display the source blob
Display the rendered blob
Raw
HTB-TwoForOne-Walkthrough.ipynb
{
"cells": [
{
"cell_type": "markdown",
"id": "1b29b806-25fc-465e-91c8-38897f21bc6a",
"metadata": {},
"source": [
"# HTB TwoForOne Walkthrough\n",
"\n",
"This is a walkthrough for the [TwoForOne](https://app.hackthebox.com/challenges/190) challenge on [Hack the Box](https://app.hackthebox.com/)\n",
"\n",
"## Analysis\n",
"\n",
"In this challenge we're initially provided 2 keys and 2 encrypted messages. Additionally the description of the challenge gives us a hint:\n",
"\n",
"> Alice sent two times the same message to Bob.\n",
"\n",
"There are a number of potential attack vectors but let's just get our baseline first by reading in the keys:"
]
},
{
"cell_type": "code",
"execution_count": 1,
"id": "b723f8d2-ca87-4204-a287-b1fa70aa1cf9",
"metadata": {
"tags": []
},
"outputs": [
{
"data": {
"text/plain": [
"RsaKey(n=25080356853331150673712092961488349508728123694382279186941974911344272809718201683391687288116618021523872262260746884803456249468108932413753368793568123710905490623939699616018064364038794824072468125668702688048418916712950393799664781694224559810656290997284081084848717062228887604668548576609649709572412523306016494962925450783098637867249337121156908328927249731928363360657779226929980928871118145919627109584218577535657544952661333527174942990937484743860494188129607347202336812042045820577108243818426559386634634103676467773122325120858908782192357380855678371737765634819794619802582481594876770433687, e=65537)"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"RsaKey(n=25080356853331150673712092961488349508728123694382279186941974911344272809718201683391687288116618021523872262260746884803456249468108932413753368793568123710905490623939699616018064364038794824072468125668702688048418916712950393799664781694224559810656290997284081084848717062228887604668548576609649709572412523306016494962925450783098637867249337121156908328927249731928363360657779226929980928871118145919627109584218577535657544952661333527174942990937484743860494188129607347202336812042045820577108243818426559386634634103676467773122325120858908782192357380855678371737765634819794619802582481594876770433687, e=343223)"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Two keys N's match: True\n",
"Two keys e's match: False\n"
]
}
],
"source": [
"from Crypto.PublicKey import RSA\n",
"\n",
"key1 = RSA.import_key(open('key1.pem', 'r').read())\n",
"key2 = RSA.import_key(open('key2.pem', 'r').read())\n",
"\n",
"display(key1)\n",
"display(key2)\n",
"print(f\"Two keys N's match: {key1.n == key2.n}\")\n",
"print(f\"Two keys e's match: {key1.e == key2.e}\")"
]
},
{
"cell_type": "markdown",
"id": "26a59292-0871-4c5b-85bf-bbc8e8907845",
"metadata": {},
"source": [
"## Attack Vector\n",
"\n",
"We now have 2 messages that have the same modulus and different public exponents. This seems like a good candidate for the [Common Modulus Attack](https://thescipub.com/pdf/jcssp.2006.665.671.pdf):\n",
"\n",
"> A Common Modulus attack can be used to recover\n",
"> the plaintext when the same message is encrypted to\n",
"> two RSA keys that use the same modulus. This\n",
"> algorithm works if and only if message sends with the\n",
"> same modulus and relatively prime encryption\n",
"> exponents. The main task of Common Modulus attack\n",
"> algorithm is computing a and b such that e1*a+e2*b=1,\n",
"> this process needs O((log k)2), where k is maximum\n",
"> size of a or b.\n",
"\n",
"The important bit is the public exponents are relative primes, so let's check that."
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "7a013c1a-50bb-44a0-a7e2-eb6c5b8cbe0c",
"metadata": {
"tags": []
},
"outputs": [
{
"data": {
"text/plain": [
"(mpz(1), mpz(133132), mpz(-25421))"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"import gmpy2\n",
"\n",
"g, a, b = gmpy2.gcdext(key1.e, key2.e)\n",
"assert g == 1\n",
"display((g,a,b))"
]
},
{
"cell_type": "markdown",
"id": "bdb3585f-5fa7-47e6-b444-88ada61ec73c",
"metadata": {},
"source": [
"## Decrypting the Message\n",
"\n",
"With relative primality of the public exponents confirmed we can move onto the decryption itself. Per the above linked reference we simply need to do the following:\n",
"\n",
"> Algorithm: Find a, b such that: e1 * a+e2 * b=1, using Extended Euclidean Algorithm.\n",
"> Computes original message m = c1^a * c2^b mod N."
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "b3c44a23-0314-4e11-9ebe-3816b0ed9019",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"def common_modulus_attack(ct1, ct2, e1, e2, N):\n",
" # Find a/b to satisfy e1 * a+e2 * b=1\n",
" g, a, b = gmpy2.gcdext(key1.e, key2.e)\n",
" assert g == 1\n",
" \n",
" # If either component of the extended Euclidean is negative, we need to invert the ct value\n",
" ct1v = gmpy2.invert(ct1, N) if a < 0 else ct1\n",
" ct2v = gmpy2.invert(ct2, N) if b < 0 else ct2\n",
" # Then ensure a/b are positive for the final step\n",
" a = abs(a)\n",
" b = abs(b)\n",
" # Multiply \n",
" m = gmpy2.powmod(ct1v, a, N) * gmpy2.powmod(ct2v, b, N) % N\n",
" return int(m)"
]
},
{
"cell_type": "code",
"execution_count": 7,
"id": "2c34c51e-751c-4a91-a432-358002fbb63e",
"metadata": {
"tags": []
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": []
},
{
"data": {
"text/plain": [
"'HTB{I_REMOVED_THE_REAL_FLAG_FOR_PUBLISHING}'"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"from Crypto.Util.number import long_to_bytes, bytes_to_long\n",
"from base64 import b64decode\n",
"\n",
"ct1 = bytes_to_long(\n",
" b64decode(\n",
" open('message1', 'r').read()\n",
" )\n",
")\n",
"ct2 = bytes_to_long(\n",
" b64decode(\n",
" open('message2', 'r').read()\n",
" )\n",
")\n",
"\n",
"long_to_bytes(common_modulus_attack(ct1, ct2, key1.e, key2.e, key1.n)).decode()"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"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.10.9"
}
},
"nbformat": 4,
"nbformat_minor": 5
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment