[SISS/암호학 스터디] 여름 9주차 스터디 - 전자 서명

여름 9주차 스터디 - 전자 서명

수강 인증 화면 캡쳐

: 9주차 08/26 ~ 09/01 전자 서명

 

전자 서명

---

• 전자 서명
  • 메시지의 무결성과 부인 방지를 위해 사용
  • 서명키와 검증키를 이용
• 기본 원리
  • 서명과 검증
  • 해시 함수를 이용한 전자 서명 → 데이터 크기에 따른 불편을 최소화 → 안전성 향상

 

• RSA 전자 서명
  • RSA 공개키 암호를 사용하여 서명과 검증을 진행
  • 공격 - 유효한 메시지와 서명 쌍 생성
    1. 검증키 이용
    2. 두 개의 유효한 메시지와 대응되는 서명 쌍 이용
  • 해시 이용한 RSA 전자 서명 → 위의 공격으로부터 안전

 

• DSA 전자 서명
  • Digital Signature Algorithm
  • 특징
    • 서명 길이가 짧음
    • RSA보다 빠름
  • DSA 파라미터 및 키 생성
    • 파라미터 p, q, g
      1. 무작위 소수 q를 고름
      2. p-1이 q의 배수인 p 선택
      3. 출력이 q 이상인 해시 함수 선택
      4. p-1보다 작고 1보다 큰 정수 h 선택
      5. g ≡ h^(p−1)/q (mod p)를 계산 → g가 1일 경우, h를 다시 선택하여 재계산
    • 검증키, 서명키
      1. 1 ≤ x ≤ q−1인 정수 x 선택
      2. y ≡ g^x (mod p)를 계산 → y는 검증키, x는 서명키
    • 서명 생성
      1. 1 ≤ k ≤ q−1인 k를 선택
      2. 서명 s 계산
         • δ = (H(m) + xγ)k^(−1) mod q
         • s = (γ, δ)
         • γ = (g^k mod p) mod q
    • 서명 검증
      1. e_1, e_2 계산
         • e_1 = H(m)δ^(-1) mod q
         • e_2 = γδ^(-1) mod q
      2. γ′을 계산하여 서명의 γ와 비교
         • γ′ = (*g^e_1y^e_*2 mod p) mod q

• 증명
  • w ≡ δ^(-1) (mod q)인 w에 대해 δ ≡ (H(m) + xγ)k^(-1) (mod q)이므로
  • k ≡ H(m)δ^(-1) + xγδ^(-1) ≡ H(m)w + xγw (mod q)가 성립
  • k = H(m)w + xγw + nq를 만족하는 정수 n이 존재
  • g ≡ h^{(p−1)/q} (mod p)이므로 페르마의 소정리에 의해 g^q ≡ h^(p−1) ≡ 1 (mod p)
  • g^q ≡ 1 (mod p)가 성립하므로 다음이 성립
  • g^k ≡ g^{H(m)w + xγw + nq} **≡ g^{H(m)w + xγw} **≡ g^{H(m)w}g^{xγw} **≡ g^{H(m)w}y^{γw} **≡ g^e_1y^*e_*2(mod p)
  • γ = (g^k mod p) mod q = (g^e_1y^*e_*2 mod p) mod q
  → 올바른 서명 s에 대해, 계산한 γ′이 γ와 동일할 경우 서명 유효

 

DSA 실습 1

---

