Re: hand huffman encoding at PGP world HQ

[Hal Finney <[e-mail]>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Adam Back <[e-mail]> writes:
> Hal Finney <[e-mail]> writes:
> > First, the difficulty is really not as large as people are making out.
> > The code to read the packet lengths in the various cases is less than a
> > page, and it's very simple.  Read a byte to see if it is the old or new
> > packet formats.  In the old case, read 1, 2, or 4 bytes to get the length;
> > in the new case, read 1 byte and if it's 0xc0 or over, read a second.
>
> The issue is the complexity and the code bloat.
>
> So with universal 32 bit length values, the code looks like:
> [code samples, maybe with some endianness problems]

Ideally you only have to write this code once, in a subroutine.  You
test it and get it right, and from then on you can rely on it.  Yes, it's
a few more lines of code, but it is not a major part of implementing OP.

> Seems to me there is more likely to be an error in the second set of
> code (probably is -- I haven't compiled it), also that the second
> example will be larger, and the second example took about 4 times
> longer to code.  Multiply by the other bit twiddling operations (new
> 192 bit twiddling, proprietry floating point stuff, and the same kind
> of philosophy applied throughout etc) stir in some programmer error,
> and there is significant extra complexity and code bloat, adding to
> development time, creating errors, and dissuading people from coding
> to OpenPGP.  The code bloat will affect smart card implementations.

I agree, as I said, that there is some additional cost to the coder.
And you may be right that this will dissade some people from attempting
the project, since apparently developers within this WG are concerned
about the difficulty of implementing these fields.  I can only reiterate
that the payoff is intended to be for end users and not developers, and
that compared to the level of effort for an OP implementation, writing
a page of code to handle packet headers is not that large a burden.

> I don't think it's that big a deal.  The only place where size at the
> bit scrimping level matters much is signatures.  I reckon use of 32
> bit ints will add at max 3 bytes to the length of the signature.  That
> won't even cause an additional line wrap on your DSS sig example.  The
> longer keyID will be much more significant.

This is one example we see now.  Note that until we went to DSS it was
not a very effective point.  RSA signatures are many times larger than
DSS ones.  "Bit scrimping" was not very effective there.

However, the point is that its philosophy of parsimony put PGP in position
to exploit the concise nature of DSS signatures.  The raw data for DSS
sigs is only 40 bytes long.  Saving a few bytes here and there is a
significant percentage improvement.  So this design philosophy gave us
the advantage of a beautifully compact signature even though it was not
specifically intended to address that case.

When a philsophical approach gives you a serendipitous result like this,
it creates hope that the philosophy is valid and will have similar
unexpected payoffs in the future.  (Or contrariwise that abandoning it
in favor of bulky 32 bit and 64 bit lengths is going to foreclose some
future opportunities.)  This is a philosophical argument rather than a
practical one since we can't point to specific future applications where
it will matter.  But generally it leaves more options open.

> If you really want some nasty hacks to save space, I'm sure I could
> construct some -- I am something of a past master at hand huffman
> encoding cf the RSA in perl and dc signature -- an implementation of
> RSA which is smaller than most PGP signatures :-)

Yes, no doubt you could.  You and Phil would probably make quite a team.

> > Compare that with SMIME.  If you've seen an SMIME signed message
> > in any public forum, you've probably also seen complaints about it.
> > The signature block is about 50+ lines long.  
>
> Yes David Sternlight just posted one to this forum.  I had just
> previously picked apart a x509 signature made by a colleague -- 4350
> bytes, and most of it turned out to be text disclaimers and legalese.

Yes, and level 2 certs include the cert holders street address!  People
didn't even know.

> One pass processing is a useful feature -- perhaps we could do
> something simple like SSLv3 does -- max of 16k -- a simple 16 bit
> integer.  No need for this > 192 means something odd hacking -- the 1
> byte of bloat I don't think will be a problem.

However you do it, it will add some complexity, which may reduce the
attractiveness of the simple-seeming 32 or 64 bit length field.

Hal

-----BEGIN PGP SIGNATURE-----
Version: PGP for Personal Privacy 5.0
Charset: noconv

iQA/AwUBNHmfQ8Dh8jnv1nHwEQKXvQCbB0nPw1/3NhlTCEno0RK/ByZjTp8AnR8w
G//rDgQg4V7U7fQdgGWxAhyK
=jFgv
-----END PGP SIGNATURE-----