雅礼中学计算机协会
CSA

洋葱路由相关

发表时间:2019-08-27 14:09

洋葱路由

洋葱路由(英语:Onion routing)为一种在电脑网络上匿名沟通的技术。在洋葱路由的网络中,消息一层一层的加密包装成像洋葱一样的数据包,并经由一系列被称作洋葱路由器的网络节点发送,每经过一个洋葱路由器会将数据包的最外层解密,直至目的地时将最后一层解密,目的地因而能获得原始消息。而因为透过这一系列的加密包装,每一个网络节点(包含目的地)都只能知道上一个节点的位置,但无法知道整个发送路径以及原发送者的地址。 [1]
中文名
洋葱路由
外文名
OnionRouting
原    理
Chaum的混合瀑布原理
目    标
保护信息发送者和接受者的隐私
学    科
密码学
领    域
密码学

发明与实现

编辑
1990年代中期,美国海军研究实验室的研究员保罗‧塞维利亚森(Paul Syverson)、麦可‧里德和大卫‧戈尔德施拉格(David Goldschlag)为了保护美国在线情报系统而开发了洋葱路由。其后国防高等研究计划署接手该项目继续开发,并在1998年获得海军的专利。2002年计算机科学家罗杰‧丁高戴恩(Roger Dingledine)和尼克‧马修森(Nick Mathewson)加入了塞维利亚森的项目,并开始开发Tor;Tor为“洋葱路由项目”(The Onion Routing project)的头字语,该项目后来成为规模最大的洋葱路由实现并广为人知。之后美国海军研究实验室将Tor以自由软件授权的方式公开了源代码,丁高戴恩、马修森以及其他五位成员在2006年成立了名为“The Tor Project”的非营利组织,并获得包含电子前哨基金会在内的几个组织的财政资助。 [2]

数据结构

编辑
一个在洋葱路由网络中传递的数据包例子。发送者首先将数据包发送给路由器A,解密了蓝色一层,并发现要传给B,而数据包发送至B时又解密了绿色一层,同理再传给C,而C在解密了红色一层后得到原始要发送的消息并将之传给目的地。
被称作洋葱路由的原因在于消息一层一层的加密包装成被称作洋葱数据包的数据结构,层数取决于到目的地中间会经过的节点数,每经过一个节点层会将数据包的最外层解密,因此任一个节点都无法同时知晓这个消息最初与最终的目的地,使发送者达到匿名的效果。
数据包的创建与发送
为了发送洋葱数据包,发送消息者会从“目录节点”(directory node)提供的列表中选取一些节点,并以这些规划出一条被称作“链”(chain)或“线路”(circuit)的发送路径,这条路径将为传输数据包所用。为了确保发送者的匿名性,任一节点都无法知道在链中自己的前一个节点是发送者还是链上的另一节点;同理,任一节点也无法知道在链中自己的下一节点是目的地还是链上另一节点。只有链上的最后一个节点知道自己是链上最终节点,该节点被称作“出口节点”(exit node)。
洋葱路由网络使用非对称加密,发送者从目录节点获得一把公开密钥,用之将要发送的消息加密并发送给链上的第一个节点,该节点又被称作入口节点(entry node);其后与之创建连接和共享密钥。创建连接后发送者就可以通过这条连接发送加密过的消息至链上的第二个节点,该消息将只有第二个节点可以解密;当第二个节点收到此消息后,便会与前一个节点也就是入口节点同样的创建连接,使发送者的加密连接延伸到它,但第二个节点并不晓得前一个节点在链中的身份。之后按照同样原理,发送者通过入口节点和第二个节点的这条加密连接将只有第三个节点能解密的消息发送给第三个节点,第三节点同样的与第二个节点创建连接;借由重复相同的步骤,发送者能产生一条越来越长的连接,但在性能上仍有限制。
当链上的连接都创建后,发送者就可以透过其发送数据并保持匿名性。当目的地回送数据时,链上的节点会透过同一条连接将数据回传,且一样对数据层层加密,但加密的顺序与发送者完全相反;原发送者收到目的地回传的数据时,将仅剩最内一层加密,此时对其解密就可拿到目的地回送的消息。

弱点

编辑

计时分析

