<4D F736F F D D0C25FC1F5D5DCC0ED2C3139D2B35F2DD3C5CFC8B3F6B0E6434E4B492E646F63>

Transcription

1 软 件 学 报 ISSN , CODN RUXUW -mail: Journal of Software,2012,23(1): [doi: /SP.J ] 中 国 科 学 院 软 件 研 究 所 版 权 所 有. Tel/Fax: 保 留 格 式 加 密 技 术 研 究 刘 哲 理 1,2, 贾 春 福 1,2 1,2+, 李 经 纬 1 ( 南 开 大 学 信 息 技 术 科 学 学 院 计 算 机 与 信 息 安 全 系, 天 津 ) 2 ( 福 建 师 范 大 学 网 络 安 全 与 密 码 技 术 重 点 实 验 室, 福 建 福 州 ) Research on the Format-Preserving ncryption Techniques LIU Zhe-Li 1,2, JIA Chun-Fu 1,2, LI Jing-Wei 1,2+ 1 (Department of Computer and Information Security, College of Information Technical Science, Nankai University, Tianjin , China) 2 (Key Laboratory of Network Security and Cryptology, Fujian Normal University, Fuzhou , China) + Corresponding author: -mail: lijw1987@gmail.com Liu ZL, Jia CF, Li JW. Research on the format-preserving encryption techniques. Journal of Software, 2012, 23(1): Abstract: The paper reviews the current research situation of (format-preserving encryption) including basic constructing methods, encryption modes and security. When describing the basic constructing methods, it introduces the basic principles of Prefix, Cycle-Walking and Generalized-Feistel and their application scopes. When explaining the encryption modes, it mainly analyzes the construction features of modes or schemes, introduces the principles of three classical modes, summarizes the different types of Feistel networks and presents an overview of their applications in. When talking about the security, it describes the security notions of and their corresponding games, analyzing the relationship among them. In the end, it introduces the application scopes of and points out that performance, integrity authentication and key problems of database encryption with, such as making range query and arithmetic operation on encrypted data, are the major problems to be solved in the future. All these works will play a role in promoting research of format-preserving encryption. Key words: format-preserving encryption; rank-then-encipher; Feistel network; security goal; order preserving encryption; privacy homomorphism 摘 要 : 围 绕 基 本 构 建 方 法 加 密 模 型 和 安 全 性 等 方 面, 对 保 留 格 式 加 密 (format-preserving encryption, 简 称 ) 的 研 究 现 状 进 行 了 综 述. 在 基 本 构 建 方 法 方 面, 介 绍 了 Prefix,Cycle-Walking 和 Generalized-Feistel 方 法 的 工 作 原 理 及 适 用 范 围 ; 在 加 密 模 型 方 面, 分 析 了 模 型 或 方 案 所 呈 现 的 构 造 特 点, 介 绍 了 典 型 模 型 的 工 作 原 理, 总 结 了 Feistel 网 络 的 类 型 及 其 在 中 的 应 用 情 况 ; 在 安 全 性 方 面, 描 述 了 保 留 格 式 加 密 的 安 全 目 标 及 相 关 的 游 戏 模 型, 分 析 了 各 安 全 目 标 之 间 的 关 系. 最 后 介 绍 了 保 留 格 式 加 密 的 应 用 领 域, 指 出 性 能 完 整 性 认 证 以 及 在 数 据 库 加 密 应 用 中 基 金 项 目 : 国 家 自 然 科 学 基 金 ( ); 天 津 市 自 然 科 学 基 金 (09JCYBJ00300); 高 等 学 校 博 士 学 科 点 专 项 科 研 基 金 ( ); 网 络 安 全 与 密 码 技 术 福 建 省 高 校 重 点 实 验 室 开 放 课 题 ( ); 中 央 高 校 基 本 科 研 业 务 费 专 项 资 金 收 稿 时 间 : ; 修 改 时 间 : ; 定 稿 时 间 : ; jos 在 线 出 版 时 间 : CNKI 优 先 出 版 时 间 : :19,

2 刘 哲 理 等 : 保 留 格 式 加 密 技 术 研 究 153 如 何 对 密 文 进 行 范 围 查 询 算 术 运 算 将 是 进 一 步 需 要 解 决 的 问 题. 这 些 研 究 工 作 将 对 保 留 格 式 加 密 的 研 究 起 到 一 定 的 促 进 作 用. 关 键 词 : 保 留 格 式 加 密 ; 排 序 后 加 密 ;Feistel 网 络 ; 安 全 目 标 ; 保 序 加 密 ; 秘 密 同 态 中 图 法 分 类 号 : TP309 文 献 标 识 码 : A 在 实 际 应 用 中, 对 数 据 库 中 的 信 用 卡 号 身 份 证 号 等 敏 感 数 据 进 行 加 密 非 常 必 要, 然 而 使 用 传 统 分 组 密 码 通 常 会 扩 展 数 据, 使 数 据 长 度 和 类 型 发 生 变 化, 需 要 修 改 数 据 库 结 构 或 应 用 程 序 来 适 应 这 些 变 化, 成 本 非 常 高. 此 类 加 密 要 求 密 文 与 明 文 具 有 相 同 的 格 式, 是 一 类 新 的 加 密 问 题, 称 为 保 留 格 式 加 密 (format-preserving encryption, 简 称 ). 的 初 衷 是 为 了 解 决 数 据 库 或 者 应 用 系 统 中 敏 感 数 据 的 加 密 问 题, 随 着 研 究 的 进 展, 其 应 用 并 不 仅 限 于 此. 比 如 : 可 以 应 用 于 数 据 遮 蔽 (data masking) [1] 领 域, 通 过 克 隆 原 始 数 据 进 行 掩 码 转 换, 输 出 一 个 与 原 数 据 格 式 关 联 一 模 一 样 的 数 据, 用 于 解 决 从 生 产 环 境 的 数 据 向 测 试 环 境 ( 或 者 开 发 环 境 ) 导 入 时 可 能 产 生 的 数 据 内 容 安 全 问 题. 此 外, 对 于 网 络 数 据 安 全 一 样 有 用, 可 以 使 数 据 报 在 不 改 变 格 式 的 情 况 下 在 传 输 过 程 中 受 到 保 护. 目 前, 国 外 已 公 开 发 表 多 篇 有 关 的 理 论 研 究 成 果, 美 国 Voltage 公 司 已 将 技 术 应 用 到 其 安 全 产 品 SecureData 中. 本 文 关 注 近 年 来 保 留 格 式 加 密 研 究 的 进 展, 描 述 了 保 留 格 式 加 密 的 研 究 历 史, 并 主 要 围 绕 基 本 方 法 加 密 模 型 以 及 安 全 性 等 方 面 对 已 有 的 研 究 成 果 进 行 综 述, 指 出 已 有 加 密 模 型 的 构 造 特 点, 全 面 介 绍 了 与 相 关 的 安 全 目 标 和 相 应 的 游 戏 模 型, 以 期 对 保 留 格 式 加 密 在 国 内 的 研 究 起 到 一 定 的 推 动 作 用. 1 保 留 格 式 加 密 1.1 问 题 保 留 格 式 加 密 是 一 种 对 称 密 码, 要 求 密 文 与 明 文 具 有 相 同 的 格 式. 在 1997 年,Smith 和 Brightwell [2] 认 为, 有 助 于 增 强 数 据 库 和 数 据 仓 库 的 安 全 性, 并 指 出 使 用 传 统 分 组 密 码 解 决 该 问 题 的 困 难 : 数 据 库 中 敏 感 数 据 加 密 后, 密 文 要 和 明 文 具 有 大 致 的 相 似 性. 使 用 DS 算 法 对 一 个 社 会 保 险 号 加 密 后, 密 文 不 仅 不 像 社 会 保 险 号, 甚 至 不 包 含 任 何 数 字, 由 于 社 会 保 险 号 在 数 据 库 中 被 定 义 为 长 度 为 9 的 字 符 型 字 段, 因 此 无 法 存 储 DS 算 法 加 密 后 的 数 据, 应 用 程 序 也 无 法 正 确 读 取 和 显 示, 除 非 在 应 用 程 序 和 数 据 库 中 进 行 大 量 的 修 改 来 适 应 加 密 后 数 据 格 式 的 变 化. 对 于 数 据 库 敏 感 数 据 的 保 留 格 式 加 密, 需 要 保 证 密 文 满 足 数 据 库 对 于 数 据 格 式 的 约 束, 主 要 包 括 :(1) 数 据 不 能 被 扩 充. 例 如, 当 加 密 N 位 的 数 字 时, 必 须 输 出 另 外 一 个 N 位 的 数 字 ;(2) 数 据 类 型 不 能 被 改 变 ;(3) 数 据 必 须 能 被 确 定 性 地 加 密. 对 于 数 据 库 中 作 为 主 键 或 者 索 引 字 段 的 数 据, 被 加 密 后 将 保 留 其 所 在 的 列 作 为 主 键 或 者 索 引 的 特 性 ;(4) 加 解 密 过 程 可 逆. 1.2 研 究 历 史 问 题 自 提 出 以 来 已 有 大 约 30 年 的 研 究 历 史, 可 以 划 分 为 两 个 阶 段 : 早 期 的 研 究 学 者 致 力 于 探 索 可 行 的 解 决 方 法, 最 近 的 研 究 学 者 则 致 力 于 解 决 复 杂 消 息 空 间 上 的 保 留 格 式 加 密 问 题 和 提 出 高 效 的 加 密 模 型. 其 中, 具 有 代 表 性 的 有 关 的 文 献 及 其 所 做 的 贡 献 可 见 表 基 本 方 法 探 索 阶 段 基 本 方 法 探 索 阶 段 主 要 致 力 于 提 出 简 单 问 题 域 上 问 题 的 解 决 方 法. 自 1981 年 提 出 问 题 以 来, 直 到 2002 年 才 提 出 了 适 用 于 整 数 集 上 的 3 种 基 本 的 构 建 方 法. 问 题 最 早 可 以 追 溯 到 1981 年, 文 献 [3] 描 述 了 一 种 使 用 DS 算 法 加 密 字 符 串 的 方 法. 与 分 组 密 码 算 法 不 同, 该 方 法 要 求 密 文 与 明 文 具 有 相 同 的 格 式 : 假 设 密 文 和 明 文 是 由 确 定 字 母 表 chars 中 字 母 组 成 的 字 符 串, 比 如 chars={0,1,,9}, 则 加 解 密 必 须 在 集 合 chars n ( 由 chars 中 字 符 组 成 的 长 度 为 n 的 字 符 串 构 成 的 集 合 ) 中 完

3 154 Journal of Software 软 件 学 报 Vol.23, No.1, January 2012 成, 即 对 于 每 个 明 文 x chars n, 其 将 被 映 射 成 密 文 y chars n [3]. 然 而 随 着 2005 年 5 月 FIPS 74 标 准 的 停 止 使 用, 该 方 法 也 被 废 弃. Table 1 History of format-preserving encryption researches 表 1 保 留 格 式 加 密 的 研 究 历 史 时 间 论 文 方 法 或 贡 献 解 决 的 问 题 域 1981 Guidelines for implementing and using the NBS data encryption standard [3] 一 种 基 于 DS 的 加 密 方 案 chars n 1997 Using datatype-preserving encryption to 一 种 基 于 DS 的 enhance data warehouse security [2] CFB 模 式 的 加 密 方 案 chars n 2002 Prefix Ciphers with arbitrary finite domains [4] Cycle-Walking 整 数 集 Generalized-Feistel 2004 Security of random Feistel schemes 证 明 了 Feistel 网 络 的 轮 数 with 5 or more rounds [6] 与 由 其 安 全 性 的 关 系 2008 Voltage security whitepaper: 提 出 使 用 来 保 护 数 据 Format preserving encryption [7] 库 中 的 个 人 识 别 信 息 2008 Feistel finite set encryption mode [8] FFSM 整 数 集 Rank-then-ncipher 任 意 正 则 语 言 2009 Format-Preserving encryption [9] 一 种 基 于 非 平 衡 Feistel 网 络 的 整 数 方 案 整 数 集 2009 The FFX mode of operation for [10] format-preserving encryption FFX charsn 2009 How to encipher messages on a small domain 一 种 基 于 Thorp Shuffle 的 Deterministic encryption and the thorp shuffle [17] 解 决 方 案 小 型 整 数 集 2010 BPS: A format-preserving encryption proposal [13] BPS chars n 2010 A new scheme based on Feistel network [18] 基 于 Type-2 Feistel 网 络 的 整 数 方 案 2010 Format-Preserving encryption for DateTime [19] 基 于 随 机 基 准 值 的 加 密 方 案 注 :chars 为 一 个 有 限 字 符 表 整 数 集 数 据 库 中 日 期 时 间 型 字 段 1997 年, 文 献 [2] 考 虑 了 更 一 般 的 情 况, 描 述 了 对 数 据 库 中 特 定 类 型 字 段 进 行 加 解 密 的 困 难, 试 图 寻 找 一 种 保 留 数 据 类 型 不 变 的 加 解 密 方 法, 将 其 定 义 为 保 留 数 据 类 型 加 密 (datatype-preserving encryption, 简 称 DP), 并 指 出 传 统 的 分 组 密 码 不 适 合 解 决 该 问 题. 文 献 [2] 的 作 者 提 供 了 可 参 考 的 解 决 方 法 : 使 用 DS 算 法 基 于 CFB (cipher-feedback) 模 式 来 产 生 一 个 偏 移 量 向 量, 并 与 明 文 字 符 串 的 索 引 向 量 求 和, 得 到 密 文 字 符 串 的 索 引 向 量, 最 后 再 将 其 转 化 为 密 文 字 符 串. 然 而, 该 方 法 在 固 定 密 钥 的 情 况 下, 当 两 个 明 文 字 符 串 具 有 相 同 的 前 缀 时, 所 得 的 密 文 也 具 有 相 同 的 前 缀, 这 会 造 成 明 文 部 分 信 息 的 泄 露 年, 文 献 [4] 首 次 从 密 码 学 角 度 研 究 了 问 题, 认 为 核 心 是 设 计 某 密 码 :K X X. 其 中,K 是 密 钥 空 间, X 是 有 限 的 消 息 空 间. 文 献 [4] 关 注 整 数 集 X= n ={0,1,,n 1} 上 的 问 题, 提 出 了 3 种 构 建 方 法 :Prefix, Cycle-Walking 和 Generalized-Feistel.Prefix 密 码 在 内 存 中 建 立 一 个 伪 随 机 置 换, 利 用 该 置 换 来 加 密 数 据, 仅 适 合 于 较 小 整 数 集 (6 位 以 内 十 进 制 整 数 ).Cycle-Walking 方 法 能 够 使 用 传 统 分 组 密 码 ( 分 组 大 小 为 2m) 在 小 于 但 接 近 于 2 2m 的 整 数 集 上 产 生 一 个 安 全 置 换, 然 而, 如 果 待 加 密 整 数 集 的 大 小 远 远 小 于 所 采 用 密 码 分 组 的 长 度 时, 则 Cycle-Walking 会 消 耗 更 高 的 代 价. 实 验 证 明, 采 用 64 位 加 密 算 法, 适 合 加 密 的 范 围 为 二 进 制 位 数 为 54~64 位 的 [5] 整 数 集 (16~19 位 十 进 制 整 数 ).Generalized-Feistel 方 法 利 用 Feistel 网 络 构 造 分 组 长 度 为 2m 的 分 组 密 码 ( 这 里 使 2 2m 略 大 于 待 加 密 整 数 集 的 大 小 ), 并 结 合 Cycle-Walking 方 法, 理 论 上 可 对 任 意 大 小 的 整 数 集 进 行 保 留 格 式 加 密. 实 验 证 明, 该 方 法 较 适 合 二 进 制 位 数 为 40~240 位 的 整 数 集 (12~80 位 十 进 制 整 数 ). 文 献 [4] 还 证 明, 当 攻 击 者 拥 有 的 明 文 密 文 对 少 于 2 m/2 时,Generalized-Feistel 方 法 具 有 足 够 的 安 全 性.2004 年,Patarin [6] 简 单 扩 展 了 Black 和 Rogaway 的 结 论, 用 更 多 轮 次 的 Feistel 运 算 替 代 原 来 的 3 轮 运 算, 证 明 了 攻 击 者 至 少 需 要 拥 有 2 m 的 明 文 密 文 对 时 才 可 能 破 译 密 码, 使 得 Feistel 网 络 能 够 在 更 大 范 围 内 得 以 应 用.

4 刘 哲 理 等 : 保 留 格 式 加 密 技 术 研 究 加 密 模 型 研 究 阶 段 2008 年, 美 国 Voltage 公 司 公 布 了 其 安 全 产 品 中 所 采 用 的 技 术 的 白 皮 书 [7], 介 绍 了 已 有 的 研 究 成 果, 提 出 了 社 会 保 险 号 和 信 用 卡 号 的 方 案. 自 此, 得 到 了 更 多 关 注, 研 究 学 者 们 基 于 已 提 出 的 简 单 问 题 域 上 的 方 法, 试 图 解 决 更 复 杂 问 题 域 上 的 问 题, 并 提 出 高 效 的 加 密 模 型 年, 文 献 [8] 基 于 平 衡 Feistel 网 络, 以 截 断 基 础 分 组 密 码 AS 输 出 的 方 式 构 造 所 需 的 伪 随 机 函 数, 提 出 了 FFSM(Feistel finite set encryption mode) 模 型. 该 模 型 使 用 Cycle-Walking 方 法, 理 论 上 可 以 解 决 任 意 整 数 集 上 的 问 题, 已 被 NIST( 美 国 国 家 标 准 和 技 术 协 会 ) 所 采 纳 年,Bellare 在 文 献 [9] 中 对 问 题 进 行 了 更 深 入 的 研 究, 充 分 考 虑 了 消 息 空 间 的 复 杂 性, 完 整 地 定 义 了 的 密 码 学 概 念 及 安 全 目 标, 提 出 了 一 种 通 用 的 构 建 方 法 Rank-then-ncipher, 简 称 Rt 方 法. 该 方 法 主 要 包 括 两 个 步 骤, 即 排 序 和 加 密, 能 否 在 待 加 密 消 息 空 间 中 找 到 高 效 的 排 序 算 法 是 该 方 法 的 关 键. 然 而, 并 不 是 所 有 消 息 空 间 都 存 在 高 效 的 排 序 算 法,Bellare 等 人 将 此 作 为 开 放 性 问 题 保 留 下 来, 即 在 实 际 问 题 中 寻 找 一 个 不 需 要 使 用 排 序 算 法 的 高 效 方 法. 同 年,Bellare 在 消 息 空 间 Feistel 网 络 类 型 和 轮 运 算 等 方 面 对 FFSM 进 行 了 扩 展, 提 出 了 FFX(formatpreserving,Feistel-based,X 是 参 数 选 择 等 相 关 因 素 ) 模 型 [10]. 该 模 型 使 用 非 平 衡 Feistel 网 络 [11], 可 以 解 决 长 度 为 n 的 字 符 串 构 成 的 消 息 空 间 chars n (chars 为 某 固 定 字 符 表 ) 上 的 问 题. 与 FFSM 相 比,FFX 所 解 决 的 问 题 的 消 息 空 间 更 加 复 杂, 加 入 了 对 调 整 因 子 (tweak) [12] 的 支 持, 支 持 非 二 进 制 字 母 表 和 非 平 衡 划 分, 并 且 在 加 密 信 用 卡 号 社 会 保 险 号 等 信 息 时, 可 以 避 免 使 用 Cycle-Walking 年, 文 献 [13] 对 FFX 进 行 了 改 进, 详 细 描 述 了 调 整 因 子 的 使 用 方 法, 提 出 了 BPS 模 型. 在 该 模 型 中, 可 以 使 用 TDS [14],AS [15] 或 SHA-2 [16] 构 建 内 部 分 组 加 密 算 法, 通 过 CBC 模 式 (cipher-block chaining mode) 可 以 加 密 任 意 长 度 的 字 符 串 并 保 留 其 格 式. 除 了 上 述 典 型 的 加 密 模 型 外, 在 2009 年, 文 献 [17] 针 对 文 献 [4] 中 所 提 出 的 方 法 (Prefix,Cycle-Walking 和 Generalized-Feistel) 不 能 解 决 的 较 小 整 数 集 ( 比 如 6~12 位 十 进 制 整 数 ) 内 的 问 题, 提 出 了 基 于 Thorp Shuffle 的 解 决 方 案, 并 详 细 分 析 了 其 安 全 性. 在 2010 年, 文 献 [18] 基 于 k- 分 割 的 Type-2 Feistel 网 络 提 出 了 新 的 整 数 方 案. 同 年, 文 献 [19] 针 对 Rt 方 法 在 对 日 期 型 数 据 进 行 时 效 率 较 低 的 问 题, 提 出 了 基 于 随 机 基 准 值 的 日 期 类 型 的 解 决 方 案, 基 本 思 想 是 随 机 选 取 一 个 日 期 作 为 基 准 值, 通 过 对 待 加 密 的 日 期 相 对 于 该 基 准 值 的 偏 移 量 进 行 加 解 密 的 方 法, 将 日 期 类 型 的 问 题 转 移 为 整 数 域 上 的 问 题, 极 大 地 提 高 了 效 率. 1.3 两 种 定 义 基 于 已 有 的 研 究 成 果, 从 两 个 角 度 对 进 行 了 定 义 : 基 本 和 一 般 化. 基 本 描 述 了 要 解 决 的 问 题, 即 确 保 密 文 属 于 明 文 所 在 的 消 息 空 间 ; 一 般 化 则 强 调 问 题 的 复 杂 性 在 于 待 加 密 消 息 空 间 的 复 杂 性. 定 义 1( 基 本 ). 可 以 简 单 描 述 为 一 个 密 码 :K X X, 其 中,K 为 密 钥 空 间,X 为 消 息 空 间. 基 本 强 调 明 文 和 密 文 处 于 相 同 的 消 息 空 间, 因 此 具 有 相 同 的 格 式. 以 n 位 信 用 卡 号 的 保 留 格 式 加 密 为 例, 密 文 要 求 与 明 文 一 样, 都 是 由 十 进 制 数 字 组 成 的 长 度 为 n 的 字 符 串, 即 两 者 均 为 消 息 空 间 {0,,9} n 内 的 元 素. 根 据 基 本 的 定 义, 分 组 密 码 也 是 一 种 特 殊 的, 它 是 由 分 组 长 度 n 决 定 的 {0,1} n 字 符 串 集 合 上 的 置 换. 然 而, 要 处 理 的 消 息 空 间 远 比 分 组 密 码 复 杂 的 多, 比 如 格 式 为 YYYY-MM-DD 的 日 期 型 消 息 空 间, 不 仅 有 长 度 为 10 的 字 符 串 长 度 限 制, 还 需 要 满 足 特 定 位 置 是 字 符 - 年 月 日 在 合 理 范 围 内 等 格 式 要 求. 为 了 更 准 确 地 描 述 问 题, 定 义 集 合 Ω 为 格 式 空 间, 任 意 一 个 格 式 ω Ω, 可 确 定 消 息 空 间 的 一 个 与 格 式 ω 相 关 的 子 空 间 X ω. 与 集 合 {X ω } ω Ω 有 关, 称 X ω 为 由 格 式 ω 确 定 的 消 息 空 间 的 一 个 分 片, 每 个 分 片 都 是 一 个 有 限 集. 当 给 定 密 钥 k 格 式 ω 和 调 整 因 子 t 后, 就 是 一 个 定 义 在 X ω 上 的 置 换, t ω k. 定 义 2( 一 般 化 ). 可 以 描 述 为 一 个 密 码 :K Ω T X X { }, 其 中,K 为 密 钥 空 间,Ω 为 格 式 空 间,T 为 调 整 空 间,X 为 消 息 空 间. 所 有 空 间 都 非 空, 且 X.

