# Write-ups Diffie-Hellman Starter 1-5, Static Client 1,2

## Tóm tắt thuật toán trao đổi khóa Diffie-Hellman

- Alice và Bob thỏa thuận sử dụng chung một nhóm cyclic hữu hạn $G$ và một phần tử sinh $g$ của $G$. Phần tử sinh $g$ công khai với tất cả mọi người, kể cả kẻ tấn công. Dưới đây chúng ta giả sử nhóm $G$ là nhóm nhân.
- Alice chọn một số tự nhiên ngẫu nhiên $a$ và gửi $g^{a} \bmod p$ cho Bob.
- Bob chọn một số tự nhiên ngẫu nhiên $b$ và gửi $g^{b} \bmod p$ cho Alice.
- Alice tính $(g^b)^a \bmod p$
- Bob tính $(g^a)^b \bmod p$
- Vì giá trị $(g^b)^a$ và $(g^a)^b$ là bằng nhau (do nhóm $G$ có tính kết hợp), cả Alice và Bob đều tính được giá trị $g^{ab}$ và có thể sử dụng nó cho khóa bí mật chung.


- Cả Alice và Bob đều có được giá trị chung cuối cùng vì $(g^a)^b = (g^b)^a \bmod p$. Lưu ý rằng chỉ có $a, b$ và $g^{ab} = g^{ba} \bmod p$ là được giữ bí mật. Tất cả các giá trị khác như $p, g, g^a \bmod p$ và $g^b \bmod p$ được truyền công khai. Sau khi Alice và Bob tính được bí mật chung, cả hai có thể sử dụng nó làm khóa mã hóa chung chỉ có hai người biết để gửi dữ liệu trên kênh truyền thông mở.
- Trong thực tế để giao thức được an toàn, người ta sử dụng giá trị lớn hơn nhiều cho $a, b$, và $p$, vì trong ví dụ trên chỉ có tổng cộng 23 kết quả khác nhau cho $n \bmod 23$ (do đó kẻ tấn công chỉ cần thử hết $23$ trường hợp là tìm ra khóa bí mật). Nếu số nguyên tố $p$ có ít nhất $300$ chữ số, còn $a$ và $b$ có ít nhất $100$ chữ số, thì ngay cả những máy tính hiện đại nhất hiện nay cũng không thể tìm được $a$ nếu chỉ biết $g, p, g^b \bmod p$ và $g^a \bmod p$. Bài toán này, gọi là bài toán Lôgarit rời rạc, hiện chưa có cách giải hiệu quả bằng máy tính (vì vậy được sử dụng để tạo khóa công khai).
- Lưu ý, $g$ không cần thiết là một căn nguyên thủy có giá trị lớn. Trong thực tế người ta hay sử dụng các giá trị $2, 3$ hoặc $5$.

## Diffie-Hellman Starter 1
- Đề bài cho số nguyên tố $p=991$ và phần tử $g=209$, yêu cầu tìm phần tử nghịch đảo d sao cho $g.d \bmod p = 1$
- $g.d \bmod p = 1 \iff d = g^{-1} \bmod p = 209^{-1} \bmod 991 = 569$

## Diffie-Hellman Starter 2

- Đề bài cho số nguyên tố $p = 28151$ và yêu cầu tìm phần tử nguyên thủy nhỏ nhất $g$ của $F_{p}$

``sol.py``

def order(g, p): 
    for i in range(2, p): 
        if pow(g, i, p) == g:
            return i
    return p

p = 28151
for g in range(2,p):
    o = order(g, p)
    if o == p:
        print(f"g = {g}")
        break

- $g = 7$

## Diffie-Hellman Starter 3
- Đề bài cho 3 số $p,g,a$ và yêu cầu tính $g^{a} \bmod p$

## Diffie-Hellman Starter 4
- Đề bài cho các số $g,p,A,b,B$, yêu cầu tìm lại shared secret
- $\text{shared secret} = A^{b} \bmod p$

## Diffie-Hellman Starter 5
- Đề bài cho các số $g,p,A,b,B$, 1 json gồm iv và encrypted_flag và 2 file source.py và decrypt.py

``source.py``

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib
import os
from secret import shared_secret

FLAG = b'crypto{????????????????????????????}'


