Subject: Re: [saag] security consideration of CGA and SSAS - I-D action : draft-rafiee-6man-ssas

From: "Hosnieh Rafiee" <[email-masked]>
Date: Fri, 22 Mar 2013 00:08:02 +0100

Jari,

> What changes from RFC 3972 to your draft in this high-level analysis?

The difference between my draft and that of RFC 3972 is that I make use of
the public key in the IP address directly. Doing it the way I have explained
in my draft eliminates the need for the use of those SHAx steps  because I
believe the use of those steps does not lend itself to improved security. My
reason for this opinion is that RFC 3972 can only prevent DAD attacks and
not the other types of attacks. This attack can also be prevented by using
CGA if we add this extra verification step (that of the node checking the
public key of the sender to his own), otherwise RPKI would be used. This is
the same procedure as outlined in my draft. So the security of both depends
on the security of the public/ private keys. After a successful verification
(which could have resulted from a fast relay attack) the attacker's
link-layer address is included in a cache as a legitimate address, and if
routing is based on the link-layer address,  then the node has no way of
knowing that it was just a replay attack. Otherwise, the use of RPKI, where
the node that has this IP address/or link layer is specified, would contain
this public key. This is why, in this case, the keys' security is very
important.

Thanks,
Hosnieh

-----Original Message-----
From: Jari Arkko [mailto:[email-masked]] 
Sent: Thursday, March 21, 2013 10:56 PM
To: Hosnieh Rafiee
Cc: 'Jari Arkko'; 'Santosh Chokhani'; [email-masked]; [email-masked]; 'Ray
Hunter'; 'Christian Huitema'; Erik Nordmark; [email-masked];
'Jeffrey Hutzelman'
Subject: Re: [saag] security consideration of CGA and SSAS - Ii-D action :
draft-rafiee-6man-ssas

Hosnieh,

> What is it that you don't understand. I will be happy to explain it to
you.

Thanks. I read the details, but I'm missing the big picture. I.e., some
effort is required from the owner to create an address. By repeating that
effort (2^59)/2 times, someone else is likely to hit the same key with a key
pair that he or she controls, and an attack can be launched. What changes
from RFC 3972 to your draft in this high-level analysis?

> There has been no resolution to the topic of the thread. 

Ok. Well that clarifies at least the state of the discussion. Thanks.

Jari

---

From: Christian Huitema <[email-masked]>
Date: Thu, 21 Mar 2013 23:56:20 +0000

Hosnieh,

You should probably split your proposal in two parts: the proposal to replace CGA by just checking an extract of the address; and potential improvements to SEND that are independent of whether we use CGA or your direct comparison alternative. 

Your replacement of CGA works by copying some bits of the public key in the IID field, instead of using bits from a hash function. I think this is a really bad idea, since the number of bits that you can copy is limited. Your initial design copied just 48 bits; you could change that to 56 bits or maybe 62 bits in an improved design. Cracking the 48 bit version is trivial. Cracking the 62 bit version will take longer, but with Moore's law there will come a point in the future where this too will be easy to crack. In contrast, CGA implementations can simply in the future increment the SEC value for added robustness.

Your draft is making other contributions, such as added verification steps, or caching o results to prevent DOS attacks. These contributions could be used to improve SEND. It would be better to separate them from the debate about hash functions.

-- Christian

-----Original Message-----
From: Hosnieh Rafiee [mailto:[email-masked]] 
Sent: Thursday, March 21, 2013 4:08 PM
To: 'Jari Arkko'
Cc: 'Santosh Chokhani'; [email-masked]; [email-masked]; 'Ray Hunter'; Christian Huitema; 'Erik Nordmark'; [email-masked]; 'Jeffrey Hutzelman'
Subject: RE: [saag] security consideration of CGA and SSAS - I-D action : draft-rafiee-6man-ssas

Jari,

> What changes from RFC 3972 to your draft in this high-level analysis?

