plain textbook RSA signature with a fixed format input

Question

We have an old system using the following algorithm related to authentication:

• input: a fixed format integer (hex): <user-id>0000f000<device-id>
  • user-id: 4 bytes
  • device-id: 4 bytes
• algorithm: textbook RSA 2048, sign with (N, d).

and assumes that an attacker can request limited times (5 times per account per day) with arbitrary device-ids, or try with different user-ids.

Update

1. sign with (N, d), not (d, e), already updated above;
2. the background is, logged-in users can apply for usage of a device, if the device is not in use, the user will get a QR code containing the info of the signature. The device will check it (user-id and device-id), if succeeded, the device will unlock automatically.

Question: is it possible that an attacker without login can generate a QR code to unlock any device (device-id is right on the device, and is a random number each time)?

by the way, the device does not deserve much cost. We consider it is not safe when there is an easily-adopted hacking method. And also ignore the case that one can remember the corresponding QR code.

Answer 1

That signature system is insecure assuming that the adversary

• can obtain a few signatures for <user-id> and <device-id> which s/he can choose (with perhaps <user-id> constrained, e.g. in a list),
• is deemed to succeed if creating a valid signature for some <user-id> for which s/he was not given signature (perhaps with some constraint) and <device-id> s/he can choose,
• knows the public key $(N,e)$.

In a simple form of the attack, the adversary restricts to suitably smooth values of $m_i=$<user-id>0000f000<device-id>, and finds a set of these $m_i$ and associated $k_i\in\mathbb Z$ (with $k_0=1$, $k_i\ne0$) such that $$1=\prod m_i^{k_i}$$ which, when there are enough smooth $m_i$, essentially reduces to solving a system of linear equations (obtained by considering the multiplicity of each prime factor of each smooth $m_i$). It is then easy to compute the signature $s_0$ for $m_0$ from the signatures $s_i$ for other $m_i$, as $$s_0=\prod_{i>0}s_i^{-k_i}\bmod N$$

Improvements replace the constraint $k_0=1$ with $\gcd(k_0,e)=1$, and exploit very low $e$ like $e=3$, by noticing that a signature can still be forged if the linear equations on multiplicities are satisfied modulo $e$.

How hard the attack is depends primarily on the width of the $m_i$ (here modest with at most 96 bits, perhaps 65 or 48 with enough freedom <user-id>) and on the maximum number of signatures that can be obtained; on the freedom there is on the choice of <user-id>; and to some degree on $e$. Critically, the size of $N$ is immaterial.

The attack is often designated the Desmedt and Odlyzko attack, with reference to Y. Desmedt and A. M. Odlyzko: A chosen text attack on the RSA cryptosystem and some discrete logarithm schemes, in proceedings of Crypto 1985. A modern re-exposition is in section 3 of Jean-Sebastien Coron, David Naccache, Mehdi Tibouchi and Ralf-Philipp Weinmann: Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures (in proceedings of Crypto 2009 then Journal of Cryptology, 2016).

Exhibiting actual values of <user-id> and <device-id> allowing the attack is an interesting exercise.

Answer 2

By default, textbook RSA is not safe from a modern point of view. Security definitions like ciphertext-only attacks (COA) are used to describe classical ciphers and not relevant for today's cryptosystems: If any cipher doesn't fullfill the much stronger security-definitions, it is considered broken.

So yes, textbook-RSA is considered broken, because for practical use we require security properties which textbook RSA does not have, e.g. IND-CPA.

Therefore: Use RSA with a proper padding-scheme, e.g. RSA-OAEP (for encryption) or RSA-PSS (for digital signatures).