Is there a scheme that allows to use RSA based challenge response protocol limited to signing only 8 bytes to create a secure signature of any data? I have a tiny device that has a challenge-response authentication mechanism where the device signs 8 bytes of any data with it's internal 2048 bit RSA key.

I would like to be able to certify any data using this mechanism by using a number of challenge-response pairs securely chained together (using only 1 pair already discarded because of insecurity of 64 bit long hashes). Each challenge may contain only 8 bytes, each response is a 256 long SHA256withRSA signature. The requirement is to use as few operations as possible since one operation takes 1 second to execute.

The idea is to securely prove presence of the device in a certain situation.

Any suggestions?
Yes! Here is one such scheme.

Let $s=\mathcal S(x)$ be what that the question's tiny device produces for 64-bit input $x$, and $\mathcal V(s,x)$ the public verification function for that, which outputs $1$ if $s$ matches $x$, $0$ otherwise. I'll assume this resists existential forgery under adaptive chosen message attack, and we want to extend it to arbitrarily large messages $m$; and we can assume that the question's tiny device is used only as we specify.

Let $P$ be a PRF with 256-bit output, perhaps $P(K,m)=\operatorname{HMAC}_\text{SHA-256}(K,m)$.

The signer willing to sign $m$:


draws a 256-bit true random bitstring $K$ (it shall remain secret until the last step of the signature);
computes $P(K,m)$ and breaks it into four 64-bit $x_0$, $x_1$, $x_2$, $x_3$;
obtains $s_0=\mathcal S(x_0)$, $s_1=\mathcal S(x_1)$, $s_2=\mathcal S(x_2)$, $s_3=\mathcal S(x_3)$ from the question's tiny device;
outputs $\overline{\mathcal S}(m)$ built as $\overline s=K\|s_0\|s_1\|s_2\|s_3$.


The public verifying function $\overline{\mathcal V}(\overline s,m)$


breaks $\overline s$ into $K$, $s_0$, $s_1$, $s_2$, $s_3$ (or if $\overline s$ does not have the appropriate length, outputs $0$ and terminates);
computes $P(K,m)$ and breaks it into four 64-bit $x_0$, $x_1$, $x_2$, $x_3$;
outputs $\overline{\mathcal V}(\overline s,m)$ computed as $\mathcal V(s_0,x_0)\cdot\mathcal V(s_1,x_1)\cdot\mathcal V(s_2,x_2)\cdot\mathcal V(s_3,x_3)$.


With $K$ unpredictable to an adversary, it is impossible to obtain $\mathcal S(x)$ for chosen $x$. In 34 years of operation of the question's tiny device at a rate of one evaluation of $\mathcal S$ per second, it will output less than $2^{30}$ values of $s=\mathcal S(x)$. Thus each adversarial attempt at finding suitable $(K,m)$ has odds less than $2^{4(30-64)}=2^{-136}$ to yield $x_0$, $x_1$, $x_2$, $x_3$ all among those for which the corresponding $s$ was produced by the tiny device, which would allow a forgery. Thus if an adversary can make no more than $2^{96}$ evaluations of $P$, residual odds of forgery by that method are less than $2^{-40}$ (the only other methods are exploiting some weakness in the original $\mathcal S$ or $\mathcal V$, or the TRNG generating $K$, or the PRF $P$). A rigorous security proof could be made.

If we want to push things towards shorter signature, we could use three signatures rather than four by making $P$ costly to compute; say, using Scrypt: $P(K,m)=\operatorname{Scrypt}(P=K,S=m,N,r,P,{dkLen}=24)$ with parameters $N,r,P$ optimized to match the computing capabilities of the computer used for signature and yield one second computation. We could also shorten $K$ to $40$ bits (there will be a number of collisions, but it won't really harm much).



Addition: if for some reason a secure TRNG is not available to the signer, we can do with a 32-bit counter $c$, and an extra invocation of $\mathcal S$; we


generate $K$ as $\operatorname{SHA-256}\big(\mathcal S(\text{00000000}_\text{ h}\|c)\big)\;$; or if we know the format of the output of $\mathcal S$ we can isolate some random bits of that, rather than hashing;
use $x'_i$ rather than $x_i$ so that the left half of $x'_i$ is never $0$ (these input values of $\mathcal S$ being reserved for random generation as above); e.g. if the halves of $x_i$ are $l_i$ and $r_i$, we use $x'_i= \begin{cases}x_i=l_i\|r_i&amp;\text{if }l_i\ne0\\(r_i\oplus i)\|r_i&amp;\text{if }l_i=0\text{ and }r_i\ne i\\i\|r_i&amp;\text{if }l_i=0\text{ and }r_i=i\\\end{cases}$
increment $c$ before disclosing $K$ or $\overline{\mathcal V}(\overline s,m)$.