Practical Evaluation of Security against Generalized Interpolation Attack

Interpolation attack was presented by Jakobsen and Knudsen at FSE'97. Interpolation attack is effective against ciphers that have a certain algebraic structure like the PURE cipher which is a prototype cipher, but it is difficult to apply the attack to real-world ciphers. This difficulty is due to the difficulty of deriving a low degree polynomial relation between ciphertexts and plaintexts. In other words, it is difficult to evaluate the security against interpolation attack. This paper generalizes the interpolation attack. The generalization makes easier to evaluate the security against interpolation attack. We call the generalized interpolation attack linear sum attack. We present an algorithm that evaluates the security of byte-oriented ciphers against linear sum attack. Moreover, we show the relationship between linear sum attack and higher order differential attack. In addition, we show the security of CRYPTON, E2, and RIJNDAEL against linear sum attack using the algorithm.

RSA-Based Password-Authenticated Key Exchange, Revisited

The RSA-based Password-Authenticated Key Exchange (PAKE) protocols have been proposed to realize both mutual authentication and generation of secure session keys where a client is sharing his/her password only with a server and the latter should generate its RSA public/private key pair (e, n), (d, n) every time due to the lack of PKI (Public-Key Infrastructures). One of the ways to avoid a special kind of off-line (so called e-residue) attacks in the RSA-based PAKE protocols is to deploy a challenge/response method by which a client verifies the relative primality of e and φ(n) interactively with a server. However, this kind of RSA-based PAKE protocols did not give any proof of the underlying challenge/response method and therefore could not specify the exact complexity of their protocols since there exists another security parameter, needed in the challenge/response method. In this paper, we first present an RSA-based PAKE (RSA-PAKE) protocol that can deploy two different challenge/response methods (denoted by Challenge/Response Method1 and Challenge/Response Method2). The main contributions of this work include: (1) Based on the number theory, we prove that the Challenge/Response Method1 and the Challenge/Response Method2 are secure against e-residue attacks for any odd prime e; (2) With the security parameter for the on-line attacks, we show that the RSA-PAKE protocol is provably secure in the random oracle model where all of the off-line attacks are not more efficient than on-line dictionary attacks; and (3) By considering the Hamming weight of e and its complexity in the RSA-PAKE protocol, we search for primes to be recommended for a practical use. We also compare the RSA-PAKE protocol with the previous ones mainly in terms of computation and communication complexities.

Linearization Method and Linear Complexity

We focus on the relationship between the linearization method and linear complexity and show that the linearization method is another effective technique for calculating linear complexity. We analyze its effectiveness by comparing with the logic circuit method. We compare the relevant conditions and necessary computational cost with those of the Berlekamp-Massey algorithm and the Games-Chan algorithm. The significant property of a linearization method is that it needs no output sequence from a pseudo-random number generator (PRNG) because it calculates linear complexity using the algebraic expression of its algorithm. When a PRNG has n [bit] stages (registers or internal states), the necessary computational cost is smaller than O(2n). On the other hand, the Berlekamp-Massey algorithm needs O(N2) where N ( 2n) denotes period. Since existing methods calculate using the output sequence, an initial value of PRNG influences a resultant value of linear complexity. Therefore, a linear complexity is generally given as an estimate value. On the other hand, a linearization method calculates from an algorithm of PRNG, it can determine the lower bound of linear complexity.

Modelica建模软件形成的高指标微分代数方程系统指标约简算法研究

随着产品设计的复杂化，应用领域中的数学建模和仿真越来越重要，传统建模方法基于赋值语句，主要考虑单一系统，工程人员需要对程序设计语言和算法求解有相当程度的熟悉，这导致了传统建模方法很难满足复杂产品设计的需要。欧洲仿真界的学者在总结现有建模方法的基础上于1997年推出了一种面向对象的、陈述式的基于方程的语言——Modelica，Modelica语言支持多领域建模，Modelica语言得到了仿真领域众多厂商的支持，成为统一建模领域的事实标准，实现Modelica仿真环境具有重大意义。 编译器是Modelica仿真环境中的核心组件，Modelica编译器会产生高指标DAE系统，除了部分特殊结构的高指标DAE，现有求解器一般不能对通用高指标DAE直接求解，现在一般做法是先对高指标DAE进行指标约简，将其转换成等价的低指标DAE，然后进行求解。这就要求Modelica编译器具有指标约简的功能，以便利用现有求解器进行求解。 本文介绍了几种现有的指标约简算法，给出了各个算法指标约简原理和约简步骤，并对这些算法进行了分析和比较，得出各自的优缺点。最后，本文设计并实现了一个指标约简系统，采用三个Modelica模型产生的方程对系统进行了测试，并验证了实验结果的正确性。

