무차별 대입 공격

암호학에서 무차별 대입 공격(영어: brute-force attack)은 특정한 암호를 풀기 위해 가능한 모든 값을 대입하는 것을 의미한다. 대부분의 암호화 방식은 이론적으로 무차별 대입 공격에 대해 안전하지 못하며, 충분한 시간이 존재한다면 암호화된 정보를 해독할 수 있다. 하지만 대부분의 경우 모든 계산을 마치려면 실용적이지 못한 비용이나 시간을 소요하게 되어, 공격을 방지하게 한다. 암호의 '취약점'이라는 의미에는 무차별 대입 공격보다 더 빠른 공격 방법이 존재한다는 것을 의미한다.

전자 프론티어 재단(EFF)에서 제작한 DES 무차별 대입 공격 하드웨어. 약 하루 안에 DES를 해독하는 것이 가능하다.

대칭키 암호의 경우 암호에 사용된 키를 알아내면 암호화된 정보를 복원할 수 있고, 여기에서 사용한 키 길이에 따라 무차별 대입 공격의 최대 소요 시간이 정해진다. 암호화 키가 n비트일 경우 가능한 값은 최대 $2^{n}$가지가 존재한다.

암호를 풀기위한 대입하는값의 경우의수

비밀번호 길이	경우의 수(영문+숫자조합)	경우의 수(특수문자포함)
6	61,474,519	156,238,908
7	491,796,152	1,473,109,704
8	3,381,098,545	11,969,016,345
9	20,286,591,270	85,113,005,120
10	107,518,933,731	536,211,932,256
11	508,271,323,092	3,022,285,436,352
12	2,160,153,123,141	15,363,284,301,456
13	8,308,281,242,850	70,907,466,006,720
14	29,078,984,349,975	298,824,321,028,320
15	93,052,749,919,920	1,155,454,041,309,500
16	273,342,452,889,765	4,116,305,022,165,110

사용되고 있는 대부분의 암호체계는 보통 수학적 복잡성에 기반을 두고 있고 가역적이기 때문에 언젠가는 문제가 풀리게 된다. 가장 강력한 암호체계중 하나로 불리는 RSA의 경우 문제풀이에 천문학적인 시간이 소요되므로 사용되고 있지만, 컴퓨터의 발전에 따른 처리시간의 단축으로 인해 단시간 안에 해독될 가능성이 있다는 의견이 제시되기도 했다. 반면 양자암호의 경우 수학적 복잡성이 아닌 비가역적인 물리학적 자연현상에 기반을 두고 있어서 앞선 다른 암호체계같은 수학적 접근이 불가능하다

2009년 기준으로 128비트 이상의 키는 안전하다고 평가된다. 64비트 이하의 경우 실제 무차별 대입 공격이 성공하였다. 예를 들어, 56비트를 사용하는 DES의 경우 약 하루 안에 전체 키를 대입하는 하드웨어가 1999년에 공개되었다. 64비트 키를 사용하는 RC5의 경우 Distributed.net이라는 분산 컴퓨팅 프로젝트에서 해독한 사례가 있다.

사용자 암호와 같이 암호가 특정 패턴을 이루고 있을 경우에는 대입해야 할 값의 범위를 크게 줄일 수 있다. 이 경우 사전의 단어를 조합하여 대입하는 사전 공격이 사용된다. 그러므로 암호의 패턴을 불규칙적으로 하고 자신의 개인정보와 연계되지 않도록 하는 것이 좋다.

2017년에는 영국과 스코틀랜드 의회가 무차별 대입 공격의 피해를 보았고, 1년 뒤에는 북아일랜드 의회를 대상으로도 비슷한 공격이 일어났지만 성공하지 못했다. 다음 해에는 캐세이 퍼시픽(Cathay Pacific) 항공이 무차별 대입 공격을 받았는데, 영국 데이터 감독 기관은 충분한 예방 수단을 두지 않았다는 이유로 캐세이 퍼시픽에 50만 파운드(약 63만 달러) 벌금을 부과했다. 광고 차단 서비스인 애드 가드(Ad Guard) 역시 무차별 대입 공격을 받은 이후 모든 사용자를 대상으로 강제 비밀번호 재설정을 했다.

소수를 이용한 RSA 암호화 방식

저장된 인증 정보의 비밀번호가 길고 암호화 수준이 높을수록 이 공격이 성공하기 위해 필요한 시간과 컴퓨팅 성능도 높아진다. 따라서 이런 방법으로 공격이 사실상 불가능한 수준까지 무차별 대입 공격의 효과를 낮출 수 있다.

${\frac {2^{2}}{{2^{2}}-1}}*{\frac {3^{2}}{{3^{2}}-1}}*{\frac {5^{2}}{{5^{2}}-1}}*{\frac {7^{2}}{{7^{2}}-1}}*{\frac {11^{2}}{{11^{2}}-1}}...*{\frac {\prime ^{2}}{{\prime ^{2}}-1}}$

$\prod _{s=firstprime}^{\infty prime}{\frac {prime^{2}=s^{2}}{(prime^{2}-1)=(s^{2}-1))}}$

ζ(2)

${\frac {{\pi }^{2}}{6}}$

1.64493406684822...

컴퓨터 과학자들은 이 시스템을 더욱 발전시켜서 소인수 분해 방식(prime number factorisation) 하에서 적용 가능하게 만들었고, 이름을 RSA Cryptography System으로 바꾸었는데, RSA는 세명의 과학자의 성을 딴 것이다. RSA 암호화 시스템은 순식간에 소수를 이용한 암호기술의 대표로 떠오르게 된다.

RSA는 1978년에 매사추세츠 공과 대학(MIT)의 리베스트(R. Rivest), 샤미르(A. Shamir), 아델먼(L. Adelman)이 공동으로 개발했기에 그들 이름의 앞 글자를 따서 붙인 이름이다. RSA 암호는 큰 수의 소인수분해에 많은 시간이 필요하나 소인수분해의 결과를 알면 원래의 수는 곱셈으로 간단히 구해지는 사실에 바탕을 두고 있다.

BB84 프로토콜

BB84 프로토콜

이 문단은 C. H. Bennet과 G. Brassard가 1984년 IEEE International Conference on Computers, Systems, and Signal Processing에서 발표한 《Quantum Cryptography: Public key distribution and coin tossing》논문과 Bouwmeester, Dirk, Artur K. Ekert, Anton Zeilinger가 저서한 Springer社의 《The physics of quantum information :quantum cryptography, quantum teleportation, quantum computation》을 토대로 작성했다.

Basis	0	1

1984년 C. H. Bennet과 G. Brassard가 양자암호에 대한 논문을 발표하면서 같이 제안한 양자암호 통신 프로토콜이다. 송신자(엘리스)와 수신자(밥) 사이에 OTP를 생성하는 프로토콜이며, 표와 같이 0비트의 상태를 나타내는 편광 2가지와 1비트의 상태를 나타내는 편광 2가지를 정의 한 다음 십자필터와 대각필터를 통해 측정하게 된다. 이 프로토콜을 통해 엘리스와 밥은 임의의 난수를 생성할 수 있으며, 중간에 도청자(이브)가 난입하여 정보를 가로채려는 시도를 해도 정확한 정보획득이 어려울뿐더러, 신호가 왜곡되어 이브의 존재가 드러나게 된다. BB84 프로토콜의 전체적인 흐름은 다음과 같다.

1. 엘리스가 임의의 비트를 생성한다
2. 비트를 전송할 편광신호로 변환하기 위해 필터를 하나 선택한다.
3. 필터에 대응되는 편광신호를 생성하고 양자채널로 보낸다
4. 밥은 측정하기 위한 편광필터를 임의로 선택한다.
5. 선택한 편광필터로 값을 측정하여 보관한다.
6. 엘리스와 밥은 퍼블릭 채널을 통해 같은 필터를 사용했는지 여부를 검증한다.
7. 같은 필터를 사용한 비트에 대해서만 보관하고 서로 다른 필터를 사용한 비트는 제거한다.

이와같은 과정을 거치면 표처럼 엘리스와 밥은 0101이라는 같은 값을 공유하게 되며 이것을 비밀키로 활용하게 된다.

엘리스가 생성한 비트	0	1	1	0	1	0	0	1
엘리스가 전송하는 편광필터
엘리스가 전송하는 광자 편광신호
밥이 선택한 측정필터
밥이 측정한 편광 상태
전송 패드와 측정패드가 일치하는지 여부 검증	퍼블릭 채널을 통한 데이터 교환(도청 가능)
최종적으로 생성되는 비밀키	0		1			0		1

같이 보기

• 키 클러스터링