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

Protocolo de acotamiento de distancias basado en canales con ruido



Valeri Korjik

Sección de Comunicaciones

CINVESTAV-IPN
Av. I. P. N. 2508

07000 México, D.F., MEXICO

Fax: (52)-5747-7088,
Tel: (52)-5747-7000 ×



Guillermo Morales-Luna
Sección de Computación

CINVESTAV-IPN
Av. I. P. N. 2508

07000 México, D.F., MEXICO

Fax: (52)-5747-7002,
Tel: (52)-5747-7000 ×

[email protected]

[email protected]



Kirill Morozov

Departamento de Seguridad de Telecomunicaciones

Universidad Estatal de Telecomunicaciones
Moika 65, San Petersburgo, 191186, RUSIA
Fax: (812)-312-1078, Tel: (812)-315-8374

[email protected]

Resumen

Consideramos un protocolo de acotamiento de distancias que le permite a una parte verificadora estimar una
cota superior práctica para la distancia física a una parte corresponsal. El protocolo puede proteger contra
llamados “fraudes mafiosos” en los que una parte se identifica ante una parte verificadora utilizando terceras
partes. Otro ataque a un protocolo de acotamiento de distancias está dado por la falsificación de la distancia
real entre dos partes por medio de un corresponsal deshonesto. Para prevenir ambos tipos de fraudes, el
protocolo de acotamiento de distancias ha de poseer una primitiva de compromiso por bits (Bit Commitment).
En este artículo desarrollamos una idea tendiente a lograr tal primitiva y consecuentemente un protocolo de
acotamiento de distancias basado en la realización de canales con ruido conectando varias partes. Para esto,
derivaremos fórmulas para estimar la seguridad y la confiabilidad del protocolo de compromiso por bits y
presentaremos un algoritmo que optimiza a sus parámetros principales habiendo logrado una complejidad
mínima. Mostraremos un ejemplo para ilustrar que nuestro protocolo es, en efecto, confiable y seguro desde
el punto de vista de la teoría de la información. Finalmente discutiremos el problema relativo al
establecimiento de canales con ruido conectando varias partes.

Abstract

We consider a distance bounding protocol that enables the verifying party to determine a practical upper-
bound on the physical distance to a proving party. This protocol can protect against so called “mafia frauds”
in which a party identifies himself to a verifying party using the third party being aware of it. Another attack
on distance bounding protocol is a falsification of real distance between parties by dishonest prover. To
prevent both types of frauds the distance bounding protocol should contain Bit Commitment primitive. In this
paper we develop the idea to achieve this primitive and hence a distance bounding protocol based on making
noisy channels connecting parties. To solve this problem we derive the formulas to estimate security and
reliability of bit commitment protocol and present an algorithm that optimizes the main parameters provided
minimal complexity. An example is given to show that this protocol is indeed reliable and information-
theoretically secure. We also discuss the problem on how to establish a noisy channel connecting parties.

Palabras claves: Fraudes mafiosos, protocolo de acotamiento de distancias, primitiva de compromiso por

bits, canales con ruido, ampliación de privacidad, códigos de corrección de errores.






Introducción

Un fraude mafioso es un fraude en tiempo real que puede ser aplicado en cualquier esquema de
identificación por un corresponsal frauduento P y un verificador V , cooperantes uno con el otro.
Le permite a P convencer a un verificador honesto V de una proposición relativa a la información
secreta de un corresponsal honesto P, sin necesidad de conocer porción alguna de la información
secreta de este último. Con tal propósito, cuando P está a punto de iniciar el cumplimiento del
protocolo con V , V establece, digamos, un enlace por radio con P para enviarle toda información
que le transmita P, y P a su vez ha de enviársela a V. La misma estrategia es aplicada por P , para
enviar a V toda información que le haya enviado V , para que V se la haga llegar a P . En esencia,
V y P actúan como un único ente transparente, asentado en medio de P y V . Todo esto le permite
a P suplantar ante V la identidad de P , sin que P o V noten el fraude. En la figura 1 mostramos
esto esquemáticamente.


Figura 1: Un fraude mafioso en un esquema de identidad.

No hay métodos prácticos para prevenir fraudes mafiosos salvo por la técnica de
acotamiento de distancias. La característica principal de este protocolo es la medición de la
distancia entre V y su corresponsal P mediante un rápido intercambio de bits a través de un canal
iβ
que los conecte. Mas, para evitar falsificaciones de la distancia, P ha de enviar cada bit
)
≤α y
inmediatamente después de recibir un correspondiente bit
(
≤β deben concatenarse, alternando un bit de una con el correspondiente de la otra, y la palabra
resultante debe ser firmada por P utilizando una llave secreta propia. Presentamos este protocolo,
propuesto en [1], en la figura 2.

iα . Las secuencias de bits (

)

i

l

i

l

i

i


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


iα y la recepción del correspondiente bit

βαβαβα
1=
l

l−2 .

L2

m

l

2

1

l





Desafortunadamente existe otro ataque que puede romper este protocolo de acotamiento de
distancias y se da en una situación en la que P , quien posee su llave secreta, es deshonesto y
procura falsificar su distancia al verificador (véase la figura 3).



Figura 2: Acotamiento de distancias para prevenir fraudes mafiosos.



Las líneas gruesas marcan envíos de bits. Las punteadas marcan
recibimientos de bits. Las variables
sobrelíneas
rt es pues el verdadero
corresponden a valores falsificados.
retraso en tiempo, en tanto que
es un falso retraso en tiempo
Figura 3: Un fraude de un corresponsal deshonesto que envía bits demasiado rápido.

con

rt

sus propios bits

iβ en tiempos “correctos” antes de que arribe

Si P conociese los tiempos en los que V le enviará sus bits

iα , entonces puede proceder a
iα ,
enviarle a V
independientemente de su distancia a V . En consecuencia, el protocolo mostrado en la figura 2 está
iβ
imposibilitado de prevenir este fraude. Para resolver el problema es necesario escoger los bits
i αβ =
de manera que dependan de los bits
,
mas con esta estrategia subsiste la vulnerabilidad al ataque de fraudes mafiosos. Para evitar ambos

iα . La manera más sencilla es imponer la condición

i





tipos de fraudes imponemos la condición
K es
generada por P y V queda comprometido por ella, utilizando un esquema de compromiso
(commitment scheme}) seguro. Tal protocolo, propuesto en [1], queda esquematizado en la figura 4.

, donde la secuencia de bits

mm

lm

m⊕= αβ
i
i

,

,

2

,

1

i

Figura 4: Protocolo para prevenir ambos tipos de fraudes.

coinciden con los bits

Con la información recibida en el cuarto paso de esa figura, V verifica si acaso los bits
βα ⊕=~
im
im comprometidos por P . Si así fuera, entonces V calcula m
i
i
de igual forma a como lo hace P y verifica si la firma recibida corresponde, en efecto, a la de P
para el mensaje 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 .


Así pues, un protocolo de compromiso por bits es una componente sumamente importante
del protocolo de acotamiento de distancias que previene ambos fraudes, el de tipo “mafioso” y el de
un corresponsal deshonesto. En la sección siguiente consideraremos el caso especial de este
protocolo basado en canales con ruido.

Protocolo de compromiso por bits basado en canales con ruido

En el caso del protocolo de compromiso por bits, un corresponsal (Alberto) desea comprometerse
con una predicción
pero no quiere revelar esa predicción a un miembro de la mafia
(Marco) 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, en el caso de que Alberto fuese deshonesto, él podría romper el
protocolo de acotamiento de distancias).


1=
mmm

L2

lm

El protocolo puede instrumentarse mediante el sencillo algoritmo siguiente:



1. Benito genera una cadena aleatoria de bits R y se la envía a Alberto.
2. Alberto calcula el texto cifrado

L=
( mREc

)

,

aleatoria y la pareja

( mR

,

)

denota a la concatenación de R con m.

y se lo envía a Benito. Aquí L es una llave


Ni Benito ni Marco pueden desencriptar el mensaje
cadena m.


( mR

,

)

, así que ambos ignoran cuál es la

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

1. Alberto envía c a Benito, por medio de un canal sin ruido.
2. Benito revela la palabra comprometida m, calculada mediante la expresión (1), pues él conoce
≤ ,
l
0

x, b y c. Calcula la distancia de Hamming
'c , y si acaso
donde 0l es un cierto umbral, entonces Benito acepta m. En otro caso la rechaza.