Question

什么是哈希锁，在RFID中怎样使用

Answer 1

RFID安全问题集中在对个人用户的隐私保护、对企业用户的商业秘密保护，防范对RFID系统的攻击以及利用RFID技术进行安全防范等多个方面。面临的挑战是： ① 保证用户对标签的拥有信息不被未经授权访问，以保护用户在消费习惯、个人行踪等方面的隐私。 ② 避免由于RFID系统读取速度快，可以迅速对超市中所有商品进行扫描并跟踪变化，而被利用来窃取用户商业机密。 ③ 防护对RFID系统的各类攻击，如重写标签以篡改物品信息;使用特制设备伪造标签应答欺骗读写器，以制造物品存在的假相;根据RFID前后向信道的不对称性远距离窃听标签信息;通过干扰RFID工作频率实施拒绝服务攻击;通过发射特定电磁波破坏标签等。 ④ 如何把RFID的唯一标识特性用于门禁安防、支票防伪、产品防伪等。 为了避免RFID标签给客户带来关于个人隐私的担忧，同时也为了防止用户携带安装有标签的产品进入市场所带来的混乱，很多商家在商品交付给客户时都把标签拆掉。这种方法无疑增加了系统成本，降低了RFID标签的利用率，并且有些场合标签不可拆卸。为解决上述安全与隐私问题，人们还从技术上提出了多种方案，包括Kill标签、法拉第网罩、主动干扰、智能标签、阻止标签和Hash锁等方法。Hash锁通过简单的Hash函数，增加闭锁和开锁状态，对标签和读写器之间的通信进行访问;但是它无法解决位置隐私和中间人攻击问题。本文提出一种Hash锁改进方法，成功解决了这个问题。 1 Hash锁方法分析 1.1 定读取控制Hash锁方法 在定读取控制Hash锁方法中，射频标签只对授权的读写器起作用，它代表了一种认证过程，认证密匙固定不变。使用该方法的射频标签分别有1个只读(ROM)和1个可读写(如RAM)的存储器，并且每个电子标签只供有限的用户使用。这些用户都共有同一个存储在读写存储器中的识别码。每个标签认证HR8002读写器的过程如图1所示。读写器对每一个电子标签都有一个认证密匙k，每个电子标签都存储有一Hash方程计算的结果metaID=Hash(k)。首先HR8002读写器向射频标签发出ID访问请求，标签向读写器发出相应的metaID。读写器根据接收到的metaID得出密匙k并发送给标签。然后该标签把接收到的密匙k代入Hash方程，检验计算得到的结果与存储在标签中的metaID是否一致。如果一致，标签就把其ID发送给读写器。 该方案提出了一种低成本解决安全与隐私问题的方法。仅仅需要一个Hash方程和存储metaID值就足够。但是它不能防止被跟踪，因为射频标签的反应能提前被预测泄露，并且随机密匙k和标签ID能被敌人窃听到。 1.2 随机读取控制Hash锁的方法 为了避免被跟踪，射频标签的反应不能被预测到而是随机的。主要有两种随机读取控制Hash锁的方法。MIT AutoID中心提出了一种随机Hash方案。读写器向射频标签发出ID访问请求，标签向读写器发出的不是固定的metaID，而是变化的。如图2所示，每个标签与读写器共享一个认证密匙IDk。当读写器向射频标签发出ID访问请求时，射频标签产生一个伪随机数字R和输出(R,h(IDk‖R))，其中h(IDk‖R)是输入R和认证密匙IDk的Hash方程。然后读写器获得所有射频标签的认证密匙。读写器根据接收的R和存储在后台数据库中所有密匙的ID计算Hash方程。如果Hash方程值与射频标签发送的Hash方程值匹配，读写器识别出该射频标签的密匙IDk并发送给射频标签。因为每次访问时，射频标签的输出改变了。该方法避免了被跟踪的缺点;但是该方法不适合少量射频标签的用户。因为被授权的读写器识别一个射频标签，就需要搜索和计算所有标签的ID，因此该方法不适合大量射频标签。 NTT提出了一种Hash链方法。在第i次与读写器交换时，射频标签有其初始值Si，发送ai=G(Si)给HR8002读写器，再根据以前的Si更新密匙Si+1=H(Si)。其中G和H都是Hash函数。 读写器把ai传给后台数据库，后台数据库维持一对列表(ID;Si)。其中Si是初始密匙值，对每一个标签,其值是不同的。后台数据库从读写器处接收标签,输出ai，并且对列表中的每个Si计算a0i=G(Hj(Si))，检查是否ai=a0i。如果ai与a0i匹配，ID就从一对a0i中识别出来了。该方法满足了不可分辨和向前的安全特性。G是单向方程，因此敌人能获得标签输出ai，但是不能从ai获得Si。G输出随机值，敌人能观测到标签输出，但不能把ai和ai+1联系起来。H也是单向方程，敌人能篡改标签并获得标签的密匙值，但不能从Si+1获得Si。该算法优势很明显，但是有太多的计算和比较。为了识别一个ID，后台服务器不得不计算ID列表中的每1个ID。假设有N个已知的标签ID在数据库中，数据库不得不进行N次ID搜索，2N次Hash方程计算和N次比较。计算机处理负载随着ID列表长度成线性增加,因此，该方法也不适合大量射频标签的情况。 2 随机读取控制Hash锁方法的改进 为了避免定读取控制Hash锁方法中的人为攻击和恶意跟踪的缺陷，并克服随机读取控制Hash锁方法中计算负载过大的不足，在随机读取控制Hash锁的基础上，提出了一种改进方法。 2.1 必需的RFID系统各部分结构 (1) 射频标签 射频标签由两部分构成:一部分是只读存储器(ROM)和随机读取存储器(RAM)，ROM存储的是标签ID的Hash值，RAM存储的是被鉴别的读写器的ID;另一部分是逻辑电路，主要用于一些简单的计算，如计算Hash方程或产生简单的伪随机数。(2) 读写器 读写器与射频标签无线通信，每一个读写器都有ReaderID，用来识别一批被鉴别的读写器。例如，在超市里的所有读写器都有一样的ReaderID，表明它们都来源于该超市。当HR8002读写器向射频标签发出访问请求时，标签通过读写器的ReaderID检验读写器。读写器同时与后台数据库连接并通信,以识别标签并运行相关的应用。 (3) 数据库 后台数据库存储了一对对射频标签ID和它的Hash方程值：[TagID,hash(TagID)]。一般地，后台数据库与读写器通过有线和安全通道相连接。 2.2 工作原理 读写器要查询射频标签ID，必须首先确定该读写器是否被认证。若读写器被认证，标签则响应读写器并让读写器获得其ID。 (1) 读写器认证 在响应读写器并让读写器获得标签ID信息前，读写器和标签确定了认证体制。因为读写器的ReaderID提前存储在标签的RAM中，所以标签通过读写器ID识别出有权限的读写器。标签不响应没有权限的读写器，因此，不可能被敌人跟踪(因为读写器都有权限)。另外，这种权限化过程是基于标签产生的随机数，因此，还可以防止敌人的哄骗。 当射频标签接收到读写器的请求时，首先射频标签产生随机数k并发送给读写器，读写器接收后传给后台数据库，后台数据库计算a(k)=Hash (ReaderID‖k)并把a(k)传回给HR8002读写器，然后读写器把a(k)发送给标签。同时射频标签计算Hash(ReaderID‖k)，然后标签比较读写器与标签计算的a(k)值是否相等。如相等，读写器通过了认证并且标签向它发送一些与TagID相关的信息;若不等，该读写器没有通过认证被屏蔽。 (2) 获得标签的TagID 如图5所示，在读写器认证后，射频标签响应认证的读写器Hash(TagID)。当读写器接收到Hash(TagID)值时，它会与后台数据库通信并寻找数据对(TagID，Hash(TagID))，读写器就会获得相应的TagID。即使Hash(TagID)值被窃听了，当标签向外发送其值时，窃听者也不会知道Hash的值。因为窃听者无法确定TagID与Hash(TagID)之间的相互关系。 (3) 在射频标签存储器里更新认证读写器的ReaderID 当一个物体从一个仓库运到另一个仓库时，被认证的读写器将从先前仓库的读写器改变为当前的读写器。这个过程如图6所示。读写器获得Hash(TagID)的值并传给后台数据库，数据库通知存储在标签里的ReaderID更新。相应地，数据库寻找出New ReaderID并把它传给读写器。当读写器接收到New ReaderID时，读写器把该值与Old ReaderID“异或”，并把“异或”值发送给射频标签。标签能够从“异或”值和Old ReaderID中得出New ReaderID，最后ReaderID被更新。 在ReaderID更新过程中，即使“异或”值被泄露，敌人也不能获取New ReaderID。因为不能获取Old ReaderID，因此防止了哄骗。 2.3 改进方法分析 (1) 防止窃听 在认证过程中，即使敌人窃听到读写器的输出a(k)，也不能在下一步获得认证。因为每一认证过程中需要的a(k)值是变化的。前一次认证的a(k)值对于后一次认证来说是无意义的。 认证完后，射频标签输出Hash(TagID)而不是TagID。因为Hash方程很难求其反函数，所以敌人捕获到输出Hash(TagID)值，也不能得到TagID的值。 当射频标签要更新存储器的ReaderID时，所更新的ReaderID是经过旧的ReaderID加密过的，也防止了窃听。 总之，上述改进方法即使在读写器和射频标签之间的通信遭遇到敌人的窃听时，也是安全的。 (2) 防止跟踪 射频标签对敌人是屏蔽的，只对被认证的读写器响应。而且，如上所述，敌人是无法伪造认证读写器的。因为没有标签输出，所以敌人不能通过跟踪标签来跟踪客户刚付费买的是什么。位置隐私及客人携带的物品得到了保护。 (3) 低计算负载 该改进方法运算速度快，成本低。当要从N个已知的射频标签中识别出一个时，读写器只需要执行1次Hash操作和N次ID搜索，而随机读取控制Hash锁方法至少需要N次Hash操作和N次ID搜索。显然在同一安全级上，所提出的改进方法计算负载显著降低;而且认证过程是依赖于N个已知的标签ID和1个Hash锁方程，因此随着标签的数量增多，计算负载缓慢增大。 (4) 适用于大量射频标签 因为计算负载低，并且随着射频标签的数量增加而缓慢增加，所以该方法非常适合有大量标签存在的被保护的RFID系统。 3 结论 以上提出的一种Hash锁改进方法，特别适合于物流管理。该方法需要必要的硬件，如可改写的存储器和简单的逻辑电路。该方法具有高安全性、小负载等优点，适用于大量标签应用的场合;解决了位置隐私和中间人攻击问题，即使敌人窃取了标签的输出，也不能获取标签的ID。

