Bug in VMAC-64 implementation making it a weak protocol in some circonstances

[Catageek]

Hello,

I discovered recently a bug in vmac.cpp affecting VMAC-64 and resulting in the repeated use of the same nonce even if the user is providing a proper unique nonce, which opens the possibility of an attack.

The vulnerability is affecting VMAC-64 when using arbitratry nonce, such as a timestamp. Appplications using a counter as nonce are not affected by the vulnerability, but do not conform to the specification (see below).

The bug in in the Resynchronize(const byte* nonce) function. This function executes the PDF algorithm and produces a pad of 128 bit. 2 equal nonces except the LSB bit produce the same pad value, this allows to save an AES operation, The code of the function implements the optimization that consists in comparing the last nonce with the nonce provided by the user (except the LSB bit) and running the PDF algorithm only if they differ, otherwise use the same pad.

The bug is at line 114 of vmac.cpp, here is the code with the diff showing how to fix the bug:
 
--              if (m_padCached && (storedNonce[s-1] | 1) == (nonce[length-1] | 1))
++            if (m_padCached && (m_padCached = (storedNonce[s-1] | 1) == (nonce[length-1] | 1)))
                {
                        m_padCached = VerifyBufsEqual(storedNonce+s-length, nonce, length-1);
                        for (size_t i=0; m_padCached && i<s-length; i++)
                                m_padCached = (storedNonce[i] == 0);
                }      
                if (!m_padCached)
                {              
                        memset(storedNonce, 0, s-length);
                        memcpy(storedNonce+s-length, nonce, length-1);
                        storedNonce[s-1] = nonce[length-1] & 0xfe;
                        AccessCipher().ProcessBlock(storedNonce, m_pad());
                        m_padCached = true;
                }      
                storedNonce[s-1] = nonce[length-1];

The issue is that the result of the comparison (storedNonce[s-1] | 1) == (nonce[length-1] | 1) is not stored in m_padCached. When the result is false, the first block is not executed, but the second block is skipped also, and the pad is not generated. The implementation uses the same pad again and again until the result of the test is true.

Using a counter as nonce, the implementation does not strictly conform to the specifications but the security level is not decreased since a pad is still computed every 2 nonces.

The code below computes the digest of the same message using a different nonce, but the tag produced will be the same:

VMAC<AES,64> hasher;
hasher.SetKeywithIV(key, keylength, nonce0);
std::string msg("test");
hasher.ComputeDigest(digest0, msg, 4);
hasher.Resynchronize(nonce1); // nonce1 ! = nonce0, has no effect
hasher.ComputeDigest(digest1, msg, 4);
// digest0 == digest1

[Jean-Pierre Münch]

Hello Catageek,

thank you for showing this bug.
I'll fix it today and tomorrow you will be able to see the fix live in the CryptoJPM library.
This library will be proposed to be integrated back into Crypto++ soon.
All users VMAC (which isn't widely used I believe)can refer to this thread until then.

BR

JPM

[Jean-Pierre Münch]

bug confirmed.
fix confirmed.
fix implemented.
fix live in CryptoJPM on Github.

BR

JPM

Am Dienstag, 6. Januar 2015 20:50:23 UTC+1 schrieb Catageek: