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

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.

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

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

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