gnupg / rsa padding question
 From: "vedaal" <vedaal@xxxxxxxxx>
 Date: 6 Dec 2005 15:30:36 0800
using rsa, assuming N=4096, e=65537
how large must the padding be to maintain security against a known
plaintext attack?
specifically, with regard to gnupg/pgp messages done with a 4k rsa key,
and a 256 bit symmetric algorithm,
the session key is a string of 64 characters, composed of { 0,1, ...
, 9, A, B, ... , F }
if the padding added to the session key, is a large string,
then,
how much of that string can be used as a steganographic channel to
contain an additional message, and still maintain enough padding to
keep the entire message secure?
i.e.
the minimal p' so that ( k + m + p' ) = ( k + p )
where
k == session key
p == quantity of padding currently typically used when encrypting a
session key to a 4096 rsa key
p' == minimal amount of padding really necessary for securely
encrypting to the same 4096 rsa key
m == message string added along with new minimal amount of padding,
so that what is being encrypted to the 4096 rsa key remains the same
size, and indistinguishable, from a typical session key that would be
encrypted to the same key
if ( p' ) is small enough to allow for an ( m ) large enough to encode
a detailed communication,
then this could be utilized for a practical and undetecable,
steganographic channel in gnupg,
with good plausible deniability.
it could work like this:
[1] Alice and Bob share a new keypair, generated by either of them and
securely sent to the other, but neither of them ever publicizing or
uploading the public key,
(call this keypair 'Stan' to indicate the encrypted steganographic
channel).
[2] Alice sends a plausible decoy message (call it 'decoy.txt' ) to
Bob using the following gnupg command:
gpg hiddenencryptto Stan encryptto Bob sign decoy.txt
(a 'plausible decoy' message == a message with mildly private enough
content to plausibly warrant encryption, but not really important
enough that either Bob or Alice would mind revealing if forced to by
the authorities)
[3] instead of ( k + p ) being rsa encrypted to the Stan key, it is
really ( k + m + p' ) that is encrypted
( this would either need to be done manually,
or by modifying gnupg to allow manual entry of a selected session key
for each public key
it would be encrypting to, and then selecting ( k ) for the Bob key,
and ( k + m ) for the Stan key.
( k ) would be gotten by encrypting and then decrypting a test message,
and using the gnupg option of 'showsessionkey' .
this would ensure the ( k ) is still appropriately random,
and gnupg would then add ( p ) and ( p' ) the same way it does now
when encrypting a session key to two separate public keys. )
[4] Bob receives a message encrypted to Bob's key, and also to an
anonymized key, which he claims he does not know whose key it is,
but assumes it to be Alice's key, that she encrypts to by default,
using the gnupg option of ' hiddenencryptto Alice' .
in reality, Bob expects the anonymized key to be Stan's, which he then
decrypts, obtaining
( k + m ).
if pressured by the authorities, either/both Bob and/or Alice can
give up ( k ) allowing the authorities to decrypt (only) the
symmetricly encrypted 'decoy.txt'.
[5] as no one other than Bob or Alice has Stan's key,
then Bob can assume reliably upon decryption of a ( k + m ) from
Stan's key,
that ( m ) came from Alice, and vice versa,
eliminating the need to use up space in ( m ) for a signature.
the questions now are:
(a) what is the approximate size of the minimal ( p' ) that would be
necessary,
and therefore the maximal ( m ) that could be concealed?
(b) can this also work for dh keys,
and if so,
would ( m ) be more or less than for an equivalently sized rsa key?
(c) would this steganographic scheme *really* work,
[with the understanding that gnupg would have to be modified to allow
for encryption and decryption of ( k + m ) ],
or did i overlook something really critical ;) ?
TIA,
vedaal
.
 FollowUps:
 Re: gnupg / rsa padding question
 From: Mike Amling
 Re: gnupg / rsa padding question
 From: Kristian Gjøsteen
 Re: gnupg / rsa padding question
 Prev by Date: Re: First quantum byte!
 Next by Date: Re: First quantum byte!
 Previous by thread: QC Unbreakable PKI system  ideas?
 Next by thread: Re: gnupg / rsa padding question
 Index(es):
Relevant Pages
