형태 보존 암호화(FPE: Format-Preserving Encryption)
- 암호화 후 평문의 형태와 암호문의 형태가 동일함을 보장하는 암호화 기술을 말함
- 숫자(0~9)로 구성(도메인)되고 길이가 16인 평문을 FPE 기술로 암호화를 하면 <그림 2>과 같이 원본 도메인과 동일하게 숫자로 구성되고 길이가 16인 암호문이 출력됨
- Black과 Rogaway가 도메인 크기별/알고리즘 복잡도별로 제안한 3가지 방법(prefix cipher, cycle-walking cipher, generalized-Feistel cipher)(5)이 여러 FPE 알고리즘의 근간이 됨
- (prefix cipher) FPE를 적용하려는 도메인이 {0, ..., N-1}과 같이 정수로 주어졌을 때, 해당 도메인에 속하는 각각의 정수에 AES, DES와 같은 블록 암호화 알고리즘을 사용하여 의사난수((6) 가중치(pseudo-random weight)를 계산하여 정렬하는 방법 (그림 3 참조)
-
- • 알고리즘이 간단하고 도메인 크기가 작은 경우 사용에 용이함
- • 도메인 크기가 커지면 매핑테이블의 크기 역시 커져 저장 및 사용이 어려워짐
- (cycle-walking cipher) 블록 암호화 알고리즘을 사용하여 원본과 동일한 형태의 결과가 나올 때까지 알고리즘을 계속 수행하는 방법
-
- • prefix-cipher와 달리 전체 매핑테이블을 유지할 필요 없음
- • 언젠가는 알고리즘이 종료되지만 언제 종료될지는 예측할 수 없음
- • 원본 형태의 허용 범위(그림 4의 집합 M)가 작을수록 지나치게 많은 반복으로 실용성이 떨어지고 허용 범위 값의 범위가 블록 암호화 알고리즘의 고정된 블록크기에 영향을 받음
- (generalized-Feistel cipher) 그림 5의 Feistel network(7)를 이용한 방법으로써 각 라운드(round)의 보조키로 블록 암호화 알고리즘의 출력을 사용하여 FPE 수행
-
- • 원본 형태와 다른 출력이 발생하는 경우 cycle-walking과 유사하게 원하는 형태가 얻어질 때까지 Feistel network을 반복 수행
- • prefix cipher와 cycle-walking cipher와 달리, 도메인 크기가 큰 경우에도 비교적 큰 성능 저하 없이 사용 가능하기 때문에 실무에서 많이 사용되며, 이를 기반으로 다양한 알고리즘이 제안됨
- 대부분의 FPE 알고리즘은 위 세 가지 개념을 변형하여 만들어지고 있으며, 블록 암호화 알고리즘을 기반으로 만들어지기 때문에 동일한 안전 정도를 보장함
- 블록 암호화(block cipher) 기술과의 차이는?
- AES, DES 등 기존 블록 암호화 기술은 이진 데이터가 암호화 대상이기 때문에 이를 이용하여 주민등록번호나 신용카드번호를 암호화할 경우 형태가 달라짐
- • 예를 들어, 신용카드번호 1234567898765432를 AES로 암호화 하면 원본과 다른 형태의 암호문이 출력됨
- • 1234567898765432를 숫자로 가정하고 AES로 암호화 할 경우 16자리보다 큰 수가 출력될 가능성 높음
- • 1234567898765432를 ASCII코드로 가정하고 AES로 암호화 할 경우 그 결과 값의 길이가 원본과 달라질 가능성이 높고 아스키 코드(ASCII code)(8) 의 숫자 범위(0x30 ~ 0x39) 사이 값이 출력될 가능성도 희박
- 토큰화(tokenization) 기술과의 차이는?
- 토큰화는 임의로 생성된 값(토큰)을 신용카드번호, 주민등록번호와 같이 민감한 정보 대신 사용하는 기술
- • 실제 민감한 정보는 안전한 곳에 따로 보관되며 토큰과 실제 데이터를 연결하는 매핑 테이블 필요
- 토큰과 실제 데이터와의 연관성이 없기 때문에 공격자가 토큰으로부터 실제 데이터를 유추하는 것 자체가 불가능
- 토큰화 시스템 구축, 데이터 분리 보관, 실시간 토큰 동기화 등 추가 보안 관련 부담과 시스템 개발/유지 비용 필요
- NIST에서 FPE 알고리즘 FF1과 FF3을 컴퓨터 보안 표준으로 제정
- Feistel network 방법을 기반으로 한 FPE 알고리즘인 FFX[Radix](FF1)와 BPS-BC(FF3)가 블록 암호화 알고리즘의 모드(mode)(9) 형태로 제안되고 NIST에서 컴퓨터 보안 표준(NIST Special Publication 800-38G(10) )으로 제정(2016. 3. 29.)
- • 기존에 승인된 모드들은 모두 이진 데이터에 대한 표준들이며 이번에 승인된 모드는 FPE와 관련된 첫 표준
- • (FF1) M. Bellare, P. Rogaway, T. Spies가 제출한 “The FFX Mode of Operation for Format-Preserving Encryption”(FFX[Radix])을 표준으로 승인(특허로 보호 받고 있음)
- • (FF3) E. Brier, T. Peyrin, J. Stern이 제출한 “BSP: a Format-Preserving Encryption Proposal”(BSP) 중 BSP-BC가 표준으로 승인(특허 공개로 누구나 사용 가능)
- FF1와 FF3 모두 파라미터로 주어지는 radix, minlen, maxlen 값에 따라 보안 정도가 달라짐
- • radix는 한 글자를 구성하는 심볼의 개수(예, 10진수의 경우 숫자 0부터 숫자 9까지 심볼 10개를 사용하기 때문에 radix는 10이 됨), minlen은 주어진 평문의 최소 길이, maxlen은 주어진 평문의 최대 길이
- • 즉, 신용카드번호는 radix는 10(신용카드번호 한자리는 숫자 0에서 숫자 9까지 사용하기 때문), minlen은 13, maxlen은 19(카드사에 따라 신용카드번호는 13자리부터 19자리까지 다양함(11))
- • 보통 radix, minlen, maxlen 등이 클수록 보안 정도가 높아짐
- FF1은 가변 길이 트윅(tweak(12))을 제공하여 좀 더 유연한 범위 내에서 데이터 사용이 가능하고, FF3는 FF1에 비해 라운드 회수(FF1은 10라운드, FF3는 8라운드로 구성)가 적어 더 높은 처리량을 보임
