Re: gnupg / rsa padding question



Mike Amling <nospam@xxxxxxxxxxx> writes:

>vedaal wrote:
>> using rsa, assuming N=4096, e=65537
>>
>> how large must the padding be to maintain security against a known
>> plaintext attack?

> I think the original OAEP paper addresses that. See
>http://www.cs.ucdavis.edu/~rogaway/papers/oaep-abstract.html.

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

The basic requirement is that the length of the message encrypted by rsa
must be of the same order as the length of the public key. Thus a 1024 bit
public key needs a message to encrypt of 1023 bits at least. (the
requirement is that the M>N/e where M is the message, N is the public
modulus and e is the public exponent).
Thus you need 256 bits for the symmetric algorithm which leaves 1024-256
bits.

Of course if someone can decrypt the M then have the session key and can
decrypt everything, so it is not much of a covert channel.



> If you don't want to mess with the session key itself, then your
>answer is the maximum length "message" under OAEP, minus the length of
>the session key.

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

>--Mike Amling
.