RSA blind signature attack but without public exponents

rengoku

6/23/23, 12:43 PM

I been trying to solve a particular challenge where we have to sign an admin message.

At first it seems a classic RSA blind signature attack but eventually they didnt give out the public exponents(e,n) and e is of prime(128) length.

The server offers to encrypt anything n number of times but not the admin message and there's is a option for verification,if we verify the admin message we get the flag!

But im completely stuck here any help would be appreciated.

Thanks.

0 + 0

rsa

attack

Score:1

Crypto

poncho

6/23/23, 2:22 PM

But im completely stuck here any help would be appreciated.

Well, this appears to be a CTF challenge (or similar), and so I won't spell out the full answer; I will give hints to the two subproblems involved.

The first problem is to recover the modulus $n$; how can we do that? If we ask for the encryption of both $c$ and $c^2$ (for some $c < \sqrt{n}$; we can get an estimate of the size of $n$ by asking for the signature of an arbitrary value), how can we get a multiple of $n$ from those two values $c^e \bmod n$ and $c^{2e} \bmod n$? What if we did that with a different pair $d, d^2$? How can that be used?

The second problem is deducing the value $m^e \bmod n$, where we know the value $n$ (but not $e$) and where $m$ is the admin message. Hint: $a^e \times b^e \equiv (ab)^e \pmod n$, even if we don't know what $e$ is...

0 + 0

rengoku

6/23/23, 4:01 PM

Thanks for the heads up! and the message seems to be a prime ==> assert isPrime(to_sign) So will be there any alternate workarounds?

poncho

6/23/23, 4:38 PM

@rengoku: well, then you'd need to compute a modular inverse in step 2 to find $b$ given $a, m$; not *that* difficult, I suppose...

rengoku

6/25/23, 2:39 PM

Thanks for the help ! I managed to solve it

Score:1

Crypto

AZAN SHAHID

9/23/23, 9:54 AM

Spoiler Alert:

If server allows to sign negative integer you can sign negative of admin message. You will get a positive value. Send negative of that as verification and you will get it. If you still want positive signature sign -1 value you will get is n-1. Just add 1 in it to get n. And for RSA sum of positive and negative of a same message is equal to n. Just subtract encryption of negative message from n and you will get encryption of positive admin message.

0 + 0

Elon Musk

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

EN: RSA blind signature attack but without public exponents

TH: การโจมตีลายเซ็น RSA ตาบอด แต่ไม่มีเลขยกกำลังสาธารณะ

RO: Atacul orb cu semnătură RSA, dar fără exponenți publici

RU: Атака со слепой подписью RSA, но без публичных экспонентов

VI: Tấn công chữ ký mù RSA nhưng không có số mũ 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.