Subject: [Hipsec] Digital Signature Algorithms

From: [email-masked] (Julien Laganier)
Date: Thu Oct 7 08:12:00 2004

Hi Folks,

Looking at the paper "Experience with the Host Identity Protocol for 
Secure Mobility and Multihoming" by Henderson et al., I found that 
DSA signing and verification account for a huge part of the 
association set-up latency.

Hence, I am wondering what is the rationale for HIP to specify DSA as 
a MANDATORY algorithm, although RSA signatures verification might be 
ten times faster than DSA?

Also what about using Elliptic Curve Cryptography (e.g., EC-DSA) which 
has reduced P.K. and signatures size, and can be as fast or faster 
than RSA?

Thanks,

--julien

---

From: [email-masked] (Jari Arkko)
Date: Thu Oct 7 08:20:01 2004

There used to be IPR concerns with RSA, but I believe
the patents expired. ECC is a mine field of IPR, so
I'd rather stay out of it if possible.

I'd go for RSA, personally.

--Jari

Julien Laganier wrote:
> _______________________________________________
> Hipsec mailing list
> [email-masked]
> http://honor.trusecure.com/mailman/listinfo/hipsec
> 
>

---

From: [email-masked] (Julien Laganier)
Date: Tue Oct 12 11:49:03 2004

> I'd go for RSA, personally.

So how does people feel about making both DSA and RSA mandatory in 
HIP?

Thanks,

--julien

> Julien Laganier wrote:
> > Hi Folks,
> >
> > Looking at the paper "Experience with the Host Identity Protocol
> > for Secure Mobility and Multihoming" by Henderson et al., I found
> > that DSA signing and verification account for a huge part of the
> > Hence, I am wondering what is the rationale for HIP to specify
> > DSA as a MANDATORY algorithm, although RSA signatures
> > verification might be ten times faster than DSA?
> >
> > Also what about using Elliptic Curve Cryptography (e.g., EC-DSA)
> > which has reduced P.K. and signatures size, and can be as fast or
> > faster than RSA?
> >
> > Thanks,
> >
> > --julien

---

From: [email-masked] (Pekka Nikander)
Date: Wed Oct 13 00:54:01 2004

> So how does people feel about making both DSA and RSA mandatory in

I don't have any strong opinions.  IIRC, the usual IETF crypto
guidelines state that

   a) there must be at least one common MUST implement
      algorithm that is considered secure enough

   b) the algorithms must be negotiable so that if the
      currently MUST implement turns out to be insecure,
      the implementations can be easily upgraded to use
      some other, new MUST implement algorithm

Anyone care to check what the guidelines and other
documents actually say?

   draft-ietf-ipsec-ikev2-algorithms-05.txt
   draft-iab-auth-mech-03.txt
   crypto forum?

 From a robustness point of view, it would of course good to
have multiple MUST implement algorithms.  OTOH, I think
that there should also be some guidelines how to use them
so that the chances of interoperability are maintained
even in the case that one of the hosts only supports one
algorithm, e.g., due to policy reasons.

Maybe we could have DSA as MUST and RSA as SHOULD?

--Pekka

---

From: [email-masked] (Julien Laganier)
Date: Wed Oct 13 10:33:01 2004

On Wednesday 13 October 2004 08:02, Pekka Nikander wrote:
> > So how does people feel about making both DSA and RSA mandatory
> > in HIP?
>

This one doesn't talk about RSA or DSS (only DH, PRF and HMAC). RSA=20
and DSS usage seems to be both MUST in draft-ietf-ipsec-ikev2-17.txt.=20

However, an interesting thing is the new requirements keywords defined=20
in draft-ietf-ipsec-ikev2-algorithms-05.txt:

SHOULD+            This term means the same as SHOULD. However it is
                   likely that an algorithm marked as SHOULD+ will be
                   promoted at some future time to be a MUST.
SHOULD-            This terms means the same as SHOULD. However an
                   algorithm marked as SHOULD- may be deprecated to a
                   MAY in a future version of this document.