传统互联网不被认为具有匿名性的一个理由为互联网服务供应商具有纪录和追踪各电脑间的连接能力;例如当有人访问一个特定网站时,往来的信息内容如密码等,虽然能透过像是HTTPS等加密连接方式保护让其他人无法得知内容,但是连接本身却仍会有纪录,包含何时创建连接,多少数据量被发送等。洋葱路由虽然能创建并隐藏两电脑之间的连接,使两者之间并无一个可分辨的直接连接,但仍会有上述的连接纪录问题。流量分析可借由搜索连接纪录的连接时间和数据传输量来试图判别潜在的一对发送者与接收者;例如当有人发送51KB的数据到一个未知的电脑,三秒后另一未知的电脑发送51KB的数据给一个特定的网站,则可以推断此人可能与该网站曾创建连接。此外还有一些原因可以让流量分析更加有效,包含节点的损坏或离开网络,以及当链已经因为定期重建而改变,但有些链上节点却仍在追踪此前创建的会话等。 [3]
大蒜路由是洋葱路由的一种变体,其结合了I2P网络并将多份消息加密打包在一起,使其更难被攻击者以流量分析的方式破解。

出口节点漏洞

虽然消息在洋葱路由网络中被层层加密,但是在出口节点时,该节点会把最后一层解密并将原始消息传给接收者;因此若出口节点遭到攻击或是受控制,则原始的消息将会被截取。瑞典研究员丹‧伊格史塔德(瑞典语:Dan Egersta)曾用此方式获得了超过100封寄给外国大使馆电子邮件密码。出口节点漏洞的原理与未加密无线网络很类似,后者为用户将未加密的数据在无线网络上传送时可能中途被其他人截走;这两种问题都可以透过端对端加密连接如SSLHTTPS等方式解决。


暗网

暗网(不可见网,隐藏网)是指那些存储在网络数据库里、但不能通过超链接访问而需要通过动态网页技术访问的资源集合,不属于那些可以被标准搜索引擎索引的表面网络。
暗网是深网(Deep Web)的一个子集,属于深网的一小部分。
中文名
暗网
外文名
Deep Web,Hidden Web
又    称
黑暗网络、影子网
特    点
无法使用普通的搜索方式找到


定义

暗网(不可见网,隐藏网)是指那些储存在网络数据库里、不能通过超链接访问而需要通过动态网页技术访问的资源集合,不属于那些可以被标准搜索引擎索引的表面网络。
迈克尔·伯格曼将当今互联网上的搜索服务比喻为像在地球的海洋表面的拉起一个大网的搜索,大量的表面信息固然可以通过这种方式被查找得到,可是还有相当大量的信息由于隐藏在深处而被搜索引擎错失掉。绝大部分这些隐藏的信息是须通过动态请求产生的网页信息,而标准的搜索引擎却无法对其进行查找。传统的搜索引擎“看”不到,也获取不了这些存在于暗网的内容,除非通过特定的搜查这些页面才会动态产生。于是相对的,暗网就隐藏了起来。

来源和现状

编辑
Hidden Web最初由Dr.Jill Ellsworth于1994年提出,指那些没有被任何搜索引擎索引注册的网站:
“这些网站可能已经被合理地设计出来了,但是他们却没有被任何搜索引擎编列索引,以至于事实上没有人能找到他们。我可以这样对这些不可见的网站说,你们是隐藏了的。”
另外早期使用“不可见网络”这一术语,是一家叫做“个人图书馆软件”公司的布鲁斯·芒特(产品开发总监)和马修·B·科尔(首席执行官和创建人)发明的。当他们公司在1996年12月推出和发行的一款软件时,他们对暗网工具的有过这样的一番描述:
不可见网络这一术语其实并不准确,它描述的只是那些在暗网中,可被搜索的数据库不被标准搜索引擎索引和查询的内容,而对于知道如何进入访问这些内容的人来说,它们又是相当可见的。
第一次使用暗网这一特定术语,是2001年伯格曼的研究当中。
从信息量来讲,与能够索引的数据相比,“暗网”更是要庞大得多。根据Bright Planet公司此前发布的一个名为《The Deep Web-Surfacing The Hidden Value》(深层次网络,隐藏的价值)白皮书中提供的数据,“暗网”包含100亿个不重复的表单,其包含的信息量是“非暗网”的40倍,有效高质内容总量至少是后者的1000倍到2000倍。更让人无所适从的是,Bright Planet发现,无数网站越来越像孤立的系统,似乎没有打算与别的网站共享信息,如此一来,“暗网”已经成为互联网新信息增长的最大来源,也就是说,互联网正在变得“越来越暗”。
当然,所谓“暗网”,并不是真正的“不可见”,对于知道如何访问这些内容的人来说,它们无疑是可见的。2001年,Christ Sherman、GaryPrice对Hidden Web定义为:虽然通过互联网可以获取,但普通搜索引擎由于受技术限制而不能或不作索引的那些文本页、文件或其它通常是高质量、权威的信息。根据对HiddenWeb的调查文献得到了如下有意义的发现:
  1. Hidden Web大约有307,000个站点,450,000个后台数据库和1,258,000个查询接口。它仍在迅速增长,从2000年到2004年,它增长了3~7倍。
  2. Hidden Web内容分布于多种不同的主题领域,电子商务是主要的驱动力量,但非商业领域相对占更大比重。
  3. 当今的爬虫并非完全爬行不到Hidden Web后台数据库内,一些主要的搜索引擎已经覆盖Hidden Web大约三分之一的内容。然而,在覆盖率上当前搜索引擎存在技术上的本质缺陷。
  4. Hidden Web中的后台数据库大多是结构化的,其中结构化的是非结构化的3.4倍之多。
  5. 虽然一些Hidden Web目录服务已经开始索引Web数据库,但是它们的覆盖率比较小,仅为0.2%~15.6%。
  6. Web数据库往往位于站点浅层,多达94%的Web数据库可以在站点前3层发现。

