Subject: Crypto-oriented comments on x942-04

From: "Linn, John" <[email-masked]>
Date: Wed, 13 Jan 1999 13:30:42 -0500

Per Russ' solicitation for review of smime-x942-04 by cryptographers, I'm
forwarding the attached comments provided to me by Burt Kaliski and Yiqun
Lisa Yin of RSA Laboratories. 

--jl

1. In general, the draft is a nice condensation of the ANSI X9.42 draft into
IETF S/MIME terms.

2. ANSI X9.42 is still an unapproved draft, and should be cited as such, not
as a standard.

3. The shared secret value ZZ is sometimes called a shared secret number.
"Value" would be better throughout, since in more general settings, ZZ is a
finite field element, not a number (integer).

4. Section 2.1.1: An operator is missing in the definitions of g and h,
which should be

  g = h^{(p-1)/q} mod p ...
  h is any integer ... such that h^{(p-1)/q} ...

In this definition, it could be clarifying to state that the parameters are
(p,q,g) and to change the order of definitions to:
	p is a large prime
	q is a large prime such that p = qj+1 for some larger integer j
	g = h^{(p-1)/q} mod p where ...

Further, it may be helpful to explain that "g has order q mod p" means that
g^q mod p = 1, if g <> 1 and q is prime. 

5. Section 2.1.2: In Section 2.1.1, ZZ is a field element or integer, so
some conversion to an octet string is required. The usual conversion,
following IEEE P1363 and ANSI X9.42, is a most significant byte first
representation. ANSI X9.42 specifies that the result has as few bytes as
possible (i.e., no leading zeros); IEEE P1363 says that the result has the
same length in octets as the longest field element (i.e., the length of the
prime p), with leading zeros. So, there's an apparent IEEE P1363 vs. ANSI
X9.42 discrepancy. Given that IEEE P1363 is currently in ballot and ANSI
X9.42 needs to be recirculated, we'd recommend that IEEE P1363 be followed.
In any case, some representation should be stated. Also, the comment "the
security of this data is limited to the size of ZZ" is not accurate. The
security is related to the size of p and q. A large ZZ doesn't imply
security by itself.

6. Section 2.1.2: Editorial: Change "shared key" to "shared secret value".

7. Section 2.1.2: Identifying an algorithm by an OID rather than an
AlgorithmID risks losing some specifics about the algorithm. For instance,
in a variable-key-size block cipher (e.g., RC5), the AlgorithmID carries the
key size, so this information would be lost. As a result, it may be possible
for an opponent to substitute a key of one size for a key of a different
size, which may lead to an attack that recovers the key one part at a time.
Presumably, the reason for avoiding a full AlgorithmID is that some of its
parameters are message-specific, such as IVs, but perhaps there is some
middle ground. Including the key size as an optional field of OtherInfo is
one possibility. Other parameters that will be lost in the case of RC5 are
the block size and the number of rounds.

8. Section 2.1.2: "Parameters" is misspelled in the definition of the
algorithm field.

9. Section 2.1.2: Some additional explanation would be helpful about the
relationship between KM and a KEK. In particular, the text might say that to
generate a KEK, one generates one or more KMs from the same ZZ, where
OtherInfo varies. The variable part of OtherInfo is keyInfo; pubInfo remains
the same.

Having noted this, the field selections and names seem inappropriate: the
fact that keyInfo varies for a given key is contradictory. A preferable
organization would be to have keyInfo include the algorithm and optional
pubInfo, and put the counter in a field of its own, called keyPart, as in:

  OtherInfo ::= SEQUENCE {
    keyInfo KeySpecificInfo,
    keyPart INTEGER(1..2^32-1) }

  KeySpecificInfo ::= SEQUENCE {
    algorithm OBJECT IDENTIFIER,
    pubInfo OCTET STRING OPTIONAL,
    keySize INTEGER OPTIONAL }

10. Section 2.1.2: Why can't counter be an INTEGER? That would avoid the
unnecessary definition of an encoding format for the counter, while
maintaining an unambiguous encoding.

11. Section 2.1.2: Why must pubInfo, if present, contain a minimum of 512
bits? A minimum of 160 bits is sufficient to avoid collisions; the encoding
as an OCTET STRING is unambiguous and prevents length-extension attacks.
Also, random or nonce might be a better name, since all of otherInfo, not
just pubInfo, is public.

