Key expiration policy for 3DES / TDES / Triple DES

I have a system that signs plain text messages using a message authentication code (MAC) encrypted with 3-key Triple DES. The short message is used on connection to establish a session key, so it would take an attacker a long time to compile a lot of plaintext / MAC examples.

I need to establish a key expiration policy that says "keys shall be changed at interval X" to maintain security. What is a reasonable time limit considering only the cryptographic threats?

1. From the reading that I have done, I expect that a brute-force attack (Lucks attack, ref. rfc4772, effective 108 bits) is not practical within the lifetime of the system (30 years) and is not a threat that requires periodic changing of keys. Is this true?

2. There seem to be some attacks that benefit from compiling a lot of plaintext / ciphertext examples. A reasonable key policy would be to change the key before enough examples could be collected. What is a reasonable limit, considering the known attacks on Triple DES? Something I read (edit: http://tools.ietf.org/html/rfc4772) suggested 2^32 blocks was such a limit.

• 1) Which MAC construction are you use? 2) Why choose 3DES over HMAC or even AES? 3) Attacks become likely as you approach 2^32 blocks, you should stay significantly below that value. – CodesInChaos Mar 6 '14 at 17:18
• 1) It is a type of CBC-MAC, but I'm not familiar enough with the literature to know how "standard" or special it is. If you care to read about it, google "Subset-037". Used in train signalling. 2) Good comment, but this is a "legacy" system that I cannot change. 3) The CBC-MAC digests the message in CBC mode and cooks it down to a single block of ciphertext. I assume that this only counts as one block (for purposes of key wear) even if the message is longer. Is that correct? – John Price Mar 11 '14 at 20:10
• I would do "prior to $2^{31}$ blocks of plaintext" between key changes, for the purposes of attacks it is NOT just the last block, but the total encrypted blocks. – Richie Frame Mar 12 '14 at 6:35
• I hope you mean "I have a legacy system with Triple DES" rather than "I am building a system with Triple DES", unless you are being compelled. Incidentally, I believe it has 80 bits of security, from known/chosen plaintext attacks. – Nathan Cooper Mar 12 '14 at 11:36
• @Richie, thanks for your input - 2^31 seems like an appropriate limit also considering the comment from CodesInChaos. One clarification though - the message itself is sent in plain text with only a 64-bit (one block) MAC for authentication. In this way, the message is not "encrypted" but "authenticated" with a single block MAC. However, the entire message (about 5 blocks) is the input to the MAC algorithm. In this way, the MAC is only a single block of "encrypted" text. Would you still interpret the message length as the deciding factor for key wear? – John Price Mar 12 '14 at 14:19