MUST-              This term means the same as MUST. However we
                   expect at some point that this algorithm will no
                   longer be a MUST in a future document. Although
                   its status will be determined at a later time,it
                   is reasonable to expect that if a future revision
                   of a document alters the status of a MUST-
                   algorithm, it will remain at least a SHOULD or a
                   SHOULD-.

>=A0 =A0draft-iab-auth-mech-03.txt

It said:

=2D-------------------
While the desire to support legacy authentication systems is under-
standable, it should be resisted to the extent possible. Having mul-
tiple equivalent mechanisms dramatically increases both implementa-
tion complexity and interoperability problems. When designing a new
system, designers should choose a very small number of authentication
mechanisms, with no more than one of any given class.
=2D-------------------

And later

=2D-------------------
13.2. Use As Few Mechanisms as You Can

Preferably, systems should have only one form of authentication. The
more methods of authentication a system allows, the more things there
are to go wrong. Remember that a chain is only as strong as its weak-
est link. In general, there are two reasons why systems allow more
than one authentication mechanism. The first is that you're
retrofitting a system which already has a large number of authentica-
tion mechanisms which cannot be displaced. The second is that users
have widely different environments which for some reason cannot use
the same authentication mechanism conveniently (e.g. some users have
tokens and some do not).

Naturally, designers need to take such considerations into account
but they should take reasonable steps to minimize the number of mech-
anisms. Designers should take special care to minimize the number of
equivalent mechanisms. For instance, a system that provides a chal-
lenge/response mechanism and a public key based mechanism is a rea-
sonable design, one that provides three different challenge/response
mechanisms is not.

This doesn't mean that designers should not use security frameworks
where multiple mechanisms are appropriate, but it does mean that they
should be avoided unless necessary. Where generic security frameworks
are used, they supported mechanisms should be carefully profiled to a
minimal set.
=2D-------------------

>=A0 =A0crypto forum?

I can ask them.

> Maybe we could have DSA as MUST and RSA as SHOULD?

I'm a bit confused by what I've read on the subject: IKEv2 has DSA as=20
MUST and RSA as MUST, but draft-iab-auth-mech says that it should be=20
avoided unless necessary.

If RSA is a SHOULD, HIP will probably needs a mean to negotiate HI=20
algorithm capabilities (between RSA and DSA), so I tend to think that=20
we should have both as MUST.

Is there any other opinions the subject?

Thanks,

=2D-julien

---

From: [email-masked] (Jari Arkko)
Date: Wed Oct 13 11:16:01 2004

I'd be fine with just one algorithm (for now).
And my slight preference for that algorithm is
RSA...

--Jari

Julien Laganier wrote:
> This one doesn't talk about RSA or DSS (only DH, PRF and HMAC). RSA 
> and DSS usage seems to be both MUST in draft-ietf-ipsec-ikev2-17.txt. 
> 
> However, an interesting thing is the new requirements keywords defined 
> --------------------
> --------------------
> --------------------
> --------------------
> I'm a bit confused by what I've read on the subject: IKEv2 has DSA as 
> MUST and RSA as MUST, but draft-iab-auth-mech says that it should be 
> If RSA is a SHOULD, HIP will probably needs a mean to negotiate HI 
> algorithm capabilities (between RSA and DSA), so I tend to think that

---

From: [email-masked] (Julien Laganier)
Date: Fri Oct 15 06:58:01 2004

Folks,

About the DSA vs RSA issue, here's an excerpt of a CFRG email 
mentionning an opinion about what algorithm should be used in 
existing, and new protocol/applications.

--julien

----------  Forwarded Message  ----------

Subject: RE: [Cfrg] Re: [saag] Bad day at the hash function factory
Date: Thursday 26 August 2004 19:32
From: "Hallam-Baker, Phillip" <[email-masked]>
To: "'Steven M. Bellovin'" <[email-masked]>, "Hughes, James P" 
<[email-masked]>
Cc: "[email-masked]'" <[email-masked]>, "[email-masked]'" 
<[email-masked]>, "[email-masked]'" <[email-masked]>

