Secc

31.01.2014 01:13, by Triff

Category:

crypto

Event:

PHDays Quals IV

Задание:

This key verification scheme is built on elliptic crypto, bet this points are

impossible.

nc 195.133.87.171 5555

password: secch4l*

Так же нам даны исходники этой схемы

Решение:

Открываем файл task.py и видим:

def main():
    print "Auth:"
 
    auth = raw_input()
 
    if hashlib.sha1(auth).hexdigest() != "375d5c01ca1b8c3863024d10aac7713472eb5033": # secch4l*
        print "nope"
        return
 
    prefix = os.urandom(8)
 
    print "Proof of work, please"
    print "Prefix is (hexed) ", prefix.encode("hex")
     
    test = raw_input().decode("hex")
     
    if not test.startswith(prefix) or len(test) > 16:
        print "nope"
        return
     
    h = hashlib.sha1(test).hexdigest()
     
    if not h.startswith("000000"):
        print "nope"
        return
     
    goflag()

Первым делом надо пройти защиту от брутфорса - сервер пришлет строчку из 8 байт и мы дожны подобрать еще не более 7 байт так, чтобы хеш от всей строки начинался с 6 нулей. Это можно легко сделать на питоне, например вот так:

#!/usr/bin/env python
from socket import create_connection
from time import sleep
import string
import hashlib
 
def findproof(prefix):
	max_len = 256**7
	 
	for i in xrange(0, max_len,1):
		if i % 100000 == 0:
			print i
		ft = hex(i)
		ft = ft[2:]
		if len(ft) % 2 != 0:
			ft = "0" + ft
		 
		footer = ft.decode("hex")
		header = prefix.decode("hex")
		 
		test = header + footer
		h = hashlib.sha1(test).hexdigest()
		if h.startswith("000000"):
			return test.encode("hex")
	print "Bad luck =("
 
conn = create_connection(('195.133.87.171', 5555));
conn.recv(1024);
conn.recv(1024);
conn.send("secch4l*\n");
sleep(0.5);
 
res = conn.recv(1024);
prefix = res.split()[-1]
 
s = findproof(prefix);
conn.send(s + "\n")
sleep(3);
 
print conn.recv(1024)
print conn.recv(1024)
print conn.recv(1024)
print conn.recv(1024)

Единственная проблема - этот скрипт будет достаточно долго искать подходящий хеш (минуты 2-3, может дольше), но в итоге сервер ответит что-то такое:

EC PASSWORD CHECK

R = (32009104608775058819477673947201651309102020463966621153833804363847565759174L, 54506028353458734953786314314179377292053505167654412444092825486798869159312L)

SHARED SECRET = R ^ PASSWORD

ENCRYPTED MESSAGE: 4c106c176590bc2f26c822ba7c164dc8d04567c15511b2fbd1

В файле task.py мы видим:

def goflag():
	print "EC PASSWORD CHECK"
	 
	r = random.randint(31337, 1 << 250)
	R = p256.power(G, r)
	 
	print "R =", R
	 
	print "SHARED SECRET = R ^ PASSWORD"
	 
	S = p256.power(R, PASSWORD)
	 
	key = p256.derive(S)
	 
	cipher = encrypt(FLAG, key)
	print "ENCRYPTED MESSAGE:", cipher.encode("hex")
 
def encrypt(msg, key):
	iv = os.urandom(8)
	stream = hashlib.sha256(iv + key).digest()
	stream = hashlib.sha256(stream + iv + key).digest()
	cipher = iv + xor(msg, stream)
	return cipher

А значит зашифрованное сообщение и есть флаг, осталось только расшифровать =)

Шифрования происходит простым xor'ом с гаммой, которая получается хешированием ключа и iv. Вектор инициализации содержится в шифртексте, значит нужно найти ключ, который получается с помощью функции derive() из известной нам точки R, возведенной в степень PASSWORD, который нам не известен.

