Re: Quoting Portions of a Signed Document

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

>>It would be neat if you could quote people and prove that they signed the
>>particular paragraph quoted without supplying the entire text.  Is there
>>a way to do this?  (It seems impossible, but so does mental poker.)
>
>>A crude approach would be to sign every paragraph or line
>>separately, but that's obviously inelegant.
>
>Well this could be done by creating a document signature and then a
>collection of sub signatures but it can get ugly real quick.

Ugly's the word for it, alright. ;-)

>What level of granularity does one use for the sub signature?

It would be nifty if there was a way to show that any continuous set
of bits were signed given only one signature on a whole document.
Intuitively, it seems to me that this might be provably inconsistent
with a secure hash.  Still, crypto results are full of surprises, so I
could imagine there is a way to do this.

>Then what does the sub signature really tell you? Yes you can verify
>that the quote was written by someone but it may be taken completely
>out of context.

Good point.  It is nice that people who quote out of context now in a
misleading way are convicted when you demand proof.

Still, my sense is that this would be a pretty useful thing to be able
to do and it would be technically interesting.

For example, you might want to reveal parts of a message signed by
somebody else without revealing the entire message.

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

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQEVAwUBNHtvB5aWtjSmRH/5AQEFvgf8C2gv6G9XZjAjfYy6+wtNY0n/3k8TZXj7
Yr0x9jidiJvfRXOi6cjKskmQ8WL98EbVkjHZkPN2t7rlLtLfQVQyQhBtW0jeXlav
dC9tSbNO9ThpIAlztO4Wfpx75xNHgEyvMAMB0CnGj1ZcmgParL6F/WM9nkhaI+ZT
R8Uu53BZXsCz408/YI4yu4t6E3SXhOJQYFjQ/JxaI8G9mTBpXXbNV9PoN4i2PjHe
0VfOeU0IAJNvWazFqbwcnTuDpcFvQRY70FhgR1exb7MzPYqJMm7D5kdUtZqFWLAH
RkwjusDo01rE6+1YxPtq8dP4/8I1wEUsNLOtLyG9gQ2CT+xBhXfrDw==
=FT0Y
-----END PGP SIGNATURE-----

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

In <199711260002.BAA28863@basement.replay.com>, on 11/25/97 
   at 07:02 PM, nobody@REPLAY.COM (Anonymous) said:

>It would be nifty if there was a way to show that any continuous set of
>bits were signed given only one signature on a whole document.
>Intuitively, it seems to me that this might be provably inconsistent with
>a secure hash.  Still, crypto results are full of surprises, so I could
>imagine there is a way to do this.

Well you can do it. Wether you want to do it is another matter.

For the level of granularity you are sugesting a hash is not pratical.

You could just use RSA encryption to encrypt the message in the following
manner:

The user encrypts the message with his *private* key. Rather than
encrypting the entire document in one operation he would encrypt each
[insert you level of granularity here] and then concantinate the results.
Say we wanted a level of granularity of a word:

word1 word2 word3 word4

the resulting cypher text would be:

cypher1 cypher2 cypher3 cypher4

Now if someone wished to verifiably quote words 1,3,4 they would include
cypher1 cypher3 cypher4 in their document.

Since cypher 1,3,4 could only be generated by original author it can be
verified that he actually wrote those words.

At a bare minimum this would have to be done on a level of granularity of
a sentance to have any meaning at all and even then it's relavance would
be questioned.


- -- 
- ---------------------------------------------------------------
William H. Geiger III  http://users.invweb.net/~whgiii
Geiger Consulting    Cooking With Warp 4.0

Author of E-Secure - PGP Front End for MR/2 Ice
PGP & MR/2 the only way for secure e-mail.
OS/2 PGP 2.6.3a at: http://users.invweb.net/~whgiii/pgpmr2.html                        
- ---------------------------------------------------------------

-----BEGIN PGP SIGNATURE-----
Version: 2.6.3a
Charset: cp850
Comment: Registered_User_E-Secure_v1.1b1_ES000000

iQCVAwUBNHt00o9Co1n+aLhhAQHrKwP/SfQYrH07AA1WxJa/atnYfrnlkORgsevK
eO0EDDBcz3XIwBWP43y1l8XqRcK0F5sLjdQ6L0s8t9CmqH4N00awfM8UlN7bm69s
9AGuJwA1/UanfOi6TDXclvKJYgMCRerP0X+Yvr04gePObITYOrMKZUbDdYnO/70Y
2EpPAbaPcg4=
=5HsX
-----END PGP SIGNATURE-----

