Posts
DEFCON 22 CTF参赛记
8月5日
感谢赞助商安全宝给我们的支持，不然我们即使有决赛入场券也难以成行。去年参加DEFCON 21 CTF时，由于航班延误到第二天，比赛前一天才到达Las Vegas，把大家都弄得疲惫不堪。吸取去年的教训，今年我们决定提前两天到。我和zTrix、cbmixx、DeadCat等同行，从北京出发，其他伙伴则从上海出发。巧的是和TombKeeper一个航班……
…ISC'14 Student Cluster Competition
本学期期末参加了ISC'14 Student Cluster Competition，6月20日到6月27日住在Leipzig Messe的Sachsenpark Hotel。
6月20日
从北京出发，在Frankfurt转机抵达Leipzig。Frughafen Leipzig竟然没免费WiFi……手机电也不足了，也不知道无线网怎么弄，给先到达的伙伴们打了三个电话，费了好大功夫坐S-bahn乘到Leipzig Messe。看到ISC'14广告牌很激动呢。
会场旁的Leipzig吉祥物，四只小狮子，好萌~
Ko-Aluru suffix array construction algorithm
Suffix array是解决string search问题的一个工具，它是一个字串所有后缀的排序。
线性时间的构建算法主要有Kärkkäinen-Sanders()、Ko-Aluru()、KSP三种，其中KSP算法使用了类似suffix tree的构建方式，Kärkkäinen-Sanders算法时间复杂度的递推式为\(T(n)=T(\frac{2n}{3})+O(n)\)，通常认为性能不如\(T(n)=T(\frac{n}{2})+O(n)\)的Ko-Aluru。
按照的注记，借鉴对LMS substring递归排序使用的方法， 对原始的Ko-Aluru算法进行改动以简化内存使用和提升性能。 我的实现在字串和suffix array外仅使用两个数组：计数排序使用的桶和一个表示L/S类型的数组， 反映了Ko-Aluru算法能达到和同等的精简内存占用。
…BCTF工作组记事
CTF夺旗赛是计算机安全竞赛的一种形式。国内这一领域当前的规模最大的赛事BCTF“百度杯”全国网络安全技术对抗赛决赛刚刚落下帷幕。作为工作组的一名成员，想分享下自己的参与经历。
…算法、FP、前端、安全、系统管理——2013年总结
二月
一日回上海，回来又吃了顿海底捞~
TUNA技术沙龙，精心准备了一天的HTML幻灯片：A Pretty Printer Library in Haskell
幻灯片里的1958、555都有所指涉，1958为诞生年份，555为马路号码。到了Algebraic data type，连同后面的Tagged Union，也都有深意。
…“1001夜”学生节线上解谜活动1001/key题解
http://www.net9.org/StudentFestival/1001/是模仿东京大学设计的海报谜题：
前几关的解法可以参考http://ppwwyyxx.com/2013/Student-Festival-Puzzle/，下面以出题人角度给出其中的1001/key的题解。
本题是一道crackme，直接运行程序会提示输入密码，如果密码输入错误就会显示meow。
RedTigers Hackit Wargame - Level 1 ~ Level 7
RedTigers Hackit是关于PHP和SQL injection的wargame。
又开始做wargame了，这次的进步是用上了HTTPie，一个类似curl的工具，但语法比后者优雅一些。
D-Link路由器后门注记
这是学习 http://www.devttys0.com/2013/10/reverse-engineering-a-d-link-backdoor 动手实践时做的一些记录。
下载 ftp://ftp.dlink.eu/Products/dir/dir-100/driver_software/DIR-100_fw_reva_113_ALL_en_20110915.zip
% binwalk -e DIR100_v5.0.0EUb3_patch02.bix
DECIMAL HEX DESCRIPTION
-------------------------------------------------------------------------------------------------------------------
4 0x4 Realtek firmware header (ROME bootloader) image type: RUN, header version: 1, created: 9/17/2011, image size: 1690484 bytes, body checksum: 0xA, header checksum: 0x67
13046 0x32F6 mcrypt 2.2 encrypted data, algorithm: blowfish-256, mode: CBC, keymode: 8bit
403343 0x6278F gzip compressed data, has CRC, extra field, last modified: Tue Jun 6 18:51:20 2028
646032 0x9DB90 Squashfs filesystem, big endian, version 2.0, size: 1041011 bytes, 528 inodes, blocksize: 65536 bytes, created: Thu Sep 15 17:11:28 2011得到squashfs文件系统9DB90.squashfs。留着这个文件不动，还要准备另一个工具。
约瑟夫问题的两个O(log n)解法
这个是学习编程时的一个耳熟能详的问题了：
n个人(编号为0,1,...,n-1)围成一个圈子，从0号开始依次报数，每数到第m个人，这个人就得自杀，之后从下个人开始继续报数，直到所有人都死亡为止。问最后一个死的人的编号(其实看到别人都死了之后最后剩下的人可以选择不自杀……)。
这个问题一般有两种问法：
- 给出自杀顺序。不少数据结构初学书都会以这个问题为习题考验读者对线性表的掌握。比较常见的解法是把所有存活的人组织成一个循环链表，这样做时间复杂度是
O(n*m)的。另外可以使用order statistic tree(支持查询第k小的元素以及询问元素的排名)优化到O(n log n)。另外有篇1983年的论文An O(n log m) Algorithm for the Josephus Problem，但可惜我没找到下载链接。 - 求出最后一个人的编号。可以套用上一种问法的解法，但另外有更加高效的解法，下文展开讨论。