Is it possible to have a signature that signs itself?

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.

• There are schemes (Fiat-Shamir Transformed Sigma ZKPs) where you have a signature $(c,z)$, you derive some value $a$ from them and then check whether $c=H(a\|m)$, this is kinda cyclic. Here's a recent example I wrote up. – SEJPM Jun 11 '20 at 8:33
• Is it possible to have a signature that signs itself? Aren't we talking about an unborn child? – kelalaka Jun 11 '20 at 8:35
• I don't think length extension attacks are usable for this. As clearly indicated to me, length extensions are mainly on topic if you hash data & a secret; and I don't see the secret. – Maarten Bodewes Jun 11 '20 at 14:05

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, 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.

• I guess this rules out creating a signature using the same key pair of course; choosing the modulus $N$ - and thus primes $p$ and $q$ - seems orthogonal to such a requirement (which is not stated in the question). I guess such a scheme would break the signature requirements to begin with, as there would be two messages matching the same signature. – Maarten Bodewes Jun 13 '20 at 10:52