forbidden_attack.py

# Adapted from https://github.com/jvdsn/crypto-attacks/blob/master/attacks/gcm/forbidden_attack.py
# and https://github.com/jvdsn/crypto-attacks/blob/master/test/test_gcm.py

from sage.all import GF
import requests

x = GF(2)["x"].gen()
gf2e = GF(2 ** 128, name="y", modulus=x ** 128 + x ** 7 + x ** 2 + x + 1)


# Converts an integer to a gf2e element, little endian.
def _to_gf2e(n):
    return gf2e([(n >> i) & 1 for i in range(127, -1, -1)])


# Converts a gf2e element to an integer, little endian.
def _from_gf2e(p):
    n = p.integer_representation()
    ans = 0
    for i in range(128):
        ans <<= 1
        ans |= ((n >> i) & 1)

    return ans


# Calculates the GHASH polynomial.
def _ghash(h, a, c):
    la = len(a)
    lc = len(c)
    p = gf2e(0)
    for i in range(la // 16):
        p += _to_gf2e(int.from_bytes(a[16 * i:16 * (i + 1)], byteorder="big"))
        p *= h

    if la % 16 != 0:
        p += _to_gf2e(int.from_bytes(a[-(la % 16):] + bytes(16 - la % 16), byteorder="big"))
        p *= h

    for i in range(lc // 16):
        p += _to_gf2e(int.from_bytes(c[16 * i:16 * (i + 1)], byteorder="big"))
        p *= h

    if lc % 16 != 0:
        p += _to_gf2e(int.from_bytes(c[-(lc % 16):] + bytes(16 - lc % 16), byteorder="big"))
        p *= h

    p += _to_gf2e(((8 * la) << 64) | (8 * lc))
    p *= h
    return p


def recover_possible_auth_keys(a1, c1, t1, a2, c2, t2):
    """
    Recovers possible authentication keys from two messages encrypted with the same authentication key.
    More information: Joux A., "Authentication Failures in NIST version of GCM"
    :param a1: the associated data of the first message (bytes)
    :param c1: the ciphertext of the first message (bytes)
    :param t1: the authentication tag of the first message (bytes)
    :param a2: the associated data of the second message (bytes)
    :param c2: the ciphertext of the second message (bytes)
    :param t2: the authentication tag of the second message (bytes)
    :return: a generator generating possible authentication keys (gf2e element)
    """
    h = gf2e["h"].gen()
    p1 = _ghash(h, a1, c1) + _to_gf2e(int.from_bytes(t1, byteorder="big"))
    p2 = _ghash(h, a2, c2) + _to_gf2e(int.from_bytes(t2, byteorder="big"))
    for h, _ in (p1 + p2).roots():
        yield h


def forge_tag(h, a, c, t, target_a, target_c):
    """
    Forges an authentication tag for a target message given a message with a known tag.
    This method is best used with the authentication keys generated by the recover_possible_auth_keys method.
    More information: Joux A., "Authentication Failures in NIST version of GCM"
    :param h: the authentication key to use (gf2e element)
    :param a: the associated data of the message with the known tag (bytes)
    :param c: the ciphertext of the message with the known tag (bytes)
    :param t: the known authentication tag (bytes)
    :param target_a: the target associated data (bytes)
    :param target_c: the target ciphertext (bytes)
    :return: the forged authentication tag (bytes)
    """
    ghash = _from_gf2e(_ghash(h, a, c))
    target_ghash = _from_gf2e(_ghash(h, target_a, target_c))
    return (ghash ^ int.from_bytes(t, byteorder="big") ^ target_ghash).to_bytes(16, byteorder="big")


# UPDATE HERE
# use python bytes for the data (ex: b"\x00\x01\x02")
ct1 = b"..."
t1 = b"..."
ad1 = b"..."
nonce1 = b"..."

ct2 = b"..."
t2 = b"..."
ad2 = b"..."
nonce2 = b"..." # not used, should be the same as nonce1

ct3 = b"..."
ad3 = b"..."

print("ct1 =", ct1.hex())
print("t1 =", t1.hex())
print("ad1 =", ad1.hex())
print()

print("ct2 =", ct2.hex())
print("t2 =", t2.hex())
print("ad2 =", ad2.hex())
print()

print("ct3 =", ct3.hex())
print("ad3 =", ad3.hex())
print()

for h in recover_possible_auth_keys(ad1, ct1, t1, ad2, ct2, t2):
    t3 = (forge_tag(h, ad1, ct1, t1, ad3, ct3))

    print("potential t3 =", t3.hex())