算法攻击（精选7篇）
算法攻击 篇1
0引言
随着计算 机技术的 发展 、社会信息 化程度的 不断提高 , 安全问题 越来越受 到人们的 广泛重现 , 因此各种 形式的专 用密码电 路和密码 算法处理 器被广泛 地应用于 各类产品 中 。 分组密码 算法是一 种最常用 的加密手 段 , 具有速度 快 、易于标准 化和便于 软硬件实 现等特点 。 目前比较 流行的分 组密码算 法有DES算法 、AES算法等 , 其中DES[1]是目前使 用非常广 泛的数据 加密方法 , 它于1977年被美国 国家标准 局作为第46号联邦信 息处理标 准而采用 。
传统的密 码分析方 法是采用 数学的分 析手段 。 近年来随 着测量分 析方法的 进步 ,各种分析 攻击方法 也不断发 展 ,差分功耗 攻击和故 障攻击是 具有代表 性且对智 能卡芯片 威胁性较 强的两种 攻击方法 。 差分功耗 攻击是1998年由Paul Kocher等[2]提出 , 它利用了 密码设备 运行期间 泄露的侧 信息与密 码算法的 中间值有 一定的相 关性 , 通过多次 测量侧信 息后进行 统计分析 , 进而获得 密钥信息 。 故障攻击 的基本原 理是将密 码芯片置 于强磁场 中 , 或者改变 芯片的电 源电压 、 工作频率 、 温度等 , 使密码芯 片中的寄 存器 、存储器在 加解密过 程中产生 随机错误 , 某些输出 比特从原 来的0变成1或1变成0。 通过对正 确密文输 出和错误 密文输出 的比较 ,经过理论 分析得到 芯片内部 的秘密数 据信息 。
国内外对 于差分功 耗攻击和 故障攻击 防御方面 的研究和 技术方法 也不断涌 现 ,防御差分 功耗攻击 的方法包 括 : 随机掩码 、 动态双轨 电路技术 、 随机伪操 作等 , 防御故障 攻击的方 法主要包 括对相同 的数据计 算多次后 比较运算 结果是否 一致 。 但有的防 御方法往 往会增加 实现代价 ,而计算多 次比较运 算结果又 会降低算 法运算效 率 。 本文以DES算法为例 ,提出了分 组密码算 法的一种 有效防护 方法 , 可以同时 抵御差分 功耗攻击 和故障攻 击 。 采用流水 线技术同 一时钟周 期内有不 同的轮运 算操作叠 加 , 增加了正 常加解密 运算的噪 声 , 可以抵抗 侧信道攻 击 , 同一明文 依次进入 不同级的 流水线进 行运算 , 最后比较 运算结果 是否一致 ,可以抗故 障攻击 。 通过对电路 的仿真和 分析 ,验证了其 良好的抗 攻击性能 。
1DES差分功耗分析及故障攻击
DES是一个分组算法 , 使用长度 为56 bit的密钥加 密长度为64 bit的明文 ,获得长度 为64 bit的密文 。 它的加密 过程如下 :
( 1 ) 给定明文m , 对m进行一个 固定的初 始IP置换 。
( 2 ) 然后进行16轮完全相 同的运算 , 将数据与 密钥相结 合 。 在16轮操作的 每一轮中 ,DES都会进行8次S盒查表操 作 。 这S盒的输入 为6 bit的密钥与E扩展后的6 bit R寄存器的 异或值 , 输出为4 bit。 32 bit的S盒输出经 过P置换 , 然后与L寄存器的 值进行异 或 , 接着将L和R的值进行 交换 。
( 3 ) 进行初始 置换的逆 置换 , 得到密文 。 具体过程 如图1所示 。
1.1差分功耗分析
目前绝大 多数集成 电路均采 用CMOS工艺制作 , CMOS门级电路 的功耗模 型[3]为 :
其中Pswitch为逻辑门 翻转引起 负载电容 充放电导 致的功耗 ;Pshort_circuit为短路电 流导致的 功耗 ;Pleakage为泄漏电 流导致的 功耗 。 其中Pswitch是电路功 耗的主要 部分 ,功耗
大小与逻 辑门是否 翻转有密 切关系 ,因此电路 中运算数 据的0、1状态与电 路的功耗 必然具有 一定的相 关性 ,这个特性 是DPA攻击的物 理基础 。
以DES算法为例 ,DPA攻击的主 要步骤如 下 :
( 1 ) 随机生成 大量明文 , 加密这些 明文并记 录下加密 操作时的 功耗曲线 。
( 2 ) 关注第一 轮第一个S盒输出的 第一比特b , 猜测第一 个S盒对应的6 bit密钥 , 并用其与 相应的明 文计算出b。
( 3 ) 根据b的值 , 将能耗曲 线按照b = 0和b = 1分为两类 。
( 4 ) 计算出这 两类的平 均能耗曲 线 , 并将二者 相减求得 差分能耗 曲线 。
( 5 ) 观察步骤 ( 4 ) 生成的能 量曲线 。 若密钥猜 测正确 , 则步骤 (3) 的分组就 是正确的 , 差分能耗 曲线中将 出现明显 的峰值 。 因此攻击 者通过观 察峰值来 判断密钥 的猜测是 否正确 。
( 6 ) 重复步骤 ( 2 ) ~ ( 5 ) , 得到其他 的子密钥 。
这样 , 通过差分 迹中的尖 峰 , 就可以确 定出完整 的48 bit密钥信息 。 再使用穷 举搜索或 继续分析 下一轮等 方法 ,可以很容 易地确定 出剩下的8 bit密钥 。
1.2故障攻击
故障攻击 是通过将 故障引入 到芯片中 , 如改变芯 片的工作 频率或工 作电压 , 使得芯片 工作不正 常 , 从而获得 芯片内部 关键信息 。
Biham和Shamir提出了对DES算法的差分故障分析[4], 该攻击的 基本方法 如下 : 攻击者对 同一明文 加密两次 , 其中一次 正常加密 , 另外一次 在加密的 第15轮运算时 引入故障 ,使得芯片 输出错误 运算结果 。 攻击者通 过记录正 确加密结 果和错误 结果并对 这两个结 果进行数 学分析 ,即可获得 密钥的相 关信息 。
如图2所示 ,攻击者在 第15轮的f函数运算 期间注入 故障 ,则有 :
其中R16′ 和R15′ 分别是R16和R15对应的错 误值 , 通过对上面 的两个等 式两边异 或可以得 到 :
在该等式 中只有K16是未知的 , 通过解方 程即可获 得密钥信 息 。
2DES算法抗差分功耗攻击和故障攻击设计
流水线的 概念在数 字电路中 应用得很 广 , 它是加快 数字电路 的有效手 段 ,在分组密 码算法中 应用得同 样很广泛 , 如DES、AES等分组加 密算法都 有相关的 流水线实 现方案 。
本文通过 把流水线 技术与抗 差分功耗 分析和故 障攻击相 结合 , 同一明文 进入不同 级的流水 线进行运 算 , 其他级流 水线的输 入为随机 数 ,这样在同 一时钟周 期内有不 同的运算 操作叠加 , 增加了正 常运算的 噪声 , 可以抵抗 差分功耗 攻击 ;通过比较 同一明文 的运算结 果是否一 致 , 来检测运 算过程中 是否有故 障注入 , 可以抵抗 故障攻击 。
如图3所示 ,DES算法采用 四级流水 线 , 每级流水 线进行4轮运算 。 图中虚线 部分表示 随机数参 与该级流 水线运算 。
首先产生 所需的随 机数 , 一个随机 数用于确 定这四级 流水线中 哪两级的 输入为真 实的明文P, 两个随机 数作为随 机明文进 入另外两 级流水线 ,两个随机 数分别作 为密钥用 于为两个 随机明文 产生随机 轮密钥 。
这里不妨 假设前两 级流水线 的输入为 真实的明 文 , 后两级输 入为随机 数 。 待真实明 文的两级 流水线运 算完成后 对这两个 密文进行 比较 ,若一致则 说明运算 过程中没 有注入故 障 ,可输出正 确密文 ;否则返回 错误信息 。
当然 , 为增加抗 攻击能力 , 本文的方 法可以与 其他防护 方法相结 合 ,如每一级 的流水线 在实现时 可以引入 随机掩码 ,这样抗差 分功耗攻 击的效果 会更好一 些 。
3实验仿真及分析
以DES算法中轮 输出的寄 存器为攻 击点 ,采用汉明 距离模型 ,通过仿真 实验对本 文防护方 法的有效 性进行验 证 。
对标准的DES算法和本文的防护方法分别进行VLSI设计 ,采样后采 用Riscure公司的Inspector侧信道分 析平台对 其FPGA实现进行 分析 , 结果如图4所示 。 对于标准 的DES算法 , 分析第一 轮中的第 一个S盒 , 当猜测到 密钥为0x00时会出现明显的尖峰,这说明密钥猜测正确 ; 对于本文 的防护方 法 ,当猜测到 密钥仍为0x00时没有出 现明显的 尖峰 ,说明本方 法可以有 效的抵抗 功耗分析 。
4结论
本文以DES算法为例 ,给出了一 种既可以 抵抗差分 功耗分析 ,又可以抵 抗故障攻 击的分组 密码算法 防护方法 , 采用流水 线技术不 仅增加了 正常加解 密运算的 噪声 ,同一明文 依次进入 不同级的 流水线比 较运算结 果是否一致 ,可以抗故 障攻击 。 通过实验 验证 ,本方法可 以有效地 抵抗攻击 。
ARP攻击与防范算法改进 篇2
关键词：ARP协议,攻击,防范算法,改进
ARP攻击是发生在局域网中的一种基于计算机MAC地址的攻击方法。受到ARP攻击的网络一般表现为, 局域网中某些计算机网络连接时通时断。ARP攻击的发生通常是由于局域网中某些计算机感染了ARP木马病毒, 或有人故意使用ARP攻击工具所致。
1. ARP协议的运作方式
ARP协议的作用是将网络地址解析为物理地址。任何通信活动, 无论使用哪一种第三层的网络协议, 最终都要封装在各种各样的第二层协议的帧中进行传输。因此, 只有网络地址是不够的, 还需要知道对应的物理地址, 才能正确传输。主机通过IP地址进行通信时, 由于数据链路层只能识别MAC地址, 所以需要一种方法来完成IP地址到MAC地址的映射, 这就要用到地址解析协议ARP。在每个主机中都有一个ARP高速缓存, 里面是所在局域网上的各主机和路由器的IP地址到硬件地址的映射表, ARP协议的职责就是动态的维护该表。当源主机欲向本局域网上的某个目标主机发送IP分组时, 就先在其ARP高速缓存中查看有无目标主机的IP地址。如有, 就可查出其对应的硬件地址, 再将此硬件地址写入MAC帧, 然后通过局域网将该MAC帧发往此硬件地址。如果没有, 则先通过广播ARP请求分组, 在获得目标主机的ARP响应分组后, 将目标主机的硬件地址写入ARP高速缓存中目标主机的IP地址到硬件地址的映射。ARP是解决同一个局域网上的主机或路由器的IP地址和硬件地址的映射问题。如果所要找的主机和源主机不在同一个局域网上, 那么就要通过ARP找到一个位于本局域网上的某个路由器的硬件地址, 然后把分组发送给这个路由器, 让这个路由器把分组转发给下一个网络。剩下的工作就由下一个网络来做。ARP是IP层协议。
2. ARP攻击原理
我们知道, 局域网中计算机间的通信不是根据IP地址进行的, 而是按照MAC地址进行传输。局域网内的传输都要通过ARP协议把IP地址转换成MAC地址后传输。在一个使用TCPIP协议的网络环境中, 一个数据包发往何处及怎样发送依靠保存在路由器或交换机中的路由表决定。但当数据包到达该网络后, 哪台计算机响应这个数据包则是靠该数据包中包含的MAC地址来识别。也就是说, 只有MAC地址和该数据包中指定的MAC地址相同的机器才会应答这个数据包。
从以上介绍中可以看出, ARP攻击者在攻击成功后会得到网络中被攻击计算机发往外部网络的全部数据, 其中可能包括邮箱账号、游戏账号、QQ密码、银行账号等敏感数据。如果ARP攻击者在自己的计算机中配合运行Sniffer一类的网络嗅探工具 (抓包工具) , 就有可能分析和破解这些数据。ARP攻击的形式有许多, 上面介绍的仅是其中一种。但所有ARP攻击的原理都是相同的, 导致的后果也基本一致。
3. ARP攻击防范算法
从ARP攻击的原理可以看出, ARP协议的基础是局域网各主机之间互相信任, 在结构上存在着一系列的安全漏洞, 包括广播、动态、不受控制和无需认证等。由于结构上的漏洞问题, 所以ARP攻击的有效率相当高, 预防也比较困难。很多方法都能够提高ARP协议的安全性, 但很少能有从根本上解决ARP攻击的方法。而根据局域网终端内部着手, 所提出的ARP攻击防范方法, 具有更高的适应性, 具体思路为:检测所有主机的ARP报文一致性, 将报文中头信息不一致的抛弃;探测方式为主动, 要求ARP报文的发送方的身份认证, 拒收并警告非法的报文;ARP报文的接收顺序为先请求后应答, 拒绝应答中无请求的部分, 从而防范来自其他主机的攻击;检查发送报文中源IP与MAC地址是否为本机地址, 避免主机由于非法入侵而发动ARP攻击。基于这种思路构建的ARP防范算法由ARP头信息检测、ARP攻击检测和ARP过滤三部分组成。
(1) ARP头信息检测
ARP报文数据帧的报头与分组信息中都有报文发送机器的唯一硬件地址, MAC地址。正常状态下的数据报文中, 报文数据帧的MAC地址与分组信息中的MAC地址相同, ARP报文才是安全正确的。该算法描述如下:
(2) ARP攻击检测
报文数据帧的MAC地址与分组信息中的MAC地址相同, 也不能完全判定ARP报文的正确性, 攻击或欺骗的ARP报文在高明的策略中能够充分利用正确的报文或者模仿出格式正确能够通过的ARP报文而进行攻击。而如果能够针对ARP报文进行报文发送的身份认证, 将认证不能通过的报文抛弃, 能够将ARP报文中的攻击和欺骗的部分检测识别出。以ARP报文中IP地址与MAC地址等信息接收为基础, 构造出对应的上层协议数据包, 在网络中发布, 将数据报文及其IP地址和MAC地址的响应与否, 能够对ARP报文中IP地址和MAC地址进行真实验证。
(3) ARP过滤
在接收的ARP请求报文中, 每个ARP广播中都包含发送方的IP到MAC地址的绑定, 在目前大部分操作系统在ARP协议实现中, 对目的地址是本机的ARP请求除了发送ARP应答响应外, 为了避免额外的网络流量, 还会更新它们ARP缓存中IP到MAC地址的绑定信息。算法描述如下:
3. 结束语
ARP协议的基础是局域网各主机之间互相信任, 在结构上存在着一系列的安全漏洞, 包括广播、动态、不受控制和无需认证等。由于结构上的漏洞问题, 所以ARP攻击的有效率相当高, 预防也比较困难。根据ARP攻击方式而开发的算法, 具有更灵活、准确、全面的优点, 对于安全性要求高的网络比较适合。
参考文献
[1]陈晨, 韩宪忠, 王克俭.一种基于报文过滤防御ARP欺骗的系统架构[J].河北农业大学学报, 2009, (03) .
[2]张洁, 武装, 陆倜.一种改进的ARP协议欺骗检测方法[J].计算机科学, 2008, (03) .
算法攻击 篇3
由于旁道攻击(Side Channel Attacks)技术的攻击设备和手段简单,对密码芯片的安全构成巨大威胁。 而能量分析攻击(Power Analysis Attack)[3]是旁道攻击的一种常用技术,分为简单能量分析SPA(Simple Power Analysis) 攻击和差分能量分析DPA(Differential Power Analysis) 攻击两大类。 因此标量乘算法的设计与实现也应考虑到SPA和DPA攻击的威胁, 进而提高算法的安全性。
参考文献[4]通过仿真实验证明了Montgomery Ladder标量乘算法不能抵御DPA攻击;参考文献[5]给出了加入随机冗余操作降低信噪比来抗DPA攻击的方法,但大幅增加了电路面积与功耗。 本文将随机化的思想与Montgomery标量乘算法的特点相结合, 提出了随机Z坐标的抗DPA攻击的改进算法, 并仿真验证了该改进算法的抗DPA攻击能力。
1 Montgomery标量乘算法的安全性分析
Montgomery标量乘算法[6]具有计算效率高、 所需资源少等优点,在工程实现上被广泛运用,该算法是利用准投影坐标给出的、能代表一类投影坐标实现的标量乘算法,所以本文选取该算法进行研究,算法流程如下:
算法1:Montgomery标量乘算法
输入:参数组k=(kt - 1, … ,k1,k0)2
其中
输出:kP。
(1) X1←x,Z1←1,X2←x4+b ,Z2←x2。 {(P ,2P)}
(2) 对于i从t - 2到0 , 重复执行 :
①若 ki= 1 , 则 :
②否则:
SPA攻击和时间攻击要求密钥对功耗有显著的影响,攻击者需掌握密码设备的详细实现细节,根据测量到的功耗轨迹,沿时间轴来分析加密设备在某一时刻执行的运算操作,从而推测与操作相关的密钥信息[7]。 观察Montgomery标量乘算法的步骤2可以发现,无论ki=1还是ki=0 , 都会进行相同的运算操作, 无法通过直接分析功耗轨迹来推测密钥,因此该算法可以抵抗SPA攻击和时间攻击。
DPA攻击利用密码设备能量消耗的数据依赖性, 使用大量的能量迹来分析固定时刻设备的能量消耗,进而获取运算过程中的不变量(例如密钥信息)[7]。 为了分析方便,把算法1中的步骤2等效成下面的形式:
若 ki=1 , 则 P1←P1+P2,P2←2P2;
若 ki=0 , 则 P2←P1+P2,P1←2P1。
由于kt - 1=1 , 所以P1=P ,P2=2P 。 当kt - 2=0时,P1=2P , P2=3P ; 当kt - 2=1时,P1=3P ,P2=4P 。 由此可以看出kt - 2位的不同值会产生不同的中间结果,不同的中间结果在运算时又会产生不同的功耗,DPA攻击正是利用这些功耗差异来实施的。 参考文献[4] 利用EDA仿真软件对Montgomery标量乘算法实施了DPA攻击, 证明该算法不能抵御DPA攻击。
2 Montgomery标量乘算法的抗DPA攻击改进算法
Montgomery标量乘算法是采用准投影坐标来实现的,通过引入Z坐标将求逆运算转为乘法运算来提高算法效率, 而运算结果与Z值的选取无关。 结合Mont- gomery标量乘算法的这个特点, 本文在算法的硬件实现过程中加入了一个随机数发生器,在每次点乘运算前随机产生一个Z值,由于Z参与整个运算,这样运算的中间结果便引入了随机成分,而功耗又与数据相关,所以即使进行两次相同输入的运算,运算过程产生的功耗也不会相同,进而达到抗DPA攻击的目的。 随机Z坐标的改进算法如下所示:
算法2:随机Z坐标的Montgomery标量乘算法
输入:参数组
其中
输出:kP。
(2) 对于i从t - 2到0 , 重复执行 :
①若 ki=1 , 则 :
②否则:
(5) 返回 (x3,y3) 。
GF (2192) 域对算法2进行了硬件实现, 采用适合硬件实现的Montgomery FIOS优化算法来实现最核心的模乘单元,寄存器堆采用单端口写、双端口读的形式便于参数的灵活注入和数据的调度。 为了不影响算法效率,随机数发生器与运算单元并行执行,将产生的随机数存储起来用于下一轮的运算,随机Z坐标的改进算法硬件结构如图1所示。
利用DC综合工具将该硬件模块在0.18 μm的工艺下进行综合,并与算法1进行比较,对比结果如表1所示。
算法2增加了随机数发生电路,所以总电路面积增加了9.60%;由于随机数生成运算与运算单元并行不会影响算法效率,所以算法2只增加了2次模平方运算和3次模乘运算, 算法效率只降低了0.36% 。
3改进算法的抗DPA攻击能力验证
为了验证改进算法的抗DPA攻击能力, 本文利用EDA仿真工具对基于GF (2192) 实现的原始Montgomery标量乘算法和改进算法分别进行了DPA攻击,过程如下:
(1) 搭建功耗分析仿真系统。 首先, 利用硬件描述语言(Verilog HDL)对192长度的算法进行描述,并编写了测试激励函数(testbench);然后,利用DC工具将硬件描述文件在0.18 μm单元库下进行综合,生成门级网表文件, 将门级网表、testbench文件经过NC仿真后生成vcd文件;最后,利用PrimePower功耗分析软件,对vcd文件的功耗进行分析,并记录功耗数据。
(2)采集功耗数据。 基于步骤(1) 中的功耗数据采集系统,使用固定密钥kr与1 000个随机点P0,P1,… ,P999分别进行加密,记录1 000组功耗数据S0[j] ,S1[j] , … ,S999[j] ,j为采样点。
(3) 生成区分函数。 已知k191=1 , 猜测k190=1 , 其他位为任意值, 即猜测密钥为kg=(1 ,1 ,x, … ,x,x)2, 利用Modelsim软件分别将猜测密钥kg与步骤(2)中所用的1 000个随机点P进行仿真运算,得到一组区分函数值D0,D1, …,D999 。
(4) 处理数据。 利用Di将步骤(2)所得到的功耗曲线按如下方式分为两组:
分别求出每个采样点上两组功耗曲线的平均值并作差:
重复上述步骤, 分别获得了原始Montgomery标量乘算法和改进算法的差分功耗曲线,如图2和图3所示。
比较图2(a) 和图2(b) 可以看出, 当密钥猜测正确(k190=1) 时, 有明显的尖峰出现; 当密钥猜测错误(k190=0) 时,没有明显的尖峰出现。 这说明Montgomery标量乘算法不能抵御DPA攻击,按照上述步骤逐比特进行攻击, 进而得到正确密钥。
从图3中可以看出,无论是密钥猜测正确还是猜测错误时,差分功耗曲线都不会出现明显的尖峰,说明随机Z坐标会改变功耗和密钥的相关特性,使统计分析手段失效,进而达到了抗DPA攻击的目的。
本文分析了Montgomery标量乘算法的安全性, 结合算法的特点提出了随机Z坐标来抗DPA攻击的改进算法,并通过仿真验证了改进算法的抗DPA攻击能力。 由于很多标量乘算法通过采用标准投影坐标、雅可比投影坐标、Lopez-Dahab投影坐标来提高计算效率,投影坐标下的算法都有Z值参与整个运算,运算结果与Z值的选取无关, 所以随机Z坐标抗DPA攻击的方法理论上可以移植到其他利用投影坐标实现的算法中去,本文下一步将对此进行分析与研究。
摘要：标量乘法是椭圆曲线密码算法中最核心的运算,对整个密码体制的效率和安全性具有举足轻重的作用。在对准投影坐标系下实现的Montgomery标量乘算法的安全性进行分析的基础上,结合该算法的特点,提出了一种随机Z坐标的抗DPA攻击改进算法,并利用EDA仿真工具验证了其抗DPA攻击能力。
抗强剪切和涂抹攻击零水印算法 篇4
抗几何攻击鲁棒性数字水印算法是多媒体信息安全领域研究的热点。现有的抗几何攻击水印算法对于传统的几何变换(旋转、缩放、平移、仿射变换)和加噪、有损压缩、滤波等常规的信号处理有一定的有效性,然而对于存在信息丢失的强剪切攻击目前国内外在此方面的水印文献报道还很少。其中一些鲁棒性水印算法对于弱剪切(信息量丢失在25%以下),水印检测器在一定程度上可以提取出水印信息。但面对大面积的信息量丢失的剪切(强剪切攻击),水印检测器则无法提取出水印信息,算法失效。Xiang S等[3]提出一种基于图像低频统计特征的水印算法,将水印嵌入在图像低频直方图和均值统计特征中,实验结果表明该算法能较好地抵抗剪切攻击,但嵌入水印容量较小;Wu Kang等[4]提出了一种基于直方图调整的抗几何攻击图像水印算法,这种算法与文献[3]算法相比在一定程度上提高了水印的嵌入容量,对剪切攻击也具有一定的鲁棒性,但算法的鲁棒性是以牺牲水印的不可见性为代价的,因此该算法具有一定的局限性。文献[5,6]提出的基于各种不变矩抗几何攻击算法对于旋转、缩放和平移等攻击具有较好的鲁棒性,但不能有效抵抗强剪切攻击,这主要是由于大部分不变矩是基于图像全局特征的,对于局部的剪切无能为力;Lin等[7]提出了一种基于对等调制的抗剪切攻击水印方法,该算法通过对等调制方法将水印嵌入在图像经小波分解后的低频系数中,但随着图像的剪切部分水印信息随之不可恢复性地丢失,剪切程度愈大,水印损失愈严重。以上文献提到的各种算法均需要解决一个共性问题:水印的不可见性和鲁班性之间存在的矛盾。零水印很好地解决了这一问题,它不需要修改原始图像的任何信息,主要是利用图像的重要特征来构造水印信息,这样使其鲁棒性和安全得到加强。温泉[1]首次提出了零水印的概念,该文献利用了高阶累积量提取图像的特征来构造零水印,通过实验来证明这种方法的零水印有很好的性能。近几年来,零水印技术在温泉提出后得到了迅速的推广,这方面的科研成果和报道不断增多[8,9,10]。自D.D.Lee等[11]在Nature上首次提出了NMF算法后,NMF一直在不断地完善和发展着,目前已成功应用于人脸识别、图像融合、图像检索、文本聚类、盲源分离等诸多领域[12,13],而在数字水印领域中的应用却寥寥无几。本文基于NMF可以由部分感知全局的特性,结合Radon变换不变矩提出了一种抗强剪切和涂抹攻击零水印算法。
1 算法的理论研究背景
1.1 NMF算法
非负矩阵分解简称NMF,是目前矩阵分解新提出的一种方法。具体数学原理如下:
假设给定的一幅灰度图像Vn×m可以分解为两个非负矩阵Wn×r和Hr×m的乘积。即:,W矩阵称为基矩阵,H称为系数矩阵,r为基矩阵的维数。
NMF在本质上体现了一种非线性数据维数约减的思路(非线性降维),核心思想主要利用非负性约束来获取数据。数据具有非负性是对矩阵非常有效的限制条件,因此对于原始非负数据可以看作是由部分的和来表示。经过NMF分解后的基矩阵W具有一定的线性无关性和稀疏性,这就使得NMF对原始数据的特征具有一定的表述能力。
非负矩阵分解的目标函数一般表示为:
其中:Wij≥0,Hij≥0,i=1,2,…,m;j=1,2,…,n;m和n分别为原始矩阵V的行数和列数。
式(1)可看作在(WijHij)项上加Possion噪声或Gauss噪声产生了Vij。即V=WH+E,E表示噪声,若以Possion噪声作为E可以得到如下的迭代算法:
式(3)中j为矩阵的列,i为矩阵的行。经过若干次迭代之后使得V≈WH。基矩阵维数r的取值非常重要,它主要影响算法的收敛速度。从理论上讲r<<min(m,n),然而如果r取值过小不仅会影响收敛速度,而且经过NMF分解后的重构误差也较大。图1为基矩阵的维数r取不同值的重构误差(用E的2-范数度量)曲线;图2表示不同维数时CPU的运算时间。图1和图2表明:基的维数越小在相同的迭代次数内误差越大,而CPU运算时间越短;基的维数越大在相同的迭代次数内误差越小;而CPU运算时间越长,但分解的效果越好。r究竟取何值,应根据不同的应用而定(本文以大小为64×64baboon灰度图像为例做一说明,CPU为Intel Pentium4 2.00GHz,内存为512MB,Windows XP操作系统)。
1.2 Radon变换不变矩及其不变矩构造过程
Radon变换一般可以看作是沿该平面内的一族直线的线积分[7],如式(4)所示:
其中t表示沿着直线上的距离,t=xcosθ+ysinθ,若该函数沿着一系列投影线的积分构成了投影pθ(t),θ∈[0,π]。
设二维图像f(x,y)的Radon变换为pθ(t),则其k阶矩可以定义为:
m0(θ)=m00,m00为0阶矩,一般主要是表示图像的质量。而,表示投影pθ(t)的重心。下面构造Radon变换不变量:
(1)平移不变性构建
图像的平移会造成其投影移动,因此由此构造出的矩也将会发生变化,所以用中心矩来代替普通矩以此获得平移不变性。
表示pθ(t)的重心,式(6)为平移不变量的构造表达式。
(2)缩放不变性构建
如果图像发生缩放变化时,其投影((t))的Radon矩也会发生缩放变换。设缩放因子为λ则:
由式(7)可以得:
则的k阶中心矩为:
即:
ηk(θ)为缩放和平移不变量。
(3)旋转不变性构建
假设二维图像f(x,y)顺时针旋转某个角度Φ,则根据Radon变换其性质有:
R(r,θ){f(xcosΦ+ysinΦ,-cosΦ+ysinΦ)}=P(r,θ+Φ)(11)由上式可知Radon变换将二维图像f(x,y)旋转的操作转换成沿θ轴上的循环平移操作,而平移量为Φ;
由式(10)定义k阶矩为:
则:
因此A(k)具有旋转不变性,因此可以作为一种不变矩。
2 本文算法的实现过程
2.1本文抗剪切恢复算法
原始模型如下:
令V=[v1,v2,…,vm],H=[h1,h2,…,hm],则有:
其中vi为V的第i列,hi为H的第i列,由此可见,H矩阵因子的每一列均与原非负矩阵V的相应列对应。
令V'=[vk1,vk2,…,vkt],它是V任取T列组成的。k1,k2,…,kt∈[1,m],则有:
令H'=[hk1,hk2,…,hkt],则有V'=WH'。
即:
由以上可知:在原始图像矩阵V遭受剪切攻击时,仍可以从剩余的部分矩阵V中恢复出完整基矩阵W。为使基矩阵W存在惟一的解,系数矩阵V的秩最小应等于NMF分解的维数,即T≥r。
2.2零水印算法的实现过程
零水印算法的研究重点在于怎么样利用现有载体媒体的特征去构造零水印而并非设计如何嵌入实际水印信息,因此零水印技术很好地解决了数字水印技术中的不可见性和鲁棒性之间的矛盾,它是目前近几年来国内水印技术研究的热点。
本文零水印算法的设计中采用标准图像库里的“lena”图片作为宿主图像,大小为512×512。实验编程仿真环境:采用Matlab 7.5软件进行仿真编程实验;PC操作系统:Windows XP、CPU主频3.4GHz (双核)、内存2GB、显示卡:AMD Radeon HD 6450。
算法步骤如下:
Step1选取低阶Radon变换不变矩作为特征矢量(高阶矩对噪声比较敏感,故不作考虑)。
Step2对512×512的原始图像矩阵分块,子块大小为32×32,每一个子块展开为一列向量,则由原始矩阵得到1024×32的V矩阵。
Step3利用关系式:Vn×m=Wn×rHr×m,对V矩阵进行NMF分解得到W分量和H分量,并保存H分量,维数r=32。
Step4水印注册过程:首先计算经过NMF分解后基矩阵W分量的7个低阶不变矩,构成特征行向量A=(A1,A2,…,A7),然后将得到的特征向量,H分量数据一并在CA认证中心登记注册,当CA中心对注册信息加盖时间戳后,说明宿主图像已经在受到零水印的保护,水印注册流图如图3所示。
Step5对经过剪切的待检测图像,通过局部未剪切部分V矩阵和相应的H矩阵来恢复W矩阵。
Step6水印检测过程:首先计算Step5中恢复得到的W矩阵的7个Radon变换不变矩构成特征向量B=(B1,B2,…,B7),然后测量B向量与A向量的绝对差之和。
如果d≥ε并且时间戳与CA中心提供的信息不符(ε为经验阈值系数,实验中取值为0.005)则验证结束,证明宿主图像中不含有水印信息;否则,水印信息存在。
3 实验结果和分析过程
计算原始图像经NMF分解之后基矩阵W的Radon变换不变矩,组成A向量,实验中A=(a1,a2,…,a7),同理,待测图像的B向量也如上计算。使用峰值信噪比PSNR对失真图像进行度量。
其中,I(x,y)和I'(x,y)分别表示在(x,y)处的灰度值。
本文设计了四组实验来验证该算法的有效性。实验1是原始图像进行非几何攻击后与文献[8]的比较实验,结果见表1(d1表示受攻击后待检测图像与原始图像Tchebichef不变矩特征矢量的差距;d2表示受攻击后待检测图像与原始图像几何不变矩特征矢量的差距;d3表示受攻击后待检测图像与原始图像Radon变换不变矩特征矢量的差距)所示;实验2是对Lena图像进行几何变换后与文献[8]的比较实验,结果见表2;实验3是对Lena图像进行不同比例的剪切和涂抹攻击后的实验,结果见表3所示;实验4是为了验证对于其他图像是否会出现误判的情况所作的误检率验证实验。其他不同的载体图像分别选取pepper,plane和baboon三幅图像,实验结果见图4至图6所示。
4 结语
为了增强水印抵抗剪切和涂抹攻击的能力,提出一种抗强剪切和涂抹攻击的零水印算法。主要将NMF和Radon变换不变矩相结合设计出一种零水印算法。算法主要依靠NMF具有局部感知全局的特性,实现抗强剪切的过程。通过对该算法进行的一系列仿真实验,发现算法对各种不同角度的旋转攻击、尺度变换也有很强的鲁棒性,同时对非几何攻击如加噪、滤波、JPEG压缩等实验的分析,发现该算法对滤波、JPEG压缩也具有较强的鲁棒性。通过使用不同的载体图像进行误检率实验,结果显示对于没有嵌入水印的图像错误检测的概率很小,具有很高的检测精度。
一种追踪DDoS攻击源的算法 篇5
关键词：入侵检测,DDoS,攻击路径
随着互联网络的快速发展,DDo S攻击已成为Internet中最主要的安全威胁之一,越来越多的攻击案例已跨越了多个ISP。DDo S攻击可在世界上任何一个连接Internet的角落发起攻击,随着Internet规模不断拓展,DDo S攻击所跨越的路径将变得更长。在大多数的DDo S攻击事件中,攻击者普遍采用了“源地址欺骗”技术,使得各类基于特征信息过滤的防范手段变得十分有限,因而防范DDo S攻击是非常困难的。一些追踪算法[1,2,3,4,5,6,7]在短距离攻击事件的追踪中有良好的表现,而针对长距离攻击事件的追踪则显得力不从心。
最初的DDo S攻击追踪采用逐跳(Hop by Hop)追踪方法,例如链路测试,从最接近被攻击的路由器开始,测试其上游所有链路,找出是哪一个链路传输了攻击的数据流,然后在上一级路由器重复该过程,直到发现攻击源。由于该方法极大地依赖ISP和网络管理员的配合,人工成本很高,难以实现。
目前针对DDo S攻击源追踪主要为基于因特网层面的全局范围解决方案和基于ISP层面上的有限范围解决方案[1]。前者修改Internet中所有的路由器协议,需要路由器厂商和ISP支持,参与追踪算法的实施;后者能有效跟踪ISP内部攻击事件,但难以处理跨ISP的DDo S攻击事件。基于显式的ICMP traceback消息的追踪方案利用ICMP分组包来发送标记消息[2],而路由器以低概率从其转发的路由分组中取一个样本,目的节点根据收到的信息来重构攻击路径,但需防止攻击者发送假的ICMP traceback报文。类似于ICMP traceback,基于概率数据包标记(PPM)方案[3]在数据包到达路由器时,以某种概率来标记数据包的部分路径信息,当被攻击主机收到的带有标记信息的数据包达到一定数量时,可通过分析来恢复和构建完整的攻击路径。该方法能实现事后追踪,降低系统负载,且不会增加所传送数据包的大小。但数据包标记很容易被攻击者利用,当对付少量攻击包且高度分散的DDo S攻击时,假阳性概率会很高。对于一个平均攻击长度为25的25个用户发动的DDo S攻击事件,如采用PPM算法,被攻击主机需要花费数天的时间才能找到大致的攻击路径,而这里面还包含了一定数量的假阳性路径。
本文提出了一个追踪DDo S攻击源的算法,将攻击源快速锁定到规模相对较小的AS实体中,确定攻击源所属的AS自治域系统。由入侵检测系统的网络数据包采集器负责对网络中传输的报文进行监听、过滤、记录数据包信息,采集到的数据经加工处理后,识别并记录攻击行为或异常情况,对网络事件进行相关性分析,形成入侵攻击报警信息数据,再读取数据库的相关入侵攻击数据,对入侵攻击的路径路由进行反追踪以形成有效的入侵攻击路径路由图,从而实现入侵追踪定位的目标任务。
1 追踪处理框架
数据的采集由入侵检测系统的网络数据包采集器负责对网络中传输的报文进行监听、过滤、记录数据包信息,能够对内外网同时监控,为了更有效的采集数据,选取对主机的各种端口和网络关键节点的数据采集相结合。
入侵检测先集中采集数据,再用各种协议对数据分类,利用异常检测技术对数据源检测,如果发现有DDo S攻击行为,把结果反馈给用户,让用户决定是否进行追踪。DDo S攻击在时间上不是孤立产生的,在各个端点采集到的数据之间都有联系。新的入侵类型出现时,只要在控制中心在一定时间间隔内刷新规则库,具有很强的灵活性。
追踪攻击源对内网采用IP与MAC地址绑定的方式,对于外网采取经过路由器的数据包进行概率性的标记并记录。追踪基于Hash函数的SHTE引擎,首先扫描IDS检测到的攻击包,在查询中心查找需要的数据包头并进行综合分析,再对取得的路径信息用重构路径中心回溯攻击源路径。追踪后由用户决定是否对攻击源采取措施,警告攻击源、断开攻击源的连接或关闭对它开放的资源。
追踪定位读取入侵攻击报警数据库中的报警信息,其中包括入侵攻击源的IP地址,利用IP地址作为查询关键字,在注册设备信息数据库进行搜索查询相关入侵攻击者信息。如果入侵源IP地址存在于入侵攻击报警数据库,则输出入侵攻击报警数据库中的报警信息,否则输出警告信息。
注册设备信息数据库中入网注册主机信息包括设备主机IP地址、MAC地址、使用者相关资料等信息。网络入侵检测抓取网络业务数据后,对其进行预处理分析、决策、融合形成入侵报警信息,存放于入侵报警数据库,把入侵源信息与注册设备信息数据库中的数据进行查询比对,取得入侵攻击源更详细的信息,锁定入侵攻击源目标。
为便于对数据包的分区路由追踪,对入侵检测得到的数据和路由器中对应数据分区保存。由于ISP服务商提供服务的网络拓扑结构非常复杂,必须在网络中布置多个追踪扫描点,每个扫描点在自己的区域内,取得请求的数据包信息,追踪查询中心对这些分散的区域进行数据统计分类,查出在本区域内路由器标记过的数据包摘要信息,用于重构路径。
在锁定攻击源后,逐步追踪至入侵攻击的源头,排除攻击威胁。根据被锁定的攻击源IP地址及MAC地址信息,回溯实施入侵攻击行为走过的路径路由,在查询中心提供数据的基础上,利用拓扑结构图,得到入侵攻
击的路径路由图,以形成有效的虚拟证据链。总体结构框架如图1所示。
2 追踪实现
2.1 追踪DDo S攻击源的算法
构建入侵攻击路径路由利用ICMP包消息传递反向追踪技术,在ICMP包的传递过程中,但其存活时间TTL的值递增得足够大时,可实际抵达目标位置,由于在接收端主机上,没有进程在等待这条消息,会返回一条ICMP“端口访问不到”的消息。可以将ICMP数据包发给目的地(入侵攻击源),同时连续递增更改TTL的值。在TTL“超时”的时候,返回一条ICMP错误消息,对入侵攻击源的反向跟踪其实现入侵攻击所经过的路径路由,从而构建一张入侵攻击路径路由轮廓图。
追踪DDo S攻击源的算法采用PPM算法原理,我们采用标记信息由路由器地址换成了AS编号。由于AS的边界路由器(ASBR是此AS与其它AS之间交换信息的桥梁,任何进出AS的流量都要经过ASBR。追踪DDo S攻击源的算法用来发现DDo S攻击的AS所属源头。按照给定的概率随机把AS编号附加到进出本AS的数据包上,在确定时间段内,包含代表数据包特征信息的AS范围中的特定路由器地址;由被攻击主机重构攻击过程中经过的AS路径,使用AS编号来重构AS路径图。
标记信息获取算法:
路径构建算法:
在输入主机名或IP地址后,开始对入侵攻击源进行反向跟踪,从而构建出一幅入侵攻击路径路由图。例如,某一个入侵攻击源主机地址为11.56.1.212,程序对其进行反向追踪后,得到其入侵攻击某一主机过程中顺次经过的路由为:11.56.1.212→11.56.167.221→11.254.76.66→11.254.99.11→11.254.99.21→11.254.98.55→11.254.16.67→11.135.175.201→11.135.254.97→11.135.253.97→11.138.196.97→11.138.65.252
3.2算法性能分析
由于追踪DDo S攻击源的算法类似标记原理,因此性能分析的理论分析同样适用该算法。被攻击主机在恢复长度为d的攻击路径中所需收到的标记包数量的期望值E(X)<1/p(1-p)d-1。根据该公式计算的结果,当d=6~8时,p分别取0.13~0.17;得到15<=E(X)<=25,即被攻击主机接收到15到25个带标记的数据包就可把攻击路径构建起来。追踪DDo S攻击源算法和PPM算法相比,具有更好的收敛性;特别是标记概率较高时,算法性能更好,p取0.25时PPM算法所需的标记包数量是3601个,而追踪DDo S攻击源的算法的所需的标记包数量则是25个。PPM算法在对于近距离的攻击追踪中有非常好的收敛性。
由于IPV4中的Identification域只有16bit,而追踪DDoS攻击源的算法需要36bit的标记信息,因此采用分段标记策略(FMS)的计算量求解公式:C(k,d)=∑m[i-1].m[i]k(1<=i<=d)。其中,k表示标记信息的分段数量,d表示攻击长度,C(k,d)为发现所有d距离攻击者的计算量。
如表2所示,由于路径长度的减少,重建路径的算法计算量大大减少,重建路径所花的时间也随之大为降低。如采用每秒钟运算速度为100亿次的主流工作站,重建算法耗费的平均时间可以控制在分钟级内,非常便于实时追踪的实现。因此,追踪DDo S攻击源的算法比PPM算法在计算负荷上有更优越的表现。
3结论
本文提出了一个追踪DDo S攻击源的算法,将攻击源快速锁定到规模相对较小的AS实体中,确定攻击源所属的AS自治域系统,对入侵攻击的路径路由进行反追踪以形成有效的入侵攻击路径路由图,从而实现入侵追踪定位的目标任务。与PPM算法相比,在计算负荷上有更优越的表现。下一步的工作需要对下一代网络的支持问题展开进一步的深入研究。
参考文献
[1]Broder A,Mitzenmacher M.Network applications of bloom filters:A survey[J].Internet Mathematics,2005,1(4):485-509
[2]Sohn T,Moon J,LEE S,et al.Covert channel detection in the ICMP payload using support vector machine[M].Berlin:Springer,2003.
[3]Stefan S,David W.Network Support for IP Traceback[J].IEEE/ACM Transactions on Networking,2001,9(3):226-237.
[4]任勋益,王汝传,王海艳.基于自相似检测DDoS攻击的小波分析方法[J].通信学报,2006,27(5):6-11.
[5]任勋益,王汝传,张登银.R/S和小波分析法检测DDoS攻击的研究与比较[J].南京邮电大学学报:自然科学版,2006,26(6):48-51.
[6]张小明,许晓东,朱士瑞.基于Hurst指数方差分析的DDoS攻击检测方法[J].计算机工程,2008,34(14):149-151.
算法攻击 篇6
图像具有生动形象的特点,应用十分广泛。经过数字化而成的数字图像可由计算机高效处理,并能在网络中快速传播。为对数字图像进行有效的保护,可采用相应的加密技术。数字图像加密是目前数字图像处理领域的一个重要研究方向[1,2,3],基于各种混沌系统的数字图像加密算法也已成为近年来的研究热点之一,诸多各具特点、切实可行的算法已相继出现在有关的文献中[4,5,6,7,8]。
通过对图像加密技术及有关算法的研究,本文以混沌系统及其产生的混沌序列为基础,提出一种通用的综合使用像素坐标置乱与像素值置换技术的数字图像加密与解密算法,同时给出一种基于邻域相邻像素特性的抗剪切攻击恢复算法。
1 混沌序列
混沌序列是混沌系统中所出现的混沌现象的运动轨迹。根据混沌系统的方程,指定不同的参数与初值,即可产生一系列非相关、类随机、确定可再生的混沌序列。混沌序列对系统的参数与初值极其敏感,且在一定的区域内具有遍历性与伪随机性,因此可用于对数字图像进行加密,而相应的系统参数与初值均可作为密钥的组成部分。
Logistic映射是目前应用得相当广泛的、典型的一维混沌系统,定义为[4]
xn+1=μxn(1-xn) (1)
式中:μ为分支参数,且μ∈[0,4],xn∈(0,1),n=0,1,2,…。研究表明,当3.569 945 6<μ≤4时,Logistic映射所生成的混沌序列{xn,n=0,1,2,3,…}具有良好的随机分布特性与遍历性,是一种比较理想的伪随机序列,且对初值x0十分敏感。在应用Logistic映射时,μ与x0均可作为密钥使用。
Logistic映射具有良好的“雪崩效应”。为提高安全性,在使用Logistic混沌序列{xn,n=0,1,2,3,…}时,可适当舍弃其前面的N个数据项(一般取N≥20)。相应地,N也可作为密钥的组成部分之一。
本文在进行仿真实验时,用于生成Logistic混沌序列的密钥key=(μ,x0,N)。
2 基于混沌序列的像素坐标置乱
像素坐标置乱是指对图像的像素坐标进行变换以使其混乱。考虑到混沌序列的固有特性,可由混沌序列决定像素坐标的变换位置,以达到理想的置乱效果。
假定图像的大小为m×n,由密钥key=(μ,x0,N)产生具有相应长度的混沌序列{x1,x2,x3,…,xm×n},将其按升序或降序进行排序得到有序序列{xindex(1), xindex(2),xindex(3),…,xindex(m×n)},则该有序序列各数据项的下标序列{index(1),index(2),index(3),…,index(m×n)}即为整数序列{1,2,3,…,m×n}的一个排列。据此,可构造一个1-1变换Φ:k→index(k)。利用此变换Φ,可将该图像的像素(i,j)(其中i=0,1,2,…,m-1;j=0,1,2,…,n-1)按行列顺序变换到新位置(row,col)
经过像素的坐标变换后,图像将变得面目全非。
3 基于混沌序列的像素值置换
像素值置换是指对图像的像素值进行变换以改变其值。考虑到混沌序列的良好特性,可由混沌序列生成相应的操作数,然后再与各像素值分别进行异或运算,从而达到理想的置换效果。
假定图像的大小为m×n,由密钥key=(μ,x0,N)产生具有相应长度的混沌序列{x1,x2,x3,…,xm×n},将其按图像类型转换为无符号整数序列{z1,z2,z3,…,zm×n},然后与该图像的像素值P(i,j)分别进行异或运算,即可得到置换后的像素值Pe(i,j)。
混沌序列转换为无符号整数序列的公式为
zi=round(10k×abs(xi)×T)mod T (3)
式中:i=1,2,3,…, m×n;k=0,1,2,3,…;abs表示取绝对值;round表示取最近整数;T=2h为图像类型值,h为二值图像、灰度图像或RGB真彩图像各分量的比特深度。据此,可将k作为子密钥使用。
像素值置换的公式为
Pe(i,j)=P(i,j)⊕(zixn+j+1) (4)
式中:i=0,1,2,…,m-1;j=0,1,2,…,n-1。
反之,像素值恢复的公式为
P(i,j)=Pe(i,j)⊕(zixn+j+1) (5)
经过图像像素值的随机置换后,原图像的灰度直方图统计特性将被彻底改变。
4 加密与解密算法
在进行数字图像的加密时,同时采用基于混沌序列的像素坐标置乱与像素值置换,可有效提高加密图像的抗剪切攻击能力和抗像素特征值统计攻击能力。若在进行像素坐标置乱与像素值置换时使用的不同的混沌序列,则加密效果更佳。
为简单起见,本文加密算法基于同样的一个混沌序列进行像素坐标置乱与像素值置换,其主要步骤为:
1) 读取待加密图像,生成像素矩阵P,并确定其大小m×n与图像类型值T。
2) 由密钥key=(μ,x0,N)产生一个长度为m×n的混沌序列{x1,x2,x3,…,xm×n}。
3) 将{x1,x2,x3,…,xm×n}按升序或降序进行排序,得到有序序列{xindex(1),xindex(2),xindex(3),…,xindex(m×n)},并据此生成下标序列{index(1),index(2),index(3),…,index(m×n)}。
4) 根据{index(1),index(2),index(3),…,index(m×n)}及变换Φ:k→index(k),将像素坐标(i,j)按行列顺序变换到新位置(row,col),生成像素坐标置乱后的图像加密矩阵PE。
5) 根据子密钥k及图像类型值T,将{x1,x2,x3,…,xm×n}转换为无符号整数序列{z1,z2,z3,…,zm×n}。
6) 将{z1,z2,z3,…,zm×n}中的各个数据项分别与像素矩阵PE中的对应的像素值进行异或运算,生成像素值置换后的图像加密矩阵P。
7) 由像素矩阵P生成加密图像。
本加密算法是可逆的,因此解密算法与加密算法具有相同的密钥,但应先恢复像素的值,然后再将各像素变换至其原来所在的坐标位置。
5 抗剪切攻击恢复算法
针对恶意剪切等攻击,可采用相应的抗剪切攻击恢复算法(简称为ASAR算法),进一步提高解密图像的质量。
5.1 剪切区域的检测
像素坐标置乱与像素值置换的双重加密过程,极大地降低了图像相邻像素之间的相关性,加密图像中的像素值已呈随机分布状态,并均匀扩散至整个取值范围。因此,若发现连续的、等值的多个像素,则可认为这些像素是被剪切的。为降低误检率,一般应取3～6个连续像素作为判断条件。
首先,创建一个与加密图像大小一致的剪切区域标记零矩阵CF。然后,逐行扫描加密图像,若发现连续多个(本文算法为6个)像素的值相同,则将CF中与这些像素对应的元素置为255。
对于RGB加密图像,可通过逐一比较CF各分量中对应元素的值,将最终的剪切区域修正为各分量的相交部分。
本剪切区域检测算法采用等值的像素扫描判断技术,因此同样适用于涂鸦、污损等恶意攻击的情形。
5.2 解密图像的恢复
加密图像解密后,被剪切的像素将按加密时的坐标对应关系变换至其原始位置,从而在整个解密图像中呈均匀分布状态。根据4邻域相邻像素的高度相关特性,可将邻域像素的平均值作为各被剪切像素的值。本文解密图像恢复算法的基本步骤为:
1) 按对加密图像进行解密时各像素的坐标变换关系,将CF中的各个元素变换至相应像素在解密图像中的坐标所对应的位置,得到一个相应的图像恢复标记矩阵RF。
2) 置unfinished为0。
3) 逐行逐列扫描RF,若某个元素值为255,则计算其4邻域中未被剪切(或已被恢复)的像素的个数n以及相应的像素值之和s。若n≥2,则将该元素的值置为0,同时将对应的像素值置为平均值round(s/n);否则,置unfinished为1。
4) 若unfinished=1,则转至2)。
6 实验结果与分析
6.1 实验结果
本文使用MATLAB R2007a平台,对各类常见图像按文中算法进行仿真实验。实验采用同样的一个Logistic混沌序列对图像进行像素坐标置乱与像素值置换加密,密钥key=(μ,x0,N)=(3.69,0.567 89,50),子密钥k=3。对于RGB真彩图像,亦采用同样的混沌序列并按同样的方式加密其R,G,B各分量。图像经加密后,均变得杂乱无章、面目全非,证明了算法的有效性。限于篇幅,在此只列出几个有代表性的例子。实验结果见图1～图5。
6.2 安全性分析
如图4所示的安全性实验表明,即使只对初值x0进行微小修改(仅相差10-10),也将导致解密的完全失败,此时所生成的解密图像依然类似于待解密的加密图像。同样,只对其余的某个密钥分量(μ,N或k)进行微调时,结果亦与此类似。只有在使用完全正确的密钥与子密钥时,才能确保解密成功。可见,本文算法具有极强的密钥敏感性。此外,本文算法的密钥分量较多(包括浮点型的μ,x0的与整型的N,k),因此拥有颇为巨大的密钥空间,可有效抵御穷举攻击。
6.3 统计特性分析
1) 灰度直方图
通过对各类图像在加密前后的灰度直方图进行比较,可以发现其差异是十分明显的。图像经过加密以后,其像素在整个取值范围内的分布相当均匀,表明本文算法具有良好的扩散性,可完全改变图像的像素值统计特性。
2) 相邻像素的相关性
图像相邻像素的相关系数用于度量相邻像素的相关性,其计算公式为[5]
式中:x,y为图像中两个相邻像素的灰度值。
Lena,baidu_logo与Baboon图像在加密前后的相邻像素相关系数分别如表1、表2所示。实验数据表明,原始图像在水平、垂直与对角方向的相邻像素的相关系数均接近于±1.00,说明存在着高度相关性;而加密图像在各个方向的相邻像素的相关系数均接近于0,说明已呈几乎不相关状态。
3) 信息熵
图像的信息熵用于度量图像中灰度值的均匀分布情况,其计算公式为[6]
式中:p(xi)为图像像素值xi出现的概率。
Lena,baidu_logo与Baboon图像在加密前后的信息熵分别如表3、表4所示。实验数据表明,Lena加密图像与Baboon加密图像R,G,B各分量的信息熵均接近于8(256级灰度图像信息熵的理论最大值),baidu_logo加密图像的信息熵则刚好等于1(二值图像信息熵的理论最大值)。可见,经本文算法加密后,图像的像素值分布已相当均匀,且其出现概率亦几乎是一致的。
6.4 抗剪切能力
如图5所示的抗剪切攻击实验表明,即使加密图像被随机剪切的面积达到50%,仍然能够直接解密出相当不错的可识别的图像,进一步应用ASAR算法时则可得到还原质量更佳的恢复图像,可见本文加密算法的抗剪切攻击能力是较强的,而ASAR算法也是有效可行的。从峰值信噪比PSNR看,图5c和图5d分别为16.668 5,10.659 8,而图5e和图5f分别为25.626 2,21.218 6,这也客观地表明了本文ASAR算法的有效性。
7 结束语
基于混沌系统及其所产生的混沌序列,本文提出了一种通用的数字图像加密与解密算法,同时给出了一种基于邻域相邻像素特性的抗剪切攻击恢复算法。文中的加密算法充分利用了混沌序列的固有特性,并采用像素坐标置乱与像素值置换相结合的双重加密技术,具有较强的安全性。此外,该算法对于图像的类型及大小没有任何限制,并可使用Logistic,Henon,Lorenz等各类混沌系统所产生的混沌序列,且易于实现,具有良好适应性与实用性。为进一步提高数字图像的加密效果,可对本文算法进行相应的改进,如使用不同的混沌序列进行像素坐标置乱与像素值置换,或同时使用两种不同的混沌系统等。
参考文献
[1]李昌刚,韩正之,张浩然.图像加密技术综述[J].计算机研究与发展,2002,39(10):1317-1324.
[2]李昌刚,韩正之.图像加密技术新进展[J].信息与控制,2003,32(4):339-343.
[3]孙燮华.数字图像处理:原理与算法[M].北京:机械工业出版社,2010.
[4]高飞,李兴华.基于混沌序列的位图像加密研究[J].北京理工大学学报,2005,25(5):447-450.
[5]李太勇,贾华丁,吴江.基于三维混沌序列的数字图像加密算法[J].计算机应用,2006,26(7):1652-1654.
[6]李鹏,田东平.基于超混沌序列的数字图像加密算法[J].微电子学与计算机,2008,25(3):4-7.
[7]刘刚,王立香.一种新的基于混沌的图像加密算法[J].电视技术,2008,32(12):22-24.
算法攻击 篇7
密码算法的很多分析方法已经被提出, 与基于算法的输入和输出的传统数学攻击方法相比, 旁路攻击方法依赖于这样一个事实:任何算法的实现都是不理想的, 并会泄漏一些依赖于所处理密钥的物理上可观察的参数。这些参数包括时间, 能量消耗, 电磁辐射和算法错误行为等。目前人们研究最多的旁路攻击之一是能量分析攻击[1], 又叫功耗分析攻击, 按照对泄漏信息分析原理的不同, 可将其分为简单能量分析SPA (Simple Power Analysis) 、差分能量分析DPA (Differential Power Analysis) 、相关能量分析CPA (Correlation Power Analysis) 、模板攻击[2]、碰撞攻击[3]等。
目前, 国内对分组密码的碰撞攻击研究还较少, 国外也主要对密码算法的软件[8]实现做了一些碰撞攻击的研究;而对密码算法的硬件实现, 如FPGA实现的密码算法, 研究较少。DES自公布以来, 20年内一直超越国界成为国际上商用保密通信和计算机通信中最常用的加密算法。因此, 研究针对DES密码算法FPGA实现的旁路碰撞攻击, 采取有效的碰撞检测方法显得尤为重要。
1 Feistel结构分组密码旁路碰撞攻击
旁路碰撞攻击作为传统数学攻击方法和旁路攻击方法的结合体, 关键在于如何有效地检测碰撞, 下面对碰撞的攻击流程和碰撞检测原理进行详细讨论。
1.1 旁路碰撞攻击流程
2003年Schramm在FSE上提出了碰撞攻击的概念[4], 并给出了对包含DES算法的密码设备的实际攻击。其基本思想是寻找特定位置的“内部碰撞” (如果密码算法的某个内部函数的两个不同输入产生相同输出, 则称发生了内部碰撞现象) , 如果发生了内部碰撞, 则可以根据相等的式子推导出密钥的一些信息, 从而破解密码设备。碰撞攻击方法主要分为以下几个步骤 (如图1所示) :
(1) 对算法进行分析, 找到可能发生碰撞的碰撞点;
(2) 根据碰撞点选择输入明文对;
(3) 对选择的明文对进行加密, 同时采集加密各明文对应的功耗信息;
(4) 利用采集到的功耗信息检测碰撞;
(5) 如果碰撞发生, 则可以根据碰撞建立等式分析密钥, 如果未检测到碰撞, 则重新执行步骤 (2) , 直到检测到发生碰撞。
1.2 Feistel结构碰撞模型
通常, Feistel结构密码算法是一个输入明文长度为2w比特数据分组的迭代分组密码[7], 如图2所示。首先长度为2w比特的输入数据被分为左半部分L (w位) 和右半部分R (w位) , 经过轮函数F后, 变为 (L', R') :
对于Feistel结构分组密码算法, 假设输入两个不同明文 (L1, R1) 和 (L2, R2) , 令L1和L2之间的差为δL, R1和R2之间的差为δR, 令δR经过F函数之后得到的是Δ。旁路碰撞攻击的目标是在算法的第二轮输入中消除第一轮中引入的差, 即Δ=δL, 如果碰撞发生, 第二轮中的F函数运算就完全相同, 硬件实现中在第二轮就可以得到具有高度相关的能量消耗。
1.3 基于最小一乘法的旁路碰撞检测原理
为了寻找这种高度相关的特性, 我们采用基于最小一乘法的碰撞检测方法, 下面给出碰撞检测的原理[9]。
给定两条旁道迹T1和T2, 取相同时间段上的l个特征点, 记:
我们假设每个点Ti, j在统计学上都可被描述为下式的形式:
其中, Ti, j为波形中该点的纵坐标值;ri, j表示随机噪声, 公认地, 随机噪声服从均值为0, 方差为σr2的高斯分布;Si, j表示给定时间点j上的信号恒定分量 (不含噪声) , 不妨根据中心极限定理, 将其看作是期望为μs, 方差为σs2的高斯分布。
我们研究两次加密的 (两条波形) 两段相同位置的波形。在两段相同位置上各取l个特征点, 我们定义ΔT来衡量两段波形之间的“距离”, 其期望E (ΔT) 可作为判断碰撞发生与否的区分器。
当碰撞发生时, S1, j=S2, j恒成立, 因此由于则因此, 根据半正态分布的原理:若x∶N (μ, σ2) , 则我们可以推导出E (ΔT) 的结果:
显然, 碰撞未发生时的E (ΔT) 要大于碰撞发生时的E (ΔT) , 当波形条数达到一定数量时, 二者的差是不可忽略的。在二者之间有效地选取一个阈值, 当E (ΔT) 小于这个阈值时, 即可判定发生了碰撞。
2 针对DES的旁路碰撞攻击
2.1 DES碰撞分析
作为典型的Feistel结构密码算法, DES算法的内部碰撞符合Feistel结构碰撞模型的特征。DES的8个S盒是26→24的满射函数, 由S盒的设计特点可知[5], 对于DES中每一个S盒, 相应于任意一个输入zi∈{0, …, 26-1}, 都存在三个差δ1、δ2和δ3, 满足下式:
其中, δ1≠δ2≠δ3, 即在一个单独的S盒中发生了碰撞。
S盒的六位输入是明文经过E盒扩展后与子密钥进行异或操作得到的, 如图3所示。
有因此, 只需知道z和x, 就可获得k的有关信息。对于每一个S盒, 都可以得到一个差δ的列表, 表1为第二个S盒的部分差δ的列表。
表1中第一列为δ差的值, 第二列为所有对应δ差的在S盒输出端发生碰撞的输入对。
为了获得子密钥中对应某一个S盒的六位, 需要保持其他S盒的输入不变, 攻击者可以选择一个特殊的δ, 改变输入x直到检测到碰撞S (x⊕k) =S (x⊕δ⊕k) 。由于E盒的性质, 使得输入x和x⊕δ的两个最高有效位和两个最低有效位也会进入临近的两个S盒, 如图4所示。如果保持δ的两个最高有效位和两个最低有效位都为0, 那么相邻两个S盒在输入为x和x⊕δ的情况下将保持不变。由S盒的设计准则可知, 这样的δ并不存在。因此, 保持其他S盒输入不变, 而由一个S盒产生碰撞的情况是不可能的。
由文献[5]知, 碰撞可以在三个相邻S盒中发生。记第一轮中经过E盒传播后三个相邻S盒的输入为性x (i-1) i (i+1) , x (i-1) i (i+1) ⊕Δ为另一个输入, 其中Δ=δi-1|δi|δi+1表示对应Si-1、Si、Si+1三个相邻S盒的差δi-1、δi和δi+1的拼接。为了不改变左右两个临近S盒Si-2和Si+2的输入, 的两个最高有效位和两个最低有效位必须为0, 即Δ[0]=Δ[1]=Δ[16]=Δ[17]=0。另外, 为了满足扩展变换E盒的特性, Δ必须满足以下条件:Δ[4]=Δ[6], Δ[5]=Δ[7], Δ[10]=Δ[12], Δ[11]=Δ[13]。
因此, Δ=δi-1|δi|δi+1必须服从Δ=00x1x2vwvwx3x4yzyzx5x600, 其中xi, v, w, y, z∈{0, 1}, 如图5所示。
通过对δ列表的分析, 揭露了服从以上所描述属性的差Δ的存在性。即, 存在输入x和x⊕δ, 可以在f函数中导致碰撞f (x) =f (x⊕Δ) 。
例如, 我们选择第一轮中第2、3、4个S盒作为攻击点, 由算法分析知, 这三个S盒的输入对应输入明文的4、6、14、22、30、32、38、40、46、48、54、56、62、64共14位输入。遍历明文的这14位输入, 保持剩余50位明文不变。在f函数中, 这14位明文被扩展为18位输入x, 并和48位轮密钥中相应的密钥位k相异或。结果z=x⊕k进入目标S盒, 攻击者利用能量分析平台记录密码设备在第二轮中的能量消耗。然后, 将输入设为x⊕Δ, 再次记录第二轮中的能量消耗。利用本文提出的碰撞检测方法检测碰撞, 一旦检测到碰撞, 三个相应δ表的分析将揭示可能的密钥候选值k=z⊕x。
2.2 旁路碰撞检测过程
本文提出的碰撞检测方法的前提条件是, 攻击者能够获得并完全控制一个与目标芯片相同或类似的芯片, 我们称其为实验芯片。以DES为例, 选择第一轮中第2、3、4个S盒作为攻击点, 碰撞检测算法如下:
(1) 在实验芯片上对任意明文和密钥进行加密实验, 确定待研究碰撞点在功耗曲线中的位置;
(2) 对实验芯片, 选择密钥K, 通过算法分析, 选取会导致碰撞发生的x和x⊕Δ对应的特殊明文对, 用这组明文对在实验芯片上分别加密m次, 获取m×2条波形, 对获取的m×2条波形利用Matlab软件对碰撞点后的一段波形 (即加密第二轮) 中每个采样点噪声的标准差进行参数估计, 计算碰撞发生时ΔT的期望, 记作E0 (ΔT) ;
(3) 对特定密钥K, 通过对算法分析, 选取n组不会导致碰撞发生的x和x⊕Δ对应的特殊明文对, 对n组明文对分别进行m次加密, 获取n×m×2条波形, 利用Matlab软件分别获取n组明文对加密第二轮中每个采样点的标准差的参数估计, 对每组的m×2条波形进行平均, 得到n组均值, 再对各点均值的标准差进行参数估计, 计算碰撞未发生时ΔT的期望, 记作E1 (ΔT) ;
(4) 根据第1-3步获取的实验数据, 选取作为阈值E;
(5) 对目标芯片, 固定三个临近S盒的差Δ, 遍历明文x的14位, 对每一组x和x⊕Δ对应的明文各加密m次, 获取m×2条波形, 通过Matlab分析获取ΔT的期望E' (ΔT) , 比较E' (ΔT) 和E的大小, 若E' (ΔT)
(6) 若碰撞未发生, 选择满足条件的其他Δ, 重复第 (5) 步。
3 攻击验证
3.1 功耗仿真平台
功耗仿真平台由综合工具DC、仿真工具VCS和功耗计算工具Prime Power 3部分组成[10], 如图6所示。
基于功耗仿真的碰撞攻击步骤如下:
(1) 首先, 使用DC综合工具, 将Verilog硬件语言描述的DES算法综合为门级.v文件。
(2) 编写输入数据到DES算法的testbench中, 在VCS中对DES算法的门级.v文件和testbench进行仿真得到所输入数据加密运算的.vcd文件。
(3) 利用Prime Power功耗仿真软件对门级.v文件与.vcd文件进行分析, 计算该组数据加密运算的功耗。
(4) 将得到的功耗文件利用Matlab软件进行分析。
3.2 功耗实测平台
在实验室现有设备基础上[6], 构建了功耗信息采集平台, 如图7所示。
其中, PC机主要负责对控制模块和FPGA密码芯片进行信息配置, 并对示波器采集到的波形数据进行分析;控制模块主要负责产生控制信号控制FPGA密码芯片;信号发生器负责给密码芯片提供1MHZ的系统时钟;FPGA密码芯片中下载待攻击密码算法, 在其内核电源与地之间串联一个电阻, 通过差分探头测量电阻两端之间的电压值;示波器将采样得到的波形以数据形式存储, 最终在PC机上进行分析。
3.3 攻击结果分析
利用功耗仿真平台, 确定待测密钥, 选择Δ=18'b000011110010101000, 对DES加密200组明文对的过程进行仿真, 得到功耗文件。由于第二轮的仿真功耗为几个离散值, 无法利用本文的碰撞检测过程对其进行分析。因此, 我们用第二轮的ΔT表示明文对加密过程的相关性, ΔT越小, 明文对发生碰撞的可能性越大, 反之, 1/ΔT越大, 明文对发生碰撞的可能性越大。图8为200组明文对第二轮ΔT的倒数。
在实验芯片上, 利用功耗信息采集平台, 将DES硬件描述文件下载到FPGA密码芯片中, 密钥设置为64'h3132333435363738。对任意明文, 利用示波器采集加密过程中产生的功耗信息, 采集到的波形曲线如图9所示, 图中上方波形为触发信号, 下方波形为能量信号。从图中可以很明显地看出, 这是DES加密16轮得到的功耗曲线, 其中方框内表示第二轮的功耗信息。
为了确定阈值, 需要选择在第二轮中会发生碰撞的明文对。通过算法分析, 选择Δ=18'b000011110010101000, 取相应于x的明文plain1=64'h20A0A00020000020, 则相应于x⊕Δ的明文为plain2=64'h A0A0800000000000。为采集第二轮的功耗信息, 我们对示波器进行如下设置:采样速率设置为500 MS/s, 采样点数设置为2.5 k, 触发方式设置为上升沿触发。其中一条波形曲线如图10所示, 方框内为第二轮加密的波形。
对plain1和plain2各加密10次, 采集波形文件并分析, 得到E0 (ΔT) =5.204。选择不会发生碰撞的10组明文对, 各加密10次, 得到200条波形文件, 对波形文件分析, 得到E1 (ΔT) =5.446。因此, 阈值E=5.325。
对目标芯片, 固定差Δ, 遍历明文的14位, 保持其他50位不变, 对每一组x和x⊕Δ对应的明文各加密10次。图11即为对200组明文对分析的结果, 图中横坐标表示明文对数, 纵坐标表示ΔT的期望值。
对比图8和图11可知, 存在一组明文对的期望在阈值E以下且1/ΔT最大, 表示发生了碰撞。明文对为plain1=64'h0080208000200000, plain2=64'h8080008020200020。
4 结语
本文通过对碰撞检测过程的改进, 实现了基于最小一乘法的碰撞检测技术。利用仿真功耗采集平台和实测功耗采集平台, 成功检测到碰撞的发生, 验证了基于最小一乘法碰撞检测技术的有效性。
参考文献
[1]Paul K, Jaffe J, Jun B.Differential power analysis[C]//1999 International Conference on Advances in Cryptology (CRYPTO’99) , 1991, 1666:388-397.
[2]Suresh Chari, Josyula R Rao, Pankaj Rohatgi.Template Attacks[C]//Cryptographic Hardware and Embedded Systems (CHES’02) , 2002, 13-28.
[3]林克成, 邓高明, 赵强, 等.一种基于DES密码算法的旁路内部碰撞攻击方法[J].现代计算机, 2011 (Z1) :3-5.
[4]Schramm K, Wollinger T, Paar C.A New Class of Collision Attacks and Its Application to DES[C]//FSE 2003, LNCS, 2003, 2887:206-222.
[5]Davio M, Desmedt Y, Quisquater J J.Propagation Characteristics of the DES.In Advances in Cryptology[C]//CRYPTO’84, 1984:62-74.
[6]李佩之, 严迎建, 段二朋.DES密码芯片模板攻击技术研究[J].计算机应用与软件, 2013, 30 (4) :310-312.
[7]Ledig H, Muller F, Valette F.Enhancing Collision Attacks[C]//M Joye, J-J Quisquater.CHES 2004, LNCS 3156, 2004:176-190.
[8]Schramm K, Leander G, Felke P, et al.A Collision Attack on AES Combining Side Channel-and Differential Attack[C]//M Joye, J-J Quisquater.CHES 2004, LNCS 3156, 2004:163-175.
[9]Andrey Bogdanov.Multiple-Differential Side-Channel Collision Attacks on AES[C]//E Oswald, P Rohatgi.CHES 2008, LNCS 5154, 2008.International Association for Cryptologic Research 2008:30-44.