# RSA Signing - Existential forgery and message prefix question. It's a weird one

I'm new to this. Please be kind. I have a theoretical question that I would like sanity checked:

Bob and Alice are doing RSA signing without a hash function -- just putting a message in, and getting a signature out.

The messages Bob and Alice are sending each other are random numbers.

Without a hash function involved an attacker can create a message with the signature they want. But they can't control the message.

However because Bob and Alice are sending each other random numbers, this attacker could create a valid looking message. That is, a valid signature on a seemingly random looking number.

But Bob and Alice want to make this scheme secure, so they add a known prefix to their messages. They add some structure.

So instead of a message looking like: 484262 It looks like: prefix_484262

Here's the thing I want sanity checked:

By adding the known prefix, an attacker can only forge messages by brute force, and as a result the security of this scheme is proportional to the length of the prefix.

That is to say, the length of the prefix matters. For instance if the prefix was just one octet, presumably the attacker would just need about 255 tries to forge a message that works. But, if the prefix was two octets The attacker would need 65,536 tries.

The other thing I want sanity checked is:

Knowing the prefix is not an advantage to brute forcing the messages (other than the fact that the attacker knows what the output needs to look like).

Thanks for any help. I appreciate it.

• Maybe you could check this answer. Note that PKCS#1 v1.5 padding is basically prefix + hash that is put through modular exponentiation with the private key. Note too that you would want the result to be about as big as the modulus, so using a dynamically sized prefix makes sense. Apr 10, 2022 at 19:23

By adding the known prefix, an attacker can only forge messages by brute force, and as a result the security of this scheme is proportional to the length of the prefix.

Here is my understanding of the scenario (and if this is incorrect, what I say becomes invalid):

• Alice (and Bob) is willing to compute $$M^d \bmod n$$, for arbitrary messages $$M$$ as long as $$M$$ has the agreed on prefix (and secret $$d$$, but public $$n$$ and $$e$$ (which is the public exponent corresponding to the private exponent $$d$$).

• The attack you are considering is a blinded RSA attack; the attacker has a message $$M'$$ and they want to compute $$M'^d \bmod n$$, however $$M'$$ does not start with the prefix. So, what the attacker does is select a random value $$R$$, computes $$R^eM'$$, and checks if just happens to have the prefix - if it does, they give that to Alice, who signs it, forming $$R M'^d$$, and the attacker divides out $$R$$ and they win.

The probability (per iteration) of this attack succeeding is dependent on the probability that $$R^eM'$$ happens to have the prefix, which is proportional to the prefix length.

If that is the scenario, well, that's not the only attack we need to be concerned with.

Another attack would be if the attacker finds a large number of smooth integers that all start with the prefix, and has Alice 'sign' them; smooth integers are ones which have only small factors. If the attacker can find $$k$$ such smooth integers that each consist of only the first $$k$$ primes, then (ignoring the possibility of the linear equations not being independent; this can be easily gotten around by having a couple extra), the attacker can learn the value $$p^d \bmod n$$ for all the first $$k$$ primes $$p$$.

There are several ways an attacker can exploit this, the most likely way is to improve the search time for the original attack: if we assume that the attacker can learn $$2^d \bmod n$$, then they can test $$2^z M'$$ for increasing values of $$z$$; for each failed test, they would do a doubling, which is a lot cheaper than the original (where multiplying by $$2^e \bmod n$$ would appear to be the most efficient possible).

• I've come to conclusion that RSA is well known but is trickier to use than DSA. We're just used to avoiding RSA's foibles (until we aren't; somebody busted a large number of keys generated by a stupid algorithm putting them too close to the midpoint). Of course, DSA has its own. Don't leak any information about k; use a crypto-strong RNG to get a new k for each message. Apr 11, 2022 at 4:27

I assume the signature system proposed takes a message $$M$$, converts it to an integer $$m$$ less than $$n$$ by somewhat adding a fixed constant $$c$$ on the left of the expression of $$M$$ of as $$i$$ digits in some base $$b\ge2$$ (base 10 in the question) thus $$m:=c\,b^i+M$$, then builds the signature $$\sigma=\mathrm{Sig}(M)$$ per textbook RSA with private key $$(n,d)$$, that is $$\sigma:=m^d\bmod n$$; and the verifier given $$(n,e)$$ and $$(M,\sigma)$$ (or just $$\sigma$$) computes $$\sigma^e\bmod n$$ then checks that's $$c\,b^i+M$$. For now, I leave it unspecified if $$i$$ is fixed, or depends on $$M$$ (and how).

By adding the known prefix, an attacker can only forge messages by brute force, and as a result the security of this scheme is proportional to the length of the prefix.

For this proposition to have any chance of standing true, we must add "up to the point the prefix $$c$$ becomes so large that factorization of $$n$$ becomes the easiest attack". I assume this in the following.

That proposition appears true (but we don't have a proof) if we take as definition of security for signature Existential Un-Forgeability under Known Message Attack, in which adversaries have the public key $$(n,e)$$ plus a number of valid $$(M_j,\sigma_j)$$ pairs for random $$M_j$$, and try to exhibit a $$(M,\sigma)$$ pair for $$M$$ none of the $$M_j$$.

But that's incorrect if we take Existential Un-Forgeability under Chosen Message Attack, in which the adversary is allowed to query for signature $$\sigma_j$$ of any message $$M_j$$ of their choice, before exhibiting $$(M,\sigma)$$ as above. Problem is, under this model of security there are attacks better than brute-force.

• Attack is easy if we allows $$i$$ to be the number of digits of $$M$$ in base $$b$$ (be it with or without suppressing leading zeroes), and use a small public exponent $$e$$ (e.g. 3): an attacker finds the signature of any message $$M$$ it sees fit (up to some size limit) from the signature of message $$M'=M\,b^e$$ if $$M$$ is short enough to meet the $$c\,b^{i'}+M'=c\,b^{i+e}+M\,b^e requirement, since $$\mathrm{Sig}(M')\,b^{-1}\bmod n=\mathrm{Sig}(M)$$.
• For fixed $$i$$, things are harder, but the Desmedt and Odlyzko attack allows forgery with difficulty much lower than brute force, far from doubled when we allow $$c$$ to be twice as large, and even sub-exponential with $$\log_2(c)$$.
• The previous attack becomes easier if we allow $$i$$ fixed for a given $$c$$, but equal to the size of $$c$$ in base $$b$$.

Knowing the prefix is not an advantage to brute forcing the messages (other than the fact that the attacker knows what the output needs to look like).

The motivation of signature is to allow verification with no secret information, and making the prefix secret goes against that. I'll assume it nevertheless.

Then, that statement is correct except under the unrealistic Key-Only Attacks, but moot for the very reason that makes it correct: adversaries know at least one $$(M_0,\sigma_0)$$ pair in addition to the public key $$(n,e)$$, and they can thus easily find the prefix $$c$$ by computing $${\sigma_0}^e\bmod n$$.