#!/usr/bin/env python3
"""Reproduce the NXP AN12196 Secure Dynamic Messaging examples from scratch.

WHY THIS EXISTS
nfcdoc.com/sdm prints hexadecimal from NXP AN12196 and says the numbers were
recomputed rather than transcribed. This is the recomputation. It implements
AES-128 and AES-CMAC in pure Python with no dependencies, checks that
implementation against the FIPS 197 and RFC 4493 published test vectors first,
and only then reproduces the application note's worked examples.

Run it:   python verify_sdm.py
Exit 0 means every number on that page still checks out. If a number on the
page is ever changed, change it here too, or the page is no longer checkable.
"""
import sys
try:
    sys.stdout.reconfigure(encoding="utf-8", errors="replace")
except Exception:
    pass

# ---- AES-128 ---------------------------------------------------------------
SBOX = []
def _init_sbox():
    p = q = 1
    sbox = [0] * 256
    while True:
        p = p ^ ((p << 1) & 0xFF) ^ (0x1B if p & 0x80 else 0)
        q ^= q << 1; q ^= q << 2; q ^= q << 4; q &= 0xFF
        if q & 0x80:
            q ^= 0x09
        x = q ^ ((q << 1) | (q >> 7)) ^ ((q << 2) | (q >> 6)) \
              ^ ((q << 3) | (q >> 5)) ^ ((q << 4) | (q >> 4))
        sbox[p] = (x ^ 0x63) & 0xFF
        if p == 1:
            break
    sbox[0] = 0x63
    return sbox
SBOX = _init_sbox()
INV_SBOX = [0] * 256
for _i, _v in enumerate(SBOX):
    INV_SBOX[_v] = _i
RCON = [0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1B, 0x36]


def xtime(a):
    a <<= 1
    return (a ^ 0x1B) & 0xFF if a & 0x100 else a


def mul(a, b):
    r = 0
    while b:
        if b & 1:
            r ^= a
        a = xtime(a)
        b >>= 1
    return r


def expand_key(key):
    assert len(key) == 16
    w = [list(key[i * 4:i * 4 + 4]) for i in range(4)]
    for i in range(4, 44):
        t = list(w[i - 1])
        if i % 4 == 0:
            t = t[1:] + t[:1]
            t = [SBOX[b] for b in t]
            t[0] ^= RCON[i // 4 - 1]
        w.append([w[i - 4][j] ^ t[j] for j in range(4)])
    return [sum(w[4 * r:4 * r + 4], []) for r in range(11)]


def _add_rk(s, rk):
    return [s[i] ^ rk[i] for i in range(16)]


def _sub(s, box):
    return [box[b] for b in s]


def _shift(s):
    o = list(s)
    for r in range(1, 4):
        row = [s[r + 4 * c] for c in range(4)]
        row = row[r:] + row[:r]
        for c in range(4):
            o[r + 4 * c] = row[c]
    return o


def _inv_shift(s):
    o = list(s)
    for r in range(1, 4):
        row = [s[r + 4 * c] for c in range(4)]
        row = row[-r:] + row[:-r]
        for c in range(4):
            o[r + 4 * c] = row[c]
    return o


def _mix(s, m):
    o = [0] * 16
    for c in range(4):
        col = s[4 * c:4 * c + 4]
        for r in range(4):
            o[4 * c + r] = (mul(col[0], m[r][0]) ^ mul(col[1], m[r][1])
                            ^ mul(col[2], m[r][2]) ^ mul(col[3], m[r][3]))
    return o


MIX = [[2, 3, 1, 1], [1, 2, 3, 1], [1, 1, 2, 3], [3, 1, 1, 2]]
INV_MIX = [[14, 11, 13, 9], [9, 14, 11, 13], [13, 9, 14, 11], [11, 13, 9, 14]]


def _to_state(b):
    return [b[4 * c + r] for c in range(4) for r in range(4)]


def aes_encrypt_block(key, block):
    rk = expand_key(key)
    s = _add_rk(list(block), rk[0])
    for rnd in range(1, 10):
        s = _sub(s, SBOX)
        s = _shift(s)
        s = _mix(s, MIX)
        s = _add_rk(s, rk[rnd])
    s = _sub(s, SBOX)
    s = _shift(s)
    s = _add_rk(s, rk[10])
    return bytes(s)


def aes_decrypt_block(key, block):
    rk = expand_key(key)
    s = _add_rk(list(block), rk[10])
    for rnd in range(9, 0, -1):
        s = _inv_shift(s)
        s = _sub(s, INV_SBOX)
        s = _add_rk(s, rk[rnd])
        s = _mix(s, INV_MIX)
    s = _inv_shift(s)
    s = _sub(s, INV_SBOX)
    s = _add_rk(s, rk[0])
    return bytes(s)


def aes_cbc_decrypt(key, iv, data):
    out = b""
    prev = iv
    for i in range(0, len(data), 16):
        blk = data[i:i + 16]
        out += bytes(a ^ b for a, b in zip(aes_decrypt_block(key, blk), prev))
        prev = blk
    return out


# ---- AES-CMAC, NIST SP 800-38B --------------------------------------------
def _dbl(b):
    n = int.from_bytes(b, "big") << 1
    n ^= 0x87 if b[0] & 0x80 else 0
    return (n & ((1 << 128) - 1)).to_bytes(16, "big")


def cmac(key, msg):
    L = aes_encrypt_block(key, b"\x00" * 16)
    k1 = _dbl(L)
    k2 = _dbl(k1)
    if len(msg) and len(msg) % 16 == 0:
        blocks = [msg[i:i + 16] for i in range(0, len(msg), 16)]
        last = bytes(a ^ b for a, b in zip(blocks[-1], k1))
        blocks = blocks[:-1]
    else:
        pad = msg + b"\x80" + b"\x00" * (15 - len(msg) % 16)
        blocks = [pad[i:i + 16] for i in range(0, len(pad), 16)]
        last = bytes(a ^ b for a, b in zip(blocks[-1], k2))
        blocks = blocks[:-1]
    x = b"\x00" * 16
    for blk in blocks:
        x = aes_encrypt_block(key, bytes(a ^ b for a, b in zip(x, blk)))
    return aes_encrypt_block(key, bytes(a ^ b for a, b in zip(x, last)))


def mact(key, msg):
    """AN12196 MACt: keep S14||S12||...||S0, i.e. bytes 1,3,5..15 of the CMAC."""
    full = cmac(key, msg)
    return bytes(full[i] for i in range(1, 16, 2))


H = bytes.fromhex
ok = True


def check(label, got, want):
    global ok
    g = got.hex().upper() if isinstance(got, bytes) else str(got).upper()
    w = want.upper().replace(" ", "")
    good = g == w
    ok = ok and good
    print(("  PASS  " if good else "  FAIL  ") + label)
    if not good:
        print("          got  " + g)
        print("          want " + w)


print("AES-128 sanity (FIPS-197 C.1)")
check("AES-128 encrypt",
      aes_encrypt_block(H("000102030405060708090a0b0c0d0e0f"),
                        H("00112233445566778899aabbccddeeff")),
      "69c4e0d86a7b0430d8cdb78070b4c55a")

print("\nAES-CMAC sanity (RFC 4493)")
K = H("2b7e151628aed2a6abf7158809cf4f3c")
check("CMAC, empty message", cmac(K, b""), "bb1d6929e95937287fa37d129b756746")
check("CMAC, 16-byte message",
      cmac(K, H("6bc1bee22e409f96e93d7e117393172a")),
      "070a16b46b4d4144f79bdd9dd04a287c")
check("CMAC, 40-byte message",
      cmac(K, H("6bc1bee22e409f96e93d7e117393172a"
                "ae2d8a571e03ac9c9eb76fac45af8e51"
                "30c81c46a35ce411")),
      "dfa66747de9ae63030ca32611497c827")

print("\nAN12196 Table 1, section 3.3  SDM session key generation")
k_file = H("5ACE7E50AB65D5D51FD5BF5A16B8205B")
uid = H("04C767F2066180")
ctr = H("010000")
sv1 = H("C33C00010080") + uid + ctr
sv2 = H("3CC300010080") + uid + ctr
check("SV1 as built", sv1, "C33C0001008004C767F2066180010000")
check("SV2 as built", sv2, "3CC30001008004C767F2066180010000")
check("KSesSDMFileReadENC", cmac(k_file, sv1), "66DA61797E23DECA5D8ECA13BBADF7A9")
check("KSesSDMFileReadMAC", cmac(k_file, sv2), "3A3E8110E05311F7A3FCF0D969BF2B48")

print("\nAN12196 Table 2, section 3.4.2.2  PICCData decryption")
zero = b"\x00" * 16
picc_enc = H("EF963FF7828658A599F3041510671E88")
picc = aes_cbc_decrypt(zero, zero, picc_enc)
check("decrypted PICCData", picc, "C704DE5F1EACC0403D0000DA5CF60941")
print("          PICCDataTag  %02X  (bit7 UID mirrored, bit6 ctr mirrored, "
      "bits3-0 UID length = %d)" % (picc[0], picc[0] & 0x0F))
print("          UID          %s" % picc[1:8].hex().upper())
print("          SDMReadCtr   %s  = %d decimal, LSB first"
      % (picc[8:11].hex().upper(), int.from_bytes(picc[8:11], "little")))

print("\nAN12196 Table 4, section 3.4.4.2.1  SDMMAC, MAC input offset == MAC offset")
sv2b = H("3CC300010080") + picc[1:8] + picc[8:11]
check("SV2 as built", sv2b, "3CC30001008004DE5F1EACC0403D0000")
kses = cmac(zero, sv2b)
check("KSesSDMFileReadMAC", kses, "3FB5F6E3A807A03D5E3570ACE393776F")
check("SDMMAC over zero-length input", mact(kses, b""), "94EED9EE65337086")
# nfcdoc.com/sdm prints this full CMAC to show that the surviving bytes are not
# a prefix of it. Asserted here so the page cannot drift from the arithmetic.
check("full CMAC behind that signature", cmac(kses, b""),
      "E194C7EE12D9F7EE8A65C8331B704386")
print("          URL: https://ntag.nxp.com/424?e=%s&c=%s"
      % (picc_enc.hex().upper(), mact(kses, b"").hex().upper()))

# AN12196 section 3.4.1 also shows a plain identifier and counter mirror,
#   https://ntag.nxp.com/424?uid=04C767F2066180&ctr=000001&c=54A45B2C3A558765
# but the note does not disclose the key that produced that signature, so it
# cannot be recomputed. Tried here against the all-zero delivery key and the
# Table 1 key, with the counter in both byte orders: none reproduce it. The
# page therefore does not reprint it as a verified example. Nothing to assert.

print("\nAN12196 Table 5, section 3.4.4.2.2  MAC input offset != MAC offset")
picc_enc2 = H("FD91EC264309878BE6345CBE53BADF40")
picc2 = aes_cbc_decrypt(zero, zero, picc_enc2)
check("decrypted PICCData", picc2, "C704958CAA5C5E80080000A243C86DFC")
sv2d = H("3CC300010080") + picc2[1:8] + picc2[8:11]
check("SV2 as built", sv2d, "3CC30001008004958CAA5C5E80080000")
kses2 = cmac(zero, sv2d)
check("KSesSDMFileReadMAC", kses2, "3ED0920E5E6A0320D823D5987FEAFBB1")
mac_input = b"CEE9A53E3E463EF1F459635736738962&cmac="
check("MAC input, ASCII bytes", mac_input,
      "434545394135334533453436334546314634353936333"
      "537333637333839363226636D61633D")
check("SDMMACfull", cmac(kses2, mac_input), "81EC45C175E72FF6FAC61BC7AB3BAEF6")
check("SDMMAC truncated", mact(kses2, mac_input), "ECC1E7F6C6C73BF6")

print("\nTruncation check: which CMAC bytes survive MACt")
full = H("81EC45C175E72FF6FAC61BC7AB3BAEF6")
print("          full  " + " ".join("%02X" % b for b in full))
print("          kept  " + " ".join(
    ("%02X" % b) if i % 2 else "..." for i, b in enumerate(full)))
print("          -> bytes at index 1,3,5,7,9,11,13,15, MSB first")

print("\n" + ("ALL CHECKS PASSED" if ok else "SOMETHING FAILED"))
sys.exit(0 if ok else 1)