def encrypt_flag(shared_secret: int):
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Encrypt flag
    iv = os.urandom(16)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    ciphertext = cipher.encrypt(pad(FLAG, 16))
    # Prepare data to send
    data = {}
    data['iv'] = iv.hex()
    data['encrypted_flag'] = ciphertext.hex()
    return data


print(encrypt_flag(shared_secret))

``decrypt.py``

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib


def is_pkcs7_padded(message):
    padding = message[-message[-1]:]
    return all(padding[i] == len(padding) for i in range(0, len(padding)))


def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Decrypt flag
    ciphertext = bytes.fromhex(ciphertext)
    iv = bytes.fromhex(iv)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    plaintext = cipher.decrypt(ciphertext)

    if is_pkcs7_padded(plaintext):
        return unpad(plaintext, 16).decode('ascii')
    else:
        return plaintext.decode('ascii')


print(decrypt_flag(shared_secret, iv, ciphertext))

- Dựa vào file source.py mình biết được rằng flag đã được mã hóa theo AES-CBC
- Công việc của mình là tìm lại key = shared secret giống như bài trên, hoàn thiện file decrypt.py là sẽ thu lại được flag

``decrypt.py``

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib


def is_pkcs7_padded(message):
    padding = message[-message[-1]:]
    return all(padding[i] == len(padding) for i in range(0, len(padding)))


def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Decrypt flag
    ciphertext = bytes.fromhex(ciphertext)
    iv = bytes.fromhex(iv)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    plaintext = cipher.decrypt(ciphertext)

    if is_pkcs7_padded(plaintext):
        return unpad(plaintext, 16).decode('ascii')
    else:
        return plaintext.decode('ascii')

g = 2
p = 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
A = 112218739139542908880564359534373424013016249772931962692237907571990334483528877513809272625610512061159061737608547288558662879685086684299624481742865016924065000555267977830144740364467977206555914781236397216033805882207640219686011643468275165718132888489024688846101943642459655423609111976363316080620471928236879737944217503462265615774774318986375878440978819238346077908864116156831874695817477772477121232820827728424890845769152726027520772901423784
B = 1241972460522075344783337556660700537760331108332735677863862813666578639518899293226399921252049655031563612905395145236854443334774555982204857895716383215705498970395379526698761468932147200650513626028263449605755661189525521343142979265044068409405667549241125597387173006460145379759986272191990675988873894208956851773331039747840312455221354589910726982819203421992729738296452820365553759182547255998984882158393688119629609067647494762616719047466973581
b = 197395083814907028991785772714920885908249341925650951555219049411298436217190605190824934787336279228785809783531814507661385111220639329358048196339626065676869119737979175531770768861808581110311903548567424039264485661330995221907803300824165469977099494284722831845653985392791480264712091293580274947132480402319812110462641143884577706335859190668240694680261160210609506891842793868297672619625924001403035676872189455767944077542198064499486164431451944
shared_secret = pow(A,b,p)
iv = '737561146ff8194f45290f5766ed6aba'
ciphertext = '39c99bf2f0c14678d6a5416faef954b5893c316fc3c48622ba1fd6a9fe85f3dc72a29c394cf4bc8aff6a7b21cae8e12c'

print(decrypt_flag(shared_secret, iv, ciphertext))
#crypto{sh4r1ng_s3cret5_w1th_fr13nd5}

- flag: crypto{sh4r1ng_s3cret5_w1th_fr13nd5}

## Static Client 1


- Chall mô phỏng lại Man-In-The-Middle Attack, trong đó Alice và Bob thực hiện trao đổi key bằng DHKE
- Mình sẽ đóng vai trò là kẻ nghe lén, công việc của mình là sẽ tìm lại key để decrypt flag
- Đầu tiên mình thử tìm lại key bằng cách dùng discreet logarithm để tìm lại 2 số mũ bí mật $a,b$ nhưng không được :v
- Mình để ý thấy rằng có thể tìm lại được shared secret bằng cách gửi cho Bob:

- $p'= p$
- $g' = A$
- $A' = 1$
- Khi đó Bob sẽ gửi lại số $B = g'^{b} \bmod p = A^{b} \bmod p = \text{shared secret}$

``decrypt.py``

from pwn import *
from Crypto.Util.number import *
import json


from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib


r = remote('socket.cryptohack.org', 13373)

def json_recv():
    line = r.recvline()
    return json.loads(line.decode())

