포맷 보존 암호화

암호학에서 형식 보존 암호화(FPE)는 출력(암호 문자)이 입력(일반 텍스트)과 동일한 형식인 방식으로 암호화하는 것을 말한다."형식"의 의미는 다양하다.일반적으로 숫자, 알파벳 또는 영숫자 등 유한한 문자 집합만 사용된다.예를 들면 다음과 같다.

• 암호문이 또 다른 16자리 숫자가 되도록 16자리 신용 카드 번호를 암호화한다.
• 암호문이 또 다른 영어단어가 되도록 영어단어를 암호화한다.
• 암호문이 또 다른 n비트 번호(n비트 블록 암호의 정의)가 되도록 n비트 번호를 암호화한다.

그러한 유한한 도메인의 경우, 그리고 아래 논의의 목적상, 암호는 N 정수 {0, ... , N-1}의 순열과 같으며, 여기서 N은 도메인의 크기다.

동기

제한된 필드 길이 또는 형식

FPE를 사용하는 한 가지 동기는 잘 정의된 데이터 모델과 함께 기존 애플리케이션에 암호화를 통합하는 것과 관련된 문제에서 비롯된다.대표적인 예가 다음과 같은 신용카드 번호일 것이다.1234567812345670(16바이트 길이, 숫자만 해당).

일반적으로 필드 길이 제한이나 데이터 유형의 변경을 수반하기 때문에 데이터 모델을 변경해야 하는 경우 그러한 애플리케이션에 암호화를 추가하는 것은 어려울 수 있다.예를 들어, 일반적인 블록 암호의 출력은 신용카드 번호를 16진수로 바꿀 것이다(예:0x96a45cbcf9c2a9425cde9e274948cb67, 34바이트, 16진수 숫자) 또는 Base64 값(예:lqRcvPnCqUJc3p4nSUjLZw==, 24바이트, 영숫자 및 특수 문자)로 신용카드 번호가 16자리 숫자가 될 것으로 예상하는 기존 응용 프로그램을 중단시킬 수 있다.

간단한 포맷 문제 외에도, AES-128-CBC를 사용하여 이 신용카드 번호는 16진수 값으로 암호화될 수 있다.0xde015724b081ea7003de4593d792fd8b695b39e095c98f3a220ff43522a2df02. 유효하지 않은 문자를 만들고 데이터의 크기를 증가시킴으로써 야기되는 문제 이외에도, 암호화 알고리즘의 CBC 모드를 사용하여 암호화된 데이터도 해독되어 다시 암호화할 때 그 값이 변경된다.이는 암호화 알고리즘을 초기화하는 데 사용되며 암호화된 값의 일부로 포함되는 임의 시드 값이 암호화 작업마다 다르기 때문에 발생한다.이 때문에 CBC 모드로 암호화된 데이터를 고유한 키로 사용하여 데이터베이스에서 행을 식별하는 것은 불가능하다.

FPE는 원본 데이터의 형식과 길이를 보존함으로써 전환 과정을 단순화하려고 시도하며, 레거시 애플리케이션에서 일반 텍스트 값을 암호 텍스트로 드롭인 대체하는 것을 허용한다.

실제 랜덤 순열과 비교

비록 진짜 무작위 순열은 이상적인 FPE 암호지만, 큰 도메인의 경우, 정말로 무작위 순열을 미리 생성하여 기억하는 것은 불가능하다.따라서 FPE의 문제는 단일 값에 대한 계산 시간이 작은(이상적으로 일정하지만 가장 중요한 것은 O(N)보다 작은) 방식으로 비밀 키로부터 유사산담 순열을 생성하는 것이다.

블록 암호와 비교

안n-비트 블록 암호는 기술적으로 {0, ..., 2-1ⁿ} 세트의 FPE이다.이러한 표준 크기 세트 중 하나에 FPE가 필요한 경우(예:n= DES의 경우 64 및n= AES의 경우 128) 적절한 크기의 블록 암호를 사용할 수 있다.

그러나, 일반적인 용법에서는 임의의 긴 메시지를 암호화할 수 있는 작동 방식과 위에서 논의한 초기화 벡터로 블록 암호를 사용한다.이 모드에서 블록 암호는 FPE가 아니다.

보안 정의

암호 문헌(아래 대부분의 참고문헌 참조)에서 "착한" FPE의 척도는 공격자가 FPE와 실제 무작위 순열을 구별할 수 있는지 여부다.다양한 유형의 공격자는 그들이 오르락 또는 알려진 암호문/플레인텍스트 쌍에 대한 액세스 권한을 가지고 있는지에 따라 가정된다.

알고리즘

