Subject: [Hipsec] SHA1 broken?

From: [email-masked] (Pekka Nikander)
Date: Tue Mar 8 15:38:01 2005

> The HIT needs two properties:
>
> 1) probably unique
> 2) a identifier for the HI
>
> SHA1 will still supply property 1).
>
> As for property 2), I thought HIP was using a non-keyed SHA1 hash for
> HI=>HIT computation?  Basically, HIP is using SHA1's "randomness" 
> property
> to meet property 1), yes?  In this case, there is nothing to break and
> property 2) holds as well.  As for using keyed SHA1 for say, signing a
> packet or whatnot, then yes, looks like SHA256 will have to be used 
> soon.

Well, there is more in this.  The HIT essentially works as a
channel binding, giving assurance to the application that when
it does connect(HIT) it actually gets a (secured) connection to
the identified host.  From that point of view, if SHA-1 has a
weakness so that it becomes feasible to generate another (perhaps
very short) public key that hashes to the same HIT, we do have a
problem.  My crypto understanding is too weak to be able to say
for sure, but my understanding is that it has became easier to
do that.

I'm putting this up on the base spec slides for tomorrow.  My
personal opinion is to move to HMAC and SHA-256.  I don't know
if we want to change the HIT length in the HIP header at the
same time or not.  Maybe, just for the sake.  We could then use
the uppermost 128 bits of the HIT at the API, with the current
01/10 restriction.  The LSI would then probably use 24 top most
bits from the HIT instead of the 24 low bits, as now, but we are
moving LSIs away from the base spec probably anyway.

--Pekka

---

From: [email-masked] (Yogesh Prem Swami)
Date: Tue Mar 8 16:08:01 2005

[Getting back on this mailing list after a long time :-) ]

As far as SHA1 is concerned, I guess HITs (and HIP KE) are still quite
secure. The reason is that HITs are generated from the public keys, so
an attacker can potentially generate a string that will result in the
same HITs, however for the attacker to be able to make use of this
string she must must also be able to generate the private keys
corresponding to that string. This is non trivial under standard crypto
assumptions. For example, let say, I have [Priv, Pub] as my private and
public keys, and an attacker generate Pub2 string such SHA1(Pub) ==
SHA1(Pub2). For the attacker to be able to use Pub2 during key exchange,
she must sign her messages with the private key corresponding to Pub2.
This is clearly not possible.

Hash Collisions get so much attention because it makes certificates
untrustworthy. HIP, on the other hand is quite secure in spite of the
collisions.

Thanks
Yogesh  

On Tue, 2005-03-08 at 14:37, ext Pekka Nikander wrote:
> _______________________________________________
> Hipsec mailing list
> [email-masked]
> http://honor.trusecure.com/mailman/listinfo/hipsec

---

From: [email-masked] (Pekka Nikander)
Date: Tue Mar 8 17:01:03 2005

> corresponding to that string.

Well, a potential problem is that HIP allows you to use very short keys 
as your public identifier.  Hence, presumably, an attacker could just 
keep developing new short public key pairs until it finds one that 
matches with the colliding string.
Alternatively, if the attacker can generate a large number of colliding 
strings, the effort of generating a matching key pair may be reduced 
from what it was assumed to be.  So, to me it looks like that attacking 
HIP may indeed have become slightly easier than before.

Apparently replacing the currently used simple hash with a HMAC is 
sufficient to plug the potential leak.  Hence, if people are unwilling 
to move to SHA-256 or 256-bit HITs at this time, I don't see any need.

--Pekka

---

From: [email-masked] (Tim Shepard)
Date: Tue Mar 8 17:28:02 2005

If I understand correctly the newly reported weaknesses in various
hash functions, we have not yet seen a demonstration of a weakness
that would allow an attacker to create a key pair that hashes to a HIT
that you are using.

MD5 weaknesses
--------------

Collisions in md5 have been demonstrated, and more such pairs of md5
inputs that produce collisions can be easily generated.

Furthermore, it has been shown is that you could generate a pair of
RSA key pairs where the two public keys (of differing lengths if you
like) both hash to the same md5 value.

This can also be done (such a pair of key pairs can be found) if there
is known (constant) prefix that will be prepended to the two keys
before they are hashed.  A constant suffix can also be appended to
both, for once the hash function colides, it continues to colide as
you append a constant suffix.

The weaknesses in md5 that allow these attacks do not apply to SHA-1
(as far as I know as of today).

SHA-1 weakness
--------------

Brute-forcing SHA-1 was believed to have a 2^80 work factor, but now
appears to have a 2^69 work factor.  As was recently mentioned on an
IETF mailing list, this is a situation where we can "walk" to a
solution.  (No panic and running around is needed at this time.)
While this is considered a significant new development, the practical
security of systems using SHA-1 are not immediately compromised.
However the long-term suitability of SHA-1 is now in doubt.
(And such doubt, by itself, is enough reason to deprecate the use of
cryptographic algorithms.)

Implications for HIP
--------------------

For HIP I think we need to be able to handle longer HITs, and I think
we need a way of encoding in the HIT itself (in an unambiguous way)
what hash function it is that is supposed to demonstrate the binding
of the HIT to a public key.  (Otherwise, a weakness in one hash
function might allow you to create a public key which can be
"demonstrated" to be bound to a HIT that was created with a different
hash function.)

			-Tim Shepard
			 [email-masked]

---

From: [email-masked] (Julien Laganier)
Date: Tue Mar 8 17:54:00 2005

