형태보존암호

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

참고자료

• 정수용, 홍도원, 서창호, 〈[메시지 복구 공격에 안전한 형태보존암호]〉, 《한국정보과학회》, 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) • 암호해독 암호학 인물 라이언 플레이페어 • 레너드 애들먼 • 로널드 리베스트 • 마틴 헬만 • 블레즈 드 비즈네르 • 아디 샤미르 • 앨런 튜링 • 웨슬리 피터슨 • 찰스 휘트스톤 • 휫필드 디피 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반