Subject: RE: [Cfrg] Request For Opinions

From: [email-masked]
Date: Mon, 5 May 2003 12:19:54 -0400

Yes, that is what is meant.  I may have mis-used the term "authentication",
let me know if I did.

Thanks,
Jon
-----Original Message-----
From: Steven M. Bellovin [mailto:[email-masked]]
Sent: Monday, May 05, 2003 12:17 PM
To: [email-masked]
Cc: [email-masked]
Subject: Re: [Cfrg] Request For Opinions 

In message <[email-masked]>,
js
[email-masked] writes:
>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.

Let me clarify something, since the phrase "non-repudiation" is often
misused.  Without going into technical definitions, the right meaning is
"A wants to prove to a third party -- the judge -- that B sent certain 
packets, and in particular that A cannot have forged them".  Is that 
what you mean?

		--Steve Bellovin, http://www.research.att.com/~smb (me)
		http://www.wilyhacker.com (2nd edition of "Firewalls" book)

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

---

From: David Mcgrew <[email-masked]>
Date: Mon, 05 May 2003 11:29:52 -0700

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),
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.

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

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
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.
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.

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

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]

---

From: "Scott Cadzow" <[email-masked]>
Date: Thu, 8 May 2003 14:16:51 +0200

The data is streamed generally, storage is frowned upon.
 
S

	-----Original Message----- 
	From: Hallam-Baker, Phillip [mailto:[email-masked]] 
	Sent: Thu 08/05/2003 13:56 
	To: 'David Mcgrew'; [email-masked] 
	Cc: [email-masked] 
	Subject: RE: [Cfrg] Request For Opinions

	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), 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.
		
		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
		
		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    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.  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.
		
		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

			Hey all,

			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).

			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.

			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 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

---

From: "Hallam-Baker, Phillip" <[email-masked]>
Date: Thu, 8 May 2003 06:51:57 -0700

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

> From: canetti [mailto:[email-masked]]
> Sent: Thursday, May 08, 2003 9:04 AM
> To: Hallam-Baker, Phillip
> Cc: 'David Mcgrew'; [email-masked]; [email-masked]
> 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:
> 
> > 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
> >  
> >  
> > 
> > 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:
> > 
> > http://citeseer.nj.nec.com/gennaro97how.html
> > <http://citeseer.nj.nec.com/gennaro97how.html> .
> > 
> > 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> 
> > 
> > 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://www.ietf.org/internet-drafts/draft-bew-ipsec-signatures-00.txt
> > 
> <http://www.ietf.org/internet-drafts/draft-bew-ipsec-signature
> s-00.txt> .
> > 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,
> > <https://www1.ietf.org/mailman/listinfo/cfrg>  
> > 
> > _______________________________________________ Cfrg mailing list
> > [email-masked] https://www1.ietf.org/mailman/listinfo/cfrg
> > 
> > 
>

---

From: [email-masked]
Date: Thu, 8 May 2003 10:09:25 -0400

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:[email-masked]]
Sent: Thursday, May 08, 2003 9:52 AM
To: 'canetti'; Hallam-Baker, Phillip
Cc: 'David Mcgrew'; [email-masked]; [email-masked]
Subject: RE: [Cfrg] Request For Opinions

Ran,

	Some other thoughts

So there are 8 keys

		Phill

---

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

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

> From: [email-masked] [mailto:[email-masked]]
> Sent: Thursday, May 08, 2003 10:09 AM
> To: [email-masked]; [email-masked]
> Cc: [email-masked]; [email-masked]

---

From: David Mcgrew <[email-masked]>
Date: Thu, 08 May 2003 07:48:17 -0700

Jon,

thanks for clarifying.  I have a couple of questions.

The work that I'd cited was aimed at asymmetric authentication of packet 
flows.  One of the goals of this work is to limit the amount of data that a 
receiver needs to buffer, for obvious networking reasons.  However, I 
expect that in your case, buffering is not an issue.  Since we expect to be 
able to provide long-term nonrepudiation on the data, we're storing it 
somewhere :-)   So if there were no packet loss, then we could hash all of 
the packets in a flow, then sign it once its over.  You mention that a 
sequence number is associated with the packets in the flow, so I expect 
that there's a well-defined session.  (I'm curious here.  What is the 
protocol, and how is the 'session' defined?)   The sequence number would 
make the order of the packets fed into the hash unambiguous, so it seems to 
me that the packet loss is the only complication.  Thinking out loud, this 
would seem to be a problem if the point in the network where the 
nonrepudiation service were applied was different from the point that did 
the storage.  I expect that this is the case, since otherwise we could just 
use a trusted storage device and go home early that day :-)

David

