Subject: Re: [Cfrg] Request For Opinions

From: "Steven M. Bellovin" <[email-masked]>
Date: Mon, 05 May 2003 12:16:49 -0400

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: [email-masked]
Date: Mon, 5 May 2003 11:52:34 -0400

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.

---

From: [email-masked] (David Wagner)
Date: 5 May 2003 16:01:07 GMT

>extremely cost sensitive.  

Your approach sounds like a reasonable one.  I take it you have
a reliable link?  (Otherwise, if packets can be dropped, you'll
need some extra mechanism: it's hard to verify the signature if
you're missing a packet.)

Since you want non-repudiation, you probably don't want to skimp
on the size of the public key.  Since you're probably CPU-bound,
I'd choose keysizes as large as you can reasonably afford.

I assume signing cost is the only important metric.  (RSA gives
big improvements in verification time, but that sounds irrelevant
to your application.)

Notice that DSA allows precomputation.  You can do most of the
work of the signature ahead of time, before you know the message;
basically, you create a "blank check" that can later be filled in
with the message, and most of the work comes in creating the blank
check (filling in the message is fast).  If you have stretches of
quiet time punctuated by bursts of activity, you might be able to
use the idle time for precomputation.

If speed is still a problem, you might consider faster public-key
systems, like elliptic curves or maybe even NTRU.  The security
of these systems is more uncertain, so DSA is preferable from a
security point of view.  Still, if DSA is too slow and your only
choice is between NTRU or nothing, NTRU is a much better bet than
nothing!  However, beware of patents and other intellectual property
minefields in this area.

I'd use SHA1 rather than MD5.
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: Alfonso De Gregorio <[email-masked]>
Date: Mon, 5 May 2003 19:23:13 +0200

Dear Jon,

the mechanism the working group have come up reminds me the method employed
in syslog-sign [1] to add "origin authentication, message integrity,
replay-resistance, message sequencing, and detection of missing messages"
to the BSD syslog protocol [2].

As far as I can tell, in a generic application context (i.e., not in the
message logging one), this mechanism is less than optimal since the 
recipient cannot rely neither upon the integrity, nor upon the 
authenticity of exchanged PDUs until authentication-PDU get received.

Hope it helps.

Cheers,
Alfonso

[1] C. Lonvick, "The BSD syslog Protocol", rfc 3164,
    <http://www.ietf.org/rfc/rfc3164.txt>

[2] J. Kelsey, J. Callas, "Syslog-Sign Protocol",
    draft-ietf-syslog-sign-10.txt,
    <http://www.ietf.org/internet-drafts/draft-ietf-syslog-sign-10.txt>

---

From: "Anton Stiglic" <[email-masked]>
Date: Mon, 5 May 2003 14:22:27 -0400

"David Wagner" <[email-masked]> wrote in message
news:[email-masked]...

[...]
> use the idle time for precomputation.

Is there not a patent on this technique (by Micali maybe)? I remember
something about a patent on DSA precomputation, but I don't remember
the details...

--Anton

---

From: Gé Weijers <[email-masked]>
Date: Mon, 05 May 2003 13:56:30 -0700 (US Mountain Standard Time)

> use the idle time for precomputation.

A scheme like GPS could be useful if the efficiency constraints are
severe. It requires only one multi-precision multiplication and no modular
arithmetic in the time-critical signing operation if you generate
use-and-throw coupons during processor idle times. DSA still requires
arithmetic modulo a 160-bit prime.

Patent caveats do apply.

Ge'

-- 
Gé Weijers                mailto:[email-masked]
Sun Linux Security Group  Tel: (877)240-7611 x69536
Sun Microsystems, Inc.    Fax: (877)240-7611
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg