PGP Comment feature weakens remailer securityPGP Comment feature weakens remailer security

-----BEGIN PGP SIGNED MESSAGE-----

Suppose you want to mail or post something sensitive enough
to chain through several remailers with PGP encryption at every stage
to protect the privacy of communications.  PGP can bite you.
The PGP comment feature lets you stick one (or more?) lines of comment
into your encrypted messages, after the Version: line but before the
encrypted message body.  If you use the PGP comment feature to say something
more or less unique (mine says that you can get PGP outside the country
from ftp.ox.ac.uk), anybody eavesdropping the last remailer in your chain
can notice this in the remailer's input and recognize that it's from you,
even though you've chained through six different places to get there.
It's still encrypted, and protected to the extent that the remailer protects
you, but if the remailer is corrupt or your message can be identified 
by size among the other remailer inputs, you're hosed.

So, for safety, either turn off PGP comments before using it 
with remailers, or wipe out the comments by hand  before each layer of encryption
(easy to do with GUI-based systems like Private Idaho; I don't know
if premail lets you do this or not.)

                                      Bill Stewart

-----BEGIN PGP SIGNATURE-----
Version: 2.7.1
Comment: PGP available outside U.S.A. at ftp.ox.ac.uk

iQBVAwUBMKAgw/thU5e7emAFAQFStwH/QnIiiaeSmUp1YynDBLVo3HAWsVkS0nx8
Fc95Mr0YJ/YIoRDz+xuNgLHbjJZSTUbhOnigMRb7JLNqhmCGvS5RBQ==
=ZWhB
-----END PGP SIGNATURE-----

#---
#                                       Thanks;  Bill
# Bill Stewart, Freelance Information Architect, stewarts@ix.netcom.com
# Phone +1-510-247-0664 Pager/Voicemail 1-408-787-1281
#---

Point well taken.

   I'm seriously considering completely disabling the PGP comment
feature when invoked from premail. In fact, that's what the new code
does right now.

   On an unrelated topic... cypherpunks like to count bits, right?
What is the correct number of pseudorandom bits to use in a MIME
multipart separator? If the data has a line which matches the
separator, the message is corrupted. Of course, if you can take
multiple passes through the data, you can simply verify that it does
not contain a line which matches the separator. But if you're
restricted to a single pass, then the only way to do it is to use a
randomly generated separator.
   I figure that 128 bits should _definitely_ be enough (that's what
is in the new premail code now). Even 64 bits should ensure that it is
unlikely that anyone will ever experience message corruption over the
expected lifetime of premail. However, it makes me nervous. What do
people think?

Raph

I think you are fine if the odds of corrupting the message are less than 
the odds of getting hit by a a falling meteor while running the program. 
In general there is little point in making any one part of the system 
many orders of magnitude more reliable than any other part.

	-Lance


On Wed, 8 Nov 1995, Raph Levien wrote:

>    Point well taken.
> 
>    I'm seriously considering completely disabling the PGP comment
> feature when invoked from premail. In fact, that's what the new code
> does right now.
> 
>    On an unrelated topic... cypherpunks like to count bits, right?
> What is the correct number of pseudorandom bits to use in a MIME
> multipart separator? If the data has a line which matches the
> separator, the message is corrupted. Of course, if you can take
> multiple passes through the data, you can simply verify that it does
> not contain a line which matches the separator. But if you're
> restricted to a single pass, then the only way to do it is to use a
> randomly generated separator.
>    I figure that 128 bits should _definitely_ be enough (that's what
> is in the new premail code now). Even 64 bits should ensure that it is
> unlikely that anyone will ever experience message corruption over the
> expected lifetime of premail. However, it makes me nervous. What do
> people think?
> 
> Raph
> 

----------------------------------------------------------
Lance Cottrell   loki@obscura.com
PGP 2.6 key available by finger or server.
Mixmaster, the next generation remailer, is now available!
http://obscura.com/~loki/Welcome.html or FTP to obscura.com

"Love is a snowmobile racing across the tundra.  Suddenly
it flips over, pinning you underneath.  At night the ice
weasels come."
                        --Nietzsche
----------------------------------------------------------

