Re: [IPsec] Some speculations about puzzles
Hi Yaron, We are almost in agreement. My understanding is that both the IKE_SA_INIT and IKE_AUTH puzzles are needed, and each one has a different goal: - IKE_SA_INIT puzzle: should counteract the responder's memory cost of keeping the half-open SA, and its CPU cost in computing DH. - IKE_AUTH puzzle: should counteract the responder's CPU cost of validating the AUTH payload. Thank you, now I better understand your position. Let me rephrase it. You propose that IKE_AUTH puzzle resides inside SK payload and its verifications takes place after computing DH and verifying authenticity of IKE_AUTH messag, but before any actionts dealing with peer authentication take place. Am I right? This will allow attacker to perform an attack on responder's CPU power by sending single garbage message in IKE_AUTH, which will be partially counteracted by IKE_SA_INIT puzzle. But this will definitely ease legitimate client's burden in case of IKE fragmentation. I still prefer IKE_AUTH puzzle to reside outside SK payload and to be verified before performing DH and computing SKEYSEED. However, after some thoughts, I think that in case of IKE fragmentation, puzzle must only present in the very first fragment (outside SKF payload), not in the every fragment, as I proposed before. The responder in this case will pay no attention on the other fragments untill it receives the first one and verifies the puzzle. Fragments that were received before this event could be dropped (in a hope that they will be eventually retransmitted) or just collected with no action. In the latter case after the puzzle is vefified and DH is computed all the collected fragments must be verified for theit authenticity. This approach would still require legitimate client to re-solve puzzle in case it first sends unfragmented message and then switches IP fragmentation on (or in case it refragments the message with smaller MTU), but it would provide better defense against attacks on CPU exhausting in IKE_AUTH. Regards, Valery. ___ IPsec mailing list IPsec@ietf.org https://www.ietf.org/mailman/listinfo/ipsec
Re: [IPsec] Some speculations about puzzles
But I think we're looking at the wrong problem. Let us look at why we might need to add puzzles to IKE_AUTH at all. There are two cases: - The IKE SA is set up by a valid initiator. - The IKE SA is set up by an attacker. In the first case, the responder needs to compute SKEYSEED anyway. It should compute it once and cache it, even if it sees multiple bogus IKE_AUTH messages sent by attackers. Verifying IKE_AUTH messages is cheap once SKEYSEED has been computed, because you only need to verify that the SK integrity protection is valid. The (valid) initiator "pays the price" once, in the form of an IKE_SA_INIT puzzle. In the second case, the attacker also pays the price if we have a puzzle attached to IKE_SA_INIT. And the responder only computes SKEYSEED once, and caches the result. Since SKEYSEED is known to the attacker, it can send valid SK payloads, and the responder is forced to validate the certificate (expensive). So attaching a puzzle to IKE_AUTH is justified, to make the attacker pay for each certificate validation. But this also shows that the IKE_SA_INIT puzzle is sufficient to counteract the cost of computing SKEYSEED (which is all you need for reassembly), and when even using fragmentation, this is only done once. I agree with your analysis. However I'm not sure I agree with conclusion. IKE_SA_INIT puzzle defends from exhausting responder's memory, while IKE_AUTH puzzle defends from exhausting CPU power. My primary concern is distributed DoS attack when attackers are indistinguishable from legitimate clients. In this case attacker does pay the price of IKE_SA_INIT puzzle, but after that it is free to attack responder's CPU by sending bogus messages or valid messages with bogus content. I agree, that once SKEYSEED is computed the bogus messages are easy to detect. However performing DH is relatively expensive for responder, while sending bogus message is free for attacker (once it has paid an "entrance fee"), that makes this attack attractive. Another option - sending valid messages with bogus auth content, that will require responder to do a lot of work. It will require from attacker to compute SKEYSEED, but the responder would have to spend much more resources, so the attack is also attractive. IKE_AUTH puzzle eliminates the first attack and makes the second expensive for attacker. IKE_AUTH puzzle is just a "second line of defense". You are probably right that we can get rid of it and raise the difficulty level of the "first line", but I'm not yet sure that we will gain an equal effect. We are almost in agreement. My understanding is that both the IKE_SA_INIT and IKE_AUTH puzzles are needed, and each one has a different goal: - IKE_SA_INIT puzzle: should counteract the responder's memory cost of keeping the half-open SA, and its CPU cost in computing DH. - IKE_AUTH puzzle: should counteract the responder's CPU cost of validating the AUTH payload. Thanks, Yaron ___ IPsec mailing list IPsec@ietf.org https://www.ietf.org/mailman/listinfo/ipsec
Re: [IPsec] Some speculations about puzzles
I get your point, but I think this is more than unfortunate, this is real ugly. RFC 7383 is primarily about IKE_AUTH, and now, in the case of those broken networks that limit the MTU, we are reducing the effective MTU yet again. Not much, a dozen of bytes. But I think we're looking at the wrong problem. Let us look at why we might need to add puzzles to IKE_AUTH at all. There are two cases: - The IKE SA is set up by a valid initiator. - The IKE SA is set up by an attacker. In the first case, the responder needs to compute SKEYSEED anyway. It should compute it once and cache it, even if it sees multiple bogus IKE_AUTH messages sent by attackers. Verifying IKE_AUTH messages is cheap once SKEYSEED has been computed, because you only need to verify that the SK integrity protection is valid. The (valid) initiator "pays the price" once, in the form of an IKE_SA_INIT puzzle. In the second case, the attacker also pays the price if we have a puzzle attached to IKE_SA_INIT. And the responder only computes SKEYSEED once, and caches the result. Since SKEYSEED is known to the attacker, it can send valid SK payloads, and the responder is forced to validate the certificate (expensive). So attaching a puzzle to IKE_AUTH is justified, to make the attacker pay for each certificate validation. But this also shows that the IKE_SA_INIT puzzle is sufficient to counteract the cost of computing SKEYSEED (which is all you need for reassembly), and when even using fragmentation, this is only done once. I agree with your analysis. However I'm not sure I agree with conclusion. IKE_SA_INIT puzzle defends from exhausting responder's memory, while IKE_AUTH puzzle defends from exhausting CPU power. My primary concern is distributed DoS attack when attackers are indistinguishable from legitimate clients. In this case attacker does pay the price of IKE_SA_INIT puzzle, but after that it is free to attack responder's CPU by sending bogus messages or valid messages with bogus content. I agree, that once SKEYSEED is computed the bogus messages are easy to detect. However performing DH is relatively expensive for responder, while sending bogus message is free for attacker (once it has paid an "entrance fee"), that makes this attack attractive. Another option - sending valid messages with bogus auth content, that will require responder to do a lot of work. It will require from attacker to compute SKEYSEED, but the responder would have to spend much more resources, so the attack is also attractive. IKE_AUTH puzzle eliminates the first attack and makes the second expensive for attacker. IKE_AUTH puzzle is just a "second line of defense". You are probably right that we can get rid of it and raise the difficulty level of the "first line", but I'm not yet sure that we will gain an equal effect. Regards, Valery. Thanks, Yaron ___ IPsec mailing list IPsec@ietf.org https://www.ietf.org/mailman/listinfo/ipsec
Re: [IPsec] Some speculations about puzzles
And again for IKE_AUTH, I don't see why with fragmentation you need one puzzle solution per fragment. The major CPU cost (DH computation, certificate stuff and decryption) comes once, after the message is re-assembled. So it seems to me only one puzzle response is needed for the entire message. In this case the responder would become succeptible to the attack when attacker emits forged fragments, that takes place of good fragments from legitimate initiator in the reassembly queue. To detect the forgery responder needs to check fragment authenticity before inserting it into the reassembly queue. That would require performing DH and calculating SK_a*, but that is what we are willing to defer unless peer proves that it is really really wants to setup connection and is ready to spend quite a lot of resources to do it. It would be possible to protect with puzzle only the very first fragment, because as we have calculated SK_a* it takes very little resources to verify the other fragments, but fragments can arrive in any order, so puzzle must be in each fragment. That is a bit unfortunate for the initiator, I admit. I get your point, but I think this is more than unfortunate, this is real ugly. RFC 7383 is primarily about IKE_AUTH, and now, in the case of those broken networks that limit the MTU, we are reducing the effective MTU yet again. But I think we're looking at the wrong problem. Let us look at why we might need to add puzzles to IKE_AUTH at all. There are two cases: - The IKE SA is set up by a valid initiator. - The IKE SA is set up by an attacker. In the first case, the responder needs to compute SKEYSEED anyway. It should compute it once and cache it, even if it sees multiple bogus IKE_AUTH messages sent by attackers. Verifying IKE_AUTH messages is cheap once SKEYSEED has been computed, because you only need to verify that the SK integrity protection is valid. The (valid) initiator "pays the price" once, in the form of an IKE_SA_INIT puzzle. In the second case, the attacker also pays the price if we have a puzzle attached to IKE_SA_INIT. And the responder only computes SKEYSEED once, and caches the result. Since SKEYSEED is known to the attacker, it can send valid SK payloads, and the responder is forced to validate the certificate (expensive). So attaching a puzzle to IKE_AUTH is justified, to make the attacker pay for each certificate validation. But this also shows that the IKE_SA_INIT puzzle is sufficient to counteract the cost of computing SKEYSEED (which is all you need for reassembly), and when even using fragmentation, this is only done once. Thanks, Yaron ___ IPsec mailing list IPsec@ietf.org https://www.ietf.org/mailman/listinfo/ipsec
Re: [IPsec] Some speculations about puzzles
Hi Valery Thanks again. I interoperated the thread as your approach would have 'difficulty' replaced with 'generation_id'. (I now know this isn't the case). thanks On 04/12/2014 11:50, "Valery Smyslov" wrote: >In my approach >the level is encoded in the cookie itself, in Yoav's approach it is >locally accociated with "generation_id", which is encoded >in the cookie. smime.p7s Description: S/MIME cryptographic signature ___ IPsec mailing list IPsec@ietf.org https://www.ietf.org/mailman/listinfo/ipsec
Re: [IPsec] Some speculations about puzzles
Hi Yaron, Going back to your original message (I guess not everyone read it to the end :-) If your guess is correct then it's a pity :-( I don't understand how puzzles for IKE_AUTH can be mandatory without breaking the protocol. The responder doesn't even know that the initiator supports puzzles. At the very least, we would need to add a "puzzles supported" notification. I probably wasn't clear enough. I meant that if client supports puzzles and accepts puzzle in IKE_SA_INIT, then it must also solve puzzle in IKE_AUTH. In other words, the puzzles in IKE_SA_INIT are optional for the client, but if they are accepted by client in IKE_SA_INIT, then they must also be used in IKE_AUTH. The reason for such a strong requirement is that in the situation when responder has already created the state but has not yet authenticated the initiator it becomes an easy target for DoS attack (as it is mentioned in the draft). And again for IKE_AUTH, I don't see why with fragmentation you need one puzzle solution per fragment. The major CPU cost (DH computation, certificate stuff and decryption) comes once, after the message is re-assembled. So it seems to me only one puzzle response is needed for the entire message. In this case the responder would become succeptible to the attack when attacker emits forged fragments, that takes place of good fragments from legitimate initiator in the reassembly queue. To detect the forgery responder needs to check fragment authenticity before inserting it into the reassembly queue. That would require performing DH and calculating SK_a*, but that is what we are willing to defer unless peer proves that it is really really wants to setup connection and is ready to spend quite a lot of resources to do it. It would be possible to protect with puzzle only the very first fragment, because as we have calculated SK_a* it takes very little resources to verify the other fragments, but fragments can arrive in any order, so puzzle must be in each fragment. That is a bit unfortunate for the initiator, I admit. Thanks, Yaron Regards, Valery. ___ IPsec mailing list IPsec@ietf.org https://www.ietf.org/mailman/listinfo/ipsec
Re: [IPsec] Some speculations about puzzles
Hi Valery, Going back to your original message (I guess not everyone read it to the end :-) I don't understand how puzzles for IKE_AUTH can be mandatory without breaking the protocol. The responder doesn't even know that the initiator supports puzzles. At the very least, we would need to add a "puzzles supported" notification. And again for IKE_AUTH, I don't see why with fragmentation you need one puzzle solution per fragment. The major CPU cost (DH computation, certificate stuff and decryption) comes once, after the message is re-assembled. So it seems to me only one puzzle response is needed for the entire message. Thanks, Yaron ___ IPsec mailing list IPsec@ietf.org https://www.ietf.org/mailman/listinfo/ipsec
Re: [IPsec] Some speculations about puzzles
Hi Graham, I'm not Yoav, but I'll try to clarify. Hi Yoav As I understand this, changing the concept from 'difficulty level' to 'puzzle/generation id' doesn't allow for a responder to hand out some puzzles weaker than others at the same time? (Unless it's tracked locally as you said), but then the Responder would need to remember all previous Yes, in Yoav's approach the responder should remember last N pairs "generation_id : difficulty: secret". Puzzles up to the last point where a certain GenerationID was used if it's to issue Puzzles of different difficulty at the same time. (Otherwise I see an attack where someone can potentially just make all new connections have the most difficult puzzles, there might be a need for some random un-fairness with 1 in X having hard puzzles?). Also if the 'difficulty level' is no longer used, how does the client know what difficulty this is ? Generation 9 could be 23-bit one day and 0 the next. In any case (with mine or Yoav's approach) the difficulty level must be indicated to initiator explicitely, in a separate field (it presumably must be in (to be defined) PUZZLE Notification). Difficulty level in cookie (as I suggested) is for responder's use only. For initiator the cookie is an opaque blob in any case, but responder must be able to determine which difficulty level was requested with any particular cookie. In my approach the level is encoded in the cookie itself, in Yoav's approach it is locally accociated with "generation_id", which is encoded in the cookie. Both approaches are workable. There are some advantages and drawbacks in each, but they are insignificant, IMHO. Regards, Valery. If both are included this allows for the Responder to change secret and also allow for multiple difficulty types. Cookie = | | | | | Hash(Ni | IPi | SPIi | | | | | ) thanks On 03/12/2014 23:46, "Yoav Nir" wrote: Why? The responder can remember that generation 8 had a 20-bit difficulty level. If the attack then gets worse, than generation 9 is created with a 23-bit difficulty level. The responder needs only remember the generation and associated difficulty level. On Dec 4, 2014, at 1:07 AM, Graham Bartlett (grbartle) wrote: If the 1 byte 'difficulty level' has become the 'puzzle id', could we break the 1 byte into two 4 bits? 1st 4 bits is 'puzzle/generation id', next 4bits is 'difficulty level', this allows for 16 cycles for when every secret changes and still allows 16 levels of puzzles.. (just a thought as if the difficulty level disappears you loose the ability to set a the hardness of the puzzle) On 03/12/2014 16:01, "Yoav Nir" wrote: On Dec 3, 2014, at 5:44 PM, Valery Smyslov wrote: Hi Scott, this is almost identical to what I proposed in my original e-mail, if you substitute "difficulty level" with "puzzle id©ч. Or call it ©шgeneration id©ч, and increment it whenever you generate a new secret and/or change the difficulty level. ___ IPsec mailing list IPsec@ietf.org https://www.ietf.org/mailman/listinfo/ipsec
Re: [IPsec] Some speculations about puzzles
Hi Yoav As I understand this, changing the concept from 'difficulty level' to 'puzzle/generation id' doesn't allow for a responder to hand out some puzzles weaker than others at the same time? (Unless it's tracked locally as you said), but then the Responder would need to remember all previous Puzzles up to the last point where a certain GenerationID was used if it's to issue Puzzles of different difficulty at the same time. (Otherwise I see an attack where someone can potentially just make all new connections have the most difficult puzzles, there might be a need for some random un-fairness with 1 in X having hard puzzles?). Also if the 'difficulty level' is no longer used, how does the client know what difficulty this is ? Generation 9 could be 23-bit one day and 0 the next. If both are included this allows for the Responder to change secret and also allow for multiple difficulty types. Cookie = | | | | | Hash(Ni | IPi | SPIi | | | | | ) thanks On 03/12/2014 23:46, "Yoav Nir" wrote: >Why? The responder can remember that generation 8 had a 20-bit >difficulty level. If the attack then gets worse, than generation 9 is >created with a 23-bit difficulty level. > >The responder needs only remember the generation and associated >difficulty level. > >> On Dec 4, 2014, at 1:07 AM, Graham Bartlett (grbartle) >> wrote: >> >> >> If the 1 byte 'difficulty level' has become the 'puzzle id', could we >> break the 1 byte into two 4 bits? >> >> 1st 4 bits is 'puzzle/generation id', next 4bits is 'difficulty level', >> this allows for 16 cycles for when every secret changes and still allows >> 16 levels of puzzles.. >> >> (just a thought as if the difficulty level disappears you loose the >> ability to set a the hardness of the puzzle) >> >> >> On 03/12/2014 16:01, "Yoav Nir" wrote: >> >>> On Dec 3, 2014, at 5:44 PM, Valery Smyslov wrote: Hi Scott, this is almost identical to what I proposed in my original e-mail, if you substitute "difficulty level" with "puzzle id². >>> >>> Or call it ³generation id², and increment it whenever you generate a >>>new >>> secret and/or change the difficulty level. > smime.p7s Description: S/MIME cryptographic signature ___ IPsec mailing list IPsec@ietf.org https://www.ietf.org/mailman/listinfo/ipsec
Re: [IPsec] Some speculations about puzzles
> On Dec 4, 2014, at 9:20 AM, Valery Smyslov wrote: > >>> Hi Scott, >>> >>> this is almost identical to what I proposed in my original e-mail, >>> if you substitute "difficulty level" with "puzzle id”. >> >> Or call it “generation id”, and increment it whenever you generate a new >> secret and/or change the difficulty level.= > > That will work. In this case it is better to make “generation id” long enough > (4 bytes or longer) > and initialize it with random value after reboot. > > Anyway, it doesn't matter how exactly the cookie is constructed and it should > not be mandated in RFC, as it doest't affect interoperability. However, some > guidance and examples should be given. Definitely agree. If a document doesn’t give an example of how to do this non-stupidly, implementers will come up with multiple creative ways of doing this wrong. > In particular, RFC should advise > implementers to construct cookie in such way, that the responder is able to > quickly detect > invalid/stale/forged cookies/puzzles spending as little resources as possible. Yoav ___ IPsec mailing list IPsec@ietf.org https://www.ietf.org/mailman/listinfo/ipsec
Re: [IPsec] Some speculations about puzzles
Hi Scott, this is almost identical to what I proposed in my original e-mail, if you substitute "difficulty level" with "puzzle id”. Or call it “generation id”, and increment it whenever you generate a new secret and/or change the difficulty level.= That will work. In this case it is better to make “generation id” long enough (4 bytes or longer) and initialize it with random value after reboot. Anyway, it doesn't matter how exactly the cookie is constructed and it should not be mandated in RFC, as it doest't affect interoperability. However, some guidance and examples should be given. In particular, RFC should advise implementers to construct cookie in such way, that the responder is able to quickly detect invalid/stale/forged cookies/puzzles spending as little resources as possible. ___ IPsec mailing list IPsec@ietf.org https://www.ietf.org/mailman/listinfo/ipsec
Re: [IPsec] Some speculations about puzzles
Why? The responder can remember that generation 8 had a 20-bit difficulty level. If the attack then gets worse, than generation 9 is created with a 23-bit difficulty level. The responder needs only remember the generation and associated difficulty level. > On Dec 4, 2014, at 1:07 AM, Graham Bartlett (grbartle) > wrote: > > > If the 1 byte 'difficulty level' has become the 'puzzle id', could we > break the 1 byte into two 4 bits? > > 1st 4 bits is 'puzzle/generation id', next 4bits is 'difficulty level', > this allows for 16 cycles for when every secret changes and still allows > 16 levels of puzzles.. > > (just a thought as if the difficulty level disappears you loose the > ability to set a the hardness of the puzzle) > > > On 03/12/2014 16:01, "Yoav Nir" wrote: > >> >>> On Dec 3, 2014, at 5:44 PM, Valery Smyslov wrote: >>> >>> Hi Scott, >>> >>> this is almost identical to what I proposed in my original e-mail, >>> if you substitute "difficulty level" with "puzzle id². >> >> Or call it ³generation id², and increment it whenever you generate a new >> secret and/or change the difficulty level. ___ IPsec mailing list IPsec@ietf.org https://www.ietf.org/mailman/listinfo/ipsec
Re: [IPsec] Some speculations about puzzles
If the 1 byte 'difficulty level' has become the 'puzzle id', could we break the 1 byte into two 4 bits? 1st 4 bits is 'puzzle/generation id', next 4bits is 'difficulty level', this allows for 16 cycles for when every secret changes and still allows 16 levels of puzzles.. (just a thought as if the difficulty level disappears you loose the ability to set a the hardness of the puzzle) On 03/12/2014 16:01, "Yoav Nir" wrote: > >> On Dec 3, 2014, at 5:44 PM, Valery Smyslov wrote: >> >> Hi Scott, >> >> this is almost identical to what I proposed in my original e-mail, >> if you substitute "difficulty level" with "puzzle id². > >Or call it ³generation id², and increment it whenever you generate a new >secret and/or change the difficulty level. smime.p7s Description: S/MIME cryptographic signature ___ IPsec mailing list IPsec@ietf.org https://www.ietf.org/mailman/listinfo/ipsec
Re: [IPsec] Some speculations about puzzles
> On Dec 3, 2014, at 5:44 PM, Valery Smyslov wrote: > > Hi Scott, > > this is almost identical to what I proposed in my original e-mail, > if you substitute "difficulty level" with "puzzle id”. Or call it “generation id”, and increment it whenever you generate a new secret and/or change the difficulty level. ___ IPsec mailing list IPsec@ietf.org https://www.ietf.org/mailman/listinfo/ipsec
Re: [IPsec] Some speculations about puzzles
Hi Scott, this is almost identical to what I proposed in my original e-mail, if you substitute "difficulty level" with "puzzle id". In more generic way - responder encodes in cookie/puzzle all the information that could help him quickly reject invalid/stale/forged puzzles without wasting resources. Valery. I think it’s simpler to keep a short list (a queue actually, but usually with no more than 2-5 entries) or pairs. Generate a new pair every 10 seconds or whenever the difficulty level needs to change. Remember all entries for the last 20 seconds. Calculate the cookie as described in the RFC. When receiving a cookie, you try to validate it using all the remembered secret-difficulty pairs (I guess you check for sufficiently many zeros before you check for the hash), and let them in if one such pair validated. You can do it easier than that; encode a 'puzzle id' within the puzzle you send to the client (and which they must send back); that way, you can look up the puzzle you originally asked, and check the answer only against that one. ___ IPsec mailing list IPsec@ietf.org https://www.ietf.org/mailman/listinfo/ipsec
Re: [IPsec] Some speculations about puzzles
> -Original Message- > From: IPsec [mailto:ipsec-boun...@ietf.org] On Behalf Of Yoav Nir > Sent: Wednesday, December 03, 2014 10:06 AM > To: Valery Smyslov > Cc: ipsec; Graham Bartlett (grbartle) > Subject: Re: [IPsec] Some speculations about puzzles > > I think it’s simpler to keep a short list (a queue actually, but usually with > no > more than 2-5 entries) or pairs. > > Generate a new pair every 10 seconds or whenever the difficulty level needs > to change. Remember all entries for the last 20 seconds. Calculate the cookie > as described in the RFC. > > When receiving a cookie, you try to validate it using all the remembered > secret-difficulty pairs (I guess you check for sufficiently many zeros before > you check for the hash), and let them in if one such pair validated. You can do it easier than that; encode a 'puzzle id' within the puzzle you send to the client (and which they must send back); that way, you can look up the puzzle you originally asked, and check the answer only against that one. ___ IPsec mailing list IPsec@ietf.org https://www.ietf.org/mailman/listinfo/ipsec
Re: [IPsec] Some speculations about puzzles
It is probably a bit simpler, but less efficient. With this try-and-catch approach you would need to perform hash (or PRF) computations several times before rejecting invalid puzzles. I'm in favor to minimize wasting of resourses for solution, which primary goal is to defend against DoS attack. - Original Message - From: "Yoav Nir" To: "Valery Smyslov" Cc: "Graham Bartlett (grbartle)" ; "ipsec" Sent: Wednesday, December 03, 2014 6:06 PM Subject: Re: [IPsec] Some speculations about puzzles I think it’s simpler to keep a short list (a queue actually, but usually with no more than 2-5 entries) or pairs. Generate a new pair every 10 seconds or whenever the difficulty level needs to change. Remember all entries for the last 20 seconds. Calculate the cookie as described in the RFC. When receiving a cookie, you try to validate it using all the remembered secret-difficulty pairs (I guess you check for sufficiently many zeros before you check for the hash), and let them in if one such pair validated. Yoav ___ IPsec mailing list IPsec@ietf.org https://www.ietf.org/mailman/listinfo/ipsec
Re: [IPsec] Some speculations about puzzles
I think it’s simpler to keep a short list (a queue actually, but usually with no more than 2-5 entries) or pairs. Generate a new pair every 10 seconds or whenever the difficulty level needs to change. Remember all entries for the last 20 seconds. Calculate the cookie as described in the RFC. When receiving a cookie, you try to validate it using all the remembered secret-difficulty pairs (I guess you check for sufficiently many zeros before you check for the hash), and let them in if one such pair validated. Yoav ___ IPsec mailing list IPsec@ietf.org https://www.ietf.org/mailman/listinfo/ipsec
Re: [IPsec] Some speculations about puzzles
Hi Graham,
Would the Timestamp be generated every time cycle? If this wasn't a static
figure (per timecycle - maybe when the secret is changed?, but rather a
rolling unix time), then how would the Responder be able to validate this
Cookie (without trying every previous timestamp or having the timestamp
included in the Initiators reply?).
Yes, it is included in Initiator's reply. More precisely - it is encoded in
cookie.
So, the cookie has some structure. The particular encoding is implementation
dependant (since it is a local responder's matter), but the idea is that
the cookie contains some fields, that responder can extract from it
and these fields are also included in Hash(Ni | IPi | SPIi | ... )
calculation to prevent attacker from manipulating them. For example:
1. First byte of cookie contains VersionIDofSecret
2. Next byte contains requested PuzzleDifficulty
3. Next 2 bytes contain transform ID for selected PRF
4. Next 4 bytes contain timestamp (just unix time())
5. The rest of the cookie contains hash of all these values + Ni + IPi +
SPIi +
Would it not be better to save X
number of Secrets and just try them instead (assuming that the Secret is
changing fairly regularly)? The Secret could also be used to tell (approx)
how old the Cookie is.
Using the fact that the secret for cookie generation must be changed
periodically is another option to deal with old puzzles. However,
the secret is global and the period of its changes is relatively
long (tens of seconds or even minutes). It is desirable to have finer
mechanism to deal with different puzzle difficulty levels for different
IP-addresses/prefixes. Of course it is possible to change secret every
second, but then we should make the long
enough to prevent wrapping and it is desirable that it survives reboots
and so on, so it just becomes a timestamp :-)
Regards,
Valery.
I like the two options of the header in the clear.
Many thanks
On 01/12/2014 15:34, "Valery Smyslov" wrote:
Hi, this is a long message.
First of all I think that the puzzles mechanism is a great tool
to make DoS attacks harder for attackers and we should
try to incorporate it into IKE. Moreover, I think that
the puzzles could be used not only in IKE_SA_INIT, but also
to defend against DoS attacks in IKE_AUTH exchange (see below).
However, the puzzles mechanism is a controversal thing,
since it requires an additional work from legitimate clients.
It could be particularly troublesome for small battery-powered wireless
devices (smartphones, IoT devices etc) - not only would it delay
connection
setup, but it also would decrease battery lifetime.
So think that the puzzles mechanism if incorporated into IKE should follow
some general principles:
1. Puzzles should be optional. It should be possible for client to just
return
cookie even if puzzle is given by SGW).
2. The ultimate decision whether to solve puzzle or ignore it should be
made
by client.
3. Those, who ignore puzzles (for any reason - either they are legacy
clients
or they decide to save battery) should still have a chance to setup
connection
(on "best effort" basis).
In other words, let's consider puzzles mechanizm not as discriminating
tool
("those who cannot solve puzzles won't be allowed in"), but as
a "first-class ticket" for those, who are ready to pay for it.
And the price for the first-class service should be high enough to make it
unattractive for attackers.
Concrete proposals.
1. Algorithm agility for puzzles. It is relatively easy to achieve. When
IKE_SA_INIT request comes from the client, the server could quicly parse
it,
find SA payload and figure out the list of transforms the client proposes.
Then it could select mutually supported PRF and indicate it to the client
in response containing puzzle. The puzzle in this case would look like:
"please, give me a string of octets such, that if this PRF is applied
to that string of octets using supplied cookie as the key, then the
result would contain this number of trailing zero bits" (another option -
apply PRF to cookie + string of octets using zero key).
Parsing IKE_SA_INIT message is a relatively easy task.
The side advantage of this approach is that the server
could quickly check the structure of the message and
the list of proposed transforms and wouldn't spend more resources
in case the initial message is malformed or no proposals are acceptable
to the responder.
2. Cookie generation. Currently RFC7296 suggestd the following
formula to compute cookie:
Cookie = | Hash(Ni | IPi | SPIi | )
With puzzles more information should be present in the cookie
to prevent some attacks from initiator. First, when
responder asks initiator to solve the puzzle, it sets puzzle
difficulty to some level and indicates it in the response message.
When the solved puzzle is returned back to the responder,
it must know in a stateless manner what level of difficulty
it has requested. Otherwise the initiator could cheat. So responder
must encode thi
Re: [IPsec] Some speculations about puzzles
Hi Valery
Would the Timestamp be generated every time cycle? If this wasn't a static
figure (per timecycle - maybe when the secret is changed?, but rather a
rolling unix time), then how would the Responder be able to validate this
Cookie (without trying every previous timestamp or having the timestamp
included in the Initiators reply?). Would it not be better to save X
number of Secrets and just try them instead (assuming that the Secret is
changing fairly regularly)? The Secret could also be used to tell (approx)
how old the Cookie is.
I like the two options of the header in the clear.
Many thanks
On 01/12/2014 15:34, "Valery Smyslov" wrote:
>Hi, this is a long message.
>
>First of all I think that the puzzles mechanism is a great tool
>to make DoS attacks harder for attackers and we should
>try to incorporate it into IKE. Moreover, I think that
>the puzzles could be used not only in IKE_SA_INIT, but also
>to defend against DoS attacks in IKE_AUTH exchange (see below).
>However, the puzzles mechanism is a controversal thing,
>since it requires an additional work from legitimate clients.
>It could be particularly troublesome for small battery-powered wireless
>devices (smartphones, IoT devices etc) - not only would it delay
>connection
>setup, but it also would decrease battery lifetime.
>
>So think that the puzzles mechanism if incorporated into IKE should follow
>some general principles:
>1. Puzzles should be optional. It should be possible for client to just
>return
>cookie even if puzzle is given by SGW).
>2. The ultimate decision whether to solve puzzle or ignore it should be
>made
>by client.
>3. Those, who ignore puzzles (for any reason - either they are legacy
>clients
>or they decide to save battery) should still have a chance to setup
>connection
>(on "best effort" basis).
>
>In other words, let's consider puzzles mechanizm not as discriminating
>tool
>("those who cannot solve puzzles won't be allowed in"), but as
>a "first-class ticket" for those, who are ready to pay for it.
>And the price for the first-class service should be high enough to make it
>unattractive for attackers.
>
>
>Concrete proposals.
>
>1. Algorithm agility for puzzles. It is relatively easy to achieve. When
>IKE_SA_INIT request comes from the client, the server could quicly parse
>it,
>find SA payload and figure out the list of transforms the client proposes.
>Then it could select mutually supported PRF and indicate it to the client
>in response containing puzzle. The puzzle in this case would look like:
>"please, give me a string of octets such, that if this PRF is applied
>to that string of octets using supplied cookie as the key, then the
>result would contain this number of trailing zero bits" (another option -
>apply PRF to cookie + string of octets using zero key).
>
>Parsing IKE_SA_INIT message is a relatively easy task.
>The side advantage of this approach is that the server
>could quickly check the structure of the message and
>the list of proposed transforms and wouldn't spend more resources
>in case the initial message is malformed or no proposals are acceptable
>to the responder.
>
>2. Cookie generation. Currently RFC7296 suggestd the following
>formula to compute cookie:
>
>Cookie = | Hash(Ni | IPi | SPIi | )
>
>With puzzles more information should be present in the cookie
>to prevent some attacks from initiator. First, when
>responder asks initiator to solve the puzzle, it sets puzzle
>difficulty to some level and indicates it in the response message.
>When the solved puzzle is returned back to the responder,
>it must know in a stateless manner what level of difficulty
>it has requested. Otherwise the initiator could cheat. So responder
>must encode this information into cookie, as the cookie is an entity that
>initiator cannot forge. Then, it is desirable to also include
>timestamp into cookie to prevent initiator from re-using solved puzzles
>and from collecting a lot of puzzles, solving them and then presenting
>them
>all at once. Including timestamp allows the responder
>to determine how old this cookie is and, therefore,
>how much time it was taken from the initiator to solve the puzzle.
>If the results are suspicious (an easy puzzle took too long to be solved),
>then the request should be rejected, even in the case it contains
>a valid solution for the puzzle. And in case of accepting
>algorithm agility method described above the selected PRF
>must also be encoded in cookie.
>
>So, the cookie generation would look like:
>
>Cookie = | | |
>
>|
>Hash(Ni | IPi | SPIi | | | |
>)
>
>Note, that should be allowed to be zero here -
>in case it is just a cookie request with no puzzle request.
>
>To summarize here is a possible sequence of messages in IKE_SA_INIT:
>
> request --> HDR, SA, KE, Ni,
> [N(NAT_DETECTION_SOURCE_IP)+,
>N(NAT_DETECTION_DESTINATION_IP),]
> [V+][N+]
>
>
