생활노하우


카테고리가 애매하여 생활노하우 게시판에 올립니다.



현재 가장 대중적으로 쓰이고 안정성이 입증된 알고리즘은 블럭 암호화 알고리즘이 대부분입니다.

블럭 암호화 알고리즘이란, 데이터 스트림을 일정한 크기(블럭 사이즈)로 잘라서 암호화하는 방식입니다.


대표적으로 DES, Triple-DES, AES를 주로 사용하고 있습니다.

키 사이즈는 DES: 56-bit, Triple-Des: 112-bit or 168-bit, AES: 128-bit or 192-bit or 256-bit 로 구성되어 있습니다.


암호에서 가능한한 모든 경우의 수를 대입해서 키를 맞추는 공격을 brute-force 공격이라 합니다.

사실 가장 무식한데, 가장 확실한 방법이기도 합니다. 다만.. 죽을 때 까지 게속 대입만 하고 있을 가능성이 높습니다.



brute-force의 경우, DES인 56-bit은 좀 위험합니다. 2^56회 대입하면 죽으나 사나 키는 구할 수 있습니다.

제 컴퓨터로 돌려봤더니 4일이면 암호가 깨집니다. 즉 개인용 컴퓨터로도 56-bit은 보통 쉽게 뚫을 수 있습니다.

(서울시교통카드 1세대가 마이페어 + DES암호화라서 뚫렸었죠.)


그래서 대칭키 알고리즘의 경우, 보통 128-bit 이상의 키를 필수로 생각합니다.

예외가 Triple-DES(3DES)가 있는데, 이 경우 키를 두 개만 사용해서 112-bit을 쓰는 경우도 어렵지 않게 찾아볼 수 있습니다.


사실 Triple-DES를 112-bit의 키로 사용하는건 권장할만한 방법은 아니나 (통계적 공격이 가능함)

Triple-DES 112-bit라 하더라도 brute-force로 깨기는 호락호락하지 않습니다.

어찌됐든지 간에, Triple-DES 112-bit은 안 쓰는 것이 좋습니다.


대신에 AES를 지원하는 시스템이라면 AES 128-bit을 사용하는 것이 가장 좋고

Triple-DES 168-bit를 사용하는 것도 좋습니다.






말이 약간 샜는데, 블럭 암호화 알고리즘에서는 128-bit 이상의 키를 써야 안전하다고 판단합니다.


이 글에서는 "왜 대칭키 알고리즘에서 128-bit이상의 키 사이즈를 요구하는지"에 대해 알아보겠습니다.







1. 블럭 암호화 알고리즘의 목표


시저 암호화, 2차 세계대전의 에니그마 등 역사적으로 많은 암호화 알고리즘이 존재했었습니다.

그런데 이 암호화 기법은 모두 한 가지의 문제점을 가지고 있습니다.

바로 Plaintext의 통계적 유의미함을 완전히 숨기지 못한다는 것입니다.


영어는 알파벳 E가 가장 많이 나오고, 그 다음엔 뭐가, 그 다음엔 뭐가, x는 거의 안나오고..

이런 식의 통계적 유의미함을 고전 암호는 완벽히 감출 수 없었습니다.



블럭 암호화 알고리즘은 Output, 즉 Ciphertext의 비트스트림이 통계적 유의미함을 가지지 못하는 것을 목표로 합니다.

즉 Ciphertext는 Random Number로 출력되도록 하는 것을 목표로 합니다.




2. Random Number


암호화 알고리즘의 목표가 Ciphertext가 랜덤넘버로 구성된 것을 말한다고 했는데,

정작 랜덤 넘버는 만들기가 어렵습니다. 수학적으로 랜덤넘버 생성 알고리즘을 만들면, 추측이 가능합니다.

추측이 가능하다면 암호화 알고리즘을 공격할 수 있겠죠.


그래서 Cpu클럭을 랜덤넘버의 초기화 값으로 사용하기도 하고

때로는 전자기장의 세기를 이용해 랜덤넘버를 만들어 내기도 합니다. Current의 세기로도 만들어내기도 하고요.



하지만 Random Number는 못 만들어도, Random Number를 생성하는 장치를 정의할 수는 있습니다.

그런게 있다고 가정하는 것이죠. 이 '임의의 랜덤 넘버 생성기'를 Pseudo Random Function(PRF)라 이름 짓겠습니다.


요 PRF를 가정하면, 이제 블럭 암호화 알고리즘이 얼마나 안전한지 판단할 수 있는 방법도 정의할 수 있게 됩니다.




3. 블럭 알고리즘의 안정성 판별


튜링 테스트를 통해 블럭 알고리즘을 판별합니다.


튜링 테스트에는 Human과 Program이 있습니다.

