Leetcode 24. Swap Nodes in Pairs(详细图解一看就会)

题目内容

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list’s nodes, only nodes itself may be changed.
大概意思是说每两个节点为一组交换位置。只使用常量空间,不能修改链表的值,只能修改链表的指针

解法(迭代)

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode *dummy = new ListNode(-1), *pre = dummy;
        dummy->next = head;
        while (pre->next && pre->next->next) {
            ListNode *t = pre->next->next;
            pre->next->next = t->next;
            t->next = pre->next;
            pre->next = t;
            pre = t->next;
        }
        return dummy->next;
    }
};

该代码已经是非常经典了,但乍一看还是有点晕,我们来对代码进行一步步的解析。

可以看出该代码实现了两个相邻节点的交换,最后并将pre指向了下一个节点,然后继续该过程

递归解法

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode *t = head->next;
        head->next = swapPairs(head->next->next);
        t->next = head;
        return t;
    }
}; 

这可能是最详细的解析HTTP走私攻击的文章

前言

HTTP Desync Attacks也就是HTTP走私攻击,是我见到的比较有趣的一种攻击方式,这里来对这种漏洞进行介绍。

TL;DR

HTTP走私攻击利用了HTTP协议本身的问题:HTTP中存在两种方式来指定请求的结束位置。因此,相同的HTTP请求,不同的服务器可能会产生不同的处理结果,这样就产生了了安全风险。

具体分析

HTTP/1.1

在HTTP协议中,存在两种Header来指定请求的结尾,分别是Content-Length以及Transfer-Encoding。Content-Length用来指明发送给接收方的消息主体的大小,后面的数字就代表了这个消息的大小;Transfer-Encoding指明了将实体安全传递给用户所采用的编码形式,常见的值有chunked,compress,deflate,gzip等,其中chunk表示消息体使用分块编码(Chunked Encode),也就是整个请求会分块发送,由多个消息组成,整个消息体以大小为0的块结束,也就是说解析遇到0数据块就结束,因此带来了一种新的判断结尾的方式。
这两个Header都源于RFC 7230也就是HTTP/1.1,在之前的版本中HTTP协议规定浏览器与服务器只保持短暂的连接,服务器完成请求即断开连接。显然,这种方式是有问题的,因此HTTP 1.1支持持久连接,在一个TCP连接上可以传送多个HTTP请求和响应。同时这个规范也带来了Content-Length以及Transfer-Encoding这两个Header,虽然协议明确说明以Transfer-Encoding为准,但是仍然存在很多服务器没有完全遵守规范,从而导致不同的服务器对结尾的判断不同,也就导致了这种漏洞。

CDN和代理

其实该漏洞早在2005年就有人提出,不过随着内容分发网络(CDN)的兴起,CDN本质上是一个反向代理,缓存了大量的静态网站数据,如果用户访问静态数据,直接从代理服务器中就可以获取到,不用再从源站所在服务器获取,从而提高访问速度并且降低网络拥塞,一个典型的CDN结构如下图:

可以看出,CDN的出现,使得大量用户会先访问CDN服务器,CDN服务器会判断是否有动态请求或者没有命中缓存的情况,如果存在,CDN会先代替用户请求,最后将封装好的请求返回给用户。可以看到,如果请求一个动态内容如查询等,CDN此时相当于一个代理,会讲用户的请求发送给服务器,如果这两者没有正确处理结尾,就会导致HTTP走私的出现。当下CDN的大量使用使得这种漏洞的重新兴起。

分类

我们可以将这种情况抽象为前端和后端两种服务器,根据前后服务器处理方式的差异,HTTP走私共分为三种:
– CLTE:前端服务器使用 Content-Length 头,后端服务器使用 Transfer-Encoding 头
– TECL:前端服务器使用 Transfer-Encoding 标头,后端服务器使用 Content-Length 标头。
– TETE:前端和后端服务器都支持 Transfer-Encoding 标头,但是可以通过以某种方式来诱导其中一个服务器不处理它。

CLTE

对于CLTE类型,如果构造如下请求,由于pipeline特性,会导致下一个请求的开头多了个PP

POST / HTTP/1.1\r\n
Host: example.com\r\n
...
Connection: keep-alive\r\n
Content-Length: 6\r\n
Transfer-Encoding: chunked\r\n
\r\n
0\r\n
\r\n
pp

前端由于是从Content-Length获取结尾,因此会讲全部作为一个包发送,但后端会在0处截断,从而导致认为pp是下一个包的开始,导致下一个请求的开头多了个pp

CL/CL

CLCL是构造一个包含两个Content-Length的包,根据规范此时应当返回400错误,但如果没有正确遵守规范,且前端按不同的CL进行处理,这可能会导致HTTP走私,例子如下:

POST / HTTP/1.1\r\n
Host: example.com\r\n
Content-Length: 8\r\n
Content-Length: 7\r\n
12345\r\n
a

该例子的过程和上一节类似

TE/TE

该种方式是前后端服务器都支持并且默认使用te来处理,使用某种方式导致一端不识别te块来达到,cl-te或者te-cl的方式。例子如下:

POST / HTTP/1.1\r\n
Host: example.com\r\n
Content-length: 4\r\n
Transfer-Encoding: chunked\r\n
Transfer-encoding: cow\r\n
\r\n
5c\r\n
aPOST / HTTP/1.1\r\n
Content-Type: application/x-www-form-urlencoded\r\n
Content-Length: 15\r\n
\r\n
x=1\r\n
0\r\n
\r\n

可以看到前后的Transfer-Encoding,E的大小写不同,因此可能导致识别的不同。

TE/CL

TE-CL指前端服务器处理 Transfer-Encoding 请求头,而后端服务器处理 Content-Length 请求头。

POST / HTTP/1.1\r\n
Host: example.com\r\n
...
Content-Length: 4\r\n
Transfer-Encoding: chunked\r\n
\r\n
12\r\n
aPOST / HTTP/1.1\r\n
\r\n
0\r\n
\r\n

前端全读,后端只读一部分

DEFCON CTF QUAL 2020 uploooadit

该题给了两个接口,一个是POST /文件/,该接口用于上传文件,会返回文件的id。另一个是GET /files/<guid>,该接口用于请求保存的文件。
同时我们可以看到前端服务器是一个haproxy 1.9.10,后端是Flask。
通过测试发现存在CL/TE类型的HTTP Desync,因此构造

这个的解析流程是,haproxy看到了187,便将整个请求发送给了后端,而后端只看TE,因此在0处截断,并将后面的内容看作第二个包,后面的部分只有CL,因此后端会继续读内容知道达到385长度为止,如果此时有别人传文件,文件内容会被我们的2aaaaa-aaaaa-aaaaa-aaaaaaaaaa读取到。
这个题目是存在一个不断上传flag的机器人,因此我们只要一直发送这样的包,读取我们上传的文件,就有可能获取到机器人上传的内容,最后我们GET /files/2aaaaaaa-aaaa-aaaa-aaaa-aaaaaaaaaaaa,读取到了机器人上传的flag

总结

HTTP走私是源于服务端没有正确按照HTTP规范行事从而导致的漏洞,因此解决方案也很简单,按照HTTP/1.1规范正确处理请求,或者尽量避免服用连接就可以解决该漏洞。