네트워크 보안 에센셜 3장 연습 문제 풀이

컴퓨터 네트워크 보안 3장 연습 문제

3. 메시지 길이가 다음과 같을 때, SHA-512 패딩 필드에 들어가야 할 값을 나타내라

1. 1919 비트
   • 1919-1024 = 895
   • 1024-(128+895) = 1bit
2. 1920 비트
   • 1920-1024 = 896
   • 1024-(128+896) = 0
   • Sha512는 Padding을 무조건 추가하므로 1024bit를 추가 한다.
3. 1921 비트
   • 1921-1024 = 897
   • 1024-(128+897) = -1
   • 1024 - 1 = 1023bit

6. Toy Tetrgraph Hash(tth)

이 문제는 2진수 자료 대신 문자를 가지고 SHA에서 사용하는 방법으로 해시 함수를 만드는 방법을 소개 하고 있다

• 문자로 이루어진 메시지가 주어졌을 때,tth는 4개의 문자로 된 해시 값을 출력한다.
• 우선 tth는 주어진 메시지를 16개의 문자로 이루어진 블록으로 나눈다.
  • 이 때 스페이스와 마침표와 대소문자는 무시한다.
  • 만약 메시지가 16으로 나누어지지 않을 경우에는 16의 배수가 되도록 Null로 채워 넣는다
• 하나의 4개의 숫자로 이루어진 running total을 필요로 하는데, 최초의 running total은 (0. 0. 0. 0)이다.
  • 이 것은 첫 번째 블록을 처리할 때 압축 함수의 입력에 사용 된다.
• 압축 함수는 두 라운드로 이루어진다.
  • 라운드 1
    • 다음 텍스트 블록을 행별로 4x4 텍스트 블록을 만든 다음 이것을 숫자로 변경한다. (A=0, B=1 …)
    • 그 다음 각 열을 모듈로 26으로 더한다. 그리고 그 결과 값을 모듈로 26으로 running total에 더한다.
  • 라운드 2
    • 라운드 1에서 얻은 행렬을 이용하여 첫 번째 행을 왼쪽으로 한 자리 옮기고, 두 번째 행은 두 자리를 옮기고, 세 번째 행은 3자리를 왼쪽으로 옮기고, 네 번째 행은 자리를 역순으로 바꾼다.
    • 이제 각 열을 모듈로 26으로 더한 다음 그 결과 값을 모듈로 26으로 running total에 더한다.
    • 마지막 블록이 처리되고 나면, 마지막 running total을 문자로 다시 전환한다

전반적인 Tth의 논리와 압축 함수의 논리를 설명하기 위해 그림 3.4와 그림 3.5에 대응 되는 그림을 그려라

48개의 문자로 이루어진 텍스트 "I Leave Twenty Million Dollars to My Friendly Cousin Bill"에 대한 해시 값을 구하라

• 주어진 문자열을 매트릭스로 변환하고, 이를 a~z까지 대소문자,공백을 고려하지 않고 정렬한다.
• 
• 문제에서 주어진 단일 매트릭스를 계산하는 방법을 위의 사진의 위 매트릭스부터 하나씩 통과 시킨다.
  • 즉 병렬 식으로 동시에 진행하는 것이 아니라, 앞의 매트릭스의 값에 의존하는 형태이다.
• 라운드 2까지 각 매트릭스를 정렬한 값은 아래와 같다.
• 
• 이제 첫번째 매트릭스 부터 initial total을 계산하고, 그 값을 연속적으로 다른 매트릭스에 적용하면 답을 얻을 수 있다.
  • 
  • 정답 : BFQG

TTH 의 취약점을 증명하기 위해 B에서 구한 해시 값과 동일한 값을 갖는 문장을 만들어라

• AYHGDAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAA
• A가 0이기 때문에, 해쉬 값이 같도록 하는 문자들을 입력 후 A로 채우면 된다
  

해시 값과 동일한 값을 갖는 문장을 구하는 방법을 일반화 하면 아래와 같다.
아래와 같이 문자열을 정렬하면, d가 나오는게 자명하기 때문에, 변수를 하나씩 소거해서 원하는 문자열 생성이 가능하다

9. DES의 CFB 모드를 이용해 처리를 해도 CBC 모드로 처리 했을 때와 동일한 결과가 나옴을 보여라 - 유레카

CBC (Cipher Block Chaining) 모드와 CFB (Cipher Feedback) 모드는 서로 다른 암호화 모드이지만, 특정한 조건에서는 같은 결과를 생성할 수 있습니다.

