简化轮LBlock的密钥中比特检测及分析

LBlock密码算法是近来提出的一类轻量级分组加密算法。利用LBlock算法的结构特点,结合立方检测的基本思想,设计2个密钥中比特捕获算法,对LBlock算法输出所涉及的密钥比特个数情况进行分析。9轮简化LBlock的每个输出比特全部卷入所有的主密钥比特信息,在18维立方变元下,11轮简化LBlock的输出累加中每个比特全部卷入所有的主密钥比特信息。上述2轮简化LBlock均不存在密钥中比特。研究结果表明,全轮LBlock密码算法具有稳固的密钥信息扩散及混淆性,足以抵抗经典立方攻击。     

基于Cauchy矩阵的线性变换的研究

P-置换是实现分组密码扩散原则的关键组件.一般来说,分支数越大,扩散效果越明显.人们利用MDS矩阵设计最优线性变换作为分组密码组件的扩散层.在达到最优线性变换的同时,针对扩散矩阵还应满足矩阵中元素尽量少的要求,对Cauchy型MDS矩阵分别与Hadmard矩阵和循环移位矩阵的相互结合方式构造最优线性层的方法进行了研究.对Cauchy-Hadmard矩阵(同时是Cauchy矩阵和Hadmard矩阵)构造线性变换的一种方法进行了分析,给出了算法的C语言的关键程序,根据算法给出了一个最优线性变换的示例;对循环移位矩阵构造Cauchy矩阵进行了尝试和证明.结果显示Cauchy-Hadmard矩阵满足矩阵元素最少和运算复杂度低的要求,利用循环移位矩阵无法构造出Cauchy矩阵.这些结论为设计分组密码组件的扩散层提供了重要的方法参考.     

SPN分组密码中最优扩散层的构造与验证

SPN结构中的扩散层往往是矢量空间GF(2m)n上的线性变换,它与n阶矩阵在确定基 下一一对应。分支数B=n+1的扩散层是最优的,其充分必要条件是:对应矩阵的任意k阶子阵均 为非奇异。设计了构造最优SPN线性层的算法,并给出了线性变换最优扩散特性的验证算法。最 后,给出GF(28)8上一个最优线性变换及其验证结果的示例。     

针对LBlock算法的踪迹驱动Cache攻击

LBlock是一种轻量级分组密码算法,其由于优秀的软硬件实现性能而备受关注。目前针对LBlock的安全性研究多侧重于抵御传统的数学攻击。缓存( Cache)攻击作为一种旁路攻击技术,已经被证实对密码算法的工程实现具有实际威胁,其中踪迹驱动Cache攻击分析所需样本少、分析效率高。为此,根据LBlock的算法结构及密钥输入特点,利用访问Cache过程中密码泄露的旁路信息,给出针对LBlock算法的踪迹驱动Cache攻击。分析结果表明,该攻击选择106个明文,经过约27.71次离线加密时间即可成功恢复LBlock的全部密钥。与LBlock侧信道立方攻击和具有Feistel结构的DES算法踪迹驱动Cache攻击相比,其攻击效果更明显。     

基于LBlock算法的密码SoC安全存储总线设计

密码片上系统(SoC)的数据访存通路是侵入式探针分析的重要目标,为抵御侵入式分析,利用LBlock算法设计一种SoC存储加密总线。将LBlock算法硬件结构每4轮展开为1个时钟周期,使32轮加解密时序压缩到8个时钟周期,同时将数据存储器一般采用的32位总线缓冲至64位,以配合LBlock算法的分组操作。FPGA验证结果表明,该设计方案使得芯片内嵌数据存储器(如RAM、Flash等)的总线即使被探针攻击获取也无法解读,应用64位数据块进行8个时钟周期加密的访存吞吐率达到533 kb/s,且避免了32位分组加密穷举攻击,实现代价低。     

递归扩散层的权值系数计算方法

