[SISS/암호학 스터디] 여름 7주차 스터디 - 디피헬만 키 교환

여름 7주차 스터디 - 디피헬만 키 교환

수강 인증 화면 캡쳐

: 7주차 08/12 ~ 08/18 키 교환 알고리즘

 

키 교환 알고리즘

---

• 대칭키 암호 → 송신자와 수신자가 같은 키를 공유하고 있어야 함
• 디피-헬만 알고리즘
  • 이산 로그 문제 → a^x ≡ b (mod m)을 만족하는 x를 구하는 것이 어렵다는 점을 이용 (m^(1/2)번 정도의 연산을 해아함)
    • 쉽게 해결되는 경우 → p-1에 대해 smooth할 때 (소인수가 모두 p-1보다 작을 때/p는 소수 중 p+1, p-1이 작은 소수로 소인수분해되는 수)
  • 키 교환 과정 → K가 키로 사용됨
    • 앨리스: 소수 p와 1 ≤ g ≤ p−1인 g를 밥에게 전송
    • 밥: 1 ≤ b ≤ p−1인 b를 정하여 B = g^(ba) mod p를 앨리스에게 전송
      • 앨리스: 밥이 보낸 B를 a제곱하여 K ≡ B^a ≡ (g^b)^a ≡ g^(ba) mod p를 계산
    • 앨리스: 1 ≤ a ≤ p−1인 a를 정하여 A = g^a mod p를 밥에게 전송
      • 밥: 앨리스가 보낸 A를 b제곱하여 K ≡ A^b ≡ (g^a)^b **≡ g^(ab) mod p를 계산
  • 중간자 공격
    • 통신하는 상대가 누구인지 모른다는 점을 이용해 공격자가 송수신자의 가운데에서 두 사람과 각각 키를 생성중간자 공격

중간자 공격

 

실습 - 중간자 공격

---

• challenge.py → 공격자에 대한 검증이 없음
  

  #!/usr/bin/python3
  from Crypto.Util.number import getPrime
  from Crypto.Util.Padding import pad, unpad
  from Crypto.Cipher import AES
  import hashlib
  import random
  
  class Person(object):
      def __init__(self, p):
          self.p = p
          self.g = 2
          self.x = random.randint(2, self.p - 1)
      
      def calc_key(self):
          self.k = pow(self.g, self.x, self.p)
          return self.k
  
      def set_shared_key(self, k):
          self.sk = pow(k, self.x, self.p)
          aes_key = hashlib.md5(str(self.sk).encode()).digest()
          self.cipher = AES.new(aes_key, AES.MODE_ECB)
  
      def encrypt(self, pt):
          return self.cipher.encrypt(pad(pt, 16)).hex()
  
      def decrypt(self, ct):
          return unpad(self.cipher.decrypt(bytes.fromhex(ct)), 16)
  
  flag = open("flag", "r").read().encode()
  prime = getPrime(1024)
  print(f"Prime: {hex(prime)}")
  alice = Person(prime)
  bob = Person(prime)
  
  alice_k = alice.calc_key()
  print(f"Alice sends her key to Bob. Key: {hex(alice_k)}")
  print("Let's inturrupt !")
  alice_k = int(input(">> "))
  if alice_k == alice.g:
      exit("Malicious key !!")
  bob.set_shared_key(alice_k)
  
  bob_k = bob.calc_key()
  print(f"Bob sends his key to Alice. Key: {hex(bob_k)}")
  print("Let's inturrupt !")
  bob_k = int(input(">> "))
  if bob_k == bob.g:
      exit("Malicious key !!")
  alice.set_shared_key(bob_k)
  
  print("They are sharing the part of flag")
  print(f"Alice: {alice.encrypt(flag[:len(flag) // 2])}")
  print(f"Bob: {bob.encrypt(flag[len(flag) // 2:])}")
  

 

