Hace algún tiempo yo trató de responder una pregunta en Security Stack Exchange, pero me he dado cuenta de que no estoy seguro de haber hecho bien las cuentas, y estoy aquí para pedir ayuda.
El escenario es el siguiente: alguien intenta entrar en la cuenta de otro usuario. Esa cuenta está protegida por una contraseña y por un llamado "segundo factor" (como un código enviado vis SMS, o generado por una app como Google Authenticator), y la hipótesis es que el atacante conoce la contraseña, por lo que la única protección viene dada por este código. Si se trata de un código de 3 dígitos, hay 1000 códigos posibles, y con un solo intento la probabilidad de adivinarlo es $p = \frac{1}{1000}$ . Esto es fácil. El punto en el que estoy atascado es el cálculo de la probabilidad de adivinar el código correcto si tiene más de un intento. Por ejemplo, él puede intentar como máximo 3 veces, y después de que la cuenta se bloquea para la protección, y es el juego terminado. ¿Cuál es la probabilidad de éxito, en ese caso?
Esto es lo que he probado.
En primer lugar, tenemos que establecer si el código correcto es el mismo para los tres intentos, o si cambia cada vez. He explorado ambos casos.
Caso A: el código es siempre el mismo.
Creo que esto se puede modelar con un hipergeométrico variable. Como dice la Wikipedia, es "la probabilidad de k aciertos en n sorteos, sin reemplazo, de una población finita de tamaño N que contiene exactamente K aciertos, en la que cada sorteo es un éxito o un fracaso". En nuestro caso, con N = 1000, K = 1, n = 3, k = 1, es
$$ \require{cancel} P_{Code\,is\,guessed} = \frac{\binom{1}{1} \binom{1000-1}{3-1}}{\binom{1000}{3}} = \frac{\binom{999}{2}}{\binom{1000}{3}} = \frac{\frac{999!}{2!\cdot\cancel{997!}}}{\frac{1000!}{3!\cdot\cancel{997!}}} = \frac{\frac{\cancel{999!}}{\cancel{2}}}{\frac{1000\cdot\cancel{999!}}{3\cdot\cancel{2}\cdot1}} = \frac{3}{1000} $$
Para confirmarlo, he dibujado un árbol con los posibles resultados: en cada nodo hay una suposición. La rama verde corresponde a adivinar el código correcto, la rama roja a no adivinarlo y pasar al siguiente intento (salvo que sea el último): 
La probabilidad de acabar en una determinada hoja es el producto de todas las probabilidades de los nodos intermedios, y la probabilidad de llegar a cualquiera de las hojas "verdes" es simplemente la suma, ya que son eventos independientes. Por lo tanto,
$$ P_{Code\,is\,guessed} = \frac{1}{1000} + (\frac{\cancel{999}}{1000} \cdot \frac{1}{\cancel{999}}) + (\frac{\cancel{999}}{1000} \cdot \frac{\cancel{998}}{\cancel{999}} \cdot \frac{1}{\cancel{998}}) = \frac{1}{1000} + \frac{1}{1000} + \frac{1}{1000} = \frac{3}{1000} $$
Esto se ve bien, porque es el mismo resultado. Estoy bastante seguro de que es correcto. ¿Es correcto?
Caso B: el código cambia cada vez
He intentado aplicar el mismo razonamiento al caso en el que el código cambia en cada intento fallido. Intuitivamente, el hecho de que el código cambie cada vez significa que para su segundo intento el atacante no puede restringir el rango a 999 códigos posibles, sino que tiene que considerar, de nuevo, 1000. Creo que esto corresponde a un distribución binomial donde intenta tener k = 1 aciertos en n = 3 intentos, pero ya tengo mis dudas: si adivinamos el código correcto, nos detenemos inmediatamente, pero creo que el binomio asume que hacemos 3 intentos en cualquier caso, es decir, aunque adivinemos el código correcto en el primer intento, el binomio asume que lo intentamos (y fallamos) 2 veces más.
De todos modos, con $p=\frac{1}{1000}$ , n=3, k=1, la probabilidad es
$$ P_{Code\,is\,guessed} = \binom{n}{k} \cdot p^k \cdot (1-p)^{(n-k)} = \binom{3}{1} \cdot \frac{1}{1000} \cdot (\frac{999}{1000})^{(3-1)} = 3 \cdot \frac{1}{1000} \cdot (\frac{999}{1000})^2 = 0.002994003 $$
De nuevo, para confirmar el resultado, probé a construir el árbol: 
Y en este caso,
$$ P_{Code\,is\,guessed} = \frac{1}{1000} + \frac{999}{1000} \cdot \frac{1}{1000} + (\frac{999}{1000})^2 \cdot \frac{1}{1000} = 0.002997001 $$
¡que es diferente del resultado anterior, el que obtuve usando el binomio! Esto significa que al menos uno de estos cálculos está mal (y posiblemente ambos), pero no estoy seguro de dónde está el error.
De todas formas el árbol me convence más, y como dije sospecho que el problema es que el binomio no es la opción correcta aquí, porque asume que el atacante siempre hace 3 intentos, y esto no es realista en este escenario.
Así que estas son mis preguntas:
- ¿Son correctos mis cálculos para el caso A (el código es siempre el mismo)?
- Para el caso B, estoy seguro de que hay un error. ¿Dónde está?
Incluso probé a simplificar el problema a tirar un dado intentando obtener una determinada cara, y si el resultado no es el deseado, tirar una vez más. Creo que el truco podría ser que si la primera tirada tiene éxito no tenemos que añadir la probabilidad de adivinar la segunda tirada, porque simplemente no habrá una segunda tirada. Pero, de nuevo, estoy confundido.