def json_send(hsh):
    request = json.dumps(hsh).encode()
    r.sendline(request)

r.recvuntil("Intercepted from Alice: ")
res = json_recv()
p = int(res["p"], 16)
g = int(res["g"], 16)
A = int(res["A"], 16)

r.recvuntil("Intercepted from Bob: ")
res = json_recv()

r.recvuntil("Intercepted from Alice: ")
res = json_recv()
iv = res["iv"]
ciphertext = res["encrypted"]

r.recvuntil("send him some parameters: ")
json_send({
    "p": hex(p),
    "g": hex(A),
    "A": hex(1)
    })

r.recvuntil("Bob says to you: ")
res = json_recv()
shared_secret = int(res["B"], 16)


def is_pkcs7_padded(message):
    padding = message[-message[-1]:]
    return all(padding[i] == len(padding) for i in range(0, len(padding)))

def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Decrypt flag
    ciphertext = bytes.fromhex(ciphertext)
    iv = bytes.fromhex(iv)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    plaintext = cipher.decrypt(ciphertext)

    if is_pkcs7_padded(plaintext):
        return unpad(plaintext, 16).decode('ascii')
    else:
        return plaintext.decode('ascii')

print(decrypt_flag(shared_secret, iv, ciphertext))
# crypto{n07_3ph3m3r4l_3n0u6h}

- flag: crypto{n07_3ph3m3r4l_3n0u6h}

## Static Client 2


- Chall tương tự như chall trên nhưng không thể dùng lại được cách hồi nãy
- Có một các tấn công khác là mình sẽ gửi cho Bob:

- $p'$ sao cho $p'-1$ là smooth number
- $g' = 2$
- $A' = A$

- $n$-Smooth number là số $a$ sao cho khi factor $a$, thừa số nguyên tố lớn nhất của $a$ không vượt quá $n$(Ví dụ: $8100$ là $5$-Smooth number vì $8100 = 2^{2}.3^{4}.5^{2}$)
- Việc tạo ra số nguyên tố $p'$ như vậy sẽ giúp cho việc dùng discreet log bằng thuật toán Pohlig-Hellman nhanh hơn rất nhiều
- Lưu ý là số bit của $p' \geq$ số bit của $p$

``decrypt.py``

from pwn import *
from Crypto.Util.number import *
import json


from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib
from sympy.ntheory.residue_ntheory import discrete_log


r = remote('socket.cryptohack.org', 13378)

def json_recv():
    line = r.recvline()
    return json.loads(line.decode())

def json_send(hsh):
    request = json.dumps(hsh).encode()
    r.sendline(request)

def smooth_p():
    mul = 1
    i = 1
    while 1:
        mul *= i
        if (mul + 1).bit_length() >= p.bit_length() and isPrime(mul + 1):
            return mul + 1
        i += 1

r.recvuntil("Intercepted from Alice: ")
res = json_recv()
p = int(res["p"], 16)
g = int(res["g"], 16)
A = int(res["A"], 16)

r.recvuntil("Intercepted from Bob: ")
res = json_recv()
B = int(res["B"], 16)

r.recvuntil("Intercepted from Alice: ")
res = json_recv()
iv = res["iv"]
ciphertext = res["encrypted"]

s_p = smooth_p()
print(s_p.bit_length())

r.recvuntil("send him some parameters: ")
json_send({
    "p": hex(s_p),
    "g": hex(2),
    "A": hex(A)
    })


r.recvuntil("Bob says to you: ")
res = json_recv()
B = int(res["B"], 16)
b = discrete_log(s_p, B, 2)

shared_secret = pow(A, b, p)


def is_pkcs7_padded(message):
    padding = message[-message[-1]:]
    return all(padding[i] == len(padding) for i in range(0, len(padding)))

def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Decrypt flag
    ciphertext = bytes.fromhex(ciphertext)
    iv = bytes.fromhex(iv)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    plaintext = cipher.decrypt(ciphertext)

    if is_pkcs7_padded(plaintext):
        return unpad(plaintext, 16).decode('ascii')
    else:
        return plaintext.decode('ascii')

print(decrypt_flag(shared_secret, iv, ciphertext))

r.interactive()
# crypto{uns4f3_pr1m3_sm4ll_oRd3r}

- flag: crypto{uns4f3_pr1m3_sm4ll_oRd3r}