Study on Static Detection of Timing Side Channel for RISC-V Architecture

doi:10.3969/j.issn.1671-1122.2022.04.002

Abstract

Abstract:

Timing side channel attacks pose a serious threat to software confidentiality for the open source RISC-V architecture, but there is currently lack of research on static analysis of timing side channel leakage on the RISC-V architecture. This paper evaluated the scope of application, advantages and disadvantages of common static analysis methods for timing side channel leakage, optimized the analysis algorithms according to the characteristics of RISC-V assembly language, and implemented a combined information flow analysis method for the 64-bit general instruction set of RISC-V RV64G and a temporal side-channel analysis model that simplified symbolic execution theory. This paper tests the implementation of AES, RSA and also other cryptographic algorithms of the general open source network communication cryptographic library OpenSSL and NaCl. The test results show that compared with the existing analysis tool that has the highest accuracy rate, the model in this paper approximately improved the accuracy by 17% and reduced the false negative rate by 22% under the same test vector, which improved the analysis speed and alleviated the path explosion problem to a certain extent, providing a reference for the design of side-channel analysis tools on RISC-V architecture.

Key words: timing side channel, static detection, RISC-V architecture, cryptographic algorithm

CLC Number:

TP309

TANG Ming, LI Cong, LI Yongbo, YUE Tianyu. Study on Static Detection of Timing Side Channel for RISC-V Architecture[J]. Netinfo Security, 2022, 22(4): 7-19.

Figures/Tables 13

References 32

