Subject: RE: [Cfrg] Request For Opinions

From: "Hallam-Baker, Phillip" <[email-masked]>
Date: Thu, 8 May 2003 04:56:17 -0700

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:[email-masked]]
Sent: Monday, May 05, 2003 2:30 PM
To: [email-masked]
Cc: [email-masked]
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, [email-masked] 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
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg
<https://www1.ietf.org/mailman/listinfo/cfrg>  

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

---

From: canetti <[email-masked]>
Date: Thu, 8 May 2003 09:04:28 -0400 (EDT)

Phill,
This seems to me reminisent of the Gennaro-Rohatgi stream signatures from
Crypto 97.

Ran