5 156 Journal of Software 软 件 学 报 Vol.23, No.1, January 2012 为 了 有 效 地 研 究 分 析 加 密 模 型, 可 通 过 算 法 三 元 组 =(Gen,nc,Dec) 来 描 述 一 般 化, 其 中 : 算 法 Gen: 初 始 化 系 统 参 数 params. 不 同 模 型 需 要 初 始 化 的 系 统 参 数 也 有 所 差 异, 通 常 包 含 3 部 分 : 1) 初 始 化 具 有 足 够 安 全 性 的 对 称 加 密 算 法 所 需 的 参 数, 比 如 Feistel 网 络 所 需 要 的 轮 次 数 轮 函 数 和 分 组 长 度 等 ; 2) 初 始 化 待 解 决 的 问 题 域, 包 括 明 确 格 式 ω 及 由 其 确 定 的 分 片 X ω ; 3) 初 始 化 用 于 加 解 密 的 对 称 密 钥 k, 该 对 称 密 钥 需 要 安 全 存 储, 不 对 外 公 开. 算 法 nc: 输 入 为 调 整 因 子 t 和 明 文 x, 返 回 在 分 片 X ω 内 的 密 文 y 或 者. 该 算 法 执 行 X) 过 程,, T Ω K ω, t () 是 X Ω 上 的 一 个 置 换. 如 果 x X ω, 则 返 回 y = ( x) ; 否 则, 返 回. k Ω, T K ( X) = (K,Ω,T, 算 法 Dec: 输 入 为 调 整 因 子 t 和 密 文 y, 返 回 相 同 分 片 X ω 内 的 明 文 x 或 者. 该 算 法 是 算 法 nc 的 逆 运 算, ω, t 定 义 如 下 : 如 果 y X ω, 则 返 回 x = D ( y) ; 否 则, 返 回. k 1.4 标 准 安 全 目 标 保 留 格 式 加 密 是 一 种 特 殊 的 对 称 密 码, 基 础 模 块 是 分 组 密 码 和 伪 随 机 函 数. 由 于 安 全 性 通 常 可 以 归 约 到 基 础 模 块 的 安 全 性 上, 因 此, 保 留 格 式 加 密 的 一 个 重 要 的 安 全 目 标 是 伪 随 机 性 年,Black 和 Rogaway [4] 首 次 描 述 了 保 留 格 式 加 密 的 安 全 性, 认 为 标 准 的 安 全 目 标 就 是 伪 随 机 置 换 (pseudorandom permutation, 简 称 PRP) 安 全. 根 据 基 本 的 定 义, 对 任 意 k K,(k, )= k ( ) 是 消 息 空 间 X 上 由 对 称 密 钥 k 决 定 的 一 种 置 换. 设 Perm k ( ) $ 表 示 消 息 空 间 X 上 所 有 置 换 的 集 合, P Perm( X) 表 示 从 Perm k ( ) 中 随 机 抽 取 一 个 置 换 P. 设 A f 是 一 个 可 以 查 询 预 言 机 f 的 攻 击 者,f 要 么 是 加 密 预 言 机 k ( ), 要 么 是 一 个 随 机 置 换 预 言 机 P( ). 假 定 攻 击 者 从 不 执 行 消 息 空 间 之 外 的 查 询, 而 且 不 重 复 相 同 的 查 询, 这 样 的 攻 击 者 A 可 以 认 为 是 保 留 格 式 加 密 方 案 的 PRP 攻 击 者, 并 且 定 义 其 在 攻 击 中 可 获 得 的 优 势 为 PRP def $ k ( ) $ P() ( A) = Pr[ k K : A = 1] Pr[ P Perm (): 1] k A = Adv. 上 式 度 量 了 攻 击 者 A 区 分 保 留 格 式 加 密 和 随 机 置 换 的 概 率 优 势. PRP PRP 定 义 3(PRP 安 全 ). 令 Adv ( tq, ) max Adv ( A), 其 中,t 为 攻 击 者 执 行 破 解 算 法 的 时 间,q 为 攻 击 者 查 询 A PRP 的 次 数. 如 果 Adv (, ) 是 一 个 可 忽 略 的 量, 则 称 该 保 留 格 式 加 密 方 案 为 伪 随 机 置 换, 也 即 达 到 了 PRP 安 全. 2 基 本 方 法 2002 年,Black 和 Rogaway [4] 提 出 了 3 种 构 建 方 法 :Prefix,Cycle-Walking 和 Generalized-Feistel. 这 3 种 方 法 不 仅 在 一 定 程 度 上 解 决 了 整 数 集 上 的 问 题, 而 且 成 为 构 造 模 型 的 基 本 方 法. 其 中,Cycle-Walking 和 Generalized-Feistel 在 后 续 的 加 密 模 型 中 得 到 了 广 泛 使 用, 包 括 FFSM [8],FFX [10],BPS [13] 等. 2.1 Prefix Prefix 方 法 很 简 单, 首 先 在 内 存 中 建 立 一 个 随 机 的 置 换 表, 然 后 基 于 该 置 换 表 对 数 据 进 行 加 解 密. 这 意 味 着 加 解 密 速 度 非 常 快, 但 在 较 大 消 息 空 间 上 建 立 置 换 表 将 会 耗 费 更 多 的 时 间, 因 此 只 适 用 于 较 小 的 有 限 集 X={0,1,,n 1},n<10 6. 将 Prefix 方 法 记 为 密 码 P, 其 密 钥 空 间 为 K, 消 息 空 间 为 整 数 集 X={0,1,,n 1},n<10 6. 为 了 建 立 置 换 表, 采 用 基 础 分 组 密 码, 其 对 称 密 钥 为 k K, 计 算 如 下 元 组 :I=( k (0), k (1),, k (n 1)). 由 于 I 中 每 个 分 量 k (i),i X 是 长 度 为 分 组 长 度 的 不 同 二 进 制 符 号 串, 可 以 按 照 数 值 关 系 对 其 进 行 排 序, 由 此 得 到 k (i) 对 应 的 排 序 值 r i. 进 一 步 对 I 进 行 操 作, 将 分 量 k (i) 换 成 其 对 应 的 排 序 值 并 得 到 元 组 J=(r 0,r 1,,r n ), 这 样 就 建 立 了 消 息 空 间 X 上 的 一 个 置 换 表 : 给 定 任 意 明 文 x X, 返 回 元 组 J 中 相 同 序 号 的 分 量 r x, 就 得 到 了 对 应 的 密 文. 举 例 : 消 息 空 间 为 X={0,1,2,3,4}, 为 了 建 立 置 换 表, 选 择 基 础 分 组 密 码 为 AS, 计 算 k (0)=166; k (1)=6; k (2)=130; k (3)=201; k (4)=78( 这 里,AS 的 加 密 结 果 原 本 为 分 组 长 度 的 二 进 制 字 符 串, 但 为 方 便 起 见, 将 其 用 十

6 刘 哲 理 等 : 保 留 格 式 加 密 技 术 研 究 157 进 制 数 来 表 示 ), 得 到 元 组 I=(166,6,130,201,78), 将 每 个 分 量 替 换 为 其 对 应 的 排 序 值 得 到 元 组 J=(3,0,2,4,1). 从 而, 假 设 要 加 密 明 文 0, 返 回 元 组 J 中 序 号 为 0 的 分 量 为 其 密 文, 即 3. 实 际 应 用 中, 通 常 会 有 对 密 钥 进 行 更 新 的 要 求, 然 而 对 于 Prefix 方 法 来 说, 密 钥 的 更 新 意 味 着 重 新 建 立 置 换 表, 需 要 消 耗 较 高 的 代 价 ( 重 新 加 密 整 个 消 息 空 间 并 进 行 排 序 和 替 换 ). 因 此, 有 必 要 在 特 定 环 境 里 对 密 码 应 用 调 整 因 子 [12], 可 以 使 其 不 需 要 密 钥 更 新 而 更 改 加 密 函 数. 文 献 [7] 已 经 提 出 一 些 构 建 可 调 整 密 码 的 方 法 : 为 分 组 密 码 引 入 调 整 因 子 t 来 加 密 明 文 x, 可 执 行 操 作 y= k (( k (x)+t) MOD n). 可 见, 引 入 调 整 因 子 后 的 加 解 密 过 程 执 行 了 两 次 加 密, 但 是 对 Prefix 方 法 而 言, 加 解 密 是 在 内 存 中 查 表 的 操 作, 因 此 不 会 影 响 效 率. Prefix 方 法 不 会 降 低 基 础 分 组 密 码 的 安 全 性, 即 当 是 PRP 安 全 的 时 候,Prefix 也 能 达 到 相 同 的 安 全 性. 2.2 Cycle-Walking Cycle-Walking 方 法 为 确 保 密 文 为 消 息 空 间 内 的 元 素 提 供 了 一 种 通 用 的 解 决 思 路, 其 加 密 的 原 理 是 利 用 基 础 分 组 密 码 (AS 或 3DS 等 ) 对 中 间 输 出 值 不 断 地 进 行 处 理, 直 至 其 在 可 接 受 的 输 出 范 围 内. 设 Cycle k (x) 表 示 使 用 Cycle-Walking 方 法 对 明 文 x 加 密, 密 钥 为 k, 加 密 过 程 为 : 要 加 密 明 文 x {0,,n 1}, 选 用 分 组 密 码 ( 如 AS), 设 y= k (x), 如 果 y {0,,n 1}, 则 返 回 y; 否 则, 循 环 执 行 y= k (y), 直 到 有 {0,,n 1} 范 围 内 的 y 产 生 为 止.Cycle-Walking 可 以 将 不 在 期 望 范 围 内 的 密 文 加 密 到 此 范 围 内, 但 是 需 要 多 次 调 用. 举 例 : 设 X={0,1,,10 6 1}, 首 先 确 定 所 采 用 的 基 础 分 组 密 码, 由 于 10 6 <2 64, 选 用 64 位 的 DS 来 处 理, 可 以 保 证 其 输 出 范 围 始 终 包 含 X. 假 设 现 在 要 加 密 明 文 x=314159, 计 算 得 到 c 1 = k (314159)= ( 这 里, 采 用 DS 算 法, 为 方 便 起 见, 将 其 的 加 密 输 出 用 十 进 制 数 表 示 ), 因 为 c 1 X, 迭 代 计 算 c 2 = k ( )=1729. 因 为 c 2 X, 所 以 Cycle k (314159)=1729. Cycle-Walking 不 会 降 低 传 统 分 组 密 码 的 安 全 性 [4], 但 在 效 率 方 面, 一 次 加 密 可 能 需 要 多 次 调 用 基 础 分 组 密 码, 当 明 文 的 二 进 制 位 数 远 小 于 分 组 长 度 时, 会 因 为 迭 代 次 数 增 加 而 导 致 性 能 降 低. 因 此,Cycle-Walking 方 法 适 合 大 小 接 近 分 组 长 度 的 整 数 集. 比 如, 如 果 采 用 DS 算 法, 适 合 的 范 围 是 54~64 二 进 制 位 的 整 数 集. 2.3 Generalized-Feistel Generalized-Feistel 方 法 要 比 Prefix 和 Cycle-Walking 复 杂, 可 以 适 用 于 更 加 广 泛 的 加 密 范 围. 由 于 Cycle-Walking 方 法 对 于 接 近 分 组 密 码 大 小 的 整 数 集 完 成 保 留 格 式 加 密 时 具 有 较 高 的 性 能, 因 此 Generalized-Feistel 方 法 的 核 心 思 想 是 基 于 Feistel 网 络 来 构 建 符 合 整 数 集 大 小 的 分 组 密 码, 并 结 合 Cycle- Walking 方 法 使 最 终 密 文 输 出 在 合 理 范 围 内.Generalized-Feistel 方 法 由 两 部 分 组 成 :1 由 Feistel 网 络 构 造 的 分 组 密 码, 假 设 消 息 空 间 元 素 个 数 为 n, 则 的 分 组 长 度 要 略 大 于 log 2 n;2 Cycle-Walking 方 法, 确 保 数 据 被 加 密 到 合 理 范 围 内. Feistel 网 络 是 目 前 主 流 的 分 组 密 码 设 计 模 式 之 一, 基 于 Feistel 网 络, 可 以 通 过 自 定 义 的 分 组 大 小 密 钥 长 度 轮 次 数 子 密 钥 生 成 轮 函 数 等 来 构 造 一 个 分 组 密 码. 它 将 输 入 的 分 组 分 为 左 半 部 分 L 和 右 半 部 分 R, 进 行 指 定 轮 数 的 迭 代 运 算, 每 次 迭 代 执 行 轮 函 数 f 产 生 新 的 L 和 R( 记 为 L 和 R ) 作 为 输 出, 如 果 没 有 完 成 指 定 轮 数 的 迭 代, 输 出 结 果 将 作 为 新 一 轮 的 输 入 参 与 下 一 轮 迭 代. 为 了 构 建 Generalized-Feistel 密 码 GF n,f,r (x), 使 用 一 个 基 本 的 伪 随 机 函 数 f 和 r 轮 Feistel 运 算 来 加 密 整 数 集 X={0,1,,n 1} 内 的 值 x, 首 先 定 义 一 个 基 于 Feistel 网 络 的 对 称 密 码 n,f,r (x): 1) 寻 找 最 小 的 w 使 得 2 2w n,2w 就 是 需 要 构 建 的 分 组 密 码 的 分 组 长 度 ; 2) 定 义 f (x)=trunc(f(x),w) 表 示 截 取 f(x) 的 低 w 位 数 据 ; 3) 定 义 轮 运 算 Round(R,L)=L XOR f (R); 4) 计 算 n,f,r ( ):1 寻 找 R,L, 使 得 x=l 2 w +R;2 重 复 r 次 :{T=Round(R,L),L=R,R=T};3 输 出 L 2 w +R. GF n,f,r (x) 将 使 用 所 构 建 的 分 组 密 码 n,f,r (x) 进 行 如 下 计 算 :1 y= n,f,r (x);2 while (y n){y= n,f,r (y)}. 很 显 然,GF n,f,r (x) 使 用 了 Cycle-Walking 方 法, 确 保 数 据 加 密 到 合 理 的 范 围 内. 由 于 其 构 建 的 分 组 密 码 的 分 组 长 度 与 待 加 密 消 息 空 间 大 小 的 二 进 制 位 数 接 近, 因 此 具 备 较 好 的 性 能.