I think that we should track status of crypto algs independently of
 their standards status. In particular I think that we should
 distinguish between Recommended and Acceptable status.

New applications should specify algorithms with Recommended status
Continued use of algorithms with Acceptable status should not raise
 concern.

So I would classify as follows:

Proposed: SHA-2
Recommended: SHA-1, HMAC-SHA1, RSA-2048, RSA-4096, AES, DH-1024
Acceptable: HMAC-MD5, RSA-1024, 3DES, DSA, DH-512, RC4
Depricated: IDEA, RSA1024+MD5
Obsolete: MD4, MD5, RSA-512, DES

The reason that I distinguish between Depricated and obsolete is that
 there are uses of RSA signatures with MD5 hash that are still
 acceptably secure and the applications concerned do not support
 SHA1. The reason I put DSA as acceptable rather than recommended is
 that it does need a good random seed, the key size is small and it
 is unlikely at this point to see much use.

RC4 has been compromised by Shamir & co, but as a general rule I
 don't think any stream cipher should ever get a higher status than
 acceptable. A stream cipher always allows a person who has a
 plaintext and ciphertext corresponding to a key to encode or decode
 all messages with that key that are shorter or the same size. In
 effect all stream ciphers are vulnerable to a trivial form of known
 plaintext attack, the attack does not reveal the key but this is not
 necessary.

I do not feel confident in recommending moving to SHA2 at this point.
 Before jumping I want to see that the place we are going to is
 better than where we left. SHA2 is not currently widely used. If it
 turns out that the recent cryptanalysis of SHA1 is also applicable
 to the structures used in SHA2 then the rationale for a change is
 lost. I would feel happier moving to a hash function based on AES
 encryption (which i had eroneously assumed had been the point of the
 SHA2 work).

---

From: [email-masked] (Petri Jokela)
Date: Mon Oct 18 06:24:00 2004

So, what people think? We have (at least) four alternatives:

1) Stay at current: DSA mandatory

2) Both DSA and RSA mandatory

3) DSA mandatory, RSA SHOULD

4) Change the mandatory to RSA

Opinions?

/petri

---

From: [email-masked] (Pekka Nikander)
Date: Mon Oct 18 06:34:01 2004

My sense from the discussion so far is that people slightly
favour RSA.  Hence, apparently we should go for

   - RSA MUST implement algorithm
   - DSA SHOULD implement algorithm

What comes to algorithm negotiation, I think that we can
go with the following approach:

   1. In the case where the Initiator pre-fetches the
      Responder's HIT from somewhere (DNS, DHT, local storage),
      it can select a HIT that uses the desirable algorithm.
      That is, if the Initiator wants to use RSA, it selects
      an RSA based HIT for the Responder.

   2. In the case where the Initiator sends a NULL HIT
      in I1 (opportunistic mode), we can simply state that
      the Initiator MUST support both RSA and DSA, and
      that the Responder SHOULD use a MUST algorithm (RSA)
      based key.

To facilitate that, it seems that changing Step 4 in
Section 8.5 is enough:

--

   4. The R1 MUST contain the received responder HIT, unless the
      received HIT is NULL, in which case the Responder SHOULD
      select a HIT that is constructed with the MUST algorithm
      in Section 3, which is currently RSA.  Other than that,
      selecting the HIT is a local policy matter.
--

Adding some text to 7.1 doesn't seem to hurt:

   Add after "NULL (all zeros) as the Responder's HIT":
--
   If the Initiator send a NULL as the Responder's HIT, it
   MUST be able to handle all MUST and SHOULD algorithms
   from Section 3, which are currently RSA and DSA.
--  

If everybody is happy with that, we apparently need the
following changes:

   - change second paragraph of Section 3 as follows:

--
    HIP implementations MUST support the Rivest Shamir Adelman (RSA)
    [XXX] public key algorithm, and SHOULD support the Digital Signature
    Algorithm (DSA) [13] algorithm; other algorithms MAY be supported.
