# A. Lý thuyết Nhóm (Abstract Algebra)
## I. Định nghĩa
- Nhóm (Group) là một khái niệm trong cấu trúc đại số bên cạnh các khái niệm khác như Tập (Sets), Vành (Rings), Trường (Fields). Cấu trúc nhóm được định nghĩa như sau:
- Cho tập G khác rỗng với phép toán `•` (có thể là `+` hoặc `*`), khi đó đại số hai ngôi `(G, •)` lập thành một nhóm nếu thỏa mãn 4 tiên đề dưới đây.
## II. Tiên đề và tính chất
### 1. Tiên đề
- *Đóng*: `a • b phải thuộc G nếu a, b thuộc G`
- *Kết hợp*: `(a • b) • c = a • (b • c) |Với mọi a, b, c thuộc G`
- *Tồn tại một và chỉ một phần tử trung hòa (phần tử đơn vị) θ thuộc G sao cho*: `x • θ = θ • x = x |Với mọi x thuộc G`
- *Với mỗi phần tử x thuộc G, tồn tại duy nhất một phần tử nghịch đảo (phần tử đối) kí hiệu là `-x` hoặc `x^-1` cũng thuộc G sao cho*: `x • (-x) = (-x) • x = θ`
- Đặc biệt, nhóm G được gọi là nhóm giao hoán (thường là nhóm Abel) nếu:
`a • b = b • a |Với mọi a, b thuộc G`
### 2. Tính chất (Hệ quả)
- Phần tử trung hòa (đơn vị) và phần tử nghịch đảo (đối) là duy nhất
- Tồn tại duy nhất một nghiệm x thuộc G thỏa mãn phương trình `x • a = b` vì có thể thực hiện phép nhân với nghịch đảo trong nhóm (có thể gọi là phép chia).
## III. Cấp trong một nhóm (Order)
- Cấp của một nhóm là số phần tử có trong nhóm đó, kí hiệu là `|G|` hoặc `ord(G)`
- Cấp của phần tử a thuộc G là số nguyên dương m nhỏ nhất thỏa `a^m = θ`, kí hiệu là `|a|` hoặc `ord(a)`. Nếu không tồn tại m thỏa mãn thì a được gọi là phần tử có cấp vô hạn.
- Cấp của nhóm và phần tử có thể hữu hạn hoặc vô hạn. Tất cả các phần tử của nhóm hữu hạn có cấp hữu hạn.
- *Định lí Lagrange*: Nếu H là nhóm con của G hữu hạn thì H cũng hữu hạn và có cấp là ước số của `|G|`
- *Định lí Cauchy*: Nếu cấp của G hữu hạn chia hết cho p nguyên tố thì tồn tại ít nhất một phần tử a thỏa `ord(a) = ord(p)`
- Hệ quả: cấp của G chia hết cho cấp của mọi phần tử a thuộc G.
- Một số tính chất:
- Nếu `ord(a) = 1` thì `a = θ`
- Nếu `ord(a) = 2` thì G là nhóm Abel
- Phần tử a và nghịch đảo (đối) của nó có cùng cấp: `ord(a) = ord(-a)`
## IV. Một số cấu trúc khác
### 1. Nhóm con (Subgroup)
- Cho nhóm G với phép toán •, tập con H của G được gọi là nhóm con nếu H và • cũng lập thành một nhóm và kí hiệu là H ≤ G.
- Khi H ≤ G hay H là nhóm con của G, phần tử trung hòa (đơn vị)`θ` của G cũng chính là phần tử trung hòa (đơn vị) của H.
### 2. Cyclic group và phần tử sinh
- Xét nhóm G với phép toán •, ta kí hiệu phép lũy thừa với ý nghĩa như sau:
```
a^0 = e (e là phần tử đơn vị)
a^1 = a
a^2 = a • a
a^3 = a • a • a
a^-2 = a^-1 • a^-1
...
```
- Khi đó, G là một cyclic group nếu tồn tại `g` thuộc G sao cho với mỗi `a` thuộc G, `a = g^k` với một số nguyên `k` nào đó. g được gọi là phần tử sinh của nhóm G và G có dạng:
```
..., g^-3, g^-2, g^-1, g^0 (=e), g^1, g^2, g^3,...
```
- Ví dụ, (Z, +) là một cyclic group với `g = 1`, Z có dạng:
```
..., 1+(-1)+(-1), 1+(-1), 1, 1+1,...
```
- Cũng chính vì tính chất trên, mọi cyclic group đều là nhóm giao hoán (nhóm Abel).
### 3. Nửa nhóm và vị nhóm (Semigroup and Monoid)
- Nếu tập G chỉ thỏa mãn:
- Tính đóng
- Tính kết hợp
thì G là một nửa nhóm (Semigroup).
- Nếu nửa nhóm G tồn tại phần tử trung hòa thì G là một vị nhóm.
- Tương tự như nhóm, nếu thỏa mãn tính giao hoán thì G trở thành nửa nhóm giao hoán hoặc vị nhóm giao hoán.
### 4. Note:
---
# B. DIFFIE-HELLMAN CRYPTOHACK
## I. STARTER
### 1. Diffie-Hellman Starter 1
#### Description (*Translated*)
- Một tập hợp các số nguyên mod `n` được trang bị hai phép toán `+` và `*` là một vành (chính xác hơn là vành modulo `n`) có tính đóng.
- Khi `n` là một số nguyên tố, vành đảm bảo tính tồn tại của phần tử nghịch đảo và trở thành một trường hữu hạn gọi là `Fp`.
- Hệ mật Diffie-Hellman được thực hiện trên trường hữu hạn `Fp` này và `n` thường là một số nguyên rất lớn.
- Cho `p = 991` và phần tử `g = 209`, tìm phần tử nghịch đảo `d` thỏa `g * d mod 991 = 1`
#### Solution
- Việc tìm `d` tương tự như tìm `trapdoor` trong hệ mật RSA và mình có được `d = pow(g, -1, 991)`
#### Flag
> ~~`569`~~
---
### 2. Diffie-Hellman Starter 2
#### Description (*Translated*)
- Các phần tử của trường hữu hạn `Fp` đều có thể lập thành nhóm con `H` bằng việc thực hiện phép nhân, ví dụ với phần tử `g` thì H = {g, g^2, g^3, ...}
- Một primitive element (mình cũng không biết dịch là gì) của `Fp` là một phần tử có nhóm con `H = Fp` sao cho mọi phần tử của `Fp` đều có thể được viết dưới dạng `g^n mod p` với `n` nguyên nào đó. Chính vì thế mà primitive element đôi khi cũng được gọi là phần tử sinh của trường hữu hạn.
- Cho trường hữu hạn với `p = 28151`, tìm phần tử sinh `g` nhỏ nhất.
#### Solution
- Nói dài dòng văn tự như trên thôi nhưng thực ra phần tử sinh `g` của `Fp`thỏa mãn tính chất sau:
`g^1 != g^2 != g^3 != ... != g^(p-1) (mod p)`
- Mục tiêu chính của mình là tránh việc sinh ra một cyclic subgroup:
- Ví dụ: 2 là phần tử sinh của F3 vì
```
2^1 mod 3 = 2 mod 3 = 2
2^2 mod 3 = 4 mod 3 = 4
```
- Nhưng 2 không là phần tử sinh của F7 vì:
```
2^1 mod 7 = 2 mod 7 = 2
2^2 mod 7 = 4 mod 7 = 4
2^3 mod 7 = 8 mod 7 = 1
2^4 mod 7 = 16 mod 7 = 2
2^5 mod 7 = 32 mod 7 = 4
2^6 mod 7 = 64 mod 7 = 1
```
- Như đã thấy, 2 không là phần tử sinh của F7 do tạo thành cyclic subgroup {2, 4, 1} có xuất hiện phần tử 2 là chính nó.
- Chính vì vậy, mình sẽ brute force bài này theo tính chất nói trên :see_no_evil:. Code:
```python=
p = 28151
def check(g, p):
for i in range(2, p):
if pow(g, i, p) == g: return False
return True
for g in range(p):
if check(g, p):
print(g)
break
```
#### Flag
> ~~`7`~~
#### Note
- Bài này còn có thể giải theo hai cách nữa, một là theo sage và hai là dựa vào tính chất của primitive element trong lý thuyết trường.
1. Sage:
- Code:
```python=
GF(28151).primitive_element()
```
2. Tính chất:
- Cho `p > 2` nguyên tố. Một số `a` được gọi là primitive element mod `p` khi và chỉ khi:
```
a ^ ((p-1) // q) != 1 (mod p) với các q là ước nguyên tố của p-1
```
- Code (cần sử dụng thêm cả factor.db):
```python=
from Crypto.Util.number import isPrime
p = 28151
qs = [2, 5, 563]
for q in qs:
assert isPrime(q)
assert (p-1) % q == 0
def check(a):
for q in qs:
temp = (p-1) // q
if pow(a, temp, p) == 1: return False
return True
for a in range(2, p):
if check(a):
print(a)
break
```
---
### 3. Diffie-Hellman Starter 3
#### Description (*Translated*)
- Giao thức Diffie-Hellman sử dụng logarit rời rạc, yêu cầu tính toán ở mức khó và phức tạp.
- Bước đầu tiên của giao thức là tạo một số nguyên tố `p` và một vài số sinh của trường `Fp`. Người dùng cần thực hiện bước này cẩn thận để tránh những trường hợp đặc biệt mà logarit rời rạc có thể giải dễ dàng bằng các thuật toán điển hình như [Pohlig-Hellman](https://en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm). Ví dụ, một số nguyên tố an toàn `p = 2*q + 1` thường được chọn với `q` cũng là một số nguyên tố lớn khác bởi hai ước nguyên tố duy nhất của `p-1` là `{2, q}` làm việc áp dụng thuật toán logarit rời rạc khó hơn.
- Sau đó cần chọn một số nguyên bí mật `a < p` và tính `A = g^a mod p`. Số `A` này có thể được gửi đi ngay cả trên một mạng công khai bảo mật kém bởi độ phức tạp của toán logarit rời rạc khiến cho việc tìm `a` dường như bất khả thi.
- Cho các tham số sau:
```python=
g = 2
p = 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
a = 972107443837033796245864316200458246846904598488981605856765890478853088246897345487328491037710219222038930943365848626194109830309179393018216763327572120124760140018038673999837643377590434413866611132403979547150659053897355593394492586978400044375465657296027592948349589216415363722668361328689588996541370097559090335137676411595949335857341797148926151694299575970292809805314431447043469447485957669949989090202320234337890323293401862304986599884732815
```
- Tính `g^a mod p`
#### Solution
- Code:
```python=
print(pow(g, a, p))
```
#### Flag
> ~~`1806857697840726523322586721820911358489420128129248078673933653533930681676181753849411715714173604352323556558783759252661061186320274214883104886050164368129191719707402291577330485499513522368289395359523901406138025022522412429238971591272160519144672389532393673832265070057319485399793101182682177465364396277424717543434017666343807276970864475830391776403957550678362368319776566025118492062196941451265638054400177248572271342548616103967411990437357924`~~
---
### 4. Diffie-Hellman Starter 4
#### Description
- Challenge parameters:
```python=
g = 2
p = 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
A = 70249943217595468278554541264975482909289174351516133994495821400710625291840101960595720462672604202133493023241393916394629829526272643847352371534839862030410331485087487331809285533195024369287293217083414424096866925845838641840923193480821332056735592483730921055532222505605661664236182285229504265881752580410194731633895345823963910901731715743835775619780738974844840425579683385344491015955892106904647602049559477279345982530488299847663103078045601
b = 12019233252903990344598522535774963020395770409445296724034378433497976840167805970589960962221948290951873387728102115996831454482299243226839490999713763440412177965861508773420532266484619126710566414914227560103715336696193210379850575047730388378348266180934946139100479831339835896583443691529372703954589071507717917136906770122077739814262298488662138085608736103418601750861698417340264213867753834679359191427098195887112064503104510489610448294420720
B = 518386956790041579928056815914221837599234551655144585133414727838977145777213383018096662516814302583841858901021822273505120728451788412967971809038854090670743265187138208169355155411883063541881209288967735684152473260687799664130956969450297407027926009182761627800181901721840557870828019840218548188487260441829333603432714023447029942863076979487889569452186257333512355724725941390498966546682790608125613166744820307691068563387354936732643569654017172
```
- You and Alice are now able to calculate a shared secret, which would be infeasible to calculate knowing only `{g,p,A,B}`.
- What is your shared secret?
#### Solution
- Mình có được `A = g^a (mod p)` `B = g^b (mod p)`, trong đó `A` là số mình nhận được từ Alice. Đề cho biết mình và Alice đang có thể tính được một shared secret nên secret khả thi nhất sẽ là `secret = pow(A, b, p)` hoặc `secret = pow(B, a, p)` nếu mình biết `a`
- Thực tế thì `secret = g^(a*b) (mod p)`
- Code:
```python=
print(pow(A, b, p))
```
#### Flag
> ~~`1174130740413820656533832746034841985877302086316388380165984436672307692443711310285014138545204369495478725102882673427892104539120952393788961051992901649694063179853598311473820341215879965343136351436410522850717408445802043003164658348006577408558693502220285700893404674592567626297571222027902631157072143330043118418467094237965591198440803970726604537807146703763571606861448354607502654664700390453794493176794678917352634029713320615865940720837909466`~~
#### Note
- Thực ra đây chính là giao thức DH trên lý thuyết, là phương pháp để **Trao đổi khóa** và khóa chính là shared secret ở trên. Cần nhấn mạnh DH chỉ dùng trong trao đổi khóa để thực hiện giải mã các hệ mật khác, chứ DH không dùng để gửi trực tiếp bản mã hay dùng trong chữ kí số.
- Bên cạnh đó, DH còn khá yếu với `man-in-the-middle-attack` vì không có khả năng xác thực người dùng.
---
### 5. Diffie-Hellman Starter 5
#### Description
- Alice wants to send you her secret flag and asks you to generate a shared secret with her. She also tells you she will be using the NIST standard:
```python=
g = 2
p = 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
A = 112218739139542908880564359534373424013016249772931962692237907571990334483528877513809272625610512061159061737608547288558662879685086684299624481742865016924065000555267977830144740364467977206555914781236397216033805882207640219686011643468275165718132888489024688846101943642459655423609111976363316080620471928236879737944217503462265615774774318986375878440978819238346077908864116156831874695817477772477121232820827728424890845769152726027520772901423784
b = 197395083814907028991785772714920885908249341925650951555219049411298436217190605190824934787336279228785809783531814507661385111220639329358048196339626065676869119737979175531770768861808581110311903548567424039264485661330995221907803300824165469977099494284722831845653985392791480264712091293580274947132480402319812110462641143884577706335859190668240694680261160210609506891842793868297672619625924001403035676872189455767944077542198064499486164431451944
B = 1241972460522075344783337556660700537760331108332735677863862813666578639518899293226399921252049655031563612905395145236854443334774555982204857895716383215705498970395379526698761468932147200650513626028263449605755661189525521343142979265044068409405667549241125597387173006460145379759986272191990675988873894208956851773331039747840312455221354589910726982819203421992729738296452820365553759182547255998984882158393688119629609067647494762616719047466973581
```
- Individually you each use the shared secret to derive an AES private key. This allows you to encrypt large amounts of data over your channel without needing to exchange keys again.
- Alice sends you the following IV and ciphertext:
```python=
iv = '737561146ff8194f45290f5766ed6aba'
encrypted_flag = '39c99bf2f0c14678d6a5416faef954b5893c316fc3c48622ba1fd6a9fe85f3dc72a29c394cf4bc8aff6a7b21cae8e12c'
```
- Decrypt this to obtain your flag!
- Challenge code:
```python=
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))
```
#### Solution
- Bài khá đơn giản khi mình chỉ cần điền giá trị cho các biến có trong file `decrypt.py`, trong đó `ciphertext` là `encrypted_flag` và `shared_secret` là khóa mã hóa theo giao thức DH. Làm tương tự bài trên thui :smile_cat:
- Code:
```python=
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 = 197395083814907028991785772714920885908249341925650951555219049411298436217190605190824934787336279228785809783531814507661385111220639329358048196339626065676869119737979175531770768861808581110311903548567424039264485661330995221907803300824165469977099494284722831845653985392791480264712091293580274947132480402319812110462641143884577706335859190668240694680261160210609506891842793868297672619625924001403035676872189455767944077542198064499486164431451944
B = 1241972460522075344783337556660700537760331108332735677863862813666578639518899293226399921252049655031563612905395145236854443334774555982204857895716383215705498970395379526698761468932147200650513626028263449605755661189525521343142979265044068409405667549241125597387173006460145379759986272191990675988873894208956851773331039747840312455221354589910726982819203421992729738296452820365553759182547255998984882158393688119629609067647494762616719047466973581
shared_secret = pow(A, b, p)
iv = '737561146ff8194f45290f5766ed6aba'
ciphertext = '39c99bf2f0c14678d6a5416faef954b5893c316fc3c48622ba1fd6a9fe85f3dc72a29c394cf4bc8aff6a7b21cae8e12c'
print(decrypt_flag(shared_secret, iv, ciphertext))
```
#### Flag
> ~~`crypto{sh4r1ng_s3cret5_w1th_fr13nd5}`~~
---
## II. MAN IN THE MIDDLE
### 6. Parameter Injection
#### Description
- You're in a position to not only intercept Alice and Bob's DH key exchange, but also rewrite their messages. Think about how you can play with the DH equation that they calculate, and therefore sidestep the need to crack any discrete logarithm problem.
- Use the script from "Diffie-Hellman Starter 5" to decrypt the flag once you've recovered the shared secret.
- Connect at `socket.cryptohack.org 13371`
#### Solution
- Quy trình trong bài như sau:
```=
In from Alice: p, g, A
Send to Bob: fake_p, fake_g, fake_A
In from Bob: B
Send to Alice: fake_B
In from Alice: iv, encrypted_flag
```
- Trong đó, mình cần lấy được `iv`, `encrypted_flag` và `key`. Mình sẽ thực hiện `man-in-the-middle attack` ở đây. Biết rằng Alice sẽ tính `key = pow(fake_B, a, p)` nên mình sẽ tìm cách để `key` là một số mình biết trước. Mình sẽ chọn `fake_B = 1` để `key = 1`, khi đó chỉ cần lấy `iv` và `encrypted_flag` đi giải mã là xong.
- Code:
```python=
from pwn import *
from json import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
import hashlib
HOST = 'socket.cryptohack.org'
PORT = 13371
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')
def send(msg):
return r.sendline(dumps(msg))
r = remote(HOST, PORT)
r.recvuntil(b'Intercepted from Alice: ')
get = loads(r.recvuntil(b'}'))
r.recvuntil(b'Send to Bob: ')
send(get)
r.recvuntil(b'Send to Alice: ')
send({'B': hex(1)})
r.recvuntil(b'Intercepted from Alice: ')
get = loads(r.recvuntil(b'}'))
iv = get['iv']
encrypted_flag = get['encrypted_flag']
key = 1
print(decrypt_flag(key, iv, encrypted_flag))
```
#### Flag
> ~~`crypto{n1c3_0n3_m4ll0ry!!!!!!!!}`~~
#### Note
- Mình cũng đã từng thử chọn `fake_g` và `fake_p` để loại bỏ đi phép modulo kia nhưng không khả thi lắm. Having tried with `fake_g = 10` and `fake_p = 10**700` but it is impossible :crying_cat_face:
---
### 7. Export-grade
#### Description
- Alice and Bob are using legacy codebases and need to negotiate parameters they both support. You've man-in-the-middled this negotiation step, and can passively observe thereafter. How are you going to ruin their day this time?
- Connect at `socket.cryptohack.org 13379`
#### Solution
- Tiếp tục là `man-in-the-middle`
- Ban đầu vào thì Alice và Bob sẽ thống nhất với nhau về giao thức DH thích hợp, vì DH64 là giao thức với `key` 64 bit kém bảo mật nên mình sẽ lựa chọn để tấn công. Sau một loạt các trao đổi thì mình có được các tham số sau: `{p, g, A, B, iv, encrypted_flag}` và nhiệm vụ là giải mã `encrypted_flag` bằng `key` 64 bit.
- Code lấy các tham số:
```python=
from pwn import *
from json import *
HOST = 'socket.cryptohack.org'
PORT = 13379
def send(msg):
return r.sendline(dumps(msg).encode())
def cvrt(hex):
return int(hex, 16)
r = remote(HOST, PORT)
r.recvuntil(b'Send to Bob: ')
send({"supported": ["DH64"]})
r.recvuntil(b'Send to Alice: ')
send({"chosen": "DH64"})
r.recvuntil(b'Intercepted from Alice: ')
get = loads(r.recvuntil(b'}'))
p, g, A = get['p'], get['g'], get['A']
r.recvuntil(b'Intercepted from Bob: ')
B = loads(r.recvuntil(b'}'))['B']
r.recvuntil(b'Intercepted from Alice: ')
get = loads(r.recvuntil(b'}'))
iv, encrypted_flag = get['iv'], get['encrypted_flag']
p, g, A, B, iv, encrypted_flag = cvrt(p), cvrt(g), cvrt(A), cvrt(B), cvrt(iv), cvrt(encrypted_flag)
print(f'{p = }')
print(f'{g = }')
print(f'{A = }')
print(f'{B = }')
print(f'{iv = }')
print(f'{encrypted_flag = }')
```
- Để tìm được `key`, mình cần biết được `a` hoặc `b` vì `A = pow(g, a, p)` và `B = pow(g, b, p)`. Cái này liên quan đến logarit rời rạc nên mình sẽ thực hiện trên sage (có thể sử dụng tool online)
- Giả sử một trường hợp mình bắt được:
```python=
p = 16007670376277647657
g = 2
A = 9989801226209336220
B = 14534189480232724354
iv = 38571510066310834468440389169008255603
encrypted_flag = 56801805763315812000647527321092706170023633891652995062990491131977722679933
```
- Code sage:
```python=
sage: p = 16007670376277647657
....: g = 2
....: A = 9989801226209336220
....: B = 14534189480232724354
....: iv = 38571510066310834468440389169008255603
....: encrypted_flag = 568018057633158120006475273210927
....: 06170023633891652995062990491131977722679933
sage: A = Mod(A, p)
sage: g = Mod(g, p)
sage: a = discrete_log(A, g)
sage: a
3996205933053804434
```
- Vậy là xong, giờ mình thực hiện như bài trước là lấy được flag thui :smiley_cat:
- Code:
```python=
from Crypto.Cipher import AES
from Crypto.Util.Padding import 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')
p = 16007670376277647657
g = 2
A = 9989801226209336220
B = 14534189480232724354
iv = 38571510066310834468440389169008255603
encrypted_flag = 56801805763315812000647527321092706170023633891652995062990491131977722679933
a = 3996205933053804434
assert A == pow(g, a, p)
shared_secret = pow(B, a, p)
s, i, e = shared_secret, hex(iv)[2:], hex(encrypted_flag)[2:]
print(decrypt_flag(s, i, e))
```
#### Flag
> ~~`crypto{d0wn6r4d35_4r3_d4n63r0u5}`~~
#### Note
- Thực ra độ khó bài này không cao, phức tạp chỉ nằm ở việc tìm logarit rời rạc nhưng may thay mình có sage để hỗ trợ :smile_cat:
---
### 8. Static Client
#### Description
- You've just finished eavesdropping on a conversation between Alice and Bob. Now you have a chance to talk to Bob. What are you going to say?
- Connect at `socket.cryptohack.org 13373`
#### Solution
- Sau khi `nc socket.cryptohack.org 13373`, mình có được các tham số `{p, g, A, B, iv_A, encrypted_A}`, tiếp tục gửi các tham số `{fake_p, fake_g, fake_A}` cho Bob thì mình nhận được `{fake_B, iv_B, encrypted_B}`
- Mình sẽ thử đọc tin nhắn của Bob bằng cách thay đổi `fake_g = 1` và `fake_p = 2` để `fake_key = 1` cho dễ giải. Code:
```python=
from pwn import *
from json import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
import hashlib
HOST = 'socket.cryptohack.org'
PORT = 13373
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')
def send(msg):
return r.sendline(dumps(msg).encode())
r = remote(HOST, PORT)
r.recvuntil(b'Intercepted from Alice: ')
get = loads(r.recvuntil(b'}'))
p, g, A = get['p'], get['g'], get['A']
r.recvuntil(b'Intercepted from Bob: ')
get = loads(r.recvuntil(b'}'))
B = get['B']
r.recvuntil(b'Intercepted from Alice: ')
get = loads(r.recvuntil(b'}'))
iv_A, encrypted_A = get['iv'], get['encrypted']
r.recvuntil(b'Bob connects to you, send him some parameters: ')
fake_g = 1
fake_p = 2
fake = {
'g': hex(fake_g),
'p': hex(fake_p),
'A': A
}
send(fake)
r.recvuntil(b'}')
r.recvuntil(b'Bob says to you: ')
get = loads(r.recvuntil(b'}'))
iv_B, encrypted_B = get['iv'], get['encrypted']
shared_secret = 1
print(decrypt_flag(shared_secret, iv_B, encrypted_B))
```
- Nhận được `Hey, what's up. I got bored generating random numbers did you see?`. Well, vậy là flag do Alice giữ và mình cần tìm lại `key` để giải `encrypted_A` :crying_cat_face:. Ý tưởng ban đầu của mình ngay sau khi nc là gửi lại chính `A` và `p` cho Bob nhưng chưa biết flag do ai giữ nên làm cách trên, giờ sẽ thử phân tích xem sao:
```
Ta có:
key = A ^ b (mod p)
Bob tính:
fake_B = fake_g ^ b (mod fake_p)
```
- Từ trên mình chắc chắn rằng nếu gửi `fake_g = A` và `fake_p = p` thì Bob sẽ trả về cho mình `fake_B = key` và mình có thể vác `key` này đi giải rồi :smile_cat:. Code:
```python=
from pwn import *
from json import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
import hashlib
HOST = 'socket.cryptohack.org'
PORT = 13373
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')
def send(msg):
return r.sendline(dumps(msg).encode())
r = remote(HOST, PORT)
r.recvuntil(b'Intercepted from Alice: ')
get = loads(r.recvuntil(b'}'))
p, g, A = get['p'], get['g'], get['A']
r.recvuntil(b'Intercepted from Alice: ')
get = loads(r.recvuntil(b'}'))
iv_A, encrypted_A = get['iv'], get['encrypted']
r.recvuntil(b'Bob connects to you, send him some parameters: ')
fake = {
'p': p,
'g': A,
'A': '0x0'
}
send(fake)
r.recvuntil(b'Bob says to you: ')
fake_B = loads(r.recvuntil(b'}'))['B']
shared_secret = int(fake_B, 16)
print(decrypt_flag(shared_secret, iv_A, encrypted_A))
```
#### Flag
> ~~`crypto{n07_3ph3m3r4l_3n0u6h}`~~
#### Note
- Bài này cũng khá hay và flag cũng gần như tựa đề vậy :penguin:, `not ephemeral ~ static`
---
## III. GROUP THEORY
### 9. Additive
#### Description
- Alice and Bob decided to do their DHKE in an additive group rather than a multiplicative group. What could go wrong?
- Use the script from "Diffie-Hellman Starter 5" to decrypt the flag once you've recovered the shared secret.
- Connect at `socket.cryptohack.org 13380`
#### Solution
- Mình đã biết được giao thức DH thực hiện trong nhóm nhân `(G, *)` tạo phép lũy thừa và có được các phép toán sau:
```
A = g^a (mod p)
B = g^b (mod p)
key = B^a = A^b = g^(a*b) (mod p)
```
- Nên nếu thực hiện giao thức DH trong nhóm cộng `(G, +)` thì phép lũy thừa sẽ chuyển thành phép nhân và được các hệ quả:
```
A = g*a (mod p)
B = g*b (mod p)
key = A*b = B*a = g*a*b (mod p)
```
- Mình có thể dễ dàng tính được `a`, `b` bằng cách tìm phần tử nghịch đảo `inverse` trong trường mod p rồi từ đó suy ra `key` thui :smile_cat:, công thức như sau:
```
g*a = A (mod p) --> g = A*inverse(g) (mod p)
g*b = B (mod p) --> g = B*inverse(g) (mod p)
```
- Code:
```python=
from pwn import *
from json import *
from Crypto.Util.number import inverse
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
import hashlib
HOST = 'socket.cryptohack.org'
PORT = 13380
def cvrt(hex):
return int(hex, 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')
r = remote(HOST, PORT)
r.recvuntil(b'Intercepted from Alice: ')
get = loads(r.recvuntil(b'}'))
p, g, A = get['p'], get['g'], get['A']
r.recvuntil(b'Intercepted from Bob: ')
get = loads(r.recvuntil(b'}'))
B = get['B']
r.recvuntil(b'Intercepted from Alice: ')
get = loads(r.recvuntil(b'}'))
iv, encrypted = get['iv'], get['encrypted']
p, g, A, B = cvrt(p), cvrt(g), cvrt(A), cvrt(B)
a = A * inverse(g, p)
b = B * inverse(g, p)
assert (g*a*b)%p == (B*a)%p == (A*b)%p # thêm assert cho ngầu
key = (g*a*b)%p
print(decrypt_flag(key, iv, encrypted))
```
#### Flag
> ~~`crypto{cycl1c_6r0up_und3r_4dd1710n?}`~~
---
### 10. Static Client 2
#### Description
- Bob got a bit more careful with the way he verifies parameters. He's still insisting on using the p and g values provided by his partner. Wonder if he missed anything?
- Connect at `socket.cryptohack.org 13378`
#### Solution
- Về server thì sau khi nc xong quy trình cũng tương tự, nhưng theo desc, mình biết được rằng Bob vẫn sử dụng `p` và `g` do mình cung cấp nhưng sẽ check cả 3 tham số `p`, `g`, `A`. Sau khi mình thử thì:
- `g` = `g`
- `p-1 > A > 2`
- `p` cần phải mạnh, mình không hiểu mạnh ở đây nghĩa là gì lắm nhưng chắc nó là safe prime ở bài `Diffie-Hellman Starter 3`
- Một điều nữa, nếu vẫn sử dụng `p` và `g` như trên, Bob không làm thay đổi `B` vì `B = g^b (mod p)`. Mình đã thử factor số `p-1` và nhận ra nó có duy nhất 2 ước là
```python=!
{2, 1205156213460516294276038011098783037428475274251229971327058470979054415841306114445046929130670807336613570738952006098251824478525291315971365353402504611531367372670536703348123007294680829887020513584624726600189364717085162921889329599071881596888429934762044470097788673059921772650773521873603874984881875042154463169647779984441228936206496905064565147296499973963182632029642323604865192473605840717232357219244260470063729922144429668263448160459816959}
```
- Như đã nói ở [trên](https://hackmd.io/1ZSPW3h-QOK8EeSMlY8RwA?view#3-Diffie-Hellman-Starter-3), việc chọn safe primes có thể làm cho [thuật toán](https://en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm) khó áp dụng hơn (nhưng không có nghĩa là không dùng được).
- Thực tế thì khi giải `x` trong phương trình `g^x = h (mod p)`, ý tưởng của Pohlig-Hellman là giải logarit rời rạc trên nhóm mà phần tử có cấp nhỏ hơn rồi kết hợp các kết quả để tìm `x` - [Reference](https://crypto.stackexchange.com/questions/52724/pohlig-hellman-algorithm). Cũng chính vì thế, nếu số `p` thỏa `p-1` là một smooth number thì thuật toán sẽ thực hiện nhanh hơn - [Reference](https://www.youtube.com/watch?v=B0p0jbCGvWk).
- Smooth number: Trong lý thuyết số, một số `n` được gọi là n-smooth number khi không có ước nguyên tố nào của `n` lớn hơn nó (định nghĩa wiki) nhưng mình nghĩ nó không quan trọng lắm :penguin:. Trong bài này tạm coi số `p` là smooth number khi mà các ước nguyên tố của nó rất nhỏ so với `p-1`.
- Mình được phép thay đổi `p` trong tin nhắn gửi cho Bob và mình sẽ chọn `p'` thỏa hai điều kiện:
- `p'` là safe prime: `p' = 2*q + 1` với `q` là một số nguyên tố khác (nhưng mình cũng không cần quan tâm nó là nguyên tố hay không vì số gen dưới đây cũng được Bob accept :monkey:)
- `p'-1` là p'-smooth number
- Code để gen ra số `p'`, mình tạm chọn `p' > p` cho đủ mạnh:
```python=
def find(p):
res = 1
i = 2
while res < p or not isPrime(res+1):
res *= i
i += 1
res += 1
return res
# How fuck số to vch
# 21161033472192524829557170410776298658794639108376130676557783015578090330844472167861788371083170940722591241807108382859295872641348645166391260040395583908986502774347856154314632614857393087562331369896964916313777278292965202780626304839725254323083321245935920345445760469315716688808181386083935737705284353395869520861742156127496385090743602309049820934917134755461873012945704938955132724663075880436995904093654709349552656965610546540372048421026608925808493978164019986593442564905462745669412326023291812269608558332157759989142549649265359278848084868920655698461242425344000000000000000000000000000000000000000000000000000000000000000000000000000001
```
- Có được số `p'` rùi, bên cạnh đó mình biết `B = g ^ b (mod p')` nên áp dụng discrete log tìm `b` là oke:
```python=
from sympy.ntheory.residue_ntheory import discrete_log
b = discrete_log(fake_p, int(B, 16), int(g, 16))
print(b)
# 1919572943691512325783103720167834163677411292709378502535498859989993544026380143919501049584589675317643993465536543895780854808442293000014297210200227069779643763121704810281976733978781152126062646602812482025293137787739116693980988513420732289020477701182639042794562638875881378349771734410919106042203493166198706573467903966100368713572415175654342828296086659529676015616513470105470901979846373335352656586302787870238998914215908919919219987614105175
```
- Có vẻ `b` cũng không thay đổi, giờ mình lấy lại flag thôi:
```python=
from pwn import *
from json import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
import hashlib
HOST = 'socket.cryptohack.org'
PORT = 13378
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')
def send(msg):
return r.sendline(dumps(msg).encode())
r = remote(HOST, PORT)
r.recvuntil(b'Intercepted from Alice: ')
get = loads(r.recvuntil(b'}'))
p, g, A = get['p'], get['g'], get['A']
r.recvuntil(b'Intercepted from Bob: ')
get = loads(r.recvuntil(b'}'))
B = get['B']
r.recvuntil(b'Intercepted from Alice: ')
get = loads(r.recvuntil(b'}'))
iv_A, encrypted_A = get['iv'], get['encrypted']
r.recvuntil(b'Bob connects to you, send him some parameters: ')
fake_p = 21161033472192524829557170410776298658794639108376130676557783015578090330844472167861788371083170940722591241807108382859295872641348645166391260040395583908986502774347856154314632614857393087562331369896964916313777278292965202780626304839725254323083321245935920345445760469315716688808181386083935737705284353395869520861742156127496385090743602309049820934917134755461873012945704938955132724663075880436995904093654709349552656965610546540372048421026608925808493978164019986593442564905462745669412326023291812269608558332157759989142549649265359278848084868920655698461242425344000000000000000000000000000000000000000000000000000000000000000000000000000001
fake = {
'g': g,
'p': hex(fake_p),
'A': A
}
send(fake)
r.recvuntil(b'Bob says to you: ')
B = loads(r.recvuntil(b'}'))['B']
r.recvuntil(b'Bob says to you: ')
get = loads(r.recvuntil(b'}'))
iv_B, encrypted_B = get['iv'], get['encrypted']
r.close()
b = 1919572943691512325783103720167834163677411292709378502535498859989993544026380143919501049584589675317643993465536543895780854808442293000014297210200227069779643763121704810281976733978781152126062646602812482025293137787739116693980988513420732289020477701182639042794562638875881378349771734410919106042203493166198706573467903966100368713572415175654342828296086659529676015616513470105470901979846373335352656586302787870238998914215908919919219987614105175
A, p = int(A, 16), int(p, 16)
shared_secret = pow(A, b, p)
print(decrypt_flag(shared_secret, iv_A, encrypted_A))
```
#### Flag
> ~~`crypto{uns4f3_pr1m3_sm4ll_oRd3r}`~~
#### Note
- Bài có đi osint và học code từ nguồn khác :penguin:
---
## IV. MISC
### 11. Script Kiddie
#### Description
- Found this cool script on Github and I've been using it to keep my secrets from anyone listening in on the school wifi!
- Challeng code:
```python=
from Crypto.Cipher import AES
import hashlib
import secrets
def header():
print(""" _____ _ __ __ _
| __ \(_)/ _|/ _(_)
| | | |_| |_| |_ _ ___
| | | | | _| _| |/ _ \
| |__| | | | | | | | __/
|_____/|_|_| |_| |_|\___|
| | | | | | |
| |__| | ___| | |_ __ ___ __ _ _ __
| __ |/ _ \ | | '_ ` _ \ / _` | '_ \
| | | | __/ | | | | | | | (_| | | | |
|_| |_|\___|_|_|_| |_| |_|\__,_|_| |_|
""")
def is_pkcs7_padded(message):
padding = message[-message[-1]:]
return all(padding[i] == len(padding) for i in range(0, len(padding)))
def pkcs7_unpad(message, block_size=16):
if len(message) == 0:
raise Exception("The input data must contain at least one byte")
if not is_pkcs7_padded(message):
return message
padding_len = message[-1]
return message[:-padding_len]
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)
return pkcs7_unpad(plaintext).decode('ascii')
def generate_public_int(g, a, p):
return g ^ a % p
def generate_shared_secret(A, b, p):
return A ^ b % p
def goodbye():
print('Goodbye!')
def main():
header()
print('[-] Collecting data from Alice')
p = int(input('> p: '))
q = (p - 1) // 2
g = int(input('> g: '))
A = int(input('> A: '))
print('[+] All data collected from Alice')
print('[+] Generating public integer for alice')
b = secrets.randbelow(q)
B = generate_public_int(g, b, p)
print(f'[+] Please send the public integer to Alice: {B}')
print('')
input('[+] Press any key to continue')
print('')
print('[+] Generating shared secret')
shared_secret = generate_shared_secret(A, b, p)
query = input('Would you like to decrypt a message? (y/n)\n')
if query == 'y':
iv = input('[-] Please enter iv (hex string)\n')
ciphertext = input('[-] Please enter ciphertext (hex string)\n')
flag = decrypt_flag(shared_secret, iv, ciphertext)
print(f'[+] Flag recovered: {flag}')
goodbye()
else:
goodbye()
if __name__ == '__main__':
main()
```
- Challenge output:
```python=
p: 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
g: 2
A: 539556019868756019035615487062583764545019803793635712947528463889304486869497162061335997527971977050049337464152478479265992127749780103259420400564906895897077512359628760656227084039215210033374611483959802841868892445902197049235745933150328311259162433075155095844532813412268773066318780724878693701177217733659861396010057464019948199892231790191103752209797118863201066964703008895947360077614198735382678809731252084194135812256359294228383696551949882
B: 652888676809466256406904653886313023288609075262748718135045355786028783611182379919130347165201199876762400523413029908630805888567578414109983228590188758171259420566830374793540891937904402387134765200478072915215871011267065310188328883039327167068295517693269989835771255162641401501080811953709743259493453369152994501213224841052509818015422338794357540968552645357127943400146625902468838113443484208599332251406190345653880206706388377388164982846343351
iv: 'c044059ae57b61821a9090fbdefc63c5'
encrypted_flag: 'f60522a95bde87a9ff00dc2c3d99177019f625f3364188c1058183004506bf96541cf241dad1c0e92535564e537322d7'
```
#### Solution
- Đọc script một chút, đầu tiên "server" sẽ nhận vào các tham số `{p, g, A}`. Tiếp đến "server" sẽ gen `{b, B, key}` với `b thuộc [0, (p-1)/2)`, `B = (g xor b) % p` và `key = (A xor b) % p` rồi trả về `B`. Sau khi xác nhận chúng ta muốn decrypt hay không thì "server" sẽ nhận vào `{iv, ciphertext}` và trả về `plaintext`
- Đối với output mình nhận được, mình cần tìm lại `key` để giải mã. Vì code thực hiện phép xor có tính giao hoán nên mình thử:
```python=
b = (g ^ B) % p
key = (A ^ b) % p
Trial: key = g ^ A ^ B
```
- Và thử đem đi giải flag:
```python=
from Crypto.Cipher import AES
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 pkcs7_unpad(message, block_size=16):
if len(message) == 0:
raise Exception("The input data must contain at least one byte")
if not is_pkcs7_padded(message):
return message
padding_len = message[-1]
return message[:-padding_len]
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)
return pkcs7_unpad(plaintext).decode('ascii')
p = 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
g = 2
A = 539556019868756019035615487062583764545019803793635712947528463889304486869497162061335997527971977050049337464152478479265992127749780103259420400564906895897077512359628760656227084039215210033374611483959802841868892445902197049235745933150328311259162433075155095844532813412268773066318780724878693701177217733659861396010057464019948199892231790191103752209797118863201066964703008895947360077614198735382678809731252084194135812256359294228383696551949882
B = 652888676809466256406904653886313023288609075262748718135045355786028783611182379919130347165201199876762400523413029908630805888567578414109983228590188758171259420566830374793540891937904402387134765200478072915215871011267065310188328883039327167068295517693269989835771255162641401501080811953709743259493453369152994501213224841052509818015422338794357540968552645357127943400146625902468838113443484208599332251406190345653880206706388377388164982846343351
iv = 'c044059ae57b61821a9090fbdefc63c5'
encrypted_flag = 'f60522a95bde87a9ff00dc2c3d99177019f625f3364188c1058183004506bf96541cf241dad1c0e92535564e537322d7'
key = g ^ A ^ B
print(decrypt_flag(key, iv, encrypted_flag))
```
#### Flag
> ~~`crypto{b3_c4r3ful_w1th_y0ur_n0tati0n}`~~
#### Note
- Làm xong kiểu wtf ủa sao vậy thì mình mới nhận ra ngay từ đầu phép `mod p` kia đã vô dụng rồi. Nếu thử `print(g^p < p)` sẽ nhận được `True`, điều này chứng tỏ `g^p mod p = g^p` và từ đó tính giao hoán có tác dụng. Điều này cũng đúng với cả `g^A^B`. Một bài khá troll :money_mouth_face:
---
### 12. The Matrix
#### Description
- I must get out of here. I must get free, and in this mind is the key, my key!
- Challenge code:
```python=
import random
P = 2
N = 50
E = 31337
FLAG = b'crypto{??????????????????????????}'
def bytes_to_binary(s):
bin_str = ''.join(format(b, '08b') for b in s)
bits = [int(c) for c in bin_str]
return bits
def generate_mat():
while True:
msg = bytes_to_binary(FLAG)
msg += [random.randint(0, 1) for _ in range(N*N - len(msg))]
rows = [msg[i::N] for i in range(N)]
mat = Matrix(GF(2), rows)
if mat.determinant() != 0 and mat.multiplicative_order() > 10^12:
return mat
def load_matrix(fname):
data = open(fname, 'r').read().strip()
rows = [list(map(int, row)) for row in data.splitlines()]
return Matrix(GF(P), rows)
def save_matrix(M, fname):
open(fname, 'w').write('\n'.join(''.join(str(x) for x in row) for row in M))
mat = generate_mat()
ciphertext = mat^E
save_matrix(ciphertext, 'flag.enc')
```
- Challenge output:
```python=
00000001111101100001101010010001001011000110001001
10111010010100110001011011111110011000001001000001
01011101000110110101010100100100111110110110011111
11101100011011010001111011011000100010110001001010
11111111101001010101001011111101010010011010101001
10010011101000000010000110100101111011110011101110
00011100010011010110000000001011000111010101001011
01001111000110100111110011000101011110010111111110
01111001110011000100000110010101011111010000000011
11001101010111111011110110101010001101001001111101
01100111000100010101000001011011001101001110101000
00010001001011101111100010101101011000101100010111
01101100101101011101101000110001011111111010000100
00001110111111000111111100011110000101100100000011
10001001111111011000111011111010110111111111000110
01111101100011110110111000011110000100111001110100
11111100110101111001111000110100011010111011110001
00100011011100101010111011111100000010000101111111
01111001110100011111011100100011011010010011111000
01011011101011111111101011011011000111110011111010
00010100110111110011111100111101100000001101110111
10011011011101110101100110110000011101000010101011
01111000001111011011111000100010010010010111101001
00100000010001110000001101111100011111110011011000
10010101101011011111101111101000111010010011111001
10011011000111000001010111011000000000100111100011
11001001010001111111000011011011101001101010001000
00100100000101110010001001011001111011001110100001
00000101000101100111010111101010001101111110011001
00101000011010100110100111111110000101011001011110
11011001001111111010000001100111011101101100110110
00111000011011011111111011110001001101001101101100
11110010101001100110000110110000100000101010101011
00101001000011001110110111100010010011100101001000
11000100010010111110110010100110110110101000110110
01101011000111001111011110000110001011111000011100
11010011001111111110100101100011000000000011110001
10000011000101100011000110111111011010110111101000
11000011000100010001001011010011010000001101100011
11011001111001010100010101001100001010101100010010
10110101010111111010110001111111100100110001001100
11101001100110001001001100000011100101001010011010
10000011100110001101010110010010100001010011011101
10001110111111100110011000010000011011011111011001
00011100011111110101011100111000110010100011000010
00111111010010111100100101100001001011110101111100
10000100101101000011011010100100011111100101101111
00011101110001001010111001111011111110110011011001
11111100110101111100110001011001000001111100110011
00110010110110011001001111110110000011001111010110
```
#### Solution
- Trước tiên mình sẽ thử phân tích thuật toán mã hóa của bài. Cho
```python=
P = 2
N = 50
E = 31337
```
với `N` là cỡ của ma trận, nói cách khác ma trận của bài có cỡ 50x50. Ma trận đã cho sẽ được đặt trong trường `Fp` với `P = 2`, gần giống với kết quả của phép XOR:
```
Trong F2 thì:
1 + 1 = 0
1 + 0 = 1
0 + 0 = 0
0 + 1 = 1
```
- Quy trình mã hóa như sau. Đầu tiên `flag` sẽ được chuyển thành một ma trận nhị phân `mat`. Nếu độ dài của `flag` không lớn hơn cỡ 50x50 thì `mat` sẽ được đệm thêm các số 0, 1 ngẫu nhiên vào cuối. Sau đó bằng một code lằng nhằng thì `mat` trở thành ma trận chuyển vị của chính nó.
Sign in with Wallet
Connect another wallet