般的线性表、树中，记录在结构中的相对位置是随机的即和记录的关键字之间不存在确定的关系，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较”的基础上，查找的效率与比较次数密切相关。理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立一确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。因而查找时，只需根据这个对应关系f找到给定值K的像f(K)。若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上，由此不需要进行比较便可直接取得所查记录。在此，称这个对应关系f为哈希函数，按这个思想建立的表为哈希表（又称为杂凑法或散列法）。

哈希表不可避免冲突(collision)现象：对不同的关键字可能得到同一哈希地址 即key1≠key2，而f(key1)=f(key2)。具有相同函数值的关键字对该哈希函数来说称为同义词(synonym)。 因此，在建造哈希表时不仅要设定一个好的哈希函数，而且要设定一种处理冲突的方法。可如下描述哈希表：根据设定的哈希函数H(key)和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集(区间)上并以关键字在地址集中的“象”作为相应记录在表中的存储位置，这种表被称为哈希表。

注：这个函数f(key)为哈希函数。(注意：这个函数并不一定是数学函数) 哈希函数是一个映象，即：将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可。 现实中哈希函数是需要构造的，并且构造的好才能使用的好。

对于动态查找表而言，1) 表长不确定；2)在设计查找表时，只知道关键字所属范围，而不知道确切的关键字。因此，一般情况需建立一个函数关系，以f(key)作为关键字为key的录在表中的位置，通常称这个函数f(key)为哈希函数。(注意：这个函数并不一定是数学函数)

哈希函数是一个映象，即：将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可。

现实中哈希函数是需要构造的，并且构造的好才能使用的好。

用途：加密，解决冲突问题。。。。
用途很广，比特精灵中就使用了哈希函数，你可 以自己看看。
具体可以学习一下数据结构和算法的书。

字符串哈希函数（著名的ELFhash算法）
int ELFhash(char key)
{ unsigned long h=0;
while(key)
{ h=(h<<4)+key++;
unsigned long g=h&0Xf0000000L;
if(g) h^=g>>24;
h&=~g;
}
return h%MOD;
}
希望能帮到你！