From: nobody@REPLAY.COM (Anonymous)
Date: Wed, 3 Dec 1997 08:44:09 +0800
To: cypherpunks@Algebra.COM
Subject: Cantsin Protocol No. 2
Message-ID: <199712030038.BAA29410@basement.replay.com>
MIME-Version: 1.0
Content-Type: text/plain



Anonymous <anon@anon.efga.org> wrote:
>Monty Cantsin writes:
>> You can't see it up here, but this is a signed message using a
>> protocol which is modestly titled "Cantsin Protocol No. 1".
>> Suggestions for improvement are most welcome.
>
>A very interesting idea!  Please consider the following suggestions
>if you like, or feel free to ignore them.

Your suggestions were very helpful.  Thank you for making them!

I'm calling the latest version "Cantsin Protocol No.2" and its
identifying number is "25BA1A9F5B9010DD8C752EDE887E9AF3".

It is similar to Cantsin Protocol No. 1, but the bug with the hash of
the public key is fixed.  Instead of concatenating the values p, g,
and y, you concatenate "p:<p> g:<g> y:<y>" and compute the hash.  p,
g, and y should be represented as ASCII hexadecimal digits without
leading 0s.

The hashes should now be correct SHA1 hashes.

>One problem with signatures which have no indication at the top is
>that two passes over the data are necessary: the first to scan and
>find the start-of-signature indicator, and another to go back and
>calculate the hash.  Signatures such as S/MIME and PGP have enough
>information at the top of the signed message to allow one pass
>processing.

My thinking on this is that passes are cheap these days.  I want the
signature to be unobtrusive which probably can't be done if only one
pass is required.

Incidentally, a nice feature of these signatures is that they can be
moved around in the file just by changing the offset.  You don't need
to control the secret key to do it.

>> The first line is "16A5942B6EED349ECF4594C784DFD177 [Cantsin
>> Protocol No. 1]".  The hexadecimal number was chosen randomly and
>> is the indicator that this is a Cantsin Protocol No. 1 signature.
>> The number was chosen randomly and it is somewhat unlikely that
>> anybody else will accidently choose it.
>
>You might want to think about what happens if the document itself
>contains (maliciously, or perhaps because it is talking about your
>signatures) the string in question (as yours does and this one does
>as well).  This could throw off an automated signature checker.

The signature checker should ignore bad or incomplete signatures.  I
would consider this to be a bug in the software and not a bug in the
protocol.  A bad signature simply lacks meaning and an error message
need not be reported.

That might seem a little callous, but actually it's how we should
regard signatures.  The current model seems to be "computer, check the
signature on this file and tell me if it's good", whereas the correct
(in my view) model is, "computer, extract all of the material from
this file which is properly signed and throw out the rest."

(Of course, you could imagine a smart editor which highlighted the
areas of a document which were signed by various parties.  It seems a
little early to implement this.)

If it's not authenticated, you shouldn't even look at it.  I've taken
to putting the To: and Subject: header lines at the bottom of my
messages for this purpose.  There's really no need to keep any of the
header fields.

The header fields can be put at the end just as unambiguously as at
the beginning, but at the end they can be signed.

>> The second line in the signature is an SHA1 hash of the public key.
>> The hash is computed on the concatenation of the hexadecimal ASCII
>> forms of p, g, and y respectively.  There should be no leading zeros.
>> (Remember to leave off the newline!)
>
>Presumably you could use the key hash to look up the key to use for
>verifying the message.

Strictly speaking it's there to save space.  If we put the public key
components in every signature it wouldn't be much harder for the key
management software to compute a hash on them somehow.  This does not
have to be standardized.

>This has a mild denial of service attack.  Someone else could create
>a key with different boundaries between p, g, and y but which would
>create the same string as this concatenation, and therefore the same
>hash.  If you left the "p: ", "g: ", and "y: " in place it would
>prevent this.  PGP's key fingerprints have had the same problem.

