Create a TOTP for machines using HMAC or AES I'm trying to create a sort of Time-based One Time Password (TOTP) where machines are involved (not humans). In this kind of TOTP the step is 15 minutes between one code to the next one and both server and client share the same 256 bit secret key (k).
The message (m) is the current unix timestamp that is known by an attacker so suppose the text plain message m is known.
The key k is always the same and the attacker also knows the algorithm used for cryptography.
I think about two possible solutions for this problem:

HMAC(k,m) using sha256 as base algorithm client side, send the result and check server side that the hash is the same, then ok.
AES(k,m) and send crypted message as base 64 to the server. The server decrypt the message and check the time. If the time is included in accepted range then ok.

Possible scenario:
An attacker knows the plain text (time) and the crypted message (that can be the HMAC hashed text for option 1 or the crypted text after AES for option 2) and have maybe 500 possible combination of textplain plus related encrypted text.
Questions:
Q1: is it possible for the attacker to know the key k before a time range of 5 years for both of options with current computational power?
Q2: Which is the most secure option to use? Option 1 or option 2?
I'm studying these algorithms for days but I haven't find an answer to my questions yet.
Note: I studied TOTP in RFC 6238 too but it seems more related to Machine-human than machine-machine TOTP. For machines, with a 15 minutes step, seems more insecure than the 2 options proposed.
Thanks for everyone can help me in these questions, are making me crazy.
Be reassured: both $\text{HMAC}(k,m)$ [instantiated with a strong hash function, e.g. SHA-512; even SHA-256 would do] and $\text{AES}(k,m)$ [understood as direct encryption of 128-bit $m$ with the block cipher] are believed to be computationally secure Message Authentication Codes for the foreseeable future when the key is 256-bit, irrespective of how many message/cryptogram pairs are available. Both can be truncated: 64-bit would be ample if the verifier limits the attack rate.
$\text{HMAC}$ has the security advantage of being less susceptible to cache-based side channel attacks than $\text{AES}(k,m)$ is, for implementations in software without AES-NI on CPUs with caches.
From a functional perspective, $\text{AES}(k,m)$ has the slight advantage that (if kept 128-bit) it conveys the timestamp $m$, which can be recovered by decryption. Otherwise  we may need to transfer or guess some low bit(s) of the timestamp to fix any drift there may be, especially at startup.
Whatever the MAC, one operational vulnerability is likely to be the establishment and storage of the long-term 256-bit key $k$. There might be other attacks on the protocol, which is not described.