Creating a message authentication scheme

Question

I have such situation. I have a device like dongle. But it has certain limitations. For example, it can only have implemented encryption and decryption functionality.

The availability of ciphers which it can use it can use is also limited. Current option is 3DES.

Now, I need to create a message authentication scheme (which gives both integrity and authenticity) from this situation. I know ideally HMAC, CBC-MAC, should be used, but we don't have that situation.

I am interested would such option be considered a somewhat secure MAC:

1. I want to authenticate message M
2. I apply hash on message M say SHA1, e.g. M' = SHA1(M). This I do from my PC which is more powerful than my dongle, HASP.

3. I feed the device-HASP, with M' (there is an issue here, please see below), it encrypts it with a key, e.g.,

   TAG = 3DES_ECB_ENCRYPT(M', KEY)

The 3rd step is done because to avoid sending lot of data to the device.

My TAG is the authentication tag, which I will send together with message M. This is the scheme basically:

My problems and questions are:

• You know 3DES block size is 8 bytes, how can I feed it with output of SHA1 (in a secure way) which is 20 bytes? Or what workaround exists for it?
• How secure is my MAC?

I know this is not the most secure, but like I said we have some limitations, and are ok with it if it is not catastrophic mac scheme. e.g. our current MAC was just DEC ECB encryption, of XORED plain text. So now instead of XOR ing plain text blocks between each other we use SHA1. Old scheme is described here.

PS. Similar approach is mentioned here: https://cseweb.ucsd.edu/~mihir/cse207/w-mac.pdf, but there whole plain text is given to encryption function, here I can't do that - I can't give 200 bytes of data say to the dongle, that is why I want to hash it first, and give smaller amount of data to the device

Answer 1

Doing this would not be secure.

1. If you truncate the SHA-1 to 64 bits before encryption, then anyone can find a collision in about $2^{32}$ tries (taking minutes on a desktop CPU), and by finding the encryption of one message hash also learn the other. Even a second preimage attack may be feasible.
2. If you use ECB mode to encrypt a longer hash, then the attacker can attack it "piece by piece", finding one hash value that collides with several block-aligned parts of earlier hashes. This is more difficult than finding a 64-bit collision, but much easier than finding a full collision.

The best you could hope for would be somewhere between 60- and 70-bit security (collision search on full SHA-1), but that would require better encryption/MAC on the hash, and would be more complex than simply implementing HMAC or CBC-MAC.

---

If the dongle can do (semi-)arbitrary things with 3DES and the PC can do arbitrary things, then I would recommend:

1. Using a longer hash, e.g. SHA-256, on the PC: $h = H(m)$
2. Using a block cipher-based MAC on the device on the hash: $t = M(k, h)$.

That gives you the weaker of:

1. the collision resistance of the hash (128 bits for SHA-256) and
2. the security of the MAC.

The block cipher based MAC could be e.g. CBC-MAC. That is simple enough and with SHA-256 you would only need to process four blocks on the device itself.