пятница, 17 января 2014 г.

CSAW 2013: CSAWpad (Crypto100)

Из задания дан только исходный код:
import os
from hashlib import sha512
from binascii import hexlify

#generates s box and sinverse box, called f and g respectively, using 
#sha 512 as a deterministic random number generator
def genTables(seed="Well one day i'll be a big boy just like manhell"):
    fSub={}
    gSub={}
    i=0
    prng=sha512()
    prng.update(seed)
    seed=prng.digest()
    for el in xrange(256):
        cSeed=""
        for x in xrange(4):
            cSeed+=prng.digest()
            prng.update(str(x))
        prng.update(cSeed)
        fCharSub=[0]*256
        gCharSub=[0]*256
        unused=range(256)
        for toUpdate in xrange(256):
            i+=1
            curInd=ord(cSeed[toUpdate])%len(unused)
            toDo=unused[curInd]
            del unused[curInd]
            fSub[(el,toUpdate)]=toDo
            gSub[(el,toDo )]=toUpdate
    return fSub,gSub
f,g=genTables()


def encrypt(pad, ptext):
    assert(len(ptext)<=len(pad))#if pad < plaintext bail
    ctext = []
    if type(ptext)==type(""):
        ptext=map(ord,ptext)
    if type(pad)==type(""):
        pad=map(ord,pad)
    for padByte,ptextByte in zip(pad,ptext):
        ctext.append(f[padByte,ptextByte])
    return  "".join(map(chr,ctext))
def decrypt(pad, ciphertext):
    assert(len(ciphertext)<=len(pad))#if pad < ciphertext bail
    ptext = []
    if type(ciphertext)==type(""):
        ciphertext=map(ord,ciphertext)
    if type(pad)==type(""):
        pad=map(ord,pad)
    for padByte,ctextByte in zip(pad,ciphertext):
        ptext.append(g[padByte,ctextByte])

    return "".join(map(chr,ptext))


def sanity():
    for x in xrange(256):
        for y in xrange(256):
            enc=f[(x,y)]
            dec=g[(x,enc)]
            assert(y==dec)
    for x in xrange(1000):
        toTest=os.urandom(1000)
        pad=os.urandom(1000)
        enc=encrypt(pad,toTest)
        dec=decrypt(pad,enc)
        assert(dec==toTest)
