RE: [Cfrg] Request For Opinions

[canetti <[e-mail]>]

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:[e-mail]]
> Sent: Monday, May 05, 2003 2:30 PM
> To: [e-mail]
> Cc: [e-mail]
> 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-signatures-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-spec-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, [e-mail] 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
> [e-mail]
> https://www1.ietf.org/mailman/listinfo/cfrg
> <https://www1.ietf.org/mailman/listinfo/cfrg>  
> 
> _______________________________________________ Cfrg mailing list
> [e-mail] https://www1.ietf.org/mailman/listinfo/cfrg
> 
> 

_______________________________________________
Cfrg mailing list
[e-mail]
https://www1.ietf.org/mailman/listinfo/cfrg