Confidentiality aims to keep the message content private to everyone except authorized users, while authenticity aims to verify that the message content was created by a legitimate author, and those are two major goals of cryptography. In symmetric-key cryptography, confidentiality is guaranteed through message encryption and authentication through message authentication codes (MACs). Authenticated encryption (AE) provides both confidentiality and authenticity at the same time. Most of the currently widely used symmetric-key cryptographic schemes provide security within the birthday-bound of the input length of the underlying primitive. For example, the GCM authenticated encryption mode guarantees security only for less than 2^64 messages when 128-bit block cipher (e.g. AES) is used. Although this security security bound is still sufficient in most environment, as data usage increases, the need for symmetric-key cryptographic schemes that provide higher security is increasing. From this point of view, this study deals with authentication encryption and message authentication schemes with beyond birthday-bound security, especially, 1) security analysis on Double-block Hash-then-Sum (DbHtS) and 2) the proposal and analysis of Synthetic Counter with Masking (SCM), a nonce-misuse-resistance authentication encryption that provides almost-perfect security.
DbHtS MAC has a structure that uses double-block internal state, PolyMAC, SUM-ECBC, 3kf9, PMAC-Plus, and LightMAC-Plus that follow this structure and all of them have been proved to be pseudorandom up to 2^{2n/3} queries when they are instantiated with an n-bit block cipher, while the best known generic attacks require 2^{3n/4} queries. In this study, we proved that all DbHtS MACs are secure up to
2^{3n/4} queries through a refinement of mirror theory and identification of the security requirements of the internal hash function.
SCM follows the NSIV structure proposed by Peyrin and Seurin, encrypts the nonce and the hashed message separately, then adds them to create a tag, and uses both the tag and nonce to encrypt the message in a similar way to counter mode. As a result, we obtain, for the first time, a block cipherbased authenticated encryption scheme of rate 1/2 that provides n-bit security with respect to the query complexity. The efficiency of SCM was slightly better than AES-GCM-SIV, which is a standardized misuse-resistant AE.
기밀성과 무결성은 각각 허가받지 않은 사용자에 의한 정보의 접근과 정보의 수정을 차단하는 성질로, 암호학의 가장 큰 두 가지 목표이다. 대칭키 암호에서 기밀성은 메시지 암호화를 통해, 무결성은 메시지 인증코드(Message Authentication Codes, MAC)를 통해 보장되며 인증 암호화 모드(Authenticated Encryption)는 기밀성과 무결성을 동시에 제공한다. 현재 널리 사용되고 있는 대칭키 암호 프리미티브들은 대부분 기반 프리미티브의 입력 길이에 대한 생일 상한(birthday-bound) 이내의 안전성을 제공한다. 예를 들어, 128bit 블록 암호인 AES기반의 인증 암호화 모드 AES-GCM은 2^64개보다 적은 수의 메시지에 대해서만 안전성을 보장한다. 아직 대부분의 상황에서 이러한 안전성 상한은 충분하지만, 데이터 사용량이 늘어남에 따라 더 높은 안전성을 제공하는 대칭키 암호 프리미티브의 필요성이 높아지고 있다. 이러한 관점에서 본 연구는 생일 상한을 넘는 안전성을 가지는 인증 암호화와 메시지 인증 스킴을 다루며 그중에서도 1) 생일 상한을 넘는 안전성을 제공하는 Double-block Hash-then-Sum (DbHtS) MAC의 정확한 안정성 분석과 2) 거의 완전한 안전성을 제공하는 논스 오용 저항 인증 암호화 모드 Synthetic Counter with Masking (SCM)의 제안과 분석을 다룬다.
DbHtS MAC은 두배 크기의 내부 상태를 사용하는 구조로, 이런 구조를 따르는 PolyMAC, SUM-ECBC, 3kf9, PMAC-Plus, LightMAC-Plus 모두 n-bit 블록암호에 기반했을 때 2^{2n/3}개의 쿼리까지 안전하다는 것이 증명되어 있으며 2^{3n/4}개의 쿼리를 사용하여 공격할 수 있다는 것이 알려져 있다. 우리는 본 연구에서 미러 이론의 발전과 내부 해시 함수의 안전성 요건에 대한 자세한 분석을 통해 DbHtS MAC이 모두 2^{3n/4}개의 쿼리까지 안전하다는 것을 보여 증명과 공격 사이의 차이를 메꾸었다.
SCM은 Peyrin과 Seurin이 제안한 NSIV 구조를 따르며, 논스와 해시된 메시지를 각각 암호화 한뒤 더 하여 태그를 생성하고 태그와 논스를 모두를 이용해 카운터 모드와 유사한 방식으로 메시지를 암호화한다. 그 결과 최초로 논스 재사용이 없을 때 짧은 메시지에 대해서 2^n개의 쿼리까지 안전한 블록 암호 기반 논
스 오용 저항 인증 암호화를 제안할 수 있었으며 SCM의 효율성역시 비슷한 안전성 목적을 가지는 표준인 AES-GCM-SIV보다 약간 뛰어난 모습을 보였다.
