6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – SEJPM Jun 11 at 8:33
  • $\begingroup$ Is it possible to have a signature that signs itself? Aren't we talking about an unborn child? $\endgroup$ – kelalaka Jun 11 at 8:35
  • $\begingroup$ 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. $\endgroup$ – Maarten Bodewes Jun 11 at 14:05
4
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Maarten Bodewes Jun 13 at 10:52

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.