초기화 벡터(IV)가 0인 CBC 모드와, 첫 번째 블록(D1)을 IV로 사용하는 64비트 CFB 모드의 경우, 둘 다 다음 블록을 암호화할 때 입력값과 출력값이 동일합니다.
즉, 이전 블록의 출력값을 현재 블록의 입력값으로 사용하는 CFB 모드와는 달리, CBC 모드는 이전 블록의 출력값과 현재 블록의 입력값을 XOR한 결과를 다음 블록의 입력값으로 사용하기 때문입니다.

Way to yield the same result.

• The CBC mode with an IV of 0 and plaintext blocks D1, D2, . . ., Dn
  • CBC 모드에서 IV가 0인 경우, 첫 번째 평문 블록 D1이 암호화 과정에서 초기값으로 사용됩니다
• 64-bit CFB mode with IV = D1 and plaintext blocks D2, D3, . . ., Dn
  • 평문 블록의 첫 번째 블록인 D1이 초기 벡터(IV)로 사용될 경우, 암호화 결과는 평문 블록들에 대한 순차적인 변화를 따르게 됩니다.

12. 공격자가 요청하지 않은 메시지 0 || (T0 XOR T1)에 대한 정확한 MAC를 계산 할 수 있음을 보여라

• 자세한 내용은 블록 암호 기반 MAC(CMAC)을 참고해주세요
  • 
    • 그림 출처 (CMAC(Cipher-based MAC))

문제 해결을 위한 단계별 접근 방법은 다음과 같습니다

1. 먼저, 상대방이 세 가지 쿼리를 통해 얻은 값을 기록합니다
   • T0 = CBC(K, 0) ⊕ K1
   • T1 = CBC(K, 1) ⊕ K1
   • T2 = CBC(K, [CBC(K, 1)]) ⊕ K1
2. 이제 목표는 상대방이 (쿼리되지 않은) 메시지 0 || (T0 ⊕ T1)에 대한 올바른 MAC을 계산하는 것입니다.
   • 변형된 CMAC 방식을 사용하여 해당 메시지의 MAC을 구해봅니다.
   • VMAC(K, [0 || (T0 ⊕ T1)]) = CBC(K, [0 || (T0 ⊕ T1)]) ⊕ K1

문제 흐름을 CMAC 방식으로 먼저 표현합니다

앞의 주어진 T0,T1,T2를 변형하면 각 단계 별로 값을 구할 수 있습니다. XOR 연산의 특성 때문입니다

1. 두 개의 블록을 처리해야 하므로, 첫 번째 블록의 암호화 출력을 구합니다.
   • E(K, 0) = CBC(K, 0) = T0 ⊕ K1
     • XOR을 반대 항으로 넘겨서 E(K,0)를 구합니다
2. 첫 번째 블록의 암호화 출력을 두 번째 메시지 블록과 XOR합니다.
   • (T0 ⊕ T1)
3. 두 번째 암호화의 입력값을 구합니다.
   • (T1 ⊕ K1) = CBC(K, 1) = E(K, 1)
     • (T0 ⊕ K1) ⊕ (T0 ⊕ T1) = T1 ⊕ K1
       • 같은 값을 XOR하니까 T0 사라질 수 있음
4. 두 번째 암호화의 출력을 구합니다.
   • E(K, [E(K, 1)]) = CBC(K, [CBC(K, 1)]) = T2 ⊕ K1
   • T2 ⊕ K1 ⊕ K1 = T2 인데, 또 같은 값을 XOR 하므로 사라진다
5. 마지막으로, 최종적으로 K1과의 XOR 연산 후 결과값을 구합니다.
   • VMAC(K, [0 || (T0 ⊕ T1)]) = T2
     결과적으로, 상대방은 VMAC(K, [0 || (T0 ⊕ T1)]) = T2를 통해 (쿼리되지 않은) 메시지 0 } (T0 ⊕ T1)에 대한 올바른 MAC을 계산할 수 있습니다.

이렇게 해서 변형된 CMAC 알고리즘은 암호화가 작동하지 않음이 증명되었습니다.

15. RSA를 이용하는 공개키 시스템에서 평문 M을 계산하라

• 공개 키가 e = 5, n = 35, 공격자가 사용자에게 보내지는 암호문 C = 10를 가로챘다고 하자.
  현재 공격자가 모르는 것어 p와 q이다. 하지만 n= pq = 35이며, 1< e = 5 < n 이므로 유추 가능하다.