递归扩散层是一种新型的密码函数线性扩散层,具有良好的结构特征,能达到最优扩散层的效果,但其构造函数中的参数比较复杂,搜索空间也较大。为此,对递归扩散层的结构特点进行分析,从低阶扩散层的结构出发,结合最优扩散层的相关理论基础,得到递归扩散层的一般性结论,在此基础上设计权值系数计算方法,并通过仿真实现得到部分低阶递归扩散层的构造函数。分析结果表明,该方法构造的扩散层只需要少数的XOR运算、旋转运算和简单的求反运算,满足最优扩散层的性质,具有较好的安全特性。     

1~5轮LBlock的多项式表示及完全性分析

用统计测试方法分析密码算法的完全性存在误差。为此,利用符号计算软件Mathematica 7.0,以明文和密钥比特为自变量,得到LBlock分组密码第1轮~第5轮输出的多项式表达式,结果显示,LBlock第5轮输出的任何比特至多与45个明文比特、49个密钥比特有关,说明5轮LBlock还未达到完全性。     

LBlock算法的相关密钥不可能差分分析

LBlock算法是2011年提出的轻量级分组密码,适用于资源受限的环境.目前,关于LBlock最好的分析结果为基于14轮不可能差分路径和15轮的相关密钥不可能差分路径,攻击的最高轮数为22轮.为研究LBlock算法抵抗不可能差分性质,结合密钥扩展算法的特点和轮函数本身的结构,构造了新的4条15轮相关密钥不可能差分路径.将15轮差分路径向前扩展4轮、向后扩展3轮,分析了22轮LBlock算法.在已有的相关密钥不可能差分攻击的基础上,深入研究了轮函数中S盒的特点,使用2类相关密钥不可能差分路径.基于部分密钥分别猜测技术降低计算量,分析22轮LBlock所需数据量为261个明文,计算量为259.58次22轮加密.     

AES线性层分析及扩散特性仿真

通过由线性码设计最优扩散线性层的方法,对AES算法的线性层进行分析和仿真,结果表明它具有最优扩散特性,同时证明了这种设计方法的有效性。     

分组密码对称置换算法设计*

证明了对称置换的圈结构与计数,提出并设计了一种以特定对称结构作为分组密码算法的置换部分,以减小加密算法硬件空间,提高加/解密速度。指出了分组密码的多次迭代使对称置换结构复杂化,可以选择对称置换作为分组密码算法的扩散部分来设计。     

Verifiable shuffles: a formal model and a Paillier-based three-round construction with provable security

A shuffle takes a list of ciphertexts and outputs a permuted list of re-encryptions of the input ciphertexts. Mix-nets, a popular method for anonymous routing, can be constructed from a sequence of shuffles and decryption. We propose a formal model for security of verifiable shuffles and a new verifiable shuffle system based on the Paillier encryption scheme, and prove its security in the proposed dmodel. The model is general and can be extended to provide provable security for verifiable shuffle decryption.This paper is the extended version of the paper [37] presented at ACNS ‘04.     

Infinite unfair shuffles and associativity

We consider a general shuffling operation for finite and infinite words which is not necessarily fair. This means that it may be the case that in a shuffle of two words, from some point onwards, one of these words prevails ad infinitum even though the other word still has letters to contribute. Prefixes and limits of shuffles are investigated, leading to a characterization of general shuffles in terms of shuffles of finite words, a result which does not hold for fair shuffles. Associativity of shuffling is an immediate corollary.     

A shuffle to achieve high efficiency through pre-computation and batch verification

Shuffle is an important anonymous routing protocol, in which a shuffling node (router) re-encrypts and reorders some encrypted messages. It is usually used to build anonymous communication networks. A new shuffle scheme is proposed in this paper. A shuffling node’s costly operations can be carried out offline in advance so that its online efficiency is very high. Moreover, any verifier can employ batch verification to efficiently verify validity of the shuffle. As in practical applications of shuffles like e-voting, there are many verifiers including some entities with weak computation capability, and offline pre-computation is a feasible solution for a shuffling node; our proposal is an effective efficiency optimisation mechanism. So our new shuffle design has an advantage in practical efficiency over the existing shuffle schemes. Moreover, its achievement of desired security properties is formally proved only on the base of the most basic computational assumption inevitable in any shuffle. Application of our new shuffle to e-voting is described in the end of this paper to show its importance and applicability in practice.     

Related-Key Impossible Diferential Attack on Reduced-Round LBlock简

LBlock is a 32-round lightweight block cipher with 64-bit block size and 80-bit key. This paper identifies 16- round related-key impossible differentials of LBlock, which are better than the 15-round related-key impossible differentials used in the previous attack. Based on these 16-round related-key impossible differentials, we can attack 23 rounds of LBlock while the previous related-key impossible differential attacks could only work on 22-round LBlock. This makes our attack on LBlock the best attack in terms of the number of attacked rounds.     

Efficient MapReduce algorithms for triangle listing in billion-scale graphs

This paper addresses the classical triangle listing problem, which aims at enumerating all the tuples of three vertices connected with each other by edges. This problem has been intensively studied in internal and external memory, but it is still an urgent challenge in distributed environment where multiple machines across the network can be utilized to achieve good performance and scalability. As one of the de facto computing methodologies in distributed environment, MapReduce has been used in some of existing triangle listing algorithms. However, these algorithms usually need to shuffle a huge amount of intermediate data, which seriously hinders their scalability on large scale graphs. In this paper, we propose a new triangle listing algorithm in MapReduce, FTL, which utilizes a light weight data structure to substantially reduce the intermediate data transferred during the shuffle stage, and also is equipped with multiple-round techniques to ease the burden on memory and network bandwidth when dealing with graphs at billion scale. We prove that the size of the intermediate data can be well bounded near to the number of triangles in the graph. To further reduce the shuffle size and memory cost, we also propose improved algorithms based on a compact data structure, and present several optimization techniques to accelerate the computation and reduce the memory consumption. The extensive experimental results show that our algorithms outperform existing competitors by several times on both synthetic graphs and real world graphs.     

轻量级密码算法LBlock的FPGA优化实现

LBlock密码算法是我国学者吴文玲和张蕾在ACNS2011提出的轻量级分组加密算法.论文对LBlock加密算法的硬件优化实现进行了研究,一方面将相同运算用一个模块设计完成,通过主程序重复调用完成加密;另一方面将轮操作和密钥更新放在同一个模块中并行执行,而且使用相同寄存器完成S盒变换和密钥变换,这样既可以不影响加密速度,又不需要将密钥更新中间结果另存,有效地节省寄存器的使用开销.然后分模块进行实现并仿真实验,和进行整体正确性实验验证.通过实验,验证论文所用优化方法可以较大幅度减少 LBlock 密码算法的实现面积, slices占用比减少了14%, LUT占用比减少了32%.在VIRTEX 5下的系统吞吐率为14.53Gb/s,更能有效满足较小芯片面积的应用需求,给当前的物联网加密提供参考.     

A cross-layer adaptive transmission scheme combined with SR-ARQ over correlated fading channels

Current adaptive transmission schemes all assume independent block fading. However, in slow fading channels, it is highly possible for consecutive block transmissions to be correlated. In this paper, we propose a cross-layer adaptive transmission scheme, which is an optimum combination of modulation format and packet size, combined with selective repeat automatic repeat request (SR-ARQ) to improve the throughput in correlated slow fading channels. We apply a multi-state Markov system model to analyze the system performance and to optimize the selection of modulation levels at the physical layer and packet sizes at the data link layer in a correlated slow fading channel, which is also described by a finite-state Markov chain. A general closed-form expression of the average throughput for this cross-layer adaptive transmission scheme is presented. Simulation results show that our adaptive transmission scheme combined with SR-ARQ can obtain a good performance in correlated slow fading channels.