12. In general, the different terms for byte ordering should be harmonized
or adopted from some other standard: "leftmost", "network byte order", etc.

13. Section 2.1.3: KEK computation states that each algorithm requires a
specific size key. But some algorithms have variable-size keys, and it's
possible that future algorithms will require more than just a random string
(e.g., more structure). So, it would be preferable to say that the currently
proposed S/MIME algorithms assume a random string, perhaps with parity
changes.

14. Section 2.1.5: Editorial: Change "received public keys" to "a received
public key y".

Also, add a reference to IEEE P1363 security considerations for more
discussion on public-key validation.

15. Section 2.1.6: This 16-byte example doesn't comply with the draft's
160-bit minimum (Section 2.2).

16. Section 2.2: Should a lower bound on the prime p also be given? Why is
there a 160-bit minimum on q? (Note that the 128-bit minimum in the same
paragraph is inconsistent.) Also, a minimum size on the private key x is
inconsistent with saying that x is in the interval [2,q-2].

The first paragraph of this section is missing a parenthesis.

Per Sec. 2.2.1.1, we believe that it would be appropriate for the document
to state explicitly that alternate parameter generation algorithms MAY be
used; P1363 can be cited for discussion. Per Sec. 2.2.1.1, step 6, it would
be useful to give a reference to what primality algorithm(s) can be used. 

17. Sections 2.3 and 2.4: Key validation is not the only way to prevent a
small-subgroup attack. Another method is cofactor multiplication, as
described in IEEE P1363 and in [LAW98]. Cofactor multiplication performs an
additional operation on the shared secret value so that it is not in a small
subgroup. (There is a "compatibility mode" that keeps the shared secret
value the same as in ordinary Diffie-Hellman when the system is not under
attack; discussion is available in B.S. Kaliski Jr. Compatible cofactor
multiplication for Diffie-Hellman primitives. Electronics Letters,
34(25):2396-2397, December 10, 1998.)

Another method is to choose the primes p and q so that p = qj + 1 where j is
small and to check the received public key against a small set of excluded
values. In this case, the leakage due to a small subgroup attack will be
only a few bits.

Editorial: Change "If the sender cannot" to "If an opponent cannot"; change
"failure of decryption" to "failure of a decryption operation by the
recipient".

18. General: Replace "S" with "Section" for cross-referencing.

19. Security considerations. The last two paragraphs could be merged into
Sections 2.1.5 and 2.2, or at least should be made consistent, so there are
not two sources for the same information. 

In the last paragraph, the effective length of 3DES keys is 112, not 168,
due to a meet-in-the-middle attack.

In a general design, one looks for a minimum security level and selects
algorithms to meet that level. So, for instance, if an 80-bit security level
is desired, a designer may choose 3DES or RC2 and a 160-bit minimum
subgroup. Selecting the subgroup size to be double the effective key
strength, while effective, is more than what is necessary. The subgroup size
should be double the desired security level rather than double the symmetric
key size.

Moreover, there needs to be a prime size selection (1024 bits, 2048 bits,
etc.) that matches the desired level.

Finally, the selection must take into account the number of users sharing
the primes, since it costs only slightly more to compute several discrete
logarithms than to compute the first one.

---

From: EKR <[email-masked]>
Date: 14 Jan 1999 07:11:38 -0800

> Lisa Yin of RSA Laboratories. 
Thanks to John, Burt, and Lisa.

> 2. ANSI X9.42 is still an unapproved draft, and should be cited as such, not
Ok.

> finite field element, not a number (integer).
Well, a lot of the point here is to concretize (there's a horrible
neologism for you) X9.42 for S/MIME use, and for the purposes of 
S/MIME, it's an integer.

Anyone else want to comment on this?

> g^q mod p = 1, if g <> 1 and q is prime. 
Right. I'm happy to change this.

> In any case, some representation should be stated.
Agreed. Myself I prefer fewest octets. 

> Also, the comment "the
I agree that this is misleading. I'll fix it.

> 6. Section 2.1.2: Editorial: Change "shared key" to "shared secret value".
Agreed.

> the block size and the number of rounds.
I think this is weird, but this is how X9.42 does it, so our
choices are kind of limited.

> 8. Section 2.1.2: "Parameters" is misspelled in the definition of the
I'll fix this.