여기에 열거된 대부분의 접근법에서, 이상적인 무작위 함수를 대신하기 위해 잘 이해되는 블록 암호(AES와 같은)를 원시적인 것으로 사용한다.이는 비밀키를 알고리즘에 통합하는 것이 쉽다는 장점이 있다.다음 논의에서 AES가 언급되는 경우, 다른 좋은 블록 암호도 또한 작동할 것이다.

블랙과 로가웨이의 FPE구축

기반 블록 암호의 보안과 관련된 FPE 구현은 암호학자 존 블랙과 필립 로가웨이에 의해 처음 논문에서 수행되었는데,^[1] 이 논문에서는 이를 위한 세 가지 방법을 설명했다.그들은 이러한 각각의 기법이 그것을 구성하는 데 사용되는 블록 암호만큼 안전하다는 것을 증명했다.즉, FPE 알고리즘을 격파할 수 있는 적수 또한 AES 알고리즘을 격파할 수 있기 때문에 AES 알고리즘을 생성하기 위해 AES 알고리즘을 사용할 경우 결과적으로 FPE 알고리즘이 AES만큼 안전하다는 것이다.따라서 AES가 안전하다면, AES로 구성된 FPE 알고리즘도 안전하다.다음에서 E는 FPE 알고리즘을 구성하는 데 사용되는 AES 암호화 작업을 나타내고 F는 FPE 암호화 작업을 나타낸다.

접두사 암호의 FPE

{0, ..., -1}에 FPE 알고리즘을 생성하는 한 가지 간단한 방법은 각 정수에 유사체중량을 할당하고 중량별로 정렬하는 것이다.가중치는 기존 블록 암호를 각 정수에 적용하여 정의한다.블랙과 로가웨이는 이 기법을 "프리픽스 암호"라고 부르며 그것이 사용된 블록 암호만큼 아마도 훌륭하다는 것을 보여주었다.

따라서 키가 지정된 {0,1,2,3} 도메인에 FPE를 생성하려면 다음과 같이 하십시오.KAES를 적용하다.K각 정수에 대해, 예를 들어,

weight(0) = 0x56c644080098fc5570f2b329323dbf62 weight(1) = 0x08ee98c0d05e3dad3eb3d6236f23e7b7 weight(2) = 0x47d2e1bf72264fa01fb274465e56ba20 weight(3) = 0x077de40941c93774857961a8a772650d

[0,1,2,3]을 무게별로 분류하면 [3,1,2,0]이 나오므로 암호는 다음과 같다.

F(0) = 3 F(1) = 1 F(2) = 2 F(3) = 0

이 방법은 다음의 작은 값에만 유용하다.N. 큰 값의 경우, 룩업 테이블의 크기와 테이블을 초기화하는 데 필요한 암호화 수가 너무 커 실용적이지 못하다.

사이클 보행을 통한 FPE

유사 순열 영역 내에 허용된 값의 M이 설정된 경우P(예를 들어)PAES와 같은 블록 암호일 수 있다), 결과가 허용 값(M 내) 중 하나가 될 때까지 블록 암호를 반복적으로 적용함으로써 FPE 알고리즘을 블록 암호로부터 생성할 수 있다.

CycleWalkingFPE(x) { P(x)가 M의 요소인 경우 P(x)를 반환하고 그렇지 않으면 CycleWalkingFPE(P(x)) }

그 재귀는 확실히 종결될 것이다.(P는 일대일이고 도메인은 유한하기 때문에 P의 반복적 적용은 사이클을 형성하므로 M의 한 지점부터 시작하여 결국 사이클은 M에서 종료된다.)

이는 M의 원소를 연속된 시퀀스 {0,...,N-1}의 정수에 매핑할 필요가 없다는 장점이 있다.M이 훨씬 작을 때 단점이 있다.P각 작업에 너무 많은 반복이 필요할 수 있는 도메인만약PAES와 같은 고정된 크기의 블록 암호로, 이것은 이 방법이 효율적인 M의 크기에 대한 심각한 제한이다.

예를 들어, 응용 프로그램은 다른 100비트 값을 생성하는 방법으로 AES로 100비트 값을 암호화할 수 있다.이 기법으로 AES-128-ECB 암호화는 28개의 최고 비트를 모두 0으로 설정한 값에 도달할 때까지 적용할 수 있으며, 평균 2번의²⁸ 반복이 필요하다.

Feistel 네트워크의 FPE

Feistel 네트워크를 이용하여 FPE 알고리즘을 만드는 것도 가능하다.Feistel 네트워크는 각 라운드의 서브키에 대한 의사 난수 값의 출처를 필요로 하며, AES 알고리즘의 출력을 이러한 의사 난수 값으로 사용할 수 있다.이 작업이 완료되면 충분한 라운드를 사용하면 결과적인 페이젤 구조가 좋다.^[2]

