→ Nuit du Hack (NdH2k11) - crypto300

| No TrackBacks
Видим протокол: клиент цепляется к серверу, отправляет публичный ключ, сервер отправляет свой, на основе ключей генерируется сессионный ключ. Если публичный ключ разрешен на сервере, то получим флаг. Задача - иметь возможность представиться клиентом с разрешенным публичным ключом. Т.к. в генерации сессионного ключа используется приватный ключ, то для заданного публичного ключа попробуем найти приватный. В конструкторе класса BraidKey видим, что перемешиваются только 2 часть ключа длиной N инициализированного цифрами 0..N-1.
self.privkey = Braid(N)
if client:
    self.privkey.shuffle(offset=N/2)
Видим, что длина приватного ключа клиента 22 байта, а первые 11 байт всегда статичны. Для того чтобы найти вторую часть ключа, переберем 11!(~40M) вариантов перестановок. Leet More описали этот метод как неэффективный(en), но столь большое количество времени необходимо лишь из-за неоптимальной процедуры комбинации ключей в исходном коде. Развернутый код(thanks to bma!):
% time python b.py
Found!!! [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 15, 18, 17, 14, 13, 21, 20, 16, 19, 11, 12]
41.922u 0.000s 0:42.14 99.4%    1261+1261k 0+0io 0pf+0w
Исходник:
#!/usr/local/bin/python
# -*- coding: UTF-8 -*-
from sys import exit
from itertools import permutations

#def gen_pub(priv_key, key, len_key):
#    # reverse
#    privr_key = range(len_key)
#    pub_key = range(len_key)
#    temp0 = range(len_key)
#    for i in xrange(len_key):
#        privr_key[priv_key[i]] = i
#    # combine part one
#    for i in xrange(len_key):
#        temp0[i] = privr_key[key[i]]
#    # combine part two
#    for i in xrange(len_key):
#        pub_key[i] = temp0[priv_key[i]]
#    return pub_key


def main():
    key = [13, 18, 20, 4, 1, 8, 6, 15, 5, 12, 14, 2, 7, 3, \
            10, 21, 16, 9, 0, 11, 19, 17]
    npub = [15, 12, 17, 4, 1, 8, 6, 11, 5, 21, 14, 16, 0, 9, \
            10, 3, 13, 19, 18, 20, 2, 7]
    bpkey = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    spkey = [11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21]
    len_key = len(key)
    privr_key = range(len_key)
    pub_key = range(len_key)
    temp0 = range(len_key)

    iter = 0

    for p in permutations(spkey):
        iter += 1
        if iter % 100000 == 0:
             print iter

        pkey = bpkey + list(p)

        for i in xrange(len_key):
            privr_key[pkey[i]] = i
        # combine part one
        for i in xrange(len_key):
            temp0[i] = privr_key[key[i]]
        # combine part two
        for i in xrange(len_key):
            pub_key[i] = temp0[pkey[i]]

        if pub_key == npub:
            print "Found!!!", pkey
            return 0
    return 0

if __name__ == '__main__':
    try:
        import psyco
        psyco.full()
    except ImportError:
        print 'Psyco not installed, the program will just run slower'
    exit(main())

No TrackBacks

TrackBack URL: http://smokedchicken.org/m/mt-tb.cgi/49

About this Entry

This page contains a single entry by kyprizel published on April 4, 2011 7:56 PM.

ruCTF-2011 Quals - Forensic 300 was the previous entry in this blog.

Nuit Du Hack (NdH2k11) - RCE100 is the next entry in this blog.

Find recent content on the main index or look in the archives to find all content.