--

   - new text to 3.1.1 to define, exactly, how to compute a
     HIT from a given RSA key. [I'm off-line so I can't prepare
     a proposal.]

   - fix the references in 6.2.10

   - change the example text in the end of 6.2.13 to
     include text for RSA.

   - Add RFC 3110 reference which seems to be missing.

I couldn't find any other places in the base spec, but
may be there are others.

--Pekka

---

From: [email-masked] (Miika Komu)
Date: Tue Oct 19 13:24:03 2004

> 4) Change the mandatory to RSA

First, I was going to say that I have had already enough fun with
debugging host identifiers, and that changing the RSA as the default in
our implementation will be a pain in you-know-where, but then I came up
with something more productive :)

There are some performance measurements on DSA and RSA e.g.
in http://www.eskimo.com/~weidai/benchmarks.html:

  DSA 1024 Signature      2.18 ms
  RSA 1024 Signature      4.75 ms

    => DSA signing is 2.2 faster

  DSA 1024 Verification   2.49 ms
  RSA 1024 Verification   0.18 ms

    => RSA verification is 13.9 faster

The initiator does two verifications (on R1 and R2) and one signature
(I2). Since the RSA verification is much more faster, and the initiator
does two of them, the initiator would get the most benefit.

Without precreated R1s, the responder does one verification (I2) and two
signatures (R1, R2). As the RSA signature creation is slower than with
DSA, the responder has to do more work when using RSA.

Intuitively, changing the default algorithm from DSA to RSA favours more
initiators. We can verify this with a quick-and-dirty calculation based on
the number of the cryptographic operations, and the time required for the
cryptographic operations:

initiator(dsa): 2 * 2.49 ms + 2.18 ms = 7.16  ms
responder(dsa): 2 * 2.18 ms + 2.49 ms = 6.85  ms
                                        ====
                                total = 14.01 ms

initiator(rsa): 2 * 0.18 ms + 4.75 ms = 5.11  ms
responder(rsa): 2 * 4.75 ms + 0.18 ms = 9.68  ms
                                        ====
                                total = 14.79 ms

We can see the favouring of the initiator of the above figures quite
clearly. It should be noticed that the total time spent for signing and
verifying remains almost the same with both the RSA and DSA. Of course,
the figures are greater when a real HIP base exchange is conserned, but
still proportional to the figures above. With precreated R1s the figures
are as follows (responder "skips" one signature):

initiator(dsa): 2 * 2.49 ms + 2.18 ms = 7.16  ms
responder(dsa): 2.18 ms + 2.49 ms     = 4.67  ms
                                        ====
                                total = 11.83

initiator(rsa): 2 * 0.18 ms + 4.75 ms = 5.11  ms
responder(rsa): 4.75 ms + 0.18 ms     = 4.93  ms
                                        ====
                                total = 10.04 ms

The total time is almost the same with RSA and DSA. The initiator is now
half the faster using RSA and responder is only slightly slower. This is a
much better situation than before from the viewpoint of the responder, but
performance obtained by the initiator is still quite minimal.

In the light of these performance estimation figures, I still prefer the
DSA because it is more friendly for the responders (i.e. busy servers) in
the case where R1s are created on-the-fly; this is also coherent with the
current architecture in which the initiators should do more work than
responders due to DoS protection. On the other hand, we may have the
increase the cookie size artificially in the implementation when using RSA
because the responder will be doing more work in such a case. As a result,
the *total* amount of work done by both the initiator and responder
increases, and it is a bad idea IMHO.

We should also notice that DSA is about 60 times faster in the key
generation than RSA. Maybe this is useful e.g. for hosts that create lots
of anonymous identifiers on the fly.

-- 
Miika Komu              [email-masked]          http://www.iki.fi/miika/

---

From: [email-masked] (Jari Arkko)
Date: Tue Oct 19 14:05:01 2004

Hi Miika, and thanks for doing the math for
the rest of us! Your numbers are indeed interesting,
and somewhat surprising, taking into account the
difference between initiators and responders.

> the case where R1s are created on-the-fly; this is also coherent with the