• challenge.py → 공개키 및 비밀키 생성 → p, q, g, y, 토큰 출력
  • 구현된 DSA 클래스의 두 가지 문제
    • (난수 재사용) sign에서 각각의 k를 사용하지 않고 공통된 k를 사용
    • 비밀키 x의 역원을 난수로 사용 → 한 서명으로부터 생성된 r, s로 x에 대한 방정식을 세울 수 있음

  from Crypto.Util.number import getPrime, inverse, bytes_to_long, isPrime
  from random import randrange, choices
  from hashlib import sha1
  import string
  
  class DSA(object):
      def __init__(self):
          while True:
              self.q = getPrime(160)
              r = randrange(1 << 863, 1 << 864)
              self.p = self.q * r + 1
              if self.p.bit_length() != 1024 or isPrime(self.p) != True:
                  continue
              self.g = pow(2, r, self.p)
              if self.g == 1:
                  continue
              self.x = randrange(1, self.q)
              self.y = pow(self.g, self.x, self.p)
              self.k = inverse(self.x, self.q)
              break
  
      def sign(self, msg):
          r = pow(self.g, self.k, self.p) % self.q
          h = bytes_to_long(sha1(msg).digest())
          s = inverse(self.k, self.q) * (h + self.x * r) % self.q
          return (r, s)
  
      def verify(self, msg, sig):
          r, s = sig
          if s == 0:
              return False
          s_inv = inverse(s, self.q)
          h = bytes_to_long(sha1(msg).digest())
          e1 = h * s_inv % self.q
          e2 = r * s_inv % self.q
          r_ = pow(self.g, e1, self.p) * pow(self.y, e2, self.p) % self.p % self.q
          if r_ == r:
              return True
          else:
              return False
  
  dsa = DSA()
  token = "".join(choices(string.ascii_letters + string.digits, k=32)).encode()
  
  print("Welcome to dream's DSA server")
  while True:
      print("[1] Sign")
      print("[2] Verify")
      print("[3] Get Info")
  
      choice = input()
  
      if choice == "1":
          print("Input message (hex): ", end="")
          msg = bytes.fromhex(input())
          if msg == token:
              print("Do not cheat !")
          else:
              print(dsa.sign(msg))
  
      elif choice == "2":
          print("Input message (hex): ", end="")
          msg = bytes.fromhex(input())
          if len(msg) > 100:
              print("Too long message")
          else:
              print("Input signagure (r, s as decimal integer): ", end="")
              sig = map(int, input().split(", "))
              if dsa.verify(msg, sig) == True:
                  print("Signature verification success")
                  if msg == token:
                      print(open("flag", "rb").read())
              else:
                  print("Signature verification failed")
  
      elif choice == "3":
          print(f"p = {dsa.p}")
          print(f"q = {dsa.q}")
          print(f"g = {dsa.g}")
          print(f"y = {dsa.y}")
          print(f"token = {token}")
  
      else:
          print("Nope")
  

 

 

• ex.py → 난수 재사용을 이용한 풀이 → 두 서명의 s 값을 서로 빼 rx가 소거시킨 후 k를 구함(이를 이용해 비밀키 x를 복구)

from Crypto.Util.number import bytes_to_long, inverse
from hashlib import sha1
from pwn import *

hsh = lambda m: bytes_to_long(sha1(m).digest())

io = remote("host3.dreamhack.games", 20200)

io.sendlineafter(b"[3] Get Info\n", b"3")
exec(io.recvuntil(b"[1] Sign\n", drop=True))

io.sendlineafter(b"[3] Get Info\n", b"1")
io.sendlineafter(b"(hex): ", b"00")
r1, s1 = eval(io.recvline())

io.sendlineafter(b"[3] Get Info\n", b"1")
io.sendlineafter(b"(hex): ", b"01")
r2, s2 = eval(io.recvline())

h1 = hsh(b"\x00")
h2 = hsh(b"\x01")
k = (h1 - h2) * inverse(s1 - s2, q) % q
x = (k * s1 - h1) * inverse(r1, q) % q

assert pow(g, x, p) == y

flag_s = x * (hsh(token) + x * r1) % q

io.sendlineafter(b"[3] Get Info\n", b"2")
io.sendlineafter(b"(hex): ", token.hex().encode())
io.sendlineafter(b"integer): ", f"{r1}, {flag_s}".encode())

io.interactive()

 

• ex.sage → associated nonce를 이용한 풀이 → 비밀키 x에 대한 이차 합동식을 만들어 해를 통해 비밀키를 복구

from Crypto.Util.number import bytes_to_long, inverse
from hashlib import sha1
from pwn import *

hsh = lambda m: bytes_to_long(sha1(m).digest())

io = remote("host3.dreamhack.games", "15773")

io.sendlineafter(b"[3] Get Info\n", b"3")
exec(io.recvuntil(b"[1] Sign\n", drop=True))

io.sendlineafter(b"[3] Get Info\n", b"1")
io.sendlineafter(b"(hex): ", b"00")
r, s = eval(io.recvline())

h = hsh(b"\x00")

P.<x> = PolynomialRing(Zmod(q))
roots = (r * x^2 + h * x - s).roots()

for root in roots:
    x = int(root[0])
    if pow(g, x, p) == y:
        break

flag_s = x * (hsh(token) + x * r) % q

io.sendlineafter(b"[3] Get Info\n", b"2")
io.sendlineafter(b"(hex): ", token.hex().encode())
io.sendlineafter(b"integer): ", f"{r}, {flag_s}".encode())

io.interactive()

DSA 실습 1

 

DSA 실습 2

---