[1]	KOCHER P, HORN J, FOGH A, et al. Spectre Attacks: Exploiting Speculative Execution[C]// IEEE. 2019 IEEE Symposium on Security and Privacy (SP). New York: IEEE, 2019: 1-19.
[2]	LIPP M, SCHWARZ M, GRUSS D, et al. Meltdown: Reading Kernel Memory from User Space[C]// USENIX. 27th USENIX Security Symposium (USENIX Security18). Berkeley: USENIX, 2018: 973-990.
[3]	LE A T, DAO B A, SUZAKI K, et al. Experiment on Replication of Side Channel Attack via Cache of RISC-V Berkeley Out-of-Order Machine (BOOM) Implemented on FPGA[EB/OL]. (2020-05-26)[2021-08-21]. [2021-08-21]. https://carrv.github.io/2020/slides/CARRV2020_slides_2_Le.pdf .
[4]	GONZALEZ A, KORPAN B, ZHAO J, et al. Replicating and Mitigating Spectre Attacks on an Open Source RISC-V Microarchitecture[EB/OL]. (2019-06-22)[2021-09-11]. https://carrv.github.io/2019/papers/carrv2019_paper_5.pdf .
[5]	CAMPOS F, JELLEMA L, LEMMEN M, et al. Assembly or Optimized C for Lightweight Cryptography on RISC-V[C]// Springer. International Conference on Cryptology and Network Security. Heidelberg: Springer, 2020: 526-545.
[6]	AUJLA G S, CHAUDHARY R, KUMAR N, et al. SecSVA: Secure Storage, Verification, and Auditing of Big Data in the Cloud Environment[J]. IEEE Communications Magazine, 2018, 56(1): 78-85.
[7]	LE A T, HOANG T T, DAO B A, et al. A Real-Time Cache Side-Channel Attack Detection System on RISC-V Out-of-Order Processor[J]. IEEE ACCESS, 2021(9): 164597-164612.
[8]	PISTOIA M, CHANDRA S, FINK S J, et al. A Survey of Static Analysis Methods for Identifying Security Vulnerabilities in Software Systems[J]. IBM Systems Journal, 2007, 46(2): 265-288. doi: 10.1147/sj.462.0265 URL
[9]	MOLNAR D, PIOTROWSKI M, SCHULTZ D, et al. The Program Counter Security Model: Automatic Detection and Removal of Control-Flow Side Channel Attacks[C]// Springer. International Conference on Information Security and Cryptology. Heidelberg: Springer, 2005: 156-168.
[10]	LUX A, STAROSTIN A. A Tool for Static Detection of Timing Channels in JAVA[J]. Journal of Cryptographic Engineering, 2011, 1(4): 303-313. doi: 10.1007/s13389-011-0021-z URL
[11]	DEWALD F, MANTEL H, WEBER A. AVR Processors as a Platform for Language-Based Security[C]// Springer. European Symposium on Research in Computer Security. Heidelberg: Springer, 2017: 427-445.
[12]	KRAK R. Cycle-Accurate Timing Channel Analysis of Binary Code[D]. Enschede: University of Twente, 2017.
[13]	WANG F, SHOSHITAISHVILI Y. Angr-the Next Generation of Binary Analysis[C]// IEEE. 2017 IEEE Cybersecurity Development (SecDev). New York: IEEE, 2017: 8-9.
[14]	ASANOVIC K, AVIZIENIS R, BACHRACH J, et al. The Rocket Chip Generator[R]. Berkeley: University of California at Berkeley, UCB/EECS-2016-17, 2016.
[15]	ASANOVIC K, PATTERSON D A, CELIO C. The Berkeley Out-of-Order Machine (BOOM): An Industry-Competitive, Synthesizable, Parameterized RISC-V Processor[R]. Berkeley: University of California at Berkeley, UCB/EECS-2015-167, 2015.
[16]	DOYCHEV G, KÖPF B, MAUBORGNE L, et al. CacheAudit: A Tool for the Static Analysis of Cache Side Channels[J]. ACM Transactions on Information and System Security, 2015, 18(4): 1-32.
[17]	WANG Guanhua, CHATTOPADHYAY S, BISWAS A K, et al. KLEEspectre: Detecting Information Leakage through Speculative Cache Attacks via Symbolic Execution[J]. ACM Transactions on Software Engineering and Methodology (TOSEM), 2020, 29(3): 1-31.
[18]	CADAR C, DUNBAR D, ENGLER D R. Klee: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs[C]// USENIX. 8th USENIX Conference on Operating Systems Design & Implementation (OSDI). Berkeley: USENIX, 2009.
[19]	ROSCOE A W, WOODCOCK J C P, WULF L. Non-Interference through Determinism[C]// Springer. European Symposium on Research in Computer Security. Heidelberg: Springer, 1994: 31-53.
[20]	BERNSTEIN D J. Cache-Timing Attacks on AES[EB/OL]. (2005-04-15)[2021-09-23]. https://www.researchgate.net/publication/228939782_Cache-timing_attacks_on_AES .
[21]	ANDRYSCO M, KOHLBRENNER D, MOWERY K, et al. On Subnormal Floating Point and Abnormal Timing[C]// On Subnormal Floating Point and Abnormal Timing[C]//IEEE. 2015 IEEE Symposium on Security and Privacy. New York: IEEE, 2015: 623-639.
[22]	WATERMAN A, LEE Y, PATTERSON D A, et al. The RISC-V Instruction Set Manual[R]. University of California at Berkeley, UCB/EECS-2014-54, 2014.
[23]	JOHNSON D B. Finding All the Elementary Circuits of a Directed Graph[J]. SIAM Journal on Computing, 1975, 4(1): 77-84. doi: 10.1137/0204007 URL
[24]	TARJAN R. Depth-First Search and Linear Graph Algorithms[J]. SIAM Journal on Computing, 1972, 1(2): 146-160. doi: 10.1137/0201010 URL
[25]	DIGILEN T. Xilinx Zedboard Document[EB/OL]. (2017-12-31)[2021-10-27]. http://www.digilentinc.com/Products/Detail.cfm?Prod=ZEDBOARD/ .
[26]	KOCHER P, HORN J, FOGH A, et al. Spectre Attacks: Exploiting Speculative Execution[C]// IEEE. 2019 IEEE Symposium on Security and Privacy (SP). New York: IEEE, 2019: 1-19.
[27]	BRUMLEY B B, TUVERI N. Remote Timing Attacks are Still Practical[C]// Springer. European Symposium on Research in Computer Security. Heidelberg: Springer, 2011: 355-371.
[28]	FINKE T, GEBHARDT M, SCHINDLER W. A New Side-Channel Attack on RSA Prime Generation[C]// Springer. International Workshop on Cryptographic Hardware and Embedded Systems. Heidelberg: Springer, 2009: 141-155.
[29]	CAULIGI S, SOELLER G, BROWN F, et al. Fact: A Flexible, Constant-Time Programming Language[C]// IEEE. 2017 IEEE Cybersecurity Development (SecDev). New York: IEEE, 2017: 69-76.
[30]	BRUMLEY D, BONEH D. Remote Timing Attacks are Practical[J]. Computer Networks, 2005, 48(5): 701-716. doi: 10.1016/j.comnet.2005.01.010 URL
[31]	WANG Wenbo, FAN Shuqin. Attacking OpenSSL ECDSA with a Small Amount of Side-Channel Information[J]. Science China Information Sciences, 2018, 61(3): 1-14. doi: 10.1007/s11432-017-9235-7 URL
[32]	FUA P, LIS K. Comparing Python, Go, and C++ on the N-Queens Problem[EB/OL]. (2020-01-08)[2021-11-13]. https://arxiv.org/abs/2001.02491 .