At 10:09 AM 5/8/2003 -0400, [email-masked] wrote:
> > <http://www.ietf.org/internet-drafts/draft-bew-ipsec-signature> s-00.txt> .
> > <http://www.ietf.org/internet-drafts/draft-ietf-msec-tesla-spe> c-00.txt> .
> > >

---

From: "Steven M. Bellovin" <[email-masked]>
Date: Sat, 10 May 2003 08:49:29 -0400

In message <[email-masked]>, Alex Alten write
s:

>
>I don't know about SSH, but I don't consider SSL a high-performance design.
>Heck the hashing alone eats up 30% of its performance. I seriously doubt a
>FTP or NetBIOS file transfer over SSL can go much above 10 Mbps (even
>with the RC4 cipher) on a 1 GHz PC across a LAN. PGP is more for large
>static files so it is not a model for a secure computer networking protocol
>with smaller PDU packets.

For fun, I tried a ttcp over ssh transfer between my laptop (850 Mhz) and my
desktop (750 Mhz), over a 100 Mbps switched hub.  I got 59 Mbps using 
AES encryption.  SSL with RC4 would be much faster.

Sender:
b149$ ttcp -f k -n 20480 -p 5000 -s -t 127.0.0.1
ttcp-t: buflen=8192, nbuf=20480, align=16384/0, port=5000  tcp  -> 127.0.0.1
ttcp-t: socket
ttcp-t: connect
ttcp-t: 167772160 bytes in 22.21 real seconds = 59025.17 Kbit/sec +++
ttcp-t: 20480 I/O calls, msec/call = 1.11, calls/sec = 922.27
ttcp-t: 0.0user 0.9sys 0:22real 4% 0i+0d 0maxrss 0+2pf 10238+83csw

Receiver:
$ ttcp -f k -p 5000 -r -s
ttcp-r: buflen=8192, nbuf=2048, align=16384/0, port=5000  tcp
ttcp-r: socket
ttcp-r: accept from 127.0.0.1
ttcp-r: 167772160 bytes in 22.22 real seconds = 58993.64 Kbit/sec +++
ttcp-r: 20481 I/O calls, msec/call = 1.11, calls/sec = 921.82
ttcp-r: 0.0user 0.3sys 0:22real 1% 0i+0d 0maxrss 0+2pf 10241+36csw

Now, you specified "file transfer", which implies disk I/O, and that 
has nothing to do with over-the-wire crypto speed.  I first ensured 
that a 11 MB file was in the buffer cache.  I then copied it between 
the same two machines using scp (the ssh copy command).  Wire transfer 
time was 31 Mbps -- and that's counting the overhead of the public key 
operations to set up the connection.  To better measure just the 
symmetric encryption, which is what you asked about, I copied a 110 MB 
file -- it went at 55 Mbps.

The test software was OpenSSH 3.4 on NetBSD 1.6.1 and OpenSSH 3.6.1 on
NetBSD-current, using AES-128 for confidentiality, RSA for 
authentication, and DH for perfect forward secrecy.

---

From: "Hallam-Baker, Phillip" <[email-masked]>
Date: Sat, 10 May 2003 06:20:23 -0700

An interesting corollary to Steve's post is 'XML Accelerator' boxes that
promise to secure Web Service transactions through fast XML Schema
validation.

Just a pity they don't do hardware acceleration of RSA signature generation
and verification, guess what is the bottleneck when you are doing signed
messages of about 4-16K a time?

		Phill

> Sent: Saturday, May 10, 2003 8:49 AM
> To: Alex Alten
> Cc: [email-masked]; [email-masked]
> In message 
> <[email-masked]>, Alex Alten write
> s:
> 
> 
> >

---

From: Alex Alten <[email-masked]>
Date: Sat, 10 May 2003 14:04:49 -0700

I forgot to cc this to the list.  I bet the NetBios is behaving badly
with the MS VPN underneath it.  - Alex

>Date: Sat, 10 May 2003 03:55:26 -0700
>To: Henrick Hellström <[email-masked]>
>From: Alex Alten <[email-masked]>
>At 12:03 PM 5/10/2003 +0200, you wrote:
>
>>>with the RC4 cipher) on a 1 GHz PC across a LAN.
>>
>>With a good implementation, RC4_MD5 can go above 100 MBit/s on a 1 GHz PC 
>>and ~2/3 of the CPU.
>
>Really?  I haven't done direct measurements with SSL lately.  However I 
>just recently
>was trying out the Microsoft VPN (PPTP/CHAPv2).  It uses RC4.  I tried to 
>transfer
>a large file over Fast Ethernet using a 1.7 GHz PC (the other end was 2.4 
>GHz).
>I could only get 12-16 Mbps throughput.  In the clear I got about 90 Mbps.  So
>your results seem rather remarkable.  Did you use ordinary HTTP file 
>transfer or
>something else?
>
>- Alex

--

Alex Alten
[email-masked]