2022. 3. 23. 19:23ㆍMajor`/정보보호개론
대칭키 암호
- 암호화 & 복호화할 때 사용하는 key가 동일한 암호 시스템
>> Stream Cipher & Block Cipher
Stream Cipher
안전성을 덜 보장하면서 사용하기 쉽도록 상대적으로 작은 키를 사용한다는 점을 제외하고는 One Time Pad와 거의 유사한 방식으로 동작한다
- One-Time Pad와 다르게, key의 size가 상대적으로 작고 작은 key를 stream형태로 생성해서 사용한다
- "Confusion"의 원칙만 적용이 되는 암호 기법
Stream Cipher는 일단 초기에 "길이가 n인 키 K"를 보유하고 있다
K는 input이 들어올 때마다 각 input size에 맞는 key stream으로 늘어나게 된다
생성된 key stream과 input은 XOR 연산을 통해서 Ciphertext를 만들어낸다
1. 일단 처음에 Cipher Key가 주어지고 "Key Generator"를 초기화
2. input이 계속 들어옴에 따라 Cipher Key를 "Key Generator"를 통해서 일종의 key stream을 만든다
3. key stream으로 input을 암호화해서 cipher text를 생성해준다
1) A5/1
- H/W 기반에서 작동하는 Stream Cipher
- 주로 GSM 휴대폰에서 사용되고 있다
- (X, Y, Z) 3개의 LFSR(Linear Feedback Shift Register)를 사용한다
- X : 19bits >> (x0, x1, ...., x18)
- Y : 22bits >> (y0, y1 ...., y21)
- Z : 23bits >> (z0, z1 ...., z22)
>> X + Y + Z = 64bit이므로, A5/1의 key size는 64bit이다
※ 암호화 과정
1. Key를 X, Y, Z에 각각 채워준다
2. m = maj(x?, y?, z?)를 통해서 m값 설정 (다수결 기능 사용)
- 예를 들어서 maj(x8, y10, z10)이면 (x8, y10, z10)에서 1이 더 많으면 m = 1 & 0이 더 많으면 m = 0
3. (x?, y?, z?)가 m이랑 일치하면 다음 작업을 수행
- x?가 m이랑 일치하면 x단계 수행
- y?가 m이랑 일치하면 y단계 수행
- z?가 m이랑 일치하면 z단계 수행
- t값이 정해지면 각 (X, Y, Z) 레지스터는 각 bit들을 우측 시프트해주고, 우측 시프트해주면 0번째 bit가 비게되는데 0번째 bit에 t값을 넣어주면 된다
4. 최종적 key stream은 (X, Y, Z)의 마지막 비트의 XOR 연산을 통해서 구해진다
>> H/W기반 알고리즘이므로, H/W의 속도에 비례해서 key stream이 생성되고, 1 clock당 하나씩 생성된다
2) RC4
- S/W 기반에서 작동하는 Stream Cipher
- A5/1가 "Key Stream" 1 bit를 생성하는 것에 반해, RC4는 각 단계에서 "Key Stream" 1 byte를 생성한다
- Lookup Table을 항상 보유하고, Lookup Table은 256byte의 Permutation이 들어있다 (0 ~ 255)
- 각 단계에서 key stream이 1byte씩 생성되는데 매번 단계마다 Lookup Table은 update된다
※ 암호화 과정
1. key를 사용해서 Lookup Table 초기화
for i = 0 to 255
S[i] = i
K[i] = key[i mod N]
next i
j = 0
for i = 0 to 255
j = (j + S[i] + K[i]) mod 256
swap(S[i], S[j])
next j
i = j = 0
2. RC4 알고리즘에 따라서 key stream byte를 생성
i = (i + 1) mod 256
j = (j + S[i]) mod 256
swap(S[i], S[j]) // Self-Modifying : Lookup Table update
t = (S[i] + S[j]) mod 256
keyStreamByte = S[t]
>> RC4 알고리즘의 취약점은 "첫 256 key stream byte 버리기"를 통해서 보완이 가능하다
Block Cipher
Plaintext를 고정된 크기의 block으로 나누고 block단위별로 암호화를 수행하는 방식이다
- plaintext는 길이가 가변적이고, 그에 따라서 한번에 암호화를 하지 못하기 때문에 "고정 크기의 여러 block"으로 나누어서 각각의 block을 여러 round(Round Function)에 걸쳐서 최종적으로 암호화한다
Feistel Cipher
- 암호 체계가 아니라 암호 설계의 원리이다 (Algorithm X / Style O)
- Substitution + Permutation(Transposition)
1. Plaintext를 반으로 쪼갠다
"Plaintext = (L0, R0)"
2. 각 round에 걸쳐서 암호화를 수행한다
- 여기서 round끼리 서로 연관이 있어서 round(i)의 결과를 round(i + 1)의 input으로 넣어준다
- 각 round마다 "round function" & "subkey"를 사용해서 암호화한다
- 각 round에서 오른쪽의 bit들은 그대로 왼쪽 pipe?로 흘러 들어간다
- 왼쪽 bit들은 각 round의 round_Function의 연산을 통해서 오른쪽 pipe로 들어가는데 round_Function은 각 round의 subkey와 오른쪽 bit들을 XOR 연산을 통해서 연산된다
1) DES : Data Encryption Standard
- IBM의 "Lucifer Cipher"를 기반으로 하는 1970년대 후반에 개발된 암호 표준
- 미국의 NSA(우리나라 국정원)에서 비밀리에 참여한 프로젝트이다
- 비밀리로 참여를 해서 외부에서는 프로젝트 과정에 대한 모든것이 비밀로 지켜졌다
- 이로 인해서 외부에서는 NSA가 맘만 먹으면 백도어를 통해서 암호를 풀 수 있다고 의심을 했다
- 하지만 결론적으로 이런 백도어 의심은 사실이 아니라고 밝혀졌다
※ DES 특징
구조 : Feistel Ciipher
Block : 64bits
Key : 56bits
sub key : 48bit (각 round)
Round : 16 round
※ DES - Round Function
1. "E Table"을 통해서 32bits(64/2 << Feistel Cipher)를 48bits로 확장시킨다
2. 확장된 48bits와 subkey간에 XOR연산을 수행
3. 2)의 결과를 "S Box"를 통해서 48bit → 32bit로 변환
→ 48bits를 8개로 나누기 : 각 part당 6bit
→ 6개의 bit중 (1, 6)을 이용해서 row값을 결정하고, (2, 3, 4, 5)를 통해서 column값을 결정한다
- ex) bit = 110010
- row = 10 = 2
- column = 1001 = 9
- >> (2, 9)
→ "S Box Table"에서 (row, column)의 값을 6bit에 대한 암호화된 새로운 4bit로 결정
4) "S Box"를 통해서 변환된 32bit를 "P Box"를 통해서 각 bit들을 Transposition해서 최종적인 output을 산출한다
>> key의 길이가 56bit이므로 Exhaustive Key Search를 통해서 파악 가능한 문제점이 있다
1-1) Triple DES
단순 DES에 비해 2배의 연산이 필요해서 효율성이 떨어지긴 하지만 112bit의 Key를 사용함에 있어서 보안상의 장점이 존재한다
하지만 DES & 3-DES는 거의 동일한 수준으로 공격이 가능하다
K1, K2를 모두 K1 or 모두 K2로 사용한다면 3-DES를 사용하는 의미가 없다
이러한 문제를 위해서 AES를 발명하였다
2) AES : Advances Encryption Standard
- DES의 한계를 극복하기 위해 나온 알고리즘
- DES에서의 suspected를 없애기 위해서 NSA에서 공개적으로 참여한 프로젝트이다
- "Rijndael Algorithm"이 최종적으로 선택되었다
>> Like DES : AES는 Block Cipher이다
>> Unlike DES : AES는 Feistel Cipher가 아니다
- 이 말은 "AES를 복호화하기 위해서는 AES 암호화 과정을 거꾸로 수행할 수 있어야 한다"라는 말과 동일하다
※ AES 특징
Block : 128bit / 192bit / 256bit
key : 128bit / 192bit / 256bit중 하나
round : 10 ~ 14 (key의 길이에 따라 가변적이다)
S-P Network에 기반한다 (Substitution - Permutation)
※ AES - Round Function
1. AES SubBytes
- "S Box"와 비슷한 원리로 각 byte들을 치환해준다
- AES의 block은 128bit(16 byte)이므로 Lookup Table을 16 X 16로 구현해준다
- 각 byte의 16진수를 4bit로 쪼개서 (row, column)의 값을 Lookup Table에서 찾아서 치환해준다
>> Confusion을 강화시켜준다
2. AES ShiftRows
- 각 row들을 좌측으로 shift해준다
3. AES MixColumns
- 각 column들을 별도의 Matrix를 이용해서 곱셈 연산을 수행해준다
>> 2, 3을 통해서 Diffusion을 강화시켜준다
4. AES subkey_XOR
- 1, 2, 3을 거쳐서 변환된 byte들을 subkey와 XOR연산을 통해서 다음 round로 input될 결과를 생성해준다
>> 1 ~ 9 round까지는 (1) ~ (4)의 과정을 반복하지만, 마지막 10 round는 (4) 과정을 생략하고 (1) ~ (3)의 과정까지 반복하고 최종적인 ciphertext를 만들어준다
※ AES - Key Schedule
1) key matrix에서 마지막 column을 꺼내서 rotate해준다
2) "S BOX"를 통해서 column의 값들을 치환해준다
3) key matrix의 사용하지 않은 첫번째 column과 2)의 결과와 Rcon의 사용하지 않은 첫번째 column을 서로 XOR연산 해준다
4) 3)을 통해서 생성된 column을 round key에다가 insert해준다
>> 이 과정들을 동일하게 반복해서 하나의 round key matrix를 생성해준다
Block Cipher Mode
Block Cipher Mode는 Block Cipher에서 Block들을 어떻게 암호화할지, 어떤 모드로 암호화 할지 결정해주는 것이다
→ 각 블록들이 독립적으로 암호화 : ECB
→ 각 블록들이 연관성 있게 암호화 : CBC
1) ECB : Electronic CodeBook Mode
- 각 Block들이 독립적으로 암호화되는 모드이다
| P -> P1, P2, P3, ...., Pn | |
| C1= E(P1, K) | P1 = D(C1, K) |
| C2 = E(P2, K) | P2 = D(C2, K) |
| .... | .... |
| CN = E(PN, K) | PN= D(CN, K) |
- key K를 기반으로 "codebook"을 생성한다
>> 따라서 다른 block이지만, 동일한 input에 대해서 동일한 output이 나온다
※ ECB Cut and Paste Attack
다음과 같은 plaintext가 있다고 가정하자
"Alice digs Bob. Trudy digs Tom."
8-bits의 block들로 plaintext를 나눠보자
- P1 = "Alice di"
- P2 = "gs Bob. "
- P3 = "Trudy di"
- P4 = "gs Tom. "
여기서 중간에 Attacker가 P1~P4의 암호화된 블럭 C1 ~ C4의 전달 순서를 바꾼다고 가정해보자.
(C1, C2, C3, C4) -> (C1, C4, C3, C2)
그러면 ciphertext를 받는 receiver입장에서는 원래 순서를 모르니까 "이대로 암호화해서 주었구나"라고 생각을 하고 ciphertext를 받아서 복호화를 할 것이다
"Alice digs Tom. Trudy digs Bob."
이러면 처음 plaintext와 완전히 다른 문장이 복호화됨에 따라 나왔다
>> 이러한 공격방법이 ECB mode의 문제점이다
※ image encryption : ECB Mode
ECB Mode는 다른 block이여도 동일한 input에 대해서 동일한 output이 발생한다.
위의 왼쪽 사진을 보면 흰색 바탕을 전부 block으로 나누면 각 흰색 block은 다른 block임에도 불구하고 동일한 input이기 때문에 암호화를 해도 동일한 output으로 암호화가 된다
>> 따라서 암호화를 해도 원래 사진의 스케치가 남아있는 것을 볼 수 있다
2) CBC : Cipher Block Chaining
- ECB Mode의 취약점을 보완할 수 있는 암호화 모드 중 하나
- 각 Block들이 연결되어서 암호화가 진행된다
물론 CBC Mode에서도 동일한 key를 사용하지만, 각 Time에서 XOR하는 대상은 전단계에서 암호화된 ciphertext이다
근데 가장 첫번째 단계에서는 전단계에서 암호화된 ciphertexr가 존재하지 않는다
>> 이를 해결하기 위해서 IV(Initialization Vector) : 초기화 벡터를 사용한다
IV는 랜덤값이지만 private가 아닌 public이다
각 단계마다 연결되어서 암호화가 진행되기 때문에 동일한 input이여도 서로 다른 output이 나온다
하지만 Cut and Paste Attack에 대해서는 여전히 가능하지만, 공격 방법이 더 복잡해진다
- Cut and Paste Attack은 어느 모드이든지 공격 시도는 가능한 공격방법이다
※ image encryption : CBC Mode
ECB Mode와 달리 CBC Mode는 동일 input에 대해서도 각 암호화 단계가 연속적으로 이루어지기 때문에 서로 다른 output이 나온다
따라서 이미지를 암호화한 결과는 완벽히 가려진다
3) CTR : Counter Mode
CTR은 중간 임의의 Block에 대한 암호화가 가능하다
왜냐하면 Encryption 모듈에 Plaintext가 아닌 Counter를 넣음으로써 중간 임의의 block을 암호화할 때 Counter 값만 적절히 설정해주면 되기 때문이다
그리고 CTR은 Block Cipher이지만 Stream Cipher 형식으로 암호화되는 모드이다
데이터 무결성
앞에서 설명한 각 암호화 알고리즘들은 "데이터 기밀성"을 쉽게 보장할 수 있다
- "데이터 기밀성"이란 허가되지 않은 사용자가 데이터를 읽을 수 없는 성질을 의미한다
하지만 이러한 암호화 알고리즘들이 "데이터 무결성"도 보장할 수 있을까?
"데이터 무결성"은 "데이터 기밀성"과 완전히 다른 개념이다
Attacker가 암호화된 데이터들을 쉽게 읽을 수는 없겠지만, 이와 상관없이 암호화된 데이터의 흐름을 임의로 섞음으로써 "데이터 무결성"을 침해하는 것은 굉장히 쉽다
>> 따라서 Attacker에 의한 "변조 시도"는 막을 수 없지만 변조가 되면 암호문을 전달받는 Receiver가 "변조 사실"을 알아챌 수는 있게 해줘야 한다
Receiver가 "변조 사실"을 알아챌 수 있게 해주는 것이 MAC이다
MAC : Message Authentication Code
- 데이터의 무결성을 보장하기 위한 코드
- MAC은 CBC Mode를 활용한 방식이다 (Block Cipher를 사용)
- Message를 "Mac Algorithm"을 통해서 계산을 해준다
- 사진에 "MAC Algorithm"에서 사용되는 Key는 Sender와 Receiver 둘다 알고 있어야 한다
1. MAC-Algorithm에 Message & Key 넣기
- 이를 통해서 "MAC"이라는 결과가 추출된다
2. (Message + MAC)을 Receiver에게 전달한다
Receiver는 위의 과정을 동일하게 수행하고 본인이 수행한 결과 MAC과 전달받은 MAC이 동일한지 확인한다
>> 만약 동일하면 변조가 없는 것이고, 다르다면 중간에 Attacker에 의해서 Message가 변조되었음을 의미한다