The difference between my draft and that of RFC 3972 is that I make use of the public key in the IP address directly. Doing it the way I have explained in my draft eliminates the need for the use of those SHAx steps  because I believe the use of those steps does not lend itself to improved security. My reason for this opinion is that RFC 3972 can only prevent DAD attacks and not the other types of attacks. This attack can also be prevented by using CGA if we add this extra verification step (that of the node checking the public key of the sender to his own), otherwise RPKI would be used. This is the same procedure as outlined in my draft. So the security of both depends on the security of the public/ private keys. After a successful verification (which could have resulted from a fast relay attack) the attacker's link-layer address is included in a cache as a legitimate address, and if routing is based on the link-layer address,  then the node has no way of knowing that it was just a replay attack. Otherwise, the use of RPKI, where the node that has this IP address/or link layer is specified, would contain this public key. This is why, in this case, the keys' security is very important.

Thanks,
Hosnieh

-----Original Message-----
From: Jari Arkko [mailto:[email-masked]]
Sent: Thursday, March 21, 2013 10:56 PM
To: Hosnieh Rafiee
Cc: 'Jari Arkko'; 'Santosh Chokhani'; [email-masked]; [email-masked]; 'Ray Hunter'; 'Christian Huitema'; Erik Nordmark; [email-masked]; 'Jeffrey Hutzelman'
Subject: Re: [saag] security consideration of CGA and SSAS - Ii-D action :
draft-rafiee-6man-ssas

Hosnieh,

you.

Jari

---

From: Francis Dupont <[email-masked]>
Date: Fri, 22 Mar 2013 10:26:54 +0100

In your previous mail you wrote:

>  the public key in the IP address directly.

=> this is IMHO a bad idea because it limits the search space in the
best case (i.e., not when the structure of the public key allows
trivial attacks as in the RSA case) to 2**64.

>   Doing it the way I have explained
>  believe the use of those steps does not lend itself to improved security.

=> I strongly disagree: the use of those SHAx steps is the way to extend
the search space and until SHAx pre-images are broken for the worst case
(i.e., no attack better than brute force).

>   My

=> this seems to be replay attacks. RFC 3972 (CGAs) doesn't protect against
replay but provides message (aka connectionless) integrity so any use
of CGAs can add an anti-replay device (RFC 3971 (SEND) uses nonces and
timestamps for anti-replay). BTW CGAs and SSASs are the same for this
point.

Regards

[email-masked]

PS: I don't say to put the public key in the address is intrinsically
broken but it cannot be done this way. I suggest to look at Identity
Based Cryptography (the SAAG could provide guidance).

---

From: "Hosnieh Rafiee" <[email-masked]>
Date: Fri, 22 Mar 2013 13:45:44 +0100

Francis, 

=> I strongly disagree: the use of those SHAx steps is the way to extend the
search space and until SHAx pre-images are broken for the worst case (i.e.,
no attack better than brute force).

Be patient please. It takes time to prepare a response because I will need
to work on code to break RSA and also SHAx (CGA) and currently I have no
opportunity to work on this.

=> this seems to be replay attacks. RFC 3972 (CGAs) doesn't protect against
replay but provides message (aka connectionless) integrity so any use of
CGAs can add an anti-replay device (RFC 3971 (SEND) uses nonces and
timestamps for anti-replay). BTW CGAs and SSASs are the same for this point.

Nonce and timestamp both cannot be much helpful for relay attacks. I
mentioned a fast replay attack. You need to consider the clock skew for
timestamp (two seconds or so). The other nodes do not know the nonce is for
an attacker or for your node. I, as an attacker, can easily copy and paste
the whole packet content in my message with my own link layer address and
send it back to you. There is difference between SSAS and CGA in DAD
process.  There is no doubt that CGA verification needs improvements, I
probably try to write another draft and improve that document too while at
the same time as I am improving SSAS with the best design of RPKI (I will do
that after my trip :-)  so give me more time...).

