RE: [Cfrg] Request For Opinions

"Hallam-Baker, Phillip" <pbaker@verisign.com> Thu, 08 May 2003 14:24 UTC

Received: from www1.ietf.org (ietf.org [132.151.1.19] (may be forged)) by ietf.org (8.9.1a/8.9.1a) with ESMTP id KAA24865 for <cfrg-archive@odin.ietf.org>; Thu, 8 May 2003 10:24:32 -0400 (EDT)
Received: (from mailnull@localhost) by www1.ietf.org (8.11.6/8.11.6) id h48EY2U16308 for cfrg-archive@odin.ietf.org; Thu, 8 May 2003 10:34:02 -0400
Received: from ietf.org (odin.ietf.org [132.151.1.176]) by www1.ietf.org (8.11.6/8.11.6) with ESMTP id h48EY2816301 for <cfrg-web-archive@optimus.ietf.org>; Thu, 8 May 2003 10:34:02 -0400
Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id KAA24849 for <cfrg-web-archive@ietf.org>; Thu, 8 May 2003 10:24:01 -0400 (EDT)
Received: from ietf-mx ([132.151.6.1]) by ietf-mx with esmtp (Exim 4.12) id 19DmLV-000398-00 for cfrg-web-archive@ietf.org; Thu, 08 May 2003 10:26:05 -0400
Received: from ietf.org ([132.151.1.19] helo=www1.ietf.org) by ietf-mx with esmtp (Exim 4.12) id 19DmLU-000395-00 for cfrg-web-archive@ietf.org; Thu, 08 May 2003 10:26:04 -0400
Received: from www1.ietf.org (localhost.localdomain [127.0.0.1]) by www1.ietf.org (8.11.6/8.11.6) with ESMTP id h48EX5816230; Thu, 8 May 2003 10:33:05 -0400
Received: from ietf.org (odin.ietf.org [132.151.1.176]) by www1.ietf.org (8.11.6/8.11.6) with ESMTP id h48EWT816194 for <cfrg@optimus.ietf.org>; Thu, 8 May 2003 10:32:29 -0400
Received: from ietf-mx (ietf-mx.ietf.org [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id KAA24782 for <cfrg@ietf.org>; Thu, 8 May 2003 10:22:28 -0400 (EDT)
Received: from ietf-mx ([132.151.6.1]) by ietf-mx with esmtp (Exim 4.12) id 19DmK0-00038z-00 for cfrg@ietf.org; Thu, 08 May 2003 10:24:32 -0400
Received: from peacock.verisign.com ([65.205.251.73]) by ietf-mx with esmtp (Exim 4.12) id 19DmJz-00038w-00 for cfrg@ietf.org; Thu, 08 May 2003 10:24:31 -0400
Received: from MOU1WNEXC03.verisign.com (verisign.com [65.205.251.57]) by peacock.verisign.com (8.12.9/) with ESMTP id h48EPQdv022145; Thu, 8 May 2003 07:25:26 -0700 (PDT)
Received: by mou1wnexc03.verisign.com with Internet Mail Service (5.5.2653.19) id <KKJG1VQK>; Thu, 8 May 2003 07:25:26 -0700
Message-ID: <CE541259607DE94CA2A23816FB49F4A301AE246C@vhqpostal6.verisign.com>
From: "Hallam-Baker, Phillip" <pbaker@verisign.com>
To: "'jsjoberg@toplayer.com'" <jsjoberg@toplayer.com>
Cc: cfrg@ietf.org
Subject: RE: [Cfrg] Request For Opinions
Date: Thu, 08 May 2003 07:25:25 -0700
MIME-Version: 1.0
X-Mailer: Internet Mail Service (5.5.2653.19)
Content-Type: text/plain; charset="iso-8859-1"
Sender: cfrg-admin@ietf.org
Errors-To: cfrg-admin@ietf.org
X-BeenThere: cfrg@ietf.org
X-Mailman-Version: 2.0.12
Precedence: bulk
List-Unsubscribe: <https://www1.ietf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@ietf.org?subject=unsubscribe>
List-Id: Crypto Forum Research Group <cfrg.ietf.org>
List-Post: <mailto:cfrg@ietf.org>
List-Help: <mailto:cfrg-request@ietf.org?subject=help>
List-Subscribe: <https://www1.ietf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@ietf.org?subject=subscribe>

Jon,

	You might well find that your problem fits into the 5% that does not
get addresses in a 95%/5% split :-(

	I have tried to develop schemes of this type but I have something of
an aversion to anything that looks like mission critical novelty crypto :-)

	I would also see if you could combine an advisory scheme that is
breakable with a non repudiation scheme at regular intervals. In fact I am
recommending that people ALWAYS use HMAC even if they also sign, otherwise
you end up with DoS attacks.

	Note also that chaining blocks may buy you something, if you always
put the hash of the last block in the next the client can choose to validate
as many signatures as it feels it needs to to get NR. Fast clients validate
every one, slow clients validate one a minute.

		Phill



> -----Original Message-----
> From: jsjoberg@toplayer.com [mailto:jsjoberg@toplayer.com]
> Sent: Thursday, May 08, 2003 10:09 AM
> To: pbaker@verisign.com; canetti@watson.ibm.com
> Cc: mcgrew@cisco.com; cfrg@ietf.org
> Subject: RE: [Cfrg] Request For Opinions
> 
> 
> Non-repudiation is a requirement, and going back to the 
> source to validate
> the authentication has been ruled out.
> 
> Putting these together with my weak understanding of the 
> Gennaro-Rohatgi
> stream method, it seemed that scheme didn't work (had to be 
> able to go back
> to the source, or have the stream stored ahead of time).
> 
> Also the ruling out of going back to the source of the data 
> for validation
> is what keeps us from using a nice fast keyed hash approach :(
> 
> I don't think, however, taking the authentication out-of-band has been
> considered.  Not sure what it buys, but worth looking into.
> 
> Thanks again,
> Jon
> 
> -----Original Message-----
> From: Hallam-Baker, Phillip [mailto:pbaker@verisign.com]
> Sent: Thursday, May 08, 2003 9:52 AM
> To: 'canetti'; Hallam-Baker, Phillip
> Cc: 'David Mcgrew'; jsjoberg@toplayer.com; cfrg@ietf.org
> Subject: RE: [Cfrg] Request For Opinions
> 
> 
> Ran,
> 
> 	I think you are probably being unkind to them, they 
> have a solution
> for the infinite case, the scheme I suggest is actually a 
> special case of a
> scheme they describe in the introduction. They also point to 
> some pretty
> good prior art - the java libraries use this technique.
> 
> http://citeseer.nj.nec.com/gennaro97how.html
> 
> 	The article also proposes a solution to the infinite 
> streams case. 
> 
> 
> 	One point to consider is that the bar to an acceptable 
> solution is
> pretty high since it has to address a problem for which HMAC is not
> acceptable (a hard non-repudiation requirement) and for which custom
> hardware is not acceptable.
> 
> 	One issue that I did think of pushing on is the 
> question of whether
> true non-repudiation is the objective or whether it suffices 
> to have an
> authentication metric that does not depend on a shared key across a
> population.
> 
> 
> 	If I had an order to do streaming video over multicast the way I
> would do it is with two independent streams for each user. 
> The first stream
> would be the shared multicast stream. The second stream would be a
> per-subscriber stream that contained the authentication data.
> 
> 	I would encapsulate the video feed in something like 
> DIME and put a
> message digest (SHA1) at the end of each block.
> 
> 	Then I would send to each subscriber a UDP packet 
> containing HMAC
> (MD, k) where k is the session key established between the 
> user and the
> service.
> 
> 	The advantage of DIME is that you can separate the 
> authentication
> channel or do it in band as you choose.
> 
> 	We really need a replacement for the current video-conference
> protocols. the H.3??? scheme stops at every firewall I know. 
> So there is no
> way that most corporate users can videoconference from home. 
> So there might
> be an opportunity to drop this type of idea into the same scheme.
> 
> 
> 	Some other thoughts
> 
> - could use some sort of scheme that was symmetric key based 
> but each party
> only had a subset of the total keying material. Essentially a 
> CDMA type
> idea, each party has a unique subset of the keyspace. 
> 
> So there are 8 keys
> 
> A has the key map  10101010
> B has the key map  11001100
> C has the key map  11110000
> 
> So A can validate the key stream but cannot generate the key 
> stream unless
> she colludes with enough other parties to guarantee she has 
> all the keys.
> 
> 
> To make the process harder there could be a much larger pool 
> of keys than is
> used in each sample. The key maps would change from one step 
> to another so
> that the key maps for block n would be different to those for block m.
> 
> Anyway back to fighting spam, you know the simple stuff.
> 
> 		Phill
> 
> 
> > -----Original Message-----
> > From: canetti [mailto:canetti@watson.ibm.com]
> > Sent: Thursday, May 08, 2003 9:04 AM
> > To: Hallam-Baker, Phillip
> > Cc: 'David Mcgrew'; jsjoberg@toplayer.com; cfrg@ietf.org
> > Subject: RE: [Cfrg] Request For Opinions
> > 
> > 
> > 
> > Phill,
> > This seems to me reminisent of the Gennaro-Rohatgi stream 
> > signatures from
> > Crypto 97.
> > 
> > Ran
> > 
> > 
> > On Thu, 8 May 2003, Hallam-Baker, Phillip wrote:
> > 
> > > Is the data stored data or being generated on the fly?
> > >  
> > > If the data is stored you could sign the data as follows:
> > >  
> > > Divide the stream into n blocks, say 100 blocks of 8K
> > >  
> > > Compute H(n)  the hash of block n,
> > > Compute H(n-1) the hash of block n-1 + H(n)
> > > and so on
> > > Compute H(1), the hash of block 1 + H(2)
> > >  
> > > Then sign H(1) and put it at the START of the stream.
> > > Next send H(1), block 1
> > > H(2), block 2 etc...
> > >  
> > >  
> > > This lets you check the integrity of the stream as you read 
> > the chunks, with
> > > the ability to verify each chunk as you read.
> > >  
> > > You cannot of course sign an infinite stream unless you 
> > have a buffer of
> > > infinite length.
> > >  
> > >  
> > > I have no idea if anyone has thought of this before 
> > (probably have it seems
> > > obvious enough) or if it is patented or anything.
> > >  
> > >         Phill
> > >  
> > >  
> > > 
> > > -----Original Message-----
> > > From: David Mcgrew [mailto:mcgrew@cisco.com]
> > > Sent: Monday, May 05, 2003 2:30 PM
> > > To: jsjoberg@toplayer.com
> > > Cc: cfrg@ietf.org
> > > Subject: Re: [Cfrg] Request For Opinions
> > > 
> > > 
> > > Jon,
> > > 
> > > it seems like you have a viable scheme.  You might be 
> > interested in the
> > > efficient methods for signing of packet streams that have 
> > been discussed in
> > > the IRTF, starting with the Secure Multicast/Group (SMUG) RG (
> > > http://www.securemulticast.org/smug-index.htm
> > > <http://www.securemulticast.org/smug-index.htm> ), which is 
> > now defunct but
> > > has spawned both the IRTF Group Security (GSEC) RG and the 
> > IETF MSEC WG.
> > > There are a bunch of methods that amortize the work of 
> > digital signatures
> > > across multiple packets.  I think the following list 
> covers the main
> > > methods:
> > > 
> > > How to Sign Digital Streams, Gennaro and Rohatgi, Crypto 
> > '97, online at
> > > http://citeseer.nj.nec.com/gennaro97how.html
> > > <http://citeseer.nj.nec.com/gennaro97how.html> .
> > > 
> > > Digital Signatures for Flows and Multicasts, Chung Kei Wong 
> > and Simon S.
> > > Lam,Technical Report TR-98-15, May 31, 1998; revised, June 
> > 14, 1999, in
> > > IEEE/ACM Transactions on Networking, August 1999.
> > > http://www.cs.utexas.edu/users/lam/Vita/IEEE/WongLam99.pdf
> > > <http://www.cs.utexas.edu/users/lam/Vita/IEEE/WongLam99.pdf> 
> > > 
> > > Authenticating Streamed Data in the Presence of Random 
> > Packet Loss, Golle
> > > and Modadugu, NDSS '00, online at
> > > http://crypto.stanford.edu/~nagendra/projects/StreamAuth/auth.pdf
> > > 
> <http://crypto.stanford.edu/~nagendra/projects/StreamAuth/auth.pdf>
> > > Similar but independent work was done by Perrig, Song and 
> > Canetti, IIRC,
> > > though I can't find a link for it at present.
> > > 
> > > The Use of RSA Signatures within ESP and AH, Brian Weis,
> > > 
> > 
> http://www.ietf.org/internet-drafts/draft-bew-ipsec-signatures-00.txt
> > > 
> > <http://www.ietf.org/internet-drafts/draft-bew-ipsec-signature
> > s-00.txt> .
> > > This method could be used with one of the standard methods 
> > for accerating
> > > public key signing or verifying, though it's not explicitly 
> > discussed in the
> > > document.
> > > 
> > > A related but probably not applicable work is "TESLA: 
> > Multicast Source
> > > Authentication Transform Specification", Perrig, Canetti, 
> Whillock,
> > > 
> > 
> http://www.ietf.org/internet-drafts/draft-ietf-msec-tesla-spec-00.txt
> > > 
> > <http://www.ietf.org/internet-drafts/draft-ietf-msec-tesla-spe
> > c-00.txt> .
> > > 
> > > Which of these solutions is the best for any given 
> > application depends on a
> > > bunch of factors, such as the possibility loss and reorder 
> > of packets,
> > > whether or not it is acceptable to buffer packets on the 
> > sender or on the
> > > receiver, and the amount of data that can safely be added 
> > to each packet. 
> > > 
> > > Hope this help,
> > > 
> > > David
> > > 
> > > 
> > > At 11:52 AM 5/5/2003 -0400, jsjoberg@toplayer.com wrote:
> > > 
> > > 
> > > Hey all,
> > > 
> > > I'm in an ETSI working group and we are trying to find a 
> > way to provide
> > > integrity checks along with non-repudiation on a 
> > theoretically infinite
> > > amount of data delivered over a network at 10's to 100's Mbps.
> > > Crypto-hardware is not a reasonable expectation and the 
> solution is
> > > extremely cost sensitive.  
> > > 
> > > The data link will be sending PDU's an an as need basis, 
> > with each PDU being
> > > tagged with a sequence number.  At some point later in time
> > > (days/weeks/years) we need to be able to prove the 
> > integrity of the PDU's as
> > > well as the authenticity.
> > > 
> > > The following is what we have come up with and I'm 
> > wondering if anyone has
> > > anything to add, remove, or change that would make a better 
> > solution.  The
> > > idea is to get some of the authentication strength of 
> > DSS/DSA without the
> > > full strength or the full cost (in processing time).
> > > 
> > > Thanks in advance for any input,
> > > Jon
> > > 
> > > Periodically, hashes over the data PDUs will be inserted 
> > into the data
> > > stream. A hash will only be created if at least one PDU 
> > packet was sent
> > > since the last hash was sent or since startup.
> > > 
> > > Every <n1> PDU packets or when <t1> seconds have passed a 
> > MD5 hash is
> > > generated over all PDU
> > > packets sent since the last MD5 hash was sent or since 
> > startup. The MD5 hash
> > > is sent in a HashPDU, where the HashSequenceNr increments 
> > for every hash
> > > sent for this intercept. The array PDUSequenceNrsIncluded 
> > contains the
> > > sequence number of every data PDU that was included in the hash.
> > > 
> > > NOTE: The values for n1 and t1 are configurable. 
> > > 
> > > Periodically, a hash over the hashes specified above and a 
> > signature of that
> > > hash, will be inserted into the  the data stream. The 
> > signed hashes allows
> > > authentication of the sender and to verfify the integrity 
> > of the recevied
> > > MD5 hashes.
> > > 
> > > Every <n2> hashes or when <t2> seconds have passed, a MD5 
> > hash is generated
> > > over all hashes sent since the last signed hash was sent or 
> > since startup
> > > and that MD5 hash is signed
> > > using DSS/DSA. The MD5 hash and corresponding DSS/DSA 
> > signature are sent
> > > over in a SignedHashPDU, where the SignedHashSequenceNr 
> > increments for every
> > > signed hash sent. The array HashSequenceNrsIncluded 
> > contains the sequence
> > > number of every HashPDU that
> > > was included in the signed hash.
> > > 
> > > NOTE: The values for n2 and t2 are configurable.
> > > 
> > > NOTE: The distribution of the DSS/DSA public key is outside 
> > the scope of
> > > this specification.
> > > 
> > > _______________________________________________
> > > Cfrg mailing list
> > > Cfrg@ietf.org
> > > https://www1.ietf.org/mailman/listinfo/cfrg
> > > <https://www1.ietf.org/mailman/listinfo/cfrg>  
> > > 
> > > _______________________________________________ Cfrg mailing list
> > > Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg
> > > 
> > > 
> > 
> 
_______________________________________________
Cfrg mailing list
Cfrg@ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg