# 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?

• Prove presence to whom? A Webserver? An application on your local computer? – SEJPM Jun 12 '15 at 19:25
• @SOJPM to a system. I was thinking about signing a time-stamped packet or time-stamping the signature, or both to be able to prove later, in case of an audit, that this device was present while certain information was being processed during an activity where device's holder participated. – Glushiator Jun 12 '15 at 19:30
• Is your "securely prove presence of the device in a certain situation" idea quantitative or just qualitative? $\:$ For example, would it still work for your idea if an adversary could get signatures for $q^{\hspace{.03 in}5}$ messages with just $q$ queries to the device, for arbitrary positive integers $q$? $\;\;\;\;$ – user991 Jun 15 '15 at 7:46

## 1 Answer

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&\text{if }l_i\ne0\\(r_i\oplus i)\|r_i&\text{if }l_i=0\text{ and }r_i\ne i\\i\|r_i&\text{if }l_i=0\text{ and }r_i=i\\\end{cases}$
• increment $c$ before disclosing $K$ or $\overline{\mathcal V}(\overline s,m)$.
• On the other hand, with $K$ predictable to an adversary, $P$ would need something like collision-resistance. $\;$ – user991 Jun 15 '15 at 7:49
• @Ricky Demer: if $K$ is predictable, the schemes becomes brittle, especially if $P$ is not purposely slow. In particular the adversary can (with effort about $2^{62}$ evaluations of $P$) find $m$ such that $P(K,m)$ for the predicted next $K$ has an $x_i$ of the adversary's choice, and make an existential forgery with about $2^{64}$ evaluations of $P$ and 4 queries to the broken signer with predictable $K$. – fgrieu Jun 15 '15 at 8:21
• I'm actually talking about a very efficient special-case attack. $\;\;\;$ Namely, suppose that when $\: K = K_{\hspace{.02 in}0} \:$, $\:$ $P$ does not actually depend on $m$. $\;\;\;$ (After all, if there are PRFs then there are PRFs with that property.) $\;\;\;$ For such PRFs, 4 chosen queries to the device would allow production of signatures for all subsequently-determined messages, so although this would not constitute a forgery attack on your scheme, it does show that something more than PRFness of $P$ is needed for your scheme to "prove presence of the device". $\;\;\;\;\;\;\;\;$ – user991 Jun 15 '15 at 8:39