ACK!  I knew about this problem, but I couldn't remember exactly how
it worked.  So I said, "Monty, let's not be dumb like those PGP guys.
Let's concatenate the keys together and compute the hash.  Nobody will
ever..."

Thank you very much for pointing this out.

>> The fourth line contains an offset and a length to specify the area
>> of the text which is signed.  The offset is relative to the
>> signature itself.  That is, the first character of the Cantsin
>> Protocol No. 1 code is at position 0.  As signatures are usually
>> appended, the offset will usually be the additive inverse of the
>> length.
>
>It is intriguing that this can be used to sign a subset of the text.
>Presumably there could be multiple signature blocks each of which
>signed different subsets, possibly with different keys.  One problem
>is that it is not obvious to the human reader what part of the text
>is signed.  A nice effect with PGP and S/MIME signatures is that even
>readers who don't have the tools can have some slight confidence in
>signatures, because other readers will often report it when
>signatures don't verify.  With a signature that only covers a portion
>of the text, people might assume that if there are no reports of
>failure, more of the text is signed than is the case.  This is not a
>technical problem but is a social phenomenon which may not interact
>well with this signature format.

People who want this feature should type something like "BEGIN CANTSIN
PROTOCOL NO. 2" and "END CANTSIN PROTOCOL NO. 2" into the text at the
right points.

>You need to specify a canonical line ending format.  Based on the
>count values in your document, it appears that you are counting line
>terminators as being one character long.  Your count value of 1CB9
>corresponds to decimal 7353, there are exactly 7353 characters from
>the first character of your message body to the beginning of your
>signature magic number, if line ends are one character.
>
>The specific characters for line endings need to be specified as well
>for the hash to be calculated consistently.  Your hash appears to be
>calculated with LF as the line ending (although the hash program is
>broken, see below).  Probably CR/LF would be preferable for the line
>endings as that is a widely used internet standard as well as being
>common on windows.

My feeling on this is that this is outside the scope of a signature
protocol.  The protocol should not make any assumptions about what is
being signed nor should it modify what is being signed.

I use LF to terminate lines and would recommend this to others, but it
is not part of the Cantsin Protocol No. 2 specification.

In any event, if we must put in patches to handle the poor fidelity of
electronic mail, the patches should go in afterwards.  When a
signature checking program finds ">From" it should replace it with
"From" and see if it can get the right checksum.  Likewise, it should
try the various line endings until it gets a match.  There can't be
more than about 12 variants, so this shouldn't create an onerous
burden on the machine.  (And, I suppose, it would be possible to add a
field after the length or after the hash which made a suggestion about
the line ending.)

>> You also need to be able to compute SHA1 hashes.  I've been using
>> something called "sha1file" which, I believe, originated at Adam
>> Back's web site.
>
>That program has a bug.  The routine SHA1_update in the file sha1.c
>is missing a line:
>
>   CENSORED BY THE UNITED ST
>   A
>      TES GOVERNMENT CENSORED BY THE UNITED STATES
>       GOVERNMENT CENSORED B
>      Y THE UNITED STATES GOVERN
>      MENT CENSORED BY THE UNITED 
>      STATES GOVERNMEN
>      T CENSORED BY TH
>***   E UNITED STA  ***  MISSING  ***
>   T
>
>Correcting this will make your hashes be correct.

Another great suggestion.  The hashes should be correct now.

Incidentally, in another thread I've been talking about partial
signatures.  The code above is an example of where this would be
useful.  In some countries we are not allowed to express ourselves
freely without persecution.  If I wanted to provably quote somebody
who included forbidden ideas in their message, it wouldn't be possible
without partial signatures.

>> El Gamal is simple enough that the signature on this message can be
>> checked using standard Unix tools such as dc version 1.1.  Let's
>> say M is the SHA1 hash of the message.  It is checked by verifying
>> the truth of this equation: (y^a * a^b) mod p = g^M mod p.
>
>El Gamal is a rather lengthy signature, although the verification
>equation is relatively simple.  DSS has a shorter signature.

