September 12th, 2019

Criptografía y Ataque del cumpleaños

El ataque de cumpleaños (Birthday Attack en inglés) es un tipo de ataque criptográfico que explota las matemáticas detrás del problema de cumpleaños en la teoría de la probabilidad[1][2].
Consideremos la probabilidad de encontrar un par de personas que compartan el mismo día cumpleaños en una habitación, ignorando los años bisiestos, si hay 366 personas presentes, entonces sucede con certeza, pero ¿y si hay menos personas?. La paradoja establece que para que haya un 50% de posibilidades de que alguien en una habitación determinada comparta la misma fecha de cumpleaños, necesita 253 personas en la habitación. Sin embargo, si está buscando una probabilidad de más del 50% de que dos personas en la habitación tengan el mismo cumpleaños, solo necesita 23 personas.
Esto sucede porque las coincidencias se basan en pares. Si me elijo como un lado del par, entonces necesito un total de 253 personas para llegar al número de 253 pares. En otras palabras, soy yo combinado con otras 253 personas para formar los 253 conjuntos.
Para llevar a cabo el análisis, suponemos que los cumpleaños se distribuyen uniformemente en el conjunto 1,...,365. Para npersonas en una habitación, queremos evaluar la probabilidad de que al menos dos personas compartan el mismo día de cumpleaños. Fije el espacio de la muestra, O, que se compone de tuplas ordenadas (x1,...,xn)con xi pertenece a {1,..., 365}. Por lo tanto, |O|=365n. Ahora establezca el evento Apara que sea el conjunto de todas las tuplas (xi,...,xj)donde xi = xj para algunos distintos iy j.
Ahora consideremos Ac que consiste en tuplas donde xi != xjpara todas las iy jdistintas (el evento de que no hay ningún par de cumpleaños en el grupo). En este caso,

El código siguiente calcula las probabilidades analíticas, así como también los estima a través de la simulación de Monte Carlo. Para las soluciones numéricas, emplea dos implementaciones alternativas, matchExists1()y matchExists2(). Se presenta el error máximo entre las dos implementaciones numéricas.
Uno de los fundamentos de la criptografía moderna es la función hash criptográfica o función hash unidireccional. [3]
Definición: Una función hash es una función computacionalmente eficiente que asigna cadenas binarias de longitud arbitraria a cadenas binarias de cierta longitud fija, denominadas valores hash.
Para una función hash que genera valores hash de n-bit(por ejemplo, n=128 o160) y tiene propiedades particulares, la probabilidad de que una cadena elegida aleatoriamente se asigne a un determinado valor hash nes de 2^-n. La idea básica es que un valor hash sirve como un representante compacto de una cadena de entrada. En criptografía, una función hash hes seleccionada de tal manera que es inviable computacionalmente encontrar dos valores de entrada distintos con el mismo hash, es decir, dos entradas colisionantes xe ytal que h(x)=h(y), y que dado un valor hash específico y, es inviable computacionalmente encontrar una entrada xde tal manera queh(x)=y.
Por lo tanto, Una función hash Hlibre de colisiones es aquella para la cual no es factible computacionalmente encontrar dos mensajes xe ytales que H(x)=H(y).
Los algoritmos de hashing se usan ampliamente en firmas digitales y para integridad de los datos. En las firmas digitales, se aplica un hash a un mensaje largo (texto, archivo) y solo se firma el valor hash. A continuación, el receptor aplica la función hash al mensaje recibido y comprueba que la firma recibida es correcta para este valor hash. Esto ahorra tiempo y espacio en comparación con la firma del mensaje directamente, lo que implicaría dividir el mensaje en bloques de tamaño adecuado y firmar cada bloque individualmente.
Una segunda utilización de los algoritmos de hashing tiene relación con la integridad de datos, en este caso se calcula un valor hash de n-bits para un mensaje de entrada particular, posteriormente el receptor de esa información puede utilizar el mimo hash para comprobar que los datos del archivo no han sido modificados.
Por otra parte, una tercera aplicación de funciones hash es su utilización en protocolos que implican compromisos a priori, incluidos algunos esquemas de firma digital y protocolos de identificación.
La idea del ataque del cumpleaños esencontrar dos valores de entrada distintos con el mismo hash, análogamente, encontrar dos personas que estén de cumpleaños el mismo día[4]. Por otra parte, si, dado que un mensaje x, es computacionalmente inviable encontrar un mensaje yigual a x tal que H(x)=H(y), entonces se dice que Hes una función hash débilmente libre de colisiones.



