현대 정보화 시대에서 정보보호의 중요성은 아무리 강조해도 지나치지 않습니다. 인터넷 뱅킹, 온라인 주식거래, 각종 전자 상거래 등에서 개인정보를 보호하고, 국가 안보 및 국방 분야에서 중요 정보를 보호하는 것은 선택이 아니라 필수적인 사항입니다. 정보보호 기술의 핵심은 암호 기술이며, 각종 정보보호 프로토콜과 함께 가장 근본적으로 안전성을 담보해주는 것이 바로 암호 알고리즘입니다.

  암호 알고리즘은 크게 대칭키(symmetric-key) 방식과 비대칭키(asymmetric-key) 방식으로 구분됩니다. 비대칭키 방식은 암호화(encryption) 키와 복호화(decryption) 키가 다른 데에서 연유한 것으로 RSA, 타원곡선 암호 등이 여기에 속합니다. 비대칭키 방식에서 암호화 키는 전화번호처럼 공개해야 암호통신이 가능하므로 공개키(public-key) 방식으로 불립니다. 공개키 방식의 안전성은 인수분해 문제, 이산대수 문제 등과 같은 수학적 난제에 기반합니다.

  한편, 공개키 암호 방식은 복잡한 수학적 연산을 사용하는 알고리즘의 특성 때문에 속도가 느리다는 단점을 지닙니다. 이러한 단점을 보완하고 다양한 정보보호 기능을 효율적으로  구현하기 위해서는 대칭키 암호 방식과 공개키 암호 방식을 적절히 혼합하여 사용해야 합니다. 대칭키 방식은 두 통신 당사자만이 공유하는 하나의 키를 비밀로 간직해야 원하는 정보보호 기능을 얻을 수 있기 때문에 비밀키(secret-key) 알고리즘으로 불립니다.

  일반적으로 공개키 암호 알고리즘에 비해서 매우 빠른 속도를 나타내는 비밀키 알고리즘은 블록암호와 스트림 암호로 구분되는데, 이 중에서 블록암호 알고리즘이 가장 널리 사용되고 있습니다. 블록암호는 기밀성(confidentiality)을 얻기 위한 것뿐만 아니라 난수발생기, 해쉬함수, MAC 알고리즘 등 다양한 암호 기술의 원천으로 그 사용빈도가 매우 높기 때문에 표준으로 지정되어 있습니다. 1970년대 중반에 개발되어 미 연방 표준의 위치를 점하고 있는 블록암호 DES(Data Encryption Standard)가 있었으며, 2000년 이후에는 차세대 미국표준 블록암호인 AES(Advanced Encryption Standard)가 새로운 표준으로 자리 잡고 있지만, DES는 3-DES라는 모드로 여전히 많은 정보보호 시스템에 사용되고 있습니다.

  블록암호 알고리즘의 안전성을 평가하는 방법으로는 이론적인 안전성 분석, 통계적 난수성 평가, 부채널(side channel) 공격 관점의 안전성 분석, 컴퓨터 계산량 관점의 안전성 평가 등이 있습니다. 이 중에서 가장 현실적이고 실증적인 것은 컴퓨터 계산량 관점의 안전성 평가 방법으로 키 전수조사(exhaustive search) 공격량 관점의 안전성을 평가하는 것입니다.  DES는 56-비트, 3-DES는 112-비트, AES는 128-비트 길이의 키를 일반적으로 사용하는데, 이러한 키 길이를 결정하는 요소 중 핵심적인 사항이 바로 키 전수조사 관점의 공격량인 것입니다.

  키 전수조사 공격이 무엇인지 알아보기 전에 블록암호 알고리즘이 어떻게 사용되는 것인지 간단히 알아보겠습니다. 그림 1과 같이 두 사람의 사용자가 비밀키를 공유합니다. 한 사람이 어떤 문서를 비밀키를 가지고 암호문으로 만들어서 보내면 다른 사람은 같은 비밀키로 받은 암호문을 복호화해서 문서의 내용을 알게 됩니다. 두 사용자가 아닌 다른 사람이 특정한 방법으로 암호문을 획득하더라고 비밀키를 모르기 때문에 내용을 알 수 없습니다. 여기서 키 전수조사 공격이란 가능한 모든 값을 시도해서 비밀키를 찾는 것입니다. 예를 들면 우리가 흔히 볼 수 있는 3회전 다이얼식 자물쇠를 생각해봅시다. 여기서 전수조사 공격은 다이얼의 모든 조합 1000 ( = 10 X 10 X 10 ) 가지를 다 체크하는 것입니다.

  키 공간이 작다면 위와 같이 누구나 전수조사 공격으로 키를 찾을 수 있습니다. 하지만 과거 미국 표준 암호이자 세계적으로 많이 사용된 DES는 56비트의 키 공간을 가지고 있습니다. 의 키 공간은 1초에 100만개의 키를 체크할 수 있는 컴퓨터가 2285년 동안 쉬지 않고 체크해야 모든 공간을 체크하게 됩니다. 이처럼 한대의 컴퓨터로 작업을 하기에 오래 걸리는 작업을 여러 대의 컴퓨터가 나누어서 한다면 참여한 컴퓨터의 양만큼 작업이 빨리 끝나게 됩니다.