> I think you are fine if the odds of corrupting the message are less than 
> the odds of getting hit by a a falling meteor while running the program. 
> In general there is little point in making any one part of the system 
> many orders of magnitude more reliable than any other part.

I agree entirely. That's why my PGP key at school is 382 bits. It's a
lot easier to compromise my machine than factor a 382 bit number.

So let me rephrase the question: what's the minimum number of entropy
bits that can be used and still give you that warm and fuzzy feeling
that you don't have to worry about the possibility that the message
might be corrupted?

The winning answer gets a free mention in the PGP/MIME Implementation
notes Web page: http://www.c2.org/~raph/impl.html

Raph

Raph Levien writes:
> > I think you are fine if the odds of corrupting the message are less than 
> > the odds of getting hit by a a falling meteor while running the program. 
> > In general there is little point in making any one part of the system 
> > many orders of magnitude more reliable than any other part.
> 
> I agree entirely. That's why my PGP key at school is 382 bits. It's a
> lot easier to compromise my machine than factor a 382 bit number.

On the other hand, it costs nothing by most people's standards to use
a 1024 bit key, so why not use one? I find that there is only a point
in using low security for anything in particular when there is a
perceivable cost to it -- if the cost is typing a different number
while doing key generation, I don't see why one should suffer the
tradeoff.

Perry

> > I agree entirely. That's why my PGP key at school is 382 bits. It's a
> > lot easier to compromise my machine than factor a 382 bit number.
> 
> On the other hand, it costs nothing by most people's standards to use
> a 1024 bit key, so why not use one? I find that there is only a point
> in using low security for anything in particular when there is a
> perceivable cost to it -- if the cost is typing a different number
> while doing key generation, I don't see why one should suffer the
> tradeoff.

Perhaps it costs you "nothing," Perry, but not all of us have the
massively parrallel 64-way interleaved banked memory nanosecond-latency
box you have on your desk.

Since RSA decryption is cubic in key size, it takes about twenty times
as long to sign or decrypt a message. Since latency-hiding (for example,
caching the decrypted session keys) is not widely implemented, the user
actually sees the difference.

For applications such as remailers, a 20-fold factor can make the
difference between smooth operation and totally hosing the machine.

Another reason to use small keys is to communicate the relative insecurity
of the machine to senders. A 382-bit key says, loud and clear, "don't send
sensitive or incriminating information using this key."

Raph

Raph Levien writes:
> > On the other hand, it costs nothing by most people's standards to use
> > a 1024 bit key, so why not use one? I find that there is only a point
> > in using low security for anything in particular when there is a
> > perceivable cost to it -- if the cost is typing a different number
> > while doing key generation, I don't see why one should suffer the
> > tradeoff.
> 
> Perhaps it costs you "nothing," Perry, but not all of us have the
> massively parrallel 64-way interleaved banked memory nanosecond-latency
> box you have on your desk.

I've found that in practice the compression pass takes longer than the
RSA pass for PGP. If you accept the time for the file compression I
don't see how you can have trouble with the 1024 bit RSA operation.

Perry

> I've found that in practice the compression pass takes longer than the
> RSA pass for PGP. If you accept the time for the file compression I
> don't see how you can have trouble with the 1024 bit RSA operation.

When in doubt, measure. The following measurements were done on a DEC
Alpha 3000/300, 150Mhz, Digital Unix 3.2. The first test file was an
email I sent this morning, with a size of 5379 bytes, which is typical
for the email I send. The second test file was the PostScript version
of a 52 page tech report done by our research group this summer, with
a size of 656676 bytes. The version of PGP used was MIT 2.6.2, compiled
with the default osf configuration (-O compile flag).

In all cases, user time only (not system time) is measured. This seems
reasonable, because neither compression nor RSA inherently require I/O.
The standard deviation on timings was somewhere around 5 or 10 ms. I
took the average "by eye" over about ten runs each. I did not include
signing tasks, as neither PGP/MIME signing nor clearsigning include a 
compression step.

Task 1: encrypt file, generating compressed output (RSA is quadratic)
keysize  compression  time   file size in   file size out
---------------------------------------------------------
382      on           95 ms   5379 bytes      2205 bytes
382      off          90 ms   5379 bytes      8165 bytes
1024     on           90 ms   5379 bytes      2315 bytes
1024     off          85 ms   5379 bytes      8275 bytes
382      on           3.86 s  656676 bytes    255575 bytes
382      off          2.43 s  656676 bytes    920984 bytes
1024     on           3.84 s  656676 bytes    255685 bytes
1024     off          2.43 s  656676 bytes    921090 bytes

Task 2: decrypt file from Task 1 (RSA is cubic)
keysize  compression  time   file size in   file size out
---------------------------------------------------------
382      on           135 ms  2205 bytes      5379 bytes
382      off          140 ms  8165 bytes      5379 bytes
1024     on           1.14 s  2315 bytes      5379 bytes
1024     off          1.14 s  8275 bytes      5379 bytes
382      on           1.43 s  255575 bytes    656676 bytes
382      off          2.68 s  920984 bytes    656676 bytes
1024     on           2.42 s  255685 bytes    656676 bytes
1024     off          3.74 s  921090 bytes    656676 bytes

We can conclude that for small files, the size of a typical email,
compression is completely negligible, and the effect of key size is
significant. We can also conclude that for large compressible files,
compression increases encryption time by roughly two seconds per
MB, but decreases decryption time by roughly the same amount (by
virtue of having to decrypt fewer bytes).

Raph

-----BEGIN PGP SIGNED MESSAGE-----

>>>>> "Raph" == Raph Levien <raph@CS.Berkeley.EDU> writes:

    Raph> Since RSA decryption is cubic in key size, it takes about
    Raph> twenty times as long to sign or decrypt a message. Since

Actually Sedgewick shows an algorithm that runs in O(N*N*log N). 

Andreas

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
Comment: Processed by Mailcrypt 3.4, an Emacs/PGP interface

iQCVAgUBMKNApkyjTSyISdw9AQHSVQP/eUBnTOX/kzZU4/T3w/60mnj0GpT88Saa
qsgLq3N2b2U2lOOmQYE5JGb9FTds/3Hj9kxKMGxmSlyt3nOjgWmAKLJf5AvDMY1Y
MzSVaswzst/EyQYeQBZcUl+ahy3HFLLR8CUMX/IIeJS0w3iJbW4FNsmsTqCf/7Tg
p1Pa+TXQKYk=
=Vrsb
-----END PGP SIGNATURE-----

On Thu, 9 Nov 1995, Perry E. Metzger wrote:

> > I agree entirely. That's why my PGP key at school is 382 bits. It's a
> > lot easier to compromise my machine than factor a 382 bit number.
> 
> On the other hand, it costs nothing by most people's standards to use
> a 1024 bit key, so why not use one? I find that there is only a point
> in using low security for anything in particular when there is a
> perceivable cost to it -- if the cost is typing a different number
> while doing key generation, I don't see why one should suffer the
> tradeoff.

Actually, it makes a sort of sense; if I see a 384 bit PGP key, it 
strikes me as insecure, and I really consider it; unless it says so on 
the 1024 bit key, I wouldn't think about it much.  It's useful as a human 
identifier, assuming it's not the weakest link in the chain.

Jon
------------------------------------------------------------------------------
Jon Lasser                <jlasser@rwd.goucher.edu>            (410)494-3072 
          Visit my home page at http://www.goucher.edu/~jlasser/
  You have a friend at the NSA: Big Brother is watching. Finger for PGP key.

On Tue, 7 Nov 1995 anonymous-remailer@shell.portal.com wrote:

> to protect the privacy of communications.  PGP can bite you.
> The PGP comment feature lets you stick one (or more?) lines of comment
> into your encrypted messages, after the Version: line but before the
> encrypted message body.  If you use the PGP comment feature to say something

---- 8< snip

> 
> -----BEGIN PGP SIGNATURE-----
> Version: 2.7.1
> Comment: PGP available outside U.S.A. at ftp.ox.ac.uk
> 

You are using Viacrypt PGP, which has a release out which fixes the 
comment "feature" - contact them for an upgrade.

This was fixed in the freeware version some time ago as well.

-NetSurfer

#include <standard.disclaimer>

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
==  =     = |James D. Wilson        |V.PGP 2.7:   512/E12FCD 1994/03/17 >
 "  "  o  " |P. O. Box 15432        |     finger for full PGP key        >
 "  " / \ " |Honolulu, HI  96830    |====================================>
