3
$\begingroup$

In his book "Applied Cryptography" Bruce Schneier, when talking about public key cryptography, says that:

If the same algorithm is used for both encryption and digital-signature verification there is a possible attack. In these cases, the digital signature operation is the inverse of the encryption operation: Vx = Ex and Sx = DX.

I'm not sure how that is possible, could you further explain what Bruce is proposing here?

$\endgroup$
  • $\begingroup$ Well, you can chose randomly (or probably also systematically) encrypt strings and you will forge a valid signature every single time (even though probably for a message that you can't exactly control but probably at least recover). $\endgroup$ – SEJPM Jul 26 '17 at 19:57
  • $\begingroup$ One thing of note: Applied cryptography is outdated and contains some bad advice. The book has been updated, the current title is "Cryptography Engineering: Design Principles and Practical Applications" by Schneier, Ferguson, and Tohno. $\endgroup$ – SAI Peregrinus Jul 27 '17 at 0:25
4
$\begingroup$

$\newcommand{\Z}{\mathbb{Z}}$Pick primes $p$ and $q$ with $2^{1023} < p < q < 2^{1024}$ and $n = p q > 2^{2047}$, drawing $p$ and $q$ uniformly at random. $n$ is the public key, and $p$ and $q$ are the private key, with which you can quickly compute cube roots modulo $n$. (You can also use $65537^\text{th}$ roots, but $e = 3$ makes the public-key computations faster and makes no difference for security in sensible RSA-based signature and encryption schemes.)

Suppose a ‘signature’ on a message $m \in \Z/n\Z$ is a cube root $s$ of $m$ modulo $n$ so that $s^3 \equiv m \pmod n$, and suppose you ‘encrypt’ a message $m \in \Z/n\Z$ by cubing it giving a ciphertext $c \equiv m^3 \pmod n$ so that ‘decrypting’ $c$ requires computing cube roots modulo $n$. This is what is endearingly called ‘textbook RSA’, though it should more properly be called ‘do you even RSA, bro‽’.

  • The signature scheme is itself pathetically broken because I just forged the signature $s = 3$ on the message $m = 27$, and given two signatures $s_0, s_1$ on messages $m_0, m_1$ I can forge the signature $s_0 s_1$ on $m_0 m_1$ by multiplying numbers.
  • The encryption scheme is itself pathetically broken because if you try to encrypt a short message, such as a 32-byte secret key, whose encoding as an element $m$ of $\Z/n\Z$ has an integer representative below $\sqrt[3]{n}$, I can just compute the integer cube root of $c$ to recover $m$.

How does using the same key for signature and encryption make it worse, you ask? Suppose you intercepted a ciphertext $c \equiv m^3 \pmod n$ that someone sent to me, and you want to find the message $m$. If you persuade me to sign $c$ as a message, giving the signature $s$ with $s^3 \equiv c \pmod n$, then the signature I reveal to you is $s \equiv m \pmod n$. Oops.

This is not how modern RSA-based signature or encryption schemes work, fortunately.

In modern RSA-based signature schemes (RSASSA-PSS, RSA-FDH), a signature on an octet string $m$ is a pair $(r, s)$ where $r$ is a (possibly empty) uniform random bit string and $s$ is a cube root of $H_0(r, m)$ modulo $n$, for some standard hash function $H_0$ mapping messages to elements of $\Z/n\Z$ over which the attacker has little control.

In modern RSA-based encryption schemes, we either

(a) RSAES-OAEP: pick a short secret session key $k$ uniformly at random, pick a bit string $r$ uniformly at random, and send $c \equiv H_1(r, k)^3 \pmod n$, where $H_1$ is a hash function mapping short strings to elements of $\Z/n\Z$; or

(b) RSA-KEM: pick $x \in \Z/n\Z$ uniformly at random, send $c \equiv x^3 \pmod n$, and derive the short secret session key $k = H_2(x)$, where $H_2$ is a hash function mapping elements of $\Z/n\Z$ to short octet strings.

Then we use $k$ as the secret key for a symmetric-key AEAD to enclose the message.

Since the attacker can't control more than $b$ bits of the output of $H_0$, $H_1$, or $H_2$ without spending at least $2^b$ effort, varying either the message $m$ to be signed or the ciphertext $c$ to be decrypted doesn't help them either to decrypt messages of their choice or to sign any messages they can figure out.

All that said, the lesson here is that the security of a cryptosystem that uses one key for two different purposes—e.g., signing and encrypting, or even two different encryption schemes such as RSAES-PKCS1-v1_5 and RSAES-OAEP—is not determined by independently analyzing each purpose; combining them may have catastrophic consequences, and the composite cryptosystem must be studied in its own right. If you also want to use, say, a verifiable random function with the same key, you have to study it again.

$\endgroup$
  • $\begingroup$ We call $(n,e)$ is the public key, $(n,d)$ is the private key. $n$ is called public modulus, $e$ is public exponent, $d$ is the private exponent. Of course, you know the factorization of $n$ you now $p,q$. $\endgroup$ – kelalaka Oct 3 at 19:01
  • $\begingroup$ I kept it simpler by considering only cubes and cube roots, so there is no need to consider $e = 3$ to be part of the per-user public key; it is just a standard part of the system. Part of my point, after all, is to de-emphasize false suggestions of symmetry between encryption and signature. $\endgroup$ – Squeamish Ossifrage Oct 3 at 19:03
4
$\begingroup$

Say you ask the holder of the private key to decrypt something that you've encrypted for him. You've however lost the original data. So the holder of the private key decrypts the seemingly random data and returns the result.

Now imagine that instead of a ciphertext you send a message to be signed or a hash over the message to be signed. The holder of the private key will try to decrypt it. However, because $D(x) = S(x)$ what is returned is a valid signature over the message. This could be the case for, for instance, raw RSA.

However, for most encryption algorithms this won't be possible in real life. For instance, raw RSA is insecure, so PKCS#1 padding is used. Not only is PKCS#1 padding different for encryption and signature generation, but remember that we have to unpad for decryption and pad for signature generation.

So it depends on the algorithm used, but for often-used encryption primitives the problem is usually not applicable. Still, it is always preferable to use a different key pair for authentication, signing (or rather, non-repudiation) and encryption.

If you have to create your own protocol for, for instance, homomorphic encryption, where raw primitives are more common then sure, remember Bruce's advice.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.