• 올바르지 않은 해시 함수를 사용할 경우
• prob.py → 공개키 및 비밀키 생성 → 파라미터, p, q, g, y, 토큰 출력(매 서명 생성 시 k 업데이트)

  #!/usr/bin/env python3
  from Crypto.Util.number import getPrime, inverse, bytes_to_long, isPrime
  from random import randrange, choices
  from hashlib import sha1
  import string
  
  class DSA(object):
      def __init__(self):
          print('generating parameters...')
          while True:
              self.q = getPrime(160)
              r = randrange(1 << 863, 1 << 864)
              self.p = self.q * r + 1
              if self.p.bit_length() != 1024 or isPrime(self.p) != True:
                  continue
              h = randrange(2, self.p - 1)
              self.g = pow(h, r, self.p)
              if self.g == 1:
                  continue
              self.x = randrange(1, self.q)
              self.y = pow(self.g, self.x, self.p)
              self.k = randrange(1, self.q)
              break
      
      def update(self):
          self.k = randrange(1, self.q)
  
      def sign(self, msg):
          r = pow(self.g, self.k, self.p) % self.q
          h = bytes_to_long(msg) % self.q
          s = inverse(self.k, self.q) * (h + self.x * r) % self.q
          self.update()
          return (r, s)
  
      def verify(self, msg, sig):
          r, s = sig
          if s == 0:
              return False
          s_inv = inverse(s, self.q)
          h = bytes_to_long(msg) % self.q
          e1 = h * s_inv % self.q
          e2 = r * s_inv % self.q
          r_ = pow(self.g, e1, self.p) * pow(self.y, e2, self.p) % self.p % self.q
          if r_ == r:
              return True
          else:
              return False
  
  dsa = DSA()
  token = "".join(choices(string.ascii_letters + string.digits, k=32)).encode()
  
  print("Welcome to dream's DSA server")
  while True:
      print("[1] Sign")
      print("[2] Verify")
      print("[3] Get Info")
  
      choice = input()
  
      if choice == "1":
          print("Input message (hex): ", end="")
          msg = bytes.fromhex(input())
          if msg == token:
              print("Do not cheat !")
          else:
              print(dsa.sign(msg))
  
      elif choice == "2":
          print("Input message (hex): ", end="")
          msg = bytes.fromhex(input())
          if len(msg) > 100:
              print("Too long message")
          else:
              print("Input signagure (r, s as decimal integer): ", end="")
              sig = map(int, input().split(", "))
              if dsa.verify(msg, sig) == True:
                  print("Signature verification success")
                  if msg == token:
                      print(open("flag", "rb").read())
              else:
                  print("Signature verification failed")
  
      elif choice == "3":
          print(f"p = {dsa.p}")
          print(f"q = {dsa.q}")
          print(f"g = {dsa.g}")
          print(f"y = {dsa.y}")
          print(f"token = {token}")
  
      else:
          print("Nope")
  

 

• ex.py
  • 이전 실습과의 차이점
    • sign 함수와 verify 에서 h 생성 과정이 다름
    • 이전 문제는 h = bytes_to_long(sha1(msg).digest())이용
    • h = bytes_to_long(msg) % self.q로 변경
  • 문제점
    • 주어진 토큰을 bytes_to_long의 인자로 해 q를 몇 번 더하거나 빼 다시 bytes 스트링으로 변환할 경우 다른 입력에도 같은 두 입력이 생성되는 결과가 발생
    • 제 2 역상 저항성을 만족하지 않음(특정 토큰의 해시값과 같은 해시값을 가지는 다른 입력값을 쉽게 찾을 수 있음) → q가 160비트의 소수이고, if len(msg) > 100:에서 입력은 최대 100바이트임을 알 수 있음 → 목표 토큰에서 q의 값을 충분히 더하거나 뺄 수 있음

  from pwn import *
  from Crypto.Util.number import *
  
  # io = process(["python3", "prob.py"])
  io = remote("host3.dreamhack.games", "24389")
  
  io.sendline(b"3")
  
  def recv():
      io.recvuntil(f"= ".encode())
      return eval(io.recvline())
  
  p, q, g, y, token = [recv() for _ in range(5)]
  
  token_int = bytes_to_long(token)
  forge_token = long_to_bytes(token_int + q)
  
  io.sendline(b"1")
  io.sendlineafter(b": ", bytes.hex(forge_token).encode())
  r, s = eval(io.recvline())
  
  io.sendline(b"2")
  io.sendline(bytes.hex(token).encode())
  io.sendline(f"{r}, {s}".encode())
  
  io.recvuntil(b"success\\n")
  
  flag = eval(io.recvline()).decode()
  io.close()
  
  print(flag)
  

DSA 실습 2