7 158 Journal of Software 软 件 学 报 Vol.23, No.1, January 2012 安 全 性 方 面,Black 和 Rogaway [4] 证 明 了, 当 攻 击 者 拥 有 明 文 密 文 对 少 于 2 w/2 时,GF n,f,r (x) 是 足 够 安 全 的. 2.4 结 论 Prefix,Cycle-Walking 和 Generalized-Feistel 方 法 能 够 解 决 特 定 范 围 整 数 集 上 的 问 题, 见 表 2. Table 2 Applicable scopes of basic methods 表 2 基 本 方 法 的 适 用 范 围 方 法 处 理 的 整 数 集 大 小 ( 二 进 制 位 数 ) 处 理 的 整 数 集 大 小 ( 十 进 制 整 数 ) Prefix 1~20 1~6 Cycle-Walking 50~63 16~19 Generalized-Feistel 40~240 12~80 表 2 描 述 了 3 种 基 本 方 法 的 适 用 范 围, 对 于 6~12 位 整 数 集 的 问 题,2009 年,Morris 和 Rogaway [17] 提 出 了 基 于 Thorp Shuffle 的 解 决 方 案. 3 种 基 本 方 法 为 保 留 格 式 加 密 方 案 的 构 造 提 供 了 基 本 的 思 路 : 1) Prefix 方 法 揭 示 了 保 留 格 式 加 密 的 本 质, 即 消 息 空 间 内 的 置 换.Prefix 方 法 采 用 建 立 预 置 换 表 的 做 法, 为 复 杂 问 题 域 上 的 问 题 提 供 了 一 种 思 路, 即 通 过 某 种 方 式 ( 比 如 排 序 ) 来 建 立 消 息 空 间 内 的 置 [9] 换,Rt 方 法 排 序 后 加 密 的 思 想 与 此 异 曲 同 工 ; 2) Cycle-Walking 方 法 是 一 种 解 决 任 意 有 限 问 题 域 的 问 题 的 通 用 办 法, 目 前 所 提 出 的 模 型 在 解 决 任 意 有 限 域 上 的 问 题 时, 通 常 基 于 该 方 法 来 确 保 数 据 被 加 密 到 正 确 的 范 围 内 ; 3) Generalized-Feistel 方 法 允 许 用 户 通 过 定 义 Feistel 网 络 的 相 关 参 数 来 构 建 合 适 分 组 长 度 的 对 称 密 码, 成 为 保 留 格 式 加 密 模 型 普 遍 适 用 的 构 造 方 法, 目 前 所 提 出 的 FFSM [8],FFX [10],BPS [13] 等 模 型 都 基 于 其 完 成 模 型 的 构 造. 3 加 密 模 型 研 究 首 先, 从 构 造 角 度 对 已 有 模 型 进 行 了 分 析, 总 结 出 模 型 的 构 造 特 点 ; 然 后, 介 绍 了 3 种 典 型 的 保 留 格 式 加 密 模 型, 分 析 了 其 适 用 的 问 题 域 及 存 在 的 主 要 问 题 ; 最 后, 针 对 Feistel 网 络 在 构 造 中 的 广 泛 应 用, 描 述 了 Feistel 网 络 的 类 型 及 其 在 模 型 中 的 应 用 情 况, 并 分 析 了 其 特 点. 3.1 构 造 特 点 [4] Black 和 Rogaway 在 2002 年 提 出 的 3 种 构 建 方 案 的 基 本 方 法 成 为 后 来 模 型 设 计 的 主 要 参 照, 已 提 出 的 主 要 模 型 或 方 案 及 其 采 用 的 构 建 方 法 见 表 3. Table 3 Modes or schemes of format-preserving encryption 表 3 保 留 格 式 加 密 模 型 或 方 案 时 间 模 型 或 方 案 所 解 决 的 问 题 域 基 本 方 法 Prefix Cycle-Walking Generalized-Feistel 其 他 2008 [7] 社 会 保 险 号 的 方 案 社 会 保 险 号 2008 FFSM [8] 整 数 集 2009 Rt [9] 任 意 正 则 语 言 基 于 Feistel 网 络 的 整 数 [9] 整 数 集 2009 FFX [10] chars n 2009 [17] 基 于 Thorp Shuffle 的 方 案 小 型 整 数 集 2010 BPS [13] chars n 基 于 Type-2 Feistel 网 络 的 整 数 [18] 整 数 集 注 :chars 为 一 有 限 字 符 表 由 表 3 可 以 看 出 : 1) Generalized-Feistel 方 法 得 到 了 更 多 的 关 注. 绝 大 多 数 方 案 都 用 到 了 Feistel 网 络 (Rt 方 法 强 调 先

8 刘 哲 理 等 : 保 留 格 式 加 密 技 术 研 究 159 排 序 后 加 密, 其 加 密 过 程 使 用 了 整 数 方 案, 而 目 前 已 提 出 的 整 数 方 案, 包 括 文 献 [9] 中 所 提 出 的 两 种 整 数 方 案, 都 是 基 于 Feistel 网 络 来 实 现 ), 这 与 Feistel 网 络 相 对 完 备 的 研 究 成 果 和 算 法 本 身 对 保 留 格 式 的 要 求 相 关 ; 2) 复 杂 问 题 域 上 的 问 题 通 常 需 要 结 合 Cycle-Walking 方 法. 问 题 的 复 杂 性 除 了 表 现 在 保 留 格 式 上 以 外, 也 表 现 在 待 解 决 消 息 空 间 的 复 杂 性 上, 这 种 复 杂 性 使 得 很 难 发 现 对 不 同 消 息 空 间 的 通 用 解 决 办 法. 消 息 空 间 越 复 杂, 问 题 也 就 越 难 解 决.Cycle-Walking 方 法 为 确 保 密 文 输 出, 在 消 息 空 间 内 提 供 了 一 种 通 用 的 解 决 思 路, 通 常 在 解 决 复 杂 问 题 域 上 的 问 题 时, 需 要 使 用 Cycle-Walking 方 法 ; 3) 模 型 的 设 计 思 想 逐 渐 向 降 低 问 题 域 复 杂 性 的 方 向 发 展. 在 解 决 愈 加 复 杂 的 消 息 空 间 上 的 问 题 时, 无 论 是 Rt 模 型 还 是 FFX 模 型, 都 不 在 复 杂 问 题 域 上 直 接 寻 求 问 题 的 解 决 办 法, 而 是 将 问 题 转 化 到 等 价 的 具 有 较 低 复 杂 度 的 整 数 集 上. 这 种 通 过 降 低 问 题 域 的 复 杂 性 来 解 决 复 杂 消 息 空 间 上 的 问 题 的 解 决 方 法, 将 会 成 为 保 留 格 式 加 密 领 域 的 一 种 可 采 纳 的 有 效 研 究 手 段. 3.2 主 要 模 型 FFSM,Rt 和 FFX 模 型 是 3 类 具 有 代 表 意 义 的 模 型, 研 究 其 构 造 特 点 和 优 缺 点, 对 于 研 究 分 析 加 密 模 型 具 有 重 要 意 义 FFSM 模 型 FFSM 是 基 于 Generalized-Feistel 方 法 的 整 数 集 上 的 典 型 方 案, 它 由 两 个 基 本 部 分 组 成 :1 平 衡 Feistel 网 络, 用 来 产 生 指 定 分 组 长 度 的 分 组 密 码 ;2 Cycle-Walking, 用 2m 位 的 分 组 密 码 对 大 小 为 n(n<2 2m ) 的 集 合 进 行 加 解 密 的 普 遍 方 法. 算 法 Gen:FFSM 初 始 化 阶 段 主 要 定 义 :1 FFSM-PRF, 即 平 衡 Feistel 网 络 中 所 使 用 的 伪 随 机 函 数, FFSM 使 用 截 断 基 础 分 组 密 码 AS 输 出 的 方 式 构 造 了 FFSM-PRF;2 基 础 分 组 密 码 的 密 钥 k 消 息 空 间 的 大 小 n 和 轮 次 数 r 等. 详 细 的 参 数 信 息 参 阅 文 献 [8]; 算 法 nc: 输 入 为 明 文 x, 输 出 为 满 足 格 式 要 求 的 密 文 y. 首 先, 将 明 文 x 编 码 为 l= log 2 n +1 位 的 二 进 制 数 ( 这 里, x 表 示 不 超 过 x 的 最 大 整 数 ), 不 足 的 二 进 制 位 用 0 来 填 充 ; 然 后 执 行 Cycle-Walking 过 程, 每 次 Cycle-Walking 都 将 执 行 r 轮 Feistel 轮 运 算, 直 到 产 生 合 适 的 密 文 ; 最 后, 对 密 文 进 行 二 进 制 解 码 得 到 对 应 数 值 的 整 数, 其 加 密 过 程 如 图 1 所 示. x 二 进 制 编 码 x 输 入 问 题 域 X= n 二 进 制 解 码 y 是 否 是 否 在 X 中 ( 2 ) l y 输 出 平 衡 Feistel 网 络 Cycle-Walking Fig.1 Feistel finite set encryption mode 图 1 FFSM 模 型 目 前, 该 加 密 模 型 已 被 Voltage 公 司 广 泛 应 用, 而 且 被 NIST 所 采 纳. 然 而,FFSM 仅 解 决 了 整 数 集 上 的 问 题, 并 不 能 成 为 一 种 普 遍 适 用 的 模 型 ; 而 且 Cycle-Walking 过 程 需 要 多 次 调 用 基 础 分 组 密 码, 存 在 不 确 定 的 性 能 问 题 Rt 方 法 Rt 是 一 种 较 通 用 的 方 法, 其 基 本 思 想 是, 对 消 息 空 间 内 的 元 素 先 排 序 后 加 密, 将 解 决 复 杂 有 限 域 上 的

9 160 Journal of Software 软 件 学 报 Vol.23, No.1, January 2012 问 题 转 化 到 建 立 索 引 与 元 素 的 对 应 关 系 和 设 计 整 数 算 法 上. 为 了 实 现 对 元 素 的 排 序, 需 要 有 效 地 描 述 消 息 空 间. 在 编 码 理 论 研 究 领 域, 自 1977 年 文 献 [20] 发 表 以 来, 已 经 开 始 了 对 特 定 消 息 空 间 上 高 效 rank 算 法 的 研 究. 其 中, 文 献 [9] 针 对 可 用 正 则 语 言 描 述 的 消 息 空 间, 介 绍 了 高 效 的 rank 和 unrank 算 法. Rt 方 法 的 工 作 原 理 如 图 2 所 示. 索 引 号 0 x 正 则 语 言 y rank 算 法 unrank 算 法... i... j 输 入 输 出 整 数 算 法... n-2 rank 和 unrank 过 程 n-1 整 数 过 程 Fig.2 Rank-then-ncipher approach 图 2 Rt 方 法 算 法 Gen:Rt 方 法 的 初 始 化 阶 段, 主 要 确 定 : 1) rank 和 unrank 函 数. 对 于 消 息 空 间 X, 其 上 的 排 序 函 数 可 以 描 述 为 映 射 rank:x X { }( 对 于 有 多 个 分 片 的 消 息 空 间, 通 常 对 每 个 分 片 分 别 进 行 rank 整 数 和 unrank, 这 里 假 设 待 加 密 消 息 空 间 只 有 一 个 分 片 ), 通 过 rank 算 法 可 以 找 到 x X 在 X 中 的 索 引 i X, 如 果 x X, 则 rank(x)=. 与 此 对 应, 反 排 序 函 数 将 一 个 整 数 映 射 为 其 在 X 中 对 应 的 元 素, 描 述 为 unrank: X { }. 通 过 unrank 算 法, 可 以 根 据 索 引 i X 找 到 其 在 X 内 的 对 应 元 素 x X, 如 果 i X, 则 unrank(i)=. 2) 整 数 方 案 及 其 所 需 的 参 数, 文 献 [9] 基 于 非 平 衡 Feistel 网 络 提 出 了 两 种 整 数 方 案, 而 Rt n 方 法 并 不 限 制 所 采 用 的 整 数 方 案, 比 如 FFSM [8] 等. 算 法 nc: 输 入 为 方 案 所 需 的 密 钥 k 明 文 x 调 整 因 子 t 等, 输 出 为 满 足 格 式 要 求 的 密 文 y. n 加 密 过 程 首 先 执 行 rank 算 法, 获 得 明 文 x 在 消 息 空 间 X 中 的 索 引 i; 然 后, 利 用 整 数 方 案 n 对 i 加 密 得 到 密 文 索 引 j; 最 后 执 行 unrank 算 法, 返 回 X 中 索 引 为 j 的 元 素 y 而 得 到 密 文. Rt 方 法 的 安 全 性 等 同 于 整 数 方 案 的 安 全 性, 只 要 安 全, 它 就 是 安 全 的. n Rt 方 法 的 效 率 主 要 取 决 于 消 息 空 间 内 的 排 序 算 法, 其 时 间 复 杂 度 约 为 rank 算 法 和 unrank 算 法 时 间 的 总 和.Bellare 针 对 用 正 则 语 言 描 述 的 消 息 空 间, 描 述 了 高 效 的 排 序 算 法 [9]. 除 此 之 外, 对 于 无 二 义 的 上 下 文 无 关 文 法 产 生 的 语 言,Bellare [9] [21] 指 出, 使 用 Mäkinen 提 出 的 rank 算 法 可 以 对 其 进 行 排 序. 其 他 各 种 组 合 结 构 也 存 在 高 效 的 rank 算 法, 例 如, 如 果 想 在 域 X n! ( 该 问 题 域 由 n 个 元 素 的 所 有 置 换 集 合 组 成 ) 上 加 密, 可 以 使 用 Lucas-Lehmer 编 码 提 供 的 高 效 rank 算 法 [22]. 其 他 的 例 子 还 有 伸 展 树 B 树 [23] [24] DYCK 语 言 等. 然 而, 并 不 是 所 有 消 息 空 间 都 存 在 基 于 排 序 的 高 效 算 法, 文 献 [9] 将 在 实 际 问 题 中 寻 找 一 个 不 需 要 使 用 排 序 算 法 的 高 效 作 为 有 趣 的 开 放 性 问 题 保 留 下 来 FFX 模 型 Bellare 在 消 息 空 间 Feistel 网 络 和 运 算 等 方 面 对 FFSM [8] 进 行 了 扩 展, 提 出 了 扩 展 机 制 FFX 模 型 [10]. 该 模 型 使 用 了 非 平 衡 Feistel 网 络, 通 过 自 定 义 运 算 可 以 解 决 n 位 字 符 串 所 构 成 的 消 息 空 间 chars n 的 问 题. FFX 模 型 的 工 作 原 理 如 图 3 所 示.

10 刘 哲 理 等 : 保 留 格 式 加 密 技 术 研 究 161 x 映 射 i 输 入 问 题 域 X=chars n 域 (chars ) n 非 平 衡 Feistel 网 络 y 逆 映 射 j 输 出 Fig.3 FFX mode 图 3 FFX 模 型 算 法 Gen:FFX 模 型 的 初 始 化 阶 段, 主 要 定 义 : 1) 字 母 表 chars={char 0,char 1,char 2,char 3,,char radix 1 } 及 其 基 数 radix= chars ; 2) 所 使 用 的 非 平 衡 Feistel 网 络 类 型 ; 3) 消 息 空 间 中 元 素 的 长 度 n; 4) 每 轮 中 所 用 到 的 伪 随 机 函 数 f 所 采 用 的 运 算 类 型 轮 次 数 r 和 调 整 因 子 t 等. 详 细 的 参 数 信 息 参 阅 文 献 [10]. 算 法 nc: 输 入 为 基 础 分 组 密 码 的 密 钥 k 调 整 因 子 t 和 字 符 串 x, 输 出 为 满 足 格 式 要 求 的 字 符 串 y. 字 符 串 x 和 y 都 是 由 字 母 表 chars={char 0,char 1,char 2,char 3,,char radix 1 } 中 字 符 组 成 的 长 度 为 n 的 字 符 串. 首 先, 将 字 符 串 x 中 的 字 符 编 码 替 换 为 数 字 : 建 立 字 母 表 chars={char 0,char 1,char 2,char 3,,char radix 1 } 与 chars ={0,1,2,3,,radix 1} 的 一 一 映 射, 将 每 个 字 符 char i 编 码 为 对 应 的 第 i 个 数 字. 需 要 注 意 的 是,chars 中 每 个 数 字 前 面 的 0 与 其 他 字 符 一 样 计 入 长 度, 例 如,chars={a,b,c,,z},x=acz, 将 x 编 码 后 得 到 x= 然 后, 执 行 r 轮 指 定 非 平 衡 Feistel 网 络 的 运 算 : 首 先, 将 输 入 ( 字 符 串 x 的 编 码 ) 分 割 为 左 右 两 部 分 L 和 R, L R ; 然 后, 执 行 伪 随 机 函 数 f, 对 L 和 f k (R) 执 行 选 择 的 类 型 的 运 算 得 到 L :1 c i =(a i +b i ) MOD radix, 当 radix=2 时, 该 运 算 就 是 异 或 运 算 ;2 c n i ( n i n i ) MOD n iradix = airadix + biradix radix ; 最 后, 连 接 L 与 R 得 到 输 出 L R, 并 将 其 作 为 下 一 轮 非 平 衡 Feistel 网 络 运 算 的 输 入. 可 见,FFX 模 型 通 过 将 非 数 字 字 母 表 与 数 字 集 合 建 立 双 射, 将 每 个 字 符 映 射 为 对 应 的 数 字 参 与 加 密 运 算, 实 现 对 消 息 空 间 chars n 的 保 留 格 式 加 密. 与 FFSM 相 比,FFX 适 用 的 范 围 更 广, 而 且 在 处 理 信 用 卡 号 社 会 保 险 号 等 问 题 时 避 免 了 Cycle-Walking, 具 有 较 高 的 效 率. 3.3 Feistel 网 络 及 其 应 用 自 2002 年 Generalized-Feistel 方 法 首 次 使 用 Feistel 网 络 来 构 造 算 法 以 来, 其 后 的 方 案 大 多 都 采 用 了 这 种 结 构, 这 与 Feistel 网 络 相 对 完 备 的 研 究 成 果 和 算 法 本 身 对 保 留 格 式 的 要 求 相 关. Feistel 网 络 是 目 前 主 流 的 分 组 密 码 设 计 模 式 之 一, 基 于 Feistel 网 络, 可 以 通 过 定 义 分 组 大 小 密 钥 长 度 轮 次 数 子 密 钥 生 成 轮 函 数 等 来 构 造 一 个 分 组 密 码. 在 模 型 的 构 造 过 程 中,Feistel 网 络 被 广 泛 应 用 于 构 造 合 适 分 组 长 度 的 分 组 密 码, 其 中,FFSM 使 用 了 平 衡 的 Feistel 网 络,FFX 模 型 中 使 用 了 两 种 非 平 衡 Feistel 网 络. 本 节 总 结 了 常 见 类 型 的 Feistel 网 络 及 其 在 不 同 模 型 中 的 应 用 Feistel 网 络 的 类 型 常 见 的 Feistel 网 络 类 型 主 要 包 括 传 统 的 Feistel 网 络 非 平 衡 Feistel 网 络 交 互 式 Feistel 网 络 及 以 上 3 种 的 数 值 形 式. 传 统 的 Feistel 网 络 [5], 即 平 衡 Feistel 网 络, 每 一 轮 运 算 的 基 本 原 理 如 图 4 所 示 : 输 入 为 长 度 为 2n 的 字 符 串,

