Is it possible to have a signature that signs itself?

Question

This is a curiosity. I don't see any value (yet) of using this.

Is it possible to have a signature that signs itself?

What I mean is that when you send a signed message, you send something like $(message \mathbin\| signature)$, where $signature = Sign(message)$. Is there a signature scheme in which $signature = Sign(message \mathbin\| signature)$?

Because the message should be hashed, you can't solve for $signature$ or do some sort of meet-in-the-middle solution.

My initial thoughts are (1) using SHA-2 or some other hash functions vulnerable to a length extension attack or (2) use homomorphic hash in some fashion. (1) would still require brute-force, but it would reduce computation. I haven't figured out how to use (2), especially since all the homomorphic hashes I know about aren't homomorphic w/r/t concatenation.

Answer 1

Is there a signature scheme in which $\text{signature} = \mathsf{Sign}(\text{message} \mathbin\| \text{signature})$ ?

With standard RSA signatures (RSASSA-PKCS1-v1_5, RSASSA-PSS of PKCS#1), that's possible if one chooses the public/private key pair for that purpose, as a function of the message. On top of that one can even make the signature nearly anything (any bytestring the size of the public modulus except two¹: the all-zero bytestring, and its variation with the last byte 0x01).

I'll use RSASSA-PKCS1-v1_5 with RSA-2048 and SHA-256, because that's simple and common. I'll silently assimilate bitstrings to integers per big-endian convention.

Choose our arbitrary message $M$. Choose our 256-byte signature $S$ of 2048-bit, other than 0 or 1, and not overly close to $2^{2048}$ (say, the first byte is not 0xFF). Hash $M\mathbin\|S$ with SHA-256, yielding $H$, and form the 256-byte representative per EMSA-PKCS1-v1_5 $$R = \mathtt{00\,01}\,\underbrace{\mathtt{FF…FF}}_{202\text{ bytes}}\,\mathtt{00\,30\,31\,30\,0d\,06\,09\,60\,86\,48\,01\,65\,03\,04\,02\,01\,05\,00\,04\,20}\mathbin\|H$$

There remains to build a public/private RSA key pair $(N,e,d)$ with $N$ of 2048 bits such that $S^e\bmod N=R$ and $S<N$, which will insure that $S=\mathsf{Sign}_{(n,d)}(M\mathbin\|S)=S$, as asked.

The central idea is to choose $N$ the product of two primes $p$ and $q$ such that we can find odd $e_p$ with $S^{e_p}\equiv R\bmod p$ and $e_q$ with $S^{e_q}\equiv R\bmod q$, with $(p-1)/2$ and $(q-1)/2$ coprime, and product of distinct small primes. We'll then find $e$ by using the Chinese Remainder Theorem. Refer to this answer for details.

That takes like 30s in Python, Try It Online! (revised 2020-06-13).

---

¹ For deterministic schemes, there can be a few more forbidden signatures, depending on message. That's because when $R=S$ the method described won't work. However, exhibiting a concrete example would be a break of the hash.