I can't understand HMAC enough to know whether it solves it, but there seems to be a trade-off between keeping it secure and introducing randomness and making people do lookups on the other end (which would have been super slow then, and I don't know how feasable hash tables are when dealing with punchcards)
Why is encryption weak due to the simple pattern of increasing numbers? Encrypting increasing numbers is how CTR and GCM mode work; those are arguably some of the best modes of operation we have commonly available.
A MAC of a message m can only be computed with the knowledge of a key K. Specifically, with a cryptographic hash function h,
HMAC(K, m) = h(K + a || h(K + b || m)),
where + is addition mod 2 (xor), || is concatenation and a and b are constants. (This construction takes into account possible length extension attacks on h.)
Given that h is secure, knowledge of any reasonable number of pairs (m, HMAC(K, m)) does not allow you to recover K, and without K, you cannot compute HMAC(K, m) for known m, i.e. enumerate all the possible MACs for serial numbers.
http://en.wikipedia.org/wiki/German_tank_problem#Countermeas... http://en.wikipedia.org/wiki/Known-plaintext_attack
I can't understand HMAC enough to know whether it solves it, but there seems to be a trade-off between keeping it secure and introducing randomness and making people do lookups on the other end (which would have been super slow then, and I don't know how feasable hash tables are when dealing with punchcards)