• M = C^d mod n = 10^d mod 35
  임의로 pq=35가 되는 소수 중 가장 작은 쌍을 찾으면 7,5 이므로 해당 식에 대입해서 문제를 풀어보도록하자

• de mod (p-1)(q-1) = 1

• 5d mod 24 = 1
  결과적으로 d는 5임을 알 수 있다.

• 정답 : M = 10^5 mod 35 = 5

18. 문제 3.13에서 어떻게 RSA가 행렬 M1, M2, M3에 의해 표현 될 수 있었는가

문제 13번에서는 충분히 크고 무작위로 선택 된 값들이 M1과 M2를 채울 때 안전함을 보였습니다.
즉 악의적인 공격자가 평문 메시지를 얻기 위해 k를 찾는 것은 거의 불가능 합니다.

앨리스와 밥의 암호화/복호화 과정 또한 동일합니다.
밥은 무작위 수 k를 개인키로 가지고, m1에 맵핑하여 공개키 x를 얻고 이를 앨리스에게 보냅니다
앨리는 x를 사용하여 m2로 자신의 메시지를 암호화하여 z를 얻고 이를 밥에게 보냅니다.
밥은 k를 사용하여 m3를 통해 z를 해독하여 평문 메시지 P를 얻습니다.

RSA도 행렬로 표현 할 수 있습니다. 거듭 제곱 연산 때문입니다. 거듭 제곱 연산은 행렬의 곱셈으로 표현 할 수 있습니다.

1. m을 행렬로 표현합니다. 이때, 행렬의 크기는 (1 x n)입니다.
2. e를 2진수로 변환합니다.
3. e의 각 비트에 대해, m을 제곱하여 행렬로 표현합니다.
4. 각 비트가 1인 경우에 대해, 해당 행렬을 모두 곱하여 결과를 얻습니다.
   이렇게 거듭제곱 연산을 행렬 곱셈으로 표현하면 RSA 알고리즘을 행렬로 나타낼 수 있습니다.
   다만, 실제 구현에서는 거듭제곱 연산을 빠르게 수행할 수 있는 모듈러 거듭제곱 알고리즘 등을 사용하여 계산을 최적화합니다.

솔루션

1. 평문 메시지 p를 암호화하여 전송하려는 경우, Alice와 Bob이 통신합니다. Bob은 M1 및 M3를 사용하고, Alice는 M2를 사용합니다.
2. Bob은 무작위 수 k를 선택하여 자신의 개인 키로 사용하고, M1을 통해 k를 매핑하여 x를 얻습니다. 그런 다음 x를 Alice에게 공개 키로 보냅니다.
3. Alice는 x를 사용하여 평문 메시지 p를 M2로 암호화하여 암호문 z를 얻습니다. 그런 다음 암호문 z를 Bob에게 전송합니다.
4. Bob은 M3를 사용하여 암호문 z를 자신의 개인 키 k로 복호화하여 평문 메시지 p를 얻습니다.

이 방식을 사용하면, Alice는 공개 키를 사용하여 메시지를 암호화하고, Bob은 개인 키를 사용하여 메시지를 복호화할 수 있습니다. 이렇게 하면 공개 키 암호화 방식이 구현되어 메시지를 안전하게 전송할 수 있습니다.

21. 공통된 소수 q=11 과 원시근 Alpha = 2를 가지는 Diffe-hillman 알고리즘 구조를 고려하자

만일 사용자 A가 공개키 Y_a = 9를 갖는다면, A의 개인 키 X_a는 무엇인가

• Y_A = alpha^X_a mod q
  • 9 = 2^X_a mod 11
  • X_a = 6

만일 사용자 B가 공개 키 Y_b = 3을 갖는다면, 공유하는 비밀 키 K는 무엇인가

문제 오류인지 이전 문제에서 얻은 값을 토대로 풀면 됨

• K = Y_B^(X_A) mod q = Y_A^(X_B) mod q
  • 공유하는 비밀키는 혼자서는 만들 수 없다. 앞선 문제에서 구한 X_a를 이용해서 구하자
  • 3^6 mod 11 = 3
• 공유하는 비밀 키 K는 3이다

레퍼런스

• tth
• DES Overview
• 암호 블록 운용 모드란 무엇인가
• RSA는 무엇인가?
• Diffe-hillman 알고리즘

부족한 점이나 잘못 된 점을 알려주시면 시정하겠습니다 :>