使用Trie树快速搜索顶级域名
2023-11-11 12:11:25 Author: 白帽子左一(查看原文) 阅读量:4 收藏

扫码领资料

获网安教程

免费&进群

前言

  • 在开发或者研究过程中经常会遇到域名,例如,攻击者可能会使用钓鱼攻击,欺骗用户点击看似合法但实际上是恶意的链接(最近zip域名比较火),这些链接中的域名都可能是伪造的。通过识别顶级域名,我们可以快速判断链接的真实性并减少恶意链接对系统的威胁。此外,在开发安全工具时,识别顶级域名也可以帮助我们更好地理解和分析网络流量,从而提高安全性。所以用rust基于trie树重写了https://github.com/john-kurkowski/tldextract/。

公共后缀列表

  • Mozilla维护了一个公共后缀列表,在页面中可以看到它在浏览器中的应用,还用各种编程语言的支持。得到公共后缀列表后初步对列表进行分析,可以得到列表以//开头作为注释,主要分为两类:ICANNPRIVATE,以下面分割线分割。

// ===BEGIN ICANN DOMAINS===...// ===END ICANN DOMAINS===...// ===BEGIN PRIVATE DOMAINS===...// ===END PRIVATE DOMAINS===
  • 每个后缀上面有注释标识来源和提交组织,例如:

// cn : <https://en.wikipedia.org/wiki/.cn>// Submitted by registry <[email protected]>cnac.cncom.cnedu.cngov.cnnet.cnorg.cnmil.cn公司.cn网络.cn網絡.cn
  • 还有一些特殊的后缀:

    • *开头的为泛域名,就是前面加上任意一个词,拼接起来还是算一个顶级域名,比如:asd.kawasaki.jp。

    • !开头的会被排除(为了约束上面的*),city.kawasaki.jp不算是顶级域名,www.city.kawasaki.jp提取出来的顶级域名是kawasaki.jp。

// jp geographic type names// <http://jprs.jp/doc/rule/saisoku-1.html>*.kawasaki.jp*.kitakyushu.jp*.kobe.jp*.nagoya.jp*.sapporo.jp*.sendai.jp*.yokohama.jp!city.kawasaki.jp!city.kitakyushu.jp!city.kobe.jp!city.nagoya.jp!city.sapporo.jp!city.sendai.jp!city.yokohama.jp

Trie树是什么

  • Trie树是一种数据结构,用于高效地存储和搜索字符串集合。它通常用于在字符串集合中搜索前缀或匹配项。它是一种树形结构,其中每个节点代表一个字符。通过遍历树,可以构建完整的字符串。但是在域名这里明显用单个字符不太合适,因为域名是以.分割的,使用一个字符串作为最小单元构造树比较合理一点。

  • Trie树非常适合用于搜索前缀或匹配项,因为它可以在O(k)的时间内找到一个字符串,其中k是字符串的长度。trie树在许多应用程序中都有用,包括搜索引擎,拼写检查器和数据压缩。

Trie的结构

  • 例如我将:下面四个域名转为树可以的到下面的树结构。

blog.kali-team.cnwww.gd.gov.cnwww.zj.gov.cnmirrors.tuna.tsinghua.edu.cn
  • 根节点没有任何词,每个节点有一个词,加粗的表示可以为顶级域名

将公共后缀列表构造到Trie树

  • 了解了公共后缀列表和Trie树后,以cn为例子生成Trie树

cnac.cncom.cnedu.cngov.cnnet.cnorg.cnmil.cn公司.cn网络.cn網絡.cn
  • 生成Trie树为:

flowchart TDRoot --> cn[<b>cn</b>]cn --> edu[<b>edu</b>]cn --> gov[<b>gov</b>]cn --> com[<b>com</b>]cn --> ac[<b>ac</b>]cn --> net[<b>net</b>]cn --> org[<b>org</b>]cn --> mil[<b>mil</b>]cn --> 公司[<b>公司</b>]cn --> 网络[<b>网络</b>]cn --> 網絡[<b>網絡</b>]

代码实现

  • 实现一个嵌套的树结构,node为下一层的叶子节点,end表示当前这层是否可以为顶级域名。

/// TLDTrieTree#[derive(Debug, Clone, Serialize, Deserialize)]pub struct TLDTrieTree {    // 节点    node: HashMap<String, TLDTrieTree>,    // 是否可以为顶级域名    end: bool,}

插入数据

  • 代码实现:

