gnupg / rsa padding question

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,
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?

the minimal p' so that ( k + m + p' ) = ( k + p )
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

[2] Alice sends a plausible decoy message (call it 'decoy.txt' ) to
Bob using the following gnupg command:

gpg --hidden-encrypt-to Stan --encrypt-to 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 '--show-session-key' .

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 ' --hidden-encrypt-to 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
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 ;-) ?




Relevant Pages

  • Re: gnupg / rsa padding question
    ... how large must the padding be to maintain security against a known ... if the padding added to the session key, is a large string, ... encrypting to the same 4096 rsa key ...
  • Re: RijndaelManaged problem...
    ... If you wish to pad with zeros, the temporary workaround is to do the padding ... is not a multiple of the block size (which it does in Everett). ... > Encrypting 27 bytes ...
  • Re: Encryption ??
    ... What do you think about my idea to add pad handling ... although I was actually only encrypting data that fit into 8 ... It is mentioned for the padding type I used (Method 3 - nulls plus ... in test.prg adds a whole 8 character block when needed. ...
  • Re: Removing extra padding.
    ... While Encrypting a file the original data gets padded as per the ... I remove this extra padding in the output, ... in bits of the padded message becomes congruent to 448, modulo 512. ... This method can only be used to pad messages which are a whole number ...
  • Re: Interoperability problem in encrypting and decrypting files between 2K & XP
    ... is assuming that the cipher data size is the same as the original plaintext. ... Usually the ciphertext is longer because a padding has to be added by the ... If I am encrypting and decrypting on the same OS, ...