Language selection

Search

Patent 2462384 Summary

Third-party information liability

Some of the information on this Web page has been provided by external sources. The Government of Canada is not responsible for the accuracy, reliability or currency of the information supplied by external sources. Users wishing to rely upon this information should consult directly with the source of the information. Content provided by external sources is not subject to official languages, privacy and accessibility requirements.

Claims and Abstract availability

Any discrepancies in the text and image of the Claims and Abstract are due to differing posting times. Text of the Claims and Abstract are posted:

  • At the time the application is open to public inspection;
  • At the time of issue of the patent (grant).
(12) Patent Application: (11) CA 2462384
(54) English Title: A KEY AGREEMENT PROTOCOL BASED ON NETWORK DYNAMICS
(54) French Title: PROTOCOLE D'ECHANGE DE CLE FONDE SUR LA DYNAMIQUE D'UN RESEAU
Status: Dead
Bibliographic Data
(51) International Patent Classification (IPC):
  • H04L 9/08 (2006.01)
(72) Inventors :
  • BRUEN, AIDEN (Canada)
  • FORCINITO, MARIO (Canada)
  • WEHLAU, DAVID (Canada)
(73) Owners :
  • NON-ELEPHANT ENCRYPTION SYSTEMS (BARBADOS) INC. (Barbados)
(71) Applicants :
  • NON-ELEPHANT ENCRYPTION SYSTEMS (BARBADOS) INC. (Barbados)
(74) Agent: GOWLING LAFLEUR HENDERSON LLP
(74) Associate agent:
(45) Issued:
(86) PCT Filing Date: 2002-09-20
(87) Open to Public Inspection: 2003-03-27
Availability of licence: N/A
(25) Language of filing: English

Patent Cooperation Treaty (PCT): Yes
(86) PCT Filing Number: PCT/IE2002/000135
(87) International Publication Number: WO2003/026197
(85) National Entry: 2004-03-19

(30) Application Priority Data:
Application No. Country/Territory Date
S2001/0842 Ireland 2001-09-20
2002/0742 Ireland 2002-09-13

Abstracts

English Abstract




Published without an Abstract


French Abstract

Publié sans précis

Claims

Note: Claims are shown in the official language in which they were submitted.



We claim:

A method of generating an unconditionally secure cryptographic key between a
first
and a second cryptographic station A and B, said method comprising the steps
of:
a) in said first and second station A and B, constructing, in a pre-arranged
way
from an independently recorded measurement of a given physical phenomena,
a first and second correlated string L A, L B each of a given length N (i.e.,
said
first and second string L A, L B constructed such that the corresponding
statistical variables are not independent) of digits selected from a finite
alphabet;
b) in said first and second station A and B, applying a predetermined
permutation
g = g N to L A, L B to obtain a first and second permuted string g(L A) and
g(L B),
wherein g = g H is a pre-determined permutation and then expressing g(L A),
g(LB) as a pre-determined concatenation U1(=S A), U2, ... ,U m and
V1(=S B), V2, ... ,V m' respectively wherein S A is a substring of said first
permuted string g(L A), S B is a substring of said second permuted string g(L
B),
and the length of U i equals the length of V i for 1 <= i <= m;
c) evaluating recursively P (S A,S B) = P i (S A,S B) wherein l = ¦S A¦ = ¦S
B¦ is the
common length of S A and S B, and P is a function defined on certain ordered
pairs (U,V) of strings U, V having a common length s= ¦U¦ = ¦V¦, said
evaluating step further comprising the substeps of;
(i) in said first station A, transmitting to said second station B, the
computed value .GAMMA.(S A), of a predetermined function .GAMMA. on S A,
wherein .GAMMA.
is a function mapping strings to strings that maps the null string to the
null string having the property that for strings X,Y with ¦X¦ = ¦Y¦,
.GAMMA.(X) = .GAMMA.(Y)- and transmitting said value to station B;
(ii) in said second station B, transmitting to said first station A the digit
1 if
.GAMMA.(S A) is equal to the computed value .GAMMA.(S B) and the digit 0
otherwise;
(iii) in said first and second station A and B, respectively, calculating
strings f(S A), f(S B) wherein f is a pre-assigned function mapping strings
to strings that maps the null string to the null string, maps all strings of
length one to the null string and is such that for any string X the length
of f(X) is less than or equal to the length of X and having the property
that for strings X,Y with ¦X¦ = ¦Y¦, ¦f(X)¦ = ¦f(Y)¦;
(iv) in said first and second station A and B, setting
P l (S A,S B) = (f(S A),f(S B)) in the case when .GAMMA.(S A) = .GAMMA.(S B);
(v) when .GAMMA.(S A) .noteq. .GAMMA.(S B), performing the substeps of:
a. in said first station A, writing f(S A) as a concatenation M A N A
of strings M A, N A. having .lambda. = ¦N A¦ =1/2 t or 1/2 t + 1/2 (when t is
even or
odd respectively) where t is the common length of f(S A), f(S B),
b. in said second station B, writing f(S B) as a concatenation M B N B
of strings M B, N B having .lambda.= ¦N A¦ = ¦N B¦ ;
(vi) in said first station A, transmitting .GAMMA.(N A) to said second station
B;
(vii) in said second station B, transmitting to said first station A the digit
1 if
.GAMMA.(N A) = .GAMMA.(N B) and the digit 0 otherwise;
(viii) setting P l (S A,S B) = (X 1,Y 1) in the case when .GAMMA.(N A) =
.GAMMA.(N B) wherein
X1 is a concatenation of the first component of P t-.lambda.(M A,M B) with the


15




string f(N A) and Y1 is a concatenation of the second component of P T-
.lambda.
(M A, M B) with f(N B);
(ix) setting P l(S A,S B) = (X2,Y2) in the case when .GAMMA.(N A) .noteq.
.GAMMA.(N B), where X2
is a concatenation of M A with the first component of P .lambda.(N A, N B) and
Y2
is the concatenation of M B with the second component of P.lambda.(N A,N B).
(x) recursively calculating P .lambda.(N A,N B), (or P t-.lambda.,(M A,M B))
by repetition of
sub-steps (i) to (ix) with S A=N A , S B=N B (or S A=M A, S B=M B) thereby
obtaining P l (S A,S B).
d) calculating successively P li (U i,V i) with l i = ¦U i¦=¦V i¦ by repeating
step (c) with
S A = U i, S B = V i and then concatenating W1, W2, W3, ... W m to construct a
first concatenated string K A in said station A where W 1 is the first
component
of the pair P l (U1,V1) = P l (S A,S B) and W i is the first component of the
pair
P i (U i,V i), 2 <=< i <= m ;
e) calculating successively P li (U i,V i) with l i= ¦U i¦=¦V i¦ by repeating
step (c) with
S A = U i, S B = V i and then concatenating the strings Z1, Z2, Z3, ... Z m to
construct a second concatenated string K B of length n in said station B where
Z1 is the second component of the pair P l (U i,V i) = P~ (S A,S B) and Z i is
the
second component of the pair P l (U i,V i), with l i = ¦U i¦=¦V i¦, 2 <=
i <= m;
f) from ¦K A¦=¦K B¦ calculating a bit correlation x = x(K A,K B) from a pre-
determined formula using the length n = ¦K A¦= ¦K B¦ wherein K B is replaced
by a
Boolean complement K B* (obtained by replacing 1 and 0 in K B by 0 and 1
respectively) whenever the bit correlation between K A and K B is less than
0.5,
yielding x > 0.5;
g) determining whether x(K A,K B) satisfies a pre-determined stopping
inequality
S;
h) repeating steps (b) to (g) with L A = K A, L B = K B in the case that S is
not
satisfied;
i) otherwise in the event that inequality S is satisfied, performing the
substeps of;
(i) evaluating C(K A) in said first station A where C is a pre-determined
hash function defined on all non-null strings;
(ii) in said first station A, transmitting C(K A) to said second station B;
(iii) evaluating C(K B) in said second station B;
(iv) in said second station B, transmitting to said first station A a digit 1
if
C(K B)= C(K A) and a digit 0 otherwise;
j) in the event that C(K A) = C(K B), constructing A(K A) = A(K B), an
unconditionally secure cryptographic key shared by said first and second
cryptographic stations A and B, wherein A is a pre-determined hash function
that eliminates all of an eavesdropper's potential information; and
k) repeating steps (b) to (j) in the event that C(K A) ~ C(K B), wherein L A =
K A and
L B = K B, respectively.

2) A method of generating an unconditionally secure cryptographic key between
a first
and second cryptographic station A and B according to claim 1, wherein step a)
further
comprises the substeps of:
a.1) respectively providing said first and second station A and B a first
secret string
R1 and a second secret string R2, R1 and R2 being correlated (i.e., the
statistical
variables corresponding to R1 and R2 are not independent) and having the same
length; and

16




a.2) respectively replacing said first and second string LA and LB with said
first and
second secret string R1and R2.
3) A method of generating an unconditionally secure cryptographic key between
a first
and second cryptographic station A and B, said method comprising the method of
claim 2,
wherein said secret strings R1 and R2 are obtained from the bounded storage
model (of Maurer
and Rabin).
4) The method of claim 1, wherein said predetermined hash function C of step
i) is the
syndrome of a binary linear code of minimum distance d wherein d is some
predetermined
positive integer.
5) The method of claim 1, wherein step a) further comprises the substeps of:
a. l ) in said first and second station A and B, respectively concatenating a
generated
first and second random string RA and RB with said first and second string LA
and LB to result in a first and second concatenated string LARA and LBRB; and
a.2) in said first and second station A and B, respectively substituting said
first
concatenated string LARA for said first string LA and said second concatenated
string LBRB for said second string LB.
6) The method of claim 2, wherein the strings R1 and R2 are replaced by the
concatenated strings R1 Rp,, R2 RB respectively wherein RA is a random string
generated in
station A and RB is a random string generated in station B with RA and RB
having the same
length.
7) The method of claim 1, wherein step a) further comprises the substep of in
said first
and second station A and B, respectively, replacing said first and second
string LA and LB
with the dot product modulo 2 of a generated first and second random binary
string RA and RB
with said first and second string LA and LB to form a first and second dot
product string
LA~RA and LB~RB, wherein RA and RB are generated random binary strings having
the same
length as LA and LB, respectively.
8) The method of claim 2, wherein the strings R1 and R2 are replaced by the
strings
R1~RA, R2 ~RB, respectively, wherein RA is a random string generated in
station A and RB is a
random string generated in station B with RA and RB having the same length as
R1 and R2,
respectively.
9) A method of generating a first and second string U and V in first and
second station
A and B, respectively, said first and second string U and V having a
predetermined bit
correlation x0, 0.5 < x0 < 1, said method comprising the steps of
i. conducting steps a) to f) of claim 1 to construct a first and second string
KA
and KB having bit correlation x > 0.5;
ii. if x < x0, repeatedly conducting steps a) to f) of claim 1 until the bit
correlation
x = x (KA,KB) is greater than or equal to x0; and
if x > x0, replacing KA, KB by a first and second concatenated string U = RAKA
and V = RBKB, respectively, wherein RA and RB is a first and second random


17




