Conditional TMDTO as a MILP Instance

密钥流 流密码 计算机科学 密码 算法 国家(计算机科学) 密码学 理论计算机科学 数学 加密 操作系统
作者
Satyam Kumar,Santanu Sarkar
标识
DOI:10.1109/tit.2022.3230910
摘要

Conditional Time-Memory-Data Trade-off (TMDTO) attack given by Biryukov and Shamir can be reduced to the following problem: “Find the minimum number of state bits that should be fixed in order to recover the maximum number of state bits by utilizing the keystream bits and value of rest of the state bits”. As per our literature survey, existing algorithms search for state bits that should be fixed (as minimum as possible) in order to recover the maximum possible state bits directly through the keystream bits. However, those algorithms are cipher specific and require extensive manual effort in analyzing the keystream bit equations. In this manuscript, we have constructed an automated framework that is easy to implement and solves the above problem (for the case when bits are fixed to 0) for any NLFSR based stream cipher with better complexity, thereby reducing manual efforts. However, we do not claim any global optimum for fixed bits. We tried to reduce the number of fixed bits as much as possible. To show that our algorithm is applicable to a majority of NLFSR based stream ciphers, we implement it on three different stream ciphers: LIZARD, GRAIN-128a and ESPRESSO. It improves all existing TMDTO results on these ciphers. The framework involves modelling keystream bit equations into a set of linear constraints, which is then solved by using a Mixed Integer Linear Programming (MILP) solver, Gurobi. The advantages of our automated framework over other methods are that we can achieve better results with far less effort, and it can be applied to any stream cipher of a similar structure with very ease. To the best of our knowledge, our MILP model is the first work that converts the conditional TMDTO of a stream cipher into a linear optimization problem. As a consequence, for LIZARD cipher, we reduce the number of fixed bits by 20 bits from the previous best result when the number of recovered bits is 18. In the case of GRAIN-128a, the highest reduction in the number of fixed bits is by 34 bits when the number of recovered bits is 35. Lastly, for ESPRESSO cipher, the reduction is by 7 bits when the number of recovered bits is 35.
最长约 10秒,即可获得该文献文件

科研通智能强力驱动
Strongly Powered by AbleSci AI
更新
大幅提高文件上传限制,最高150M (2024-4-1)

科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
1秒前
任梓宁发布了新的文献求助10
2秒前
SMLW完成签到 ,获得积分10
4秒前
彩色若发布了新的文献求助10
4秒前
davvero发布了新的文献求助10
7秒前
茗竹完成签到,获得积分10
7秒前
ruri完成签到,获得积分10
7秒前
7秒前
7秒前
7秒前
8秒前
Billy应助现实的楼房采纳,获得30
8秒前
8秒前
满意沧海完成签到,获得积分10
8秒前
葵花杜甫完成签到,获得积分20
9秒前
10秒前
CodeCraft应助Fangxintu采纳,获得10
10秒前
周游发布了新的文献求助10
11秒前
香蕉觅云应助赵西里采纳,获得10
11秒前
祝你今天愉快关注了科研通微信公众号
11秒前
11秒前
满意沧海发布了新的文献求助10
12秒前
12秒前
赘婿应助彩色若采纳,获得10
13秒前
13秒前
望仔发布了新的文献求助10
13秒前
13秒前
太阳雨发布了新的文献求助10
14秒前
小太阳发布了新的文献求助10
16秒前
虚心半莲发布了新的文献求助10
16秒前
一一应助周游采纳,获得10
16秒前
16秒前
茗竹发布了新的文献求助10
16秒前
17秒前
17秒前
17秒前
yingtiao完成签到 ,获得积分10
18秒前
18秒前
wzy发布了新的文献求助30
18秒前
YUMI发布了新的文献求助10
18秒前
高分求助中
The late Devonian Standard Conodont Zonation 2000
Nickel superalloy market size, share, growth, trends, and forecast 2023-2030 2000
The Lali Section: An Excellent Reference Section for Upper - Devonian in South China 1500
Smart but Scattered: The Revolutionary Executive Skills Approach to Helping Kids Reach Their Potential (第二版) 1000
Very-high-order BVD Schemes Using β-variable THINC Method 850
Mantiden: Faszinierende Lauerjäger Faszinierende Lauerjäger 800
PraxisRatgeber: Mantiden: Faszinierende Lauerjäger 800
热门求助领域 (近24小时)
化学 医学 生物 材料科学 工程类 有机化学 生物化学 物理 内科学 纳米技术 计算机科学 化学工程 复合材料 基因 遗传学 催化作用 物理化学 免疫学 量子力学 细胞生物学
热门帖子
关注 科研通微信公众号,转发送积分 3252159
求助须知:如何正确求助?哪些是违规求助? 2894970
关于积分的说明 8284470
捐赠科研通 2563627
什么是DOI,文献DOI怎么找? 1391819
科研通“疑难数据库(出版商)”最低求助积分说明 651926
邀请新用户注册赠送积分活动 629033