0
$\begingroup$

I am trying the Blind signature attack against an RSA crypto system (we have the value of N and e).

The system is defined as:

class RSA:
    def __init__(self, e, d, n):
        self.e = e
        self.d = d
        self.n = n

    def sign(self, msg):
        msg = int(msg.encode('hex'), 16)
        return pow(msg, self.d, self.n)

    def verify(self, msg, sig):
        msg = int(msg.encode('hex'), 16)
        verify = pow(sig, self.e, self.n)
        return msg == verify

This system allows me to do the following:

  1. Sign a message (other than the desired message)

  2. Verify the message

To sign the message, the code interprets my input message as shown below:

m = base64.b64decode(m)
m = int(m.encode("hex"), 16)

The desired message which I want to sign is: "check this"

So, I decided to use the Blind Attack as shown below:

  1. Chose a random value of 'r' such that 'r' is relatively prime to 'n' (gcd(r, n) = 1)

  2. Calculated the blinded message as shown below:

    M = "check this"

    M = int(M.encode("hex"), 16)

    M = 469440048988568330725747

    r = 3

So, M' = M * r^e mod N

I got M' = 23197755639757063616251098896030929296620390502715479513148568685304900389950103581065892241031729644711286485127332671201824316337367085311388408882287463092871368604873199283728291840921486779532441684227161682803605783877395206374452279642370838342344078339859990917350469230030211065087702649725450845840496395823640212936132815100326836805829209891510238692029283719097643211255749411742768146971730579472485865485182974850559517457334368981656730791912298827394135772525085384096283147715147158921374800971030021813145161866835151076051818566789845851064713174040021840255625914702552338381580735541362965413692

  1. Then, I sent the above message base64 encoded to the crypto system so that it signs it for me:

base64.b64encode(M') = "MjMxOTc3NTU2Mzk3NTcwNjM2MTYyNTEwOTg4OTYwMzA5MjkyOTY2MjAzOTA1MDI3MTU0Nzk1MTMxNDg1Njg2ODUzMDQ5MDAzODk5NTAxMDM1ODEwNjU4OTIyNDEwMzE3Mjk2NDQ3MTEyODY0ODUxMjczMzI2NzEyMDE4MjQzMTYzMzczNjcwODUzMTEzODg0MDg4ODIyODc0NjMwOTI4NzEzNjg2MDQ4NzMxOTkyODM3MjgyOTE4NDA5MjE0ODY3Nzk1MzI0NDE2ODQyMjcxNjE2ODI4MDM2MDU3ODM4NzczOTUyMDYzNzQ0NTIyNzk2NDIzNzA4MzgzNDIzNDQwNzgzMzk4NTk5OTA5MTczNTA0NjkyMzAwMzAyMTEwNjUwODc3MDI2NDk3MjU0NTA4NDU4NDA0OTYzOTU4MjM2NDAyMTI5MzYxMzI4MTUxMDAzMjY4MzY4MDU4MjkyMDk4OTE1MTAyMzg2OTIwMjkyODM3MTkwOTc2NDMyMTEyNTU3NDk0MTE3NDI3NjgxNDY5NzE3MzA1Nzk0NzI0ODU4NjU0ODUxODI5NzQ4NTA1NTk1MTc0NTczMzQzNjg5ODE2NTY3MzA3OTE5MTIyOTg4MjczOTQxMzU3NzI1MjUwODUzODQwOTYyODMxNDc3MTUxNDcxNTg5MjEzNzQ4MDA5NzEwMzAwMjE4MTMxNDUxNjE4NjY4MzUxNTEwNzYwNTE4MTg1NjY3ODk4NDU4NTEwNjQ3MTMxNzQwNDAwMjE4NDAyNTU2MjU5MTQ3MDI1NTIzMzgzODE1ODA3MzU1NDEzNjI5NjU0MTM2OTI="

  1. Then the system returns me the blinded signature, S'

so, S = (S' / r) % N

24818914914910373440924495286483732355034193918009758466268010322182571967031502513659086048658916042028823976943003185617946970036963881199841837196441552911705581109341260054593328566162456841895142950218979750677266736949402372670566292112370217099902986474876478008060410181643482927728261550661880472137789429832725542464999274462836317230085457545621451042531445414310707428331233889365772556917427615047373474133265125316113512167796060915505971722864776035325707620199263636430413757299372893302287102120461140519757246629337547966487338931336250142558314387457650036181961012203870138191022307166022035263943

So, I have the signature, S corresponding to M.

Now, I can send the message, M to the system along with its signature, S.

However, this is not working and I suspect that this might be due to the fact that M = integer representation of the message. When I send the integer representation of the message, the crypto system again applies (int(message.encode("hex"), 16) on it.

In which format must I send my message for signing?

Note: The attack I am using is similar to the one described here: http://the2702.com/2015/09/07/RSA-Blinding-Attack.html

Thanks.

$\endgroup$

closed as off-topic by Squeamish Ossifrage, Maarten Bodewes Mar 30 at 19:51

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Programming questions are off-topic even if you are writing or debugging cryptographic code. Unless your question is specifically about how the cryptographic algorithm, protocol or side-channel (mitigation) works, you should look into asking on Stack Overflow instead." – Squeamish Ossifrage, Maarten Bodewes
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ What is the particular RSA cryptosystem you are using? Standard RSA signatures hash the message so that shenanigans like this don't work, and it's been that way for four decades. $\endgroup$ – Squeamish Ossifrage Mar 29 at 23:27
  • $\begingroup$ How are you computing $(S' / r) \bmod n$? Note that this is not integer division; rather it's division in the ring $\mathbb Z/n\mathbb Z$. $\endgroup$ – Squeamish Ossifrage Mar 29 at 23:31
  • $\begingroup$ @SqueamishOssifrage: I have included the definition of the RSA Crypto System now in the question. Could you please check? I think Blind Attack is possible. $\endgroup$ – Neon Flash Mar 29 at 23:40
  • $\begingroup$ I am calculating (𝑆′/𝑟)mod𝑛 using the same method described in the link I shared in my question. I am using sage math. $\endgroup$ – Neon Flash Mar 29 at 23:41
  • 1
    $\begingroup$ If the code is defined in terms of bit strings, not integers, then you'd better send in a bit string. Have you tried passing in '%x' % (m_,) instead of m_, where m_ is $M'$? $\endgroup$ – Squeamish Ossifrage Mar 30 at 0:02
1
$\begingroup$

Here is what should be done:

  1. After getting the blinded message M' You should convert it back to string format. (First to hex, then string)

  2. You should convert this m' to base64 like you did.

  3. Send this base64 encoded message to client like you did.

The rest of the solution looks okay.

P.S: There is still a defect in that solution that i can not find.

$\endgroup$
  • $\begingroup$ Could you explain with an example? $\endgroup$ – Neon Flash Mar 30 at 14:09
  • $\begingroup$ I will if i can completely solve the question :) $\endgroup$ – codemonkey Mar 30 at 14:10

Not the answer you're looking for? Browse other questions tagged or ask your own question.