11 162 Journal of Software 软 件 学 报 Vol.23, No.1, January 2012 首 先 将 其 等 分 为 长 度 相 等 的 两 部 分 L 和 R, 这 里, L = R =n, 然 后 对 R 执 行 轮 函 数 f k (R) 后 并 与 L 异 或 得 到 L =f k (R) XOR L, 最 后 将 新 的 字 符 串 R L 作 为 下 一 轮 迭 代 的 输 入. 文 献 [25] 证 明 了 迭 代 (6/ε 1) 轮 次 的 传 统 Feistel 网 络 在 选 择 密 文 攻 击 模 型 下 能 够 抵 御 2 n(1 ε) 次 恶 意 查 询. Schneier 和 Kelsey 对 传 统 Feistel 网 络 进 行 改 进, 引 入 扩 张 或 收 缩 轮 的 伪 随 机 函 数, 提 出 了 非 平 衡 Feistel 网 络 [11]. 非 平 衡 Feistel 网 络 能 够 支 持 对 输 入 字 符 串 不 平 衡 的 划 分, 即 L R. 由 于 L 与 R 不 等 长, 这 就 需 要 对 轮 函 数 f 进 行 调 整, 使 得 在 每 一 轮 迭 代 中 f k (R) = L 恒 成 立. 文 献 [25] 证 明, 进 行 足 够 多 轮 次 的 迭 代 运 算 之 后, 该 类 型 Feistel 网 络 能 够 抵 御 2 n 次 选 择 密 文 查 询. Anderson 和 Lucks 分 别 在 文 献 [26] 和 文 献 [27] 中 提 出 了 交 互 式 Feistel 网 络. 交 互 式 Feistel 网 络 也 支 持 对 输 入 字 符 串 的 不 平 衡 划 分, 其 关 键 在 于 能 够 根 据 当 前 迭 代 轮 次 的 奇 偶 性 质 来 判 定 使 用 哪 一 种 伪 随 机 函 数 的 类 型 ( 压 缩 还 是 扩 张 ) 及 作 用 对 象 (L 或 R):1 在 奇 数 轮 次, 伪 随 机 函 数 f 作 用 于 R, 并 将 作 用 结 果 与 L 进 行 异 或 操 作, 得 到 下 一 轮 迭 代 的 左 部 分 L, 下 一 轮 迭 代 的 右 部 分 直 接 由 R 产 生 ;2 在 偶 数 轮 次, 伪 随 机 函 数 g 作 用 于 L, 并 将 作 用 结 果 与 R 进 行 异 或 操 作, 得 到 下 一 轮 迭 代 的 右 部 分 R, 下 一 轮 迭 代 的 左 部 分 直 接 由 L 产 生. 平 衡 非 平 衡 和 交 互 式 Feistel 网 络 每 一 轮 运 算 的 过 程 如 图 4 所 示. L(n 位 ) R(n 位 ) R(n 位 ) L(m 位 ) R(n 位 ) f k + f k + L(m 位 ) L (m 位 ) R(n 位 ) R(n 位 ) L (n 位 ) R(n 位 ) L (m 位 ) L (m 位 ) R (n 位 ) 平 衡 Feistel 网 络 非 平 衡 Feistel 网 络 交 互 式 Feistel 网 络 + f k g k + Fig 4 Balanced, unbalanced and alternating Feistel networks 图 4 平 衡 非 平 衡 和 交 互 式 Feistel 网 络 数 值 的 Feistel 网 络 是 对 以 上 各 类 Feistel 网 络 的 输 入 进 行 优 化, 使 其 支 持 n 范 围 内 的 加 密. 假 设 输 入 为 整 数 x n, 一 个 可 行 的 划 分 办 法 就 是 选 定 整 数 a,b, 使 得 n=ab, 取 L= x/a ( 其 中, 为 向 下 取 整 运 算 ),R=x MOD a, 则 有 L a,r b. 于 是, 再 根 据 Feistel 网 络 的 具 体 类 型, 进 行 相 应 的 迭 代 运 算. 在 Feistel 网 络 中, 每 一 轮 迭 代 的 输 出 都 保 持 了 长 度 ( 对 输 入 为 字 符 串 的 Feistel 网 络 ) 或 范 围 ( 对 输 入 为 整 数 的 Feistel 网 络 ) 不 变, 这 一 特 点 使 其 非 常 适 合 于 处 理 问 题. 不 同 类 型 的 Feistel 网 络 在 方 案 中 的 应 用 现 状 可 见 表 4. Table 4 modes and their Feistel networks 表 4 模 型 及 其 采 用 的 Feistel 网 络 方 案 Feistel 网 络 Generalized-Feistel [4] 交 互 式 Feistel 网 络 的 数 值 形 式 FFSM [8] 传 统 Feistel 网 络 ( 平 衡 Feistel 网 络 ) FFX [10] 非 平 衡 Feistel 网 络, 交 互 式 Feistel 网 络 基 于 Feistel 网 络 的 整 数 [9] 非 平 衡 Feistel 网 络 的 数 值 形 式, 交 互 式 Feistel 网 络 的 数 值 形 式 BPS [13] 交 互 式 Feistel 网 络 通 过 表 4 可 以 看 出, 目 前, 典 型 的 方 案 所 采 用 的 Feistel 网 络 类 型 都 将 输 入 划 分 为 等 长 或 不 等 长 的 L 和 R 两 部 分, 即 所 采 用 的 都 是 2- 分 割 的 Feistel 网 络 类 型. 最 近, 文 献 [18] 基 于 l- 分 割 的 Type-2 Feistel 网 络 类 型 提 出 了 一 种 新 的 整 数 方 案. Type-1,Type-2 和 Type-3 Feistel 网 络 是 Feistel 网 络 的 3 种 扩 展 形 式 [28], 将 输 入 长 度 为 lm 的 比 特 串 等 分 为 l 个 分 组 X 1,X 2,,X l, 然 后 分 别 进 行 各 自 的 轮 运 算 ( 图 5 描 述 了 l=4 时 的 工 作 原 理 ): 1) Type-1 Feistel 网 络 执 行 X 2 = fk ( X1) X2, 并 连 接 X 2 X3 X4 X1作 为 下 一 轮 迭 代 的 输 入 ;

12 刘 哲 理 等 : 保 留 格 式 加 密 技 术 研 究 163 2) Type-2 Feistel 网 络 执 行 X 2 = fk ( X1) X2 和 X 4 = gk ( X3) X4, 并 连 接 X 2 X3 X 4 X1作 为 下 一 轮 迭 代 的 输 入 ; 3) Type-3 Feistel 网 络 执 行 X 2 = fk( X1) X2, X 3 = gk( X2) X3和 X 4 = hk ( X3) X4, 并 连 接 X 2 X 3 X 4 X 1 作 为 下 一 轮 迭 代 的 输 入. X 1 X 2 X 3 X 4 X 1 X 2 X 3 X 4 X 1 X 2 X 3 X 4 f + f + g + f + g + h + X X 3 X 4 X 1 X 2 X 3 X 4 X 1 X X X X 1 Type-1 Feistel 网 络 Type-2 Feistel 网 络 Type-3 Feistel 网 络 Fig.5 Type-1, Type-2, Type-3 Feistel networks 图 5 Type-1,Type-2,Type-3 Feistel 网 络 基 于 Feistel 网 络 的 模 型 和 方 案 的 特 点 基 于 Feistel 网 络 的 模 型 和 方 案, 包 括 FFSM [8],FFX [10],BPS [13] 等, 普 遍 具 有 如 下 特 点 : 1) 通 常 与 Cycle-Walking 方 法 结 合 使 用. 在 表 4 中, 只 有 FFSM [8] 在 内 部 构 造 中 使 用 了 Cycle-Walking 方 法. 事 实 上, 基 于 Feistel 网 络 的 加 密 模 型 在 解 决 任 意 有 限 域 上 的 问 题 时, 与 Cycle-Walking 方 法 相 结 合 是 一 种 通 用 的 做 法 ; 2) 具 有 可 证 明 的 安 全 性.Luby 和 Rackoff 证 明 了, 当 分 组 长 度 为 2m 且 攻 击 者 拥 有 明 文 密 文 对 少 于 2 m/2 时,Feistel 网 络 是 安 全 的 [5]. 如 果 用 更 多 轮 次 运 算 替 代 Generalized-Feistel 方 法 中 的 3 轮 运 算, 只 有 当 攻 击 者 至 少 拥 有 2 m 的 明 文 密 文 对 时 才 可 能 破 译 密 码 [6], 使 得 Feistel 结 构 能 够 在 更 大 范 围 内 得 以 应 用 ; 3) 现 有 方 案 的 Feistel 网 络 中 所 用 到 的 伪 随 机 函 数 的 构 造 方 法 主 要 有 两 类 :1 采 用 直 接 截 断 基 础 分 组 密 码 输 出 的 办 法, 构 造 伪 随 机 函 数, 比 如 FFSM 中 FFSM-PRF 的 构 造 方 法 ;2 以 基 础 分 组 密 码 为 核 心 算 法, 采 用 CBC-MAC,HMAC 等 消 息 认 证 码 方 案, 将 产 生 的 消 息 认 证 码 作 为 PRF 的 输 出, 比 如 FFX 中 伪 随 机 函 数 的 构 造 方 法 [10]. 这 两 类 构 造 方 法 都 具 有 可 证 明 的 安 全 性. 4 安 全 性 研 究 在 设 计 密 码 学 方 案 时, 主 要 考 虑 在 可 能 面 临 的 攻 击 模 型 下 所 要 达 到 的 安 全 目 标, 通 常 使 用 安 全 目 标 与 攻 击 模 型 相 结 合 的 方 式 来 定 义 密 码 学 方 案 的 安 全 性. 对 于 公 钥 密 码 体 制 而 言, 安 全 目 标 主 要 有 : 语 义 安 全 (semantic security) [29] 不 可 区 分 性 (indistinguishability, 简 称 IND) [29,30] 不 可 展 性 (non-malleability, 简 称 NM) [31] 和 明 文 可 意 识 性 (plaintext awareness, 简 称 PA) [32]. 由 于 明 文 可 意 识 性 是 在 随 机 预 言 机 模 型 (random oracle model) [33] 下 定 义 的, 而 随 机 预 言 机 模 型 又 是 一 种 理 想 化 的 模 型, 因 此, 对 于 实 际 系 统 中 安 全 性 的 讨 论 较 少 提 到 明 文 可 意 识 性.Goldwasser 和 Micali [29,30,34,35] 证 明 了, 安 全 目 标 中 的 语 义 安 全 等 价 于 不 可 区 分 性 安 全. 公 钥 密 码 体 制 的 安 全 目 标 通 常 也 适 用 于 对 称 密 码 体 制. 除 此 之 外, 因 为 密 码 学 方 案 一 般 建 立 在 底 层 基 础 模 块 上, 所 以 方 案 的 安 全 性 通 常 也 可 以 规 约 到 基 础 模 块 的 安 全 性. 由 于 对 称 密 码 体 制 的 基 础 模 块 是 分 组 密 码 和 伪 随 机 函 数, 因 此, 对 称 密 码 体 制 的 另 一 个 重 要 的 安 全 目 标 是 伪 随 机 性. 保 留 格 式 加 密 是 一 种 对 称 密 码, 因 此, 对 称 密 码 体 制 的 安 全 目 标 对 其 通 常 都 适 用. 在 2009 年,Bellare [9] 对 问 题 进 行 了 深 入 研 究, 结 合 保 留 格 式 加 密 的 特 性, 定 义 了 相 关 的 多 种 安 全 目 标. 4.1 安 全 目 标 对 于 保 留 格 式 加 密 而 言, 标 准 的 安 全 目 标 是 PRP 安 全. 也 就 是 说, 本 质 是 在 特 定 消 息 空 间 内 的 伪 随 机 置