工具名称	检测程序的语言类型	覆盖时间泄露种类	硬件架构	检测密码库	技术路线
程序计数器模型^[9]	C	循环/分支	高级语言检测	简化的C语言Demo	信息流分析
SCF-AVR^[11]	AVR汇编	循环/分支	AVR	µNaCl	信息流分析
SMArTCAT^[12]	VEX(IR)	循环/分支/Cache	ARM	OpenSSL	符号执行
SCF-JAVA^[10]	Java	循环/分支	高级语言检测	Java FlexiProvider/GNU Classpath	信息流分析
CacheAudit^[16]	x86汇编	Cache	x86	PolarSSL	抽象解释
KleeSpectre^[17]	LLVM(IR)	Spectre v1	x86	LibTom Crypt/OpenSSL	符号执行
本文模型	RV64G 汇编	循环/分支/ Cache/浮点	RISC-V	OpenSSL/NaCl	信息流分析+简化符号执行

	数字序号	文件名	泄露函数声明	泄露种类	汇编定位	高级程序语言定位	耗时
格式	Number	File.c	Type Func(Param1…)	None/CF-BR/CF-LP/DF-Cache/DF-FP	汇编地址:汇编指令	行数:语句	时间/ms
示例	1	rsa.c	long long Modular_Exponentiation(long long, int, int)	CF-LP	101c4: 04078e63 beqz x15,1022	line 114: while (num != 0)	2076

分类名称	指令原型	预估时钟周期	敏感信息传递流向	备注
寄存器立即数	instr rd, imm	1	rd → rd	—
2寄存器	instr rd, rs	1	rd&rs → rd	—
2寄存器立即数	instr rd, rs, imm	1	rd&rs → rd	—
2寄存器间接跳转(LOAD/STORE)	load	3	rd&rs → rd	取Cache miss时的周期
2寄存器间接跳转(LOAD/STORE)	store	1	rd&rs → rd	取Cache miss时的周期
3寄存器	imul	10	rd&rs1&rs2 → rd	—
	idiv(单字)	34		—
	idiv(双字)	66		—
	fadd, fmul, fmadd (单字)	5		—
	fadd, fmul, fmadd (双字)	7		—
	fdiv	20		—
	fsqrt	25		—
	instr rd, rs1, rs2	1		除特殊指令以外的3寄存器指令
4寄存器	instr rd, rs1, rs2(rs3)	1	rd&rs1&rs2&rs3 → rd	—
分支	beq/bne/blt/bltu/bge/bgeu	1	隐式污点传播规则	—
跳转	jalr/jal	1	pass	直接跳转指令不影响污点传播
伪指令	转换为对应真指令后处理	—	pass	—

密码算法名称	泄露类型	泄露函数	复现泄露方法
OpenSSL-AES	DF-Cache	aes_encrypt	S盒产生的泄露^[20]
OpenSSL-RSA	CF-BR	Modular_Exonentiation	多次调用模幂函数Modular_Exonentiation导致循环控制流类时间泄露^[26]
OpenSSL-ECDSA	CF-BR	蒙哥马利乘函数	利用ec2_GF2m_montegomery_multiply 函数恢复部分密钥^[27]
OpenSSL-BlowFish	DF-Cache	bf_encrypt	S盒产生的泄露^[28]
OpenSSL-RC2	DF-Cache	RC2_set_key	存在于密钥设置函数中的泄露,存在一个类似S盒的查找表
OpenSSL-RC4	DF-Cache	RC2_set_key	来自加密函数RC4,存在一个类似S盒的查找表
NaCl-AES	无泄露	无	无
NaCl-RSA	无泄露	无	无
Demo-AES	CF-LP	x2_time	存在循环时间泄露的AES实现程序
Demo-FP	DF-FP	Demo_FP	目前主要复现的是针对Firefox等浏览器的隐私数据库的像素窃取攻击^[21],在通用密码库中很难找到该类泄露

检测程序	本文模型	AVR 模型	SMArTCAT模型	CacheAudit模型	验证可利用漏洞数
OpenSSL-AES	2	2	1	1	1
OpenSSL-RSA	2	2	1	0	1
OpenSSL-ECDSA	2	5	4	1	2
OpenSSL-BlowFish	1	3	3	1	1
OpenSSL-RC2	1	3	2	1	1
OpenSSL-RC4	1	2	1	1	1
NaCl-AES	1	1	0	1	0
NaCl-RSA	1	1	1	2	0
Demo-AES	1	1	1	1	1
Demo-FP	1	0	0	0	1
总计	13	20	14	9	9