Subject: X9.42 comments.

From: Dr Stephen Henson <[email-masked]>
Date: Sat, 22 May 1999 21:02:19 +0100

As an initial step to implementing S/MIME v3 I started examining X9.42
at length with a view to implementing DH certificates support (which may
well end up in OpenSSL at some point). Previously I'd only verified the
KEK generation examples and not started on a full implementation.

I assume there are no examples available yet? By examples I mean
examples of key pairs, parameters, SEED values and shared secrets that
is: not just the KEK generation stuff which is already present.

A few things have cropped up: maybe some more will crop up during
(attempted) implementation. My appologies in advance for mentioning them
at this late stage, but there are certain things that only crop up when
you try to implement the algorithm.

All in section 2.2.1.1

Firstly at the start:

>Let L - 1 = n*m + b where both b and n are integers and 0 <= b < 160.

For arbitrary values of L and m this cannot always be satisfied. I'm not
100% sure but I think this should be:

"Let L - 1 = n*160 + b where both b and n are integers and 
0 <= b < 160"

which is the same as FIPS186. The reason being 'n' and 'b' are used to
generate 'W' (and ultimately p) by adding together 160 bit "chunks" in
step 10. The "160" here comes from the size of an SHA digest.

Then step 4:

> 4. for i = 0 to m' - 1
>
> U = U + SHA[SEED + i] XOR SHA[(SEED + m' + i) mod 2^160] *
> 2^(160 * i)
>
> Note that for m=160, this reduces to the algorithm of [FIPS-186]
>
> U = SHA[SEED] XOR SHA[(SEED+1) mod 2^160 ]."

Presumably SHA refers to SHA-1? 

My copy of FIPS-186 has (mod 2^g) in it (g is size of seed in bits) not
(mod 2^160). As things stand (mod 2^160) is effectively throwing away
the first g-160 bits of SEED, whereas (mod 2^g) is discarding any carry
(which is admittedly rather unlikely).

Anyway for completeness should the carry be discarded on the first part
as well? So the complete thing would read:

U = U + SHA[(SEED + i)mod 2^g] XOR SHA[(SEED + m' + i) mod 2^g] * 2^(160
* i)

Otherwise there is a very unlikely posibility that SEED + i will be
longer than SEED (but this case is excluded in the second SHA anyway).

Couple more things. The use of g for two separate things is a little
confusing: size of SEED in bits and one of the DH parameters. Though
FIPS186 does this as well.

Presumably the size of SEED in bits must be a multiple of 8? Since SEED
is represented as a BIT STRING (see PKIX) this need not be so. I assume
the "no trailing zero bits" DER encoding rule doesn't apply here:
otherwise there will be possible ambiguity.

Finally step 10 seems a bit garbled: there are a few ^ missing.

Steve.
-- 
Dr Stephen N. Henson.   http://www.drh-consultancy.demon.co.uk/
Personal Email: [email-masked] 
Senior crypto engineer, Celo Communications: http://www.celocom.com/
Core developer of the   OpenSSL project: http://www.openssl.org/
Business Email: [email-masked] PGP key: via homepage.

---

From: Dr Stephen Henson <[email-masked]>
Date: Mon, 24 May 1999 17:08:45 +0100

Couple of additional comments all about section 2.2.1.1 [note I've
retained the original X9.42 text even in places where I've claimed other
problems in a previous message].

Firstly the algorithm for calculating 'q' in step 4 will produce a value
of 'q' with lots of zero bits if m is not a multiple of 160. For example
if m=319 it will have 158 zero bits.

This can be readily fixed by setting 
m' = (m + 159)/160 
in step 3 and in step 5: 
q = U mod 2^m
initially and then set the most and least signinificant bits as before.

The second issue may not be a problem as such.

The use of SEED doesn't quite follow the FIPS-186 usage. Let me
explain...

At several points FIPS-186 uses SHA[(SEED+k)mod 2^g] for the generation
of prime number candidates. The way it uses it obeys two rules.

1. Each value of k is used only once.
2. The order of use is such that each value of k is used in sequence.

(1) may have some cryptographic reason to ensure the same pseudo random
data is not re-used.

(2) makes implementation particularly easy: an implementer only needs
retain a copy of SEED+k and increment it every time it is used. This
property is not immediately apparent because of the way FIPS-186 is
written but it goes something like this:

All this refers to Appendix 2.2 FIPS-186:

Step 2. first uses SEED. It makes use of SEED and SEED+1 to calculate U
(and ultimately a candidate q). 

If q is not prime a new SEED is tried otherwise p is constructed from:

Vk = SHA[(SEED + offset + k) mod 2^g ].

For values of k = 0,...,n, and offset initially is 2.

This means that SEED+2, SEED+3, ... SEED+n+2 are used to ultimately
build a candidate p. If this is not successful (n+1) is added to offset
making it n+3 and each Vk calculated again. As can be seen the value of
SEED is incremented on each use.

The generalisation in X9.42 obeys neither rule if m' > 1. In this case:

4. for i = 0 to m' - 1

U = U + SHA[SEED + i] XOR SHA[(SEED + m' + i) mod 2^160] * 2^(160 * i)

This ends up using SEED and SEED+m'+1 (which is compatible with FIPS186
if m'=1) however if m'=3 say this uses SEED, SEED+3, SEED+1, SEED+4,
SEED+2, SEED+5

Then when we get to step 9 we end up using SEED+2, SEED+3,... and so on.

This ends up re-using the same data and as is apparent this is not in
order.

If the algorithm used is made to be compatible with something else then
not much can be done. If we do have some control over it and the same
rules as FIPS-186 are desired then these changes should work:

Step 4.

4. for i = 0 to m' - 1

U = U + SHA[SEED + 2*i] XOR SHA[(SEED + 2*i + 1) mod 2^160] * 2^(160 *
i)

Step 8.

Let counter=0 and offset = 2*m'

Assuming I haven't made some stupid slip this should end up incrementing
SEED each time and only using each value once. As before this retains
compatability with FIPS-186 if m=160 (m'=1).

Steve.