• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Designs, Codes and Crytography >A generalized birthday approach for efficiently finding linear relations in ℓ-sequences
【24h】

A generalized birthday approach for efficiently finding linear relations in ℓ-sequences

机译：一种有效求ℓ序列线性关系的广义生日方法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Feedback with carry shift registers (FCSRs) have previously been available in two configurations, the Fibonacci and Galois architectures. Recently, a generalized and unifying FCSR structure and theory was presented. The new ring FCSR model repairs some weaknesses of the older architectures. Most notably, the carry cell bias property that was exploited for an attack on the eSTREAM final portfolio cipher F-FCSR-H v2 is no longer possible for the updated (and unbroken) F-FCSR-H v3 stream cipher. In this paper we show how to exploit a particular set of linear relations in ring FCSR sequences. We show what biases can be expected, and we also present a generalized birthday algorithm for actually realizing these relations. As all prerequisites of a distinguishing attack are present, we explicitly show a new such attack on F-FCSR-H v3 with an online time complexity of only 2~(37.2). The offline time complexity (for finding a linear relation) is 2~(56.2). This is the first successful attack on F-FCSR-H v3, the first attack to breach the exhaustive search complexity limit. Note that this attack is completely different from that of F-FCSR-H v2. We focus on this particular application in the paper, but the presented algorithm is actually very general. The algorithm can be applied to any FCSR automaton, so linearly filtered FCSRs and FCSR combiners may be particularly interesting targets for cryptanalysis.
机译：带有进位移位寄存器（FCSR）的反馈以前有两种配置，斐波那契和伽罗瓦体系结构。最近，提出了一种广义的，统一的FCSR结构和理论。新的环形FCSR模型修复了旧体系结构的一些弱点。最值得注意的是，对于更新（且不间断）的F-FCSR-H v3流密码，攻击eSTREAM最终投资组合密码F-FCSR-H v2所利用的携带信元偏置特性不再可能。在本文中，我们展示了如何利用环状FCSR序列中的特定线性关系集。我们展示了可以预期的偏差，并且还提出了用于实际实现这些关系的通用生日算法。由于存在区别攻击的所有先决条件，因此我们明确显示了针对F-FCSR-H v3的此类新攻击，其在线时间复杂度仅为2〜（37.2）。离线时间复杂度（用于找到线性关系）为2〜（56.2）。这是对F-FCSR-H v3的首次成功攻击，这是首次突破详尽的搜索复杂性限制的攻击。请注意，此攻击与F-FCSR-H v2完全不同。在本文中，我们专注于这种特定的应用，但是提出的算法实际上非常通用。该算法可以应用于任何FCSR自动机，因此线性滤波的FCSR和FCSR合并器可能是密码分析特别感兴趣的目标。

著录项

  • 来源
    《Designs, Codes and Crytography》 |2015年第1期|41-57|共17页
  • 作者

    Hui Wang; Paul Stankovski; Thomas Johansson;

  • 作者单位

    Shanghai Key Lab of Intelligent Information Processing, School of Computer Science, Fudan University, Shanghai 200433, People's Republic of China;

    Deptartment of Electrical and Information Technology, Lund University, Box 118, Lund 221 00, Sweden;

    Deptartment of Electrical and Information Technology, Lund University, Box 118, Lund 221 00, Sweden;

  • 收录信息 美国《科学引文索引》(SCI);美国《工程索引》(EI);
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

    FCSR; Linear relations; Generalized birthday attack; Distinguisher;

    机译：FCSR;线性关系;广义生日袭击;区分器;

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号