string generated in first and second station A and B, respectively, each
having
a length which ensures that the bit correlation of U and V is equal to x0_
10) A method of generating a first and second string U and V in a first and
second station
A and B, respectively, said first and second string having a predetermined bit
correlation x0 in
the range of 0 < x0 < 0.5, said method comprising the steps of:
i. constructing a third and fourth string KA, KB with bit correlation x1 = 1 -
x0
according to the method of claim 9; and
ii. replacing KB by its Boolean complement KB*, wherein said complement is
obtained by replacing 1 and 0 in KB by 0 and 1, respectively.
11 ) A method of generating a first and second string U and V in a first and
second station
A and B, respectively, said first and second string U and V having a
predetermined bit
correlation x0 in the range 0.5 < x0 < 1, said method comprising the steps of
i. conducting steps a) to f) of claim 2 to construct a first and second
concatenated
string KA and KB having bit correlation x > 0.5;
ii. if x < x0, repeatedly conducting steps a) to f) of claim 2 until the bit
correlation
x = x (K,~ KB) is greater than or equal to x0; and
iii, if x > x0 , replacing K,e,, KB by a third and fourth concatenated string
U= KA RA,
V = KB RB, respectively, where RA and RB is a first and second random string
generated in said first and second station A and B, respectively, each said
first
and second random string having a length which ensures that the bit
correlation
of U and V is equal to x0.
12) A method of predicting with arbitrarily high precision the length of an
unconditionally
secure cryptographic key generated by the method of claim 2, said method
comprising the
steps of:
i. conducting steps of a) to e) of claim 2 to create first and second
concatenated strings
KA and KB;
ii. calculating the initial bit correlation x(KA,KB); and
iii, estimating the length of an unconditionally secure cryptographic key
based on this
calculated correlation.
13) An unconditionally secure encryption method, said method comprising the
steps of:
i. generating first and second unconditionally secure keys A(KA) = A(KB)
according to
the method of claim 1; and
ii. concatenating said first and second unconditionally secure keys A(KA) and
A(KB) to
generate a one-time pad.
14) A complete cryptographic system, comprising:
a standard Kerberos configuration,
wherein a server authenticates a plurality of communicating parties and said
parties generate
an unconditionally secure cryptographic key according to the method of claim
1.
1 S) A complete cryptographic system, comprising:
an unconditionally secure key generated by claim 1; and


18



an authentication algorithm.

16) The method of claim 1, wherein all strings are binary strings.

17) The method of claim 1, wherein the function f maps a non-null string to
that same
string with the last element deleted.

18) The method of claim 1, wherein:
the alphabet is a finite abelian group G; and
the function .GAMMA. maps a string over G to the sum of the elements in the
string.

19) The method of claim 17 wherein G is the binary field and .GAMMA.maps a
string to its parity.

20) The method of claim 1, wherein the function .GAMMA. maps all strings to a
given fixed string
such that for any two strings X and Y, .GAMMA.(X) = .GAMMA.(Y).

21) The method of claim 1, wherein:
for a binary string U of length l >= 1, f(U) = parity of U; and
for a first and second substring X and Y of L A and L B, respectively,
.GAMMA.(X) = .GAMMA.(Y) such that
P l(X,Y)=(parity(X),parity(Y)).

22) The method of claim 1 wherein:
f maps a non-null string to that same string with the last element deleted;
.GAMMA. maps a binary sting to its parity; and the strings U1(=S A), U2, ...
,U m; and
V1(=S B), V2, ... ,V m all have a common length 1.

23) The method of claim 1, wherein:

all strings are over the alphabet G, wherein G is a finite abelian group;
in step a) said strings L A and L B are replaced by L A+R A,L B+R B, R A and R
B being a first and
second random string over G of the same length as L A and L B and + denoting
component-wise
addition over G.

24) The method of claim 1, wherein:
for each i, 1 <= i <= m, f and .GAMMA. are predefined on all
substrings of all iterates f(U i), f(f(U i)),
f(f(f(U i))), ... and f(V i), f(f(V i)), f(f(f(V i))), ....;
f, .GAMMA. map the null string to the null string; and
f maps all strings of length 1 to the null string.

25) The method of claim 1, wherein in step a) the physical phenomena comprises
measurement by said first station A of a plurality of message round-trip times
from said first
station A to second station B, and measurement by said second station B of a
plurality of
message round-trip times from said second station B to said first station A.


19




26) The method of claim 1, wherein in step a) the physical phenomenon
comprises a
common signal emanating from an outside transmitting source selected from at
least one of a
satellite, a group of satellites, a radio transmitter, and a group of radio
transmitters.
27) The method of claim 1, wherein S of step g) is the inequality (1-x) <
.epsilon. where s is a
pre-determined positive number.
28) The method of claim 1, wherein .lambda. is a pre-determined fraction of t,
said fraction lying
in the range between 0 and 1.
29) A method for verifying with pre-determined probability equality of a first
string S1 in
a first station A with a second string S2 in a second station B, S1 and S2
having the same
length, said method comprising the steps of
i. conducting steps a) to i) of the method of claim 2 wherein R1= S1 and R2=
S2; and
ii. conducting steps b) to f) of the method of claim 2 if C(KA) .noteq. C(KB).
30) A method for determining the correlation between a first secret string U
in a first
station A and a second secret string V in a second station B, said method
comprising the steps
of conducting steps a) through i) of the method of claim 2 wherein R1=U and
R2=V.
31 ) A method for checking the equality of a first and second key U and V in a
first and
second station A and B, respectively, comprising the steps of
obtaining said first and second key U and V, respectively, from a public key
exchange
algorithm used between said first and second; and
conducting the method of claim 28 wherein S1=U and S2=V.


20

Description

Note: Descriptions are shown in the official language in which they were submitted.



CA 02462384 2004-03-19
WO 03/026197 PCT/IE02/00135
A KEY AGREEMENT PROTOCOL BASED ON NETWORK DYNAMICS
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to cryptographic systems and more particularly
to a method
of generating an unconditionally secure cipher key based on the time
differences recorded
between two parties communicating over a noiseless public channel. Thia
Application relates
to our corresponding Application filed on the same date and entitled "Hash
Functions based on Sylvester Matrices".
2. Discussion of the Related Art
An Achilles heel of classical cryptographic systems is that secret
communication can
only take place after a key is communicated in secret over a totally secure
communication
channel. Lomonaco describes [6,7] the matter as the "Catch 22" of
cryptography, as follows.
"Catch 22. Before Alice and Bob can communicate in secret, they must first
communicate in
secret."
Lomonaco goes on to describe further difficulties involving the public key
cryptographic
systems that are currently in use. For a discussion on several other
disadvantages of the Public
Key Infrastructure (PKI) see U.S. General Accounting Office Report [9].
Let x be a common key that has been created for Alice and Bob. That is, x is a
binary
vector of length n. Then x can be used as a one-time pad, as follows. Let m be
a message that
Alice wishes to transmit to Bob: m is some binary vector that is also of
length n. Alice encodes
m as m ~ x where ~ denotes bitwise addition, i.e., exclusive OR. Thus m ~ x,
not m, is
broadcast over the public channel. Bob then decodes in exactly the same way.
Thus Bob receives
the message (m ~ x) O x, which is m, because of the properties of bitwise
addition.
Alternatively, the key x can be used in a standard symmetric key cryptosystem
such as
that of Rijndael [13] or Data Encryption Standard (DES) [14]. The idea now is
to encode m as