> OtherInfo varies. The variable part of OtherInfo is keyInfo; pubInfo remains
I'll try to add some text here.

>     keySize INTEGER OPTIONAL }
This structure is basically lifted from X9.42, so changing the
structure isn't really feasible for compatability reasons. 
Changing the names while keeping the same ASN.1 doesn't seem
to add clarity.

> maintaining an unambiguous encoding.
Again, this is how X9.42 does it.

> as an OCTET STRING is unambiguous and prevents length-extension attacks.
Russ, you care to speak up on this?

> Also, random or nonce might be a better name, since all of otherInfo, not
Yet again, this name is from X9.42.

> or adopted from some other standard: "leftmost", "network byte order", etc.
I agree.

> proposed S/MIME algorithms assume a random string, perhaps with parity
Well, the output of this process is necessarily a random string. Any
algorithm which needs a key with more structure should have a pre-processor
which produces one from a bit string.

> 160-bit minimum (Section 2.2).
So it doesn't. I changed the minimum on the last draft and forgot
that it affected the examples.

> 16. Section 2.2: Should a lower bound on the prime p also be given?
Probably. 1024 and be done with it?

> Why is
> there a 160-bit minimum on q?
IIRC, Brian LaMacchia wanted this. I'll let him speak for it.

> (Note that the 128-bit minimum in the same
> paragraph is inconsistent.)
Yes, this is inconsistent search and replace.

> Also, a minimum size on the private key x is
Yes, I'll remove the reference to x here.

> used; P1363 can be cited for discussion.
Well, SHOULD means 'do it this way unless you've got a good reason'.

> Per Sec. 2.2.1.1, step 6, it would
I can probably add something here.

> values. In this case, the leakage due to a small subgroup attack will be
I have to admit that I'm not enough of a mathematician to have
an informed opinion on this topic. I'd certainly far rather not
change the shared-secret value, and I don't want to require
an extra operation either (for perforamnce reasons).

> "failure of decryption" to "failure of a decryption operation by the
No problemo.

> due to a meet-in-the-middle attack.
Fair enough.

> should be double the desired security level rather than double the symmetric
I see your point here, but I'm not sure I agree. It seems to me
that a good design principle is to have a balanced system, where
all the algorithms are of roughly comparable strength. This speaks
for having the effctive key length as the basis for private key
size.

> etc.) that matches the desired level.
Agreed. I'd be glad to have some guidance on this one.

-Ekr

-- 
[Eric Rescorla                                   [email-masked]]

---

From: Paul Hoffman / IMC <[email-masked]>
Date: Thu, 14 Jan 1999 09:32:24 -0800

>choices are kind of limited.

This worries me. If there is a substitution attack that can recover the
key, I think we need to look at it VERY CAREFULLY. Has this same topic been
discussed on the X9.42 list? If so, can someone summarize the result? If
not, why not?

>Changing the names while keeping the same ASN.1 doesn't seem

I disagree: implementors can often be led astray by field names.

--Paul Hoffman, Director
--Internet Mail Consortium

---

From: EKR <[email-masked]>
Date: 14 Jan 1999 11:09:45 -0800

> discussed on the X9.42 list? If so, can someone summarize the result? If
I don't see how this makes any difference. Remember, all we're talking
about is the data that's input to the key expansion function. The
actual parameters that are to be used have to be conveyed separately
in any case, because this data is subsequently hashed. The only real effect
of including the algorithmId at all is to produce different keys for
different algorithms using the same pubInfo. It could easily be omitted
entirely.

> I disagree: implementors can often be led astray by field names.
As an implementor, one of the things I hate the most is when
I try to compare two protocols and have to spend a lot of time
trying to figure out if they're the same because someone has
gratiuitously changed a bunch of stuff and I can't tell if 
the changes affect the bits on the wire.

-Ekr

---

From: Russ Housley <[email-masked]>
Date: Fri, 15 Jan 1999 00:42:31 -0500

>Agreed. Myself I prefer fewest octets. 

I disagree with Eric.

I believe that ZZ should be the same size as p.  I think that this is much
easier to implement.  An implementation must have a buffer the size of p
since the result of the exponentiation could have no leading zero octets.
So, the implementation can simply use the entire buffer as the first input
to the hash function.

I have asked a couple implementors what they do.  So far, I have not found
anyone that is dropping leading zero octets.

