# EzRSA
**Source**
```python=
import base64
import hashlib
from Crypto.PublicKey import RSA
from Crypto.Util.number import *
import random
FLAG = "KMACTF{s0m3_r3ad4ble_5tr1ng_like_7his}"
def verifySignature(public_key, msg: bytes, sig_bytes: bytes, key_size: int, prefix: bytes, namePrefix):
HASH_FUNC = {
'MD5': hashlib.md5(msg).digest(),
'SHA-1': hashlib.sha1(msg).digest(),
'SHA-256': hashlib.sha256(msg).digest(),
'SHA-384': hashlib.sha384(msg).digest(),
'SHA-512': hashlib.sha512(msg).digest()
}
message_sum = HASH_FUNC[namePrefix]
c = bytes_to_long(sig_bytes)
m = long_to_bytes(pow(c, public_key.e, public_key.n))
em = bytearray(key_size//8)
em[key_size//8-len(m):] = m
em = bytes(em)
i = 0
if em[i] != 0 or em[i+1] != 1:
return 0
i = i + 2
while i < key_size//8 and em[i] == 0xff:
i += 1
if em[i] != 0:
return 0
i += 1
if em[i:i+len(prefix)] != prefix:
return 0
i = i + len(prefix)
if em[i:i+len(message_sum)] != message_sum:
return 0
return 1
def main():
HASH_ASN1 = {
'MD5': b'\x30\x20\x30\x0c\x06\x08\x2a\x86\x48\x86\xf7\x0d\x02\x05\x05\x00\x04\x10',
'SHA-1': b'\x30\x21\x30\x09\x06\x05\x2b\x0e\x03\x02\x1a\x05\x00\x04\x14',
'SHA-256': b'\x30\x31\x30\x0d\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x01\x05\x00\x04\x20',
'SHA-384': b'\x30\x41\x30\x0d\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x02\x05\x00\x04\x30',
'SHA-512': b'\x30\x51\x30\x0d\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x03\x05\x00\x04\x40'
}
namePrefix = random.choice(list(HASH_ASN1.keys()))
p, q = getPrime(1024), getPrime(1024)
modulus = p*q
key_size = modulus.bit_length()
public_key = RSA.construct((modulus, 3))
print("Hash:", namePrefix)
print("Modulus =", modulus)
try:
message = input("Enter the message you want to verify: ")
signature = base64.b64decode(input("Enter its base64 signature: "))
except:
print("Invalid input!")
exit()
err = verifySignature(public_key, message.encode(), signature, key_size, HASH_ASN1[namePrefix], namePrefix)
if err:
print("Well done! This is your flag:", FLAG)
exit()
else:
print("Not good enough! Try harder! -.-")
exit()
if __name__ == "__main__":
main()
```
## Phân tích
Về cơ bản bài này chỉ cho phép ta gửi `msg` và `sig` của nó lên rồi `verify` và nhiệm vụ ta cần kiếm `sig` phù hợp .
> Đầu tiên , khi nào hàm `verify` của ta trả ra kết quả `True`
```python=
c = bytes_to_long(sig_bytes)
m = long_to_bytes(pow(c, public_key.e, public_key.n))
em = bytearray(key_size//8)
em[key_size//8-len(m):] = m
em = bytes(em)
i = 0
if em[i] != 0 or em[i+1] != 1:
return 0
i = i + 2
while i < key_size//8 and em[i] == 0xff:
i += 1
if em[i] != 0:
return 0
i += 1
if em[i:i+len(prefix)] != prefix:
return 0
i = i + len(prefix)
if em[i:i+len(message_sum)] != message_sum:
return 0
return 1
```
Về cơ bản thì server sẽ tính toán $c ≡ sig^3 \ mod \ n$ rồi gắn nó vào trong `em` với `em` đang là 1 `bytearray` rỗng.
Tiếp theo các hàm check của nó thì ta sẽ biết $em[0] = 0$ và $em[1] = 1$ , rồi sẽ 1 hàm check giúp xét các phần tử tiếp theo , hoặc bỏ qua luôn nếu mà giá trị $em[i]$ của mình không phải $0xff$.
Tiếp đó thì nó sẽ check xem phần tiếp theo có bằng $prefix$ và $message \ sum$ không , trong đó $prefix$ là phần $hash$ mà đề bài cho và $message \ sum$ là $hash$ msg mình gửi .
> Vậy để có thể verify được thì $em$ của chúng ta sẽ có dạng :
$em = [0,1,0xff,..0xff,0,prefix,message \ sum]$ hoặc $em = [0,1,0,prefix,\ message \ sum,...]$
Nhìn vào đoạn $em$ này thì chúng ta sẽ nghĩ đến [PKCS #1 v1.5](https://crypto.stackexchange.com/questions/62783/signature-with-bleichenbacher-s-attack)
Và quả thật nó là bài toán `bleichenbacher` rồi :kissing_smiling_eyes:
Đối với bài toán này thì $em$ của chúng ta sẽ ở dạng 1 , thế mà trong giải mình ngồi giải mãi ở dạng 2 :disappointed_relieved:
## Exploit
Vậy thì giờ đây ta thấy đây sẽ là bài toán $Bleichenbacher$ rồi , thực chất trong giải mình không làm cách này , mà làm một cách lmao hơn , mình sẽ để code mình ở dưới . Cách này mình được anh Mạnh chỉ sau giải :smile_cat:
Script forge được lấy từ [đây](https://www.hackthebox.com/blog/business-ctf-2022-write-up-bbgun06) dưới sự tài trợ của anh Mạnh
**Script**
```python=
from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto.PublicKey import RSA
from base64 import b64encode
from hashlib import sha1
from gmpy2 import iroot
from pwn import *
import re
def forge_signature(message,prefix, n, e):
key_length = len(bin(n)) - 2
block = b'\x00\x01\xff\x00' + prefix + message
garbage = (((key_length + 7) // 8) - len(block)) * b'\xff'
block += garbage
pre_encryption = bytes_to_long(block)
forged_sig = iroot(pre_encryption, e)[0]
return long_to_bytes(forged_sig)
io = remote("157.15.86.73", 2003)
io.recvuntil(b'Hash: ')
namePrefix = io.recvline()[:-1].decode()
HASH_ASN1 = {
'MD5': b'\x30\x20\x30\x0c\x06\x08\x2a\x86\x48\x86\xf7\x0d\x02\x05\x05\x00\x04\x10',
'SHA-1': b'\x30\x21\x30\x09\x06\x05\x2b\x0e\x03\x02\x1a\x05\x00\x04\x14',
'SHA-256': b'\x30\x31\x30\x0d\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x01\x05\x00\x04\x20',
'SHA-384': b'\x30\x41\x30\x0d\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x02\x05\x00\x04\x30',
'SHA-512': b'\x30\x51\x30\x0d\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x03\x05\x00\x04\x40'
}
prefix = HASH_ASN1[namePrefix]
io.recvuntil(b'Modulus = ')
n = int(io.recvline()[:-1].decode())
msg = b'01'
HASH_FUNC = {
'MD5': hashlib.md5(msg).digest(),
'SHA-1': hashlib.sha1(msg).digest(),
'SHA-256': hashlib.sha256(msg).digest(),
'SHA-384': hashlib.sha384(msg).digest(),
'SHA-512': hashlib.sha512(msg).digest()
}
message_sum = HASH_FUNC[namePrefix]
sig = base64.b64encode(forge_signature(message_sum,prefix,n,3))
io.sendline(msg)
io.sendline(sig)
io.interactive()
```
Mình có sửa 1 chút hàm của nó để có thể phù hợp với các loại hash chứ không phải mỗi $SHA-1$ như trong link kia nhé , do bài kia người ta cố định $SHA-1$ rồi . Nhưng sau khi sửa thì mình cũng chỉ thành công với $3/5$ loại , $MD5$ và $SHA-512$ mình vẫn chưa làm được =(((
## Cách 2
Ừm cách của 2 của mình sẽ dùng đến cái $em = [0,1,0,prefix,\ message \ sum,...]$
Đơn giản thì chúng ta chỉ cần $em$ chứa đoạn $[0,1,0,prefix,\ message \ sum]$ là được , còn đoạn sau không quan trọng . Nên mình sẽ cho tất cả đoạn sau là $0x00$ rồi tính căn bậc 3 của nó .
Tất nhiên số sau khi căn bậc 3 sẽ không phải là 1 số nguyên , mình sẽ chọn một số nguyên gần nó thôi , thường là nhỏ hơn từ 1 2 đơn vị . Để việc tìm này dễ hơn thì mình chọn thuật toán là $SHA-1$ , thuật toán băm có độ dài ngắn nhất , nên đoạn $[0,1,0,prefix,\ message \ sum]$ sẽ ngắn hơn nhiều và đỡ bị ảnh hưởng hơn :smiley:
**Script**
```python=
from pwn import *
from json import *
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from Crypto.Util.number import *
from itertools import *
from tqdm import tqdm
import gmpy2
def cubic(ct):
with gmpy2.local_context(gmpy2.context(), precision=300) as ctx:
cube_root = gmpy2.cbrt(ct)
return int(cube_root)
HASH_ASN1 = {
'MD5': b'\x30\x20\x30\x0c\x06\x08\x2a\x86\x48\x86\xf7\x0d\x02\x05\x05\x00\x04\x10',
'SHA-1': b'\x30\x21\x30\x09\x06\x05\x2b\x0e\x03\x02\x1a\x05\x00\x04\x14',
'SHA-256': b'\x30\x31\x30\x0d\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x01\x05\x00\x04\x20',
'SHA-384': b'\x30\x41\x30\x0d\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x02\x05\x00\x04\x30',
'SHA-512': b'\x30\x51\x30\x0d\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x03\x05\x00\x04\x40'
}
while True:
io = remote("157.15.86.73", 2003)
io.recvuntil(b'Hash: ')
namePrefix = io.recvline()[:-1].decode()
if namePrefix != 'SHA-1' :
continue
prefix = HASH_ASN1[namePrefix]
io.recvuntil(b'Modulus = ')
n = int(io.recvline()[:-1].decode())
msg = b'01'
HASH_FUNC = {
'MD5': hashlib.md5(msg).digest(),
'SHA-1': hashlib.sha1(msg).digest(),
'SHA-256': hashlib.sha256(msg).digest(),
'SHA-384': hashlib.sha384(msg).digest(),
'SHA-512': hashlib.sha512(msg).digest()
}
message_sum = HASH_FUNC[namePrefix]
em = [0] + [1] + [0] + list(prefix) + list(message_sum)
tmp = bytes(em)[1:]
l = len(tmp)
x = 255 - l
tmp = bytes_to_long(tmp)*2**(8*x)
a = cubic(tmp) - 2
io.sendline(msg.decode())
send = base64.b64encode(long_to_bytes(a))
io.sendline(send)
io.interactive()
```
Flag : ```KMACTF{W0w!!_Y0u're_s0_g00d_4t_Bl3ich3nb4ch3r}```
# Encrypt Message System
**Source**
```python=
import secrets
import hashlib
from Crypto.Cipher import ChaCha20_Poly1305
from Crypto.Util.number import getPrime
import json
flag = b'KMACTF{******************************}'
l = 16
key = secrets.token_bytes(32)
def enc(cmt, nonce):
nonce = hashlib.sha256(nonce).digest()[:12]
cipher = ChaCha20_Poly1305.new(key=key, nonce=nonce)
ct, tag = cipher.encrypt_and_digest(cmt)
return nonce + ct + tag
def dec(cmt):
nonce = cmt[:12]
ct = cmt[12:-16]
tag = cmt[-16:]
cipher = ChaCha20_Poly1305.new(key=key, nonce=nonce)
pt = cipher.decrypt_and_verify(ct, tag)
return pt
def polynomial_evaluation(coefficients, x):
at_x = 0
for i in range(len(coefficients)):
at_x += coefficients[i] * (x ** i)
at_x = at_x % p
return at_x
def verify(enc_message):
message = dec(enc_message)
if message == b'give me the flag':
return True
return False
print("Welcome to the encrypt message system\n")
print("1. Encrypt message")
print("2. Get flag")
p = getPrime(512)
print(f"p = {p}")
while True:
try:
option = input("Enter option: ")
if option == "1":
coefficients = [secrets.randbelow(p) for _ in range(l)]
print(f"coefficients = {coefficients}")
message = input("Enter message: ")
if message == "give me the flag":
print("Invalid message")
break
x = int(input("Enter x: "))
y = polynomial_evaluation(coefficients, x)
encrypted = enc(message.encode(), str(y).encode())
print(encrypted.hex())
if option == "2":
encrypted = bytes.fromhex(input("Enter encrypted message: "))
try:
if verify(encrypted):
print(flag)
except:
print("you failed")
pass
except:
print("Invalid input")
break
```
## Phân tích
Đây là một bài về $Chacha20-Poly1305$ , với bài này server cho phép ta nhận được `coefficients` , gửi $message$ , $x$ lên và nhận về $encrypted$ và một chức năng là hàm `verify` để lấy `flag`
Ngó qua một chút về hàm `enc` và sự liên quan nó với thử mình nhập vào :
```python=
x = int(input("Enter x: "))
y = polynomial_evaluation(coefficients, x)
encrypted = enc(message.encode(), str(y).encode())
def enc(cmt, nonce):
nonce = hashlib.sha256(nonce).digest()[:12]
cipher = ChaCha20_Poly1305.new(key=key, nonce=nonce)
ct, tag = cipher.encrypt_and_digest(cmt)
return nonce + ct + tag
```
Như ta thấy thì enc ta sẽ được truyền nonce với $nonce = y$ vào , vậy nếu $y$ bị lặp lại thì ta có thể dễ dàng sử dụng `nonce reuse attack` đổi với `Chacha20-Poly1305` rồi :yum:
Giờ ta sẽ phải xem y được tính như thế nào để có thể cho nó lặp lại :
```python=
def polynomial_evaluation(coefficients, x):
at_x = 0
for i in range(len(coefficients)):
at_x += coefficients[i] * (x ** i)
at_x = at_x % p
return at_x
```
Như đoạn code này cho thấy thì $y = coff_0*x^0 + coff_1*x^1 + .. + coff_{15}*x^{15} \ (mod \ p)$
Gía sử mình connect đến `server` và nhận được 1 cặp `coffi` rồi gửi lên server $x=1$ thì mình sẽ có $y_1 = coff_0+ coff_1*x^1 + .. + coff_{15} \ (mod \ p)$ , tiếp tục mình lấy thêm một mảng `coffie` nữa , lúc này nhiệm vụ của mình là tìm x , sao cho :
$y_1 = coff_0*x_1^0 + coff_1*x_1^1 + .. + coff_15*x_1^{15} \ (mod \ p )$
Ta có thể làm được điều này với hàm `f.roots()` của sage .
Sau khi tìm được x thì ta gửi lên server thì lúc này $y$ sẽ được tái sử dụng hay $nonce$ sẽ bị `reuse` .
Lúc này ta chỉ cần dùng [nonce reuse attack](https://github.com/tl2cents/AEAD-Nonce-Reuse-Attacks/blob/main/chacha-poly1305/chacha_poly1305_forgery.py) thôi :yum:
> Một chút lưu ý là phương trình $y_1 = coff_0*x_1^0 + coff_1*x_1^1 + .. + coff_15*x_1^{15} \ (mod \ p )$ không phải lúc nào cũng có nghiệm nên bạn có thể tạo 1 vòng `while True` hoặc đơn giản chạy lại như mình =))
## Code
Do sage mình bị lỗi liên quan đến `pwntools` nên mình không cần cách nào khác ngoài cop cả cái thư viện vào code nha , rất xin lỗi vì đống code naỳ =((
```python=
from pwn import *
from json import *
from ast import literal_eval
import secrets
from sage.all import GF, ZZ, PolynomialRing
from Crypto.Cipher.ChaCha20 import ChaCha20Cipher
def _poly1305(msg:bytes, key:bytes, byteorder='little'):
""" A pure python implementation of the Poly1305 MAC function.
Not a standard implementation, abandoned
Args:
msg (bytes): The message to authenticate
key (bytes): The 32 byte key to use
Returns:
bytes: The 16 byte MAC
"""
p = 2**130 - 5 # the prime number used in Poly1305
r = int.from_bytes(key[:16], byteorder)
r = r & 0x0ffffffc0ffffffc0ffffffc0fffffff
s = int.from_bytes(key[16:], byteorder)
acc = 0
for i in range(0, len(msg), 16):
block = msg[i:i+16] + b'\x01'
block = int.from_bytes(block, byteorder)
acc = (acc + block) * r % p
acc = (acc + s) % p
acc = int(acc % 2**128)
return acc.to_bytes(16, byteorder)
# the implementation of the Poly1305 in the standard lib is as follows:
def poly1305(msg:bytes, key:bytes, byteorder='little'):
""" A pure python implementation of the Poly1305 MAC function
Reference: https://datatracker.ietf.org/doc/html/rfc7539#section-2.5.1
Args:
msg (bytes): The message to authenticate
key (bytes): The 32 byte key to use
Returns:
bytes: The 16 byte MAC
"""
p = 2**130 - 5 # the prime number used in Poly1305
r = int.from_bytes(key[:16], byteorder)
r = r & 0x0ffffffc0ffffffc0ffffffc0fffffff
s = int.from_bytes(key[16:], byteorder)
acc = 0
for i in range(0, len(msg), 16):
block = msg[i:i+16] + b'\x01'
block = int.from_bytes(block, byteorder)
acc = (acc + block) * r % p
acc = (acc + s) # no more % p here !!!
acc = int(acc % 2**128)
return acc.to_bytes(16, byteorder)
def construct_poly1305_coeffs(msg:bytes, byteorder='little'):
# get coefficients of the polynomial from the message bytes
coeff = []
for i in range(0, len(msg), 16):
block = msg[i:i+16] + b'\x01'
block = int.from_bytes(block, byteorder)
coeff.append(block)
return coeff
def sage_poly1305(msg:bytes, key:bytes, byteorder='little'):
r = int.from_bytes(key[:16], byteorder)
r = r & 0x0ffffffc0ffffffc0ffffffc0fffffff
s = int.from_bytes(key[16:], byteorder)
p = 2**130 - 5 # the prime number used in Poly1305
PolynomialRing_GF = PolynomialRing(GF(p), 'x')
x = PolynomialRing_GF.gen()
poly = x * PolynomialRing_GF(construct_poly1305_coeffs(msg, byteorder)[::-1]) + s
val = int(poly(r))
return int(val % 2**128).to_bytes(16, byteorder)
def is_valid_r(r):
# check if r is a valid Poly1305 key
# from RFC specification: https://datatracker.ietf.org/doc/html/rfc7539#section-2.5
return (r & 0x0ffffffc0ffffffc0ffffffc0fffffff) == r
def recover_poly1305_key_from_nonce_reuse(msg1:bytes, tag1:bytes,
msg2:bytes, tag2:bytes,
byteorder='little'):
"""Recover the Poly1305 key when nonce is reused.
Args:
msg1 (bytes): The first message
tag1 (bytes): The first tag
msg2 (bytes): The second message
tag2 (bytes): The second tag
Returns:
list: keys r, s
"""
p = 2**130 - 5 # the prime number used in Poly1305
pp = 2**128
PolynomialRing_GF = PolynomialRing(GF(p), 'x')
x = PolynomialRing_GF.gen()
poly1 = x * PolynomialRing_GF(construct_poly1305_coeffs(msg1, byteorder)[::-1])
a1 = int.from_bytes(tag1, byteorder)
poly2 = x * PolynomialRing_GF(construct_poly1305_coeffs(msg2, byteorder)[::-1])
a2 = int.from_bytes(tag2, byteorder)
# find all possible keys
roots = []
print(f"[+] Searching for the key with poly.degree() = {(poly1 - poly2).degree()}")
# the range is larger than expected
# since in poly1305 acc + s does not have to be modulo p
for tag1 in range(a1, p + pp, pp):
for tag2 in range(a2, p + pp, pp):
f = (poly1 - poly2) - (tag1 - tag2)
root = f.roots(multiplicities=False)
for r in root:
r = int(r)
if is_valid_r(r):
# print(f"[+] Found a valid key: {r}")
# check if the key is valid
s = int(a1 - int(poly1(r))) % pp
if (int(poly1(r)) + s) % pp == a1 and (int(poly2(r)) + s) % pp == a2:
roots.append((r, s))
return list(set(roots))
def derive_poly1305_key(key:bytes, nonce:bytes):
assert len(key) == 32 and len(nonce) == 12, "The key should be 32 bytes and the nonce should be 12 bytes"
chacha20_block = ChaCha20Cipher(key, nonce).encrypt(b'\x00'*64)
return chacha20_block[:32]
def chachapoly1305_merger(ad:bytes, ct:bytes):
"""Merge the associated data and the ciphertext
Args:
ad (bytes): The associated data
ct (bytes): The ciphertext
Returns:
bytes: The merged data
"""
def pad(data, block_size=16):
if len(data) % block_size == 0:
return data
return data + b'\x00' * (block_size - len(data) % block_size)
la = len(ad)
lc = len(ct)
out = pad(ad) + pad(ct) + la.to_bytes(8, 'little') + lc.to_bytes(8, 'little')
return out
def chachapoly1305_nonce_reuse_attack(ad1:bytes, ct1:bytes, tag1:bytes,
ad2:bytes, ct2:bytes, tag2:bytes):
"""Recover the Chacha-Poly1305 key when nonce is reused.
The two messages are encrypted with the same nonce and the same key.
Args:
ad1 (bytes): The first associated data
ct1 (bytes): The first ciphertext
tag1 (bytes): The first tag
ad2 (bytes): The second associated data
ct2 (bytes): The second ciphertext
tag2 (bytes): The second tag
Returns:
list: keys r, s
"""
inp1 = chachapoly1305_merger(ad1, ct1)
inp2 = chachapoly1305_merger(ad2, ct2)
return recover_poly1305_key_from_nonce_reuse(inp1, tag1, inp2, tag2)
def forge_poly1305_tag(ad:bytes, ct:bytes, r:int, s:int):
"""Forge a Poly1305 tag given the message and the key
Args:
ad (bytes): The associated data
ct (bytes): The ciphertext
r (int): The r key
s (int): The s key
"""
key = r.to_bytes(16, 'little') + s.to_bytes(16, 'little')
msg = chachapoly1305_merger(ad, ct)
return poly1305(msg, key)
def chachapoly1305_forgery_attack(ad1:bytes, ct1:bytes, tag1:bytes,
ad2:bytes, ct2:bytes, tag2:bytes,
known_plaintext1:bytes,
target_plaintext:bytes, target_ad:bytes):
"""Recover the Chacha-Poly1305 key when nonce is reused.
Args:
ad1 (bytes): The first associated data
ct1 (bytes): The first ciphertext
tag1 (bytes): The first tag
ad2 (bytes): The second associated data
ct2 (bytes): The second ciphertext
tag2 (bytes): The second tag
known_plaintext1 (bytes): The known plaintext of ct1
target_plaintext (bytes): The target plaintext to forge
target_ad (bytes): The target associated data to forge
return:
generator: yields the forged ciphertext and tag
"""
keys = chachapoly1305_nonce_reuse_attack(ad1, ct1, tag1, ad2, ct2, tag2)
if len(keys) == 0:
assert False, "Failed to recover the key for poly1305, probably the nonce is not reused"
assert len(target_plaintext) <= len(known_plaintext1), "The target plaintext should be shorter than the known plaintext"
keystream = [b1 ^^ b2 for b1, b2 in zip(known_plaintext1, ct1)]
target_ct = bytes([b1 ^^ b2 for b1, b2 in zip(keystream, target_plaintext)])
for r, s in keys:
target_tag = forge_poly1305_tag(target_ad, target_ct, r, s)
yield target_ct, target_tag
def chachapoly1305_forgery_attack_general(ads:list[bytes], cts:list[bytes], tags:bytes,
known_plaintext1:bytes,
target_plaintext:bytes, target_ad:bytes):
"""Recover the Chacha-Poly1305 key when nonce is reused.
Args:
ads (list[bytes]): The associated data
cts (list[bytes]): The ciphertexts
tags (list[bytes]): The tags
known_plaintext1 (bytes): The known plaintext of ct1
target_plaintext (bytes): The target plaintext to forge
target_ad (bytes): The target associated data to forge
returns:
target_ct, target_tag : bytes, bytes (if not unique, we simply return the first one)
"""
assert len(ads) == len(cts) == len(tags) and len(cts) >= 2, "The length of the associated data, ciphertexts, and tags should be the same and at least 2"
ad1, ct1, tag1 = ads[0], cts[0], tags[0]
keys = []
for ad2, ct2, tag2 in zip(ads[1:], cts[1:], tags[1:]):
if len(keys) == 0:
keys = chachapoly1305_nonce_reuse_attack(ad1, ct1, tag1, ad2, ct2, tag2)
else:
_keys = chachapoly1305_nonce_reuse_attack(ad1, ct1, tag1, ad2, ct2, tag2)
keys = list(set(keys) & set(_keys))
if len(keys) == 1:
break
if len(keys) == 0:
assert False, "Failed to recover the key for poly1305, probably the nonce is not reused"
elif len(keys) > 1:
print(f"[!] Found multiple keys {len(keys) = }, trying to forge the message, use the first key")
print("[!] You can use more nonce-reuse messages to find the unique key")
# anyway, use the first key
r, s = keys[0]
print(f"[+] Using Key {r = }, {s = } {len(keys) = }")
assert len(target_plaintext) <= len(known_plaintext1), "The target plaintext should be shorter than the known plaintext"
keystream = [b1 ^^ b2 for b1, b2 in zip(known_plaintext1, ct1)]
target_ct = bytes([b1 ^^ b2 for b1, b2 in zip(keystream, target_plaintext)])
target_tag = forge_poly1305_tag(target_ad, target_ct, r, s)
return target_ct, target_tag
def dec(cmt):
nonce = cmt[:12]
ct = cmt[12:-16]
tag = cmt[-16:]
return nonce , ct , tag
io = remote("157.15.86.73", 1305)
io.recvuntil(b'p = ')
p = int(io.recvline()[:-1].decode())
io.sendline(b'1')
io.recvuntil(b'coefficients = ')
coefficients = literal_eval(io.recvline()[:-1].decode())
msg1 = secrets.token_bytes(32).hex().encode()
msg2 = secrets.token_bytes(32).hex().encode()
io.sendline(msg1)
io.recvuntil(b'x: ')
io.sendline(b'1')
enc = bytes.fromhex(io.recvline()[:-1].decode())
from sage.all import *
P.<x> = PolynomialRing(Zmod(p))
at_x = 0
for i in range(len(coefficients)):
at_x += coefficients[i] * (x ** i)
at_x = at_x
ans = int(at_x(x=1))
io.sendline(b'1')
io.recvuntil(b'coefficients = ')
coefficients = literal_eval(io.recvline()[:-1].decode())
P.<x> = PolynomialRing(Zmod(p))
at_x = 0
for i in range(len(coefficients)):
at_x += coefficients[i] * (x ** i)
at_x = at_x
at_x = at_x - ans
x_tmp = str(at_x.roots()[0][0])
io.sendline(msg2)
io.recvuntil(b'x: ')
io.sendline(x_tmp.encode())
enc2 = bytes.fromhex(io.recvline()[:-1].decode())
nonce1 , ct1 , tag1 = dec(enc)
nonce2 , ct2, tag2 = dec(enc2)
assert nonce1 == nonce2
msg = b'give me the flag'
forges = list(chachapoly1305_forgery_attack(b'', ct1, tag1,
b'', ct2, tag2,
msg1,
msg, b''))
ct , tag = forges[0][0] , forges[0][1]
send_tmp = nonce1 + ct + tag
io.sendline(b'2')
io.sendline(send_tmp.hex())
io.interactive()
```
> Một chút lưu ý về cái này , đôí với ```AES-GCM``` nếu ta không sử dụng $Ad$ hay $associated \ data$ thì nó sẽ mặc định là `b'\x00` , còn đối với ```Chacha20-Poly1305``` thì nó sẽ mặc định là ```b''```
Flag : ```KMACTF{us3_poly0omia1_t0_gen3rate_n0nce_1s_the_bad_idea}```
# ZKP for QNR
Rustttttttttttttttttttttttttt :sob:
Main.rs
```rust=
use num_bigint::BigUint;
use std::str::FromStr;
pub mod prover;
pub mod utils;
pub mod verifier;
use num_traits::cast::ToPrimitive;
use prover::*;
use std::fs::{self, File};
use std::io::{BufWriter, Write};
use utils::*;
use verifier::Verifier;
fn main() -> std::io::Result<()> {
let flag = b"KMACTF{*******************************************}";
let num_flag = bytes_to_biguint(flag);
let num_rounds = num_flag.bits() as usize;
// Define the folder name
let folder_name = "Log";
// Create the folder if it doesn't exist
if fs::metadata(folder_name).is_err() {
fs::create_dir(folder_name)?;
}
println!("Number of rounds: {}", num_rounds);
let x = BigUint::from_str(
"106276637345585586395178695555113419125706596151484787339368729136766801222943",
)
.unwrap();
let y = BigUint::from_str(
"67502870359608496464376733754660348616157530226832182619029429292243849029379",
)
.unwrap();
let prover = Prover::new(x.clone(), y.clone(), num_rounds);
let mut verifier = Verifier::new(x.clone(), y.clone(), num_rounds);
for i in 0..num_rounds {
let file_name = format!("{}/output_{}.txt", folder_name, i);
let file = File::create(&file_name)?;
let mut writer = BufWriter::new(file);
writeln!(writer, "Round {}", i)?;
let bit = ((&num_flag >> i) & BigUint::from(1_u32))
.to_u32()
.expect("Can not do this");
let r = verifier.get_r();
// give the prover the pair and r
let w = verifier.gen_w(bit as i32, &r);
let pair = verifier.gen_pairs();
writeln!(writer, "w = {}", w)?;
writeln!(writer, "Pair = ")?;
for p in pair {
writeln!(writer, "({}, {})", p.0, p.1)?;
}
let list_i = prover.gen_list_i();
writeln!(writer, "list_i = {:?}", list_i)?;
let v = verifier.respond(&bit, list_i, &r);
let v = convert_rp_to_string(&v);
writeln!(writer, "list_of_respond = ")?;
for line in v {
writeln!(writer, "{}", line)?;
}
writer.flush()?;
}
Ok(())
}
```
utils.rs
```rust=
use crate::verifier::Rp;
use num_bigint::{BigUint, RandomBits};
use rand::Rng;
pub fn rand_below(n: &BigUint) -> BigUint {
let mut rng = rand::thread_rng();
let bit = n.bits();
loop {
let y: BigUint = rng.sample(RandomBits::new(bit));
if y < *n {
return y;
}
}
}
pub fn bytes_to_biguint(bytes: &[u8]) -> BigUint {
BigUint::from_bytes_be(bytes)
}
pub fn convert_rp_to_string(v: &[Rp]) -> Vec<String> {
let mut normal_numbers = vec![];
for item in v {
match item {
Rp::Tuple(a, b) => {
normal_numbers.push(format!("({}, {})", a, b));
}
Rp::Number(n) => {
normal_numbers.push(format!("{}", n));
}
}
}
normal_numbers
}
```
prover.rs
```python=
use num_bigint::BigUint;
use rand::Rng;
pub struct Prover {
pub x: BigUint,
pub y: BigUint,
pub num_rounds: usize,
pub list_i: Vec<Vec<u32>>,
}
impl Prover {
pub fn new(x: BigUint, y: BigUint, n: usize) -> Self {
Prover {
x,
y,
num_rounds: n,
list_i: Vec::new(),
}
}
pub fn gen_list_i(&self) -> Vec<u32> {
let mut rng = rand::thread_rng();
let list_i: Vec<u32> = (0..self.num_rounds).map(|_| rng.gen_range(0..2)).collect();
list_i
}
// I forgot to implement verify function
// pub fn verify() -> {
//
// }
}
```
verify.rs
```rust=
use crate::utils::*;
use num_bigint::BigUint;
use serde_derive::Serialize;
pub struct Verifier {
pub x: BigUint,
pub y: BigUint,
rs: Vec<Vec<(BigUint, BigUint)>>,
pub pairs: Vec<Vec<(BigUint, BigUint)>>,
pub num_rouns: usize,
}
#[derive(Serialize, Debug)]
pub enum Rp {
Tuple(BigUint, BigUint),
Number(BigUint),
}
impl Verifier {
pub fn new(x: BigUint, y: BigUint, n: usize) -> Self {
Verifier {
x,
y,
rs: Vec::new(),
pairs: Vec::new(),
num_rouns: n,
}
}
pub fn gen_w(&self, bit: i32, r: &BigUint) -> BigUint {
if bit == 0 {
r.modpow(&BigUint::from(2_u32), &self.x)
} else {
r.modpow(&BigUint::from(2_u32), &self.x) * &self.y % &self.x
}
}
pub fn gen_pairs(&mut self) -> Vec<(BigUint, BigUint)> {
let mut rr: Vec<(BigUint, BigUint)> = Vec::with_capacity(self.num_rouns);
let mut pair: Vec<(BigUint, BigUint)> = Vec::with_capacity(self.num_rouns);
for _ in 0..self.num_rouns {
let r1 = rand_below(&self.x);
let r2 = rand_below(&self.x);
let a = r1.modpow(&BigUint::from(2_u32), &self.x);
let b = r2.modpow(&BigUint::from(2_u32), &self.x) * &self.y % &self.x;
pair.push((a, b));
rr.push((r1, r2));
}
self.rs.push(rr.clone());
self.pairs.push(pair.clone());
pair
}
pub fn respond(&self, bit: &u32, list_i: Vec<u32>, r: &BigUint) -> Vec<Rp> {
let mut v: Vec<Rp> = Vec::with_capacity(self.num_rouns);
for (i, a) in list_i.iter().enumerate() {
match (a, bit) {
(&0, _) => {
let vj = &self.rs[self.rs.len() - 1][i];
v.push(Rp::Tuple(vj.0.clone(), vj.1.clone()));
}
(1, &0_u32) => {
let vj = r * &self.rs[self.rs.len() - 1][i].0 % &self.x;
v.push(Rp::Number(vj));
}
(1, &1_u32) => {
let vj = r * &self.rs[self.rs.len() - 1][i].1 * &self.y % &self.x;
v.push(Rp::Number(vj));
}
_ => panic!("Invalid input"),
}
}
v
}
pub fn get_r(&self) -> BigUint {
rand_below(&self.x)
}
}
```
## Phân tích
Thật ra mình cũng không tiếp xúc quá nhiều với rust nên gặp mấy bài ngôn ngữ này thưởng làm mình mất kha khá thời gian để đọc hiểu code :crying_cat_face:
Để tóm gọn bài này mình sẽ chỉ tập trung vào phần code quan trọng thôi nhé .
```rust=
for i in 0..num_rounds {
let file_name = format!("{}/output_{}.txt", folder_name, i);
let file = File::create(&file_name)?;
let mut writer = BufWriter::new(file);
writeln!(writer, "Round {}", i)?;
let bit = ((&num_flag >> i) & BigUint::from(1_u32))
.to_u32()
.expect("Can not do this");
let r = verifier.get_r();
// give the prover the pair and r
let w = verifier.gen_w(bit as i32, &r);
let pair = verifier.gen_pairs();
writeln!(writer, "w = {}", w)?;
```
Đầu tiên đối với hàm main , nó sẽ encrypt từng bit của `flag` bằng cách tạo 1 số $r$ ngẫu nhiên nhỏ hơn $x$ , rồi gen ra 1 thằng $w$
```rust=
pub fn gen_w(&self, bit: i32, r: &BigUint) -> BigUint {
if bit == 0 {
r.modpow(&BigUint::from(2_u32), &self.x)
} else {
r.modpow(&BigUint::from(2_u32), &self.x) * &self.y % &self.x
}
}
```
Trong đó , nếu `bit = 0` thì $w = r^2 \ mod \ x$ , nếu `bit = 1` thì $w = r^2*y \ mod \ x$
Tức là ta chỉ cần check `legendre` của $w$ , nếu nó tồn tại tức là bit tại vị trí đó là `0` , còn nếu không thì là `1` :smiley_cat: .
Còn phần sau , yep , ta không cần động đến nó :crying_cat_face: . Trước đó mình còn vẽ 7749 kịch bản từ recover lại $r1,r2$ từ `Pair` ,chạy tính thử bit ,.. và rồi lại tìm ra cách này :crying_cat_face:
Trước khi tìm ```legendre``` của $w$ thì 1 số điều cần lưu ý chính là $x$ nó không phải prime , tức ta không dùng được $legendre-symbol$ , nhưng mà nó chỉ có 256 bit mà thôi , nên mình vác lên ```https://www.alpertron.com.ar/ECM.HTM``` để factor .
Mình thu được x là tích của 2 số
```python=
x1 = 335838999993620015742911607048721969241
x2 = 316451148757602719584055866251668474423
```
Sau có giá trị của từng thành phần thỉ ta check ```legendre``` trong từng modul đó , nếu tất cả đều tồn tại thì bit tại đó là `0` , còn không là `1`
**Script**
```python=
def legendre_symbol(a, p):
ls = pow(a, (p - 1)//2, p)
return -1 if ls==p-1 else ls
x1 = 335838999993620015742911607048721969241
x2 = 316451148757602719584055866251668474423
y = 67502870359608496464376733754660348616157530226832182619029429292243849029379
num_rounds = 407
folder_name = "Log"
flag = ''
from Crypto.Util.number import *
for i in range(num_rounds):
file_name = f"{folder_name}/output_{i}.txt"
f = open(file_name, 'r')
f.readline()
w = int(f.readline().split('=')[1])
if legendre_symbol(w,x1) == 1 :
flag += '0'
else :
flag += '1'
print(long_to_bytes(int(flag[::-1],2)))
```
Flag : ```KMACTF{https://www.youtube.com/watch?v=fHCraDGaotM}```
Không hiểu tại sao code của mình bị mất chữ `K` :crying_cat_face: , sau một hồi xem lại thì mình nhận ra nó có 407 file chứ không phải 406 file :weary
~~Trước đó mình thật sự ngồi code 120 dòng chỉ để đọc file~~
## Cách 2
Giờ chúng ta sẽ không factor x nữa thì có thể làm kiểu gì , lúc này hàm `legendre` của ta sẽ không thế sử dụng được nữa nên ta sẽ phải khai thác các hàm ở sau . Ở đây ta sẽ khai thác hàm `respond`
```rust=
pub fn respond(&self, bit: &u32, list_i: Vec<u32>, r: &BigUint) -> Vec<Rp> {
let mut v: Vec<Rp> = Vec::with_capacity(self.num_rouns);
for (i, a) in list_i.iter().enumerate() {
match (a, bit) {
(&0, _) => {
let vj = &self.rs[self.rs.len() - 1][i];
v.push(Rp::Tuple(vj.0.clone(), vj.1.clone()));
}
(1, &0_u32) => {
let vj = r * &self.rs[self.rs.len() - 1][i].0 % &self.x;
v.push(Rp::Number(vj));
}
(1, &1_u32) => {
let vj = r * &self.rs[self.rs.len() - 1][i].1 * &self.y % &self.x;
v.push(Rp::Number(vj));
}
_ => panic!("Invalid input"),
}
}
```
Giải thích sơ qua 1 chút về hàm này thì nếu giá trị của a = 0 thì sẽ trả về giá trị `(r1,r2)` , ta không khai thác được gì từ chỗ này . Mấu chốt là ở 2 điều kiện sau :
Trong đó , ```a == 1 , bit = 0``` sẽ trả về cho ta $r*r_1 \ mod \ x$
Và , ```a==1 , bit == 1``` sẽ trả về $r*r_2*y \ mod \ x$
Ta không biết giá trị của $r_1$ hay $r_2$ nên ta không thể kiểm tra được nhưng mà ta có thể khai thác nó theo 1 hướng khác thông qua $Pair$
```rust=
pub fn gen_pairs(&mut self) -> Vec<(BigUint, BigUint)> {
let mut rr: Vec<(BigUint, BigUint)> = Vec::with_capacity(self.num_rouns);
let mut pair: Vec<(BigUint, BigUint)> = Vec::with_capacity(self.num_rouns);
for _ in 0..self.num_rouns {
let r1 = rand_below(&self.x);
let r2 = rand_below(&self.x);
let a = r1.modpow(&BigUint::from(2_u32), &self.x);
let b = r2.modpow(&BigUint::from(2_u32), &self.x) * &self.y % &self.x;
pair.push((a, b));
rr.push((r1, r2));
}
self.rs.push(rr.clone());
self.pairs.push(pair.clone());
pair
}
```
Thì như ở đây ta thấy , ta sẽ nhận được pair hay các cặp $a,b$ , trong đó :
$a \equiv r_1^2 \ mod \ x$
$b \equiv r_2^2*y \ mod \ x$
và cả $w$ trước đó là $w \equiv r^2 \ mod \ x$ nếu $bit=0$ hoặc $w \equiv r^2*y \ mod \ x$ nếu $bit = 1$
Giờ giả sử vị trí $i$ nào đó bit của ta là `0` thì ta có các dữ kiện :
Ouptut của `list of response` tạm gọi là $c$ sẽ là $r*r_1 \mod \ x$
$a \equiv r_1^2 \ mod \ x$
$w \equiv r^2 \mod \ x$
Thì ta có thể thấy : $c^2 \equiv a*w \equiv (r*r_1)^2 \mod \ x$
Vậy ta chỉ cần lấy giá trị $w,a$ và giá trị output tại vị trí mà $a=1$ thì có thể xác định bằng biểu thức trên rồi , nếu thỏa mãn sẽ là bit `0` , còn không sẽ là bit `1`
Còn khi nào biết $a=1$ thì ta nhìn output nó là được , nếu $a=0$ thì nó trả về tuple còn $a=1$ nó trả về int :v
**Script**
```python=
num_rounds = 407
folder_name = "Log"
flag = ''
x = 106276637345585586395178695555113419125706596151484787339368729136766801222943
from Crypto.Util.number import *
from ast import literal_eval
for i in range(num_rounds):
file_name = f"{folder_name}/output_{i}.txt"
f = open(file_name, 'r')
f.readline()
w = int(f.readline().split('=')[1])
f.readline()
Pair = []
for _ in range(407) :
Pair.append(literal_eval(f.readline()))
list_i = literal_eval(f.readline().split('=')[1])
f.readline()
for i in Pair :
tmp = literal_eval(f.readline())
if str(type(tmp)) == "<class 'int'>":
a = i[0]
if pow(tmp,2,x) == (w*a)%x :
flag += '0'
else :
flag += '1'
break
print(long_to_bytes(int(flag[::-1],2)))
```
# Let_them_share
**Source**
```python=
import os
import random
from Crypto.Util.number import bytes_to_long, getPrime
DEGREE = 10
BITSIZE = 64
FLAG = "KMACTF{s0m3_r3ad4ble_5tr1ng_like_7his}"
def get_coeff(p):
# bigger coeff, safer sss :D
while True:
coeff = bytes_to_long(os.urandom(BITSIZE // 16).hex().upper().encode())
if BITSIZE - 1 <= coeff.bit_length() and coeff < p:
return coeff
def _eval_at(poly, x, prime):
"""Evaluates polynomial (coefficient tuple) at x, used to generate a
shamir pool in make_random_shares below.
"""
accum = 0
for coeff in reversed(poly):
accum *= x
accum += coeff
accum %= prime
return x, accum
def make_random_shares(secret, modulus):
coefficients = [secret] + [get_coeff(modulus) for _ in range(DEGREE)]
return [_eval_at(coefficients, random.randint(0, modulus - 1), modulus) for _ in range(DEGREE)]
def main():
p = getPrime(BITSIZE)
SECRET = get_coeff(p)
points = make_random_shares(SECRET, p)
print("Wait, there's something wrong, is our secret lost ?")
print("p =", p)
print("points =", points)
print(SECRET.bit_length())
number = int(input("What's our secret ? "))
if number == SECRET:
print("Cool!! You can deal with hard challenge, get your treasure here:", FLAG)
exit()
else:
print("We lost it! :((")
exit()
if __name__ == "__main__":
main()
```
## Phân tích
Về cơ bản bài này sẽ bắt ta phải đoán đúng secrect . Trong đó secret sẽ nằm trong 1 `coefficients` và sẽ được đưa vào 1 ẩn x để tính toán.
Cơ bản là ta nhìn vào hàm `eval_at` cho dễ nhìn nhé :v. Ở đây `coeffcients` có 11 ẩn , trong đó 10 ẩn là được gen ngẫu nhiên bằng hàm `get_coeff` , và ẩn cuối của là thằng `secret của mình` cũng gen bằng `get_coeff` luôn =))
```python=
def _eval_at(poly, x, prime):
"""Evaluates polynomial (coefficient tuple) at x, used to generate a
shamir pool in make_random_shares below.
"""
accum = 0
for coeff in reversed(poly):
accum *= x
accum += coeff
accum %= prime
return x, accum
```
Ở đây thì nó sẽ tính $y = coeff_{10}*x^{10} + coeff_9*x^9 + .. coeff_0$ và chúng ta sẽ được nhận lại 1 cặp $(x,y)$ tương ứng. Và chúng ta có thể nhận được 10 cặp như vậy.
Vậy ở đây ta có 11 cái `coeff` nhưng chỉ có 10 điểm , tức không đủ để giải phương trình , thật ra vẫn giải được nhưng mà thế thì nó nhiểu nghiệm lắm , mình chạy thử tầm hơn 30p mà không tìm được nghiệm chuẩn =)).
Thì ở đây ta sẽ khai thác phần này :
``` python=
coeff = bytes_to_long(os.urandom(BITSIZE // 16).hex().upper().encode())
```
Ở đây ta sẽ biết các `coeff` chỉ là `bytes_to_long` của 1 4 bytes tức là chuỗi ký tự hex gồm 8 ký tự nên các phần tử nó sẽ thuộc trong `0123456789ABCDEF`
Giờ ta ngó qua 1 chút tính chất của hàm `bytes_to_long` , thì với chuỗi nó là 8 ký tự , mình sẽ gọi nó lần lượt là `x1,x2,..,x8`
Thì `coeff = x1*2^56 + x2*2^48 + .. + x8*2^0`
Do `x1,x2,..x8` chỉ thuộc trong `0123456789ABCDEF` nên max sẽ chỉ là 70 và min sẽ là 48
```python=
from Crypto.Util.number import *
x = b'ABCDEF0123456789'
print(min(list(x)), max(list(x)))
```
Giờ ứng với 11 `coeff` không biết , mỗi `coeff` là 8 ký tự thì ta sẽ có 88 ẩn.
Mình sẽ viết lại phương trình $y = coeff_10*x^{10} + coeff_9*x^9 + .. coeff_0$ thành
$y = (x_1*2^{56} + x_2*2^{48} + .. x_8*2^0)*x^{10} + (x_9*2^{56} + .. + x_{16}*2^0)*x^9 + ... + (x_{81}*2^{56} + x_{82}*2^{48} + .. + x_{88})$
Mấy cái hệ số $x$ nhân ở bên ngoài là điểm $(x,y)$ mình nhận từ server nha . Với các điểm tương tự ta cũng thu được thêm 9 phương trình như vậy . Lúc này thì mình sẽ solve linear nó thôi , với việc biết max và min của các biến `x1,x2,..x88` rồi.
## Code
**Script**
```python=
from pwn import *
from json import *
from ast import literal_eval
from Crypto.Util.number import *
io = remote('157.15.86.73', 2004)
io.recvuntil(b'p = ')
p = int(io.recvline()[:-1].decode())
io.recvuntil(b'points = ')
points = literal_eval(io.recvline()[:-1].decode())
scale = [2^i for i in range(56,-1,-8)]
x = []
b_values = []
for i in points :
x.append(i[0])
b_values.append(i[1])
DEGREE = 10
BITSIZE = 64
A_values = []
for i in x :
multi_tmp = [(i^z)%p for z in range(10,-1,-1)]
multi = []
for o in multi_tmp :
for f in scale :
multi.append((o*f)%p)
A_values.append(multi)
from sage.modules.free_module_integer import IntegerLattice
import numpy as np
from Crypto.Cipher import AES
from hashlib import sha256
from random import SystemRandom
import sys
from sage.all import GF, PolynomialRing, Zmod, matrix, QQ, ZZ, block_matrix, zero_matrix, vector
from copy import copy
"""
Solve a bounded system of modular linear equations.
(c) 2019-2022 Robert Xiao <nneonneo@gmail.com>
https://robertxiao.ca
Originally developed in May 2019; updated July 2022
Please mention this software if it helps you solve a challenge!
"""
from collections.abc import Sequence
import math
import operator
from typing import List, Tuple
from sage.all import ZZ, gcd, matrix, prod, var
def _process_linear_equations(equations, vars, guesses) -> List[Tuple[List[int], int, int]]:
result = []
for rel, m in equations:
op = rel.operator()
if op is not operator.eq:
raise TypeError(f"relation {rel}: not an equality relation")
expr = (rel - rel.rhs()).lhs().expand()
for var in expr.variables():
if var not in vars:
raise ValueError(f"relation {rel}: variable {var} is not bounded")
# Fill in eqns block of B
coeffs = []
for var in vars:
if expr.degree(var) >= 2:
raise ValueError(f"relation {rel}: equation is not linear in {var}")
coeff = expr.coefficient(var)
if not coeff.is_constant():
raise ValueError(f"relation {rel}: coefficient of {var} is not constant (equation is not linear)")
if not coeff.is_integer():
raise ValueError(f"relation {rel}: coefficient of {var} is not an integer")
coeffs.append(int(coeff) % m)
# Shift variables towards their guesses to reduce the (expected) length of the solution vector
const = expr.subs({var: guesses[var] for var in vars})
if not const.is_constant():
raise ValueError(f"relation {rel}: failed to extract constant")
if not const.is_integer():
raise ValueError(f"relation {rel}: constant is not integer")
const = int(const) % m
result.append((coeffs, const, m))
return result
def solve_linear_mod(equations, bounds, verbose=False, **lll_args):
"""Solve an arbitrary system of modular linear equations over different moduli.
equations: A sequence of (lhs == rhs, M) pairs, where lhs and rhs are expressions and M is the modulus.
bounds: A dictionary of {var: B} entries, where var is a variable and B is the bounds on that variable.
Bounds may be specified in one of three ways:
- A single integer X: Variable is assumed to be uniformly distributed in [0, X] with an expected value of X/2.
- A tuple of integers (X, Y): Variable is assumed to be uniformly distributed in [X, Y] with an expected value of (X + Y)/2.
- A tuple of integers (X, E, Y): Variable is assumed to be bounded within [X, Y] with an expected value of E.
All variables used in the equations must be bounded.
verbose: set to True to enable additional output
lll_args: Additional arguments passed to LLL, for advanced usage.
NOTE: Bounds are *soft*. This function may return solutions above the bounds. If this happens, and the result
is incorrect, make some bounds tighter and try again.
Tip: if you get an unwanted solution, try setting the expected values to that solution to force this function
to produce a different solution.
Tip: if your bounds are loose and you just want small solutions, set the expected values to zero for all
loosely-bounded variables.
>>> k = var('k')
>>> # solve CRT
>>> solve_linear_mod([(k == 2, 3), (k == 4, 5), (k == 3, 7)], {k: 3*5*7})
{k: 59}
>>> x,y = var('x,y')
>>> solve_linear_mod([(2*x + 3*y == 7, 11), (3*x + 5*y == 3, 13), (2*x + 5*y == 6, 143)], {x: 143, y: 143})
{x: 62, y: 5}
>>> x,y = var('x,y')
>>> # we can also solve homogenous equations, provided the guesses are zeroed
>>> solve_linear_mod([(2*x + 5*y == 0, 1337)], {x: 5, y: 5}, guesses={x: 0, y: 0})
{x: 5, y: -2}
"""
# The general idea is to set up an integer matrix equation Ax=y by introducing extra variables for the quotients,
# then use LLL to solve the equation. We introduce extra axes in the lattice to observe the actual solution x,
# which works so long as the solutions are known to be bounded (which is of course the case for modular equations).
# Scaling factors are configured to generally push the smallest vectors to have zeros for the relations, and to
# scale disparate variables to approximately the same base.
vars = list(bounds)
guesses = {}
var_scale = {}
for var in vars:
bound = bounds[var]
if isinstance(bound, Sequence):
if len(bound) == 2:
xmin, xmax = map(int, bound)
guess = (xmax - xmin) // 2 + xmin
elif len(bound) == 3:
xmin, guess, xmax = map(int, bound)
else:
raise TypeError("Bounds must be integers, 2-tuples or 3-tuples")
else:
xmin = 0
xmax = int(bound)
guess = xmax // 2
if not xmin <= guess <= xmax:
raise ValueError(f"Bound for variable {var} is invalid ({xmin=} {guess=} {xmax=})")
var_scale[var] = max(xmax - guess, guess - xmin, 1)
guesses[var] = guess
var_bits = math.log2(int(prod(var_scale.values()))) + len(vars)
mod_bits = math.log2(int(prod(m for rel, m in equations)))
if verbose:
print(f"verbose: variable entropy: {var_bits:.2f} bits")
print(f"verbose: modulus entropy: {mod_bits:.2f} bits")
# Extract coefficients from equations
equation_coeffs = _process_linear_equations(equations, vars, guesses)
is_inhom = any(const != 0 for coeffs, const, m in equation_coeffs)
NR = len(equation_coeffs)
NV = len(vars)
if is_inhom:
# Add one dummy variable for the constant term.
NV += 1
B = matrix(ZZ, NR + NV, NR + NV)
# B format (rows are the basis for the lattice):
# [ mods:NRxNR 0
# eqns:NVxNR vars:NVxNV ]
# eqns correspond to equation axes, fi(...) = yi mod mi
# vars correspond to variable axes, which effectively "observe" elements of the solution vector (x in Ax=y)
# mods and vars are diagonal, so this matrix is lower triangular.
# Compute maximum scale factor over all variables
S = max(var_scale.values())
# Compute equation scale such that the bounded solution vector (equation columns all zero)
# will be shorter than any vector that has a nonzero equation column
eqS = S << (NR + NV + 1)
# If the equation is underconstrained, add additional scaling to find a solution anyway
if var_bits > mod_bits:
eqS <<= int((var_bits - mod_bits) / NR) + 1
col_scales = []
for ri, (coeffs, const, m) in enumerate(equation_coeffs):
for vi, c in enumerate(coeffs):
B[NR + vi, ri] = c
if is_inhom:
B[NR + NV - 1, ri] = const
col_scales.append(eqS)
B[ri, ri] = m
# Compute per-variable scale such that the variable axes are scaled roughly equally
for vi, var in enumerate(vars):
col_scales.append(S // var_scale[var])
# Fill in vars block of B
B[NR + vi, NR + vi] = 1
if is_inhom:
# Const block: effectively, this is a bound of 1 on the constant term
col_scales.append(S)
B[NR + NV - 1, -1] = 1
if verbose:
print("verbose: scaling shifts:", [math.log2(int(s)) for s in col_scales])
print("verbose: unscaled matrix before:")
print(B.n())
for i, s in enumerate(col_scales):
B[:, i] *= s
B = B.LLL(**lll_args)
for i, s in enumerate(col_scales):
B[:, i] /= s
# Negate rows for more readable output
for i in range(B.nrows()):
if sum(x < 0 for x in B[i, :]) > sum(x > 0 for x in B[i, :]):
B[i, :] *= -1
if is_inhom and B[i, -1] < 0:
B[i, :] *= -1
if verbose:
print("verbose: unscaled matrix after:")
print(B.n())
for row in B:
if any(x != 0 for x in row[:NR]):
# invalid solution: some relations are nonzero
continue
if is_inhom:
# Each row is a potential solution, but some rows may not carry a constant.
if row[-1] != 1:
if verbose:
print(
"verbose: zero solution",
{var: row[NR + vi] for vi, var in enumerate(vars) if row[NR + vi] != 0},
)
continue
res = {}
for vi, var in enumerate(vars):
res[var] = row[NR + vi] + guesses[var]
return res
a = [var(f"a_{i}") for i in range(len(A_values[0]))]
eqs = []
for x in range(len(A_values)) :
eq = 0
assert len(A_values[x]) == len(a)
for c,d in zip(A_values[x],a) :
eq += c*d
eqs.append((b_values[x] == eq,p))
bounds = {x: (48,70) for x in a }
print(bounds)
sol = solve_linear_mod(eqs,bounds)
ks = list(sol.values())[-8:]
print(ks)
print(sol.values())
y = bytes(ks)
y = bytes_to_long(y)
io.sendline(str(y).encode())
io.interactive()
```
Flag : ``` KMACTF{Us1nG_LLL_1s_4n_4rt_f0rm__:)))}```
Sign in with Wallet
Connect another wallet