\"  "/ G \" |Serendipitous Solutions|    http://www.pixi.com/~netsurf   >
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

Raph Levien writes:
 >    On an unrelated topic... cypherpunks like to count bits, right?
 > What is the correct number of pseudorandom bits to use in a MIME
 > multipart separator? If the data has a line which matches the
 > separator, the message is corrupted. Of course, if you can take
 > multiple passes through the data, you can simply verify that it does
   ***************
No need !
 > not contain a line which matches the separator. But if you're
 > restricted to a single pass, then the only way to do it is to use a
 > randomly generated separator.
I've waited a bit, but as nobody seem to have pointed out, you can
definitly find a unique stream in a *single* pass (but maybe what you
really want is no pass at all ?)
{you add a new random byte each time you find your sequence in the
stream, and goes forward (as the previous separator was not in the
"past" of the stream, you don't need to go back)}

What am I missing ? (anyway, see below)
(I hope my answer is not as clueless as the "A-dice anonymous" one)

 >    I figure that 128 bits should _definitely_ be enough (that's what
 > is in the new premail code now). Even 64 bits should ensure that it is
 > unlikely that anyone will ever experience message corruption over the
 > expected lifetime of premail. However, it makes me nervous. What do
 > people think?

Isn't PGP encoded stream containing only base64 chars ? Why not use
"====PGP part #===="  (as you can't have more than 2 = in a base 64,
and only at the end anyway)
or "@PGP part #" or whatever starting with a non base64 char ?

so "@" = 8 bits is my anwser, do I win ;-) ?

dl
--
Laurent Demailly * http://hplyot.obspm.fr/~dl/ * Linux|PGP|Gnu|Tcl|...  Freedom
Prime#1: cent cinq mille cent cinq milliards cent cinq mille cent soixante sept

Greenpeace Uzi NORAD DES NSA [Hello to all my fans in domestic
 surveillance] Clinton

> Raph Levien writes:
>  >    On an unrelated topic... cypherpunks like to count bits, right?
>  > What is the correct number of pseudorandom bits to use in a MIME
>  > multipart separator? If the data has a line which matches the
>  > separator, the message is corrupted. Of course, if you can take
>  > multiple passes through the data, you can simply verify that it does
>    ***************
> No need !
>  > not contain a line which matches the separator. But if you're
>  > restricted to a single pass, then the only way to do it is to use a
>  > randomly generated separator.
> I've waited a bit, but as nobody seem to have pointed out, you can
> definitly find a unique stream in a *single* pass (but maybe what you
> really want is no pass at all ?)
> {you add a new random byte each time you find your sequence in the
> stream, and goes forward (as the previous separator was not in the
> "past" of the stream, you don't need to go back)}

Yes, that's a good strategy _if_ you're able to take multiple passes.
However, the separator must (of course) appear at the top of the multipart
message being assembled. Perhaps we don't agree on what "single pass"
means; I meant you could do the processing in a Unix pipe without
requiring storage proportional the size of the data.

> What am I missing ? (anyway, see below)
> (I hope my answer is not as clueless as the "A-dice anonymous" one)

Not quite. As they say, "A-dice" is not merely clueless, but actually
clue-resistant.

>  >    I figure that 128 bits should _definitely_ be enough (that's what
>  > is in the new premail code now). Even 64 bits should ensure that it is
>  > unlikely that anyone will ever experience message corruption over the
>  > expected lifetime of premail. However, it makes me nervous. What do
>  > people think?
> 
> Isn't PGP encoded stream containing only base64 chars ? Why not use
> "====PGP part #===="  (as you can't have more than 2 = in a base 64,
> and only at the end anyway)
> or "@PGP part #" or whatever starting with a non base64 char ?

For PGP encrypted messages, I just use "+" as the boundary, as it is
guaranteed that a valid PGP/MIME multipart/encrypted message body will
never include the line "--+" or "--+--". For the longer separators, my
concern is multipart/signed messages.

> so "@" = 8 bits is my anwser, do I win ;-) ?

I chose "+" instead of, say, "@" because it will survive EBCDIC gateways.
You might argue that this is worrying too much, but doing the right thing
here costs nothing, and may actually save somebody some trouble.

Raph