형태보존암호

형태보존암호(Format-Preserving Encryption)란 평문과 암호문의 형태를 동일하게 유지한 채 암호화를 수행하는 암호화 알고리즘 및 기술이다.

개요

형태보존암호는 평문과 암호문의 형태를 동일하게 한다. 평문이 갖고 있는 형태를 온전히 유지한 채로 암호화를 수행하는 암호화 알고리즘이자 기술이다. 예를 들면 주민등록번호는 앞의 6자리와 뒤의 7자리 총 13자리 정수로 구성되어 있다. 여기서 보통은 13자리의 평문을 암호화하면 기법에 따라서 정해진 길이의 암호문이 출력된다. 만약 AES가 적용되었다면 128비트로 출력될 것이다. 그러나 형태보존암호에서는 13자리 정수라는 형태가 보존된 상태로 암호문이 출력된다. 따라서 어떤 응용프로그램은 암호문을 통해서 평문의 값을 알아낼 수는 없지만 어떤 종류의 값을 나타내는지는 알 수 있다. 형태보존암호의 형태는 일반적으로 정의역의 크기를 의미하며, 보통 크기가 작은 평문을 암호화할 때 사용된다. 형태보존암호의 주된 장점은 작은 크기의 평문을 암호화할 수 있다는 것이며, 평문과 암호문이 같은 형태이기 때문에 평문과 암호문 각각의 크기 또한 동일하고, 따라서 일반적인 블록암호에서 상대적으로 긴 길이의 암호문을 전부 저장할 필요는 없다는 장점이 있다. 또, 기존의 시스템에 형태보존암호를 적용하고 싶을 때 기업이나 개인이 가지고 있는 기존의 시스템을 수정하거나 교체할 필요가 없기 때문에 시간이나 비용 면에서 부담을 덜 수 있다. 이처럼 유용한 형태보존암호는 대표적으로 prefix cipher, cycle-walking cipher, VFPE, FF1, FF3-1, FEA 등이 있다.

특징

장점

형태보존암호의 주된 장점은 작은 크기의 평문을 암호화할 수 있다는 것이다. 하지만 만약 평문의 크기가 작다면, 출력될 암호문의 크기 또한 작기 때문에 안전성에 큰 문제가 생길 수 있는데, 이를 형태보존암호는 추가 정보인 트윅(Tweak)을 사용해서 안전성을 확보한다. 예를 들자면 16자리 신용카드번호를 암호화한다고 할 때, 신용카드 앞의 6자리와 마지막 4자리는 신용카드 회사의 정보나 변경되지 않아야할 정보가 담겨 있기 때문에 중간의 6자리만을 암호화한다. 따라서 평문은 $10^{6}$가지, 즉 100만 가지 경우의 수가 존재한다. 만약 모든 데이터베이스에 $10^{8}$개의 카드번호가 있다면 그 중에서 약 100개는 중간 6자리가 같은 숫자로 이루어져 있다. 만약 중간 6자리가 동일한 카드 번호를 같은 트윅을 암호화한다면 모두 같은 암호문이 된다. 하지만 가운데 6자리를 제외한 나머지 카드 값을 트윅으로 사용한다면 서로 다른 암호문을 가지게 된다. 형태보존암호는 평문과 암호문이 같은 형태이기 때문에 둘의 크기도 동일하기 때문에, 일반적인 블록암호에서 상대적으로 긴 길이의 암호문을 전부 저장할 필요는 없다. 신용카드의 16자리 10진수 번호 중에서 일부 6자리를 암호화해야한다고 할 때, 만약 128비트 블록 사이즈의 블록 암호 AES를 이용해서 암호화한다면 암호문의 길이도 128비트가 될 것이다. 평문인 6자리 10진수는 $10^{6}\approx 2^{19.93}$이므로 약 20비트 밖에 안되는데, 암호문은 이보다 6배 이상 큰 128비트 길이를 갖는다. 따라서 신용카드를 담당하는 회사에서 모든 카드 번호를 암호화해서 저장한다면, 평문을 저장하는데 비해서 암호문을 저장하는데 필요한 저장 용량은 6배 이상이 된다. 하지만 여기서 형태보존암호를 사용한다면 말이 달라진다. 형태보존암호를 사용하여 6자리 10진수 신용카드 번호를 암호화하면 암호문도 마찬가지로 6자리 10진수가 된다. 따라서 평문 대신에 암호문을 저장하기 위한 추가적인 저장 용량은 필요하지 않게 된다.