AES와 Feistel 네트워크를 사용하여 FPE 알고리즘을 구현하는 한 가지 방법은 Feistel 네트워크의 왼쪽 또는 오른쪽 절반의 길이와 같도록 필요한 만큼의 AES 출력을 사용하는 것이다.예를 들어 24비트 값이 하위 키로 필요한 경우, 이 값에 대해 AES 출력의 가장 낮은 24비트를 사용할 수 있다.

이것은 입력의 형식을 보존하는 Feistel 네트워크의 출력이 될 수는 없지만, 사이클-보행기술과 같은 방법으로 Feistel 네트워크를 반복하여 포맷이 보존될 수 있도록 하는 것이 가능하다.Feistel 네트워크에 대한 입력의 크기를 조정할 수 있기 때문에, 이 반복이 평균적으로 매우 빨리 끝날 가능성이 매우 높다.예를 들어 신용카드 번호의 경우 10개의 가능한¹⁵ 16자리 신용카드 번호(중복수 체크 디지트를 설명함)가 있으며¹⁵, 10㎛ 2는^49.8 사이클 워킹과 함께 50비트 와이드 Feistel 네트워크를 사용하기 때문에 평균적으로 상당히 빠르게 암호화하는 FPE 알고리즘이 생성될 것이다.

토르프 셔플

Thorp shuffle은 이상화된 카드-shuffle과 같거나, 동등하게 한쪽이 하나의 비트인 Feistel 암호와 같다.균형이 맞지 않는 페이젤 암호에 대한 보안을 입증하는 것은 균형 잡힌 암호보다 쉽다.^[3]

VIL 모드

2의 검정력인 도메인 크기와 블록 크기가 더 작은 기존 블록 암호의 경우, 새로운 암호는 벨라레, 로가웨이에서 설명한 대로 VIL 모드를 사용하여 만들 수 있다.^[4]

성급한 푸딩 암호

셜록 푸딩 암호는 임의의 유한한 작은 도메인을 암호화하기 위해 (기존 블록 암호에 원시적인 것으로 의존하지 않음) 사용자 정의 구조를 사용한다.

AES의 FFSEM/FFX 모드

NIST가 검토를 위해 수락한 AES(사양^[5])의 FFSEM 모드는 위에서 설명한 블랙과 로가웨이의 Feistel 네트워크 구축을 라운드 기능을 위해 AES와 함께 사용하며, 하나의 키가 사용되며 각 라운드에 대해 약간 수정된다.

2010년 2월 현재 FFSEM은 미히르 벨라레, 필립 로가웨이, 테렌스 스파이스가 작성한 FFX 모드로 대체되었다(사양,^[6][7] NIST Block Cipher Modes Development, 2010).

JPEG 2000 암호화를 위한 FPE

JPEG 2000 표준에서 마커 코드(0xFF90 ~ 0xFFF 범위)는 일반 텍스트와 암호 텍스트에 나타나지 않아야 한다.단순한 모듈형-0xFF90 기법은 JPEG 2000 암호화 문제를 해결하기 위해 적용할 수 없다.예를 들어, 암호 텍스트 단어 0x23FF와 0x9832는 유효하지만 조합은 0x23FF9832는 마커 코드 0xFF98을 도입하기 때문에 무효가 된다.마찬가지로, 두 개의 유효한 암호문 블록이 결합되었을 때 잘못된 암호문을 제공할 수 있기 때문에 JPEG2000 암호화 문제를 해결하기 위해 단순한 사이클-보행 기법을 적용할 수 없다.예를 들어 첫 번째 암호문 블록이 바이트 "...30FF"로 끝나고 두 번째 암호문 블록이 바이트 "9832..."로 시작하면, 암호문에는 "0xFF98"이라는 마커 코드가 나타난다.

JPEG 2000의 포맷 보존 암호화를 위한 두 가지 메커니즘은 Hongjun Wu와 Di Ma의 "JPEG2000에 대한 효율적이고 안전한 암호화 체계"^[8]라는 논문에서 제공되었다. JPEG 2000의 포맷 보존 암호화를 수행하기 위해서는 암호화 및 암호 해독에서 바이트 "0xFF"를 제외하는 것이 기술이다.그 후 JPEG 2000 암호화 메커니즘은 스트림 암호로 modulo-n 추가를 수행하고, 또 다른 JPEG 2000 암호화 메커니즘은 블록 암호로 사이클-보행 기술을 수행한다.

기타 FPE 구성

몇몇 FPE 구성품은 암호화할 데이터에 표준 암호인 modulo n의 출력을 추가하는 것에 기초하며, 그 결과를 불편하게 하는 다양한 방법을 사용한다.많은 구성 요소들이 공유하는 modulo-n 추가는 FPE 문제에 대한 즉각적인 분명한 해결책이다(많은 경우에 FPE가 사용됨). 주요 차이점은 사용된 불편화 메커니즘이다.

