Subject: Questions on AuthenticatedData

From: "Jim Schaad" <[email-masked]>
Date: Sun, 7 Oct 2001 17:56:58 -0700

I have just started an implemenation for AutenticatedData and have the
following questions:

1.  Should we specify a suggested size for the randomly generated secret
to be used for HMAC-SHA1?  (The size for HMAC-3DES is fixed at the size
of a 3DES key.)

2.  What key wrap algorithm should I use for wrapping the secret for an
HMAC-SHA1 secret?  I can see myself generating a 512 bit secret for the
MAC operation, now I need to wrap it in a 3DES, RC2 or AES key.  What is
the proper way of doing this?

3.  Does the answer for 2 imply that we want the lengths for 1 to be the
length of a defined content encrytion algorithm key?

Jim

---

From: [email-masked] (Peter Gutmann)
Date: Mon, 8 Oct 2001 18:23:37 +1300 (NZDT)

"Jim Schaad" <[email-masked]> writes:

>Can you give a few places where this is the convention?  It seems counter to
>what would be intuitive looking at the Microsoft APIs.  This does not mean
>that you are not correct, I was just wondering.

Well, there are three major protocols which use HMAC, namely IPsec, SSL/TLS,
and SSHv2 (aka "SSL done with SSH packet formats").  If macSize is the size of
the generated MAC (128 bits for HMAC-MD5, 160 bits for HMAC-SHA) then SSL uses
a key of size macSize, SSHv2 uses a key of size macSize, and I dunno about
IPsec (the RFCs are silent on this, and I've never implemented it so I don't
know what people use).

Peter.

---

From: [email-masked] (Peter Gutmann)
Date: Mon, 8 Oct 2001 23:21:19 +1300 (NZDT)

>IPsec (the RFCs are silent on this, and I've never implemented it so I don't

Before this ends up in a spec somewhere as "Anyone who doesn't use a <macSize>
key will be banished to van Diemens Land with only an ASN.1 dump for
companionship", does it actually matter what key size you use?  Since you can
wrap arbitrary-length keys, you could certainly include an implementation note
to say that the convention is to use keys of size <macSize>, but there's
nothing to prevent you from using keys of other lengths (the SSHv2 spec
actually requires the use of 128-bit keys, but I guess the <SSH-the-company>
implementation used 160-bit keys and everyone copied that).  In fact the only
reason that SSL/TLS and SSHv2 specify a size is because their key derivation
process performed after the key exchange part of the protocol handshake
generates a whole pile of keying material and it's necessary to fix where one
key stops and the next one starts.  This isn't an issue with CMS.

In fact if you're using a 128-bit AES key from (say) a KeyTransRecipientInfo to
MAC and encrypt you'd use 128 bits, if you're using a 3DES key it's your choice
between 160 and 192 bits, if all you've got is 64 bits you'd use that.  There's
no reason to restrict the choice, particularly since you can't control where
the keying material is coming from.

(Just looking at my own code, I use 128-bit keys for all the HMACs if the user
 doesn't specify otherwise, mostly because it's "the standard", but they can
 specify anything from 40 to INT_MAX or thereabouts if they want and it still
 works).

Peter.

---

From: "Daniel Brown" <[email-masked]>
Date: Mon, 22 Oct 2001 14:47:50 -0400

Hi Jim,

I suggest the following answers to your questions, in the case
of HMAC-SHA1 and CMS-3DES-WRAP.

1.  We should specify the HMAC-SHA1 key size to be 160 bits (the
strength of HMAC-SHA1).

2.  When wrapping with 3DES, a 192-bit key is expected, so pad with
the HMAC-SHA1 key 32 zero bits (which gives an equivalent 192-bit
HMAC-SHA1 key).

3. No.

These answers need adjustments for other key wrap and
MAC algorithms.

Reasoning and further details are given below.

Recall that, as Simon, Paul and I noted in our Internet-Draft "Use of
ECC Algorithms in S/MIME", if AuthenticatedData uses two or more
RecipinientInfo's, then there is a serious problem.  Say R1 and
R2 are the recipients, the message is M and the MAC key is K.  Since
R2 receives K, receiver R2 can use it to compute MAC_K(M') for a bogus
message M' and then send a bogus AuthenticatedData to R1, using the
Wrap_R1(K) already present in the original AuthenticatedData.  R1
would think M' originated from the sender even though it originated
from R2.  Once R2 sees K and Wrap_R1(K), R2 can repeat this attack as
often as necessary.  Thus, our I-D recommends just one RecipientInfo
per AuthenticatedData.

Now, a similar attack might apply if a weak MAC key is used.  In an
extreme case, suppose a sender S sends an AuthenticatedData to a
receiver R using a 1-bit MAC key.  An adversary A knowing about the
1-bit key can guess the MAC key, confirm its guess, and then launch
the above attack.  This works no matter how strong the key management
and wrap algorithms, because A knows once K and Wrap_R(K), A can send
any message to the receiver R in an AuthenticatedData appearing to be
from S.

If 10-bit MAC key is used, then the attacker has to guess 512 MAC keys
on average.  If a 40-bit MAC key is used, the sender must guess 2^39
MAC keys on average.  Although it is probably impractical, once the
guess is made, the attacker can forge as many AuthenticatedData's as
desired.  Thus the effective strength of AuthenticatedData is limited
by the smallest MAC key size used.

In fact, in the multi-user setting where 40-bit MAC keys are used,
after about 2^20 messages, one expects identical MAC keys to have been
used.  This might also lead to problems.

Thus, I think a minimum HMAC-SHA1 key length should be set.  Perhaps
80 bits is enough, but I don't know.  Clearly, 160 bits would be
safer.

The minimum key size should be a MUST or SHOULD for the sender.
I realize some implementations may prefer a 128-bit key generator, but
this might be a little low.

It could be a SHOULD for the receiver, except that one has to be careful about
ascertaining the length of the key.  Suppose the sender selects a
random 160 bit key K, but due to pure chance, the last 8 bits are
zero.  This could happen with 1 in 256 chance.  Should the receiver
reject this because it looks like a small key (152 bits)?  Probably
not.

One possible exception to the minimum could be the following.  If a
key-wrap algorithm Wrap40 only supports 40 bits, then a 40-bit
HMAC-SHA1 K40 could be used.  The guessing attack can still be
launched, but all the forged AuthenticatedData's would contain K40 and
Wrap40(K40).  It does not seem possible to generate Wrap192(K40), so
the attack does not allow forgery of high-strength AuthenticatedData's
(assuming the wrap algorithm is secure).

My preference would be adapt such a Wrap40 to allow wrapping of
longer MAC keys using 40bit encryption.

Finally, larger key sizes would not hurt, but do not seem to help,
according to the RFC on HMAC-SHA1.  Key sizes 193-512 cannot be
wrapped with the current 3DES algorithm, but key sizes 513 and larger
can be because they are hashed to 160 bits first accoring to the
way HMAC-SHA1 is defined.

Thanks,

Dan

"Jim Schaad" <[email-masked]> on 10/07/2001 08:56:58 PM

Please respond to [email-masked]

To:   [email-masked]
cc:    (bcc: Daniel Brown/Certicom)
Subject:  Questions on AuthenticatedData

Jim