Subject: RE: [Cfrg] Request For Opinions

From: [email-masked]
Date: Thu, 8 May 2003 10:18:05 -0400

Alex,

Thanks alot.  These are good points.  The fact that we don't currently have
solid answers to many of them is uncomfortable.  What we have is:
1.)  Given non-repudiation, no forknowledge of the stream, and the desire to
not have to take the data back to the source for validation, I think we are
stuck with some PK solution.  

2.)  I tend to agree here.  The thought, and maybe it is flawed, is to
amoratize the final hash computation over several packets and buy some
efficiency as well as not have the 16 byte overhead on all packets.

3.)  We have no good answer here.

4.)  We have no good answer here.

5.)  Agreed.

6.)  We have no good answere here.

Thanks!
Jon

-----Original Message-----
From: Alex Alten [mailto:[email-masked]]
Sent: Thursday, May 08, 2003 1:44 AM
To: [email-masked]; [email-masked]
Subject: Re: [Cfrg] Request For Opinions

Hey JS Joberg,

I have been dealing with a very similar problem for the past couple of
years where we are limited to a software driver plugging into a stack.
I'm a bit pressed for time but here is a quick rundown of what I've found.

1. You cannot use any PKI, too slow for 100 Mbps networks, especially
     if you are datagram or transaction oriented with communications
     occurring among N nodes unpredictably.

2. Best to hash per packet, but current hashes are too big, at least
     for Ethernet MTU's.  I don't recommend maintaining a hash state
     across a series of packets, especially if packets can be lost, mixed
     up, or duplicated/retransmitted (true for most protocols).  And unless
     you enjoy debugging complex state machinery.

3. You must specify how manage authentication and encryption keys
     as part of your spec, otherwise it will be a failure.  Not just key
     exchange, the whole thing.  By failure I mean a lack of
interoperability
     between vendors that drives costs up, this is the opposite of what
     a standard should achieve.  By whole thing I mean who has the
     authority to hand out authentication keys, how are keys refreshed,
     how do you handle bad or damaged keys, etc.

4. Think through how you will archive hashes.  What happens if a link
     goes down or your archive crashes.  What operations can proceed
     and those that cannot. How can you recover it? All this can be non-
     trivial.

5. Think simple.  Use memory where possible to reduce design/code
     complexity.

