Lattice

Cryptohack.org

LATTICE WRITEUP

Author:

  • Pham Quoc Trung

Used Language:

  • Python3

Problem Solving:

Find the Lattice

As we've seen, lattices contain hard problems which can form trapdoor functions for cryptosystems. We also find that in cryptanalysis, lattices can break cryptographic protocols which seem at first to be unrelated to lattices.

This challenge uses modular arithmetic to encrypt the flag, but hidden within the protocol is a two-dimensional lattice. We highly recommend spending time with this challenge and finding how you can break it with a lattice. This is a famous example with plenty of resources available, but knowing how to spot the lattice within a system is often the key to breaking it.

As a hint, you will be able to break this challenge using the Gaussian reduction from the previous challenge.

Attachments: source.py

from Crypto.Util.number import getPrime, inverse, bytes_to_long
import random
import math

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


def gen_key():
    q = getPrime(512)
    upper_bound = int(math.sqrt(q // 2))
    lower_bound = int(math.sqrt(q // 4))
    f = random.randint(2, upper_bound)
    while True:
        g = random.randint(lower_bound, upper_bound)
        if math.gcd(f, g) == 1:
            break
    h = (inverse(f, q)*g) % q
    return (q, h), (f, g)


def encrypt(q, h, m):
    assert m < int(math.sqrt(q // 2))
    r = random.randint(2, int(math.sqrt(q // 2)))
    e = (r*h + m) % q
    return e


def decrypt(q, h, f, g, e):
    a = (f*e) % q
    m = (a*inverse(f, g)) % g
    return m


public, private = gen_key()
q, h = public
f, g = private

m = bytes_to_long(FLAG)
e = encrypt(q, h, m)

print(f'Public key: {(q,h)}')
print(f'Encrypted Flag: {e}')

output.txt

Đọc qua source code, mình nhận ra đây là NTRU public key cryptosystem. Nôm na cách hoạt động sẽ là như sau:

  1. Alice chọn một số nguyên lớn công khai $p$, cùng với đó là 2 số nguyên bí mật $f$ và $g$ thỏa mãn

    • $f$ < $\sqrt{q/2}$

    • $\sqrt{q/4}$ < $g$ < $\sqrt{q/2}$

    • $gcd(f, qg)$ = 1

  2. Alice tính $h$ $\equiv$ $f^{-1}g$ (mod $q$) với 0 < $h$ < $q$

    Note: $f$, $g$ là nhỏ so với $q$ bởi chúng là $O(\sqrt{q})$. h sẽ lớn bằng $O(q)$.

  3. Bob chọn tin nhắn $m$ và 1 số nguyên ngẫu nhiên $r$ thỏa mãn

    • 0 < $m$ < $\sqrt{q/4}$

    • 0 < $r$ < $\sqrt{q/2}$

  4. Bob mã hóa tin nhắn để gửi cho Alice sử dụng công thức:

    • $e$ $\equiv$ $rh$ + $m$ (mod $q$) với 0 < $e$ < $q$

  5. Alice giải mã tin nhắn bằng cách tính:

    • $a$ $\equiv$ $fe$ (mod $q$) với 0 < $a$ < $q$

    • $b$ $\equiv$ $f^{-1}a$ (mod $g$) với 0 < $b$ < $g$

  6. Để chứng minh $b$ là message của Bob, chúng ta xem xét xem $a$ có thỏa mãn:

    • $a$ $\equiv$ $fe$ $\equiv$ $f(rh + m)$ $\equiv$ $frf^{-1}g + fm$ $\equiv$ $rg + fm$ (mod $q$)

    Giới hạn kích thước của $f,g,r,m$ đảm bảo $rg+fm$ là số nhỏ:

    • $rg + fm$ < $\sqrt{q/2}\sqrt{q/2}$ + $\sqrt{q/2}\sqrt{q/4}$ < $q$

    Vậy nên khi Alice tính $a$ sẽ thu được:

    • $a$ = $rg +fm$

    Đây là điểm mấu chốt vì nó là biểu thức không có sự xuất hiện của module $q$. Cuối cùng, Alice tính:

    • $b$ $\equiv$ $f^{-1}a$ $\equiv$ $f^{-1}(rg + fm)$ $\equiv$ $f^{-1}fm$ $\equiv$ $m$ (mod $g$) với 0 < $b$ < $g$

    Vì $m$ < $\sqrt{q/4}$ < $g$, ta được $b$ = $m$.

Vậy phải tấn công như nào? Chúng ta sẽ tìm cách tính được private key $(f,g)$ thông qua public key $(q, h)$. Trước tiên, ta phải tìm cặp số nguyên $F, G$ thỏa mãn

  • $Fh$ $\equiv$ $G$ (mod $q$) (1)

  • $F$ = $O(\sqrt{q})$

  • $G$ = $O(\sqrt{q})$

Khi đó, $(F, G)$ có thể được sử dụng như khóa giải mã. Viết lại phương trình (1), ta có:

  • $Fh$ = $G$ + $qR$

Từ đó, ta tìm được 2 vecto thỏa mãn:

  • $F(1,h) - R(0,q)$ = $(F,G)$

Với $v1$ = $(1,h)$, $v2$ = $(0,q)$, chúng ta cần tính được short nonzero vector ở trong lattice $L$ = {a1$v1$ + a2$v2$ : a1, a2 $\in$ $Z$}. Ở đây, mình sẽ dùng $LLL$.

https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm

Vậy là xong, áp dụng vô code thôi:

Flag: crypto{Gauss_lattice_attack!}

Backpack Cryptography

I love this cryptosystem so much, I carry it everywhere in my backpack. To lighten the load, I make sure I don't pack anything with high densities.

Attachments: source.py

output.txt

Đây là bài toán Knapsack. Để hiểu hơn, các bạn có thể xem qua link này: https://drx.home.blog/2019/02/24/crypto-he-ma-merkle-hellman/

PreviousElliptic CurveNextStream Ciphers

Last updated