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

[Ray Hunter <[e-mail]>]

agreed.

FWIW I suggested to Hosnieh earlier (in a private mail) to support
multiple alternative authentication mechanisms, and to make this
flexible for the future.

This draft is effectively discussing tuning an authentication protocol
to reduce the amount of work done by the defender (to make it faster
than CGA) whilst keeping the amount of work the attacker has to do high
enough to avoid common attacks.

We can argue all we like about the current balance of power as of today,
but that's not the main issue.

IMHO Over the course of years that this type of protocol is in
operation, the work has to increase for both defender and attacker (due
to Moore's law) to keep the "amount of effort to break" constant. CGA
allows this. The current draft does not.
> Jari Arkko <mailto:[e-mail]>
> 22 March 2013 07:38
> Christian,
>
>
> Right. I was speaking about the relative effort increase. For Sec = 0,
> I have to do 1 unit of work, the attacker 2^59 units of work. For Sec
> = 1, I have to do 2^16 units of work, the attacker 2^16 * 2^59 units
> of work. The difference in the amount of time I and the attacker have
> to do is always 2^59, but with Sec we can change how much work that is.
>
> Jari
>
> Christian Huitema <mailto:[e-mail]>
> 22 March 2013 00:46
> SEC does not " increases costs equally for both attackers and
> defenders." An increase of time T for the defender correspond to an
> increase of time T*2^59 for the attacker.
>
> -----Original Message-----
> From: Jari Arkko [mailto:[e-mail]]
> Sent: Thursday, March 21, 2013 1:19 PM
> To: Christian Huitema; Hosnieh Rafiee
> Cc: Santosh Chokhani; [e-mail]; [e-mail]; Ray Hunter
> Subject: Re: [saag] security consideration of CGA and SSAS - Ii-D
> action : draft-rafiee-6man-ssas
>
> Is there a conclusion of this thread? My read of it is that no amount
> of tweaking how you calculate the IID help the fact that in 59/62 bits
> you have a limited space to search. The Sec scheme does help, but
> increases costs equally for both attackers and defenders.
>
> FWIW, I'm struggling to understand the draft. But I couldn't make it
> to the meeting.
>
> Jari
>
> Jari Arkko <mailto:[e-mail]>
> 21 March 2013 21:19
> Is there a conclusion of this thread? My read of it is that no amount
> of tweaking how you calculate the IID help the fact that in 59/62 bits
> you have a limited space to search. The Sec scheme does help, but
> increases costs equally for both attackers and defenders.
>
> FWIW, I'm struggling to understand the draft. But I couldn't make it
> to the meeting.
>
> Jari
>
> Christian Huitema <mailto:[e-mail]>
> 18 March 2013 03:03
>
> Santosh, I suppose we have to use more than 2048 bits for RSA then…
> But that’s not really the point of the debate.
>
> CGA is an algorithm specified for IPv6 “secure neighbor discovery” and
> is specified in RFC 3972. CGA works by associating an IPv6 address
> with a public key. The public key is hashed with the network prefix
> (first 64 bits of IPv6 address) and 59 bits of the hash are copied to
> the host identifier part of the IPv6 address. In the most basic
> implementation, senders prove ownership of the address by
> demonstrating possession of a public/private key pair, and receiver
> verify also that the specified 59 bits of the hash match what is in
> the address.
>
> Of course, 59 bits is a rather small number, and matching only 59 bits
> instead of 160 seriously weakens the strength of the algorithm. The
> CGA spec includes a “hash augmentation” mechanism, the “SEC” fields,
> which specifies an additional constraint on the content of the hash,
> namely that the hash begins by a set number of zeroes – 16 times the
> number in the SEC field. That mechanism requires that the host
> generating a secure address spends some time finding the right hash.
>
> Hosnieh proposes to replace that mechanism by simply copying in the
> IPv6 address a number of bits from the public key – 48 in the original
> proposal.
>
> *From:* Santosh Chokhani [mailto:[e-mail]]
> *Sent:* Sunday, March 17, 2013 6:36 PM
> *To:* Christian Huitema; Hosnieh Rafiee; [e-mail]; [e-mail]
> *Cc:* [e-mail]; 'Roque Gagliano (rogaglia)'; 'Erik
> Nordmark'; 'Ray Hunter'; [e-mail]
> *Subject:* RE: [saag] security consideration of CGA and SSAS - Ii-D
> action : draft-rafiee-6man-ssas
>
> 2048 bit RSA security is overstated. Cracking it requires on the order
> of 2^112 operations. You should look at NIST SP 800-57 Part 2, Table 2
> Section 5.6.1.
>
> From the description you provide on hashing, finding a second hash is
> a second pre-image attack and for SHA-1 the security strength is 160
> bits, i.e., you need on the order of 2^160 operations.
>
> I do not know what hash function you are describing for the function
> you mention and how you derived its security strength.
>
> *From:*[e-mail] <mailto:[e-mail]>
> [mailto:[e-mail]] *On Behalf Of *Christian Huitema
> *Sent:* Sunday, March 17, 2013 4:14 AM
> *To:* Hosnieh Rafiee; [e-mail] <mailto:[e-mail]>;
> [e-mail] <mailto:[e-mail]>
> *Cc:* [e-mail]
> <mailto:[e-mail]>; 'Roque Gagliano (rogaglia)';
> 'Erik Nordmark'; 'Ray Hunter'; [e-mail]
> <mailto:[e-mail]>
> *Subject:* Re: [saag] security consideration of CGA and SSAS - Ii-D
> action : draft-rafiee-6man-ssas
>
> The attack is **relatively** easier. It is not “easy.” It is much
> harder to crack RSA than to find a matching hash. Cracking a 2048 bits
> RSA key probably requires on the order of 2^1024 trials, and that will
> take you something like “forever.” Cracking the hash requires only
> something on the order of 2^91 trials with SEC=2. That’s obviously
> much less, but that’s still a very large number. The exhausting search
> will take you many years, i.e. much more than the valid lifetime of
> the address.
>
> *From:* Hosnieh Rafiee [mailto:[e-mail]]
> *Sent:* Saturday, March 16, 2013 1:45 PM
> *To:* Christian Huitema; [e-mail] <mailto:[e-mail]>;
> [e-mail] <mailto:[e-mail]>
> *Cc:* 'Erik Nordmark'; [e-mail]
> <mailto:[e-mail]>; 'Ray Hunter'; 'Michael
> Richardson'; [e-mail]
> <mailto:[e-mail]>; 'Roque Gagliano (rogaglia)'
> *Subject:* RE: security consideration of CGA and SSAS - Ii-D action :
> draft-rafiee-6man-ssas
>
> >The “SEC” part of CGA is meant to protect against a different attack,
> one in which the attacker has not cracked the private key. Instead,
> the attacker uses a public/private key pair of his own >choosing, and
> arrange for the hash of that key to match the CGA address of the
> target. This “only” requires O(2**(59+SEC*16)) operations, which even
> with large values of SEC is still far less than >what is required to
> crack RSA or ECC.
>
> So according to what I understand from what you wrote, the sec value
> makes the for an easier attack against CGA as the attacker only needs
> to find the same value generated by his own modifier and other
> parameters and matches this to the IID of the node. Now the question
> again is, if this gives an attacker a leg up in doing his brute force
> attacks why do we need to add those steps to CGA. This was why I used
> the direct public key as a part of IP address.
>
> Thanks again Christian.
>
> Hosnieh
>
> *From:*Christian Huitema [mailto:[e-mail]]
> *Sent:* Saturday, March 16, 2013 7:30 PM
> *To:* Hosnieh Rafiee; [e-mail] <mailto:[e-mail]>;
> [e-mail] <mailto:[e-mail]>
> *Cc:* 'Erik Nordmark'; [e-mail]
> <mailto:[e-mail]>; 'Ray Hunter'; Michael
> Richardson; [e-mail]
> <mailto:[e-mail]>; Roque Gagliano (rogaglia)
> *Subject:* RE: security consideration of CGA and SSAS - Ii-D action :
> draft-rafiee-6man-ssas
>
> As you say, the attack that you mention depends on the strength of RSA
> or ECC. In fact, pretty much all of public key cryptography depends on
> that strength. It is generally assumed that cracking a long enough RSA
> or ECC key is nearly impossible.
>
> The “SEC” part of CGA is meant to protect against a different attack,
> one in which the attacker has not cracked the private key. Instead,
> the attacker uses a public/private key pair of his own choosing, and
> arrange for the hash of that key to match the CGA address of the
> target. This “only” requires O(2**(59+SEC*16)) operations, which even
> with large values of SEC is still far less than what is required to
> crack RSA or ECC.
>
> *From:* Hosnieh Rafiee [mailto:[e-mail]]
> *Sent:* Saturday, March 16, 2013 10:59 AM
> *To:* Christian Huitema; [e-mail] <mailto:[e-mail]>;
> [e-mail] <mailto:[e-mail]>
> *Cc:* 'Erik Nordmark'; [e-mail]
> <mailto:[e-mail]>; 'Ray Hunter'; Michael
> Richardson; [e-mail]
> <mailto:[e-mail]>; Roque Gagliano (rogaglia)
> *Subject:* RE: security consideration of CGA and SSAS - Ii-D action :
> draft-rafiee-6man-ssas
>
> Hi Christian,
>
> > But can y toou explain why you believe that retrieving the private
> key from the public key and a clear text/encrypted text pair is easier
> than breaking a hash?
>
> Here we do not use any encryption and decryption and we just sign the
> message using private key and verify the message using public key.
>
> >Did you somehow crack RSA?
>
> I do not say that it is easier to find the private key from the public
> key. Because for both SSAS and CGA, public/private keys are used. I do
> say that the SHAx steps used for CGA generation do not increase the
> complexity when used against brute force attacks. This is because an
> attacker only needs the private key and does not need to find the
> modifier that was used in the generation of the node’s IID nor is
> there a need for checking the condition of sec by 16 bits which should
> be equal to zero. In SSAS I just use the public/private keys and the
> signature and nothing is encrypted/decrypted. In CGA some extra SHAx
> steps are used in the generation of their IID along with the
> signature. I say that these steps are not needed as long as you
> include and send all parameters, used in the SHAx process, in the
> packet for verification purposes. Some people feel that CGA is secure
> enough when those steps are used. Now what I want to point out here is
> that the CGA security level is *only* dependent on the algorithm used
> for key pair and signature generation and that those extra steps do
> nothing enhance the security side of things. The algorithms used can
> be RSA or ECC or whatever, and as such the situation will be the same
> as it is for SSAS. I just removed the complexity from the use of CGA
> in order to enable a more practical and faster generation and
> verification process.
>
> So the question isn’t how to break the encrypted text but how to break
> the signature. In other word, to find the same public key as used by
> the generator node or how to break the RSA or ECC. Based on my
> knowledge of hash algorithms, as I mentioned in my prior sentence,
> this will depend on the strength of the RSA or whatever other
> algorithm is used to generate these keys and sign the message. If you
> or anyone else thinks otherwise, please contribute to this discussion
> and share your opinions. I am just comparing the security aspects of
> SSAS, the time efficient algorithm, to those of CGA.
>
> Thank you,
>
> Hosnieh
>
> *From:*Christian Huitema [mailto:[e-mail]]
> *Sent:* Saturday, March 16, 2013 5:37 PM
> *To:* Hosnieh Rafiee; [e-mail] <mailto:[e-mail]>;
> [e-mail] <mailto:[e-mail]>
> *Cc:* Erik Nordmark; [e-mail]
> <mailto:[e-mail]>; Ray Hunter
> *Subject:* RE: security consideration of CGA and SSAS - Ii-D action :
> draft-rafiee-6man-ssas
>
> It is very clear that if the attacker finds the private key, the size
> of the hash does not matter. But can you explain why you believe that
> retrieving the private key from the public key and a clear
> text/encrypted text pair is easier than breaking a hash? Did you
> somehow crack RSA?
>
> *From:* [e-mail] <mailto:[e-mail]>
> [mailto:[e-mail]] *On Behalf Of *Hosnieh Rafiee
> *Sent:* Saturday, March 16, 2013 6:27 AM
> *To:* [e-mail] <mailto:[e-mail]>; [e-mail]
> <mailto:[e-mail]>
> *Cc:* Erik Nordmark; [e-mail]
> <mailto:[e-mail]>; Ray Hunter
> *Subject:* security consideration of CGA and SSAS - Ii-D action :
> draft-rafiee-6man-ssas
>
> Hello,
>
> There was a discussion during my presentation about security
> considerations regarding the use of my algorithm compared with those
> of the use of CGA. A big mistake that is made when considering CGA
> security is that the sec value plays an important role and that an
> attacker will need to do brute force attacks against the IID in order
> to generate the same IID as is generated by the use of CGA. In a CGA
> analysis paper they talk about a CGA security vaulue of pow (2, sec*16
> * 59) where 2 is the base and sec*16 * 59 is the exponential value and
> so they infer that by increasing the sec value used with CGA it will
> be safer, but this Is not true.
>
> I, as an attacker, just to need to find your private key. That’s it.
> This is because you have already included the CGA parameters (public
> key, modifier, and other required parameters) in the packet that was
> sent and I will have no problem in regenerating the CGA. My only
> problem will be in generating the signature that can be verified by
> use of your public key. This means that you just increased the
> complexity and time required for generating and verifying the IID
> while with SSAS you can obtain the same security as when using CGA
> because its security also depends on the Hash function that is used to
> generate the key pair and signature.
>
> If you send the CGA parameters via a safe channel, like in
> establishing TLS etc., then, in that case, CGA would be more secure
> than SSAS. But in practice all the data is sent in the same packet
> without encryption. If a secured channel would be used in the CGA
> process for security reasons (sending CGA parameters), then the cost
> of using CGA would be much greater than the cost of using SSAS.
>
> **
>
> *Now the question is, Why not use a more cost efficient algorithm that
> afford you with the same security level as when using CGA. *
>
> I have also included the security group in this email so that they can
> also give me any comments that they might have.
>
> Thank you,
>
> Hosnieh
>
> Santosh Chokhani <mailto:[e-mail]>
> 18 March 2013 02:36
>
> 2048 bit RSA security is overstated. Cracking it requires on the order
> of 2^112 operations. You should look at NIST SP 800-57 Part 2, Table 2
> Section 5.6.1.
>
> From the description you provide on hashing, finding a second hash is
> a second pre-image attack and for SHA-1 the security strength is 160
> bits, i.e., you need on the order of 2^160 operations.
>
> I do not know what hash function you are describing for the function
> you mention and how you derived its security strength.
>
> *From:*[e-mail] [mailto:[e-mail]] *On Behalf
> Of *Christian Huitema
> *Sent:* Sunday, March 17, 2013 4:14 AM
> *To:* Hosnieh Rafiee; [e-mail]; [e-mail]
> *Cc:* [e-mail]; 'Roque Gagliano (rogaglia)'; 'Erik
> Nordmark'; 'Ray Hunter'; [e-mail]
> *Subject:* Re: [saag] security consideration of CGA and SSAS - Ii-D
> action : draft-rafiee-6man-ssas
>
> The attack is **relatively** easier. It is not “easy.” It is much
> harder to crack RSA than to find a matching hash. Cracking a 2048 bits
> RSA key probably requires on the order of 2^1024 trials, and that will
> take you something like “forever.” Cracking the hash requires only
> something on the order of 2^91 trials with SEC=2. That’s obviously
> much less, but that’s still a very large number. The exhausting search
> will take you many years, i.e. much more than the valid lifetime of
> the address.
>
> *From:* Hosnieh Rafiee [mailto:[e-mail]]
> *Sent:* Saturday, March 16, 2013 1:45 PM
> *To:* Christian Huitema; [e-mail] <mailto:[e-mail]>;
> [e-mail] <mailto:[e-mail]>
> *Cc:* 'Erik Nordmark'; [e-mail]
> <mailto:[e-mail]>; 'Ray Hunter'; 'Michael
> Richardson'; [e-mail]
> <mailto:[e-mail]>; 'Roque Gagliano (rogaglia)'
> *Subject:* RE: security consideration of CGA and SSAS - Ii-D action :
> draft-rafiee-6man-ssas
>
> >The “SEC” part of CGA is meant to protect against a different attack,
> one in which the attacker has not cracked the private key. Instead,
> the attacker uses a public/private key pair of his own >choosing, and
> arrange for the hash of that key to match the CGA address of the
> target. This “only” requires O(2**(59+SEC*16)) operations, which even
> with large values of SEC is still far less than >what is required to
> crack RSA or ECC.
>
> So according to what I understand from what you wrote, the sec value
> makes the for an easier attack against CGA as the attacker only needs
> to find the same value generated by his own modifier and other
> parameters and matches this to the IID of the node. Now the question
> again is, if this gives an attacker a leg up in doing his brute force
> attacks why do we need to add those steps to CGA. This was why I used
> the direct public key as a part of IP address.
>
> Thanks again Christian.
>
> Hosnieh
>
> *From:*Christian Huitema [mailto:[e-mail]]
> *Sent:* Saturday, March 16, 2013 7:30 PM
> *To:* Hosnieh Rafiee; [e-mail] <mailto:[e-mail]>;
> [e-mail] <mailto:[e-mail]>
> *Cc:* 'Erik Nordmark'; [e-mail]
> <mailto:[e-mail]>; 'Ray Hunter'; Michael
> Richardson; [e-mail]
> <mailto:[e-mail]>; Roque Gagliano (rogaglia)
> *Subject:* RE: security consideration of CGA and SSAS - Ii-D action :
> draft-rafiee-6man-ssas
>
> As you say, the attack that you mention depends on the strength of RSA
> or ECC. In fact, pretty much all of public key cryptography depends on
> that strength. It is generally assumed that cracking a long enough RSA
> or ECC key is nearly impossible.
>
> The “SEC” part of CGA is meant to protect against a different attack,
> one in which the attacker has not cracked the private key. Instead,
> the attacker uses a public/private key pair of his own choosing, and
> arrange for the hash of that key to match the CGA address of the
> target. This “only” requires O(2**(59+SEC*16)) operations, which even
> with large values of SEC is still far less than what is required to
> crack RSA or ECC.
>
> *From:* Hosnieh Rafiee [mailto:[e-mail]]
> *Sent:* Saturday, March 16, 2013 10:59 AM
> *To:* Christian Huitema; [e-mail] <mailto:[e-mail]>;
> [e-mail] <mailto:[e-mail]>
> *Cc:* 'Erik Nordmark'; [e-mail]
> <mailto:[e-mail]>; 'Ray Hunter'; Michael
> Richardson; [e-mail]
> <mailto:[e-mail]>; Roque Gagliano (rogaglia)
> *Subject:* RE: security consideration of CGA and SSAS - Ii-D action :
> draft-rafiee-6man-ssas
>
> Hi Christian,
>
> > But can y toou explain why you believe that retrieving the private
> key from the public key and a clear text/encrypted text pair is easier
> than breaking a hash?
>
> Here we do not use any encryption and decryption and we just sign the
> message using private key and verify the message using public key.
>
> >Did you somehow crack RSA?
>
> I do not say that it is easier to find the private key from the public
> key. Because for both SSAS and CGA, public/private keys are used. I do
> say that the SHAx steps used for CGA generation do not increase the
> complexity when used against brute force attacks. This is because an
> attacker only needs the private key and does not need to find the
> modifier that was used in the generation of the node’s IID nor is
> there a need for checking the condition of sec by 16 bits which should
> be equal to zero. In SSAS I just use the public/private keys and the
> signature and nothing is encrypted/decrypted. In CGA some extra SHAx
> steps are used in the generation of their IID along with the
> signature. I say that these steps are not needed as long as you
> include and send all parameters, used in the SHAx process, in the
> packet for verification purposes. Some people feel that CGA is secure
> enough when those steps are used. Now what I want to point out here is
> that the CGA security level is *only* dependent on the algorithm used
> for key pair and signature generation and that those extra steps do
> nothing enhance the security side of things. The algorithms used can
> be RSA or ECC or whatever, and as such the situation will be the same
> as it is for SSAS. I just removed the complexity from the use of CGA
> in order to enable a more practical and faster generation and
> verification process.
>
> So the question isn’t how to break the encrypted text but how to break
> the signature. In other word, to find the same public key as used by
> the generator node or how to break the RSA or ECC. Based on my
> knowledge of hash algorithms, as I mentioned in my prior sentence,
> this will depend on the strength of the RSA or whatever other
> algorithm is used to generate these keys and sign the message. If you
> or anyone else thinks otherwise, please contribute to this discussion
> and share your opinions. I am just comparing the security aspects of
> SSAS, the time efficient algorithm, to those of CGA.
>
> Thank you,
>
> Hosnieh
>
> *From:*Christian Huitema [mailto:[e-mail]]
> *Sent:* Saturday, March 16, 2013 5:37 PM
> *To:* Hosnieh Rafiee; [e-mail] <mailto:[e-mail]>;
> [e-mail] <mailto:[e-mail]>
> *Cc:* Erik Nordmark; [e-mail]
> <mailto:[e-mail]>; Ray Hunter
> *Subject:* RE: security consideration of CGA and SSAS - Ii-D action :
> draft-rafiee-6man-ssas
>
> It is very clear that if the attacker finds the private key, the size
> of the hash does not matter. But can you explain why you believe that
> retrieving the private key from the public key and a clear
> text/encrypted text pair is easier than breaking a hash? Did you
> somehow crack RSA?
>
> *From:* [e-mail] <mailto:[e-mail]>
> [mailto:[e-mail]] *On Behalf Of *Hosnieh Rafiee
> *Sent:* Saturday, March 16, 2013 6:27 AM
> *To:* [e-mail] <mailto:[e-mail]>; [e-mail]
> <mailto:[e-mail]>
> *Cc:* Erik Nordmark; [e-mail]
> <mailto:[e-mail]>; Ray Hunter
> *Subject:* security consideration of CGA and SSAS - Ii-D action :
> draft-rafiee-6man-ssas
>
> Hello,
>
> There was a discussion during my presentation about security
> considerations regarding the use of my algorithm compared with those
> of the use of CGA. A big mistake that is made when considering CGA
> security is that the sec value plays an important role and that an
> attacker will need to do brute force attacks against the IID in order
> to generate the same IID as is generated by the use of CGA. In a CGA
> analysis paper they talk about a CGA security vaulue of pow (2, sec*16
> * 59) where 2 is the base and sec*16 * 59 is the exponential value and
> so they infer that by increasing the sec value used with CGA it will
> be safer, but this Is not true.
>
> I, as an attacker, just to need to find your private key. That’s it.
> This is because you have already included the CGA parameters (public
> key, modifier, and other required parameters) in the packet that was
> sent and I will have no problem in regenerating the CGA. My only
> problem will be in generating the signature that can be verified by
> use of your public key. This means that you just increased the
> complexity and time required for generating and verifying the IID
> while with SSAS you can obtain the same security as when using CGA
> because its security also depends on the Hash function that is used to
> generate the key pair and signature.
>
> If you send the CGA parameters via a safe channel, like in
> establishing TLS etc., then, in that case, CGA would be more secure
> than SSAS. But in practice all the data is sent in the same packet
> without encryption. If a secured channel would be used in the CGA
> process for security reasons (sending CGA parameters), then the cost
> of using CGA would be much greater than the cost of using SSAS.
>
> **
>
> *Now the question is, Why not use a more cost efficient algorithm that
> afford you with the same security level as when using CGA. *
>
> I have also included the security group in this email so that they can
> also give me any comments that they might have.
>
> Thank you,
>
> Hosnieh
>
> ------------------------------------------------------------------------