13 164 Journal of Software 软 件 学 报 Vol.23, No.1, January 2012 换. 较 低 的 安 全 目 标 包 括 SPI(single point indistinguishability),mp(message privacy) 和 MR(message recovery), 这 些 安 全 目 标 更 容 易 实 现, 而 且 可 以 满 足 典 型 应 用 的 安 全 性 要 求 定 义 PRP 安 全 :PRP 的 标 准 安 全 目 标 在 第 1.4 节 已 经 给 出 定 义, 要 求 攻 击 者 不 能 区 分 是 保 留 格 式 加 密 方 案 还 是 消 息 空 间 内 置 换 集 合 中 的 某 个 随 机 置 换.Bellare 进 一 步 在 文 献 [9] 中, 基 于 游 戏 模 型 定 义 了 适 用 于 一 般 定 义 的 PRP 安 全 目 标. PRP 安 全 的 定 义 基 于 游 戏 PRP, 该 游 戏 通 过 攻 击 者 与 挑 战 者 之 间 的 博 弈, 量 化 攻 击 者 区 分 保 留 格 式 加 密 或 随 机 置 换 的 能 力. $ $ 首 先 从 密 钥 空 间 随 机 选 取 一 个 密 钥 k K, 从 {0,1} 中 随 机 选 择 一 个 值 b {0,1}, 从 消 息 空 间 X 内 的 置 $ 换 集 合 中 随 机 选 取 一 个 置 换 P Perm( X). PRP 拥 有 加 密 预 言 机 Oracle(nc), 用 于 响 应 攻 击 者 A 的 加 密 查 询, 如 果 b=1, 加 密 预 言 机 Oracle(nc) 以 保 留 格 式 加 密 方 案 响 应 ; 如 果 b=0, 加 密 预 言 机 Oracle(nc) 以 随 机 选 取 的 方 式 置 换 P 响 应. 攻 击 者 A 的 目 标 是 : 在 查 询 加 密 预 言 机 Oracle(nc) 一 定 次 数 后, 给 出 一 个 判 定 Oracle(nc) 使 用 的 是 还 是 P, 即 输 出 一 个 判 定 值 b. 如 果 b =b, 说 明 攻 击 者 A 判 定 成 功, 相 反, 则 失 败.A 在 该 游 戏 中 具 有 的 优 势 为 PRP A Adv ( A) = 2 Pr[PRP true] 1. SPI 安 全 :SPI 要 求 攻 击 者 即 使 能 够 访 问 真 正 的 加 密 预 言, 也 不 能 区 分 是 对 选 定 的 消 息 还 是 对 某 个 随 机 点 的 加 密. SPI 安 全 的 定 义 基 于 游 戏 SPI. 类 似 于 PRP,SPI 首 先 随 机 选 取 密 钥 k 和 待 猜 测 的 布 尔 值 b. 攻 击 者 A 首 先 对 某 个 待 猜 测 的 明 文 单 点 执 行 一 次 Oracle(Test) 查 询, 该 预 言 机 根 据 b 值 返 回 密 码 下 该 单 点 的 对 应 密 文 或 消 息 空 间 中 的 某 一 个 随 机 点. 攻 击 者 A 的 目 标 是 : 在 对 真 正 的 加 密 预 言 机 Oracle(nc)( 该 加 密 预 言 机 只 以 密 码 响 应 ) 进 行 一 定 次 数 适 应 性 的 查 询 后 ( 在 此 查 询 过 程 中, 禁 止 重 复 查 询, 禁 止 对 待 猜 测 单 点 进 行 查 询 ), 给 出 一 个 判 定 首 次 执 行 的 Oracle(Test) 查 询 得 到 的 结 果 是 选 定 单 点 所 对 应 的 密 文 还 是 待 加 密 消 息 空 间 中 的 某 个 随 机 点. 即 输 出 一 个 判 定 值 b. 如 果 b =b, 说 明 攻 击 者 A 判 定 成 功, 相 反, 则 失 败.A 在 该 游 戏 中 具 有 的 优 势 为 SPI A Adv ( A) = 2 Pr[SPI true] 1. MR 安 全 : 在 对 抗 消 息 恢 复 攻 击 方 面,MR 要 求 即 使 提 供 给 攻 击 者 加 密 预 言 机 和 明 文 的 概 率 分 布 以 及 格 式 调 整 因 子 等 信 息, 攻 击 者 也 不 能 从 密 文 得 到 明 文. 通 常 情 况 下, 如 果 加 密 是 完 全 随 机 的, 就 要 求 已 知 的 目 标 密 文 y * 和 能 够 访 问 加 密 预 言 机 Oracle(nc) 对 于 恢 复 明 文 是 无 用 的. 但 是 这 对 确 定 性 加 密 的 要 求 太 高, 因 为 攻 击 者 可 以 通 过 Oracle(nc) 查 询 消 息 x 1,,x q, 得 到 其 对 应 密 文 y 1,,y q. 如 果 存 在 某 个 y i =y *, 那 么 攻 击 者 就 可 以 知 道 待 猜 测 的 目 标 明 文 x * =x i.mr 安 全 就 是 规 范 此 类 攻 击 为 针 对 密 码 方 案 最 好 的 攻 击 方 式 ( 这 里, 最 好 以 成 功 概 率 来 衡 量 ). 即 对 于 方 案, 如 果 不 存 在 成 功 概 率 明 显 大 于 上 述 攻 击 的 攻 击 方 式, 则 认 为 达 到 了 MR 安 全. MR 安 全 的 定 义 基 于 游 戏 MR.MR 提 供 了 3 个 供 攻 击 者 查 询 的 预 言 机 :Oracle(nc),Oracle(q) 和 Oracle(Test). 其 中,Oracle(nc) 用 于 以 密 码 的 加 密 方 案 响 应 攻 击 者 的 加 密 查 询,Oracle(q) 允 许 攻 击 者 查 询 一 个 消 息 空 间 内 的 元 素 是 否 是 目 标 密 文 所 对 应 的 原 始 明 文 x *,Oracle(Test) 用 于 赋 予 攻 击 者 获 取 目 标 密 文 y * 的 能 力. 在 游 戏 开 始 前, 从 攻 击 范 围 中 随 机 选 取 一 个 目 标 明 文 x *, 然 后 执 行 保 留 格 式 加 密 算 法 得 到 其 对 应 密 文 y *, 最 后 将 加 密 所 用 到 的 格 式 信 息 和 调 整 因 子 (ω,t) 发 布 给 攻 击 者. MR 中 定 义 了 两 类 攻 击 者 : 攻 击 者 A 执 行 一 次 Oracle(Test) 查 询 和 q 次 Oracle(nc) 查 询 来 获 得 有 利 的 信 息 以 便 做 出 判 定 ; 攻 击 者 S 放 弃 Oracle(Test) 查 询, 而 使 用 q 次 的 Oracle(q) 查 询 来 替 换 Oracle(nc) 查 询. 无 论 是 A 还 是 S, 其 目 标 都 是 通 过 多 次 查 询 各 自 预 言 机 后, 输 出 一 个 对 目 标 明 文 的 猜 测 值 x, 如 果 x=x *, 说 明 攻 击 者 判 定 成

14 刘 哲 理 等 : 保 留 格 式 加 密 技 术 研 究 165 功, 否 则 失 败. 事 实 上,MR 安 全 目 标 度 量 了 攻 击 者 在 能 够 获 取 目 标 密 文 并 能 q 次 访 问 加 密 预 言 机 的 情 况 下, 与 最 一 般 的 攻 击 方 式 从 待 加 密 消 息 空 间 中 选 取 q 个 候 选 值 依 次 与 目 标 密 文 判 定 相 比, 成 功 的 概 率 差. 即, 攻 击 MR 者 A 在 该 游 戏 MR 中 具 有 的 优 势 为 Adv ( ) [MR A S true], A = Pr pa 其 中, pa = max [MR true]. S Pr MP 安 全 :MP 试 图 量 化 拥 有 加 密 预 言 机 的 攻 击 者, 从 目 标 密 文 中 计 算 其 对 应 的 目 标 明 文 被 某 函 数 作 用 后 所 得 到 的 结 果 的 能 力. MP 安 全 的 定 义 基 于 游 戏 MP. 类 似 于 MR,MP 也 提 供 了 3 个 预 言 机 :Oracle(nc),Oracle(q) 和 Oracle(Test), 以 及 两 类 攻 击 者 :A 和 S, 其 中,A 可 以 执 行 1 次 Oracle(Test) 和 q 次 Oracle(nc),S 可 以 执 行 q 次 Oracle(q). 不 同 之 处 在 于, 在 MP 中, 攻 击 者 不 仅 需 要 猜 测 明 文 信 息, 还 需 要 计 算 出 该 明 文 在 某 个 函 数 f 作 用 后 的 输 出 值, 并 将 该 输 出 值 与 目 标 明 文 在 f 下 的 作 用 结 果 进 行 比 较, 判 断 攻 击 是 否 成 功. 事 实 上,MP 可 以 看 作 是 MR 的 一 般 形 式 :MR 仅 仅 是 MP 中 f 为 恒 等 函 数 的 情 况. 因 此, 攻 击 者 A 在 游 戏 MP MR 中 具 有 的 优 势 为 Adv ( ) [MP A S true], A = Pr pa 其 中, pa = max [MP true]. S Pr 关 系 4 个 安 全 目 标 之 间 的 关 系 如 图 6 所 示. Fig.6 Relation of security goals 图 6 安 全 目 标 的 关 系 图 6 中, 实 箭 头 表 示 密 切 关 联 ( 就 是 能 推 导 出 ), 虚 箭 头 表 示 有 损. 通 过 图 6 可 以 看 出,PRP 是 保 留 格 式 加 密 的 标 准 安 全 目 标,SPI 是 PRP 的 一 个 变 种, 与 其 具 有 类 似 的 安 全 性, 虽 然 安 全 性 有 损, 但 可 以 达 到 比 PRP 更 好 的 安 全 边 界. 为 了 适 应 更 早 的 确 定 性 加 密 概 念,MP 把 语 义 安 全 带 给, 它 要 求 密 文 不 能 泄 露 真 实 信 息, 安 全 性 要 比 PRP 和 SPI 安 全 性 略 低. 最 基 本 也 是 最 常 用 的 安 全 性 要 求 就 是 对 抗 适 应 性 或 者 非 适 应 性 攻 击 下 的 MR,MR 从 整 体 上 使 对 手 无 力 从 消 息 的 密 文 得 到 信 息. SPI 概 念 来 源 于 文 献 [36],PRP 安 全 就 意 味 着 SPI 安 全, 但 在 优 势 边 界 上 有 额 外 q/m 的 损 失,q 是 攻 击 者 执 行 查 询 的 次 数,M=max ω Ω X ω 是 消 息 空 间 最 大 分 片 的 元 素 数 目, 但 并 不 影 响 SPI 作 为 一 种 安 全 工 具 来 使 用. 文 献 [36,37] 中 的 混 合 参 数 表 明,SPI 安 全 同 样 也 意 味 着 PRP 安 全. Bellare [9] 证 明 了 SPI 可 以 推 导 出 MP 安 全, 但 是 MP 安 全 不 能 推 导 出 SPI 安 全. 而 且,Bellare [9] 证 明 了 MP 可 以 推 导 出 MR 安 全, 而 相 反 不 成 立. 事 实 上,MP 的 目 标 与 MR 的 目 标 类 似, 不 同 之 处 就 是, 在 后 者 中, 攻 击 者 A 从 一 开 始 就 确 定 其 所 选 用 的 函 数 为 恒 等 函 数, 因 此,MR 安 全 是 MP 安 全 的 一 种 特 殊 形 式. 4.2 攻 击 模 型 PRP SPI MP MR 攻 击 者 根 据 利 用 的 条 件 可 以 采 用 不 同 的 攻 击 模 型, 常 见 的 攻 击 模 型 包 括 唯 密 文 攻 击 (ciphertext only attack) 选 择 明 文 攻 击 (chosen plaintext attack) 和 选 择 密 文 攻 击 (chosen ciphertext attack) 等. 进 一 步 地, 根 据 询 问 预 言 机 方 式 的 不 同, 可 分 为 非 适 应 性 攻 击 模 型 和 适 应 性 攻 击 模 型. 在 非 适 应 性 攻 击 模 型 中, 攻 击 者 在 开 始 询 问 之 前 就 选 好 询 问 的 全 部 内 容, 询 问 过 程 中 内 容 不 再 发 生 变 化 ; 而 在 适 应 性 攻 击 模 型 下, 攻 击 者 可 以 随 时 根 据 每 次 询 问 的 结 果 来 调 整 询 问 的 内 容. 显 然, 适 应 性 攻 击 强 度 比 非 适 应 性 攻 击 要 高. 在 设 计 加 密 方 案 时 主 要 关 注 的 攻 击 模 型 有 : 非 适 应 性 选 择 明 文 攻 击 (non-adaptive chosen plaintext attack, 简 称 CPA1) 适 应 性 选 择 明 文 攻 击 (adaptive chosen plaintext attack, 简 称 CPA2) 非 适 应 性 选 择 密 文 攻 击 (non-adaptive chosen ciphertext attack, 简 称 CCA1) 适 应 性 选 择 密 文 攻 击 (adaptive chosen ciphertext attack, 简 称 CCA2). 一 般 使 用 安 全 目 标 与 攻 击 模 型 相 结 合 的 方 式 来 定 义 加 密 方 案 的 安 全 性, 这 与 保 留 格 式 加 密 的 4 种 安 全 目 标 和 上 述 的 攻 击 模 型 相 结 合, 就 得 到 了 保 留 格 式 加 密 主 要 的 安 全 性, 比 如 PRP-CPA1,PRP-CPA2,PRP-CCA1, PRP-CCA2,MR-CPA1,MR-CPA2,MR-CCA1,MR-CCA2 等. 很 显 然,PRP-CCA2 具 有 最 高 的 安 全 性, 而 MR-CPA1

