Eavesdropping attack on text-book RSA encryption with public nonce

smoothlee

3/23/23, 7:04 PM

Consider the following scenario: Alice has a secret key and public key pair for text-book RSA (denoted $\text{sk}$ and $\text{pk}$ respectively). Bob has an authentic copy of $\text{pk}$. The adversary has an authentic copy of $\text{pk}$.

Now, Bob wants to send his $\text{PIN}$ to Alice which is a four digit number. He encrypts as follows: First he chooses a nonce $N_0$ (a number chosen randomly from a very large domain). He then sends the encryption: $c = N_0 \mathbin\| \operatorname{RSA}(\text{pk}, [\text{PIN}\mathbin\| N_0]) = N_0 \mathbin\| [\text{PIN} \mathbin\| N_0]^e \bmod N$ where $(e,N)$ is the RSA public key.

Otherwise said, he constructs the new message $“\text{PIN} \mathbin\| N_0”$ (you may assume that he is able to embed $[\text{PIN}\mathbin\|N_0]$ as a number in $\{1, 2, … , N-1\}$) and encrypts that using text-book RSA. He also sends the number $N_0$ to Alice “in the clear”.

Show an attack which allows the adversary to learn the $\text{PIN}$ using only an eavesdropping attack.

I'm just not sure how to even start with this problem. I understand that textbook rsa creates the ciphertext with $\operatorname{Enc}(e, m) = m^e\bmod N$, but I don't know how I would get the $\text{PIN}$ if I can't tamper with messages. Any help would be appreciated.

I tried to work some things out and I've come to a different problem. Since the PIN has a relatively small number of possibilities, could I just use a brute force attack? Since the adversary knows the ciphertext, e, N0, and has access to the public key I could just keep trying different PINS correct?

103

0 + 0

rsa

attack

poncho

3/23/23, 7:33 PM

Hint: suppose you had a guess to the PIN - how would you verify that guess?

fgrieu

3/23/23, 8:37 PM

While editing the question, I took the liberty to replace the ambiguous occurrences of $a=b\pmod N$ with $a=b\bmod N$, which is the desired meaning in an RSA context. Recall $a\equiv b\pmod N$ means $b-a$ is a multiple of $N$, and $a=b\bmod N$ additionally means $0\le a<N$. If $a=b\pmod N$ is used and assigned one of the two meanings, that's best explicitly stated.

fgrieu

3/24/23, 10:45 AM

Yes you found the attack. Now your best options are writing an answer to your own question (you'll be able to accept it in a few days), or delete the question.

Score:1

Crypto

David Lui

3/30/23, 4:49 PM

RSA is deterministic. This means that if you encrypt the same message twice using the same public key, the two ciphertexts are exactly the same.

Since the adversary knows both $N_0$ and $E_{pk}(PIN || N_0)$, the adversary can guess a PIN $PIN_{guess}$ and verify their guess by computing $E_{pk}(PIN_{guess} || N_0)$ and checking if it equals $E_{pk}(PIN || N_0)$.

Since the PIN is a 4 digit number, the adversary can check all of the PINs.

0 + 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Eavesdropping attack on text-book RSA encryption with public nonce

TH: ดักฟังการโจมตีการเข้ารหัส RSA ในหนังสือเรียนด้วย nonce สาธารณะ

RO: Atac cu urechea asupra criptării RSA a cărților de text cu nonce public

RU: Атака подслушивания на стандартное шифрование RSA с общедоступным одноразовым номером

VI: Tấn công nghe lén mã hóa RSA sách giáo khoa với nonce công khai

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.