Double-block Hash-then-Sum MAC의 정확한 안전성 증명

KAIST 전산학부 정보보호대학원 박사과정 김성광, 이병학, 이주영 교수

메시지 인증 코드(MAC)은 데이터 무결성을 위해 필요하며 그 안전성 보장은 매우 중요한 과제이다. 이주영 교수 연구팀은 SUM-ECBC, 3kf9, PMAC-Plus, LightMAC-Plus 등 n-비트 블록 암호를 사용하여 2n-비트의 내부 상태를 갱신하는 형태인 double-bock hash-then-sum (DbHtS) MAC의 정확한 안전성을 증명하였다. 이들 구조는 모두 2n/3-bit 안전성이 증명되어 있었지만 최근 3n/4-bit 수준의 공격이 제안되면서 이들의 정확한 안전성이 미해결 문제로 남아있었는데 이번 연구로 이들 구조는 실제로 3n/4-bit 수준의 안전성을 가진다는 것이 증명되었다.

그림 1. PMAC-Plus

그림 1은 DbHtS MAC 중 하나인 PMAC-Plus의 묘사도이다. 그림에서 볼 수 있듯 DbHtS MAC은 메시지를 압축하는 해시 함수와 결과를 암호화한 뒤 그 차분을 출력하는 후처리 함수로 나눌 수 있다. 기존 연구에선 이 해시 함수가 blockwise-universality (블록 균일성)와cover-free의 성질을 가지면 후처리 함수와 결합되었을 때 2n/3-bit 안전성을 가진다는 것을 증명했는데, 이주영 교수 연구팀은 이 해시 함수가 추가로 alternative collision resistance를 만족한다면 3n/4-bit 안전성을 가진다는 것을 증명하였고 실제로 SUM-ECBC, 3kf9, PMAC-Plus, LightMAC-Plus에서 사용된 해시 함수들은 모두 이를 만족한다는 것 역시 증명하였다.

또한 후처리 함수의 안전성을 증명하기 위해 미러 이론(방정식 및 부등식의 해의 개수를 근사하는 이론)이 쓰이는데, 2n/3-bit 안전성까지 적용 가능했던 기존 이론을 더욱 발전시켜 3n/4-bit 안전성까지 적용 가능하도록 만들었다. 이는 방정식과 부등식들이 서로서로 연관을 가질 수 있는 상황의 미러 이론에 대한 결과 중 가장 발전된 형태의 결과로, 이번 논문에서 최초로 후처리 함수의 3n/4-bit 안전성을 증명하는데 활용되었으며 해시 함수에 대한 결과와 종합하여 DbHtS MAC의 3n/4-bit 안전성을 증명할 수 있었다.

이 논문(“Tight Security Bounds for Double-block Hash-then-Sum MACs”)은 위의 성과를 인정받아 암호학 분야 최우수 학회 Eurocrypt 2020에 채택되어 발표될 예정이다.