FIPS 74의 섹션 8, NBS 데이터 암호화 표준의 구현 및 사용에 관한 1981년 지침에서는 ^[9]모듈로-n 추가를 통해 데이터의 형식을 보존한 후 불편화 작업을 수행하는 방식으로 DES 암호화 알고리즘을 사용하는 방법을 설명한다.이 표준은 2005년 5월 19일에 철회되었기 때문에, 이 기술은 공식적인 표준이라는 측면에서 쓸모 없는 것으로 간주되어야 한다.

포맷 보존 암호화를 위한 또 다른 초기 메커니즘은 Peter Gutmann의 "값의 범위가 제한된 암호화 데이터"^[10]로, 결과를 균일하게 만들기 위해 일부 조정과 함께 모든 암호에 modulo-n을 다시 수행하며, 결과적으로 암호화가 기반이 되는 기본 암호화 알고리즘만큼 강력하다.

Michael Brightwell과 Harry Smith의 "데이터타입-보존 암호화를 사용하여 데이터 웨어하우스 보안을 강화함"^[11]은 일반 텍스트의 형식을 보존하는 방식으로 DES 암호화 알고리즘을 사용하는 방법을 설명한다.이 기법은 여기서 언급된 다른 modulo-n 기법처럼 불편화 단계를 적용하지 않는 것으로 보인다.

Mihir Bellare와 Thomas Ristenpart의 "형식 보존 암호화"^[12]는 보안 FPE 알고리즘을 만들기 위해 "거의 균형 잡힌" Feistel 네트워크를 사용하는 것을 설명한다.

Ulf Mattsson의 "암호화를 보존하는 데이터 형식을 이용한 포맷 제어 암호화"는 ^[13]FPE 알고리즘을 만드는 다른 방법을 설명한다.

FPE 알고리즘의 예로는 FNR(Flexible Naor and Reingold)이 있다.^[14]

표준 당국에 의한 FPE 알고리즘의 수락

NIST 특별 간행물 800-38G, "블록 암호 모드 운영 권장 사항:포맷 보존 암호화 방법"^[15]은 FF1과 FF3의 두 가지 방법을 명시한다.각각에 대해 제출된 제안서에 대한 자세한 내용은 특허 및 시험 벡터 정보를 포함하여 NIST 블록 암호 모드 개발 사이트에서 확인할 수 있다.^[16]샘플 값은 FF1과 FF3 모두에 사용할 수 있다.^[17]

• FF1은 FFX[Radix] "Format-reserve Feistel-based Encryption Mode"로, ANSI X9에 따른 표준 프로세스에도 X9.119와 X9.124로 있다.그것은 캘리포니아 대학교 샌디에이고의 미히르 벨라레, 캘리포니아 대학교의 필립 로가웨이, 데이비스, 그리고 전압 보안 주식회사의 테렌스 스파이들에 의해 NIST에 제출되었다.테스트 벡터가 공급되고 그 일부가 특허된다. (DRAFT SP 800-38G Rev1) 암호화되는 데이터의 최소 도메인 크기는 100만(이전 100)이 되어야 한다.

• FF3는 저자들의 이름을 딴 BPS이다.프랑스 인제니코의 에릭 브리어, 토마스 페이린, 자크 스턴에 의해 NIST에 제출되었다.저자들은 NIST에 그들의 알고리즘이 특허권이 없다고 선언했다.^[19]CyberRes Voltage 제품은 BPS 모드에 대한 특허 소유권을 주장하지만,^[20][21]NIST는 2017년 4월 12일 연구원들이 취약성을 발견했기 때문에 FF3가 "일반적인 목적 FPE 방법으로 더 이상 적합하지 않다"고 결론 내렸다.^[22]
• FF3-1(DRAFT SP 800-38G Rev1)은 FF3를 대체하며 암호화되는 데이터의 최소 도메인 크기는 100만(이전 100)이어야 한다.

다른 모드는 NIST 지침 초안에 포함되었으나 최종 발행 전에 삭제되었다.

• FF2는 FFX를 위한 VAES3 체계: "암호화 보존을 위한 FFX 운영 모드"의 부록: 암호키의 수명을 연장하기 위한 하위 키 연산을 포함한 임의 라디ix의 암호 문자열을 위한 파라미터 모음입니다.그것은 VeriFone Systems Inc.의 Joachim Vance에 의해 NIST에 제출되었다.시험 벡터는 FF1과 별도로 공급되지 않으며 그 일부가 특허된다.저자들은 NIST가 적극 검토 중인 수정된 알고리즘을^[23] DFF로 제출하였다.

한국은 FPE 표준인 FEA-1과 FEA-2도 개발했다.

구현

FF1과 FF3의 오픈 소스 구현은 C 언어, Go language, Java, Node.js, Python, C#/로 공개 가능하다.네트와 러스트

참조