• exploit.py → 밥과의 통신에서 앨리스로 위장하여 악의적인 값 전달
  • g^x_a, g^x_b를 알 수 있으므로 (앨리스 비밀키 x_a, 밥 비밀키 x_b)
    • g와 연관된 값을 송신하여 통신 종료
    • 0(또는 1)을 송신하여 밥과 앨리스의 키를 0(또는 1)로 설정하게 함

  from pwn import *
  from Crypto.Util.Padding import pad, unpad
  from Crypto.Cipher import AES
  import hashlib
  
  class Person(object):
      def __init__(self, p):
          self.p = p
          self.g = 2
          self.x = random.randint(2, self.p - 1)
      
      def calc_key(self):
          self.k = pow(self.g, self.x, self.p)
          return self.k
  
      def set_shared_key(self, k):
          self.sk = pow(k, self.x, self.p)
          aes_key = hashlib.md5(str(self.sk).encode()).digest()
          self.cipher = AES.new(aes_key, AES.MODE_ECB)
  
      def encrypt(self, pt):
          return self.cipher.encrypt(pad(pt, 16)).hex()
  
      def decrypt(self, ct):
          return unpad(self.cipher.decrypt(bytes.fromhex(ct)), 16)
  
  io = remote("host3.dreamhack.games", 21537)
  
  io.recvuntil(b"Prime: ")
  p = int(io.recvline(), 16)
  
  not_alice, not_bob = Person(p), Person(p)
  
  # Communication 1
  io.recvuntil(b"Key: ")
  not_bob.set_shared_key(int(io.recvline(), 16))
  
  io.sendlineafter(">> ", str(not_alice.calc_key()).encode())
  
  # Communication 2
  io.recvuntil(b"Key: ")
  not_alice.set_shared_key(int(io.recvline(), 16))
  
  io.sendlineafter(">> ", str(not_bob.calc_key()).encode())
  
  # Alice's shared key is same with not_bob's shared key
  io.recvuntil(b"Alice: ")
  flag1 = not_bob.decrypt(io.recvline().decode())
  
  # Bob's shared key is same with not_alice's shared key
  io.recvuntil(b"Bob: ")
  flag2 = not_alice.decrypt(io.recvline().decode())
  
  io.close()
  
  print((flag1 + flag2).decode())
  

중간자 공격 실습

 

실습 - 이산 로그 문제

---

→ smooth한 수 만들기

• chall.py → 아래 두 가지 조건을 만족하는 512비트 소수 p를 찾아야함
  1. p-1 소인수분해 시 작은 소인수만으로 구성 (B-smooth)
  2. 100회 연속 이산 로그 문제 해결 가능

  from Crypto.Util.number import isPrime
  import secrets
  
  flag = open("flag.txt", "r").read()
  
  pbits = 512
  
  p = int(input("Prime: "))
  g = int(input("g: "))
  assert isPrime(p) and p.bit_length() == pbits
  
  for rnd in range(100):
      print(f"--- Round {rnd + 1} ---")
      secret = secrets.randbits(pbits)
      print(f"{pow(g, secret, p) = }")
      assert secret == int(input("secret: "))
  
  print("Wow, you are the master of DLP!")
  print(flag)
  

 

• exploit.py
  • g의 Multiplicative order → 페르마의 소정리에 의해 p와 서로소인 모든 정수 g에 대해 g^(p−1) ≡ 1 (mod p)를 만족 → 정수 g(1 ≤ g ≤ p−1)에 대하여 p−1번 곱하면 1이 나옴 (곱셈의 항등원)
    • 원시근 → 3처럼 Multiplicative order가 p−1인 수
      • 원시근 r과 모든 [1, p−1)에 속하는 i에 대해 다음이 성립 → r^i ≢ 1 (mod p)
    ∴ 소수 p는 p−1이 smooth하면서 2^512에 최대한 가깝고, g는 p를 법으로 한 곱셈환에서의 원시근이어야 함
  • 풀이
    • p < 2^512를 만족하는 최댓값 k를 찾은 후, p = k * base + 1로 설정
    • p를 소수로 만들기 위해 base를 하나씩 뺌

•  

from sage.all import *  # 파이썬 코드로 바꾸기 위해 sage의 함수를 import
from pwn import *
from Crypto.Util.number import isPrime
from tqdm import trange

# io = process(["python3", "chall.py"])
io = remote("host3.dreamhack.games", "20106")

pbits = 512

base = 1
for small_p in Primes():
    base *= small_p
    if int(base).bit_length() >= pbits - 20:  # base를 int형으로 바꿈
        break

k = 2**pbits // base  # 연산자 수정 (^ → **)
p = k * base + 1
while not isPrime(int(p)):  # p를 int형으로 바꿈
    p -= base


Fp = GF(p)
g = Fp.multiplicative_generator()

io.sendlineafter(b": ", str(p).encode())
io.sendlineafter(b": ", str(g).encode())

for _ in trange(100):
    io.recvuntil(b"= ")
    res = int(io.recvline())
    secret = Fp(res).log(g)

    io.sendlineafter(b": ", str(secret).encode())

io.interactive()

이산 로그 문제 실습