3期 谢磊等：RFD数据管理：算法、协议与性能评测 463 符可以在物品被回收等情况下重新被激活使用.由 RFID标签实现有效认证，但却无法保护标签的隐 此来看，灭活操作使标签丧失功能，不可能再被重 私.由于在步骤1标签需要事先将标识号T:发送至 用，从而阻止对标签的任意读取和跟踪；而需要考虑 阅读器，所有邻近的阅读器都能够读取该标识信息， 到重用的场合可以采取休眠(Sleep)机制[2]，原理与 这种方式完全暴露了标签的隐私；另一方面，如果不 前者相似，但是实施休眠机制的标签可以被唤醒再 发送标识号T:,则阅读器很难迅速地定位到对应的 次使用，静电屏蔽是指将标签放人具有静电屏蔽功 密钥：来支持后续操作.为了在实现认证的同时保 能的容器中，使其不能与外界进行电磁耦合，阻止标 障隐私，事实上存在一种简单直接但性能低下的方 签被扫描，这种方法需要一个额外的物理设备，如法 法：相比于算法1，标签无需传输标识T:,而是直接 拉第网罩.主动干扰是指通过一个设备主动广播干 根据接收的挑战数R发送加密密文C=E[R].阅 扰信号来阻止或破坏附近的非授权阅读器对标签的 读器接收到加密密文C后，在本地遍历所有可能的 读写操作.文献[27]提出了一套基于掩码的主动干 k:计算C,=E,[R],如果存在某个，使得C:=C,则 扰机制.当阅读器在读取标签ID时，标签周围的保 通常情况下该密钥对应的标签即为当前认证的标签. 护设备会同时传输一串掩码序列信号，最终阅读器 假设搜索空间存在n个标签，该算法密钥搜索的时间 接收到标识符ID与掩码相混杂的信号.这种机制 复杂度为O(n),当n数值很大时，其搜索时间开销是 使得授权的阅读器能够使用该掩码序列有效恢复标 巨大的，针对上述问题，很多研究工作开始关注于如 签的标识符，而未授权的阅读器由于无法获取该掩 何根据加密密文进行快速的数据搜索.文献[30]提出 码序列的模式，从而无法对接收的混杂信号进行有 了基于对称密钥的加密数据搜索系统.文献[31-32] 效恢复.阻塞法采用一个特殊的阻止标签，通过设定 也提出了基于加密数据库的查询系统.我们也在该 的标签冲突算法来阻止未授权的阅读器读取那些受 方面开展了研究工作，文献[33]通过在标签上维护 保护的标签.文献[28]提出了上述阻止标签的理念， 一个单调增的计数器，从而利用二叉搜索方案来进 通过编入标签的可修改位来保护隐私，若隐私位为 行快速的搜索，将时间复杂度降低至O(logn), ‘0'表示可公开扫描，为‘1’则表示是私有区域.当阅 在基于对称密钥加密协议中，当密钥k:的长度 读器访问私有区域时，采用一个特殊的阻止标签来 足够大时（不小于128位），仅仅根据比特串R和C 实行干扰，从而阻止未授权的阅读器非法读取受保 是很难在短时间内使用普通的计算设备推算出密钥 护的标签. :的，协议安全性高.但是，由于RFID标签成本的 33基于对称密钥加密的协议 限制，标签内部存储单元通常少于512bit,逻辑门的 公开密钥加密算法虽然功能强大，能够有效地 数目也相当受限，实际使用在RFID系统中的比特 实现加密、电子签名等机制，但由于其复杂的计算操 串R和C以及密钥k,的长度都远小于达到正常安 作使其根本无法在资源异常受限的RFID系统上实 全标准所期望的数目.例如，德州仪器公司研发了用 现.因此，RFID系统往往借助于逻辑较为简单的对 于汽车防盗系统中的加密RFID标签，出于标签成 称密钥加密算法来实现安全与隐私保障机制.具体 本的考虑，挑战数R与密钥k:的长度仅为40bit,标签 来说，基于对称密钥加密的协议可以用来对标签进 响应结果C仅为24bit.在这种情况下完全可以通 行有效认证.在该协议中，任一标签与阅读器共享一 过逆向工程、密码破解等技术来破解该加密系统.针 个对称密钥.算法1阐述了使用对称密钥加密算法 对上述问题，研究者们提出了各种轻量级解决方案 对RFID标签进行认证的过程2]， 来保障安全性.其中，DESL3是在传统的加密协议 算法1.使用对称密钥加密算法对RFID标 DES基础上为适应.小型计算设备（如RFID标签）要 签进行认证 求的一种轻量级的扩展，是一套超低成本的加密算 1.标签向阅读器发送数值T,表明身份 法.HIGHT[35]是一种分组加密算法，它使用64位 2.阅读器生成一个随机的比特串R,发送至标签。 的分组块和128位的密钥，子密钥只在加密和解密 3.标签用密钥.：对比特串R进行加密，计算C= 的运行过程中被生成，对硬件资源的要求很低， E.[R],将C发送至标签， 3.4基于Hash函数的协议 4.阅读器本地计算C=E,[R],验证是否有C=C,若 相比于对称密钥加密协议，采用Hash函数可 是，则标签被成功认证 以在多数情况下实现等效的安全机制，且实现逻辑 上述基于对称密钥加密的协议虽然能够对 会大为简化.因此，近年来很多研究工作关注于在3期 谢 磊等 ：RFID数据管理 ：算法 、协议 与性 能评 测 463 符 可 以在物 品被 回收 等 情况 下 重新 被 激 活 使 用．由 此 来看 ，灭 活 操 作 使 标 签 丧 失 功 能 ，不 可 能再 被 重 用 ，从 而 阻止对标 签 的任 意读 取和 跟踪 ；而需 要考 虑 到 重用 的场 合可 以采 取休 眠 (Sleep)机制 [2 ，原 理与 前 者相 似 ，但 是 实施 休 眠 机 制 的 标 签 可 以被 唤 醒 再 次 使用 ．静 电屏蔽 是 指 将 标 签 放 人具 有 静 电屏 蔽 功 能的容器中，使其不能与外界进行电磁耦合 ，阻止标 签 被扫 描 ，这 种方 法需 要一 个额 外 的物 理设备 ，如 法 拉第 网罩．主动 干扰 是 指 通 过 一个 设 备 主 动 广 播 干 扰信号来 阻止或破坏附近的非授权阅读器对标签的 读 写操作 ．文 献 [-27]提 出了 一 套基 于掩 码 的主 动 干 扰机 制 ．当阅读器 在读 取标 签 ID 时 ，标签 周 围 的保 护设 备会 同时传 输 一 串掩 码 序 列 信 号 ，最 终 阅 读 器 接 收到标 识 符 ID 与 掩 码 相 混 杂 的 信 号 ．这 种 机 制 使得授权 的阅读器能够使用该掩码序列有效恢复标 签 的标识 符 ，而未 授 权 的 阅读 器 由 于无 法 获 取 该掩 码序 列 的模式 ，从 而 无 法对 接 收 的混 杂 信 号 进 行有 效恢 复．阻塞 法采 用一个 特 殊 的阻止 标签 ，通 过设定 的标 签 冲突算 法来 阻止 未授 权 的 阅读 器读 取那 些受 保护 的标 签．文献 [-281提 出 了上 述 阻止标 签 的理念 ， 通过 编人 标签 的 可修 改 位 来 保 护 隐 私 ，若 隐 私位 为 ‘0’表 示 可公 开扫 描 ，为 ‘l’则表示 是 私有 区域 ．当阅 读 器访 问私有 区域 时 ，采用 一 个 特 殊 的阻 止标 签 来 实行 干扰 ，从 而阻 止 未授 权 的 阅读 器 非 法 读 取受 保 护 的标 签 ． 3．3 基 于对 称密 钥加 密的 协议 公 开密 钥 加 密算 法 虽 然 功 能强 大 ，能 够 有效 地 实现加 密 、电子 签名 等机 制 ，但 由于其 复杂 的计 算操 作 使其 根本 无法 在 资源异 常 受 限 的 RFID系 统上 实 现．因此 ，RFID 系统往 往 借 助 于逻 辑 较 为 简单 的对 称 密钥 加 密算法 来 实 现 安 全 与 隐 私保 障机 制 ．具 体 来 说 ，基 于对称 密钥 加 密 的协 议 可 以用来 对 标 签 进 行 有效 认证 ．在 该协 议 中 ，任 一标 签与 阅读器 共 享一 个对称密钥．算法 1阐述 了使用对称密钥加密算法 对 RFID标 签进 行认证 的过程 _2． 算法 1． 使用对称密 钥加密算 法对 RFID标 签 进行 认证 ． 1．标签 向阅读 器发送 数值 表 明身份 ． 2．阅读器生成一 个随机的 比特 串 R，发送至标签． 3．标 签 用 密 钥 k对 比 特 串 R 进 行 加 密 ，计 算 C— Ek[R]，将 C发送至标签 ． 4．阅读器本地计算 C 一 [R]，验证 是否有 C—C ，若 是 ，则标 签被成功认证． 上述基 于 对称 密 钥 加 密 的 协议 虽 然 能 够 对 RFID标签 实 现 有 效 认 证 ，但 却 无 法 保 护 标 签 的 隐 私．由于在 步骤 1标 签需要 事 先将 标 识 号 T 发 送 至 阅读器 ，所 有邻 近 的阅读器 都 能够读 取该 标识 信息 ， 这 种方 式完 全暴 露 了标签 的 隐私 ；另 一方 面 ，如果不 发 送标 识号 T ，则 阅读 器很 难迅 速 地定 位 到 对应 的 密 钥 k来 支持 后续 操 作．为 了 在实 现 认 证 的 同 时保 障隐私 ，事 实上存 在 一 种 简 单 直接 但 性 能 低 下 的方 法 ：相 比于算 法 1，标 签 无需 传 输 标 识 ，而 是直 接 根据接收的挑战数 R发送加密密文 C—E [R]．阅 读 器接 收到 加密 密文 c后 ，在 本 地 遍历 所 有 可 能 的 忌计 算 C —Ek[R]，如果 存 在某个 k使 得 C 一C，则 通 常情 况下该密钥 对应 的标签 即为 当前认证 的标签 ． 假设搜 索空 间存 在 个标签 ，该 算法密 钥搜索 的时 间 复杂度 为 0()，当 n数值很 大时 ，其 搜索 时间 开销是 巨大 的．针对上 述 问题 ，很 多研 究 工作 开 始关 注 于如 何根据加密密文进行快速的数据搜索．文献[301提出 了基于对称密钥 的加密数据搜索系统．文献1-31—321 也 提 出了基 于加 密数 据 库 的查 询 系统 ．我们 也 在 该 方 面开展 了研 究 工作 ，文 献 [-331通 过 在标 签上 维 护 一 个 单 调增 的计 数器 ，从 而 利 用 二 叉搜 索方 案 来 进 行快 速 的搜 索 ，将 时 间复杂 度降低 至 O(1og，z)． 在基 于对 称密 钥 加 密协 议 中 ，当密 钥 k的长 度 足够 大 时 (不 小于 128位 )，仅仅 根 据 比特 串 R 和 C 是很 难在 短 时间 内使用 普通 的计算 设 备推算 出密 钥 k。的，协议安全性高．但是 ，由于 RFID标签成本的 限制 ，标 签 内部 存储 单元 通 常少 于 512bit，逻 辑 门的 数 目也相 当受 限 ，实 际使 用 在 RFID 系 统 中 的 比特 串 R 和 c 以及 密 钥 k的 长度 都 远 小 于 达 到 正 常 安 全标 准所 期望 的数 目．例 如 ，德州仪 器公 司研 发 了用 于汽 车 防 盗 系 统 中的 加 密 RFID标 签 ，出于标 签 成 本 的考 虑 ，挑战数 R与密钥 k的长度仅为 40bit，标 签 响应结 果 C仅 为 24bit．在 这 种 情 况 下 完 全 可 以 通 过逆 向工 程 、密 码破 解等 技术来 破 解该 加密 系统．针 对上述 问题 ，研究者们提 出了各种轻量级解决方案 来保障安全性．其中，DESL[3]是在传统的加密协议 DES基 础上 为适应 小 型计算 设备 (如 RFID标 签)要 求 的一 种轻 量级 的扩 展 ，是 一 套超 低 成 本 的加 密算 法 ．HIGHTl_3。。是 一 种 分 组 加 密 算 法 ，它 使 用 64位 的分组 块 和 128位 的密钥 ，子 密钥 只在 加 密 和解 密 的运行过程 中被生成 ，对硬件资源的要求很低． 3．4 基 于 Hash函数的协 议 相 比于对称 密钥加密协议，采用 Hash函数可 以在多数情况下实现等效 的安全机制，且实现逻辑 会 大为 简化 ．因此 ，近 年 来 很 多 研 究 工 作 关 注 于 在