436 lines
18 KiB
Plaintext
436 lines
18 KiB
Plaintext
{
|
||
"cells": [
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "04af88ae-4585-44f4-8a6b-e54ef1b369fc",
|
||
"metadata": {},
|
||
"source": [
|
||
"Ondřej Hladůvka"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "81c9f10b-5df5-4187-9be5-913c536fdb27",
|
||
"metadata": {},
|
||
"source": [
|
||
"# Task 1\n",
|
||
"You are working in the company that uses RSA cryptosystem in their solutions.\n",
|
||
"You have been sent the following abstract for the scientific paper. Based on this, would your recommendation to your company and why? \n",
|
||
"<img src=\"Screenshot_11-Apr_12-46-16_5589.png\" width=\"400\" height=\"200\">"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "19cec4fd-90ac-4255-9add-9a48879f5b89",
|
||
"metadata": {},
|
||
"source": [
|
||
"RSA key generation: \n",
|
||
"let $p,q$ be large primes \n",
|
||
"$n := p \\times q$ \n",
|
||
"let $e$ be integer $1 < e < \\text{Lcm}(\\varphi(p, q))$ \n",
|
||
"$d := e^{-1} \\pmod{\\varphi(n)}$ \n",
|
||
"\n",
|
||
"Private key := $(d, n)$ \n",
|
||
"Public key := $(e, n)$ \n",
|
||
"\n",
|
||
"------------------------------------\n",
|
||
"\n",
|
||
"It is correct that $\\varphi(n)$ for public $n$ is used to generate $d$ (using EEA), so attacker able to compute it could break an encryption.\n",
|
||
"\n",
|
||
"Another thing that attacker could do knowing $n$ and $\\varphi(n)$ is to compute primes $p, q$:\n",
|
||
"$$\n",
|
||
"\\varphi(n) = \\varphi(p \\times q) = (p-1)(q-1) = p \\times q - p - q + 1 = (n+1)-(p+q)\n",
|
||
"$$\n",
|
||
"$$\n",
|
||
"\\Rightarrow p+q = (n+1)-\\varphi(n)\n",
|
||
"\\,\\,\\,\\,\\, \\land \\,\\,\\,\\,\\,\n",
|
||
"p \\times q = n\n",
|
||
"$$\n",
|
||
"$$\n",
|
||
"\\Rightarrow p+q -(n+1)+\\varphi(n) = 0\n",
|
||
"\\,\\,\\,\\,\\, \\land \\,\\,\\,\\,\\,\n",
|
||
"p \\times q - n = 0\n",
|
||
"$$\n",
|
||
"this forms system of equations, \n",
|
||
"lets substitute $p := (n+1)-\\varphi(n) - q$:\n",
|
||
"$$\n",
|
||
"((n+1)-\\varphi(n) - q) \\times q - n = 0\n",
|
||
"$$\n",
|
||
"Solving for $q$:\n",
|
||
"$$\n",
|
||
"q = \\frac{n}{(n+1)-\\varphi(n)-q}\n",
|
||
"$$\n",
|
||
"$$\n",
|
||
"p = \\frac{n}{q} \\text{ (where } p \\text{ and } q \\text{ can be swapped)}\n",
|
||
"$$\n",
|
||
"\n",
|
||
"This proves that factorization of $n$ is trivial when $\\varphi(n)$ is known, thus computing $\\varphi(n)$ has to be at least as difficult as computing factorization of $n$\n",
|
||
"\n",
|
||
"And when we know primes $p$ and $q$, computing $\\varphi(n)$ is just $(p-1)(q-1)$ $\\Rightarrow$ computing $\\varphi(n)$ is as difficult as computing factorization of $n$ \n",
|
||
" \n",
|
||
"#### I would not make any change based on this arcicle, as RSA is based on diffclty of computing $\\varphi(n)$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "5748beac-4e59-4211-aa41-8175b332bef4",
|
||
"metadata": {},
|
||
"source": [
|
||
"# Task 2\n",
|
||
"Suppose you are given the following encryption scheme: \n",
|
||
"$KeyGen()∶$\n",
|
||
"1. Sample large prime number $p$\n",
|
||
"2. Compute modulus as $n := p^2$\n",
|
||
"3. Select $e$ to be integer such that \n",
|
||
"$Gcd(\\varphi(n), e) = 1 \n",
|
||
"\\,\\,\\,\\,\\, \\land \\,\\,\\,\\,\\,\n",
|
||
"2 < e < \\varphi(n)$\n",
|
||
"4. Calculate $d$ such that $e \\times d ≡ 1 \\, mod \\, \\varphi(n)$\n",
|
||
"5. Return private key $Sk := (d, n)$ and \n",
|
||
" public key $Pk = (e, n)$ \n",
|
||
"\n",
|
||
"$Enc(Pk, Pt)∶$\n",
|
||
"1. Compute ciphertext as $Ct = Pt^e \\, (mod \\,\\, n)$\n",
|
||
" \n",
|
||
"$Dec(Sk, Ct)∶$\n",
|
||
"1. Compute decryption as $Pt = Ct^d \\, (mod \\,\\, n)$\n",
|
||
"\n",
|
||
"provide an attack that shows that given encryption scheme is not secure with respect to the\n",
|
||
"IND-OT-CPA security definition."
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "3029803a-82e5-45a9-b5c9-a6373af60ee7",
|
||
"metadata": {},
|
||
"source": [
|
||
"#### Indistinguishability under One-Time Chosen Plaintext Attack:\n",
|
||
"1. Challenger generates a key $k$\n",
|
||
"1. Adversary submits two equal-length messages $m_0, m_1$\n",
|
||
"1. Challenger flips a random bit $b \\gets \\{0,1\\}$ and returns $Enc(k, m_b)$\n",
|
||
"1. Adversary guesses $b$ \n",
|
||
"The scheme is IND-OT-CPA secure if this advantage is negligible for all adversaries \n",
|
||
"-------------------------------------------\n",
|
||
"Knowing $n$ is square, adversary can calculate \n",
|
||
"$$\n",
|
||
"\\varphi(n) = n^2 - n\n",
|
||
"$$\n",
|
||
"there are $p^2$ total integers from $1$ to $p^2$ \n",
|
||
"out of these, the numbers that are not relatively prime to $p^2$ are the multiples of $p, 2p, 3p ... p^2$\n",
|
||
"and there are exactly $p$ such multiples. \n",
|
||
"\n",
|
||
"With $\\varphi(n)$ obtained, adversary can compute $d \\equiv e^{-1} (mod \\,\\, \\varphi(n))$ the same way challanger did. \n",
|
||
" \n",
|
||
"#### Attack\n",
|
||
"Adversary's strategy:\n",
|
||
"1. Adversary will sens two distinct messages $m_0, m_1$ and recieves compute $Ct$ and $Pk = (e, n)$\n",
|
||
"2. Computes $\\varphi(n) = n^2 - n$\n",
|
||
"3. Computes $d = e^{-1} \\, (mod \\,\\, \\varphi(n))$\n",
|
||
"4. Decrypts $Pt = Ct^d \\, (mod \\,\\, n)$\n",
|
||
"5. Comares $Pt$ against $m_0, m_1$ and select which plaintext was encrypted\n",
|
||
"\n",
|
||
"##### Adversary will win every time => scheme is not IND-OT-CPA secure"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "b911e6e5-1a14-47d4-8322-4ee26318db8e",
|
||
"metadata": {},
|
||
"source": [
|
||
"# Task 3\n",
|
||
"#### Consider the ElGamal cryptosystem with a public key $h$ and a private key $x$ \n",
|
||
"\n",
|
||
"let cyclic group $G$ of order $q$, with generator $g$ and identity element $e$. And all operation on this group... \n",
|
||
"let message $m \\in G$ \n",
|
||
"public key $h := g^x$ \n",
|
||
"shared secret $s := h^y = (g^x)^y = g^{x \\times y}$ \n",
|
||
"$c_1 := g^y$ \n",
|
||
"$c_2 := m \\times s$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "f9d7ddb7-045e-434a-8af3-d3291a57e08c",
|
||
"metadata": {},
|
||
"source": [
|
||
"1. Assume that you are given a ciphertext $(c_1, c_2)$ encrypting an unknown message $m$. Show how you can generate a new ciphertext $(c_1', c_2')$ that encrypts the same $m$, but with different randomness $y'$ (without decrypting the ciphertext)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "d3202508-ecae-4fa8-af4f-b09b842f2bd3",
|
||
"metadata": {},
|
||
"source": [
|
||
"ElGamal decryption principle:\n",
|
||
"$$\n",
|
||
"s \\times c_1^{q-x} = g^{x \\times y} \\times {(g^y)}^{q-x} = g^{x \\times y} \\times g^{y(q-x)} = g^{x \\times y + y \\times q - x \\times y} = g^{y \\times q} = {(g^q)}^y = e^y = e\n",
|
||
"$$\n",
|
||
"$$\n",
|
||
"\\Rightarrow s^{-1} = c_1^{q-x}\n",
|
||
"$$\n",
|
||
"$$\n",
|
||
"m = c_2 \\times s^{-1} = m \\times s \\times s^{-1}\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "dc716837-53fb-4f8c-92d5-38ccdb49d317",
|
||
"metadata": {},
|
||
"source": [
|
||
"to get the same message from different ct\n",
|
||
"$$\n",
|
||
"m = c_2{'} \\times s^{-1}{'} = c_2{'} \\times ({c_1'})^{q-x}\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "28980583-2777-4a56-a4f4-9c251070eb80",
|
||
"metadata": {},
|
||
"source": [
|
||
"we can modify messages with any pair $k, l$ \n",
|
||
"$c_1{'} := c_1 \\times k$ \n",
|
||
"$c_2{'} := c_2 \\times l$\n",
|
||
"$$\n",
|
||
"m = c_2{'} \\times {(c_1{'})}^{q-x} = c_2 \\times l \\times {(c_1 \\times k)}^{q-x} = c_2 \\times l \\times {c_1}^{q-x} \\times {k}^{q-x}\n",
|
||
"$$\n",
|
||
"with relation $l \\times {k}^{q-x} = e$, but we dont know private exponent $x$\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "c38e621f-392c-4b20-8102-8952c7fb2fc3",
|
||
"metadata": {},
|
||
"source": [
|
||
"this can be achived with $k := g^z$ for any choosen $z \\in G$\n",
|
||
"$$\n",
|
||
"c_1{'} = c_1 \\times g^z = g^y \\times g^z = g^{y+z}\n",
|
||
"$$ \n",
|
||
"$$\n",
|
||
"s{'} = c_1^{x} = {g}^{x(y+z)} = {g}^{xy+xz}\n",
|
||
"$$\n",
|
||
"$$\n",
|
||
"\\frac{c_2{'}}{c_2} = \\frac{m \\times s{'}}{m \\times s} = \\frac{s{'}}{s} = g^{xz} = \\frac{c_2 \\times l}{c_2} = l\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "71d98453-5695-4942-bee9-8441e95051b0",
|
||
"metadata": {},
|
||
"source": [
|
||
"2. Assume you are given ciphertext $c = (c1, c2)$ that you wants to decrypt, but you do not know corresponding private key $sk$. Suppose that you have a friend who provides you with the decryption of any other chosen ciphertext $c{'} \\not= c$ using private key $sk$. Show how can you decrypt $c$."
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "67b945b1-553a-405a-8daa-e797a3f9616f",
|
||
"metadata": {},
|
||
"source": [
|
||
"We can choose any $c'$ to decipher $m$\n",
|
||
"$$\n",
|
||
"\\frac{c_2}{c_2{'}} = \\frac{m \\times s}{m{'} \\times s} = \\frac{m}{m{'}}\n",
|
||
"$$\n",
|
||
"$$\n",
|
||
"\\Rightarrow m = m{'} \\times \\frac{c_2}{c_2{'}}\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "cd4f9b24-52d6-407d-a9e2-769b6dba6a54",
|
||
"metadata": {},
|
||
"source": [
|
||
"3. Assume you are given two ciphertexts $ct_1 = (c_{11}, c_{12})$ and $ct_2 = (c_{21}, c_{22})$ that correspond to some\n",
|
||
"plaintext messages (not known to you) $m_1$ and $m_2$. What information can you learn about $m_1$ and $m_2$, if you observe that $c_{11} = c_{21}$?"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "b95d2854-1d8c-40f8-a69e-eb35f5d19ee8",
|
||
"metadata": {},
|
||
"source": [
|
||
"$$\n",
|
||
"1 = \\frac{c_{11}}{c_{12}} = \\frac{g^{y_1}}{g^{y_2}} = g^{y_1 - y_2}\n",
|
||
"$$\n",
|
||
"$$\n",
|
||
"\\Rightarrow y_1 = y_2\n",
|
||
"$$\n",
|
||
"$$\n",
|
||
"\\Rightarrow h^{y_1} = h^{y_2}\n",
|
||
"$$\n",
|
||
"$$\n",
|
||
"\\frac{c_{12}}{c_{22}} = \\frac{m_1 \\times h^{y_1}}{m_2 \\times h^{y_2}} = \\frac{m_1}{m_2}\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "44a536aa-8f2a-4234-a88e-ae020f560d94",
|
||
"metadata": {},
|
||
"source": [
|
||
"4. Bring an example of potential application of ElGamal encryption scheme, where homomorphic property is useful and another example, where it violates the desired security of the application. Justify your answer."
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "1a8ce5ba-477e-4be8-b6f1-697da610487a",
|
||
"metadata": {},
|
||
"source": [
|
||
"- Desired application could multiply messages from multiple senders and decrypt result to protect privacy of them but get the product of all \n",
|
||
"- Undesired applicatio would be for example online auction where adversary could manipulate offers"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "a2238cd4-1944-4139-909c-ae984776d407",
|
||
"metadata": {},
|
||
"source": [
|
||
"# Task 4\n",
|
||
"You have intercepted two RSA ciphertexts $c_1 = 7$ and $c_2 = 16$ that correspond to the same plaintext – a promo code for the video game. You know that those ciphertexts have been created using corresponding public keys $pk_1 = (e = 3, n = 57)$ and $pk_2 = (e = 5, n = 57)$. What is the promo code m from the intercepted ciphertext? \n",
|
||
"Note: for this attack, your task is not to find the private key!"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "a8d3026a-1b29-4339-9548-d889871ad68e",
|
||
"metadata": {},
|
||
"source": [
|
||
"${\\lvert m^{3} \\rvert}_{57} \\equiv 7$ \n",
|
||
"${\\lvert m^{5} \\rvert}_{57} \\equiv 16$ "
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "e8358104-d161-4617-9f36-761e80cf6d63",
|
||
"metadata": {},
|
||
"source": [
|
||
"${\\lvert m^{3} \\rvert}_{57} \\equiv 16$ \n",
|
||
"${\\lvert 7 \\times m^{2} \\rvert}_{57} \\equiv 16$ \n",
|
||
"${\\lvert 7^{-1} \\times 7 \\times m^{2} \\rvert}_{57} \\equiv 16 \\times 7^{-1}$ \n",
|
||
"${\\lvert m^{2} \\rvert}_{57} \\equiv 43$ \n",
|
||
"${\\lvert \\sqrt{m} \\rvert}_{57} \\equiv \\{10, 28, 29, 47\\}$ "
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "82b4dbb3-218a-47a2-a623-8961451298cd",
|
||
"metadata": {},
|
||
"source": [
|
||
"${\\lvert {28}^{3} \\rvert}_{57} \\equiv 7$ \n",
|
||
"${\\lvert {28}^{5} \\rvert}_{57} \\equiv 16$ \n",
|
||
"$ m = 28$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "682d50fa-6ab4-4f8e-9c25-d11fea9f2b74",
|
||
"metadata": {},
|
||
"source": [
|
||
"# Task 5\n",
|
||
"Your company is building a product that heavily relies on\n",
|
||
"usage of cryptography. You receive the following list of security requirements for the system"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "6fd52e32-8336-45a9-8f2b-ea7f741603e2",
|
||
"metadata": {},
|
||
"source": [
|
||
"1. System should ensure data confidentiality and integrity in transmission \n",
|
||
"**Scheme: TLS 1.3 with AES-256-GCM or ChaCha20-Poly1305 256-bit** \n",
|
||
" $\\to$ Both provide confidentiality and integrity in single pass \n",
|
||
" $\\to$ ChaCha20 is efficient in software and resistant to timing attacks \n",
|
||
" $\\to$ AES-256 ia accelerated on almost every CPU, AES-NI instructions mitigate side-channel risks \n",
|
||
" $\\to$ TLS 1.3 removes deprecated ciphers (RC4 etc..), but may not be supported on older platforms (typically embedded devices) \n",
|
||
" using TLS 1.2 and whitelisting only secure ciphers may be option too\n",
|
||
" \n",
|
||
"3. System should ensure data confidentiality and integrity at rest \n",
|
||
"**Scheme: AES-256-XTS with HMAC-SHA-256** \n",
|
||
" $\\to$ AES-256 is resistant to brute-force attacks (even with quantum computing, Grover's algorithm would require ~$2^128$ operations) \n",
|
||
" $\\to$ XTS Encrypts each sector independently to avoids performance penalties for random I/O operations, but keeps diffusion advantage of chaining modes \n",
|
||
" $\\to$ HMAC-SHA-256 ensures integrity and can be backupped separately to ensure backup wasnt tampered with\n",
|
||
" \n",
|
||
"3. System should enforce strong authentication mechanisms for users and services to ensure that only authorized entities can access the data \n",
|
||
"**Scheme for user authentication: pow password hashing + Ed25519** \n",
|
||
" $\\to$ Argon2id is designed to not be comutable on FPGA and can be configured (iterations, memory, parallelism) to match requrements\n",
|
||
" $\\to$ Passwords should be salted before hashing and never stored as plaintext \n",
|
||
" $\\to$ Ed25519 signature can be stored on hardware authenticator providing second factor to the password \n",
|
||
" **Scheme for service to service authentication: mTLS Ed25519 256bit** \n",
|
||
" $\\to$ Mutual certificate based authentication for every two points in infrastructure \n",
|
||
" $\\to$ Ed25519 with 256-bit key comparable secure as RSA with 3072-bit key, but much cheaper to compute - saving cost on the infrastrucure \n",
|
||
"4. System must be resistant to common attacks, including side-channel attacks and brute force attacks, using strong cryptographic primitives and practices \n",
|
||
"**Mitigation of common attacks:** \n",
|
||
" $\\to$ AES-NI instructions to resis power analysis with 256-bit key to resis brute force \n",
|
||
" $\\to$ TLS 1.3 insted of 1.2 to not even include insecure schemes in the transport protocol \n",
|
||
" $\\to$ XTS mode and HMAC to mitigate tampering with data at rest\n",
|
||
" $\\to$ Argon2id for password hashing and salting to resist dictionary and bruteforce FPGA attacks in case hashes got leaked \n",
|
||
" $\\to$ Ed25519 to resist simple RSA power analysis "
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "2226a20b-4e40-4f57-881f-9ba9658ce358",
|
||
"metadata": {},
|
||
"source": [
|
||
"## Bonus Task\n",
|
||
"Show that exponential ElGamal (where the ciphertext is constructed as $c = (c_1, c_2) = (g^y, g^m \\times s)$ is not IND-CCA2 secure. You are allowed to make single encryption query and single decryption\n",
|
||
"query to the challenger."
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "cc53f0ce-b56b-4560-ab2a-ead78a0f80a9",
|
||
"metadata": {},
|
||
"source": [
|
||
"#### Indistinguishability under adaptive chosen-ciphertext attack \n",
|
||
"1. The challenger generates a key pair $Pk, Sk$, and publishes $PK$ to the adversary\n",
|
||
"2. The adversary may perform any number of calls to the encryptions and decryption oracle based on arbitrary ciphertexts\n",
|
||
"3. Eventually, the adversary submits two distinct chosen plaintexts $m_0, m_1$ to the challenger.\n",
|
||
"4. The challenger selects a bit $b \\gets \\{0, 1\\}$ uniformly at random, and sends the ciphertext $c = E(Pk, M_b)$ back\n",
|
||
"5. The adversary is free to perform any number of additional computations or encryptions and may make further calls to the decryption oracle\n",
|
||
"7. Adversary guesses $b$\n",
|
||
" \n",
|
||
"A scheme is IND-CCA2–secure secure if this advantage is negligible for all adversaries"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"id": "b89d823e-919a-4426-a860-9474b55918a5",
|
||
"metadata": {},
|
||
"source": [
|
||
"#### Adversary's startegy\n",
|
||
"1. Challenger computes a public key $h := g^x$\n",
|
||
"2. Adversary selects two messages $m_0, m_1$\n",
|
||
"3. Challenger responds with $Ct = (c_0, c_1) = (g^y, g^{m_b} \\times h^y)$\n",
|
||
"4. Adversary chooses $k \\in N$ computes and submits $Ct{'} := (c_0, c_1 \\times g^k)$ for decryption\n",
|
||
"5. Oracle returns $D(Ct{'}) = \\frac{c_1 \\times g^k}{{c_0}^x} = \\frac{g^{m_b} \\times h^y \\times g^k}{g^{y \\times x}} = \\frac {g^{m_b} \\times h^y \\times g^k}{h^y} = g^{m_b + k}$\n",
|
||
"6. Adversary computes $g^{m_0 + k}$ and $g^{m_1 + k}$, compares them to decrypted $Ct{'}$\n",
|
||
"since $m_0, m_1, k$ are known to the Adversary, he will always succeed $\\Rightarrow$ exponential ElGamal is not IND-CCA2 secure"
|
||
]
|
||
}
|
||
],
|
||
"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.11.6"
|
||
}
|
||
},
|
||
"nbformat": 4,
|
||
"nbformat_minor": 5
|
||
}
|