چالش رمزنگاری دوم - مرد مغموم

توضیحات

توضیحات این سوال شامل دو پرونده بوده است که از اینجا و اینجا در دسترس است.

حل چالش

پرونده‌های مربوط به این سوال یک اسکریپت پایتون و پرونده‌ای به نام خروجی شامل ۴۰ خروجی از همین اسکریپت است.

گام اول

در ابتدا می‌بایست به تحلیل اسکریپت پایتون پرداخته شود؛ اگر از انتهای اسکریپت بررسی را شروع کنیم متوجه می‌شویم که ۴۰ عبارت خروجی از تابع sign حاصل شده‌اند.

این تابع در اصل سه خروجی باز می‌گرداند که به ترتیب msg یک عبارت تصادفی که در خط

msg = 'parcham{' + os.urandom(16).hex() + '}'

تولید شده، و دو متغیر r و s است.

در تابع sign دو متغیر داریم که مقدار آن‌ها را نمی‌دانیم که عبارتند از k و privkey می‌توان گفت که حمله به این آسیب‌پذیری دو مرحله‌ی مهم دارد:

۱- مقدار k کوچک است و می‌توان آن را Brute Force کرد،

۲ - از دو پیام استفاده کنیم و پس از پیدا کردن k به کلید خصوصی برسیم.

در این چالش مقدار k به شکل زیر تولید شده است:

k = getRandomRange(1, nbit << 1) * pow(pubkey, privkey, p) % q

با توجه به این‌که nbit = 1024 است و عبارت nbit << 1 در معادله‌ی محاسبه‌ی k وجود دارد نتیجه می‌گیریم این مجهول حداکثر ۲۰۴۷ بیتی است که قابل Brute Force است.

بنابراین راه‌کار به این شکل است که دو پیام را انتخاب می‌کنیم و مقدار برای متغیر k به ازای هر پیام به دست می‌آوریم. سپس از این دو متغیر استفاده می‌کنیم و مقدار privkey را محاسبه می‌کنیم.

به عبارت دیگر در معادله‌ی زیر:

s = invert(k, q) * ( int(sha512(msg.encode('utf-8')).hexdigest(), 16) + privkey * r) % q

با معلوم شدن متغیر k می‌توان معادله را به شکلی نوشت که مجهول فقط کلید خصوصی باشد (به روابط معکوس دقت کنید):

privkey = s * k - int(sha512(msg.encode('utf-8')).hexdigest(), 16) * invert(r, q) % q

از طرفی دیگر می‌دانیم:

k = getRandomRange(1, nbit << 1) * pow(pubkey, privkey, p) % q

این بدین معنی است که با توجه به ثابت بودن کلید خصوصی و عمومی می‌توان مقدار pow(pubkey, privkey, p) را ثابت در نظر گرفت و به طور مثال آن را با عبارت CONSTANT نمایش دهیم.
و به این ترتیب معادله‌ی زیر را خواهیم داشت:

s = invert(k*CONSTANT, q) * (int(sha512(msg.encode('utf-8')).hexdigest(), 16) + privkey * r) % q

حال فرض کنید که دو پیام msg1 و msg2 را انتخاب می‌کنیم که به ترتیب پیام‌های هش‌شده‌ی h1 و h2 را تولید کرده‌اند یا به عبارتی داریم:

s1 = (h1 + privkey * r1) / (k1 * CONSTANT)
s2 = (h2 + privkey * r2) / (k2 * CONSTANT)

با داشتن این دو معادله می‌توان کلید خصوصی را به شکل زیر به دست آورد:

privkey = (h2 * k1 * s1 - h1 * k2 * s2) / (r1 * k2 * s2 - r2 * k1 * s1)

در معادله‌ی بالا همه چیزی معلوم است و فقط دو مقدار k1 و k2 باید Brute Force شوند.

گام دوم

حال با داشتن فرمول بالا می‌توانیم دو پیام را انتخاب کنیم و سپس کد مربوط به معادله‌ی

privkey = (c2 * k1 * s1 - c1 * k2 * s2) / (r1 * k2 * s2 - r2 * k1 * s1)

را بنویسم تا به کلید خصوصی برسیم.

from hashlib import *
from Crypto.Util.number import *
from gmpy import *
import os


def get_privkey(params, output1, output2):
    p, q, g = params
    msg1, r1, s1 = output1
    msg2, r2, s2 = output2
    c1, c2 = int(sha512(msg1.encode('utf-8')).hexdigest(), 16), int(sha512(msg2.encode('utf-8')).hexdigest(), 16)
    for k1 in range(1, 2048):
        print (k1)
        for k2 in range(1, 2048):
            print("     " + str(k2))
            privkey = (c2*k1*s1 - c1*k2*s2) * invert(r1*k2*s2 - r2*k1*s1, q) % q
            if pubkey == pow(g, privkey, p):
                return privkey
params = (13720120737233980026253393388275239688604528015886487433172133862808134585964176349049132139807947030203736604473710157861069085195049229211510821657039309202424086955456013302798712016190287548499752812932991248826955622332263920599820305419368887976002624884744767662913519465249639520163556060643939713298329291299383336901054883883608653976863427695211464481248307457182098669082773, 164663028273407722887303895802676100265679122062654801821190290397715876206529894050630133783576409704946996218229986359153067618588744821660267612637251759574055645931459025395456937528837643153717748610117235348641301594058592909800473501082025379362616053639176925461902019874541036289560963285965705684353, 5246548401022785378246154001152832370148788305651359964449077297451901338118944636207081333286707821769200497101107864297243600942154693975143404827210845450283260496477494478520344459970759738836041573903868031391490645417656391934294409103187206597941599053194860019973402544546158682097951857779285158539512880198712837799287751142171811936716685769997343785946315765687688528883355)

output1 = ('parcham{a10328d42acb896adfe97aa8c80efd34}', 159321955414329514180576661883717418803134807667310259632761475770393507098838036363966993176546953570883577111131158848993978925663214284378250626809211544873938063758993317493470277798407403380419360589084405680285415009100350728889914745602448087999500835029777326713365958952280578857240568267475583283048, 115473677438036208317129917800903602633903024304401650044855236179430131156279614144384282927168432679905876637046578828267186574436989585753444590661301132229587077386448681089434419593442616097652837343250525080428234799707012319550293777941535808695423239367883674569654088803464873341336617339747200548659)

output2 = ('parcham{0c5ba1533b272366ff4761ed90abf52f}', 152911470268946136663925223428157312539372279108597906671153102356395668390031589631556627752614388104604169691944830802019595195049945920836111380517808682420499555600958219314093481078666714030826514371406298984955068008477934104746729533905797434893610954783411762991875436999383628193295058410086681389051, 161387336765652672653378274907104666881500726640555028036336024511137635276054466961164016505104364856508996413924523668378839848465694337793023438282952860421988858651926662712319311627102428252376343412673624161243243958008170990996033252960074132992654503410920486714272714263604632107421859576748055019240)

pubkey = 13032318698611226110871145287918234094477731805643702106677390063939081097101096389739707392896865088465381965475709618506116980176038595161678874532075246342172327944957642489966575649378588009297230856419941890658076767608297852767996051968926091916751705086927992789243730781093833201985293748181136326861560778800737357223049658157191773557546620115953903522814765852924902557756092

privkey = get_privkey(params, output1, output2)
flag = 'parcham{' + sha512(str(privkey).encode('utf-8')).hexdigest() + '}'
print(flag)

با اجرای این کد به پرچم می‌رسیم:

parcham{51c0265e03d95941e90421ecf22bf7f4b2988997db05a4426e654998853bf941be8b597e9a06613b6b0002e6d17fdcb3bcbc629db674a16638b23a982784c643}

هم‌چنین خوب است بدانیم که حلقه‌ی اول ۵۴۲ بار و حلقه‌ی دوم ۱۹۴۹ در گام آخر اجرا می‌شود و اجرای این کد در حدود ۱۰ دقیقه تا رسیدن به پرچم زمان می‌برد!