Bodo Moeller writes:
> Adam Back <[EMAIL PROTECTED]>:
>
> > On how to stego pgp messages. First you have to ensure that the data
> > you are stegoing has a rectangular distribution [...]
> [...]
> > It might be nice to update stealth-2 for openPGP / pgp5. There you
> > have the additional task of coping with Elgamal key exchange. With
> > Elgamal you have g^k mod p, and m.y^k mod p which could be normalised
> > using Hal's algorithm relative to p. [...]
>
> This normalization works for the m*y^k mod p part (assuming that the
> padding that leads to m is good so that that product is reasonably
> random), but not for g^k mod p. The problem is that usually g will
> not be a generator of the group (Z/pZ)*, but merely of a proper
> subgroup thereof; and this shows in the ElGamal output.
This is a good point. The attacker can try raising the extracted g^k
value to the power of (p-1)/q; the result will be 1 if it is a stego
message, and almost certainly not 1 otherwise (assuming (p-1)/q is large).
The stego has failed.
> To use steganography with ElGamal anyway, an additional step is
> required. If you know the order of g mod p, then you can multiply
> in a random element of the "orthogonal" subgroup of (Z/pZ)*, which
> the receiver can cancel out by one exponentiation, provided that the
> order q of g is co-prime to (p-1)/q, i.e. that no factor of q
> occurs in p-1 more often than in q:
As noted, the difficulty here is determining q, the order of g. The only
way to do this is to try factoring p-1, and find the lowest factor such
that g^factor = 1 mod p. This program may fail if you get to a factor
for which this test is true, but the factor is not prime and you can't
further split it with the resources available.
However this will not be a problem in practice with PGP, as it chooses
q to be slightly smaller than p, hence p-1 can be easily factored into a
large prime q and a few small factors. So there should be no difficulty
in determining q for PGP ElGamal keys.
> Unfortunately, the OpenPGP format for ElGamal keys does not include q,
> not even as an option. What one could do to hack around this
> limitation is use the same DH-parameters for ElGamal encryption as for
> the associated DSA key (which does include q).
Is it safe to do ElGamal (or Diffie-Hellman) with a key which was
generated for use with DSA? The order of g, 160 bits, gives a work
factor of 80 bits to break the discrete log, using Pollard rho. This is
roughly the same work factor as for solving the DL problem directly on
a 512 to 1024 bit modulus, so it may seem reasonable. But actually the
full DL problem takes an intractable amount of memory (at least for
1024 bit keys) while the 80 bit Pollard rho uses very little memory.
If you are encrypting a session key of 128 bits using a DSS key then
you must be aware that you are getting only 80 bits of security.