15 166 Journal of Software 软 件 学 报 Vol.23, No.1, January 2012 是 保 留 格 式 加 密 最 基 本 的 安 全 性. 如 果 攻 击 者 只 允 许 对 加 密 预 言 机 进 行 查 询, 而 不 允 许 查 询 解 密 预 言 机, 就 定 义 了 选 择 明 文 安 全 的 攻 击 模 型. 在 这 种 情 况 下, 如 果 要 求 攻 击 者 在 第 1 次 查 询 加 密 预 言 机 之 前 就 必 须 准 备 好 所 有 要 查 询 的 问 题, 则 定 义 了 非 自 适 应 性 选 择 明 文 攻 击 的 游 戏 模 型, 即 PRP-CPA1; 相 反 地, 如 果 允 许 攻 击 者 通 过 分 析 前 面 的 查 询 结 果 再 给 出 下 一 次 要 查 询 的 问 题, 那 么 就 定 义 了 自 适 应 性 选 择 明 文 攻 击 的 游 戏 模 型, 即 PRP-CPA2. 上 一 节 关 于 安 全 目 标 的 描 述 都 基 于 CPA 攻 击 模 型. 如 果 要 达 到 CCA 安 全 标 准, 上 述 的 游 戏 模 型 中 可 以 通 过 加 入 一 个 解 密 预 言 机 来 完 成, 比 如 在 PRP 游 戏 中 引 入 解 密 预 言 机 Oracle(Dec), 用 于 响 应 攻 击 者 的 解 密 查 询. 如 果 b=1, 解 密 预 言 机 Oracle(Dec) 以 保 留 格 式 加 密 方 案 对 输 入 的 密 文 进 行 解 密 并 响 应 ; 如 果 b=0, 解 密 预 言 机 Oracle(Dec) 以 随 机 选 取 的 方 式 置 换 P 对 输 入 的 密 文 进 行 解 密 并 响 应. 在 这 种 情 况 下, 如 果 攻 击 者 既 允 许 对 加 密 预 言 机 进 行 查 询, 又 允 许 对 解 密 预 言 机 进 行 查 询, 同 时 要 求 攻 击 者 在 第 1 次 查 询 加 密 预 言 机 之 前 就 必 须 准 备 好 所 有 要 查 询 的 问 题, 于 是 定 义 了 非 自 适 应 性 选 择 密 文 攻 击 的 游 戏 模 型, 即 PRP-CCA1; 相 反 地, 如 果 允 许 攻 击 者 通 过 分 析 前 面 的 查 询 结 果 再 给 出 下 一 次 要 查 询 的 问 题, 那 么 就 定 义 了 自 适 应 性 选 择 密 文 攻 击 的 游 戏 模 型, 即 PRP-CCA2. 5 应 用 领 域 及 待 解 决 的 问 题 [7] 自 2008 年 美 国 Voltage 公 司 公 布 其 安 全 产 品 所 使 用 的 技 术 的 白 皮 书 以 来, 得 到 了 更 多 研 究 学 者 的 关 注, 发 展 成 为 极 具 实 用 价 值 的 密 码 学 体 系 : 在 加 密 模 型 方 面, 提 出 的 典 型 模 型 ( 如 FFSM [8],Rt [9] 与 FFX 模 型 [10] ) 为 特 定 领 域 的 问 题 提 供 了 较 好 的 解 决 办 法 ; 在 应 用 研 究 方 面, 目 前 已 提 出 了 适 用 于 支 付 卡 行 业 安 全 的 [7] 信 用 卡 号 等 方 案 适 用 于 数 据 库 加 密 的 日 期 型 方 法 [19] [38] 满 足 格 式 兼 容 要 求 的 JPG2000 加 密 等 实 用 的 解 决 方 案, 开 拓 了 在 不 同 领 域 的 应 用 研 究. 5.1 应 用 领 域 由 于 保 持 密 文 与 明 文 具 有 相 同 格 式 的 特 性, 因 此 适 合 于 格 式 敏 感 的 数 据 加 密 领 域, 主 要 包 括 : 1) 增 强 数 据 库 应 用 系 统 的 安 全 性 在 数 据 库 中 加 密 数 据 一 直 是 一 个 难 题, 因 为 加 密 数 据 库 中 的 信 息 就 意 味 着 扩 充 数 据 并 改 变 格 式. 然 而, 多 数 大 型 商 用 应 用 系 统 都 是 基 于 数 据 库 的 应 用 系 统, 如 金 融 社 保 电 子 政 务 电 子 商 务 等, 如 果 数 据 库 中 存 储 的 大 量 用 户 敏 感 信 息 ( 如 银 行 卡 号 社 保 卡 号 用 户 名 和 密 码 等 ) 被 窃 取, 将 造 成 致 命 的 破 坏. 引 入 技 术, 将 极 大 地 提 高 数 据 库 的 安 全 性. 无 论 新 部 署 还 是 已 有 的 数 据 库 应 用 系 统, 都 可 以 引 入 技 术 增 强 系 统 安 全 性, 因 为 其 具 有 以 下 优 势 :1 不 改 动 现 有 软 件 系 统 的 代 码 ;2 不 改 动 现 有 数 据 库 结 构. 2) 数 据 遮 蔽 数 据 遮 蔽 源 于 解 决 数 据 从 生 产 环 境 向 测 试 环 境 ( 或 者 开 发 环 境 ) 导 入 时 可 能 产 生 的 数 据 内 容 安 全 问 题, 它 通 过 克 隆 原 始 数 据 进 行 掩 码 转 换, 输 出 一 个 与 原 数 据 格 式 关 联 等 一 模 一 样 的 数 据, 用 以 进 行 功 能 测 试 性 能 测 试 和 模 拟 测 试 等. 数 据 遮 蔽 内 嵌 丰 富 的 数 据 修 改 规 则, 通 过 各 种 复 杂 算 法, 可 以 自 动 批 量 快 速 地 完 成 对 敏 感 数 据 的 修 改, 同 时 保 证 克 隆 出 来 的 数 据 库 的 数 据 量 完 全 等 同 于 生 产 库 的 数 据 量 ; 敏 感 数 据 ( 如 身 份 证 号 电 话 号 码 信 用 卡 号 码 等 ) 又 作 了 伪 装, 看 起 来 是 真 实 数 据, 实 际 上 是 已 经 进 行 了 修 改 的 假 数 据, 从 而 消 除 了 敏 感 数 据 的 泄 露 隐 患. 如 果 充 分 且 合 理 利 用 的 话, 数 据 遮 蔽 必 成 为 保 障 数 据 安 全 的 重 要 技 术. 3) 支 付 卡 行 业 安 全 支 付 卡 行 业 数 据 安 全 标 准 (payment card industry data security standard, 简 称 PCI DSS) 是 一 套 被 广 为 接 受 的 政 策 和 程 序, 目 的 是 为 了 保 证 信 用 卡 借 记 卡 和 现 金 卡 交 易 的 安 全, 保 护 持 卡 人 的 个 人 信 息, 防 止 被 他 人 利 用. PCI DSS 所 规 定 和 阐 述 的 六 大 目 标 之 一 就 是 : 持 卡 人 信 息 无 论 存 在 哪 里, 都 必 须 受 到 保 护. 应 确 保 存 放 的 社 会 保 险 号 和 身 份 证 号 等 重 要 数 据 不 被 破 解. 当 持 卡 人 的 数 据 通 过 公 共 网 络 进 行 传 送 时, 这 些 数 据 必 须 经 过 有 效 的 加

16 刘 哲 理 等 : 保 留 格 式 加 密 技 术 研 究 167 密. 数 据 加 密 技 术 在 各 种 形 式 的 信 用 卡 交 易 中 都 是 非 常 重 要 的. 金 融 交 易 过 程 很 复 杂 约 束 也 很 多, 传 统 的 分 组 密 码 加 大 了 改 变 这 些 系 统 的 复 杂 度, 代 价 昂 贵. 而 因 为 实 现 简 单, 保 留 敏 感 信 息 的 格 式, 避 免 了 从 根 本 上 去 设 计 和 审 查 整 个 系 统 的 繁 杂. 4) 格 式 兼 容 的 加 密 领 域 除 了 对 上 述 敏 感 信 息 的 数 据 加 密 以 外, 还 非 常 适 合 于 遵 循 既 有 协 议 格 式 格 式 兼 容 的 数 据 加 密 的 应 用 领 域, 这 将 是 保 留 格 式 加 密 在 未 来 的 一 个 重 要 的 应 用 领 域. 比 如,2010 年,Stütz [38] 讨 论 了 在 多 媒 体 加 密 领 域 的 应 用, 指 出 方 法 可 以 应 用 到 JPG 2000 的 加 密 中.JPG 2000 的 加 密 有 两 类 解 决 方 案 : 在 图 像 压 缩 过 程 中 进 行 加 密 ; 对 压 缩 后 的 码 流 进 行 加 密. 技 术 应 用 于 后 者.JPG 2000 标 准 将 范 围 0xff90 至 0xffff 之 间 的 值 分 配 作 为 限 定 码 流 的 标 记 码, 通 常 存 在 于 包 头 中. 因 此, JPG 2000 压 缩 流 的 包 体 中 不 包 括 超 过 0xff8f 的 序 列, 且 不 以 0xff 结 尾. 为 了 保 证 加 密 后 的 图 像 仍 然 能 被 标 准 解 码 器 识 别 并 解 码, 必 须 满 足 不 产 生 多 余 的 标 记 字 段, 即 加 密 后 的 码 流 也 不 包 括 超 过 0xff8f 的 序 列, 且 不 以 0xff 结 尾 这 样 的 条 件.Stütz [38] 通 过 有 限 自 动 机 描 述 了 JPG 2000 压 缩 流 的 包 体 部 分, 从 而 将 这 个 加 密 问 题 转 化 为 了 正 则 语 言 上 的 问 题. 5.2 待 解 决 的 问 题 问 题 的 复 杂 性 在 于 待 解 决 问 题 消 息 空 间 的 复 杂 性, 已 有 的 模 型 为 特 定 领 域 的 问 题 提 供 了 较 好 的 解 决 办 法. 然 而, 目 前 的 研 究 工 作 还 存 在 很 多 亟 待 解 决 的 问 题, 主 要 包 括 : 1) 性 能 问 题 无 论 是 应 用 FFSM [8] [10], 还 是 FFX 模 型 来 解 决 任 意 有 限 域 上 的 问 题, 理 论 上 都 需 要 使 用 Cycle- Walking, 因 而 存 在 不 确 定 的 性 能 问 题. [9] Rt 方 法 较 通 用, 对 于 存 在 高 效 排 序 算 法 的 可 描 述 的 消 息 空 间, 可 以 通 过 排 序 后 加 密 的 思 想 达 到 保 留 格 式 加 密 的 目 的. 然 而, 并 不 是 所 有 消 息 空 间 都 存 在 高 效 的 排 序 算 法, 而 且 不 同 空 间 的 排 序 算 法 其 效 率 也 各 不 相 同, 因 此 无 法 定 量 考 核 Rt 方 法 的 性 能. 现 有 的 方 案 多 数 基 于 Feistel 网 络 来 构 造 指 定 分 组 长 度 的 对 称 密 码, 通 常 使 用 基 础 分 组 密 码 来 构 造 伪 随 机 函 数, 执 行 一 次 保 留 格 式 加 密 要 执 行 数 次 基 础 分 组 密 码, 相 比 基 础 分 组 密 码 性 能 偏 低. 因 此, 在 保 证 安 全 性 的 基 础 上, 优 化 Feistel 网 络, 或 者 采 用 其 他 构 建 方 式, 设 计 高 效 的 算 法, 仍 然 是 未 来 一 个 待 解 决 的 问 题. 2) 完 整 性 认 证 问 题 目 前 的 加 密 模 型 都 只 能 完 成 加 密, 而 不 能 对 消 息 提 供 完 整 性 认 证 功 能. 消 息 认 证 通 常 需 要 通 过 附 加 认 证 码 或 进 行 签 名 来 实 现, 这 意 味 着 要 扩 充 密 文 空 间, 与 确 保 密 文 和 明 文 在 相 同 的 消 息 空 间 是 一 种 矛 盾, 该 问 题 是 对 的 新 挑 战. 3) 解 决 实 际 应 用 存 在 的 关 键 问 题 为 保 留 数 据 的 类 型 和 长 度 提 供 了 相 对 完 美 的 解 决 方 案, 并 具 有 较 高 的 安 全 性. 然 而, 每 种 应 用 问 题 都 具 有 特 定 的 格 式 要 求 或 者 某 些 约 束, 需 要 为 此 量 身 定 制, 而 且 由 于 加 密 破 坏 了 明 文 数 值, 可 能 会 违 背 一 些 应 用 的 约 束, 从 而 增 加 了 应 用 的 难 度. 一 个 的 典 型 应 用 难 题 是 在 数 据 库 加 密 中 的 关 键 问 题, 由 于 加 密 破 坏 了 明 文 数 值, 使 其 无 法 满 足 常 规 数 据 库 的 一 些 查 询 和 聚 集 操 作, 若 要 对 加 密 的 字 段 进 行 模 糊 查 询 或 者 统 计 平 均 求 和 等 数 学 运 算 很 困 难, 该 问 题 也 是 制 约 保 留 格 式 加 密 应 用 到 数 据 库 加 密 中 的 关 键 问 题. 如 果 对 所 有 加 密 数 据 进 行 解 密, 然 后 再 执 行 查 询 聚 集 操 作, 由 于 解 密 操 作 开 销 巨 大, 这 将 对 查 询 性 能 造 成 极 大 影 响. 因 此, 如 果 将 广 泛 应 用 到 数 据 库 加 密 中, 需 要 找 到 一 种 机 制, 既 能 保 证 其 安 全 性, 又 不 会 对 查 询 聚 集 操 作 等 性 能 产 生 较 大 影 响. [39 42] 与 该 问 题 相 关 的 两 类 研 究 领 域 为 保 序 加 密 和 秘 密 同 态. 保 序 加 密 是 一 种 对 数 值 型 数 据 保 留 顺 序 的 加 [43 45] 密 方 案, 它 允 许 在 密 文 上 直 接 进 行 比 较 等 操 作, 而 不 需 要 对 其 进 行 解 密. 秘 密 同 态 是 指 通 过 构 造 明 文 空 间 上 的 秘 密 同 态 函 数, 实 现 在 不 进 行 解 密 的 情 况 下 直 接 对 密 文 进 行 数 学 运 算 等.

