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$
  • 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 '19 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 '19 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 '19 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 '19 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 '19 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 '19 at 14:09
  • $\begingroup$ I will if i can completely solve the question :) $\endgroup$ – codemonkey Mar 30 '19 at 14:10

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