“Signing” with public key

Question

For this question, the following caveats and assumptions hold:

• There exists a 2048-bit RSA key pair used exclusively for signing/verification
• The private key is kept completely private
• There exists a group of users who have the public key
• There is a group shared password
• I (mostly) understand the functional difference between encryption/decryption and signing/verification for RSA, but not the specific math differences
• I am aware of hashing

 

Given the Following Operation

"ciphertext" = RSA_sign( public_key, random salt + password )

What are the security implications if using PKCS#1 old-style v1.5 padding?

Obviously, this is not the accepted way of doing things -- one does not sign with a public key. Basically, the end result is a deterministic "encryption" of the password which can ultimately be compared among the members of the group. That is, because there is no randomization of the padding, each member can perform the same procedure and arrive at a comparable result. So member A and member B (neither of which have the private key) can perform this operation (as long as they have the salt) and determine that the password is the same. (Hashing, of course, would be a much better solution.)

The above scenario is susceptible to known plaintext attacks. eg. Similar to a hash, a malicious user can attempt to brute-force the password by simply trying combinations until they get a comparable result (the salt is, for all intents and purposes, public knowledge).

Is the private key at risk (I don't believe it is)?
Is this weaker than a hash such as SHA1?

UPDATE: After thinking about the relative security of this "RSA-hashing" mechanism to SHA1 for collisions, I realize that there would be an increased chance if msg.len > RSA.n.

_{(Please don't tell me to just use hashing. This is not the point of the question. I have seen questions asking if it's okay to "encrypt" using the private key which is a clear security problem, but I've never seen an answer to the question of signing with the public key.)}

Answer 1

Actually, if everyone uses a different salt whenever they "sign", and if the RSA_sign operation doesn't involve a hash (in general, real signature operations do, I don't know about your variant), it turns out not to be secure, and in fact, the password can be recovered fairly easily if the attacker hears enough signatures based on the same password.

Here's how it works: when someone signs the password, what they effectively do is take their password, apply the PKCS #1.5 padding to it, forming a message $M$. Then, they select a salt $A_i$, compute the 'signature' $S_i = (M + kA_i)^e \bmod N$, and publish the pair $A_i, S_i$ (where the value of $k$ depends on exactly how you combine the password and the salt; whether it does addition or bitwise concatination; we'll assume that the attacker can guess that). Now, this may not be the order that the signer actually implements things, but as long as the results are the same, that doesn't matter.

Now, suppose the attacker can get $e$ different such pairs $(A_i, S_i)$, and he wants to recover the common $M$ value. What he can do is binomially expand each such pair as:

$M^e + \binom{e}{1}kS_iM^{e-1} + \binom{e}{2}k^2S_i^2M^{e-2} + \ldots + \binom{e}{e-1}k^{e-1}S_i^{e-1}M + k^eS_i^e = A_i \mod N$

Now, the attacker knows all the above values except for $M$. So, he can then treat these equations as $e$ linear equations in the $e$ variables $M^e, M^{e-1}, \ldots, M$ within the ring $\mathbb{Z}/N$, and find the solution for $M$, recovering the password.

Now, there are several obvious ways to break up this attack:

• Use a huge public exponent $e$
• Combine the password and the salt in a nonlinear way (for example, by hashing them together)

On the other hand, the existence of this attack demonstrates that you really should think twice before trying it.