Information Technology Reference
In-Depth Information
nodes
4
(remember that the repository is a non-TTP, thus the user can be misled
into believing that a certain pair of nodes within the tree are adjacent leaves).
Example 2.
Let us suppose that we want to perform a transaction using a given
certificate. The certificate is identified by
c
target
. Using the example in Fig. 3,
let us assume that
c
target
= 16. Notice that
c
target
∈
Φ
but suppose that a
P
malicious repository provides us the
ath for a couple of nodes claiming that
they are adjacent, for instance
c
minor
= 8 and
c
major
= 19. If we only check
that
Φ
, we will think that
c
target
is valid and we will perform
the fraudulent transaction.
{
c
minor
,c
major
}∈
Next, the authors propose a recursive algorithm that given a certain couple
of
TreePath
s, verifies if, actually, they belong to “real” adjacent leaves. The
algorithm works without adding any extra information to the protocol or the
data structures. The alleged adjacent leaves are denoted by
N
0
,j
and
N
0
,j
+1
.
1. The client computes
H
1
,m
and
H
1
,n
which denote respectively the crypto-
graphic values of the fathers of
N
0
,j
and
N
0
,j
+1
.
2. If
H
1
,m
=
H
1
,n
, then both leaves have the same father. Then,
(a) If
N
0
,j
=
N
1
,m
.left
and
N
0
,j
+1
=
N
1
,m
.middle
, then
they are adjacent
nodes
.
(b) If
N
0
,j
=
N
1
,m
.middle
and
N
0
,j
+1
=
N
1
,m
.right
, then
they are adja-
cent nodes
.
(c) Else,
they are not adjacent nodes
.
3. If
H
1
,m
=
H
1
,n
, then both leaves do not have the same father. Then,
(a) If
N
1
,m
has “2” children and
N
0
,j
=
N
1
,m
.middle
, then
they are not
adjacent nodes
.
(b) If
N
1
,m
has “3” children and
N
0
,j
=
N
1
,m
.right
, then
they are not
adjacent nodes
.
(c) If
N
0
,j
+1
=
N
1
,n
.left
, then
they are not adjacent nodes
.
(d) Else computes
H
2
,p
and
H
2
,q
, which denote respectively the crypto-
graphic values of the fathers of
N
1
,m
and
N
1
,n
, and applies the algorithm
recursively. In the last instance, the root is the unique common father
between the pair of nodes.
We illustrate a couple of examples of the previous algorithm in Fig. 6.
Remark 3.
It must be pointed that the strength of the previous algorithm resides
in the position that a certain node occupies relative to its father, in other words,
if a certain node LEFT, MIDDLE or RIGHT. Notice that the end user can
trust this information since the relative node positions can not be swapped by
a malicious repository because we use a non-commutative hash function. If the
malicious repository modifies the concatenation order, then it changes the next
cryptographic value (6)
H
i
+1
,k
=
h
(
H
i,j
|
H
i,j
+1
)
=
h
(
H
i,j
+1
|
H
i,j
)
.
(6)
4
This issue was not addressed in the original AD proposal.
