Paper 2024/1913

Key Guidance Invocation: A White-box Mode Enables Strong Space Hardness under Adaptively Chosen-Space Attacks

Abstract

The notion of space hardness serves as a quantitative measure to characterize the resilience of dedicated white-box schemes against code-lifting attacks, making it a widely utilized metric in the field. However, achieving strong space hardness (SSH) under the adaptively chosen-space attack model (ACSAM) remains an unresolved challenge, as no existing white-box scheme has given SSH guarantees under ACSAM. \par To address the problem, we introduce a novel mode of operation tailored for white-box cryptography, termed the Key Guidance Invocation (KGI) mode. Our security analysis reveals that the KGI mode not only significantly strengthens the resistance to adaptively chosen-space attacks, but also ensures SSH under ACSAM. Moreover, we propose a dedicated white-box construction, RubikStone-($n$,$n_{in}$,$R$,$s$), which directly leverages the concept of the lookup table pool. RubikStone offers enhanced flexibility in lookup table utilization compared to existing white-box constructions and is particularly well-suited to the KGI mode. \par Additionally, we instantiate RubikStone-(256,8,12,$2^{16}$) with the KGI mode, resulting in $\mathsf{RS_{KGI}}$-256, which delivers $(T/4,127.99)$-SSH security guarantees under ACSAM. Remarkably, $\mathsf{RS_{KGI}}$-256 also shows superior performance, surpassing the efficiency of white-box AES based on the CEJO framework by $27.1\%$ in real-world settings. Besides, we conduct a comprehensive statistical analysis of the operations in all existing white-box ciphers. Our findings indicate that $\mathsf{RS_{KGI}}$-256 remains highly competitive in computational efficiency despite offering unprecedented security.