CA 02462384 2004-03-19
WO 03/026197 PCT/IE02/00135
denotes bitwise addition, i.e., exclusive OR. Thus m ~ x, not m, is broadcast
over the public
channel. Bob then decodes in exactly the same way. Thus Bob decodes the
message (m ~ x) ~ x,
which is m, because of the properties of bitwise addition.
Alternatively, the key x can be used in a standard symmetric key cryptosystem
such as that of
Rijndael [12] or Data Encryption Standard (DES) [13]. The idea now is to
encode m as fX(m) where
fx denotes the Rijndael permutation with the parameter x. Then, to get the
message, Bob decodes by
~'x~x(m)~ = m where gx is the inverse offx
To date, practical protocols for constructing such a common key x use for
their security
unproven mathematical assumptions concerning the complexity of various
mathematical problems
such as the factoring problem, the discrete log problem, and the Diffie-
Hellman problem. Another
serious difficulty concerning present systems involves the very long keys that
are needed for even
minimal security. In his monograph R. A. Mollin [17] points out that for
elliptic curves cryptography
an absolute minimum of 300 bits should be used for even the most modest
security requirements and
500 bits for more sensitive communication. Further, key lengths of 2048 bits
are recommended for
RSA in the same reference.
In [20] chapter 5, Julian Brown gives an example of a financial encryption
system depending
on RSA keys of 512-bit, namely the CREST system introduced in 1997 by the Bank
of England. He
quotes the noted cryptographer A. Lenstra concerning such codes as follows:
"Keys of 512 bits might
even be within the reach of cypherpunks. In principle they could crack such
numbers overnight".
Randomness in Arrival Times of Network Communications
Computer networks are very complex systems formed by the superposition of
several protocol
layers [14]. Figure 1 shows the layers in a typical network. The following
analysis of how the layers
work together serves to explain the randomness in networks.
The lowest layer connects two computers, i.e., creates a channel between them,
by some
physical means and is called the Physical Layer.
2


CA 02462384 2004-03-19
WO 03/026197 PCT/IE02/00135
The second layer removes random physical errors (called "noise") from the
channel to create
an error-free communications path from one point to another. This layer, i.e.,
the Data Link Layer, is
primarily responsible for dealing with transmission errors generated as
electrical impulses
(representing bits) as sent over a physical connection. Error detection
techniques [15] are used to
identify the transmission errors in many protocols. Once an error is detected
the protocol requests a
resend. Random errors in the Data Link Layer can be observed by noting timing
delays.
The Medium Access Layer deals with allocating and scheduling all
communications over a
single channel. In a networked environment, including the Internet, many
computers communicate
over a single channel. Bursts in packet traffic is a well-known characteristic
and is due to the
uncontrollable behavior of many individual computers communicating over a
single channel [ 16]
leading to random fluctuations in transmission times.
The Network Layer deals with routing information to create a true or virtual
connection
1 S between two computers. The routing is dependent on the variety of routing
algorithms and the load
placed on each router. These two factors makes the transmission times
fluctuate randomly.
The Transport Layer interfaces with the final Application Layer to provide an
end-to-end,
reliable, connection-oriented byte stream from sender to receiver. To do so,
the Transport Layer
provides connection establishment and connection management. The times
associated with Transport
layer activities depend on all devices in the network and the algorithms being
used. Thus,
fluctuations in transmission times in the Transport Layer also occur,
contributing to timing delays.
However, not only the network influences timing fluctuations. The transmitting
and receiving
computers have internal delays resulting from servicing network packets. Thus,
even the act of
observing the timings will also introduce random fluctuations. (See appendix B
for an analysis of the
effects of perturbations on arrival timing).
SUMMARY OF THE INVENTION
The present invention provides an efficient, practical system and method for a
key agreement
protocol based on network dynamics that has the strongest possible security,
namely, unconditional
3


CA 02462384 2004-03-19
WO 03/026197 PCT/IE02/00135
security, and that does not require any additional hardware. Previous work in
this area is either
theoretical [ 11 ] or practically infeasible due the requirement for
additional channels based on
expensive and complicated hardware such as satellites, radio transmitter
arrays and accompanying
additional computer hardware to communicate with these devices [7]. All
previous cryptographic
keys only satisfy the weaker criterion of computational security.
The present invention introduces relative time sequences based on round-trip
timings of
packets between two communicating parties. These packets form the basic
building blocks for
creating an efficient and unconditionally secure key agreement protocol that
can be used as a
replacement for current symmetric and asymmetric key cryptosystems. The
present invention is an
unconditionally secure cryptographic system and method based on ideas that can
be used in the
domain of quantum encryption [1, 5 and 20 Chapter 6].. Moreover, the present
invention for the first
time provides a cryptographic protocol that exploits fundamental results (and
their
interconnectedness) in the fields of information theory, error-correction
codes, block design and
1 S classical statistics. The system and method of ~he present invention is
computationally faster, simpler
and more secure than existing cryptosystems. In addition, due to the
unconditional security provided
by the present invention, the system and method of the present invention are
invulnerable to all
attacks from super-computers and even quantum computers. This is in sharp
contrast to all previous
protocols.
The present invention provides a protocol that uses two characteristics of
network transit time:
namely, its randomness, and the fact that, despite this, the average timing
measured by two
communicating parties will converge over a large number of repetitions. The
result is that two
correlated random variables are obtained by measuring the relative time a
packet takes to complete a
round trip with respect to a first party, Alice or A, and a round trip with
respect to a second party,
Bob or B.
In a preferred embodiment, A and B engage in rallying packets back and forth
and
calculateround-trip times individually. The packets may be used for any
additional purpose since the
contents of the packets are irrelevant. Only the round-trip times are of
interest. Figure 2 shows one
round of a relative round-trip time generator of the present invention. Figure
2 diagrammatically
describes the process.
4