6. Last but definitely not least.  How do you manage your nodes
     address or name ID space.  How are authentication keys bound to
     IDs?  Are keys transient or not? I tend to like a number system
     similar to IP addresses (but don't use them directly!), it's simple
     and easy to distribute the address space management.

I'm sure there are dozen more items I've left off the list, and I'm equally
sure that someone, somewhere will object to each one of these items
above.  Ask them to present their own list to you and to us in CFRG.
It will make for interesting reading if nothing else.

Again, be aware that you need to specify the entire system, not just
a set of protocols.  This is because you must manage keys and IDs
besides the secure packets or the authentication handshakes.

Good luck,

- Alex

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

--

Alex Alten
[email-masked]

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

---

From: Alex Alten <[email-masked]>
Date: Fri, 09 May 2003 18:04:21 -0700

Jon,

>stuck with some PK solution.

Seriously re-examine your decision.  I've built several systems both PKI and
not.  PKI really limits your design options if you want to have 
high-performance.
It's very s-l-o-w cryptography.  There are plenty of fine non-PKI ways of 
doing
the things you would probably want to do.

>efficiency as well as not have the 16 byte overhead on all packets.

Unfortunately this requires queueing on the receiver side at least with the
usual pro's and con's. 16 bytes is a lot of overhead even when using the full
MTU of 1500 bytes/packet. There are two options that I like that are available
to you.

A. Don't use a hash.  The smaller the data payload you are protecting gets the
     less useful it is.  What I like to do in this case is encrypt each 
packet with
     a unique key.  However, key generation & management is much more difficult
     with this approach because of the volume of key material being passed 
around.
     If you need non-repudiation then the key material will need to come 
from a
     trusted 3rd party source.

B. Design a custom hash, say a 4-byte function.  I've done this too, but it is
      not easy to get right, and you will need spend time and treasure 
getting it
      validated properly, unless you are really confident in the hash 
designer's
      skills.  Probably at least $250K and 4-6 months with 2-3 *good* 
cryptanalysts
      (finding them is an art in itself).

- Alex

--

Alex Alten
[email-masked]

---

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

Alex Alten  wrote:
>doing the things you would probably want to do.

This is a huge over-generalization.  SSH, for instance, is quite
adequate for secure remote logsin.  SSL is adequate for e-commerce for
most purposes.  PGP is more than adequate for secure email.  PKI has many
problems, but performance isn't always one of them.  It all depends on
what you want to do and how you use the crypto.

It's tempting to think that public-key crypto is super-expensive and so
we should avoid using it, but this expectation is often not justified.
Go measure, and don't believe your intuition until you've measured.
I believe Knuth once wrote that "premature optimization is the root of
all evil", or something like this, and there's a certain something to
what he said.
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: [email-masked] (David Wagner)
Date: 10 May 2003 01:04:57 GMT

Alex Alten  wrote:
>packet with a unique key.

Maybe I misunderstood your suggestion, but this strikes me as bad
advice.  Encryption without authentication (e.g., a MAC or a signed
hash) often leads to security holes.  Using per-packet keys is no
substitute for authentication.

In any case, I believe the original poster asked for non-repudiation,
not confidentiality, and it would be a mistake to expect encryption to
provide non-repudiation.
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: Henrick Hellström <[email-masked]>
Date: Sat, 10 May 2003 11:16:47 +0200

David Wagner wrote:
 > most purposes.

Isn't that also a huge over-generalization? I would argue that SSL/TLS 
is more adequate for secure remote logins than it is for e-commerce. 
Plus that SSL/TLS often might be a better choice than SSH (just the 
transport layer protocol as per 
http://www.ietf.org/internet-drafts/draft-ietf-secsh-transport-15.txt) 
for designers of new application protocols with a need for secure remote 
logins, because of the way the server authenticates itself to the client 
as part of the transport protocol handshake. Nothing prevents the SSH 
authentication protocol 
(http://www.ietf.org/internet-drafts/draft-ietf-secsh-userauth-16.txt) 
from being run over SSL/TLS, in case the client is mobile and can't 
authenticate itself with a client certificate.

---

From: Alex Alten <[email-masked]>
Date: Sat, 10 May 2003 02:27:42 -0700

>all evil", or something like this, and there's a certain something to

David, I think for the most part we agree in principle, not necessarily in the
details. When one designs using PKI you have to bear in mind its severe
performance limitations.  Where with an AES key you might frequently rekey
to encrypt packets you would want to avoid that with RSA as much as
possible.  That's what I meant by limiting design options.

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.

- Alex
--

Alex Alten
[email-masked]

---

From: Alex Alten <[email-masked]>
Date: Sat, 10 May 2003 02:55:31 -0700

>not confidentiality, and it would be a mistake to expect encryption to

Yes, this is unusual and doesn't fit his requirements.  One design I
worked on was retrofitting an old protocol and I had to give up using a
hash (not enough room in the legacy header and I couldn't change
packet sizes or tunnel). In this case I was more concerned with raw
privacy than anything else. I was thinking that authentication would
come about in some other way. Possibly a 3rd party authenticates
both the sender and receiver before issuing them session keys.

For non-repudiation there are some well known solutions to choose
from.  The trick is not to depend on the trustworthiness of either the
sender or the receiver.

- Alex
--

Alex Alten
[email-masked]

---

From: Henrick Hellström <[email-masked]>
Date: Sat, 10 May 2003 12:03:08 +0200

> possible.  That's what I meant by limiting design options.

This is common knowledge. Renegotiation in SSL/TLS involves pseudo 
random number generation and hash based key derivation only. No 
public/private key operations.

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

---

From: [email-masked] (David Wagner)
Date: 10 May 2003 18:08:29 GMT

Alex Alten  wrote:
>privacy than anything else.

That still sounds a bad idea.  For anyone else who might be reading
this, let me innoculate you against a popular misconception: contrary to
what intuition might suggest, encryption without authentication doesn't
necessarily provide privacy.  It sounds counter-intuitive, but it's true.
Trust me.  We've been through this with IPSec, with SSH, and with WEP,
and it just keeps become more and more clear.  Even if all you want is
confidentiality, you still want to use *both* encryption and a MAC.
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: [email-masked] (David Wagner)
Date: 10 May 2003 18:05:09 GMT

Alex Alten  wrote:
>possible.

I don't think you've thought about this carefully enough.  Use public-key
crypto to exchange a shared AES key, and then you can re-key using that
AES key just as you would if you weren't using public-key crypto.

>Heck the hashing alone eats up 30% of its performance.

Two posts ago, you advised people not to use public-key crypto, because
the overhead is too high.  Now you're saying that SSL is too slow,
not because of the public-key, but because of the hashing.
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

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

>AES key just as you would if you weren't using public-key crypto.

OK, I agree this is a scenario where RSA is used to exchange a single AES
over a long session of packets is fine.  But if I'm doing single packets, and
changing AES keys a lot, it doesn't work very well.  So if you want to use
RSA then this 2nd scenario is not very feasible, performance-wise.  That's
all I'm saying about PK limiting your design options in high-speed designs.

>not because of the public-key, but because of the hashing.

That's not what I mean't.  SSL has both high PK and hash costs.  Most of
my response was discussing the PK performance penalty limiting high-
performance design choices.  David at least you can admit to the
reasonableness of that statement.  Right?

- Alex

--

Alex Alten
[email-masked]

---

From: [email-masked] (David Wagner)
Date: 10 May 2003 21:03:38 GMT

Alex Alten  wrote:
>changing AES keys a lot, it doesn't work very well.

So don't do that, then.  No one said you need to use RSA on every packet.
Come on.  This is getting really silly!

Patient: "Doctor, doctor, it hurts when I use RSA on every packet."
Doctor:  "Don't do that, then."

>reasonableness of that statement.  Right?

That's ridiculous.  The public-key in SSL has nothing to do with whether
its hash function or MAC primitive is fast or slow.  Again, I don't think
you've thought about this carefully enough.
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: Alex Alten <[email-masked]>
Date: Sat, 10 May 2003 15:56:37 -0700

>Doctor:  "Don't do that, then."

We both agree that it is silly.  And that's exactly my point.  But one might
reasonably consider using AES instead of RSA.

- Alex

--

Alex Alten
[email-masked]

---

From: "Anton Stiglic" <[email-masked]>
Date: Mon, 12 May 2003 10:26:43 -0400

----- Original Message ----- 
From: "Alex Alten" <[email-masked]>

[...]
> reasonably consider using AES instead of RSA.

I don't think you get David's point.

You were suggesting not to use PK crypto when designing protocols,
because you said it's to slow.  Then, to back up your claim you give a
dubious
example (re-keying multiple times when sending single packets).
If you would be a good crypto protocol designer, you would never suggest
such a thing.

Personally I've never seen a situation where the speed of PK crypto was
a problem  (except when the protocols where not well designed).

--Anton

---

From: Alex Alten <[email-masked]>
Date: Tue, 13 May 2003 10:38:01 -0700

>a problem  (except when the protocols where not well designed).

I sincerely believe I understand David's point.  As far as I can tell he has so
deeply ingrained in himself the limitations of various ciphers that he knows
instinctively what design approach to use for a given problem. I suppose my
example above may seem a bit contrived.  But step back and take a good look
at the  fundamental facts about PK (say RSA v.s. AES).

The facts about PK are:
1. Key generation is dog slow
2. Key setup is damn slow.
3. Encryption is like watching grass grow or paint to dry.

Yes, one can design a fast protocol with these limitations, but there are a 
lot of
hoops to jump through, with only a few tried and true ways to do it 
well.  Usually
one gets off to a slow start with PK and then as quickly as possible 
switches to
a block cipher.  Most designs tend to be fairly long lived sessions in 
order to
amortize the costly initial use of PK.

Using only a block cipher like AES, with modern PC's, in a 100 Mbps network
environment, all 3 limitations fall away.  As a result you can reconsider 
or try
new designs one would never hope to use when PK is in the mix.

I hope this clarifies my point, which is that PK hampers high-performance
design choices.

- Alex

--

Alex Alten
[email-masked]

---

From: Gé Weijers <[email-masked]>
Date: Tue, 13 May 2003 11:57:00 -0700 (US Mountain Standard Time)

> 3. Encryption is like watching grass grow or paint to dry.

4. It's often the only tool that gets the job done.

If we cannot solve a problem satisfactorily using our usual symmetric
primitives like PRPs, PRFs, hash functions, MACs etc. we will have to
resort to more expensive primitives.  They're the cheapest ones that get
the job done.

Some operations are actually quite efficient, for example RSA encryption
using a low exponent (3 or 65537).

I wrote a signature verification routine in portable C about 4-5 years
back, to verify Rabin-based signatures. The large integer routines were
home grown and far from optimized. Verification took about 1 ms on a 200
Mhz pentium clone processor (1024 bit keys). Our hardware is at least 10
times faster now, so we're probably talking about 100us verification
times.

Signature generation (2 512-bit exponentiations and an application of
Garner's algorithm) took 500 ms using a good bignum library, so on current
hardware we're probably getting close to 50 ms. No paint dries this fast.

Some new processors have instruction sets optimized to perform big number
arithmetic efficiently, so this will soon even be less of an issue. And if
you're really in a hurry you can buy accellerators that perform modular
exponentiation in hardware.

Ge'

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