impl TLDTrieTree {  /// Insert TLDTrieTree Construction Data  #[inline]  fn insert(&mut self, keys: Vec<&str>) {    let keys_len = keys.len();    let mut current_node = &mut self.node;    for (index, mut key) in keys.clone().into_iter().enumerate() {      let mut is_exclude = false;      // 以!开头的需要排除掉      if index == keys_len - 1 && key.starts_with('!') {        key = &key[1..];        is_exclude = true;      }      // 获取下一个节点,没有就插入默认节点      let next_node = current_node.entry(key.to_string()).or_insert(TLDTrieTree {        node: Default::default(),        end: false,      });      // 当这是最后一个节点,设置可以为顶级域名      if !is_exclude && (index == keys_len - 1)                // 最后一个为*的,节点可以为顶级域名                || (key != "*" && index == keys_len - 2 && keys[index + 1] == "*")      {        next_node.end = true;      }      current_node = &mut next_node.node;    }  }}
  • 以上面cn的edu.cn为例子插入Trie数,先将域名以.分割,再倒序得到列表[cn, edu],按顺序全部插入得到。

{  "node": {    "cn": {      "node": {        "mil": {          "node": {},          "end": true        },        "com": {          "node": {},          "end": true        },        "xn--od0alg": {          "node": {},          "end": true        },        "xn--io0a7i": {          "node": {},          "end": true        },        "gov": {          "node": {},          "end": true        },        "xn--55qx5d": {          "node": {},          "end": true        },        "net": {          "node": {},          "end": true        },        "ac": {          "node": {},          "end": true        },        "edu": {          "node": {},          "end": true        },        "org": {          "node": {},          "end": true        }      },      "end": true    }  },  "end": false}
  • 将下面后缀构造为Trie数后得到

*.ck!www.ck

ck同级的end为true,表示可以为顶级域名,但是www前面有!,所以end为false。

{  "node": {    "ck": {      "node": {        "*": {          "node": {},          "end": true        },        "www": {          "node": {},          "end": false        }      },      "end": true    }  },  "end": false}

查询数据

  • 代码实现:

impl TLDTrieTree {/// Search tree, return the maximum path searched  #[inline]  fn search(&self, keys: &[String]) -> Vec<Suffix> {    let mut suffix_list = Vec::new();    let mut current_node = &self.node;    for key in keys.iter() {      match current_node.get(key) {        Some(next_node) => {          suffix_list.push(Suffix {            suffix: key.to_string(),            end: next_node.end,          });          current_node = &next_node.node;        }        None => {          if let Some(next_node) = current_node.get("*") {            suffix_list.push(Suffix {              suffix: key.to_string(),              end: next_node.end,            });          }          break;        }      }    }    suffix_list  }}
  • 查询时将域名以.分割后倒序逐级从右边往左边搜索,不管end是否为true,直到找不到最后一个词,进入match中的None分支,再判断节点是否为存在*,如果存在将返回的节点的end设置为true,得到一个带有节点和是否可以为顶级域名属性的列表。

  • 例如:www.asd.city.kawasaki.jp以.分割后倒序得到[jp, kawasaki, city, asd, www],直到搜索到city,找不到下一层了,返回后缀列表:

    [Suffix { suffix"jp"endtrue }, Suffix { suffix"kawasaki"endtrue }, Suffix { suffix"city"endfalse }]
  • 然后将这个列表pop数据,遇到第一个end为true的Suffix,当前Suffix和剩下的组成顶级域名:也就是:kawasaki.jp

ExtractResult {        subdomain: Some(            "www.asd",        ),        domain: Some(            "city",        ),        suffix: Some(            "kawasaki.jp",        ),        registered_domain: Some(            "city.kawasaki.jp",        ),    },

结论

在本文中,我们介绍了如何使用Trie树来快速查找顶级域名。这种方法可以帮助我们快速识别恶意链接,并提高我们的安全性。我们还介绍了Trie树的基本概念和实现细节。希望这篇文章对你有所帮助!

参考

  • https://publicsuffix.org/learn/

  • https://github.com/emo-cat/tldextract-rs

  • https://github.com/elliotwutingfeng/go-fasttld

来源:https://blog.kali-team.cn/Trie-d96e76d5509047b2ad2c3d9504e28db1

声明:⽂中所涉及的技术、思路和⼯具仅供以安全为⽬的的学习交流使⽤,任何⼈不得将其⽤于⾮法⽤途以及盈利等⽬的,否则后果⾃⾏承担。所有渗透都需获取授权

@
学习更多渗透技能!体验靶场实战练习

hack视频资料及工具

(部分展示)

往期推荐

【精选】SRC快速入门+上分小秘籍+实战指南

爬取免费代理,拥有自己的代理池

漏洞挖掘|密码找回中的套路

渗透测试岗位面试题(重点:渗透思路)

漏洞挖掘 | 通用型漏洞挖掘思路技巧

干货|列了几种均能过安全狗的方法!

一名大学生的黑客成长史到入狱的自述

攻防演练|红队手段之将蓝队逼到关站!

巧用FOFA挖到你的第一个漏洞

看到这里了,点个“赞”、“再看”吧

文章来源: http://mp.weixin.qq.com/s?__biz=MzI4NTcxMjQ1MA==&mid=2247602643&idx=1&sn=9a9dda746e2376a01bb926de0f723939&chksm=ebeb18fedc9c91e8b6258b24bb5555ad2919de167a349677e02ac7909a685217bfdf94e16bd6&scene=0&xtrack=1#rd
如有侵权请联系:admin#unsafe.sh