2주차. CryptoHack, 그리고 Protocol 5.0

한샛코드·2025년 3월 25일

@Xpert

목록 보기

2/4

CryptoHack - 2주차

1. Symmetric Ciphers

A. Structure of AES (5분 소요)

ℹ️ AES-128 수행시, 8비트마다 바이트 치환을 16번 수행함 (즉, 4x4 배열이 나옴)

def bytes2matrix(text):
    """ Converts a 16-byte array into a 4x4 matrix.  """
    return [list(text[i:i+4]) for i in range(0, len(text), 4)]

def matrix2bytes(matrix):
    """ Converts a 4x4 matrix into a 16-byte array.  """
    # 매트릭스의 행을 각각 가져와서, 행 내에 있는 각각의 원소들에 대해 chr 연산 수행
    return ''.join(map(str, [''.join(map(str, chr(element))) for element in sum(matrix, [])]))

matrix = [
    [99, 114, 121, 112],
    [116, 111, 123, 105],
    [110, 109, 97, 116],
    [114, 105, 120, 125],
]

print(matrix2bytes(matrix))

2차원 리스트의 matrix를 sum() 함수를 이용하여, 1차원 리스트로 변경한다.
- sum(a, b) → a 리스트에 있는 요소들을 모두 b 리스트에 저장해주는 역할을 한다.
- 리스트 컴프리헨션으로도 충분히 구현 가능할 듯?
1차원 리스트로 변한 matrix를 join() 함수를 이용하여 str 형태로 변환 후, 해당 값을 리턴한다.

B. Round Keys (15분 소요)

ℹ️ Round Keys에서는 state와 round_key를 XOR 연산하여 비선형을 통해 암호의 강도를 높임

state = [
    [206, 243, 61, 34],
    [171, 11, 93, 31],
    [16, 200, 91, 108],
    [150, 3, 194, 51],
]

round_key = [
    [173, 129, 68, 82],
    [223, 100, 38, 109],
    [32, 189, 53, 8],
    [253, 48, 187, 78],
]

def add_round_key(s, k):
    # state와 round_key의 각 원소를 XOR 연산을 수행하고, 줄지어 출력함
    return ''.join(map(str, [ chr(s[y][x] ^ k[y][x]) for y in range(4) for x in range(4) ]))

print(add_round_key(state, round_key))

4x4의 2차원 리스트이므로, 2차원 중첩 for문 통해 리스트 컴프리헨션을 구성한다.
state 및 round_key 리스트의 같은 위치의 원소끼리 XOR 연산을 수행한다.
XOR 연산 수행 후, 해당 값을 chr() 함수를 이용하여 ASCII 코드 → 문자로 변경한다.
1차원 리스트의 결과를 join() 함수를 이용하여 str 형태로 변환 후, 해당 값을 리턴한다.
- 'Structure of AES'의 'matrix2bytes(matrix)' 함수를 사용하여 리턴해도 됨!

여담

몬더그린 같아요

처음 시도하였을 때, 이런 식으로 출력되어서 무언가 잘못된걸까? 싶었다. 그렇게 10분이 지나고...
알고보니 해당 작업은 y(열)를 x(행)보다 먼저 탐색을 수행하기에, 각각의 순서를 변경해서 풀었다.

2. Hash Functions

A. Jack's Birthday Hash (45분 이상 - 이해 난해..)

JACK11은 11비트 길이의 해시함수이고, 조그마한 차이에도 엄청난 차이를 보인다고 한다.

그래서, JACK11의 해시 알고리즘에 대해 아무런 정보가 없다고 할 때, (평균적으로) 잭의 비밀과 50%확률로 충돌하는 해시 값을 갖는 고유한 비밀의 수를 구하는 것이 문제이다.

표현할 수 있는 비트 수의 갯수가 11개이므로, 2^{11} = 2048개의 경우의 수가 있다.
비트수의 한계로 인해 다른 데이터에 대해 똑같은 해시 값을 가질 수 있다.
첫 번째 어떤 비밀이 다른 비밀의 해시값과 충돌하지 않을 확률은 2047/2048이다.
두 번째 어떤 비밀이 다른 비밀의 해시값과 충돌하지 않을 확률 또한 2047/2048이다.
즉, k개의 시도에 대해 충돌하지 않을 확률은 (1 - (1/2048))^k 이다.
그런데, 문제에서 충돌이 발생할 확률이 50%일 때를 묻고 있다.
즉, 위 식의 값은 0.5가 되어야 한다. → (1 - (1/2048))^k = 0.5이다.
log를 사용하여 k 값을 구하면, log_{1 - (1/2048)} 0.5 = k = 1419.21882...가 나온다.
즉, 0.21882...개는 없으므로, 반올림 과정을 거치면 1420(개)가 나온다.