Thanks,
Hosnieh

---

From: Francis Dupont <[email-masked]>
Date: Sat, 23 Mar 2013 12:44:22 +0100

>  opportunity to work on this.

=> I'll be very patient about the code to break CGAs (:-).

>  an attacker or for your node.

=> the nonce doesn't prove the origin but the signature does.

>  I, as an attacker, can easily copy and paste the whole packet
>  content in my message with my own link layer address and send it
>  back to you.

=> I have no problem with this way to improve the service. BTW
the link-layer address ND option (vs the one in the Ethernet
header) is protected by the signature so you can't change it.
And I still can't see a difference between SSAS and CGA about
this point: in both cases signatures covered the same fields.

Regards

---

From: "Sujing Zhou"<[email-masked]>
Date: Mon, 25 Mar 2013 12:06:00 +0800

Christian Huitema <[email-masked]> 写于 2013-03-22 07:56:20:

> 
> Hosnieh,
> 
> You should probably split your proposal in two parts: the proposal 
> to replace CGA by just checking an extract of the address; and 
> potential improvements to SEND that are independent of whether we 
> use CGA or your direct comparison alternative. 
> 
> Your replacement of CGA works by copying some bits of the public key
> in the IID field, instead of using bits from a hash function. I 
> think this is a really bad idea, since the number of bits that you 
> can copy is limited. Your initial design copied just 48 bits; you 
> could change that to 56 bits or maybe 62 bits in an improved design.
> Cracking the 48 bit version is trivial. Cracking the 62 bit version 
> will take longer, but with Moore's law there will come a point in 
> the future where this too will be easy to crack. In contrast, CGA 
> implementations can simply in the future increment the SEC value for
> added robustness.
What is the pointing of adding sec since the ratio of effor required by 
attacker and user is always 2^59, as Jari argued.

> 
> Your draft is making other contributions, such as added verification
> steps, or caching o results to prevent DOS attacks. These 
> contributions could be used to improve SEND. It would be better to 
> separate them from the debate about hash functions.
> 
> -- Christian
> 
> 
> 
> 
> Cc: 'Santosh Chokhani'; [email-masked]; [email-masked]; 'Ray Hunter'; 
> Christian Huitema; 'Erik Nordmark'; [email-masked]; 
'JeffreyHutzelman'
> The difference between my draft and that of RFC 3972 is that I make 
> use of the public key in the IP address directly. Doing it the way I
> have explained in my draft eliminates the need for the use of those 
> SHAx steps  because I believe the use of those steps does not lend 
> itself to improved security. My reason for this opinion is that RFC 
> 3972 can only prevent DAD attacks and not the other types of 
> attacks. This attack can also be prevented by using CGA if we add 
> this extra verification step (that of the node checking the public 
> key of the sender to his own), otherwise RPKI would be used. This is
> the same procedure as outlined in my draft. So the security of both 
> depends on the security of the public/ private keys. After a 
> successful verification (which could have resulted from a fast relay
> attack) the attacker's link-layer address is included in a cache as 
> a legitimate address, and if routing is based on the link-layer 
> address,  then the node has no way of knowing that it was just a 
> replay attack. Otherwise, the use of RPKI, where the node that has 
> this IP address/or link layer is specified, would contain this 
> public key. This is why, in this case, the keys' security is very 
important.
> Cc: 'Jari Arkko'; 'Santosh Chokhani'; [email-masked]; [email-masked]; 
> 'Ray Hunter'; 'Christian Huitema'; Erik Nordmark; zhou.sujing@zte.
> com.cn; 'Jeffrey Hutzelman'

---

From: Christian Huitema <[email-masked]>
Date: Mon, 25 Mar 2013 04:33:40 +0000

> What is the pointing of adding sec since the ratio of effor required by  attacker and user is always 2^59, as Jari argued. 

2^59 is a rather large number. Everything else being equal, another 1 second of computation at the user translates into another 18 billion years at the attacker.

-- Christian Huitema

---

From: "Sujing Zhou"<[email-masked]>
Date: Mon, 25 Mar 2013 13:54:27 +0800

Christian Huitema <[email-masked]> 写于 2013-03-25 12:33:40:

> > What is the pointing of adding sec since the ratio of effor 
> required by  attacker and user is always 2^59, as Jari argued. 
> 
> 2^59 is a rather large number. Everything else being equal, another 
> 1 second of computation at the user translates into another 18 
> billion years at the attacker.
Agree. How about 2^56?
My question is since CGA has 2^59 as a security guarantee, why bother 
increase sec?

---

From: Ray Hunter <[email-masked]>
Date: Mon, 25 Mar 2013 07:35:04 +0100

> Sujing Zhou <mailto:[email-masked]>
> 25 March 2013 06:54
>
Because as processors get faster, the relative amount of work remains
constant at 2^59, but the absolute amount of processing time per
operation decreases for both attacker and defender. So the absolute
amount of time required to mount a successful attack also decreases over
the long term.

At some point, the absolute amount of time required to mount an attack
will eventually be comparable to the amount of time an address is in
use, which makes attacks attractive.

Eventually you either have to reduce the time the CGA address remains in
use, or make the algorithm more complex for both attacker and defender
[add sec]. c.f. DES -> triple DES.
> >
> > -- Christian Huitema
> >
> >
> >
> Christian Huitema <mailto:[email-masked]>
> 25 March 2013 05:33
>
> 2^59 is a rather large number. Everything else being equal, another 1
> second of computation at the user translates into another 18 billion
> years at the attacker.
>
> -- Christian Huitema
>
>
>
> ------------------------------------------------------------------------

---

From: Christian Huitema <[email-masked]>
Date: Mon, 25 Mar 2013 15:54:18 +0000

> My question is since CGA has 2^59 as a security guarantee, why bother increase sec?

Because the evaluation of the hash itself is a very small number, and get smaller and smaller as Moore's law progresses.

Under the same proportionality rule, if the user spends 1 microsecond verifying the hash, the attacker will need to spend 18,000 years. That seems a lot, until you realize that if a botnet has access to 1 million computers, we are down to less than 7 days. And if these computers in turns have GPU with 1000 cores each, we are down to 16 minutes.

The SEC process ensures that the user spends enough time to make the attack impractical.

From: Sujing Zhou [mailto:[email-masked]] 
Sent: Sunday, March 24, 2013 10:54 PM
To: Christian Huitema
Cc: [email-masked]; 'Jeffrey Hutzelman'; 'Erik Nordmark'; [email-masked]; 'Santosh Chokhani'; 'Ray Hunter'
Subject: Re: RE: RE: [saag] security consideration of CGA and SSAS - I-D action : draft-rafiee-6man-ssas

> billion years at the attacker.
Agree. How about 2^56? 
My question is since CGA has 2^59 as a security guarantee, why bother increase sec?

---

From: Bob Hinden <[email-masked]>
Date: Mon, 25 Mar 2013 17:02:30 +0100

> amount of time required to mount a successful attack also decreases over

For example, Graphic Processing Units (GPU) are being used to crack passwords.  They have thousands of cores that can be applied to this kind of problem.   Lots of material about this on the web.

Bob

---

From: Steven Bellovin <[email-masked]>
Date: Tue, 26 Mar 2013 14:04:36 -0400

> For example, Graphic Processing Units (GPU) are being used to crack passwords.  They have thousands of cores that can be applied to this kind of problem.   Lots of material about this on the web.
See, for example, http://arstechnica.com/security/2012/12/25-gpu-cluster-cracks-every-standard-windows-password-in-6-hours/

		--Steve Bellovin, https://www.cs.columbia.edu/~smb