> You could just use RSA encryption to encrypt the message in the following
> manner:
> 
> The user encrypts the message with his *private* key. 

That's a signature. 

...
> At a bare minimum this would have to be done on a level of granularity of a 
> sent[e]nce to have any meaning at all and even then [its] rel[e]vance would
> be questioned. 

Quoting in the real world is like that (although that would allow you to
transpose/repeat sentences [?]). The problem is more one of having too much to
sign (processor time/bandwidth), but I think you're always going to have that
with a small granularity. Also, when not using a hash, you have to worry about
chosen-gidget attacks (see the excerpt from the PGP Attack FAQ after my
.sig...). 
 
> - ---------------------------------------------------------------
> William H. Geiger III  http://users.invweb.net/~whgiii
> Geiger Consulting    Cooking With Warp 4.0
> 
> Author of E-Secure - PGP Front End for MR/2 Ice
> PGP & MR/2 the only way for secure e-mail.
> OS/2 PGP 2.6.3a at: http://users.invweb.net/~whgiii/pgpmr2.html
> - ---------------------------------------------------------------

---------------------------------------------------------------------------
Randall Farmer
    rfarmer@hiwaay.net
    http://hiwaay.net/~rfarmer
---------------------------------------------------------------------------
>From the PGP Attack FAQ:

 Choosen cipher-text attack
  
   An attacker listens in on the insecure channel in which RSA messages
   are passed. The attacker collects an encrypted message c, from the
   target (destined for some other party). The attacker wants to be able
   to read this message without having to mount a serious factoring
   effort. In other words, she wants m=c^d.
   
   To recover m, the attacker first chooses a random number, r<n. (The
   attacker has the public-key (e,n).) The attacker computes:
   
   x=r^e mod n (She encrypts r with the target's public-key)
   
   y=xc mod n (Multiplies the target ciphertext with the temp)
   
   t=r^-1 mod n (Multiplicative inverse of r mod n)
   
   The attacker counts on the fact property that:
   
                      If x=r^e mod n, Then r=x^d mod n
                                      
   The attacker then gets the target to sign y with her private-key,
   (which actually decrypts y) and sends u=y^d mod n to the attacker. The
   attacker simply computes:
   
    tu mod n = (r^-1)(y^d) mod n = (r^-1)(x^d)(c^d) mod n = (c^d) mod n
                                    = m
                                      
   To foil this attack do not sign some random document presented to you.
   Sign a one-way hash of the message instead.
 
     _________________________________________________________________
                                      
   HTML 3.2 Checked!
   Last modified: 19 Nov 1996
   Author: infiNity <daemon9@netcom.com>
   Comments: galactus@stack.nl
   This document was generated with Orb v1.3 for OS/2.

On Tue, Nov 25, 1997 at 06:49:17PM -0600, William H. Geiger III wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> 
> In <199711260002.BAA28863@basement.replay.com>, on 11/25/97 
>    at 07:02 PM, nobody@REPLAY.COM (Anonymous) said:
> 
> >It would be nifty if there was a way to show that any continuous set of
> >bits were signed given only one signature on a whole document.
> >Intuitively, it seems to me that this might be provably inconsistent with
> >a secure hash.  Still, crypto results are full of surprises, so I could
> >imagine there is a way to do this.
> 
> Well you can do it. Wether you want to do it is another matter.
> 
> For the level of granularity you are sugesting a hash is not pratical.
> 
> You could just use RSA encryption to encrypt the message in the following
> manner:
> 
> The user encrypts the message with his *private* key. Rather than
> encrypting the entire document in one operation he would encrypt each
> [insert you level of granularity here] and then concantinate the results.
> Say we wanted a level of granularity of a word:
> 
> word1 word2 word3 word4
> 
> the resulting cypher text would be:
> 
> cypher1 cypher2 cypher3 cypher4
> 
> Now if someone wished to verifiably quote words 1,3,4 they would include
> cypher1 cypher3 cypher4 in their document.
> 
> Since cypher 1,3,4 could only be generated by original author it can be
> verified that he actually wrote those words.
> 
> At a bare minimum this would have to be done on a level of granularity of
> a sentance to have any meaning at all and even then it's relavance would
> be questioned.

The interesting case is when you do it at the granularity of the bit....

-- 
Kent Crispin				"No reason to get excited",
kent@songbird.com			the thief he kindly spoke...
PGP fingerprint:   B1 8B 72 ED 55 21 5E 44  61 F4 58 0F 72 10 65 55
http://songbird.com/kent/pgp_key.html