using StatsBase, Combinatorics, Plots

matchExists1(n) = 1 - prod([k/365 for k in 365:-1:365-n+1])
matchExists2(n) = 1- factorial(365,365-big(n))/365^big(n)

function bdEvent(n)
  birthdays = rand(1:365,n)
  dayCounts = counts(birthdays, 1:365)
  return maximum(dayCounts) > 1
end

probEst(n) = sum([bdEvent(n) for i in 1:N])/N

Grid = 1:50
analyticSolution1 = [matchExists1(n) for n in Grid]
analyticSolution2 = [matchExists2(n) for n in Grid]
println("Maximum error: $(maximum(abs.(analyticSolution1 - analyticSolution2)))")

N = 10^3
mcEstimates = [probEst(n) for n in Grid]
plot(Grid,analyticSolution1,line=(:dot, 3),color=[:red], label=["Analytics Solution" "Probabilidad de colisión"])
plot!(Grid,mcEstimates, line=(:solid, 1),color=[:blue], title="Birthday Attack", legend=:topleft, label=["mc Estimate" "Probabilidad de colisión"])

xlabel!("Numero de hashing en grupo")
ylabel!("Probabilidad de Colision")
savefig("bA.png")

El programa Julia anterior[5]simula una habitación llena de npersonas, y si al menos dos personas comparten un cumpleaños, devuelve true, de lo contrario devuelve false. crea los cumpleaños de matriz de longitud n, y asigna uniforme y aleatoriamente un entero en el intervalo [1, 365] a cada índice. Los valores de esta matriz se pueden considerar como las fechas de nacimiento de personas individuales.crea los cumpleaños de matriz de longitud n, y asigna uniforme y aleatoriamente un entero en el intervalo [1, 365]a cada índice. Los valores de esta matriz se pueden considerar como las fechas de nacimiento de personas individuales, cuenta cuántas veces se produce cada cumpleaños en birthdayy asigna estos recuentos a la nueva matriz dayCounts(Si dos índices tienen el mismo valor, entonces esto representa a dos personas que tienen el mismo cumpleaños) y si al menos dos personas comparten el mismo cumpleaños, devuelve true, de lo contrario false, evalúa las estimaciones de Monte Carlo y las estimaciones analíticas y numéricas de estas probabilidades en el mismo gráfico.
julia> analyticSolution1 = [matchExists1(n) for n in Grid]
50-element Array{Float64,1}:
0.0              
0.002739726027397249
0.008204165884781345
0.016355912466550215
0.02713557369979347
⋮                
0.9547744028332994
0.9605979728794225
0.9657796093226765
0.9703735795779884
julia> analyticSolution2 = [matchExists2(n) for n in Grid]
50-element Array{BigFloat,1}:
0.0                                                                            
0.002739726027397260273972602739726027397260273972602739726027397260273972602739347
0.008204165884781384875211109026083693000562957402889848001501219741039594670671175
0.01635591246655030499952444237655423798959942624615376705902312752398995416652893
0.02713557369979358932829677725461939702532984349277126002275986037304211905237107
⋮                                                                              
0.9547744028332993405868458595468285377693911544897184628044808862488344848447519
0.9605979728794224391962109132490177397552503756924122497858217036359708662483029
0.96577960932267647458958591643818800959565580573834159775919309603452812219373
0.970373579577988399918655204368403865841718450995386150388780872183317497570465
julia> println("Maximum error: $(maximum(abs.(analyticSolution1 - analyticSolution2)))")
Maximum error: 2.461172365062727820892938546467205715971256384764337390231064159958270652057059e-16
julia> N = 10^3
1000
julia> mcEstimates = [probEst(n) for n in Grid]
50-element Array{Float64,1}:
0.0
0.004
0.014
0.019
0.028
0.949
0.958
0.964
0.965

Referencias:
[1]  «Birthday attack in Cryptography», GeeksforGeeks, 10-sep-2018. .
[2]  H. Yoni y Y. Nazarathy, Statistics with Julia: Fundamentals for Data Science, Machine Learning and Artificial Intelligence [DRAFT]. 2019.
[3]  A. J. Menezes, P. C. van Oorschot, y S. A. Vanstone, Handbook of Applied Cryptography, 5 vols. CRC Press, 1996.
[4]  J. Buchmann, Introduction to Cryptography. Springer Science & Business Media, 2004.
[5]  «Tutorial - Plots Julia». [En línea]. Disponible en: http://docs.juliaplots.org/latest/tutorial/. [Accedido: 12-sep-2019].