수학을 한 지 너무 오래돼서... 이런거는 계산기한테 맏기도록 하자

B. Jack's Birthday Confusion (30분 이상)

위의 문제에서 조건은 동일하고, 서로 다른 비밀의 충돌이 발생할 확률이 75%일 때를 묻고 있다.
즉, 충돌이 발생하지 않을 확률은 25%이다. 이를 토대로 계산한다.
k번 시도까지 충돌 없을 확률 = 2048/2048 2048-1/2048 ... * 2048-k+1 / N
분자는 2048 (2048-1) ... (2048-k+1) = 2048! / (2048-n)이 된다.
분모는 2048^n이 된다. → 2048! / (2048-k)! * 2048^k = 0.25을 구하면 된다.
- 발화식은 구했으니, k값을 찾는 것은 계산기의 힘을 빌리도록 하자.
정답 k는 76(개)이 된다.

3. RSA

RSA Signatures - 다음 날까지...

import hashlib # SHA256을 위한 라이브러리
from Crypto.Util.number import bytes_to_long

N = ...
d = ...

# 해당 문장을 플래그 값으로 사용하라고 한다.
# 근데, sha256 함수에서 바이트 타입으로 매개변수를 받기 때문에 바이트로 변환한다.
sign = b"crypto{Immut4ble_m3ssag1ng}"
# hashlib에 있는 sha256 함수를 이용해서, 플래그를 바탕으로 해시 값을 생성함
sha = hashlib.sha256(sign).digest()
# 해시 값을 다시 암호화 해주는데, 그 전에 해시 값을 정수로 변환하고 작업을 진행함
print(pow(bytes_to_long(sha), d, N))

문제를 잘못 이해했어서... 계속 서순을 반대(RSA -> SHA256)로 시도하니 왜 이게 아닌지 몰랐다.
제대로 이해하면, 서명값에 대한 SHA 256을 사용하고, 결국 RSA 서명 값을 원하는 것이었다.
일단, 이 문제를 해결하려면 hashlib 라이브러리의 sha256()이라는 함수를 사용할 줄 알아야한다.
sha26에서 서명 값은 바이트 타입의 문자열을 받고 있기 때문에, 서명 값을 변환해줘야 한다.
서명 값을 넣고, digest()를 통해 연산 결과 값을 산출한다.
그리고 이 해시 값을 연산하기 전에, 바이트 타입으로 리턴되었으므로, 다시 이것을 정수로 변환해준다.
그리고, RSA 연산을 수행하면 정답이 나오는데... 너무 길어서 생략한다.

암호학 2주차 - Protocol 5.0 허점

ℹ️ 문제는 중간에 제3자(해커)가 통신을 가로채 엘리스인 척, 밥인 척하며 통신할 수 있음

즉, 랜덤넘버(R)을 가로채면 모든 통신을 가로채거나 조작할 수 있다.
"랜덤넘버를 좀 더 안전하게 암호화하면 되지 않을까"에 착안하여, R에 인증(CA)을 추가하면 되지 않을까 생각한다.
다시 말하자면, 밥은 그 비밀키가 진짜 엘리스의 비밀키로 암호화하였는지 알 수 없다.
- 애초에 비밀키는 엘리스만이 가지고 있고, 엘리스 외에는 비밀키의 진위여부를 알 수 없다.
즉, CA(제3자)를 이용하여 "CA가 이것을 보장합니다."를 추가하면 되지 않을까 생각한다.

수정된 방식

엘리스가 밥에게 "I am Alice"를 전송한다.
밥이 엘리스에게 R을 전송한다.
엘리스는 R에다가 자신의 비밀키 대신에 인증(CA)로 서명한 값을 더하여 이를 함께 전달한다.
밥이 엘리스에게 공개키를 요청한다.
엘리스가 자신의 공개키를 제공한다.
밥은 공개키를 통해 R을 검증한다.

회고

이번 차시에서 '프로토콜 5.0의 허점'에 대해서 생각하면서 떠올린 것인데, 암호학은 "방패를 뚫는 창, 그리고 그것을 막는 방패를 찾는 방안"의 무한 굴레라고 생각했다. 5.0 원리만 봤을 때에도 '완벽하다'고 생각했는데, 실질적으로 허점이 있다는 것을 들었을 때에는 생각하기 난감했었다. 그래도 배운 개념을 곱씹어보면서 "여기서 허점이 있겠구나"라고 떠올렸을 때 재미가 있었다. 약간 '해변가에서 반지 찾기', 혹은 '보물 찾기'와 비슷한 느낌이다. 아직 암호학을 새발의 피만큼 배워서 그렇게 느낀 것일지도 모르겠지만, 이러한 정신으로 계속해서 꾸준히 암호학에 도전해볼 생각이다.