Manger's Attack

manger.py

from Crypto.Util.number import getPrime, getRandomInteger, long_to_bytes


# ceil(numerator / denominator)
def frac_ceil(numerator, denominator):
    if numerator % denominator == 0:
        return numerator // denominator
    return numerator // denominator + 1


def generate_keys(nbit=512):
    p = getPrime(nbit)
    q = getPrime(nbit)
    n = p*q
    phi = (p-1)*(q-1)
    e = 65537
    d = pow(e,-1, phi)

    return ((n,e), (n,e,d,p,q))


def generate_oracle(privkey):
    n, _, d, _, _ = privkey
    k = len(long_to_bytes(n))
    B = 2**(8*(k-1))

    return lambda x: pow(x, d, n) < B


def attack(c, pubkey, oracle):
    # prepare parameters
    n, e = pubkey
    k = len(long_to_bytes(n))
    B = 2**(8*(k-1))

    if n < 2*B:
        raise ValueError("Failed...")

    # step1
    print("[+] Step1")
    f1 = 2
    while True:
        x = pow(f1, e, n) * c % n
        if oracle(x):
            f1 = 2*f1
        else:
            break

    print("[+] f1 =", f1)

    # step2
    print("[+] Step2")
    f2 = (n+B) // B * f1 // 2
    while True:
        x = pow(f2, e, n) * c % n
        if oracle(x):
            break
        else:
            f2 = (f2 + f1 // 2)

    print("[+] f2 =", f2)

    # step3
    print("[+] Step3")
    m_max = (n+B) // f2
    m_min = frac_ceil(n, f2)

    cnt = 0

    while True:
        cnt += 1
        f_tmp = 2*B // (m_max - m_min)
        i = f_tmp * m_min // n
        f3 = frac_ceil(i*n, m_min)
        x = pow(f3, e, n) * c % n
        if oracle(x):
            m_max = (i*n + B) // f3
        else:
            m_min = frac_ceil(i*n + B,f3)

        print(f"[{cnt}] width of m:", m_max - m_min)
        if m_max - m_min == 0:
            break

    print(cnt)

    return m_max



if __name__ == "__main__":
    print("[+] Generating key...")
    pubkey, privkey = generate_keys(1024)
    n,e = pubkey
    k = len(long_to_bytes(n))

    oracle = generate_oracle(privkey)

    # assumption: `m` is valid plain text on PKCS #1 ver2.0
    m = getRandomInteger(8*(k-1))
    c = pow(m, e, n)
    assert oracle(c)

    try:
        _m = attack(c, pubkey, oracle)
    except:
        print("[+] Attack is not effective to this public keys")

    assert _m == m
    print("[+] recovered message:", _m)
    print("[+] True message:", m)
    print("[+] End")