Modelica建模软件中求强连通分量与拓扑排序算法优化的研究

Modelica语言仿真建模在科研工作中已经得到了广泛应用。它能方便地对包含机械、电子、液压、控制、热流等领域的复合物理系统进行基于组件的仿真。现有基于Modelica语言的仿真建模软件支持图形化建模和文本建模两种方式，集成了面向对象、陈述式描述、统一建模、组件重用的优势，给科研工作带来了巨大的便利。 Modelica软件仿真的过程可归结为微分代数方程(differential algebraic equation,DAE)系统的求解。在求解DAE系统时，需要对DAE系统进行约简，直到庞大的DAE系统约简为目前自动求解方法成熟的ODE系统，或约简为方程个数不多的、指标较低的DAE系统，才能使Modelica建模仿真软件具有工业上的应用价值。在约简DAE系统之前，需要对之进行预处理，根据方程之间的数据依赖关系进行拓扑排序，确定求解顺序。排序的过程对应着将DAE系统结构关联矩阵进行块状下三角(block lower triangle,BLT)变换。寻找强连通分量和拓扑排序是对DAE系统进行预处理的重要组成部分。 本文剖析了Modelica软件在仿真时的运行机制，使用几个实例来详细描述在仿真过程中，Modelica软件完成的工作。在寻找强连通分量和拓扑排序这一步，本文提出了使用Kosaraju算法的策略，对由模型得到的有向图直接使用Kosaraju算法，得出DAE系统的求解顺序。文章叙述了强连通分量的含义，并阐述了在求强连通分量时的理论依据，由此引出了Tarjan算法和Kosaraju算法，再分析和比较Tarjan算法和Kosaraju算法，对比了两种策略的优劣，并进行了实验。同时，本文分析了OpenModelica软件包的结构，修改了软件包在寻找强连通分量及拓扑排序相关模块的代码。

yet another meta-language for programming language processing

The formal specification language LFC was designed to support formal specification acquisition. However, it is yet suited to be used as a meta-language for specifying programming language processing. This paper introduces LFC as a meta-language, and compares it with ASF+SDF, an algebraic specification formalism that can also be used to programming languages.

an improved smart card based password authentication scheme with provable security

Password authentication has been adopted as one of the most commonly used solutions in network environment to protect resources from unauthorized access. Recently, Lee–Kim–Yoo [S.W. Lee, H.S. Kim, K.Y. Yoo, Improvement of Chien et al.'s remote user authentication scheme using smart cards, Computer Standards & Interfaces 27 (2) (2005) 181–183] and Lee-Chiu [N.Y. Lee, Y.C. Chiu, Improved remote authentication scheme with smart card, Computer Standards & Interfaces 27 (2) (2005) 177–180] respectively proposed a smart card based password authentication scheme. We show that these two schemes are both subject to forgery attacks provided that the information stored in the smart card is disclosed by the adversary. We also propose an improved scheme with formal security proof.

欧洲21世纪数据加密标准候选算法简评

简要介绍了欧洲 NESSIE( new European schemes for signatures,integrity,and encryption)大计划最近公布的 17个分组密码算法的基本设计思想、最新分析结果及其有效性 .

对DES的Rectangle攻击和Boomerang攻击

作为加密标准，DES（data encryption standard）算法虽然已被AES（advanced encryption standard）算法所取代，但其仍有着不可忽视的重要作用．在一些领域，尤其是金融领域，DES和Triple DES仍被广泛使用着．而近年来又提出了一些新的密码分析方法，其中，Rectangle攻击和Boomerang攻击已被证明是非常强大而有效的．因此，有必要重新评估DES算法抵抗这些新分析方法的能力．研究了DES算法针对Rectangle攻击和Boomerang攻击的安全性．利用DES各轮最优差分路径及其概率，分别得到了对12轮DES的Rectangle攻击和对11轮DES的Boomerang攻击．攻击结果分别为：利用Rectangle攻击可以攻击到12轮DES，数据复杂度为2~(62)。个选择明文，时间复杂度为2~(42)次12轮加密；利用Boomerang攻击可以攻击到11轮DES，数据复杂度为2~(58)个适应性选择明密文，时间复杂度为2~(38)次11轮加密．由于使用的都是DES各轮的最优差分路径，所以可以相信，该结果是Rectangle攻击和Boomerang攻击对DES所能达到的最好结果．

对低轮AES-256的相关密钥-不可能差分密码分析

研究AES-256抵抗相关密钥-不可能差分密码分析的能力.首先给出相关密钥的差分,该差分可以扩展到8轮(甚至更多轮)子密钥差分;然后构造出一个5.5轮的相关密钥不可能差分特征.最后,给出一个对7轮AES-256的攻击和4个对8轮AES-256的攻击.