PDF de programación - Protocolo de acotamiento de distancias basado en canales de ruido

CINVESTAV-IPN

MEXICO

PROTOCOLO DE

ACOTAMIENTO DE DISTANCIAS
BASADO EN CANALES CON RUIDO

Valeri Korjik

Sección de Comunicaciones.
CINVESTAV-IPN., MEXICO.

[email protected]

Guillermo Morales-Luna

Sección de Computación.

CINVESTAV-IPN., MEXICO

[email protected]

Kirill Morozov

Departamento de Seguridad de Telecomunicaciones

Universidad Estatal de Telecomunicaciones. San Petersburgo, RUSIA

[email protected]

VI RECSI

K. Korjik, G. Morales, K. Morozov

INTRODUCCION

CINVESTAV-IPN

MEXICO

Un fraude mafioso en
un esquema de identidad

N Fraude mafioso : fraude en tiempo real aplicado en esquemas de

identificación por un corresponsal fraudulento y un verificador ,
cooperantes uno con el otro, sin necesidad de conocer porción alguna
de información secreta de ellos mismos.

V V

N Cuando P está a punto de iniciar el protocolo con , establece,
digamos, un enlace por radio con para enviarle toda información
que le transmita P, y a su vez ha de enviársela a V. La misma
estrategia es aplicada por , para enviar a toda información que le
haya enviado V , para que se la haga llegar a P .

P

P

VI RECSI

K. Korjik, G. Morales, K. Morozov

CINVESTAV-IPN

MEXICO

No hay métodos
prácticos para prevenir
fraudes mafiosos
salvo por la técnica de
acotamiento de
distancias[1].

i ≤

A partir de aquí, V puede determinar una cota superior a la distancia a P usando el mayor de los
iα
tiempos de retardo entre el envío de cada bit y la recepción del correspondiente bit de
l
vuelta, .
V aceptará este protocolo si y sólo si
P está cerca de V y la firma recibida es la correcta de P
βαβαβα
211=
para el mensaje
l
Es claro que si el esquema de firmado es seguro y P no está cerca de V , entonces un fraude
l−2
mafioso tiene una probabilidad de éxito de a lo sumo .

L2

iβ

m

.

l

VI RECSI

K. Korjik, G. Morales, K. Morozov

Otro ataque: P falsifica distancia

CINVESTAV-IPN

MEXICO

P , quien posee su llave secreta, es deshonesto y procura falsificar su distancia al verificador

rt
t
f

t =
r

es el verdadero retraso en tiempo,
es un falso retraso en tiempo

iβ

iα

iα

Si P conociese los tiempos en los que V le enviará sus bits , puede proceder a enviarle a V
sus propios bits en tiempos “correctos” antes de que arribe , sin importar su distancia a V .
En consecuencia, el protocolo mostrado NO previene este fraude. Es necesario pues escoger los
bits en función de los bits , v. gr., mas así subsiste la vulnerabilidad al ataque de
fraudes mafiosos.

i αβ =
i

iα

iβ

VI RECSI

K. Korjik, G. Morales, K. Morozov

CINVESTAV-IPN

MEXICO

m⊕= αβ
mm
,
Para evitar ambos tipos de fraudes hagamos
i
i
1 K
es generada por P y V queda comprometido por ella, utilizando un esquema de compromiso
(commitment scheme) seguro. Tal protocolo, propuesto en [1], es el siguiente:

, donde la secuencia de bits

i

,

2

,

lm

i

Con la información del cuarto paso,
βα ⊕=~
im
V verifica si acaso los bits
i
im
coinciden con los bits comprometidos
por P . Si así fuera, entonces
V calcula m de igual forma a como lo
hace P y verifica si la firma recibida
corresponde a la de P para m.
En caso afirmativo, V calcula una cota
superior de su distancia a P mediante el
máximo de los tiempos de retraso y,
finalmente,
V habrá de aceptar si y sólo si
P está cerca de V .

VI RECSI

K. Korjik, G. Morales, K. Morozov

PROTOCOLO BC SEGURO
COMPUTACIONALMENTE

CINVESTAV-IPN
MEXICO
Un protocolo de compromiso por bits (BC) es muy importante en el protocolo de acotamiento
de distancias, previene ambos fraudes: tipo “mafioso” y tipo corresponsal deshonesto.
Protocolo BC: Un corresponsal (Alberto) desea comprometerse con una predicción
1=
mmm
sino hasta algún momento posterior. El verificador (Benito), por su lado, desea asegurar
que Alberto no cambie de parecer después de que él se haya comprometido con su
predicción (pues si se le permitiera hacerlo, si Alberto fuese deshonesto, él podría romper
el protocolo de acotamiento de distancias).
El protocolo puede instrumentarse mediante el sencillo algoritmo siguiente:

pero no quiere revelar esa predicción a un miembro de la mafia (Marco)

L2

lm

Benito genera una cadena aleatoria de bits R y se la envía a Alberto.
Alberto calcula el texto cifrado y se lo envía a Benito.
L es una llave aleatoria y la pareja denota a la concatenación de R con m.

L=
( mREc
( mR
,

,
)

)

•
•

•
•

Si Alberto decide revelar su compromiso, puede realizar el protocolo siguiente:

Alberto envía la llave L a Benito.
Benito desencripta el mensaje y recupera . Habiendo recuperado m,
al comprobar que aparezca su cadena aleatoria R está verificando también la
validez de la cadena m.

( mR

)

,

VI RECSI

K. Korjik, G. Morales, K. Morozov

PROTOCOLO BC BASADO EN

CANALES CON RUIDO

CINVESTAV-IPN

MEXICO

Para mantener la seguridad del protocolo BC es necesario imponer condiciones
de cómputo limitado a Marco y a Alberto, pues de otra forma cualquiera de
Alberto o Marco podría abrir m con anticipación y falsificar su distancia, o bien
Alberto podría cambiar su compromiso y proceder a falsificar su distancia.
Aquí no introduciremos suposiciones de cómputo limitado.

p

BSC

Supongamos que Alberto y Benito se conectan mediante un canal simétrico
binario, , un canal que cambia el valor de cada bit con una probabilidad p
durante su transmisión de una parte a la otra (supondremos que hay algún otro
canal sin ruido conectando ambas partes). Seguiremos el protocolo en [2],
extendido a compromisos de cadenas de bits.

Alberto y Benito convienen en utilizar un código binario lineal
, C, con
distancia minimal de código, d. Sea el canal mediante el cual Alberto
envía mensajes a Benito.
BSC
Similarmente sea un canal simétrico entre Alberto y Marco.
'p

BSC

p

kn
),(

VI RECSI

K. Korjik, G. Morales, K. Morozov

CINVESTAV-IPN

MEXICO

Tras de una fase de inicialización, Alberto y Benito realizan el protocolo 1:

Alberto elige una palabra aleatoria , en C, y una cadena aleatoria
de n bits, b. Con ello, Alberto calcula una cadena x de l bits tal que

Cc ∈

xm

b⊕=

)(ch

•

•

•

: →Chb

}1,0{
Universal
2

donde es una función de dispersión (hash) elegida
en la clase de [3] y determinada por la cadena b. A cada
palabra de código c la transforma en una cadena de l bits, donde l es la
longitud de la cadena m con la que se ha de establecer el compromiso.

(1)

Alberto envía c a través del y le transmite a Benito, por medio
de los canales sin ruido, las palabras b y x.

p

BSC

'c
Benito conserva , b y x, donde es la versión recibida de c,
acaso corrupta por el canal ruidoso.

'c

VI RECSI

K. Korjik, G. Morales, K. Morozov

CINVESTAV-IPN

MEXICO

Si Alberto quisiese revelar su compromiso m, inicia el siguiente protocolo 2:

•
•

Alberto envía c a Benito, por medio de un canal sin ruido.
Benito revela la palabra comprometida m, calculada mediante la
expresión (1), pues él conoce x, b y c. Calcula la distancia de Hamming
d H
entre c y , y si acaso , donde es un cierto
umbral, entonces Benito acepta m. En otro caso la rechaza.

,( cc

cc
,(

d H

0l

)'

'c

)'

≤

l

0

Factores relevantes en la evaluación del protocolo:

•

cP

''c

''c

La probabilidad de una decodificación óptima correcta de m por Marco,
bh
basada en su conocimiento de C, , b, x y la función de dispersión ,
BSC
donde es la versión que él recibió de c, corrupta por el canal
'p
entre Alberto y Marco. La probabilidad queda acotada superiormente
mediante la desigualdad de Fano
l
log

−+
1(

log )

cP

(2)

≤

+

I

P
c

P
c

2

0

P
c

−
1
l
2

P
c
−
1

2

VI RECSI

K. Korjik, G. Morales, K. Morozov

CINVESTAV-IPN

MEXICO

0I

donde es la cantidad de información de Shannon que le falta a
Benito (y a Marco) sobre m dados , b, x y la función de
dispersión . El valor puede a su vez ser acotado mediante
el Teorema de Ampliación de la Privacidad [4]:

bh

0I

''c

≤

I

0

2

l

)

−−−−
trn
(
2ln

(3)

es el número de símbolos a revisar en el código C, y

−=
kn
(
=
+
n
log 1

y aquí
r
t
Marco gana con , recibido a través del canal .

es la información de Renyi [4] que

p
'
''c

−+
1(

)
)2

p

)'

BSC

'p

(

2

2

VI RECSI

K. Korjik, G. Morales, K. Morozov

CINVESTAV-IPN

MEXICO

•

•

FRP

La probabilidad de que ocurra . En esta situación,
la palabra comprometida m es falsamente rechazada por Benito,
a pesar de que Alberto ha sido honesto en su ejecución del protocolo.
Se puede ver fácilmente que puede acotarse como sigue:

0

FRP

d H

cc
,(

)'

>

l

≤

P
FR

i

n

∑

+=
l
10





n
i





i

p

1(

−

p

)

−
in



(4)

,~(
cc

c ≠~
La probabilidad de que se elija ,
d H
en un intento por cambiar su compromiso y consecuentemente en
falsificar su distancia a Benito.

FDP
. Eligiendo una tal , Alberto puede tener éxito
0

Cc ∈~
c~

tal que

)'

≤

c

l

VI RECSI