This might be a good thing to add to a later Cantsin Protocol.

>There are some subtleties to choosing El Gamal keys, but with the
>2048 bit values you have chosen you are pretty safe.

Schneier doesn't mention this, although presumably this information
will show up in one of his references.  Do you know offhand of a
published source which covers this?

>Also, you can't really justify using 2048 bit keys when your hash is
>only 160 bits.  The hash becomes the weak link for keys beyond about
>1024 bits, and unless you use a stronger hash your key strength is
>misleading.  This is why DSS is only specified up to 1024 bits.

This is just intuition, isn't it?  Since we really don't know how hard
it is to factor it seems hard to claim we know the ratio of difficulty
between breaking SHA1 and El Gamal.  Factoring could be broken before
SHA1.

Not that any great science was applied to the choice of a 2048 bit
prime, it just seemed like a good size.  ;-)

Also, I think it is a mistake for people to communicate the strength
of a system by choosing various key lengths based on general popular
views.  It's probably better to say "I estimate this system requires
at least 2^x operations to break."

We've seen this with people choosing short keys so nobody will get the
idea that it is secure.  This just seems all wrong to me.  The key
length is only one way in which a key could be insecure.  Monty
Cantsin's authentication key, for example, is not kept very securely.
But, the way to communicate that is to say "this key is not kept all
that securely."

However, in Cantsin Protocol No. 2 the size of the prime chosen is
completely unspecified.  There doesn't seem to be a reason to restrict
the choice other people will make regarding the length of the prime.

I could imagine choosing a short key for control over a
semi-persistent identity.  The advantage is that you can claim
somebody else brute forced the key for statements you wish to
repudiate.  Similarly, I could imagine choosing an obnoxiously long
key to make it hard for people who don't have super fast machines to
associate with you.

Monty Cantsin
Editor in Chief
Smile Magazine
http://www.neoism.org/squares/smile_index.html
http://www.neoism.org/squares/cantsin_10.htm

Subject: Cantsin Protocol No. 2
To: cypherpunks@algebra.com
25BA1A9F5B9010DD8C752EDE887E9AF3 [Cantsin Protocol No. 2]
94C43229A76383D818D39952F7A41ACA0394C6FE
C602F22D31BBC6245643E58AD8EB260B58DC1250
-2B49 2B49
CEDDBC793332877C29C3BF084DDD8DE8113E6C80E13995BCAFACE2E7D719194A8CAEB987D2DAC013204F1A2909B1FADCB7EFE39F0F764B140CA5711D057B4EF1EF880ACAF1FF19FB5E92E4A8E4F1CE4B0F18CBB37274629EDACFF412C5A971C20869A956497491F41F3D0E7791F85E18ED638B0552A275CF2F24002646084CB3BCF0AE52A38826D1D986CBE460B793836291326C3636A452B54A79DE949CB6A12FD1852D9FC438D6D7E63989CC031161B8872E1EE60D0C4521FCF7096B98E1DEF560432314258359370763BCE5D3D4610B097DC68C1EDCD1F3D5084069C74191C798383C3BF822EC97DE84531B20ECCB36B13EC9153252C88FFAFE71CD65B197
AFC25A731FAD9BB9A373B7D9972EA9CED870CC6FDACE0B2A2AEAC4F0C33115B15E689CBF943B757F8690C945CC1CB29E4F86276EB0643E215ADB92CEFE1394DD8320DDF703D4212EFEFA59081C21BBD2ED6282304D2DB496735BBCB3E5B802C2B78037EC041DDD8BBC1E4712CF18E56237E5BCDB37127F538BEF1E0038949B42F88140E608F02282570388D07785841069FD76EFC78E170E12DC1CF6570E7D67603707E15717704EBF8DE50014141DC8F8C80432333B5647B176093A45834F4460BDD2465306AE56156EFE1D0686F0FB4F7743CED116F47121EB4970B4CFDBEC6E56E90AADAA97836E95F3723B3216E99EC9FDE324943AFF6F257880423DFCE7