draft-ietf-smime-small-subgroup-01.txt:
ya is Party A's public key; ya = g ^ xa mod p
yb is Party B's public key; yb = g ^ xb mod p
xa is Party A's private key
xb is Party B's private key
p is a large prime
g = h^((p-1)/q) mod p, where
h is any integer with 1 < h < p-1 such that h^((p-1)/q) mod p > 1
(g has order q mod p)
q is a large prime
j a large integer such that p=q*j + 1
3.4 Compatible Cofactor Exponentiation
This method of protection is specified in [p1363] and [KALISKI]. It
involves modifying the computation of ZZ. Instead of computing ZZ as
ZZ=yb^xa mod p, Party A would compute it as ZZ=(yb^j)^c mod p where
c=j^(-1)*xa mod q. (Similarly for Party B.)
If the resulting value ZZ satisfies ZZ==1, then the key agreement should
be abandoned because the public key being used is invalid.
Note that this procedure may be subject to pending patents.
Patent applications by whom, dating from when? I described DH with
what this draft calls "compatible cofactor exponentiation" in a
message to the coderpunks mailing list in September 1996 -- although
in a different setting in that factors from "wrong" subgroups were not
injected by an attacker but by the sender, because the issue was
steganography. (A little difference in presentation is that where I
assume that an integer m such that m = 1 (mod q) and
m = 0 (mod (p-1)/q) is used as an exponent, the draft uses in two
exponentiations two factors of an explicit solution to these
congruences, namely j := (p-1)/q and j^(-1) (mod q). When all
exponents are multiplied at first instead of using multiple
exponentiations, this difference disappears.)
The DH scheme with cofactors is described in the second message
reproduced below, the first one is to provide context so that
the statements about steganography are comprehensible.
Message-Id: <m0v0apR-0000AyC(_at_)ulf(_dot_)mali(_dot_)sub(_dot_)org>
Date: Tue, 10 Sep 96 23:58 MET DST
Subject: Re: Project idea
From: Bodo_Moeller(_at_)public(_dot_)uni-hamburg(_dot_)de (Bodo Moeller)
To: coderpunks(_at_)toad(_dot_)com
In-Reply-To:
<199608291514(_dot_)AA04886(_at_)swan(_dot_)lcs(_dot_)mit(_dot_)edu>
rivest(_at_)theory(_dot_)lcs(_dot_)mit(_dot_)edu (Ron Rivest):
Joe Kilian suggested the following cute idea as a project over lunch
at CRYPTO 96: Implement a "stealth" version of Internet Phone (or
equivalent) that contains a subliminal crypto channel in the
low-order bit of the voice amplitude numbers.
[...]
Key management for the crypto could be handled out-of-band, or with
any of the standard techniques.
[...]
trying to do key-establishment in-line (e.g. with Diffie-Hellman)
probably can't hide the fact that key-establishment is happening.
Why not?
E.g., for Diffie-Hellman:
The prime p and a generator g of the whole multiplicative group
(Z/pZ)* can be built into the software. Let us assume that p has 1024
bits. Alice uniformly chooses a random numbers x (1 <= x < p) and
wants to transmit the integer y = g^x MOD p. Note that y is uniform
in [1, p). Now Alice does not directly send y through the
stego-channel (if she did, an eavesdropper would have statistical
evidence that Alice uses steganography); rather, she randomly chooses
a number z in [0, 2^(1024+128)) satisfying z == y (mod p) and
transmits z. This integer z looks like a randomly chosen (1024+128)
bits integer (there is a bias, but it is negligible if an appropriate
value of 128 is used), and thus Alice's stego-message consists of
1024+128 seemingly random bits.
Bob acts similarly, and when each of them has transmitted 1024+128
bits (via the stego-channel), the Diffie-Hellman key negotiation is
complete. Before they know the encryption key and can start sending
real data, Alice and Bob will probably have to send some random filler
bits because the exponentation takes too much time. (This problem,
plus that of the possibility of a man-in-the-middle attack, vanishes
if a public key infrastructure exists. Unfortunately, Alice and Bob
cannot simply use their DSA keys because DSA employs a generator of a
subgroup of (Z/pZ)* and not of the whole group.)
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
Date: Wed, 11 Sep 1996 18:39:40 +0200 (MET DST)
Message-Id:
<199609111639(_dot_)SAA13379(_at_)rzdspc5(_dot_)informatik(_dot_)uni-hamburg(_dot_)de>
From: Bodo_Moeller(_at_)public(_dot_)uni-hamburg(_dot_)de
To: coderpunks(_at_)toad(_dot_)com
Subject: Re: Project idea
In-Reply-To: <m0v0apR-0000AyC(_at_)ulf(_dot_)mali(_dot_)sub(_dot_)org>
I wrote:
[...]
y is uniform in [1, p). Now Alice does not directly send y through
the stego-channel (if she did, an eavesdropper would have
statistical evidence that Alice uses steganography); rather, she
randomly chooses a number z in [0, 2^(1024+128)) satisfying z == y
(mod p) and transmits z. This integer z looks like a randomly
chosen (1024+128) bits integer (there is a bias, but it is
negligible if an appropriate value of 128 is used), and thus Alice's
stego-message consists of 1024+128 seemingly random bits.
I forgot to mention that this scheme was not invented by Alice
herself, but (as far as I know) by Hal Finney. Apologies for the
omission.
[...]
Unfortunately, Alice and Bob cannot simply use their DSA keys
because DSA employs a generator of a subgroup of (Z/pZ)* and not of
the whole group.
Meanwhile, I noticed that there is a simple solution provided that
o q^2 does not divide p-1 and
o Alice knows a generator modulo Bob's p (i.e. a generator of
(Z/pZ)*).
In this case, Alice and Bob can use a variant of the Diffie-Hellman
scheme:
Assume that Bob's public DSA key is (p, q, g, y) where g is a
generator of a order-q subgroup of (Z/pZ)* and y = g^x MOD p (x is
Bob's secret parameter). Be G a generator of (Z/pZ)* that is known to
Alice. Then Alice can compute D = G^q; D generates a subgroup of
(Z/pZ)* that is "orthogonal" to the one generated by g.
When Alice wants to establish an encrypted stego-channel to Bob, she
proceeds as follows. She chooses a random number r in [0, q) and
computes K = y^r MOD p. The 128 least significant bits of K MOD q (or
something like that) will later be used as Alice's encryption key.
She also computes K' = g^r MOD p. Alice chooses a random number s in
[0, (p-1)/q) and computes F = D^s MOD p. Now the product K'*F MOD p
is a random number in [1, p) and can be sent to Bob, using the
procedure described above; i.e., Alice chooses a random number z in
[0, 2^(length(p) +128)) satisfying z == K'*F (mod p) and transmits z.
When Bob receives z, he computes z^m MOD p = K'*F MOD p where m is an
integer satisfying m == 1 (mod q) and m == 0 (mod (p-1)/q). The
result is K' (because g^m == g (mod p), D^m == 1 (mod p), and K' and F
are in the subgroups generated by g and D, respectively). Bob can now
obtain K as K'^x MOD p.
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
Bodo M"oller
<bmoeller(_at_)acm(_dot_)org>