이 모형을 현재 블럭 알고리즘에 투영시키면,

Human = Ideal World, 즉 PRF가 됩니다. (편의상 Rand로 표기)

Program = Real World, 즉 임의의 블럭 암호화 알고리즘이 됩니다. (편의상 Real로 표기)


그리고 이 튜링테스트를 진행할 사람을 T(Tester)로 정의합니다.

Tester는 어떤 방식으로 Rand와 Real을 판별할지에 대한 Rule을 가지고 있습니다.



이 때 Real, 즉 블럭 암호화 알고리즘이 얼마나 안전한지는

PRF-Advantage로 나타냅니다.


PRF-Advantage = Probability[Real(T, Rule) == TRUE] - Probability[Rand(T, Rule) == TRUE]


Probability[Real(T, Rule) == TRUE]: Tester의 Rule로 TRUE를 이끌어 낼 확률, 단 Test의 대상은 Real임(블럭 암호화 알고리즘)

Probability[Rand(T, Rule) == TRUE]: Tester의 Rule로 TRUE를 이끌어 낼 확률, 단 Test의 대상은 Rand임(PRF)


확률이기 때문에 PRF-Advantage는 Real을 맞출 확률 - Rand를 맞출 확률이 됩니다.


PRF-Advantage가 1에 가까우면 암호가 뚫리기 매우 쉬움을(PRF와 거리가 완전 멀기 때문에)

0에 가까우면 암호가 PRF와 비슷해서 뚫기 어려움을 말합니다.

(-1에 가까우면 결과값을 inverse하면 암호를 뚫을 수 있음을 말합니다.)




4. Rule 정의


Real(블럭 암호화 알고리즘)과 Rand(PRF)는 하나의 차이가 있습니다.

Real은 그 결과값이 distincti합니다. 1 to 1 대응이고 permutation입니다.

복호화 하기 위해서는 역함수가 존재해야 하기 때문입니다.


하지만 Rand(PRF)는 many to one이 될 수 있으며, permutation이 아닙니다.



따라서 Tester는 Rule을 다음과 같이 정의합니다.


RULE: Rand 또는 Real의 Domain(즉 key size만큼의 비트를 말함)의 모든 값을 입력했을 때, 그 결과값이 모두 distinct라면 TRUE.


그렇다면 각각의 확률은 다음과 같습니다.


Probability[Real(T, Rule) == TRUE] = 1

왜냐하면, 블럭 암호화 알고리즘은 distinct하기 때문입니다.



Probability[Rand(T, Rule) == TRUE] = 1 - {q(q-1)/2N} 

단 q는 쿼리의 수, N은 도메인 사이즈


거의 1에 가깝긴 한데, 뒤에 뭐 더러운게 붙었습니다.




5. Birthday Attack 


생일이 같은 사람이 존재할 확률은 얼마나 될까요?

얼핏 생각하면 굉장히 드물 것 같지만, 실제로는 사람 수가 23명을 넘어가면 확률이 절반이 넘습니다.

사람 수가 50명을 넘어가면 97%의 확률로 생일이 같은 사람이 있습니다.


특정한 생일을 가진 두 사람이 존재할 확률은 매우 낮지만,

어떤 날짜든 생일이 같기만 한 사람이 존재할 확률은 생각보다 높습니다.


이를 Birthday Paradox라고 합니다.




6. {q(q-1)/2N}의 뜻


Birthday Paradox를 수학적으로 유도하면,

Upperbound는 q(q-1) / 2N으로 유도됩니다.

유도과정은 귀차니즘상 생략합니다. (고등학교 수준의 수학으로 유도 가능)


이때 q는 사람의 수를 의미하며 N은 생일의 범주, 즉 365일을 의미합니다.


이걸 블럭 암호화 알고리즘에 투영하면

q는 질의 수, 즉 암호 대입 공격의 수가 되고

N은 키 사이즈가 됩니다. 128-bit라면 N = 2^128입니다.



Probability[Rand(T, Rule) == TRUE] = 1 - {q(q-1)/2N} 의 뒤에 붙은 {q(q-1)/2N}는

PRF가 1 to 1이 아니기 때문에 우연히 도메인 내에서 겹칠 수 있는 확률을 말합니다.


PRF가 웬만해선 1 to 1이 나오기 때문에 Probability는 1에 수렴하지만,

Birthday Paradox처럼 도메인 내에서 겹치는게 발생할 수 있기 때문에 1 - {q(q-1)/2N}이 됩니다.



7. Birthday Attack on Block Ciphers


그렇다면 블럭 암호화 알고리즘의 PRF-Advantage는?



PRF-Advantage = Probability[Real(T, Rule)] - Probability[Rand(T, Rule)]

                          = 1 - 1 + {q(q-1)/2N}

                          = q(q-1)/2N


즉 q(q-1)/2N이 됩니다.


N은 키 사이즈가 128-bit라면 2^128이라는 어마어마하게 큰 수가 되므로,

일반적인 상황에서는 PRF-Advantage가 거의 0으로 수렴하기 때문에

현존하는 블럭 암호화 알고리즘은 매우 안전한 것 처럼 보입니다.




하지만 분자의 q(q-1)을 보면, q^2이 위치하고 있습니다.

q는 암호를 깨기 위해 대입하는 횟수를 말하는데, 무려 제곱이나 들어가 있습니다.


PRF-Advantage가 1에 가까워지면 암호가 깨지는데, q를 얼마로 잡으면 PRF-Advantage가 깨질까요?


N = 키 사이즈이므로, 키 사이즈를 k-bit로 보면 N = 2^k이 됩니다.


그러면 q = 2^(k/2)가 됩니다.



따라서 Birthday Attack으로 암호를 깨려면 "Key Size의 절반(128-bit라면 2^64번)만 Try하면 깰 수 있음"이 됩니다.

앞에서 DES는 56-bit, Triple-DES는 112-bit or 168-bit, AES는 128-bit라고 말씀드렸는데요,


곧이곧대로 Brute-force공격을 하면 56-bit의 키를 깨는 데도 시간이 조금 걸리지만

Birthday Attack을 이용하면 실제로는 2^28번만 시도하면 깨 집니다.



따라서 블럭 암호화 알고리즘은 키 사이즈의 절반이 Computationally Infeasible이어야 합니다.


DES는 사실 2^28번 Try하면 뚫리고

Triple-DES는 2^56번 또는 2^86번만(?) Try하면 뚫립니다.

AES 128-bit은 2^64번 Try하면 뚫리고요.


결국 살아남는(?) 것은 Triple-DES 168-bit와 AES 128-bit, 192-bit, 256-bit밖에 없습니다.

그마저도 각 키의 제곱근만큼만 유효하고요.

어쩌면 몇년 뒤에는 AES 128-bit가 날아갈지도 모릅니다.






이러한 이유로 인해, 블럭 암호화 알고리즘을 사용할 때는

반드시 128-bit 이상의 키 사이즈를 사용해야 합니다.


Triple-DES 112-bit는 아직 많이 사용되지만, 가급적 안 쓰는게 좋고

AES 128-bit이나 Triple-Des 168-bit 사용을 생활화(?) 합시다. (생활노하우)

번호 제목 작성자 작성일 조회
79 [RC강좌]멀티콥터 제작하기 강좌 [7] yohan666 03.11 8178
78 쉽게 하는 차량 관리법 [8] 산신령 02.10 8377
77 싸고 쉽게 정전기 제거기 만들기 [1] file matsal 01.01 8408
76 안마태자판 2달 적응기 [1] 영진 10.07 8415
75 마이크로유심 구하기... [12] 하뷔 02.07 8641
74 살림하는 남자 전설의 주부용사의 소세지 야체볶음 [16] 전설의주부용사 10.30 8785
73 PC 등에 쓰이는 점퍼 케이블 직접 만들기 file matsal 06.30 8858
72 꽤 된 정보지만... 해외결제 가능 체크카드 [4] yohan666 02.16 8893
71 여름에 마시기 좋은 냉침 원두커피 만들기 [9] iris 06.01 8906
70 [휴대폰] KT 아이 요금제, 바꾸어 주기 - 아이러브 요금제 - 아이서치 포함 [5] 맑은하늘 05.03 9092
69 삼성페이로 결제한 물건 환불하기 powermax 07.19 9172
» 블럭 암호화 알고리즘 키 사이즈를 128-bit이상 사용해야 하는 이유 [4] file 에스비 10.14 9174
67 Windows10에서 Edge가 아무것도 안하고 뻗나요 ? [업데이트] [9] 나도조국 09.04 9238
66 4100만 화소의 스마트폰 루미아 1020의 화질에 대해서 - 화소만 크면 좋은 건가? [13] FFK953 07.17 9273
65 중고차 구매 or 차량 유지 잘하는 요령. [10] 피델리티 08.14 9391
64 KPUG 에서 그림 올리는 법 file matsal 08.12 9479
63 날로 먹는 운전연수 셀프 가이드(Prototype) [13] iris 08.12 9495
62 윈10에서 암호 까먹었을때 [1] 나도조국 05.18 9675
61 가계부와 예산 [2] calm 01.04 9836
60 코인전지 호환표 [3] file 바보준용군 09.30 9838

오늘:
1,813
어제:
851
전체:
15,152,038