On how to stego pgp messages. First you have to ensure that the data
you are stegoing has a rectangular distribution with even probability
of {0,1} for each bit, and apply your stego technique. Various ideas
have been discussed, but as anonymous suggests this has all been
worked out for PGP 2.x before.
As anonymous describes one problem is the RSA modulus, because RSA
encrypted messages are not uniformly distributed (they are < N the RSA
modulus, which gives some skew especially in the distribution of the
most significant bits)
Hal Finney, and Bodo Moeller and I independently came up with
different algorithms to do this. Hal's algorithm (which is the better
algorithm) is to add a random multiple of N, and then the reverse
operation is to assume the recipient's public key:
normalise:
C = M^e mod N (RSA encrypt)
S = C + rN (Hal's normalise)
unnormalise, presume N:
C = S mod N (Hal's un-normalise)
M = C^d mod N (RSA decrypt)
(C = ciphertext, M = message, e = RSA public exponent, N is RSA
modulus, S = stealthed output, r is random number)
This works because you can take any true random number output and
assume N for any public key and you can convert it into an equally
plausible C (ciphertext). So the attacker gains nothing, and the
method can be public and not need separate stego keys. stealth
version 2 beta (http://www.dcs.ex.ac.uk/~aba/stealth) implements Hal's
algorithm as described above for PGP2.x with the security parameter
that r is in the range 0..2^64. stealth version 1 was written by
Henry Hastur.
The other kind of stego key is where the stego algorithm has a key to
guide the dispersal of data in the target data. (Eg select which n of
m possible bits in the LSBs of an image file to replace with the
message).
The argument here is that the lower the encoding rate the more secure
it is, because the attacker has to both spot which bits have been
modified, and show an implausible statistical deviation from the
target data bits.
Here using public information as the key (eg. key is hash of public
key) is weaker because that would inform the attacker which bits the
data was encoded in.
If you had high confidence that the LSBits of the target data was
rectangular with having {0,1} equal probability, you would just as
well use the first n bits of the m target LSBs for the message, rather
than using some keyed bit selection algorithm.
Anonymous writes:
> Note that, with possession of the target public key, you can almost
> transform a PGP encrypted message to this stego format and back. The
> only problem is dealing with the random padding when you convert back,
> but PGP does have an encrypted packet length and it may ignore random
> encrypted noise at the end.
PGP2.x does ignore random padding in IDEA blocks, because there is an
internal (inside the encryption envelope) length field. Henry Hastur
wrote code to transform PGP messages into even distributed data and
back. The only gap in stealth-1 functionality was the uneven
distribution of C (being modulo N) was not fixed. Stealth-2 fixes
this with Hal's algorithm.
Stealth-2 has the remaining problem that it can't cope with multiple
recipients.
This is not so easy to fix, because if there are multiple recipients,
you don't know how many recipients there are, and hence don't know,
where the bulk encrypted data starts. This is compounded by the fact
that you don't know what size their keys are.
That part is tricky. You could normalize all public keys to some
upper bound (say 2048 bit for RSA). Then you would have to try
unstealthing and decrypting the stealthed encrypted session key blocks
until you got a success, or the end of the file. Then when you get a
success try bulk decrypting the remaining ciphertext starting at
multiples of the stealthed encrypted session key into the data (to
skip over later recipients if any).
Not a very efficient algorithm if the file is large. One alternatives
is to have a limited number of recipients. A slightly more efficient
method is to put the encrypted session keys at the end, attempt to
decrypt those starting from the right until you get a success or the
begining of the file, and then decrypt the data starting at the
begining. Still not pretty.
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. The other complication is that
you would have to try all private key on the keyring both Elgamal, or
RSA to decrypt.
Adam
--
print pack"C*",split/\D+/,`echo "16iII*o\U@{$/=$z;[(pop,pop,unpack"H*",<>
)]}\EsMsKsN0[lN*1lK[d2%Sa2/d0<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc`
