RuCTF Quals 2012 write-up

Hint: flag is not a frag: once you've got it, you can get one more...

Собственно, результаты:
http://blackbox.sibears.ru/contests/ructf-2012-quals/

Пожалуй, опишу одно задание по крипто =)

Цитата:
Есть вещи, которые нельзя купить, для всего остального есть BlackBank.

Адрес банка - http://[service ip address]/bank/, магазина - http://[service ip address]/store/
В /store/ видим 2 дешёвых товара (стоимостью 25 и 54) и товар "blackbox" стоимостью 1234865.
Для покупки нужно ввести имя и Sign.
В /bank/ видим кнопку "CREATE NEW ACCOUNT" и форму "Sign check", в которой нужно ввести имя и сумму покупки, и система выдаст подпись (Sign), необходимую для покупки.

Создаём аккаунт, получаем ответ:
Код:
Congrats! Please remember your account name:njkwWYGyJmGNjyB. And our gift to new customer is 999 moneys.
Очевидно, нужно купить blackbox, но у нас только 999 денег.
Пробуем ввести имя и левую подпись, например, 1. Получаем:
Код:
Don't try to cheat!!! Sign verification failed, using RSA modulus 133217581764083237802578095397754145844934112338171714542798194258566746579620699547057987645627407202684311393658799426651995853247022120770692531558065830303114976418533026429041354607519840759280278019057406139394689822787488480072988842712625752979961583262441923687694000185457751381455883960947753506297
Ага! Значит проверка подписи идёт при помощи RSA.
Проверяем догадку, введя в форму Sign check (/bank/) имя и сумму 1.
Код:
Success! Here's your signed check for account njkwWYGyJmGNjyB:
Amount -- 1
Sign--1
Да, значит сумма действительно шифруется алгоритмом RSA ( (m ^ e) % n ).
Понятно, что публичная экспонента генерируется на основе имени, и она очень большая.

Посмотрим на цену "blackbox": 1234865.
Факторизуем: 1234865 = 5 * 491 * 503. Замечаем, что 5 + 491 + 503 = 999, ровно столько денег, сколько у нас есть!

Значит мы можем получить подписи для сумм 5, 491, 503, т.е. значения:
5^e % n, 491^e % n, 503^e %n.
Далее перемножим их модулю n и получим искомое значение 1234865^e % n.
Модуль n нам выдан сервером в ошибке (см. выше).

Итак, вытаскиваем подписи из /bank/ для 5, 491 и 503 (зарегистрировав свежее имя, gIXYItEGCNhjVcg).
Числа получаются очень большие, можно загнать их в Python:

Код:
print (46455340164023484440625561346065754771374071482759026242049050347311017680185693634406503885558185754909221781580122086570442531294322089044553133063892157018020005489313990621772767283561087604169134166653265049672093461437714561786825261396401185945679047270793060295328556906044575002156062623718646074236*24586696628972454649964454739647701922057658592422453858971603679124036755054419350582461489736051832898513036927841513758984942262240944108748719753737241142503109194553687787827957717187262915825945326491388177007282911607022665274502221212829101211325410836953900767185978222063867508219196279506787979491*58318822056768562683725220013005939120152488035205781894017665476319621484224492208647716668439644245655743118867851161426125001253065920153491699594575081764792536072100045716436177589867729500475113273066508562606106751305646522014577975415369622092165918618625569847363378230498195373432781876662607043167) % 133217581764083237802578095397754145844934112338171714542798194258566746579620699547057987645627407202684311393658799426651995853247022120770692531558065830303114976418533026429041354607519840759280278019057406139394689822787488480072988842712625752979961583262441923687694000185457751381455883960947753506297
Код:
beched@linuxoid:/var/www/CTF/ructf12$ python bank.py
5615010225733588547496660600994794460777940605563969220133753166162430825908002831110081667764607140363302359140673381358223046088065395050974405754076603099340961632272490897435259937555041687277000279882624446613040889990189311469676379385066090209745766596976561244295953740925234973354134822588184357737
Покупаем blackbox, имеем:

Код:
Your flag (we're not responsible for its usefullness): _pR1C3L3s5

P.S. Что-то длинно получилось, можно было в 3 строчки =)