17 168 Journal of Software 软 件 学 报 Vol.23, No.1, January 2012 如 何 在 中 引 入 保 序 和 同 态 的 性 质, 使 其 支 持 常 规 数 据 库 的 一 些 查 询 和 聚 集 操 作, 从 而 更 好 地 应 用 到 数 据 库 加 密 领 域, 将 是 未 来 研 究 的 一 个 挑 战. 6 结 论 本 文 关 注 近 年 来 保 留 格 式 加 密 研 究 的 进 展, 主 要 从 基 本 方 法 加 密 模 型 的 构 造 安 全 性 等 角 度 对 已 有 的 研 究 成 果 进 行 了 总 结 分 析, 以 期 对 保 留 格 式 加 密 在 国 内 的 研 究 起 到 一 定 的 推 动 作 用. 从 构 造 角 度, 一 方 面,Generalized-Feistel 方 法 得 到 了 更 多 的 关 注, 模 型 通 常 都 采 用 Feistel 网 络 来 构 造 满 足 要 求 的 对 称 密 码. 常 见 的 Feistel 网 络 类 型 主 要 包 括 传 统 Feistel 网 络 ( 平 衡 Feistel 网 络 ) 非 平 衡 Feistel 网 络 交 互 式 Feistel 网 络 及 以 上 类 型 的 数 值 形 式, 它 们 都 是 2- 分 割 的 Feistel 网 络 类 型, 即 将 输 入 划 分 为 左 右 两 部 分. 最 近,l- 分 割 的 Type-2 Feistel 网 络 也 被 应 用 到 构 建 方 案 中 ; 另 一 方 面, 模 型 的 设 计 思 想 逐 渐 向 降 低 问 题 域 的 复 杂 性 方 向 发 展, 无 论 是 Rt 方 法 还 是 FFX 模 型, 都 将 问 题 转 化 到 等 价 的 具 有 较 低 复 杂 度 的 整 数 集 上. 这 种 通 过 降 低 问 题 域 的 复 杂 性 来 解 决 复 杂 消 息 空 间 上 的 问 题 的 解 决 方 法, 将 会 成 为 保 留 格 式 加 密 领 域 的 一 种 可 采 纳 的 有 效 研 究 手 段. 从 安 全 性 角 度, 保 留 格 式 加 密 主 要 有 4 种 安 全 目 标 :PRP,SPI,MP 和 MR, 本 文 介 绍 了 这 些 安 全 目 标 并 详 细 描 述 了 与 之 相 关 的 游 戏 模 型.PRP 是 保 留 格 式 加 密 的 标 准 安 全 目 标 ;SPI 是 PRP 的 一 个 变 种, 与 其 具 有 类 似 的 安 全 性, 虽 然 安 全 性 有 损, 但 可 以 达 到 比 PRP 更 好 的 安 全 边 界 ;MP 把 语 义 安 全 带 给, 它 要 求 密 文 不 能 泄 露 真 实 信 息, 安 全 性 要 比 PRP 和 SPI 略 低 ; 最 基 本 也 是 最 常 用 的 安 全 性 要 求 就 是 对 抗 适 应 性 或 者 非 适 应 性 攻 击 下 的 MR, MR 从 整 体 上 使 对 手 无 力 从 密 文 得 到 明 文. 保 留 格 式 加 密 主 要 关 心 的 攻 击 模 型 主 要 包 括 4 种 :CPA1,CPA2,CCA1, CCA2. 使 用 安 全 目 标 与 攻 击 模 型 相 结 合, 可 以 定 义 保 留 格 式 加 密 的 安 全 性. 在 所 定 义 的 安 全 性 中, PRP-CCA2 具 有 最 高 的 安 全 性,MR-CPA1 是 保 留 格 式 加 密 最 基 本 的 安 全 性. [7] 随 着 2008 年 Voltage 公 司 白 皮 书 的 公 布, 问 题 逐 渐 成 为 密 码 学 领 域 中 的 一 个 研 究 热 点. 当 前 已 有 一 些 研 究 成 果 : 在 加 密 模 型 方 面, 提 出 的 典 型 模 型 ( 如 FFSM [8],Rt [9] 与 FFX 模 型 [10] ) 为 特 定 领 域 的 问 题 提 供 了 较 好 的 解 决 办 法 ; 在 应 用 研 究 方 面, 已 提 出 了 适 用 于 支 付 卡 行 业 安 全 的 信 用 卡 号 等 方 案 [7] 适 用 于 数 据 库 加 密 的 日 期 型 方 法 [19] 满 足 格 式 兼 容 要 求 的 JPG 2000 加 密 等 实 用 的 解 决 方 案 [38], 开 拓 了 在 不 同 领 域 的 应 用 研 究. 然 而, 由 于 保 留 格 式 加 密 待 解 决 的 问 题 域 的 复 杂 性, 目 前 的 研 究 工 作 还 存 在 很 多 亟 待 解 决 的 问 题 : 如 性 能 问 题 完 整 性 认 证 问 题 以 及 解 决 实 际 应 用 存 在 的 关 键 问 题 等, 都 是 需 要 进 一 步 解 决 的 问 题. References: [1] Radhakrishnan R, Kharrazi M, Memon N. Data masking: A new approach for steganography? The Journal of VLSI Signal Processing, 2005,41(3): [doi: /s ] [2] Smith H, Brightwell M. Using datatype-preserving encryption to enhance data warehouse security. In: Proc. of the 20th National Information Systems Security Conf [3] National Bureau of Standards. FIPS PUB 74, Guidelines for Implementing and Using the NBS Data ncryption Standard, [4] Black J, Rogaway P. Ciphers with arbitrary finite domains. In: Preneel B, ed. Proc. of the Topics in Cryptology CT-RSA LNCS 2271, San Jose: Springer-Verlag, [doi: / _9] [5] Luby M, Rackoff C. How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal of Computing, 1988,17(2): [doi: / ] [6] Patarin J. Security of random Feistel schemes with 5 or more rounds. In: Franklin M, ed. Advances in Cryptology CRYPTO LNCS 3152, Santa Barbara: Springer-Verlag, %20Format%20Springer.pdf [doi: / _7] [7] Spies T. Format preserving encryption. Unpublished Voltage White Paper WhitePaper-Format-Preserving-ncryption.pdf [8] Spies T. Feistel finite set encryption mode ffsem-spec.pdf

18 刘 哲 理 等 : 保 留 格 式 加 密 技 术 研 究 169 [9] Bellare M, Ristenpart T, Rogaway P, Stegers T. Format-Preserving encryption. In: Jacobsn MJ, eds. Proc. of the Selected Areas in Cryptography (SAC 2009). LNCS 5867, Calgary: Springer-Verlag, [doi: / _19] [10] Bellare M, Rogaway P, Spies T. The FFX mode of operation for format-preserving encryption toolkit/bcm/documents/proposedmodes/ffx/ffx-spec.pdf [11] Schneier B, Kelsey J. Unbalanced Feistel networks and block cipher design. In: Gollmann D, ed. Proc. of the Fast Software ncryption 96. LNCS 1039, Cambridge: Springer-Verlag, [doi: / _49] [12] Liskov M, Rivest RL, Wagner D. Tweakable block ciphers. In: Advances in Cryptology CRYPTO LNCS 2442, Santa Barbara: Springer-Verlag, [doi: /s y] [13] ric B, Thomas P, Jacques S. BPS: A format-preserving encryption proposal. An NIST Submitted Proposal, nist.gov/groups/st/toolkit/bcm/documents/proposedmodes/bps/bps-spec.pdf [14] National Institute of Standards and Technology. SP800-67: Recommendation for the triple data encryption algorithm (TDA) block cipher [15] National Institute of Standards and Technology. FIPS 197: Advanced ncryption Standard fips/fips197/fips-197.pdf [16] National Institute of Standards and Technology. FIPS 180-2: Secure Hash Standard fips180-2/fips180-2.pdf [17] Morris B, Rogaway P, Stegers T. How to encipher messages on a small domain Deterministic encryption and the thorp shuffle. In: Advances in Cryptology CRYPTO Santa Barbara: Springer-Verlag, thorp.pdf [doi: / _17] [18] Jia CF, Liu ZL, Li JW, Dong ZQ, You XY. A new integer scheme based on Feistel network. In: Zhu X, ed. Proc. of the Int l Conf. on Services Science Management and ngineering Tianjin: I Press, [19] Liu ZL, Jia CF, Li JW, Cheng XC. Format-Preserving encryption for datetime. In: Chen W, ed. Proc. of the Intelligent Computing and Intelligent Systems 2010, Vol.2. Xiamen: I Press, [doi: /ICICISYS ] [20] Cover T. numerative source encoding. I Trans. on Information Theory, 1973,19(1): [doi: /TIT ] [21] Mäkinen. Ranking and unranking left Szilard languages. Int l Journal of Computer Mathematics, 1998,68(1-2): [doi: / ] [22] Knuth D. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms. 3rd ed., Addison-Wesley, [23] Kelsen P. Ranking and unranking trees using regular reductions. In: Puech C, ed. Proc. of the 13th Annual Symp. on Theoretical Aspects of Computer Science. LNCS 1046, Grenoble: Springer-Verlag, p2x337k42l09w032.pdf [doi: / _47] [24] Liebehenschel J. Ranking and unranking of a generalized DYCK language and the application to the generation of random trees. In: Séminaire Lotharingien de Combinatoire [25] Hoang VT, Rogaway P. On generalized Feistel networks. In: Rabin T, ed. Advances in Cryptology CRYPTO LNCS 6223, Santa Barbara: Springer-Verlag, [doi: / _33] [26] Anderson R, Biham. Two practical and provably secure block ciphers: BAR and LION. In: Gollmann D, ed. Proc. of the Fast Software ncryption 96. LNCS 1039, Cambridge: Springer-Verlag, P3L22063H7817J35.pdf [doi: / _48] [27] Lucks S. Faster Luby-Rackoff ciphers. In: Gollmann D, ed. Proc. of the Fast Software ncryption 96. LNCS 1039, Cambridge: Springer-Verlag, [doi: / _53] [28] Zheng YL, Matsumoto T, Imai H. On the construction of block ciphers provably secure and not relying on any unproved hypotheses. In: Brassard G, ed. Proc. of the 9th Annual Int l Cryptology Conf. LNCS 435, Berlin: Springer-Verlag, ftp:// [doi: / _42] [29] Goldwasser S, Micali S. Probabilistic encryption. Journal of Computer and System Sciences, 1984,28(2): [doi: / (84) ] [30] Micali S, Rackoff C, Sloan R. The notion of security for probabilistic cryptosystems. SIAM Journal on Computing, 1988,17(2): [doi: / ] [31] Dolev D, Dwork C, Naor M. Nonmalleable cryptography. SIAM Journal on Computing, 2000,30(2): [doi: / S ]

19 170 Journal of Software 软 件 学 报 Vol.23, No.1, January 2012 [32] Bellare M, Rogaway P. Optimal asymmetric encryption How to encrypt with RSA. In: De Santis A, ed. Advances in Cryptology-UROCRYPT 94. LNCS 950, Perugia: Springer-Verlag, [33] Bellare M, Rogaway P. Random oracles are practical: A paradigm for designing efficient protocols. In: Proc. of the 1st ACM Conf. on Computer and Communications Security. Fairfax: ACM Press, [doi: / ] [34] Goldreich O. A uniform complexity treatment of encryption and zero-knowledge. Journal of Cryptology, 1993,6(1): [doi: /BF ] [35] Goldreich O. Foundations of Cryptography, Vol II: Basic Applications. Cambridge: Cambridge University Press, [36] Goldreich O, Goldwasser S, Micali S. How to construct random functions. Journal of the ACM, 1986,33(4): [doi: / ] [37] Desai A, Miner S. Concrete security characterizations of PRFs and PRPs: Reductions and applications. In: Okamoto T, ed. Advanced in Cryptology- ASIACRYPT LNCS 1976, Kyoto: Springer-Verlag, viewdoc/download?doi= &rep=rep1&type=pdf [doi: / _39] [38] Stütz T, Uhl A. fficient format-compliant encryption of regular languages: Block-Based Cycle-Walking. In: De Decker B, ed. Proc. of the 11th IFIP TC 6/TC 11 Int l Conf. LNCS 6109, Linz: Springer-Verlag, pdf [doi: / _9] [39] Ozsoyoglu, G, Singer DA, Chung SS. Anti-Tamper databases: Querying encrypted databases. In: Proc. of the 17th Annual IFIP WG, Vol [40] Agrawal R, Kiernan J, Srikant R, Xu YR. Order preserving encryption for numeric data. In: Proc. of the 2004 ACM SIGMOD Int l Conf. on Management of Data. New York: ACM Press, [doi: / ] [41] Boldyreva A, Chenette N, Lee Y, O Neill A. Order-Preserving symmetric encryption. In: Joux A, ed. Advances in Cryptology-UROCRYPT LNCS 5479, Perugia: Springer-Verlag, eurocrypt2009/ / pdf [doi: / _13] [42] Lee S, Park TJ, Lee D, Nam T, Kim S. Chaotic order preserving encryption for efficient and secure queries on databases. IIC Trans. on Information and Systems, 2009,92-D(11): [doi: /transinf.92.D.2207] [43] Rivest RL, Adleman L, Dertouzos ML. On data banks and privacy homomorphisms. Foundations of Secure Computation, 1978, [44] Gentry C. Fully homomorphic encryption using ideal lattices. In: Proc. of the 41st Annual ACM Symp. on Theory of Computing (STOC 2009). New York: ACM Press, [doi: / ] [45] Van Dijk M, Gentry C, Halevi S, Vaikuntanathan V. Fully homomorphic encryption over the integers. In: Gilbert H, ed. Advances in Cryptology-UROCRYPT LNCS 6110, Perugia: Springer-Verlag, [doi: / _2] 刘 哲 理 (1978-), 男, 山 东 潍 坊 人, 博 士, 主 要 研 究 领 域 为 密 码 学 及 应 用, 智 能 卡 操 作 系 统. 李 经 纬 (1987-), 男, 博 士 生, 主 要 研 究 领 域 为 密 码 学. 贾 春 福 (1967-), 男, 博 士, 教 授, 博 士 生 导 师, 主 要 研 究 领 域 为 信 息 安 全 与 可 信 计 算, 恶 意 代 码 发 现 与 分 析.