[Cfrg] Comments on SIV and draft-dharkins-siv-aes-00

Hi Dan,

I'm sorry to take so long in getting back to you.  The new draft looks great
- thanks for carrying it forward.  I have a bunch of comments, some on the
document, and some on SIV itself.

First, a bunch of detailed comments.

The abstract says that " SIV takes a key, a plaintext, and a vector of
data".  I think the term "vector" will not be intuitive to many readers, so
perhaps it would make sense to say that the vector is "an array of
variable-length octet strings", or something like that.  I mean to suggest
that you add text describing what is meant, rather than changing the
terminology from what Phil and Tom wrote.

For the key derivation application (Section 1.3.3), what would the SIV
plaintext input be equal to?  Would it be omitted?

Also, I would guess that SIV-based key derivation would only be appropriate
for deriving keys from a given key, and that it may not be suitable for use
in deriving keys from data that is unpredictable but not uniformly random,
as is used e.g. in Diffie-Hellman.  At least, I believe that this is outside
of the scope of what is claimed in the security analysis, and it would make
sense to document that (after verifying with Phil and Tom).

I think that it might be useful to help explain the vector of inputs by
using an analogy to the POSIX "iovec" or scatter/gather functions readv and
writev; these functions also allow the user to avoid data-marshalling, and
they should be familiar to many implementers.   Of course, the way that
readv and writev work doesn't depend on the way that data is broken into
smaller elements, but SIV does.

Does S2V mean "vector to string"?  Would "V2S" be sensible?

Section 1.3.4 typo - "troughput".  Also, it might be useful to provide the
detail that SIV requires two passes over the data during an encryption
operation, and thus is less suitable for pipelined hardware implementations.

Notation "X10*" - might be notationally clearer to define p(X) as a padding
function, since "X10" looks like a variable name.

I like the compatibility between SIV-CTR and typical CTR implementations.

Sections 3 and 6 define how to use SIV as a nonce-based AEAD, and how to use
it as such in the context of [AEAD].  But I think that a bit more
specificity is needed here.  Section 3 seems to allow multiple "associated
data" inputs, while Section 6 will need to require that there is just a
single AD input.  So I think that Section 3 needs to add a definition that's
specific to the use of SIV together with [AEAD].

Next, some higher-level comments.

First, what's the motivation for key wrapping?   This is an important
question that a lot of people have wrestled with.  I understand from Section
1.3.1 that nonceless AEAD is valuable because there are existing protocols
that do not make use of nonces, so SIV's capability for nonceless AEAD
enables it to be easily adopted by these protocols.   This is a very good
point.  Nonetheless, it does not address the question of "when should a user
use nonceless AEAD?" outside of those "legacy" cases.   I would expect that
we would want to provide guidance that users SHOULD use nonces wherever
possible, but MAY otherwise do without nonces.  (Perhaps there should be an
exception for cases in which determinism is essential, e.g. database
applications in which plaintext-to-ciphertext mapping must be deterministic.
But this is clearly a special case.)

Second, I'm skeptical about the value of the vector input, so I suggest that
more motivation, explanation, and an example usage or two, be added to the
draft.  I'll summarize my skepticism below in the hope that it will be
helpful. 

As I understand it, the two benefits of the vector-input are that it
eliminates the need for the user to marshal multiple inputs into a single
input, and that it offers performance advantages in those cases that there
are repeated invocations of the crypto function in which some of the inputs
remain constant. 

Regarding performance, any AEAD algorithm can be made to support a
scatter/gather or init/update/final interface as per RFC1321.  It is a
conventional technique to copy the intermediate state after an update
operation, and then use it to process different suffixes.   Beyond that,
there are functions that support an "incremental" interface, in the sense of
"Incremental Cryptography and Application to Virus Protection" (27th ACM
Symposium on the Theory of Computing, May 1995).  GMAC, and many other
functions that make use of universal hashing, can be used in this way.  So
it is possible to reap the performance benefit claimed for SIV with some
existing functions, and it's possible to realize the performance advantage
without using a vector of inputs.   As a concrete example, one could replace
the use of AES-CMAC on a vector of inputs in SIV with a polynomial hash
function (such as GHASH, the component of GCM/GMAC) applied to a single
input.  This would allow even *more* performance optimizations (in
particular, it allows optimizations whenever there are repeated invocations
of the crypto function in which *any part* of the input remains constant).

In practice, it seems that these optimizations aren't used so much.  I
believe that the reason is because the additional complexity doesn't seem
warranted when the amount of data that stays the same across invocations is
small compared to the entire data.  FWIW, I do think that there are
applications for incremental message authentication within the area of
security for data-at-rest.

The key derivation example that's used to motivate the vector-of-inputs
points out that in key derivation applications, it is common to have
multiple inputs to the KDF, some of which stay fixed across multiple
invocations of the KDF algorithm.  This is true, though I question the
performance gains, because I suspect that in the KDF case, there are many
small inputs.  I suspect that the vector approach would perform worse than
the standard approach if there were ten one-byte inputs, for example.
Additionally, I wonder why we're that interested in designing SIV to work
well within some existing KDF models (why not just design a dedicated KDF?),
and it seems to me that SIV doesn't actually fit all of the models.  It
seems to not be usable within draft-dang-nistkdf, because SIV requires a key
as a separate and distinct input, which that draft does not provide.  Also,
as noted above, SIV-based KDFs may not be suitable for use in deriving keys
from Diffie-Hellman (or least this use would be outside the "warranty"
provided by the security analysis).

Regarding the need to avoid data marshalling, it is true that in many AEAD
cases, there are multiple data fields that are authenticated.  However, in
most of my experience (e.g. RFCs 4106 and 4543 and IEEE P1619) there is no
data-marshalling issue that needs to be solved, because the fields are
already contiguous, and the lengths of the fields are fixed, so there is no
length-encoding overhead.  In ESP (RFC 4303, not RFC 2406) and SRTP, there
are AD inputs that are not contiguous, but which have fixed lengths; this is
because both of these protocols have an authenticated but unencrypted
header, plus an authenticated "extended sequence number" that holds the
high-order bits of the sequence number, which is not carried in the packet.
For these protocols, an AEAD implementation that supports an
init/update/final interface is sufficient.   Also, in practice these
protocols are often implemented by copying the extended sequence number
field.   Perhaps there are other application areas in which the
data-marshalling before AEAD is onerous - maybe someone can chime in.

On reflection, it seems to me that the enduring advantage for using a vector
of inputs is the fact that it frees the user from the need to explicitly
encode the lengths of the component fields, when those fields have variable
length.  

Of course, applications that make use of the vector-of-inputs feature will
need to define how that vector is constructed, and make sure that the order
of the inputs is well understood.   In addition, if the applications want to
make use of a conventional AEAD method as well, then they will also need to
define a data-marshalling function.

Thirdly, I think it would be useful and interesting to have a comparison
between arbitrary-length pseudorandom permutations with associated data
(such as EME and XCB) and SIV.   But I think that's probably getting beyond
the scope of the SIV draft ;-)

Best regards,

David

_______________________________________________
Cfrg mailing list
Cfrg@ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg