AES-SIV security

I am invesigating the AES-SIV (rfc 5297) based block cipher. The construction of the S2V is lying on the AES-CMAC and dbl and XOR operation. Given a AAD the size of L and in the 128bit block operation, I have some concern that if the L<16bytes, the initial block with all 0s input is not more than an PRF function to generate the "IV" for the second block operation. My question is whether S2V operation to construct the SIV COULD be reduced to less random due to L<16bytes and in turn defeat the design purpose of Synthesize the IV from packet header. Also it occurs to me AES-SIV need more time and memory to carry out the operation compared to AES-GCM or CCM.

-
For some reason, it's hard to edit my post from my machine. I wanna take back one sentence (S2V looks like a CBC opeation in this case). But all my question is if the AD less than one block, would it reduce IV randomness level? or in another words, the contruction of the unique IV wont pay off when L is less than the key size. Also I think this AES-SIV needs more memory and time compared with AES-GCM or CCM. –  user7453 Jul 12 '13 at 19:15
I'm looking at RFC 5054, and the only search result for "SIV" or "S2V" on that page is a "siv" as $\hspace{.52 in}$ part of "1 and N-1 inclusive". $\:$ However, I am aware of SIV mode, which you might be referring to. $\hspace{.41 in}$ Do you want the last sentence in your post to be replaced with the question in your previous comment? –  Ricky Demer Jul 12 '13 at 21:17
Thanks Ricky! I have re-edited my post as you suggested. This is my first post and I would love to discuss here. I enjoy the questions/answers here everyday :) –  user7453 Jul 13 '13 at 1:53
Is "AES-SIV" just AES is SIV mode? $\:$ If yes, why are you referring to rfc 5054? $\hspace{1.68 in}$ If no, what is "AES-SIV"? $\:$ In either case, what is the "S2V operation"? $\;\;\;$ –  Ricky Demer Jul 13 '13 at 2:08
Oops! Sorry for the mistake, it should be RFC 5297, reading too many RFCs at the same time :) I am referring to the AES running in SIV mode –  user7453 Jul 15 '13 at 7:33

The synthesized IV does not need to be random.

AES-SIV is a deterministic authenticated encryption mode: it can be used without any nonce when it is not a concern if the attacker can tell that the same message is being transmitted (under the same key) multiple times. Privacy and authentication are still guaranteed.

SIV recommends to use a nonce (more precisely, to include it as the second-last string passed to S2V) to cover that scenario. If you do and fail to keep it unique, the effects are still not catastrophic as with modes like GCM and CCM, where privacy is severely compromised.

Typically, keeping a nonce is not easy and it is more practical to use random data, counting on the fact that - by using sufficient randomness - it is sufficiently unlikely to get the same value twice.

To summarize, with SIV:

• Short AAD is not a concern if you don't care about the attacker learning when you send the same message twice.
• If you have the concern above, a short AAD is still OK if it contains a true nonce like a short monotonic counter
• If you have the concern above, a short AAD may be a problem if you use randomness as a nonce. The specification recommends to use at least 16 bytes: using less than that should be carefully vetted.

You are right that SIV is not very efficient. The price to pay to have robustness against nonce-reuse is that SIV is a non-online 2-pass mode. You need to have the whole message in memory to start encryption (unlike GCM) and the plaintext is processed twice (unlike OCB). SIV was proposed as a key-wrapping mode though when keys are typically very small.

-
"...robustness against nonce-reuse is that SIV is a non-online 2-pass mode" - Single pass authenticated encryption is patented in the US and other parts of the world. Two-pass is a must to avoid the minefield. Is two-pass really required for defense against nonce-reuse? –  jww Apr 17 '14 at 2:44
Probably not. One example is McOE though I don't know its patent status and it may not have been reviewed long enough yet. –  SquareRootOfTwentyThree Apr 17 '14 at 5:24