CA 02462384 2004-03-19
WO 03/026197 PCT/IE02/00135
PHASE 1-Alice and Bob employ the system and method of the present invention to
construct
a permuted remnant bit string from a seguence of observed packet round-trip
times:
Alice and Bob exchange packets over a network, record round-trip times, and
each
form a bit string by concatenating a pre-arranged number of low order bits of
successive
packet round-trip times. Once sufficient bits are concatenated, the process is
stopped and
both Alice and Bob apply a pre-determined permutation to their respective
concatenated bit
strings to form permuted remnant raw keys K,, and KB, respectively of equal
lenght.
PHASE 2- Alice and Bob employ these remnant raw keys to create a reconciled
key:
Alice and Bob systematically partition their respective permuted remnant raw
keys, KA
and KB, into sub-blocks, compute, exchange and compare parities for each sub-
block, and,
discarding the low order bit of the sub-block, re-concatenate the modified sub-
blocks in their
original order. In the case of blocks with mismatched parities the partition
process is iterated
until mismatched bits are located and deleted.
PHASE 3- Alice and Bob create an unconditionally secure~ad or keX from their
common
reconciled key:
Privacy amplification to eliminate any partial information that an
eavesdropper, Eve,
might have is applied by both Alice and Bob using a pre-determined proprietary
hash function
[4] to produce a final unconditionally secure key of a pre-determined length
from the
reconciled key.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 illustrates a typical multi-layer computer network protocol.
FIG. 2 illustrates one rallying round between two communicating parties for
generating a
permuted remnant bit string by each party.
FIG. 3 illustrates mean arrival time as a function of channel noise (noise
parameter).


CA 02462384 2004-03-19
WO 03/026197 PCT/IE02/00135
DETAILED DESCRIPTION OF THE INVENTION
In a preferred embodiment, the key agreement scheme of the present invention
comprises
three phases. The first phase is construction of a permuted remnant bit string
wherein the iwo
communicating parties, Alice and Bob, rally packets back and forth recording
round-trip times.
Some of the bits may still be different after the initial bit string
construction so Alice and Bob then
participate in a second phase called Information Reconciliation. The second
phase results in Alice
and Bob holding exactly the same key. However, Eve may have partial knowledge
of the reconciled
strings, in the form of Shannon bits. Therefore, a third and final phase
called Privacy Amplification is
performed to eliminate any partial information collected by Eve.
PHASE I - Alice and Bob rally packets back and forth to generate a bit string
from truncated
round-trip timings. This string is then systematically permuted. The procedure
is as follows:
(i) Alice sends Bob a network packet and logs the time tAO.
(ii) Bob records the time of reception as tBO and responds immediately to
Alice with
another network packet.
(iii) Alice records the time of reception as tA~, and responds immediately
with a network
packet.
(iv) Bob records the time of reception as tBl and responds immediately to
Alice with
another network packet.
(v) Alice and Bob respectively calculate
etA = tA, - tAo
and
~tB = tB1 - tB0
Depending on the quality of the network connection, only some bits of OtA and
OtB are kept.
The higher order bits are dropped. Typical experimental data and criteria for
the truncation
can be found in [18].
By taking a suitable probability distribution it can be shown that the average
of OtA equals the
average of OtB.
6


CA 02462384 2004-03-19
WO 03/026197 PCT/IE02/00135
(vi) Repeat steps (i) through (v) in order to create enough bits which are
then concatenated
as a string of bits of a pre-determined length.
PHASE II - Once sufficient bits are created, the process is stopped. Alice and
Bob must now
use the relative time series to create an unconditionally secure pad or key.
One skilled in the art can
deduce, from a study of various papers in the list of references that there
are many ways to proceed.
The present invention uses an approach which, very loosely speaking, is
initially related to that of
Bennett et al.[1]. However in [3, 4 and 10], several changes and improvements
have been indicated.
These changes, based on fundamental results in algebraic coding theory,
information theory, block
design and classical statistics together achieve the following results:
(a) an a-priori bound on key-lengths;
(b) a method for estimating the initial and subsequent bit correlations and
key-lengths;
(c) a precise procedure on how to proceed optimally at each stage;
(d) a formal proof that KA converges to KB;
(e) a stopping rule;
(f) a verification procedure for equality; and
(g) a new systematic hash function for Privacy Amplification.
After PHASE I, Alice and Bob have their respective binary arrays KA and KB and
both
perform the following steps of PHASE II:
(vii) Shuffle and partition. Alice and Bob apply a permutation to KA and KB .
They then
partition the remnant raw keys into sub-blocks of length t = 4.
(viii) Parity exchange and bisective search with l = 4: Parities are computed
and exchanged
for each sub-block of length 4 by Alice and Bob. Simultaneously they discard
the bottom bit
of each sub-block so that no new information is revealed to Eve. If the
parities agree Alice
and Bob retain the three top bits of each sub-block. If the parities disagree
Alice and Bob
perform a bisective search discarding the bottom element in each sub-block
exactly as
described in [1] and [S] (see also [4]). The procedure in steps (vii) and
(viii) is denoted by
KAP4 .
(ix) Estimate Correlation From the length of the new key, we can calculate the
expected
initial bit correlation x0 between KA and KB [4]. Using xo we can calculate
the present
7


CA 02462384 2004-03-19
WO 03/026197 PCT/IE02/00135
expected correlation x = cp4( xo ).
(x) Shuffle, parity exchange, bisective search with the optimal l : To the
remnant keys KA,
KB we apply a permutation f in order to separate adjacent keys. As a non-
restrictive example,
one such f can be implemented by shuffling the bit order from (1,2,3,. . ..,n)
into the order (1, p
+1,2p+1,...,q~p+1,2,p+2,2p+2,...,q2p+2,...,p-1,2p-1,3p-1,...,qp_lp+p-l,p,
2 p, 3 p, qP p + p), where g; _ (n - i) l p.
Given the present correlation x we choose the optimal value for I = l(x) by
using the tables in
(4]. Similar to (viii), (ix) for the case l = 4, we carry out the procedure
KAP~ . From x, or
from the new common length of the remnant keys, we calculate the expected
present
correlation after KAP~ has been applied. We repeat (xi) until the stopping
condition holds.
(xi) Stopping Condition : For key length n and correlation x we have n(1-x) <
s ,a pre-
determined small positive number. We then proceed to the verification
procedure, an example
of which is as follows.
(xii) Verification Procedure : Let KA , KB both be of length n. Let t be the
smallest integer
for which 2' _< n . Construct a binary matrix M= m;;, (1 <_ i 5 t+1 , 1 <_ j
<_ 2' ) as follows:
a. The entries m;;, (1 <_ ij <_ t ) are the entries of the t x t identity
matrix I~ .
b. The (t +1 )u' row of M is the all-ones vector, that is mt+-y = 1 ( 1 <_ j
<_ 2t ).
c. Denote the top t entries in the j''' column by the binary vector v~ ( 1 <_
j <_ 2' )
Thus, vj = {m~ ~ 1 <_ i <_ t}. Then we impose the condition that the vectors
v~ are all
distinct. Thus, the set { v~ } equals the set of all 2l distinct binary
vectors of length t.
d. Denote the rows of M by Rl, R2, ..., R'+~ . Let x, y denote the remnant
keys KA,
KB written as row vectors of length n. Let x, y denote the vectors that result
when a
row of zeros of length 2'-n is adjoined, on the right of x, y respectively.
Thus
x = (x,000..0), y = (y,000..0).
e. Our verification criterion is to check that x . R; =y . R;, (1 <_ i <_ t+1
).
If the verification criterion is not satisfied we remove the first t+1 bits
from KA , KB
and repeat steps (x), (xi) and check again if the verification criterion is
satisfied.
Eventually, it will be satisfied.
At this stage Alice and Bob have confirmed that they now share the same key.
Once
confirmed, the final remnant raw key as transformed by Phase 2 is modified by
removing the first t+1 bits from KA = KB . Our new key is re-named the
'reconciled
8


CA 02462384 2004-03-19
WO 03/026197 PCT/IE02/00135
key" and phase 3, Privacy amplification is performed.
PHASE III- At this stage Alice and Bob now have a common reconciled key. In
certain cases
it is possible that the key is only partially secret to eavesdropper, Eve, in
the sense that Eve may have
some information on the reconciled key in the form of Shannon bits. Alice and
Bob now begin the
process of PrivacyAmplification that is the extraction of a final secret key
from a partially secret one
(see [1] and [2]). A well-known result of Bennett, Brassard and Robert (see
[19]) shows that Eve's
average information about the final secret key is less than 2-Slln 2 Shannon
bits as explained below
(See also Shannon [9]).
(xiii) Pn'vacy Amplification - Let the upper-bound on Eve's number of Shannon
Bits be k
and let s > 0 be some security parameter that Alice and Bob may adjust as
desired. Alice and
Bob now apply a hash function described in "Method For The Construction Of
Hash
Functions Based On Sylvester Matrices, Balanced Incomplete Block Designs And
Error-
1 S Correcting Codes", co-pending Irish Patent Application, (the entire
contents of which is
hereby included by reference as if fully set forth herein [3]) which produces
a final secret key
of length n - k- s from the reconciled key of length n.
The system and method of the present invention provide an unconditionally
secure key
agreement scheme based on network dynamics as follows. In PHASE I, Alice and
Bob permute the
bits of what remains of their respective raw keys, which keys incorporate
delay occasioned by
network noise. In PHASE II, the key from PHASE I undergoes the treatment of
Lomonaco [5]. That
is, in PHASE II Alice and Bob partition the remnant raw key into blocks of
length 1. An upper bound
on the length of the final key has been estimated and the sequence of values
of 1 that yield key lengths
arbitrarily close to this upper bound has also been estimated [4]. In PHASE
II, for each of these
blocks, Alice and Bob publicly compare overall parity checks, making sure each
time to discard the
last bit of the compared block. Each time an overall parity check does not
agree, Alice and Bob
initiate a binary search for the error, i.e., bisecting the mismatched block
into two sub-blocks,
publicly comparing the parities for each of these sub-blocks, while discarding
the bottom bit of each
sub-block. They continue their bisective search on the sub-block for which
their parities are not in
agreement. This bisective search continues until the erroneous bit is located
and deleted. They then
proceed to the next I-block..
9


CA 02462384 2004-03-19
WO 03/026197 PCT/IE02/00135
PHASE I is then repeated, i.e., a suitable permutation is chosen and applied
to obtain the
permuted remnant raw key. PHASE II is then repeated, i.e., the remnant raw key
is partitioned into
blocks of length 1, parities are compared, etc. Precise expressions for the
expected bit correlation (see
below) following each step have been obtained in [4], where it is also shown
that this correlation
converges to 1. Moreover in [4] the expected number of steps to convergence as
well as the expected
length of the reconciled key are tabulated.
The probability that corresponding bits agree in the arrays KA , KB is known
as the bit
correlation probability or, simply, as the bit correlation. It can be shown
(see [4]) that each round can
be used to increase the bit-correlation. For example, if we start with a bit-
correlation of 0.7 then after
one round with t = 3 the bit-correlation increases to about 0.77 and then to
0.87. For 1 = 2 the
corresponding numbers are 0.84 and 0.97. Estimates are also available for the
key lengths after a
round of the protocol of the present invention, for various values of 1 [4J.
The final secret key can now be used for a one-time pad to create perfect
secrecy or can be
used as a key for a symmetric key cryptosystem such as Rijndael [12] or Triple
DES [19].
A simplified version of the algorithm for the values 1= 2 and 3 is described
in Appendix A.
It will be understood by those skilled in the art, that the above-described
embodiments are but
examples from which it is possible to deviate without departing from the scope
of the invention as
defined in the appended claims.


CA 02462384 2004-03-19
WO 03/026197 PCT/IE02/00135
REFERENCE AND BIBLIOGRAPHY
The following references are hereby incorporated by reference as if fully set
forth herein.
[ 1 ] Charles Bennett, Fran~ois Bessette, Gilles Brassard, Louis Salvail, and
John Smolin,
Experimental quantum cryptography, EUROPCRYPT '90 (Arhus, Denmark),1990, pp.
253-
265.
[2] Charles H. Bennett, Gilles Brassard, and Jean-Marc Robert, Privacy
Amplification by
Public Discussion, Siam J. of Computing, 17, no.2 (1988), pp. 210-229.
[3] Aiden Bruen and David Wehlau, Method for the Construction o. f Hash
Functions Based on
Sylvester Matrices, Balanced Incomplete Block Designs, and Error-Correcting
Codes, Irish
Patent Co-pending Irish Patent Application.
[4J Aiden Bruen and David Wehlau, A Note On Bit-Reconciliation Algorithms, Non-
Elephant
Encryption Systems Technical Note Ol .xx NE2, 2001.
[5] Samuel J. Lomonaco, A guick glance at quantum cryptography, Cryptologia 23
( 1999),
no. 1, pp. 1-41.
[6] , A Rosetta Stone for Quantum Mechanics With An Introduction to Quantum
Computation, quant-ph/0007045 (2000).
[7] Ueli M. Maurer, Secret Key Agreement By Public Discussion From Common
Information,
IEEE Transactions on Information Theory 39 no.3 (1993), pp. 733-742.
[8] United States General Accounting Office, Advances and Remaining Challenges
to
Adoption of Ppublic Key Infrastructure Technology, GAO Ol -227 Report,
February 2001,
Report to the Chairman, Subcommittee on Government Efficiency, Financial
Management
and Intergovernmental Relations, Committee on Government Reform, House of
Representatives.
[9] Claude E. Shannon, Communication Theory of Secrecy Systems, Bell System
Technical
Journal 28(1949), 656-715.
[1 OJ David Wehlau, Report for Non-Elephant Encryption, Non-Elephant
Encryption
Technical Note 01.08.2001.
[ 11 ] A. D. Wyner, The Wire-Tap Channel, Bell System Technical Journal 54 no.
8(1975),
1355-1387.
[12] Joan Daemon and Vincent Rijnmeien, The Rijndael Block Cypher, June 1998,
htt~://csrc.nist.~ov/encr~tion/aes/riindael/ri'ndael.pdf
[13) Bruce Schneier, Applied Cryptography, 2°d Edition, John Wiley &
Sons, New York,
11


CA 02462384 2004-03-19
WO 03/026197 PCT/IE02/00135
1996, Chapter 12.
(14] Andrew Tanenbaum, Computer Networks, Prentice Hall, 1996.
[15] Claude E. Shannon, A Mathematical theory of Communication, Bell System
Technical
Journal 27(1948), pp. 379-423 and 623-656.
[16] Will E. Leland, Murad S. Taqq, Walter Willinger, and Daniel V. Wilson, On
the Self
Similar Nature of Ethernet Traffic, Proc. SIGCOMM (San Francisco, CA;
Deepinder P.
Sidhu, Ed.), 1993, pp. 183-193.
[17] R. A. Mollin, An Introduction to Cryptography, Chapman & Hall/CRC, 2000.
Chapter 6.
[18] Gerald Staruiala and Mario Forcinito, A Novel Application of The Entropic
Transformation Concept to Cryptography, Non-Elephant Encryption, Inc. White
Paper,
November 2000.
[ 19] Douglas R. Stinson, Cryptography: Theory and Practice, CRC Press, 1995.
[20] Julian R. Brown, The Quest for the Quantum Computer, Simon 8r. Schuster,
New York,
2001.
12


CA 02462384 2004-03-19
WO 03/026197 PCT/IE02/00135
Appendix A - Procedure for l = 2 and l = 3
Let us describe in more detail the procedures for l = 2 and 1= 3 in the
extraction of the reconciled key
described earlier.
Procedure for 1 = 2. Alice and Bob divide their bit strings KA and K$ into
pairs (a0, a~)...and (b0,
b~)... If KA and KB have odd lengths the last bit is dropped. Working on the
blocks (ag a,) and (bo,
b~) we proceed as follows.
Alice announces the parity of the block namely the number a0 + a~ (module2).
Bob compares the parity of his block. Then, if ao + al (module2) equals bo+b~
(module2) we cancel
the elements al, b1 and retain the elements a0, b0. However, if ao + a~
(module2) is different than
bo+b~ (module2) we cancel the four elements ag al, bo, bl.
Procedure for 1= 3. We divide the bit strings KA, KB into blocks of size 3
namely (ag al, a2). . .and
(bo, b~,b2)...respectively. If the size of KA is not divisible by 3 we discard
the last one or two
elements of KA and KB as appropriate. Working on each block of size 3, say the
blocks (ao, al, az)
and (b0, bl, b2) we again examine the parities and proceed as follows.
Case 1: If the parities agree, then cancel the elements a2, b2.
Case 2: If the parities disagree, then cancel the elements a2, b2 . Then, if
al= b1, we cancel both
blocks of size 3. However, if a~ ~ b1, then cancel al, b~.
As 1 increases, the number of rounds needed for convergence increases, but the
key-length will be
longer. Optimal procedures are described in [4].
13


CA 02462384 2004-03-19
WO 03/026197 PCT/IE02/00135
A~p~nd~ I~ - Pt~rbed l~t~l R~t~~I~I
r~zza~:lift;r~t;t~~. n~d~l shh~tv~ the izy. ~ ~..h~nI ~it~ ~~i~~ ~ P
t~~xtrc~rn i~txuc.l ~~ a~n tik~rrr~r ct~z~ lay ~,l~tt.~d '~n~l~r t~~~rt~u
~n~.i-
t~ac:~n.~: ~r~~i' h~~~s ~~ ~lz~ il~ili~r 1~~ ~;l~~~in~ ~ zn~rh,~aa~~ sy~G~m.
t~l»~ n>3nai~~~ ~h9 d;~ni~; ~' . n~~twc~rk_
'~'h~ ~~ ~k~ ~ f~ll~~_ A i~~ i~ r:~~~, ~~ the t~ A, ~h~
portico i~ ~riu ~.~ ~ ~t~~~.1 F~ to~~rr~ zip F3 0a ~axta~l ø~x,, ~j
B~c~ : try ~s ~t~rm:~l zu~j~~ ~r~h~ p~,~~ p~rrf~rrn. ~ ran~l~xn- u~;lk tea.
~r~~ Gh~ ~itr~n~i~l t~xt~r~rd~ B., ~hh~~~'i~~ i~t: ~c~ill r~Ih B in ;~ 8n3.:
~,n~un~ ~f
tdrzt~. 'L"6:~ ~wY,t~ t~riv.l rirz~: i~ ~.'L:xi~ 1~y ~:h~ L"~~~i~ ~.~'a:
~'x
~a~h~~r~ ~ a~ ~ "ier ~r~ ~~-~a .i~ ~ ~l~si~.n iai~~ ~i~~ ~ ~ i~ ifh~
st~r~z~!~h ~r~ ~ n. "The ;~t~,y~~an : 1 i~ ~ ~~i~rk~t~ pry x~(~) w~.iic~h
f~lc~ ~ k~r-Pi~.t~9c: ~r.~~t;~m: 1~'~ ~~ ~h~ l~t.~m fir ~.h~
-~.rril ti~$ t~' ~~3 ~axti~Z~ B
~r~~, = izif{~t ?~ ~,~~~~j ~ ,8 ~~at~ :~,(lj = :~~
~a,g i~ c'~tl~t,~ti ~nc~ ~r ~:h,e: c~ri~ina~ t~nia~l ~ø;~t~, Ch~r~ ~~r ~lz~
';x=
t~u#~3" ~~ut~ia;l r~~xj act ~ ~if~~:ae l:~tzx ~h~ i,~u~ i~ ~~t,~in~. ~l
p~x~~rl,~v~r~i~n ~f ~-.ia~: ~a.i~l i~ ~"u~r~ ~.~
~fxj ~ ~ ( ~~ ~ _ ~~
f~ j + ~ ~.~ -~- ~ -.a ~j ~ ~ t~ ~.. ~~,
~rf~,~~
~I:~j + ~' ~ x~ + .~ + ~j x ~ ~~, r. + ~~
x ~ (~: -~- ; .J
v~h~ ~ .y tlr~ .i~i~h~t; eel' the ~z~i~,l b~:rri~r ~t: ink ~ ~ [.~.,.~] ~ i~
hue'
t~~ l~~tih. r x~~hi~z rln~ ~ff~G ~f the r.~~,~,rl»~i~-xn i~. ~~r~. In the
limix
~+ t~, ~h~ ~+~riGt~rh~~~n i~ ~. ~:r~~ x~' i~ir~~tti~:~zz x~> jinx ~r.
'~~Sc~l~If~i~~lli; t~'.'~ ~~ ll~in~ ~! ~ixzz.~l~? a:~rt;~rzt,ir~~ '~c j --
~~,~..~ ~lr~u~ ~h~tt
~.rarit~z~ ~-fz~n~in~~r~~~ pith ~~~a r~tu=ta~C~e~ txnc~ ~iuc~,e i~
zz~~ n,~~~~~, ~h~ ric~i~ ,~ :..~ p ~F'i~.zr~ ~j. 'IYh~ ~;~~~i~:iOx~~ fir
whir~h ~h~
~z~lu~tic~n fr~tm ~hi,~ n~c~~l. ~:~;~. ~~ a~~~~.cl ~n ~. mmvni~,~. ~..l~n~
~:r~
t~~.tt~ ~~;iv~ly r~,rd ~,~; IY~.
14

Representative Drawing

Sorry, the representative drawing for patent document number 2462384 was not found.

Administrative Status

For a clearer understanding of the status of the application/patent presented on this page, the site Disclaimer , as well as the definitions for Patent , Administrative Status , Maintenance Fee  and Payment History  should be consulted.

Administrative Status

Title Date
Forecasted Issue Date Unavailable
(86) PCT Filing Date 2002-09-20
(87) PCT Publication Date 2003-03-27
(85) National Entry 2004-03-19
Dead Application 2007-09-20

Abandonment History

Abandonment Date Reason Reinstatement Date
2006-09-20 FAILURE TO PAY APPLICATION MAINTENANCE FEE

Payment History

Fee Type Anniversary Year Due Date Amount Paid Paid Date
Application Fee $400.00 2004-03-19
Maintenance Fee - Application - New Act 2 2004-09-20 $100.00 2004-03-19
Registration of a document - section 124 $100.00 2004-08-11
Registration of a document - section 124 $100.00 2004-08-11
Maintenance Fee - Application - New Act 3 2005-09-20 $100.00 2005-09-20
Owners on Record

Note: Records showing the ownership history in alphabetical order.

Current Owners on Record
NON-ELEPHANT ENCRYPTION SYSTEMS (BARBADOS) INC.
Past Owners on Record
BRUEN, AIDEN
FORCINITO, MARIO
WEHLAU, DAVID
Past Owners that do not appear in the "Owners on Record" listing will appear in other documentation within the application.
Documents

To view selected files, please enter reCAPTCHA code :



To view images, click a link in the Document Description column. To download the documents, select one or more checkboxes in the first column and then click the "Download Selected in PDF format (Zip Archive)" or the "Download Selected as Single PDF" button.

List of published and non-published patent-specific documents on the CPD .

If you have any difficulty accessing content, you can call the Client Service Centre at 1-866-997-1936 or send them an e-mail at CIPO Client Service Centre.


Document
Description 
Date
(yyyy-mm-dd) 
Number of pages   Size of Image (KB) 
Claims 2004-03-19 6 339
Abstract 2004-03-19 1 49
Drawings 2004-03-19 3 31
Description 2004-03-19 14 660
Cover Page 2004-05-25 1 24
Assignment 2004-08-11 8 364
Correspondence 2004-10-04 1 25
Assignment 2004-03-19 3 94
PCT 2004-03-19 3 145
Correspondence 2004-05-20 1 27
Assignment 2004-10-20 5 211