It turns out that the ANSI X9F1 working group was meeting today.  Good
timing.  The ANSI X9F1 working group discussed this comment, and the ANSI
X9.42 draft will be changed to align with IEEE P1363.

To me, these three points are compelling.  I strongly suggest that we adopt
Burt's and Lisa's recommendation.

>choices are kind of limited.

I think it would be inappropriate to assign OIDs that did not contain
message-specific data, such as IVs.  Assigning additional OIDs does not
seem to be the way forward.

This "partition attack" is a real concern.  That input to the hash function
must unambiguously identify the output key length.  However, I think that
there is a way forward.  The key length is either implicit from the
algorithm identifier (e.g., DES) or it is carried as a parameter in the
algorithm identifier (e.g., RC2).  So, the recipient can easily determine
the value to pass to the key derivation function.  Perhaps we can always
put the key length in the pubInfo.  If a UKM is present, the pubInfo can be
the concatenation of the key length and the UKM.

What do others think about this approach?  If this approach is acceptable
to everyone, then we need work out the exact encodings.

>Again, this is how X9.42 does it.

This is done to aid implementors.  By making the field fixed length, an
implentation can use a constant to initialize OtherInfo.  Then, the counter
portion is incremented for each invocation of the Hash function.

>Russ, you care to speak up on this?

Since the internal block size of SHA-1 is 512 bits, this seems to be the
maximum amount of entorpy that can be added with a public value.

This comment would indicate that sizes between 160 and 512 bits are useful.

Should we standarize on a single length?  512 bits?

>which produces one from a bit string.

I agree with Eric.  I do not think that we can anticipate the needs of
these future algorithms.  Rather, when a future algorithm is defined, a
mapping between the "random" X9.42 output and the structured input needed
by the algorithm can be defined.

>Probably. 1024 and be done with it?

Eric, I assume that you mean p must be at least 1024 bits long.  Not, p
must be greater than 1024.

>an extra operation either (for perforamnce reasons).

Eric, your response here does not tell me what you plan to do.   Do you
know yet?

Russ

---

From: Russ Housley <[email-masked]>
Date: Sat, 16 Jan 1999 13:56:24 -0500

>different algorithms using the same pubInfo. It could easily be omitted

I think you are missing an important point.  RC2 with a 40 bit key and RC2
with a 128 bit key result in the same inputs to the hash algorithm.  If an
attacker is able to get a less sensitive message to be encrypted with the
40 bit key, this message can be readily attacked by brute force.  Should a
more sensitive message be encrypted with the 128 bit key, the attacker
already knows the first 40 bits of the key.

Off the top of my head, I am not sure how the attacker can get this
situation to happen with S/MIME v3, but I am in favor of a robust security
standard.  We know that people are looking at CMS for other purposes.  One
of those future uses may permit an attack like this one.  And, the fix is
very simple.  We need to simply include the key length in the hash input.

Russ

---

From: EKR <[email-masked]>
Date: 16 Jan 1999 14:24:55 -0800

> already knows the first 40 bits of the key.
This is incorrect. By fiat, when used for key encryption, RC2 ALWAYS
uses a 128 bit key. The 40 bits refers only to the effective key length.
It may be possible to go from the 40 bit key to having some information
about the 128 bit key, but it's certainly not as simple as simply
knowing the first 40 bits.

>And, the fix is
I'm prepared to do it, but I'm not sure that just shoving it in the 
pubInfo is the right choice. I'll think about this and try to write 
up a proposal by monday.

-Ekr

---

From: EKR <[email-masked]>
Date: 17 Jan 1999 17:15:08 -0800

Russ Housley <[email-masked]> writes:
> You are correct. We did deal with this case.  However, I think is is a good
> idea to use the algorithm in such a way that future users of CMS cannot
> make a simple mistake and be susceptable to the partion attack.
I agree. 

> If you are going to the RSA Confernce, I will gladly have a hallway chat
> regarding the best way forward.
Yes, I'll be there.

-Ekr

---

From: Russ Housley <[email-masked]>
Date: Sun, 17 Jan 1999 19:49:23 -0500

Eric:

ANSI X9.42 is going to be changed based on this thread.  It will say
something like:
	If the algorithm identifier does not unambigiously specify
	the output key length, then that key length must be inclused
	in spuuPubInfo.

Russ