分类

编辑
它分为两种:
一种是技术的原因,很多网站本身不规范、或者说互联网本身缺少统一规则,导致了搜索引擎的爬虫无法识别这些网站内容并抓取,这不是搜索引擎自身就能解决的问题,而是有赖整个网络结构的规范化,百度的“阿拉丁计划”、谷歌的“云计算”就是要从根本解决这一问题。
另一个原因则是很多网站根本就不愿意被搜索引擎抓取,比如考虑到版权保护内容、个人隐私内容等等,这更不是搜索引擎能解决的问题了。如果他们能被搜索引擎抓取到,就属于违法了。
数据显示,能够搜索到的数据仅占全部信息量的千分之二。而对暗网的发掘能扩大搜索数据库,使人们能够在搜索引擎上搜索到更多的网页、信息。
几乎任何有抱负的通用搜索引擎都有一个共同的梦想:整合人类所有信息,并让大家用最便捷的方式各取所需。
对此,百度说:“让人们最便捷地获取信息,找到所求”;谷歌说:“整合全球信息,使人人皆可访问并从中受益”。这两者表达的实际上是同一个愿景。
然而,这注定是一项不可能完成的任务。据科学家估测,人类信息大概只有0.2%实现了web化,并且这个比例很可能在持续降低。更甚的是,即便在已经Web化的信息中,搜索引擎的蜘蛛能抓取到的和不能抓取到的比例为1:500。

处理

编辑
暗网spider结构图暗网spider结构图
为实现自动获取Hidden Web页面的任务,此爬虫必须能自动寻找表单,填写表单,然后获取和识别结果页面。HiddenWeb爬虫系统结构如图所示
1.寻找Hidden Web入口页面
Web上存在多种多样的表单,同时表单上含有各种各样的元素,如单选按钮、下拉列表框、文本框等,有些还是用户自定义的,因此处理所有的表单是比较困难的。为此,需要先解析HTML页面,获取要研究的表单类型,同时从中抽取有用信息。本文要研究的是不含或含有少量的文本框元素,其它类型元素都具有默认值的表单。这很容易通过解析HTML表单来完成,如可以使用标记序列树或DOM(文档对象模型)来过滤出要研究的表单。
2.自动提交表单
当搜索表单提供了每一表单元素所有可能的值时,直接的方法是对具有少量的文本框元素使用空串作为默认值,穷尽表单其他元素所有可能值的组合来填写表单,获取后台数据库全部的数据。此方法存在两个问题:①处理过程非常耗时;②在穷尽所有可能值组合之前,也许已经获取了所有或大部分的后台数据库数据,从而出现了重复提交;③多个字段组合可能存在语义上的冲突。Hidden Web爬虫设计的目标是使用最少的资源(如提交时间或次数等)获取特定Hidden Web站点内最大量的数据,然而不能保证对所有表单使用有限次的提交可以获取后台数据库的全部数据,因此有必要再次发送查询来确定是否已获取了全部数据。本文提出一种两阶段采样爬行策略以充分获取Hidden Web数据,它分为如下两个步骤:
  1. 首先使用表单提供的默认值来提交;
  2. 然后对表单元素值组合进行采样以确定默认值提交是否返回了后台数据库的所有数据,若返回了后台数据库所有或大部分数据则可以结束提交过程。否则,在爬虫所具有资源限制范围内穷尽所有可能值的组合。
如果C次采样提交每次都产生了新的记录,则穷尽表单元素其它可能值组合来提交表单,直到满足特定的结束条件。然而在继续提交表单前,先要估计完成这样的操作所需的最大剩余时间和用于存储所有结果记录所需的最大空间。可以指定如下几个参数来完成此阶段的任务:最大查询提交次数、最大存储空间和最大剩余时间等。
可以通过叠加每次查询所返回的数据量来估计所需最大存储空间S。类似地可以估计最大剩余时间T。
在穷尽阶段,可以使用几个参数阀值来提前结束提交过程。包括:
  • 获取Web数据库数据的百分比:通过估计Web数据库百分比以确定获取了多少数据以后可以结束提交过程。
  • 查询提交次数:通过确定查询提交次数来减轻站点的负担。
  • 获取数据的数量:即获取了多少惟一性的Web数据库信息。
  • 提交时间:爬行某特定站点需要多长时间。
上述每一个阀值或其组合都可以在穷尽阶段提前结束爬虫爬行。
3.识别和存取查询结果
对表单提交操作产生的响应主要有如下几种情况:响应页含有后台数据库部分或所有数据;响应页不仅包含有数据还包含链接;响应页含有数据和原始表单结构;响应页可能是另一张需要进一步填写的表单;错误页面通知;无记录通知或需要缺失字段。这一步主要是针对这些可能出现的情况进行处理。然后从含有丰富数据的页面中使用信息抽取工具抽取结构化的数据构建数据,以进一步提供信息检索服务。

现状

编辑
迎战“暗网”
对于庞大的“暗网”,搜索业界通行的策略主要有两种:其一,构建更有针对性的“暗网”爬虫,以便获取后台数据库;其二,与“暗网”网站合作,实现信息的对接和上浮。
对于第一种策略,它始终贯穿搜索引擎的发展过程。百度产品部相关人士对此表示,针对搜索引擎的升级和更新中,大部分与“暗网”问题有关,只不过对普通用户来讲,他们很难察觉。
第二种策略似乎更成效。不管是国外的谷歌、雅虎,还是国内的百度,都有针对性的计划,并且用户已经体验到了它们带来的变化。
富含信息查询模块技术
对于暗网爬虫来说,一个简单粗暴的方式是:将各个输入框肯呢过的输入值组合起来形成查询,比如机票查询来说,将所有出发城市、所有目的城市和时间范围的选项一一组合,形成大量的查询,提交给垂直搜索引擎,从其搜索结果里提炼数据库记录。
GOOGLE对此提出了解决方案,称之为富含信息查询模块技术。
假设为了描述一个职位,完整的查询由3个不同的属性构成:出发城市、到达城市和出发日期。如果在搜索引擎提交查询的时候,部分属性被赋予了值,而其他属性不赋值,则这几个赋值属性一起构成了一个查询模块。
如果模块包含一个属性,则称之为一维模块。图中模块1是一维模块,模块2和模块3是二维模块,模块4是三维模块。
模块1={出发城市 }
模块2={出发城市,到达城市 }
模块3={到达城市,出发日期 }
模块4={出发城市,到达城市和出发日期 }
对于某个固定的查询模块来说,如果给模块内每个属性都赋值,形成不同的查询组合,提交给垂直搜索引擎,观察所有返回页面的内容,如果相互之间内容差异较大,则这个查询模块就是富含信息查询模块。但是这将是一个庞大的查询组合基数,为了进一步减少提交的查询数目。GOOGLE的方案使用了ISIT算法。
ISIT算法的基本思路是:首先从一维模块开始,对一维查询模块逐个查询,看其是否富含信息查询模块,如果是的话,则将这个一模模块扩展到二维,再次依次查询对应的二维模块,如此类推,逐步增加维数,直到再无法找到富含信息查询模块为止。通过这种方式,就可以找到绝大多数富含信息查询模块,同时也尽可能减少了查询总数,有效达到了目的。 [1]



分享到:
咨询邮箱:2955046092@qq.com
QQ:2955046092
邮政编码:410007
社团地址:湖南省长沙市雨花区动西路428号