#sanity()
'''
Recovered texts, hex encoded
 '794d630169441dbdb788337d40fe245daa63c30e6c80151d4b055c18499a8ac3e5f3b3a8752e95cb36a90f477eb8d7aa7809427dde0f00dc11ab1f78cdf64da55cb75924a2b837d7a239639d89fe2b7bc1415f3542dba748dd40',
 '14a60bb3afbca7da0e8e337de5a3a47ae763a20e8e18695f39450353a2c6a26a6d8635694cbdc34b7d1a543af546b94b6671e67d0c5a8b64db12fe32e275',
 '250d83a7ed103faaca9d786f23a82e8e4473a5938eabd9bd03c3393b812643ea5df835b14c8e5a4b36cdcfd210a82e2c3c71d27d3c47091bdb391f2952b261fde94a4b23238137a4897d1631b4e18d63',
 '68a90beb191f13b621747ab46321a491e71c536b71800b8f5f08996bb433838fe56587f171a759cf1c160b4733a3465f5509ad7d1a89d4b41f631f3c600347a8762141095dad3714027dfc7c894d69fd896b810313259b1a0e941ecb43d6ae1857a465b4ddcdf102b7297763acb0281144b0598c326e871c3a1ad047ad4fea2093a1b734d589b8998175b3',
 '0fc304048469137d0e2f3a71885a5a78e749145510cf2d56157939548bfd5dd7e59dcebc75b678cfeac4cf408fce5dda32c9bfcbfd578bdcb801df32ebf64da365df4b285d5068975137990134bd69991695989b322b0849',
 '254c0bb31453badaca9d060ce5faa45fa66378a6716915473579d3743e315dbedf4d8cf78b93c3267d579247e32c8c7cd3e71e7dda6138a2ab015166fa03f2ce6ab74b89ce561eb16a65990189e169f1c457d9af622ba119a66acedb108fae18825bf3efc0428b9dae250791cb0ea018966e257d601a87f9914d646026eeab5c45cbaedd27e4c47643ab4e25193aa64f79',
 '41cd1c01c62883b2ca71e671dce57e5f96b1610e29507b6c03c38211653284576d4d8cdc967764147d1a0578102cb05f32a73065f11009041fa3cc5f60b24d8c7098598627df37322f814525966acabc99be5303c2322b43ecf358ac8b8541bd82214d1cc042cac3869c54e2964fa376229c2563ba3fd03e2d4d4d441721c60b6d817e034965be28b7d463cf2b97baebfe2729ed2aa41ffe',
 '68c50bd5197bfdbdfa887883783d2455a673a685436915bd72d1af74dffdd2b89df335daee93c36d5f57e147e9a35913d3b3bf33' 

Код имеет функцию генерации матрицы подстановок, шифрования, дешифрования.
Внизу даны 8 шифротекстов, которые нужно расшифровать.
Попробуем понять, как происходит шифрование:
1.    genTables(seed="..") генерирует матрицу и ее обратную матрицу.
2.    Берет 1 байт случайного ключа и 1 байт открытых данных.
3.    Конвертирует эти байт в числовые значения (‘A’ = 65, ‘6’ = 54).
4.    Берем результат шифрования из элемента матрицы по координатам, составленных из этих 2 байт (1 – строка, 2 – столбец).
5.    Значение элемента матрицы принимаем как байт шифротекста.
6.    Повторим эти шаги для всех байт.

Дешифрование аналогично т.к. используются обратные матрицы.
Матрица имеет размер 256*256. Заполняется псевдослучайным генератором.
Требуется расшифровать строки, которые явно зашифрованы одинаковым ключом.
Т.к. мы не знаем значения ключа, мы пробуем перебрать все возможные значения.

Пример для 1 символа:
Переберем 256 вариантов PAD:
1)    Зная первый байт первого шифротекста, матрицу и PAD – получим первый байт первого открытого текста.
2)    Если байт читаемый (a-z,A-Z,0-9,пробел,запятая,точка…) – помечаем его как кандидата.
3)    Повторяем 2 шаг для первого байта каждого шифротекста.
4)    Если для каждого шифротекста байт получился читаемый, значит PAD верный.

Вероятность, что байт будет читаемый 70 из 256.
Для 8 шифротекстов: (70.0/256)^8 * 100% = 0.003%
Поэтому, 2 разных PAD мы вряд-ли получим.

import string
strings = [ '794d630169441dbdb788337d40fe245daa63c30e6c80151d4b055c18499a8ac3e5f3b3a8752e95cb36a90f477eb8d7aa7809427dde0f00dc11ab1f78cdf64da55cb75924a2b837d7a239639d89fe2b7bc1415f3542dba748dd40',
 '14a60bb3afbca7da0e8e337de5a3a47ae763a20e8e18695f39450353a2c6a26a6d8635694cbdc34b7d1a543af546b94b6671e67d0c5a8b64db12fe32e275',
 '250d83a7ed103faaca9d786f23a82e8e4473a5938eabd9bd03c3393b812643ea5df835b14c8e5a4b36cdcfd210a82e2c3c71d27d3c47091bdb391f2952b261fde94a4b23238137a4897d1631b4e18d63',
 '68a90beb191f13b621747ab46321a491e71c536b71800b8f5f08996bb433838fe56587f171a759cf1c160b4733a3465f5509ad7d1a89d4b41f631f3c600347a8762141095dad3714027dfc7c894d69fd896b810313259b1a0e941ecb43d6ae1857a465b4ddcdf102b7297763acb0281144b0598c326e871c3a1ad047ad4fea2093a1b734d589b8998175b3',
 '0fc304048469137d0e2f3a71885a5a78e749145510cf2d56157939548bfd5dd7e59dcebc75b678cfeac4cf408fce5dda32c9bfcbfd578bdcb801df32ebf64da365df4b285d5068975137990134bd69991695989b322b0849',
 '254c0bb31453badaca9d060ce5faa45fa66378a6716915473579d3743e315dbedf4d8cf78b93c3267d579247e32c8c7cd3e71e7dda6138a2ab015166fa03f2ce6ab74b89ce561eb16a65990189e169f1c457d9af622ba119a66acedb108fae18825bf3efc0428b9dae250791cb0ea018966e257d601a87f9914d646026eeab5c45cbaedd27e4c47643ab4e25193aa64f79',
 '41cd1c01c62883b2ca71e671dce57e5f96b1610e29507b6c03c38211653284576d4d8cdc967764147d1a0578102cb05f32a73065f11009041fa3cc5f60b24d8c7098598627df37322f814525966acabc99be5303c2322b43ecf358ac8b8541bd82214d1cc042cac3869c54e2964fa376229c2563ba3fd03e2d4d4d441721c60b6d817e034965be28b7d463cf2b97baebfe2729ed2aa41ffe',
 '68c50bd5197bfdbdfa887883783d2455a673a685436915bd72d1af74dffdd2b89df335daee93c36d5f57e147e9a35913d3b3bf33']
printable = string.printable[:-5]

strings = map(lambda s: s.decode("hex"), strings)
maxl = max(map(len, strings))
pad = [0,]*maxl
# pos: (string, char)
guess = {0:(1,"G"),
	14: (0, " "),
	16: (0, "e"),
	17: (0, "t"),
	20: (0, "e"),
	22: (0, " "),
	24: (0, "t"),
	34: (0, "n"),
	38: (0, "e"),
	39: (0, "n"),
	43: (0, " "),
	46: (0, " "),
	51: (0, " ")}

for pos in range(maxl):
	possible = []
	for i in range(256):
		ok = True
		x = []
		for string in strings:
			if len(string) <= pos:
				continue
			c = chr(g[i,ord(string[pos])])
			if c not in printable:
				ok = False
				break
			x.append(c)
		if ok and len(x) > 0:
			possible.append((i,x))
	if len(possible) == 1:
		pad[pos] = possible[0][0]
	elif pad[pos] == 0:
		gotone = False
		if pos in guess:
			for padval, solutions in possible:
				if guess[pos][1] in solutions[guess[pos][0]]:
					pad[pos] = padval
					gotone = True
					break
			
		if not gotone:
			pad[pos] = possible[0][0]

for string in strings:
	print decrypt(pad, string)


Читаем расшифрованные тексты и видим в одном: key for you is {And yes the nsa can read this to} Вводим ключ «And yes the nsa can read this to» и получаем 100 баллов.

Многопользовательский OTR

Задумался на днях, как же можно создать групповой чат с функцией PFS. Вариант нашелся на странице википедии об OTR. Оказывается, что есть проект "multi-party OTR", который реализует такую фишку.
http://www.cs.ucdavis.edu/~hchen/paper/ccs09.pdf

четверг, 9 января 2014 г.

CSAW 2013: Life (Misc 300)

Из описания к заданию дана только команда: nc 128.238.66.216 45678
По названию Life понимаем, что нас ожидает игра Конвея (http://en.wikipedia.org/wiki/Conways_Game_of_Life)

Правила
Место действия этой игры — «вселенная» — это размеченная на клетки поверхность или плоскость — безграничная, ограниченная, или замкнутая (в пределе — бесконечная плоскость).
Каждая клетка на этой поверхности может находиться в двух состояниях: быть «живой» или быть «мёртвой» (пустой). Клетка имеет восемь соседей (окружающих клеток).
Распределение живых клеток в начале игры называется первым поколением. Каждое следующее поколение рассчитывается на основе предыдущего по таким правилам:
в пустой (мёртвой) клетке, рядом с которой ровно три живые клетки, зарождается жизнь;
если у живой клетки есть две или три живые соседки, то эта клетка продолжает жить; в противном случае (если соседей меньше двух или больше трёх) клетка умирает («от одиночества» или «от перенаселённости»).
Игра прекращается, если на поле не останется ни одной «живой» клетки, если при очередном шаге ни одна из клеток не меняет своего состояния (складывается стабильная конфигурация) или если конфигурация на очередном шаге в точности (без сдвигов и поворотов) повторит себя же на одном из более ранних шагов (складывается периодическая конфигурация).
Эти простые правила приводят к огромному разнообразию форм, которые могут возникнуть в игре.
Игрок не принимает прямого участия в игре, а лишь расставляет или генерирует начальную конфигурацию «живых» клеток, которые затем взаимодействуют согласно правилам уже без его участия (он является наблюдателем).
Описание
Для начала, напишем скрипт на языке Python, который будет подключаться к серверу и получать 2 параметра (поле и количество ходов).
Дальше от нас требуется вернуть серверу то поле, которое появится после N ходов.

Например, сервер возвращает нам следующий текст, значит, мы должны ответить ему, переслав поле, которое получится из исходного спустя 25 ходов.

##### Round 1: 25 Generations #####
#######################
#           *         #
#*         *          #
# *                 * #
# * **        *    ***#
# **  *      **       #
#**    *       *      #
# *             *     #
#      *        *     #
#     *    * *   *    #
#  * *                #
# *              *    #
#     *           *   #
#       *             #
#           **        #
#      *              #
#                     #
#                *    #
#         **          #
#        *     *     *#
#       *    *  **  * #
#######################


Код эксплойта
#coding: utf-8

"""
    Conway's Game of Life implementation with console interface
    Author: Antonio Ribeiro - alvesjunior.antonio@gmail.com
    license: Do What You Want to
"""

from time import sleep
from random import randint
import socks
import re

def get_neighbours(p, i, j, w, h):
    # возвращаем ответ для (i,j) исходя из соседей по правилам
    n = 0
    for a in [-1, 0, 1]:
        for b in [-1, 0, 1]:
            if a+i < 0 or b+j < 0 or a+i >= h or b+j >= w or a == b == 0:
                continue 
            if p[i+a][j+b]:
                n += 1
    
    if p[i][j] and n < 2 or n > 3:
        return 0
    elif n == 3:
        return 1
    else:
        return p[i][j]


def step(p,w,h):
    # делаем 1 ход по правилам игры
    l = len(p)
    new_p = []          # новый массив (поле)
    for i in range(h):
        new_p.append([])
        for j in range(w):
            new_p[i].append(p[i][j])

                        # заполняем новый по правилам
    for i in range(h):
        for j in range(w): 
            new_p[i][j] = get_neighbours(p, i, j, w, h)

    return new_p

def set_board(socket):
    # получаем от сервера ответ и заполняем доску (массив p),
    # количество ходов (res), ширину (w) и высоту (h) поля
    round = socket.recv(1024)
    r = re.compile('(\d+)')
    if len(r.findall(round)) < 2:
        print socket.recv(10240)
    else:
        res = int(r.findall(round)[1])  # res - количество ходов
    a = socket.recv(10240)
    l = 0
    for c in a:
        if c!='#':
            break
        l += 1
    s = ""
    w = l - 2               # ширина
    h = len(a) / (l+1) - 2  # высота
    #print w,h
    
    p = []                  # массив поля
    for i in range(1,h + 1):
        le = []
        for j in range(w):
            if (a[i*(w+3)+j+1]=='*'):
                le.append(1)
            else:
                le.append(0)
        p.append(le)
    
    return res,p,w,h

def show(p,w,h):    
    # выводит доску в требуемом формате
    f = ""
    for j in range(w+2):
        f +='#'
    f += '\n'
    for i in range(h):
        f += '#'
        for j in range(w):
            if p[i][j]==1:
                f += "*"
            else:
                f += " "
        f += "#\n"
    for j in range(w+2):
        f += '#'
    f += '\n'
    return f
    
if __name__ == '__main__':
    socket = socks.socksocket() 
    socket.connect(('128.238.66.216' , 45678))  # соединяемся с сервером
    w = 0
    h = 0
    for i in range(101):    # 100 раз с нас требуют пройти игру
        res,p,w,h = set_board(socket)   # получаем параметры карты и расстановку
        for i in range(res):            # ходим N раз
            p = step(p,w,h)             # 1 ход
        socket.send(show(p,w,h))        # отправляем результат
    socket.close()
С помощью догадки, понимаем, что от нас требуют пройти игру аж 100 раз. После 100 прохождения, сервер вернул строку: Congratulations!You made it!Here's your prize: key{that comp sci assignment was useful after all} Ключ «that comp sci assignment was useful after all» принес 300 баллов.

пятница, 3 января 2014 г.

Стеганосистема

Вот и подвели итоги нашего эпического соревнования между командами КБ и ПМ.

Есть у нас такой предмет - "стеганография". Чтобы получить зачет, нужно было в группах разработать новую стеганосистему, либо улучшить существующую. Мы разделились на группы по 3 человека и начали работать.

У нас получилось 5 команд, у ПМ - 3.
1) Стеганосистема "Мыщъ" - сетевая стеганография, основанная на временных задержках между пакетами в локальной сети. Прикольно смотрится, но фраза про "30 бит в минуту" нас всех очень позабавила.
2) Наша стеганосистема "Вектор" - суть в том, чтобы прятать сообщения в векторном формате SVG. Прятали мы очень "оригинально", с помощью новейшего алгоритма LSD - это как LSB только decimal)) Несмотря на то, что все очень просто, мы обратили внимание на сложные проблемы этого формата и навернули много сложных "фишек", которые сделали задумку небанальной.
3) Стеганосистема "Sec&Ran" - система с принципом недоказуемости. По сути, они передают секретное сообщение в рандомизированных данных протокола SSL. Для этого переписали клиент и сервер openSSL. Получилось круто, но передает только 28 байт за пакет.
4) Стеганосистема "StegFat" - суть в том, что секретное сообщение составляется из расположения блоков в Fat таблице. Забавная идея, но информации мало.
5) Стеганосистема "Порт". Не очень стегано. Шлют на разные порты сообщения, в зависимости от порта формируется значащий бит.

Шоколадная медалька досталась нам :)