是否有一种方案允许使用基于RSA的挑战响应协议，仅限于签名8个字节，以创建任何数据的安全签名？

Question

我有一个很小的设备，它有一个挑战响应认证机制，设备用它的内部2048位RSA密钥对任何数据的8个字节进行签名。

我希望能够通过使用一些安全链接在一起的问题响应对来验证使用这种机制的任何数据(只使用1对已经被丢弃的数据，因为不安全的64位长散列)。每个挑战可能只包含8个字节，每个响应都是一个256个长的SHA256withRSA签名。要求使用尽可能少的操作，因为一个操作需要1秒才能执行。

这样做的目的是在一定的情况下安全地证明设备的存在。

有什么建议吗？

Answer 1

是!这里有一个这样的计划。

让s=\mathcal S(x)是问题的小设备为64位输入x所产生的结果，并为其提供\mathcal V(s,x)的公共验证功能，如果s与x匹配，0则输出1。我假设这是在自适应选择的消息攻击下抵抗生存伪造的，我们希望将它扩展到任意大的消息m；我们可以假设这个问题的微小设备仅用于我们指定的。

假设P是一个具有256位输出的PRF，也许是P(K,m)=\operatorname{HMAC}_\text{SHA-256}(K,m)。

愿意签署m的签名人：

• 绘制一个256位的真正随机位字符串K (它将保持秘密直到签名的最后一步)；
• 计算P(K,m)并将其分解为四个64位x_0、x_1、x_2、x_3；
• 从问题的微小装置中获取s_0=\mathcal S(x_0)、s_1=\mathcal S(x_1)、s_2=\mathcal S(x_2)、s_3=\mathcal S(x_3)；
• 输出作为\overline{\mathcal S}(m)构建的\overline s=K\|s_0\|s_1\|s_2\|s_3。

公共验证函数\overline{\mathcal V}(\overline s,m)

• 将\overline s分解为K、s_0、s_1、s_2、s_3 (或者如果\overline s没有适当的长度，则输出0并终止)；
• 计算P(K,m)并将其分解为四个64位x_0、x_1、x_2、x_3；
• 输出\overline{\mathcal V}(\overline s,m)，计算为\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)。

对于对手来说，K是不可预测的，选择x是不可能获得\mathcal S(x)的。在这个问题的微型设备以每秒一次\mathcal S的速度运行34年后，它的输出将小于s=\mathcal S(x)的2^{30}值。因此，每一次寻找合适的(K,m)的对抗性尝试都比2^{4(30-64)}=2^{-136}更容易产生x_0、x_1、x_2、x_3，所有这些都是由微小的设备产生相应的s，从而允许伪造。因此，如果对手只能对2^{96}进行P的评估，则该方法的剩余伪造概率小于2^{-40} (唯一的其他方法是利用原始\mathcal S或\mathcal V，或TRNG生成K或PRF P中的一些弱点)。可以提供严格的安全证据。

如果我们想把事情推向更短的签名，我们可以使用三个签名，而不是四个签名，方法是让P计算成本很高；例如，使用氪石：P(K,m)=\operatorname{Scrypt}(P=K,S=m,N,r,P,{dkLen}=24)和参数N,r,P进行优化，以匹配用于签名的计算机的计算能力，并产生一秒钟的计算结果。我们还可以将K缩短为40位(会有很多冲突，但不会造成太大的伤害)。

附加:如果由于某种原因，签名者无法使用安全TRNG，我们可以使用32位计数器c和额外的\mathcal S调用；

• 将K生成为\operatorname{SHA-256}\big(\mathcal S(\text{00000000}_\text{ h}\|c)\big)\;；或者，如果我们知道\mathcal S输出的格式，我们可以分离其中的一些随机比特，而不是散列；
• 使用x'_i而不是x_i，这样x'_i的左半部分就不会是0 (这些\mathcal S的输入值保留给上面的随机生成)；例如，如果x_i的一半是l_i和r_i，我们就使用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}
• 在披露c或\overline{\mathcal V}(\overline s,m)之前增加K。