# 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 --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

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

.

**Follow-Ups**:**Re: gnupg / rsa padding question***From:*Mike Amling

**Re: gnupg / rsa padding question***From:*Kristian Gjøsteen

- 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):