# plain textbook RSA signature with a fixed format input

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.

• "Is it safe?" Safe in what way? You want to prevent leakage of private key? You want to prevent learning of user-id?; What can he get from system? How is that authentication used? You don't give nearly enough details for proper answer. – axapaxa May 22 '17 at 10:47
• @axapaxa Sorry I just wanted to simplify the question. Now added detail description. And really thank you for your nice answer. – Wizr May 27 '17 at 2:24

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.

• I think (N, e) can be easily got, theoretically or practically, especially by our user, if they want. So assume they know. And I'm not familiar with cryptography, but from recent days' studying, I think they can hardly generate a valid QR code using chosen text attack when they can only get limited pairs of s, m. – Wizr May 27 '17 at 2:45

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).