형태보존암호은 기존의 시스템에서 이용하고 싶을 때 시간과 비용 면에서 부담을 덜 수 있다. 개인정보와 거래정보 등 각종 정보를 지금까지 한번도 암호화를 하지않고 관리해온 시스템을 갖고 있는 기업이 있다고 가정한다. 암호화가 안되어 있는 그 정보들을 정부의 정책이나 다른 모종의 이유로 암호화를 해야하게 될 경우, 이 기업에서 사용하고 있던 시스템은 평문의 형태에 맞춰서 작동하고 있었기 때문에 암호문의 형태에 맞춰서 시스템이 운용될 수 있도록 주변의 모든 시스템을 교체하거나 수정해야만 한다. 시간과 비용면에서 상당한 부담이 될 과정이기 때문에 기업 입장에서는 당연히 부담스러울 수 밖에 없다. 그러나 여기서 형태보존암호를 적용한다면 기존의 시스템을 크게 바꿀 필요 없이 그대로 사용할 수 있다. 기존의 시스템을 수정하거나 교체할 필요가 없어서 시간과 비용 면에서 부담을 덜 수 있다.

종류

형태보존암호 기법은 prefix cipher, cycle-walking cipher, VFPE, FF1, FF3-1, FEA, Mix-and-cut, Swap-ornot, Sometimes-recurse-shuffle 등이 있다. 이러한 다양한 기법들 중 FFX, VAES3, BPS는 각각 FF1, FF2, FF3라는 명칭으로 미국 국립표준기술 연구소의 표준에 제정되었다. 하지만 FF2는 안전성 문제가 제기되어서 표준에서 삭제되었고, 현재 FF1과 FF3만 표준으로 사용되고 있다.

• FF1, FF3

FF1과 FF3은 둘 다 AES 같은 기존의 블록암호를 파이스텔 구조와 함께 적용해서 암호화한다. 임의의 평문 길이에 모두 적용할 수 있는 파이스텔 구조의 형태보존암호이다. 내부 F 함수로 일반 블록암호를 사용하며, 매 라운드에서 법 연산을 취해서 평문의 길이를 유지한다. 두 기법은 파이스텔 구조의 라운드 수와 입력되는 트윅의 길이, 평문이 입력되는 순서 등에서 차이점이 존재하는데, 예를 들어 FF1은 1평문이 입력되는 그대로 사용하며 10라운드를 사용한다. 반면에 FF3은 평문이 역순으로 입력되어야 하고, 8라운드를 사용한다. FF1, 즉 FFX를 제안한 벨레어(Bellare)는 FF1과 FF3에 대해 새로운 복구 공격을 제안했고 이들에게 취약점이 있다고 말했었다. 메시지 복구 공격은 파이스텔 구조에서 오른쪽 절반 값이 동일한 서로 다른 두 입력 값에 대해서, 두 초기 값의 왼쪽 절반 연산과 출력된 값들의 왼쪽 절반 연산을 비교한다. 이때 라운드 수가 크지 않다면 초기 값과 출력 값의 연산 결과가 같은 확률이 높다는 성질을 기반으로 공격한다. 결론적으로 FF1과 FF3가 고정된 라운드 수를 수행하면 크기가 작은 평문에 대해 메시지 복구 공격에 약할 수도 있다.

• prefix cipher

prefix cipher은 모든 평문에 대해서 임의의 블록암호를 사용하여 암호문을 얻은 다음 오름차순으로 정렬한다. 그리고 다시 복호화한 것을 제일 처음의 평문들의 prefix cipher 암호문으로 대응시킨다. 알고리즘이 간단하고 도메인 크기가 작은 경우에 용이하다는 장점이 있다. 그러나 한번 암호화할 때마다 평문의 크기만큼 암호화를 하고 정렬해야 하는 불편함이 있어 효율적인 방식은 아니다.

• cycle-walking cipher

cycle-walking cipher은 임의의 블록암호에 대해서 원하는 형태의 암호문이 나올 때까지 계속해서 같은 키로 암호화하는 방식을 말한다. prefix-cipher와 달리 전체 매핑 테이블 유지가 필요 없지만, 알고리즘을 수행할 때 종료 시간을 예측할 수 없다. 사용하는 블록 암호에 비해서 원하는 형태의 크기가 작을 때 반복 횟수가 많이 증가할 수도 있어 다소 위험하다.

• VFPE

VFPE는 ISA 카드회사에서 채틱한 형태보존암호로, 카운터 모드를 사용한다. 각 카운터에서 얻은 블록 암호의 암호문에 법 연산을 취하여 원하는 형태의 암호문을 얻는 방식이다. 예를 들어 카드번호인 16자리 10진수의 암호문은 16개의 카운터에서 얻어진 블록 암호의 암호문들에 각각 법 10연산을 취해서 얻을 수 있다.

• FEA: 국가보안기술연구소에서 개발한 국내 형태보존암호로, 파이스텔 구조를 사용한다. 그러나 FF1과 FF3와 달리 내부 F 함수로서 FEA 함수를 사용한다. 그리고 F 함수의 길이를 조정해서 평문의 길이를 유지한다.

표준화

ISO에 등재되는 암호기법들이 표준화되기 위해서는 필요성과 적합성을 모두 적합해야한다. 여러 분야에서 자체적으로 사용되고 있는지 여부와 산업계의 요구 등을 충족해야하며, 보통 최소 3년 정도의 국제적인 공개검증 기간을 진행해야만 한다. 따라서 형태보존암호의 표준화는 쉬운일이 아니다.

형태보존암호의 표준화는 산업계의 요구에서 시작되었다. 산업체의 요청으로 형태보존암호 표준화 필요성이 대두되었다. 2017년 10월에 진행된 제 55차 ISO/IEC JTC1 SC27 국제 표준화 회의에는 한국대표단도 참여했었다. 한국대표단은 회의에서 FEA를 소개하며 산업계의 형태보존암호 표준화 요청에 따라서 표준화의 필요성을 제시했다. 제시된 내용에 따라 형태보존암호의 필요성과 적합성을 검토하기 위해 SP 절차를 시작했으며, SP에는 한국의 송정환 교수와 미국의 릴리 첸이 참가했다. 하지만 이 이후에 형태보존암호에 대한 의견은 한국과 미국을 제외하고는 많지 않은 편이었고, 결국 2018년 4월 중국에서 열리는 제56차 ISO/IEC JTC1 SC27 국제표준화 회의에서 각국의 전문가들에게 구체적인 질문을 남기기 위해 SP를 연장했다. 이후 한국에서는 FEA-2를, 미국에서는 미국 국립표준기술 연구소 표준 형태보존암호인 FF1과 FF3을 표준화 후보 알고리즘으로 제안했다. 그러나 형태보존암호가 작은 정의역을 갖는다는 특성을 기반으로 한 키 복구 공격과 코드북 공격 등 다양한 안전성 검증 절차를 진행한 결과, 프랑스와 러시아는 형태보존암호의 안전성이 우려된다는 의견을 제시했다. 이에 작은 정의역 특성을 이용한 공격들에 대한 논의를 위해서 SP 기간을 또 6개월을 늘려 연장전을 진행했다. 작은 크기의 정의역을 이용한 공격은 상당히 효과적이라 미국의 FF3은 코드북 공격으로 완전히 깨졌다. FF1과 FEA-2도 안전성 분석에서 뛰어난 결과를 보여주지 못했고, 형태보존암호는 작은 정의역을 갖는다는 특성을 이용한 공격에 대응하기 위해 정의역의 최소 크기에 대한 제한이 필요하다는 의견이 나왔다. 의견에 따라, 작은 크기의 정의역을 이용한 공격에서 FEA-2는 정의역의 크기가 218 이상일 때 안전하다는 결론이 나왔는데, 이는 18비트 길이로 약 5자리 10진수가 되는 상당히 짧은 길이에 해당한다. 반면에 미국의 FF1, FF3은 FEA-2와 동일한 조건에서 32비트 길이의 정의역 크기가 필요하다는 결과가 나왔다. 특히 FF3은 코드북 공격으로 완전히 깨진 상황에서 알고리즘을 수정해야 했고, 결국 FF3을 FF3-1로 수정해서 2019년 12월 28일에 미국 국립표준기술 연구소 800-38G revision 1 이라는 문서를 발행했다. 2019년 4월에 이스라엘에서 열린 제 58차 ISO/IEC JTC1 SC27 국제표준화 회의에서 러시아와 프랑스는 함께 형태보존암호의 안전성 분석에 대해서 아직 충분히 논의되지 않았기 때문에 표준화를 시작하기에는 시기가 이르다고 의견을 제시했다. 형태보존암호에 대한 공격이 비교적 적었으며, 발표된 논문들이 모두 2016년에서 2018년 사이에 몰려있기 때문이다. 따라서 SP 기간이 6개월 더 연장되었다.

참고자료

• 정수용, 홍도원, 서창호, 〈[메시지 복구 공격에 안전한 형태보존암호]〉, 《한국정보과학회》, 2017-08

같이 보기

• 암호
• 알고리즘

이 형태보존암호 문서는 암호 알고리즘에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.

블록체인 : 블록체인 기술, 합의 알고리즘, 암호 알고리즘 □■⊕, 알고리즘, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스 암호기술 개인키 • 경량암호 • 다자간 계산(MPC) • 다중서명(멀티시그) • 동형암호 • 디지털서명 • 링서명 • 배타적 논리합(XOR) • 복호화 • 블랙박스 암호 • 서명 • 소수 • 소인수분해 • 슈노르서명 • 스케인 • 스키테일 • 스테가노그래피 • 안전한 다자간 계산(SMPC) • 암호 • 암호경제학 • 암호문 • 암호키 • 암호학 • 암호화 • 이산로그 • 전자봉투 • 전자서명 • 전치암호 • 종단간 암호화 • 치환암호(대체암호) • 키 • 패딩 • 패스워드 • 평문 • 합성수 • 해독 • 해시 • 형태보존암호 • 혼돈 • 화이트박스 암호 • 확산 논리연산 논리곱(AND) • 논리연산 • 논리합(OR) • 배타적 논리합(XOR) • 부울곱 • 부울대수 • 부울합 • 부정논리곱(NAND) • 부정논리합(NOR) • 부정연산(NOT) SHA SHA • SHA0 • SHA1 • SHA2 • SHA224 • SHA256 • SHA384 • SHA512 • SHA512/224 • SHA512/256 • SHA3 • SHA3-224 • SHA3-256 • SHA3-384 • SHA3-512 MD MD • MD2 • MD4 • MD5 • RIPEMD • RIPEMD-128 • RIPEMD-160 • RIPEMD-256 • RIPEMD-320 기타 해시 CRC-16 • CRC-32 • CRC-64 • Keccak-256 • Keccak-384 • Keccak-512 • Shake-128 • Shake-256 • 베이스32 • 베이스32 파일 • 베이스58 • 베이스64 • 베이스64 파일 • 순환중복검사 대칭키 AES • ARIA(아리아) • DES • HIGHT(하이트) • LEA • SEED(시드) • 대칭키 • 대칭키 암호 알고리즘 • 디피-헬만 • 디피-헬만 키교환 • 레인달 • 블로피시 • 블록암호 • 스트림 암호 • 에스박스(S-Box) • 트리플 DES 비대칭키 PKI • RSA • 공개키 • 공개키 암호 알고리즘 • 비대칭키 • 엘가말 • 타원곡선 • 타원곡선 디지털서명 알고리즘 • 타원곡선암호 영지식증명 영지식 상호 증명(ZKIP) • 영지식 스나크 • 영지식 스타크 • 영지식증명 양자암호 BB84 프로토콜 • E91 프로토콜 • B92 프로토콜 • 비밀키 오류율 • 안전성 증명 • 양자난수생성기 • 양자내성암호 • 양자암호 • 양자얽힘 • 양자역학 • 양자중첩 • 양자컴퓨터 • 양자키 • 양자키분배 • 양자통신 • 연속 변수 프로토콜 암호해독 기지평문공격(KPA) • 선택암호문공격(CCA) • 선택평문공격(CPA) • 암호공격 • 암호문 단독공격(COA) • 암호해독 암호학 인물 라이언 플레이페어 • 레너드 애들먼 • 로널드 리베스트 • 마틴 헬만 • 블레즈 드 비즈네르 • 아디 샤미르 • 앨런 튜링 • 웨슬리 피터슨 • 찰스 휘트스톤 • 휫필드 디피 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반