I think the precreated R1 case is the default assumption,
and should be at any rate if performance is a concern.
So I'd like us to consider that situation as our primary
problem. If I understood your numbers right, there was a
minor increase dsa->rsa for responders in this case and
a bigger decrease dsa->rsa for initiators. Based on this,
RSA appears better from my point of view, though certainly
not quite as much as I initially thought.

--Jari

---

From: [email-masked] (Andrew McGregor)
Date: Tue Oct 19 15:17:01 2004

If I recall correctly, Miika has done the same math as Bob did when he was 
designing this.  In other words, that DSA is lighter on the responder is 
the reason for DSA being the default at present.  Bob's opinion was, I seem 
to recall, that the difference wasn't large but did slightly favour DSA.

Andrew

---

From: [email-masked] (Miika Komu)
Date: Thu Oct 21 01:48:01 2004

> not quite as much as I initially thought.

Using RSA as the default algorithm makes dynamically created R1s less
appealing from a performance point of view. In a way, this limits the way
implementations will be done in the real world.

I have understood that most of the current (research prototype)
implementations create R1s on-the-fly rather than off-the-shelf. The
reason for this is that the precreated R1s are tricky due to numerous
variables involved. Introducing the rendezvous server does not help
either; it introduces new permutations, and increases the complexity
of precreated R1s. But may be this a problem that needs to be solved
separately from the DSA/RSA matter.

Other than that, I am fine with the change to RSA. I just want us to do it
with an understandment of the little trade-offs involved.

---

From: [email-masked] (Jari Arkko)
Date: Thu Oct 21 01:59:01 2004

Miika Komu wrote:

> variables involved. 

Just for my education, can you elaborate a bit more about
these problems?

--Jari

---

From: [email-masked] (Miika Komu)
Date: Thu Oct 21 02:28:00 2004

> Just for my education, can you elaborate a bit more about

http://honor.trusecure.com/pipermail/hipsec/2004-June/000789.html

(especially the third message in the thread)

---

From: [email-masked] (Julien Laganier)
Date: Fri Oct 22 10:02:52 2004

> existing, and new protocol/applications.

BTW, I=A0just thought about having as mandatory encryption algorithm=20
"AES-CBC with HMAC-SHA1" instead of
"3DES-CBC with HMAC-SHA1". Do you guys think it's worth?

=2D-julien

> To: "'Steven M. Bellovin'" <[email-masked]>, "Hughes, James
> P" <[email-masked]>
> The reason that I distinguish between Depricated and obsolete is
> that there are uses of RSA signatures with MD5 hash that are still
>  plaintext and ciphertext corresponding to a key to encode or
> decode all messages with that key that are shorter or the same
> size. In effect all stream ciphers are vulnerable to a trivial form
> of known plaintext attack, the attack does not reveal the key but
> this is not necessary.
>
> I do not feel confident in recommending moving to SHA2 at this
> point. Before jumping I want to see that the place we are going to
> is better than where we left. SHA2 is not currently widely used. If
> it turns out that the recent cryptanalysis of SHA1 is also
> applicable to the structures used in SHA2 then the rationale for a
> change is lost. I would feel happier moving to a hash function
> based on AES encryption (which i had eroneously assumed had been
> the point of the SHA2 work).

=2D-=20
Julien Laganier=20
SUN Microsystems Laboratories

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." -- Brian W.  Kernighan

*NOTICE*: This email message is for the sole use of the intended
recipient(s) and may contain confidential and privileged information.
Any unauthorized review, use, disclosure or distribution is
prohibited. If you are not the intended recipient, please contact the
sender by reply email and destroy all copies of the original message.

---

From: [email-masked] (Jari Arkko)
Date: Fri Oct 22 10:57:01 2004

Julien Laganier wrote:

> BTW, I just thought about having as mandatory encryption algorithm 

Yes.

--Jari

---

From: [email-masked] (Pekka Nikander)
Date: Fri Oct 22 11:11:00 2004

> BTW, I=A0just thought about having as mandatory encryption algorithm

Ok to me.

--Pekka