On Tuesday 08 March 2005 23:27, Tim Shepard wrote:

<snip>

> Implications for HIP
> --------------------
>
> For HIP I think we need to be able to handle longer HITs, and I
> think we need a way of encoding in the HIT itself (in an
> unambiguous way) what hash function it is that is supposed to
> demonstrate the binding of the HIT to a public key.  (Otherwise, a
> weakness in one hash function might allow you to create a public
> key which can be "demonstrated" to be bound to a HIT that was
> created with a different hash function.)

I concur with this. BTW if you looks at the HIPHI DNS RR format, it 
already encodes both the HIT algorithm and size.

Also, I am wondering to what extent we might also want to include in 
the HI itself the algorithm used to verify it (e.g. RSA), like Tim's 
proposal for HITs, instead of just signalling this algorithm in the 
HOST_ID TLV.

Or perhaps just say that the HI is the whole HOST_ID TLV...

What does the WG think?

--julien

---

From: [email-masked] (Greg Perkins)
Date: Mon Mar 14 11:52:00 2005

If you add a check that the RSA public key (the HI) must be of at least a
certain length then this attack stays very difficult because key generation
is a O(n^4) operation.  I have yet to get the details on this new SHA1
attack but can elaborate on this further when I do.

I do agree that the encoding should include a few semantic bits, like Pekka
discussed at the meeting.  I'd like these to include not only the hash
algorithm and bit length, but also the ability to define alternative
identifiers.  For instance, if we goto a 256 identifier I can reasonably
argue that using ECC would be a pretty good idea since the public keys are
currently 160 bits and thus no need to have a 'middle-man' HIT identifier
(ECC usage has IPR implications, which is typically why it is shunned, as
discussed earlier.  Just using it as an example and maybe if we asked
Certicom nicely they'd let HIP use their ECC method for free.  I can think
of a few business reasons why they might do that).

  Another alternative is to use symmetric cyphers (AES, ect.).  Basically,
one can use a random value as a 'hip session identifier' and then encrypt it
using the current session key.  This new step would be part of the protocol
but has pretty drastic implications for LSI use.  This is probably the only
way to minimize the bits used by an identifier while maintaining strong
security (hmmm, since both values, the random identifier and a session key
are unknown to an attacker, one should be able to just use a XOR mask, thus
96 bits get you 2^96 security - but there is no persistence across sessions,
like an HIT has).  I imagine this idea was discussed before and that hashed
HIs to generate HITs was decided to be better (always seemed better to me,
but if you really want to minimize packet headers, seems we would need to
use something like this).  I have to think on this.  Maybe it would be
better to leave the IP source addr to it's typically usage and add a 64 or
96 bit session identifier field to HIP headers that is masked by a random
session key?

Greg

----- Original Message ----- 
From: "Julien Laganier" <[email-masked]>
To: <[email-masked]>
Cc: "Tim Shepard" <[email-masked]>; "Pekka Nikander"
<[email-masked]>; "Yogesh Prem Swami"
<[email-masked]>; "Greg Perkins" <[email-masked]>
Sent: Tuesday, March 08, 2005 5:56 PM
Subject: Re: [Hipsec] SHA1 broken?

---

From: [email-masked] (Pekka Nikander)
Date: Fri Mar 18 05:23:01 2005

Greg,

> is a O(n^4) operation.

It is desirable to allow short host identity public keys for various
reasons.  Hence, IMHO we can't rely (much) on the fact that public
key generation is a hard operation.  Additionally, it may well happen
that some HITs in the future would be hashes of something else but
just a public key; e.g., consider HITs that are hashes over self signed
certificates.

> identifiers.

Well, I disagree.  IMHO we should keep the HITs themselves as 
semantic-free
as possible.  The hash algorithm we have to encode there, but IMHO we 
should
not encode the type.

We've gone through this type-encoding discussion before (I'm off-line so
I can't check the archive), and then the conclusion was to move from
type-tagged identifiers into pure hashes.  I don't remember the details
of that discussion any more, though.  What I remember is the following:

  - Any information in the HIT is a potential privacy issue.  The HITs,
    even temporary ones, will often be visible to external parties.
    They should be able to learn as little as possible from the HIT 
alone.

  - Many people at the November 2004 Washington DC workshop argued that
    the HITs should have even less semantic information; i.e., it should
    be possible to have HITs that are not considered to be hashes of
    public keys.  Unfortunately, that collides with the implicit channel
    bindings property of HITs.

Other than that, I think that your ideas about ECC and symmetric
keys are interesting and warrant more study.  However, while doing
so, it is good to keep in mind the current design constrains and
competing requirements.

--Pekka

---

From: [email-masked] (Miika Komu)
Date: Wed Mar 30 03:44:01 2005

FYI,

        Title           : Attacks on Cryptographic Hashes in Internet
                          Protocols
        Author(s)       : P. Hoffman, B. Schneier
        Filename        : draft-hoffman-hash-attacks-00.txt
        Pages           : 11
        Date            : 2005-3-28

   Recent announcements of better-than-expected collision attacks in
   popular hash algorithms have caused some people to question whether
   common Internet protocols need to be changed, and if so, how.  This
   document summarizes the use of hashes in many IETF protocols,
   discusses how the collision attacks affect and do not affect the
   protocols, shows how to thwart known attacks on digital certificates,
   and discusses future directions for protocol designers.

A URL for this Internet-Draft is:

http://www.ietf.org/internet-drafts/draft-hoffman-hash-attacks-00.txt

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