V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
爱意满满的作品展示区。
typcn
V2EX  ›  分享创造

根据 Hashcash 做的 反机器人 CC 攻击算法

  •  
  •   typcn ·
    typcn · 2014-12-24 04:20:28 +08:00 · 6736 次点击
    这是一个创建于 3616 天前的主题,其中的信息可能已经有所发展或是发生改变。

    我想了想还是单独贴出来让更多的人看到,大家一起看一下可行性以及是否存在问题。

    体验可以到这里 http://blog.eqoe.cn/ 在右边进行搜索

    请求

    我们可以看到点击搜索的时候客户端发送了 3 次请求。

    • 第一次:提交 Get 请求,服务器返回 error=1 表示该关键词没有被内存缓存,需要 Hash 验证
    • 第二次:提交 Get 请求,获得一个 TOKEN,然后客户端在此 TOKEN 后增加数字,直到这个字符串 SHA1 值的前4位为0(服务器需要保证 TOKEN 与每个 IP 地址对应)

    客户端计算 Hash 示例代码

    var tk = "获得的TOKEN内容";
    var str = 10000;
    var lasthash = "";
    while(lasthash.indexOf("0000") != 0){ //如果 lasthash 前4位不是0则持续循环
        str++;
        lasthash = sha1(tk+str.toString()); //把 Token 和 数字拼接起来
    }; //经过多次测试 PC端计算大约需要1-3秒 移动端需要2-5秒
    
    • 第三次:我们将 tk str 以及 要搜索的内容 POST 到服务器上,服务器识别 TOKEN 与 IP 地址相符,并且与 str 合并之后的 sha1 结果前4位为0,服务器返回搜索结果,否则提示客户端进行重试。

    如果需要的话你可以对我的 blog 进行压力测试,别打太狠就行。。。

    假设使用 C 语言制作客户端计算一个 Hash 需要 2 秒,攻击者使用 16 核电脑和若干代理IP,那么你的服务器每秒只会收到 8 个以下的请求,这种算法应对一般的攻击应该可以无压力的防住吧?

    51 条回复    2014-12-27 07:54:57 +08:00
    ihacku
        1
    ihacku  
       2014-12-24 07:01:07 +08:00
    typcn
        2
    typcn  
    OP
       2014-12-24 07:27:20 +08:00
    @ihacku 思路都一样吧,具体实现稍有不同。在计算的时候浏览器会假死,用户打字会超难受,而且没法根据输入内容动态生成key。

    这个明显有问题,在计算出key之后,使用相同的时间和key可以提交很多次,经过超时时间后再之重新计算,要是针对的话基本跟没有一样。
    zeraba
        3
    zeraba  
       2014-12-24 07:52:11 +08:00
    貌似还有通过解析器进行判断的 nginx+ lua
    RIcter
        4
    RIcter  
       2014-12-24 08:02:10 +08:00 via iPad
    这种算法是不是需要在后端计算出lasthash?
    如果我大量POST前四位为0但是后面随机的hash,后端会不会因为大量的计算而卡死?
    RIcter
        5
    RIcter  
       2014-12-24 08:04:57 +08:00 via iPad
    又看了一遍…后端没验证hash是否正确,只验证了前四位是不是0?
    这样不还是可以bypass么…
    typcn
        6
    typcn  
    OP
       2014-12-24 08:05:56 +08:00
    @RIcter 先校验 TOKEN 是否符合,才计算 lasthash 的,一个 IP 地址同一时间只能拥有一个 TOKEN,在发放 TOKEN 的程序做一些限制就好了。

    另外做 hash 运算不算什么吧? PHP 的 SESSION 也需要计算 hash 啊。
    typcn
        7
    typcn  
    OP
       2014-12-24 08:06:30 +08:00
    @RIcter 这个肯定是要先校验是否符合再校验是否为0的 我写的有些不严谨
    sanddudu
        8
    sanddudu  
       2014-12-24 08:08:58 +08:00 via iPhone
    @RIcter 如果完全验证,用户数又多,就会被拖死
    wy315700
        9
    wy315700  
       2014-12-24 08:09:37 +08:00 via Android
    hash前四位是0 不就是挖坑的思路吗
    typcn
        10
    typcn  
    OP
       2014-12-24 08:17:35 +08:00
    @RIcter 如果严格一点的话, POST 的时候不需要上传 token,后端自动根据用户的 IP 地址到数据库/内存缓存中取 token,然后拼接 token 和 用户计算出的数字,验证 lasthash 。 如果验证成功删除这个 IP 地址对应的 token 。
    a2z
        11
    a2z  
       2014-12-24 08:18:31 +08:00
    @RIcter


    计算完POST过去的时候内容是:
    TK:4ceda3e028287b9b6d1e1a2ba904e4b4d75761af
    ua:20389

    两个拼起来hash的确是00008e2609258df65582eea4e51c91259f3b780d

    但是这个hash并没有发送到服务器。
    服务器只需要把TK和ua拼起来计算下sha1是否前四位是0000就行了,也就是说客户端要计算几万次sha1,服务器只用计算1次。

    有种挖比特币的感觉。
    typcn
        12
    typcn  
    OP
       2014-12-24 08:19:12 +08:00
    @a2z 是的 就是根据比特币的算法想出来的
    RIcter
        13
    RIcter  
       2014-12-24 08:32:24 +08:00 via iPad
    @a2z souka,才反应过来T^T
    a2z
        14
    a2z  
       2014-12-24 08:32:52 +08:00
    @typcn

    token根据ip计算的话有点多此一举的感觉,直接限制每个ip的访问次数不就行了,和v2ex一样。
    typcn
        15
    typcn  
    OP
       2014-12-24 08:36:36 +08:00
    @a2z 这个倒是。
    我开启 IP 验证是因为怕碰到代理狂魔。vps 上开着 Minecraft 服务器,各种数据库,剩的资源很少,太容易被打挂,每个月已经 700 多了,0 收入,实在不想加钱了。
    typcn
        16
    typcn  
    OP
       2014-12-24 08:38:11 +08:00
    @a2z 又不想限制访问次数,怕误伤
    rrfeng
        17
    rrfeng  
       2014-12-24 08:38:39 +08:00
    我感觉到一种很容易针对这种策略的攻击的可能性
    比普通的 CC 可能还要高效……
    kslr
        18
    kslr  
       2014-12-24 08:40:36 +08:00
    就是个令牌桶算法++
    typcn
        19
    typcn  
    OP
       2014-12-24 08:43:44 +08:00
    @rrfeng 说来听听?
    a2z
        20
    a2z  
       2014-12-24 08:46:54 +08:00
    @rrfeng
    @typcn

    我也想到了 :D
    procen424
        21
    procen424  
       2014-12-24 08:53:44 +08:00 via Android
    楼主找个强一点的工作量证明算法吧
    SHA1用显卡或FPGA跑 会把CPU虐哭的
    而且都是现成的代码
    icedx
        22
    icedx  
       2014-12-24 09:37:05 +08:00
    博客是WP?
    lijun20020229
        23
    lijun20020229  
       2014-12-24 09:51:38 +08:00
    比特币的工作量证明据说早就有了,1996年Adam Back开发的“Hashcash"用来反垃圾邮件。
    typcn
        24
    typcn  
    OP
       2014-12-24 09:53:58 +08:00
    @icedx 不是WP 是 node.js 自己写的
    binux
        25
    binux  
       2014-12-24 09:57:46 +08:00
    我直接压 sha1 就完了,按照几万次 sha1 就需要1秒计算,只要我每秒请求超过几万次,你就挂了。
    typcn
        26
    typcn  
    OP
       2014-12-24 10:00:34 +08:00
    @binux 防火墙吃干饭啊。。。你1秒还没请求10次就被封IP了,而且在服务端也可以加验证,验证失败X次进行拦截,X个同段IP失败拦截IP段。
    binux
        27
    binux  
       2014-12-24 10:30:19 +08:00
    @typcn 谁说我就一个IP了
    icedx
        28
    icedx  
       2014-12-24 10:34:27 +08:00
    @typcn 窝巢菊...
    typcn
        29
    typcn  
    OP
       2014-12-24 10:39:38 +08:00
    @binux 真要有超多IP,打静态文件也打挂了,别说仅仅是 SHA1。 还有,执行一次 sha1 比执行一次搜索耗费的资源小了无数倍
    geew
        30
    geew  
       2014-12-24 10:46:54 +08:00
    就用户体验来说 我觉得这种方法不好 用更简单的频率限制不挺好的么 过高的频率直接打入黑名单 限制一定的时间再开放
    binux
        31
    binux  
       2014-12-24 10:50:56 +08:00
    @typcn 比静态资源高。
    typcn
        32
    typcn  
    OP
       2014-12-24 10:53:50 +08:00
    @geew 简单的频率限制,去网上抓一堆垃圾代理,分分钟拥有几千 IP
    nilai
        33
    nilai  
       2014-12-24 10:58:17 +08:00
    @typcn 有一个问题想问你, 你一个长40 位的字符串 再后面拼接了一个 1--10000的随机数 再进行sha1加密, 生成的这1万个hash中。 一定会有一个hash的前4位为0么?
    typcn
        34
    typcn  
    OP
       2014-12-24 10:58:22 +08:00
    @binux 静态资源也会发生散列哈希运算,磁盘读取之后,计算服务器上文件的 ETag ,将 header 等信息发送给用户。
    大部分静态资源服务器有这个。
    typcn
        35
    typcn  
    OP
       2014-12-24 10:59:29 +08:00
    @nilai 随机数是无限+1的,经过我的测试一般会在3秒之内得到结果
    hellogbk
        36
    hellogbk  
       2014-12-24 11:00:02 +08:00
    感觉客户端会卡死呢。
    binux
        37
    binux  
       2014-12-24 11:04:30 +08:00
    @typcn 你的静态资源没有缓存吗,每次都重新计算?etag 计算量比 sha1 要小。
    typcn
        38
    typcn  
    OP
       2014-12-24 11:17:21 +08:00
    @hellogbk 浏览器会暂时无响应,但是等三秒比输入验证码好多了。

    @binux 不重新计算如何知道文件变化了没有?我知道计算量小,我只是提供这一种方法,至于到底用在哪个地方合适与否就是使用者考虑的了。。比如我用在了搜索上,执行 sha1 就比执行搜索快多了,很显然可以大大减轻压力。
    binux
        39
    binux  
       2014-12-24 11:19:40 +08:00
    其实这个是有效的,攻击找的是系统中最消耗资源的请求。
    而将搜索用 sha1 验证,降低了搜索的请求消耗。
    其实也不一定要用 sha1 ,关键是拉大客户端和服务器端的计算压力差,比如这里是 0xffff : 1。换成 md5 也是一样的,服务器还算得快一点。
    binux
        40
    binux  
       2014-12-24 11:20:04 +08:00
    @typcn 实际上 nginx 是 mtime + size
    nilai
        41
    nilai  
       2014-12-24 11:30:52 +08:00
    @typcn 另同一局域网下都是同一个外网IP。何解
    typcn
        42
    typcn  
    OP
       2014-12-24 11:32:08 +08:00
    @nilai 不可能两个人同时在搜吧?
    lecher
        43
    lecher  
       2014-12-24 12:35:45 +08:00
    这个仅仅就是防单机单ip发起的cc。
    但是就像binux大神说的,单机多ip代理无限构造0000+随即字符串,根本不用算正确的请求,就可以打死了。
    和打有验证码的一个道理,不用突破到数据库处理层面,直接多ip代理打服务器,服务器光是计算hash和缓存hash的结果就要算到死了。

    也不一定是打搜索页面,比如打注册账号验证用户名是否有效和邮箱是否有效的请求,这个一般网站为了一致性,缓存找不到的一定回去数据库查的,而校验用户名有效性这个请求,一般都没有做校验就直接打到数据库了。多ip代理打过去,服务器的压力要比单机的压力大一些。
    millken
        44
    millken  
       2014-12-24 12:51:41 +08:00
    方法很新颖,我去尝试下。

    真正的防御应该是应用层验证(js,flash,captcha),提交验证未通过的ip到防火墙。
    lqs
        45
    lqs  
       2014-12-24 14:02:54 +08:00
    把while循环改成for一个固定次数加setTimeout 1ms,就不会让浏览器卡住了
    nilai
        46
    nilai  
       2014-12-24 14:36:09 +08:00
    @typcn 完全有可能, 现在的移动网络是一块区域内的用户用几个公网IP。
    zhicheng
        47
    zhicheng  
       2014-12-24 23:25:22 +08:00
    hashcash 必然是有效的,要不然 bitcoin 早就被攻击死了。
    LS们讨论的大量IP+0000随机数的不太现实。。。
    sha1 大部分语言 100K/s hash 轻轻松松的。但你不太可能有那么多 IP 地址。或者说,如果真有这么大的资源,也无所谓攻击这个地址了,静态页面都能打死了,光流量服务器都撑不住。完全不在一个讨论层次上。
    小规模的单服务器网站,直接在存 session 在页面渲染出挑战值就可以。
    大规模的多服务器网站,可以用 hmac(ip + timestamp) 做挑战值,验证写到 nginx 里,性能损失可以忽略。
    kocd
        48
    kocd  
       2014-12-26 16:04:22 +08:00
    我事先得知一个前4位是0的一条tk_after,返回给你tk和tk-tk_after。。。
    是不是能不停的攻击你。。。
    typcn
        49
    typcn  
    OP
       2014-12-26 16:59:28 +08:00
    @kocd token使用完自动回收啊
    kocd
        50
    kocd  
       2014-12-27 07:05:08 +08:00
    @typcn 你的服务器端好像只判断(tk+一个数字的hash)前4位是0,我每次请求你都给我一个tk,我只要返回tk和我已知的随便一个tk_after的tk_after-tk对吧,没做过网站,单纯从逻辑考虑的。
    typcn
        51
    typcn  
    OP
       2014-12-27 07:54:57 +08:00
    @kocd TK 在用过一次后就立马被销毁的,下次用就提示失效。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2010 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 00:47 · PVG 08:47 · LAX 16:47 · JFK 19:47
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.