Cryptography concepts summary.
Semantic Security
- Adversary \(A\) computes 2 messages of same length \(m_0\), \(m_1\in M\)
- Challenger \(C\) computes the encryption of one of the message \(e=E(k, M_b)\) with \(b\in\{0,1\}\) randomly and sends the encrypted text
- \(A\) decides which message was encrypted by \(C\) given \(e\)
The advantage of \(C\) winning the game is defined as
\[SSadv[A,\varepsilon]:=|Pr[W_0]-Pr[W_1]|\]A cipher \(\varepsilon\) is semantically secure if for all efficient adversaries \(A\), the value \(SSadv[A,\varepsilon]\) is negligible[1].
Block Cipher
Block ciphers use the same message and cipher space \(X\) and only defines a scheme for translating one block \(m\in X\) to another block \(c\in X\) based on some secret key \(k\in K\) in the key space.
The security of block ciphers depends on the true randomness in translating one block to another. Block ciphers are malleable and needs integrity guarantees. AES block ciphers in counter mode is often used in practice.
Message Authentication Code (MAC)
To prevent attackers from modifying cipher texts, message includes MAC to authenticate the message. Secure MACs need to be unforgeable and, as an intuitive understanding, need to change with the message (ie. Encrypt-then-MAC is better than MAC-then-Encrypt).
Hashing
Hashing functions maps a block of text of length \(L\) into a length \(l\) signature (ie. \(l<L\)). By the Birthday Paradox[3] and Pigeon Hole principle, collisions can be computed by bruteforce. MD5 and SHA1 have efficient collision finders and are insecure.
Diffie-Hellman Key Exchange
Given the group \(\mathbb{Z}_p\) of integers \(\bmod p\) where \(p\) is a prime, pick an element \(g\in(0, p)\). Because \(p\) is a prime, \(\mathbb{Z}_p\) must be a cyclic group. The subgroup \(\mathbb{G}\) generated by \(g\) must also be cyclic and has group order \(q\) (also a prime) that divides \(\vert\mathbb{Z}_p\vert\).
In addition, by Fermat’s Little Theorem \(g^{p-1}\equiv 1\bmod p\). Since \(\mathbb{G}\) is cyclic and elements in \(G\) are closed under multiplication, for any elements \(g^a\in\mathbb{G}\), there is another element \(g^{-a}\in\mathbb{G}\) such that \(g^a\cdot g^{-a}\equiv 1\bmod p\).
The key exchange process is:
- Alice computes \(\alpha\in\mathbb{Z}_q\), \(u=g^\alpha\) and sends \(u\) to Bob
- Bob computes \(\beta\in\mathbb{Z}_q\), \(v=g^\beta\) and sends \(v\) to Alice
- Alice computes \(w=v^\alpha\)
- Bob computes \(w=u^\beta\)[1]
The shared secret \(w\) is easily computed by multiplication but the reverse process of recovering \(\alpha,\beta\) is difficult. Any attacker, given \(g^\alpha, g^\beta\) cannot easily compute \(g^{ab}\).
This is guaranteed by the Decisional Diffie–Hellman (DDH) assumption:
Given a triplet that is either
- \((g^\alpha, g^\beta, g^\gamma)\) or
- \((g^\alpha, g^\beta, g^{\alpha\beta})\) where \(\alpha,\beta,\gamma\) are random elements in \(\mathbb{Z}_q\)
the probability of any efficient attacker in deciding which of the 2 cases the triplet is in is negligible.[2]
Diffie-Hellman is great for synchronous communications as it generates random keys for each connection. It can prevent replay-attacks and is widely-used in today’s network communications.
The security of Diffie-Hellman, when used in practice, depends on good choices of \(g\) and \(\mathbb{G}\). If the group order is too small, a brute-force like attack can easily break the cipher. Pohlig-Hellman and Pollard Rho algorithms can be used to find the keys secret key \(d\) in at most \(log(\vert q\vert)\) time where \(p\) is the largest prime factorization of \(\mathbb{G}\). Therefore, it’s good practice to choose a safe prime \(p=2q+1\).
RSA Encryption
RSA is built on the idea that factoring of the product of 2 primes is difficult. However, its security also depends on the selection of public/private keys and the product.
The server…
- Generate 2 large primes \(p, q\) and set \(N=pq\)
- By the Euler’s totient function, compute \(\phi(N)=(p-1)(q-1)\). Choose \(e\in(1,\phi(N))\) and \(gcd(e, \phi(N))=1\). Publish tuple \((e, N)\) as the public key
- Compute the modular inverse of \(d\) such that \(de\equiv 1\bmod\phi(N)\), which is kept as the secret key
- On receiving cipher text \(c=m^e\bmod N\), recover \(m=c^d\bmod N\)
Anyone can encrypt message using the same public key, but only the server is able to decrypt and recover the message (ie. prevents man-in-the-middle). However, many factors affect the actual security of RSA. Some of them includes, padding oracle attack with, Coppersmith’s attack with Lattice Reduction. In addition, the message must be able to wrap around \(N\) (ie. \(m^e>N\)) to offer any security by RSA.
References
[1]: A Graduate Course in Applied Cryptography by Dan Boneh and Victor Shoup
[2]: DDH - Wikipedia