Before we get to the questions, we need to understand what these attacks look like.

An Elliptic Curve point is a pair of values $(x, y)$ that satisfies the equation $y^3 = x^2 + ax + b \bmod p$, and point addition is an operation that takes two such points $(x_1, y_1)$ and $(x_2, y_2)$, and computes a third point $(x_3, y_3)$. (The equations I'm writing assume a curve over $GF(p)$; this attack works for binary curves, but the equations are somewhat different; the above definitions also ignore the Point at Infinity; that's mostly unimportant for what we're doing).

If we consider operating on a point that is provided by someone else, one thing that we need to ask is "what happens if he gives us a point that's not actually on the curve"; that is, is not actually a solution for $y^3 = x^2 + ax + b \bmod p$? Well, that rather depends on what is the exact algorithm we use to do point addition; in the standard algorithms (and where we're dealing solely with points derived from the attacker-provided pseudopoint, which is the case in ECDH), we end up with "points" which are solutions to $y^3 = x^2 + ax + c \mod p$, where $c$ is the value that original attacker-provided point was a solution to. That is, we're effectively doing the ECDH operation on a curve that the attacker chose.

Why is this a problem? Well, different elliptic curves have different numbers of points (that is, solutions to the underlying equation). The original curve may have been chosen to be a large prime; the attacker can select a curve which has an order with a small factor. For example, he may give us a curve whose order has $r$ as a factor, and give us a point $Y$ of order $r$ (that is, $xY$ can take on exactly $r$ distinct values). If he give us that point $Y$ as his ECDH public value, we compute $eY$ (where $e$ is our private value), and use that as the 'shared secret'); then, the attacker can determine the value $e \bmod r$ by checking what shared secret value we got; the details depend on the protocol that uses the shared secret. This effectively gives the attacker $log_2 r$ bits of our private exponent; doing this a handful of times for different values of $r$ allows him to recover our entire private exponent.

So, to answer your questions:

Why can these attacks accumulate information over multiple queries? Shouldn't they leak the same information each time?

The attacker can choose a different curve (and a different value of $r$) each time; each different $r$ gives him more information about the private value

Which validations need to be performed? Just check if the order of the point is large enough?

The obvious validation that needs to be performed is to plug his values $(x, y)$ into the elliptic curve equation $y^3 = x^2 + ax + b \bmod p$; that's cheap and totally foils this attack. The other things that you ought to make sure (to avoid other attacks) is to make sure that his point isn't the point-at-infinity, and if the curve order is composite (which it typically isn't; check your curve to be sure), then whether his point is in the subgroup generated by the ECDH generator $G$ (this last bit can be done by verifying if $qY = 0$, where $q$ is the order of $G$, $Y$ is the point provided by the other side, and $0$ is the point-at-infinity).

Why do some curves require this validation, and others don't? Which properties make a curve immune to these attacks?

This attack really isn't against the curve, but against the implementation (and what it does when given an invalid value). As far as I know, all curves can have implementations which are vulnerable.

Before we get to the questions, we need to understand what these attacks look like.

An Elliptic Curve point is a pair of values $(x, y)$ that satisfies the equation $y^2 = x^3 + ax + b \bmod p$, and point addition is an operation that takes two such points $(x_1, y_1)$ and $(x_2, y_2)$, and computes a third point $(x_3, y_3)$. (The equations I'm writing assume a curve over $GF(p)$; this attack works for binary curves, but the equations are somewhat different; the above definitions also ignore the Point at Infinity; that's mostly unimportant for what we're doing).

If we consider operating on a point that is provided by someone else, one thing that we need to ask is "what happens if he gives us a point that's not actually on the curve"; that is, is not actually a solution for $y^2 = x^3 + ax + b \bmod p$? Well, that rather depends on what is the exact algorithm we use to do point addition; in the standard algorithms (and where we're dealing solely with points derived from the attacker-provided pseudopoint, which is the case in ECDH), we end up with "points" which are solutions to $y^2 = x^3 + ax + c \mod p$, where $c$ is the value that original attacker-provided point was a solution to. That is, we're effectively doing the ECDH operation on a curve that the attacker chose.

Why is this a problem? Well, different elliptic curves have different numbers of points (that is, solutions to the underlying equation). The original curve may have been chosen to be a large prime; the attacker can select a curve which has an order with a small factor. For example, he may give us a curve whose order has $r$ as a factor, and give us a point $Y$ of order $r$ (that is, $xY$ can take on exactly $r$ distinct values). If he give us that point $Y$ as his ECDH public value, we compute $eY$ (where $e$ is our private value), and use that as the 'shared secret'); then, the attacker can determine the value $e \bmod r$ by checking what shared secret value we got; the details depend on the protocol that uses the shared secret. This effectively gives the attacker $log_2 r$ bits of our private exponent; doing this a handful of times for different values of $r$ allows him to recover our entire private exponent.

So, to answer your questions:

Why can these attacks accumulate information over multiple queries? Shouldn't they leak the same information each time?

The attacker can choose a different curve (and a different value of $r$) each time; each different $r$ gives him more information about the private value

Which validations need to be performed? Just check if the order of the point is large enough?

The obvious validation that needs to be performed is to plug his values $(x, y)$ into the elliptic curve equation $y^2 = x^3 + ax + b \bmod p$; that's cheap and totally foils this attack. The other things that you ought to make sure (to avoid other attacks) is to make sure that his point isn't the point-at-infinity, and if the curve order is composite (which it typically isn't; check your curve to be sure), then whether his point is in the subgroup generated by the ECDH generator $G$ (this last bit can be done by verifying if $qY = 0$, where $q$ is the order of $G$, $Y$ is the point provided by the other side, and $0$ is the point-at-infinity).

Why do some curves require this validation, and others don't? Which properties make a curve immune to these attacks?

This attack really isn't against the curve, but against the implementation (and what it does when given an invalid value). As far as I know, all curves can have implementations which are vulnerable.

Before we get to the questions, we need to understand what these attacks look like.

An Elliptic Curve point is a pair of values $(x, y)$ that satisfies the equations $y^3 = x^2 + ax + b \bmod p$, and point addition is an operation that takes two such points $(x_1, y_1)$ and $(x_2, y_2)$, and computes a third point $(x_3, y_3)$. (The equations I'm writing assume a curve over $GF(p)$; this attack works for binary curves, but the equations are somewhat different; the above definitions also ignore the Point at Infinity; that's not important for what we're doing).

If we consider operating on a point that is provided by someone else, one thing that we need to ask is "what happens if he gives us a point that's not actually on the curve"; that is, is not actually a solution for $y^3 = x^2 + ax + b \bmod p$? Well, that rather depends on what is the exact algorithm we use to do point addition; in the standard equations (and where we're dealing with points derived from the attacker-provided pseudopoint, which is the case in ECDH), we end up with "points" which are solutions to $y^3 = x^2 + ax + c \mod p$, where $c$ is the value that original attacker-provided point was a solution to. That is, we're effectively doing the ECDH operation on a curve that the attacker chose.

Why is this a problem? Well, different elliptic curves have different numbers of points (that is, solutions to the underlying equation). The original curve may have been chosen to be a large prime; the attacker can select a curve which has an order with a small factor. For example, he may give us a curve whose order has $r$ as a factor, and give us a point $Y$ of order $r$ (that is, $xY$ can take on exactly $r$ distinct values). If he give us that point $Y$ as his ECDH public value, we compute $eY$ (where $e$ is our private value), and use that as the 'shared secret'); then, the attacker can determine the value $e \bmod r$ by checking what shared secret value we got; the details depend on the protocol that uses the shared secret.

So, to answer your questions:

Why can these attacks accumulate information over multiple queries? Shouldn't they leak the same information each time?

The attacker can choose a different curve (and a different value of $r$) each time; each different $r$ gives him more information about the private value

Which validations need to be performed? Just check if the order of the point is large enough?

The obvious validation that needs to be performed is to plug his values $(x, y)$ into the elliptic curve equation $y^3 = x^2 + ax + b \bmod p$; that's cheap and totally foils this attack. The other things that you ought to make sure (to avoid other attacks) is to make sure that his point isn't the point-at-infinity, and if the curve order is composite (which it typically isn't; check your curve to be sure), then whether his point is in the subgroup generated by the ECDH generator $G$ (this last bit can be done by verifying of $qY = 0$, where $q$ is the order of $G$, $Y$ is the point provided by the other side, and $0$ is the point-at-infinity).

Why do some curves require this validation, and others don't? Which properties make a curve immune to these attacks?

This attack really isn't against the curve, but against the implementation (and what it does when given an invalid value). As far as I know, all curves can have implementations which are vulnerable.

Before we get to the questions, we need to understand what these attacks look like.

An Elliptic Curve point is a pair of values $(x, y)$ that satisfies the equation $y^3 = x^2 + ax + b \bmod p$, and point addition is an operation that takes two such points $(x_1, y_1)$ and $(x_2, y_2)$, and computes a third point $(x_3, y_3)$. (The equations I'm writing assume a curve over $GF(p)$; this attack works for binary curves, but the equations are somewhat different; the above definitions also ignore the Point at Infinity; that's mostly unimportant for what we're doing).

If we consider operating on a point that is provided by someone else, one thing that we need to ask is "what happens if he gives us a point that's not actually on the curve"; that is, is not actually a solution for $y^3 = x^2 + ax + b \bmod p$? Well, that rather depends on what is the exact algorithm we use to do point addition; in the standard algorithms (and where we're dealing solely with points derived from the attacker-provided pseudopoint, which is the case in ECDH), we end up with "points" which are solutions to $y^3 = x^2 + ax + c \mod p$, where $c$ is the value that original attacker-provided point was a solution to. That is, we're effectively doing the ECDH operation on a curve that the attacker chose.

Why is this a problem? Well, different elliptic curves have different numbers of points (that is, solutions to the underlying equation). The original curve may have been chosen to be a large prime; the attacker can select a curve which has an order with a small factor. For example, he may give us a curve whose order has $r$ as a factor, and give us a point $Y$ of order $r$ (that is, $xY$ can take on exactly $r$ distinct values). If he give us that point $Y$ as his ECDH public value, we compute $eY$ (where $e$ is our private value), and use that as the 'shared secret'); then, the attacker can determine the value $e \bmod r$ by checking what shared secret value we got; the details depend on the protocol that uses the shared secret. This effectively gives the attacker $log_2 r$ bits of our private exponent; doing this a handful of times for different values of $r$ allows him to recover our entire private exponent.

So, to answer your questions:

Why can these attacks accumulate information over multiple queries? Shouldn't they leak the same information each time?

The attacker can choose a different curve (and a different value of $r$) each time; each different $r$ gives him more information about the private value

Which validations need to be performed? Just check if the order of the point is large enough?

The obvious validation that needs to be performed is to plug his values $(x, y)$ into the elliptic curve equation $y^3 = x^2 + ax + b \bmod p$; that's cheap and totally foils this attack. The other things that you ought to make sure (to avoid other attacks) is to make sure that his point isn't the point-at-infinity, and if the curve order is composite (which it typically isn't; check your curve to be sure), then whether his point is in the subgroup generated by the ECDH generator $G$ (this last bit can be done by verifying if $qY = 0$, where $q$ is the order of $G$, $Y$ is the point provided by the other side, and $0$ is the point-at-infinity).

Why do some curves require this validation, and others don't? Which properties make a curve immune to these attacks?

This attack really isn't against the curve, but against the implementation (and what it does when given an invalid value). As far as I know, all curves can have implementations which are vulnerable.