Настало время открыть файл ecc.py. Там находится реализация эллиптической криптографии, на первый взгляд - хорошая: функции add, power выглядят правильно, кривая взята NIST'овская. Зато функция derive() вызывает подозрения:

def derive(self, p):
	return hashlib.sha256(str((p[0] << 10) / p[1])).digest()

Выражение str((p[0] << 10) / p[1]) возможно будет иметь очень плохое распределение, проверим это, добавив в derive строчку print str((p[0] << 10) / p[1]) и запустив такой скрипт:

#!/usr/bin/env python
#-*- coding:utf-8 -*-
 
import os
import random
import hashlib
 
from ecc import p256, G, s2n, xor
 
PASSWORD = s2n("adadsd")
FLAG = "111"
 
for i in xrange(0, 10000, 1):
	r = random.randint(31337, 1 << 250)
	R = p256.power(G, r)
	S = p256.power(R, PASSWORD)
	key = p256.derive(S)

В консоли мы увидим что-то вроде такого:

Видно, что числа редко превосходят даже 10000, а значит можно просто перебрать все варианты и попробовать расшифровать сообщение на каждом из них, проверяя, что в результате расшифрования получилась строка, содержащая только печатные символы. Например вот так:

#!/usr/bin/env python
#-*- coding:utf-8 -*-
 
import os
import random
import hashlib
import string
 
def xor(a, b):
	return "".join([chr(ord(a[i]) ^ ord(b[i % len(b)])) for i in xrange(len(a))])
 
encoded_msg = '4c106c176590bc2f26c822ba7c164dc8d04567c15511b2fbd1'
decoded_msg = encoded_msg.decode("hex")
 
def main():
	for i in xrange(0, 1000000,1):
		key = hashlib.sha256(str(i)).digest()
	 
		result = decrypt(decoded_msg,key)
		if all(c in string.printable for c in result):
			print result
			break
	 
def decrypt(msg, key):
	iv = msg[0:8]
	stream = hashlib.sha256(iv + key).digest()
	stream = hashlib.sha256(stream + iv + key).digest()
	cipher = xor(msg[8:], stream)
	return cipher
	 
if __name__ == '__main__':
	main()

В результате получаем:

ecc_is_too_s3cure

Флаг: ecc_is_too_s3cure

Скрипт, который выполняет всю атаку:

#!/usr/bin/env python
from socket import create_connection
from time import sleep
import string
import hashlib
 
def xor(a, b):
	return "".join([chr(ord(a[i]) ^ ord(b[i % len(b)])) for i in xrange(len(a))])
 
def findproof(prefix):
	max_len = 256*256*256*256*256*256*256
 
	for i in xrange(0, max_len,1):
		if i % 100000 == 0:
			print i
		ft = hex(i)
		ft = ft[2:]
		if len(ft) % 2 != 0:
			ft = "0" + ft
		 
		footer = ft.decode("hex")
		header = prefix.decode("hex")
		 
		test = header + footer
		h = hashlib.sha1(test).hexdigest()
		if h.startswith("000000"):
			return test.encode("hex")
	print "Bad luck =("
 
def decrypt(msg, key):
	iv = msg[0:8]
	stream = hashlib.sha256(iv + key).digest()
	stream = hashlib.sha256(stream + iv + key).digest()
	cipher = xor(msg[8:], stream)
	return cipher
 
conn = create_connection(('195.133.87.171', 5555));
conn.recv(1024);
conn.recv(1024);
conn.send("secch4l*\n");
sleep(0.5);
 
res = conn.recv(1024);
prefix = res.split()[-1]
 
s = findproof(prefix);
conn.send(s + "\n")
sleep(3);
 
res = conn.recv(1024)
 
encoded_msg = res.split()[-1]
decoded_msg = encoded_msg.decode("hex")
 
for i in xrange(0, 1000000,1):
	key = hashlib.sha256(str(i)).digest()
 
	result = decrypt(decoded_msg,key)
	if all(c in string.printable for c in result):
		print result
		break

latest Running Sneakers | Nike

Last events