SNI 안전성을 가진 효율적인 AES S-Box 마스킹 설계 = Design of Efficient and t-SNI Secure Higher-order masking of AES S-Box

국문 초록 (Abstract)

부채널 분석은 시간, 전자파, 전력 등 부채널 정보를 이용하여 비밀 키를 탈취하는 공격 기법으로 암호 알고리즘이 동작하는 암호 장치의 비밀 정보를 쉽게 탈취할 수 있다. 따라서 랜덤 바이트를 통해 비밀 정보를 분할하여 부채널 분석 공격을 막는 주요한 기법 중 하나인 마스킹 연구와 고차 부채널 분석 공격을 막는 고차 마스킹 기법에 관한 연구가 활발히 진행되고 있다. 고차 마스킹 기법은 부채널 분석에 대한 이론적인 보안성을 제공하지만, 마스킹 기법을 적용 안한 대상에 비해 느리고 대량의 random bytes를 요구하는 등 필연적으로 추가 오버헤드를 초래하기 때문에, 효율성이 저하된다. 따라서 효율적인 고차 마스킹 기법이 필요하다.
본 논문은 SNI 안전성을 가진 효율적인 고차 AES S-Box 마스킹을 제안한다. 결합 probing security가 등장하기 이전, 제안된 합성체와 look-up table을 이용한 고차 AES S-Box 마스킹 연구 경우, 결합 probing security에 대한 안전성을 만족하지 않아 t+1 shares일 때, t-probing security를 만족하지 않는다.
본 논문은 해당 논문인 이론적으로 왜 t+1 shares일 때, t-probing security를 만족하지 않는지 보여주고, 실제 환경에서 파형을 수집하여 3 share일 때, 2차 상관 전력 분석 성공하고 실제 Test Vector Leakage Assessment 시험 검증을 했을 때 실패함을 보여준다. 그리고 해당 문제에 대한 원인을 파악하여 이전에 제안된 고차 AES S-Box 마스킹 기법을 개선하고 common multiplication 기법을 적용하고 coupling 현상을 제거하여 SNI 안전성을 만족하는 효율적인 고차 AES S-Box 마스킹 기법을 제안한다. 제안한 기법에 대해 t-probing security를 증명하여 부채널 분석에 대한 이론적인 안전성을 제공하고 1차 TVLA와 multivariate TVLA test를 통해서 현실적인 부채널 분석에 대해 안전함을 증명했다. 그리고 이전에 보였던 3 shares일 때 2차 상관 전력 분석 실패함을 보여주어 기존 취약점에 대해 안전함을 보여준다.
본 논문이 제안한 고차 AES S-Box 마스킹과 같은 SNI 안전성을 만족하는 다른 고차 AES S-Box 마스킹과의 성능 비교 결과, 사용되는 random bytes 수를 최소 39% 줄이고 clock cycle을 76% 줄여 성능이 향상했음을 보였다. 그리고 이전 합성체와 look-up table을 이용한 고차 AES S-Box 마스킹 연구와 비교했을 때, 약 37% clock cycle을 줄였으며, 약 55%의 random bytes 수를 줄여 효율적임을 보였다.

다국어 초록 (Multilingual Abstract)

Side-channel analysis (SCA) is attack technique that exploits physical leakage such as timing, electromagnetic radiation, and power consumption to recover secret keys from cryptographic devices. Since secret information can be efficiently extracted from cryptographic implementations, masking has been widely studied as a fundamental countermeasure against SCA by splitting sensitive variables using random bytes. In particular, higher-order masking schemes have been actively researched to resist higher-order side-channel attacks. Although higher-order masking provides strong theoretical security guarantees, it inevitably introduces significant overhead in terms of performance degradation and increased consumption of random bytes, leading to reduced efficiency. Therefore, the development of efficient higher-order masking schemes remains an important research challenge.
In this paper, we propose an efficient higher-order AES S-Box masking scheme that satisfies Strong Non-Interference (SNI) security. Prior to the introduction of composable probing security, several higher-order AES S-Box masking schemes based on composite fields and look-up tables were proposed. However, these schemes do not satisfy composable probing security and consequently fail to achieve -probing security when implemented with t+1 shares.
We theoretically analyze why these existing schemes do not satisfy t-probing security for t+1 shares. Furthermore, through practical experiments, we collect power traces and demonstrate that second-order correlation power analysis (CPA) successfully recovers the secret key in the case of three shares. We also show that these implementations fail the Test Vector Leakage Assessment (TVLA) in real-world evaluation. By identifying the root causes of these vulnerabilities, we improve the previously proposed higher-order AES S-Box masking schemes by applying the common multiplication technique and eliminating coupling effects. As a result, we present a more efficient higher-order AES S-Box masking scheme that satisfy SNI security. The proposed scheme is proven to satisfy t-probing security, providing strong theoretical guarantees against side-channel attacks. In addition, its practical resistance is validated through first-order TVLA and multivariate TVLA tests. We also demonstrate that the previously successful second-order CPA attack on the three-share implementation is no longer effective, confirming that the identified vulnerabilities have been mitigated.
Performance evaluations show that, compared to other SNI-secure higher-order AES S-Box masking schemes, the proposed method reduces the number of required random bytes by up to 39% and the number of clock cycles by up to 76%. Moreover, when compared to earlier composite-field and look-up-table based higher-order AES S-Box masking schemes, our approach achieves approximately a 37% reduction in clock cycles and a 55% reduction in random byte consumption, demonstrating its superior efficiency.

목차 (Table of Contents)

• 제 1 장. 서론 1
• 제 2 장. 배경 지식 4
• 제 1 절. 표기법 4
• 제 2 절. AES S-Box 4
• 제 3 절. Masking 대응기법 5
• 3.1. Probing security 보안 증명 개념 6
• 3.2. 함수별 고차 마스킹 적용 방안 10
• 3.2.1. 선형 함수의 고차 마스킹 적용 방안 10
• 3.2.2. 비선형 함수의 고차 마스킹 적용 방안 11
• 3.2.2.1. Multiplication 11
• 3.2.2.2. Refreshmask 13
• 3.2.3. 고차 AES S-Box 적용 방안 15
• 3.2.3.1. 지수승 기반 고차 AES S-Box 마스킹 기법 15
• 3.2.3.2. 합성체와 Look-up table 기반 고차 AES S-Box 마스킹 기법 18
• 제 3 장. 효율적이고 안전한 고차 AES S-Box 마스킹 기법 23
• 제 1 절. 기존 논문의 부채널 공격 24
• 1.1. 이론적인 부채널 공격 24
• 1.2. 실험적인 부채널 공격 26
• 1.3. TVLA 결과 30
• 1.4. 해결 방안 33
• 제 2 절. 효율적이고 안전한 고차 AES S-Box 마스킹 설계 34
• 2.1. 제안한 고차 마스킹 알고리즘 설계 34
• 2.2. Coupling 효과 제거 38
• 제 3 절. 제안한 고차 AES S-Box 마스킹의 이론적 안전성 증명 40
• 3.1. 고차 역원 마스킹의 이론적 안전성 증명 40
• 3.2. 고차 AES S-Box 마스킹의 이론적 안전성 증명 42
• 제 4 장. 실용적인 부채널 누설 평가 47
• 제 1 절. TVLA 검증 결과 47
• 제 2 절. 2차 상관 전력 분석 공격 결과 50
• 제 5 장. 성능 평가 53
• 제 6 장. 결론 54