M A S A R Y K O V A U N I V E R Z I T A
F A K U L T A I N F O R M A T I K Y
Group key agreement in
Android-based mobile devices
M A S T E R ' S T H E S I S
Be. Ondřej Güttner
B r n o , S p r i n g 2014
Declaration
Hereby I declare, that this paper is m y original authorial w o r k , w h i c h I
have w o r k e d out by m y o w n . A l l sources, references and literature used or
excerpted during elaboration of this w o r k are properly cited and listed i n
complete reference to the due source.
Advisor: prof. R N D r . Václav Matyáš, M . S c , P h . D .
ii
Acknowledgement
I w o u l d like to thank m y advisor prof. R N D r . Václav Matyáš, M . S c , Ph.D.,
for his valuable advice and suggestions.
iii
Abstract
This thesis deals w i t h the implementation of chosen group key agreement
protocols for Android-based mobile devices. A brief overview of this area is
provided i n order to support the protocol choice, w i t h an emphasis o n the
A n d r o i d environment properties. The thesis also contains an implementation
of a randomness extractor. A n analysis and comparison to the randomness
source native to the environment are presented. Sources of entropy i n
Android-based mobile devices are investigated, and the relevant one is utilized
i n the randomness extraction process.
iv
Keywords
group key agreement, randomness extractor, A n d r o i d , entropy
Contents
1 Randomness extraction 5
1.1 Basic terms 6
1.1.1 Extractors
1.2 Important results 8
1.2.1 e-closeness to u n i f o r m distribution 8
1.2.2 Impossibility of non-seeded randomness extraction using
min-entropy source 8
1.2.3 Bounds 9
1.3 Explicit constructions 9
1.3.1 Universal families of hash functions 10
2 Group key agreement 11
2.1 Diffie-Hellman assumptions 12
2.2 On security and provability 14
2.2.1 Adversary types 14
2.2.2 Authentication 15
2.2.3 Security model 16
2.2.4 Other security goals 17
Replay attack 17
K e y compromise impact 17
2.3 Group protocol specifics 18
2.4 Overview 19
2.4.1 Ring-based protocols 19
2.4.2 Tree-based protocols 20
2.4.3 Star-based protocols 20
2.4.4 Protocols properties 20
3 Android environment 23
3.1 Architecture 23
3.2 Android security 24
3.2.1 System security 24
3.2.2 Application security 25
Permissions 25
Interprocess communication 26
1
3.3 Security provider 27
3.3.1 SecureRandom 28
3.3.2 KeyAgreement 29
4 Implementation 30
4.1 Randomness extraction in Android environment 31
4.1.1 Sources of entropy 31
4.1.2 Camera as a source of randomness 32
NIST testing 34
4.1.3 / d e v / r a n d o m utilization 35
4.1.4 Implemented randomness extractor 35
4.2 Group key agreement in Android environment 37
4.2.1 Communication channels 37
4.2.2 Choice-influencing factors 38
4.2.3 A u g o t protocol and its modifications 40
Authentication 40
K e y confirmation 42
Protocol settings 43
4.3 Application design and user interface 44
4.3.1 provider 45
4.3.2 gka 45
4.3.3 Communication services 46
4.3.4 randgkaapp 46
M a i n A c t i v i t y (Main) 47
MinEntropySourceActivity (MES) 47
RandExtractorActivity (RE) 48
LongTermKeyActivity (LTK) 48
G K A D e c i s i o n A c t i v i t y (Dec) 48
G K A M e m b e r A c t i v i t y (Mem) 49
G K A A c t i v i t y ( G K A ) 49
4.4 Security 49
4.4.1 Interprocess communication 50
Intent-using attack 50
Intent-using attack prevention 50
4.4.2 User interface and communication 51
4.4.3 Storage 51
5 Conclusion 52
A List of relevant files 59
2
Introduction
In the past few years, mobile devices have experienced a giant development
leap. Starting as feature phones able to provide telecommunication
only, they have evolved into smartphones, tablets, etc. - devices w i t h characteristics
of stored-program computers. Their internal management have
been getting more complex, until it have reached the point, w h e n w e could
describe it as a fully equipped operating system.
H a n d i n h a n d w i t h this improvement, a number of means of their use
has grown. Simple applications w i t h functionalities such as a calculator or
a buzzer were followed by more complex ones, that were able to provide
time management, perform e-banking, communicate w i t h enterprise application,
or even process electronic payments. A l l these new functionalities
demanded higher security assurance to protect the valuable information
they handle. This also induced a demand for high-quality cryptography.
Within the scope of this thesis, w e reflect this need and try to study
the problem of a particular cryptographic primitive - random secure key
shared between a group of participants. In the past, a lot of group key agreement
protocols were designed to cover this problem theoretically, w i t h n u merous
implementations. In several cases, these protocols were also regarding
mobile devices. To contribute a n e w feature, w e decided to investigate
A n d r o i d environment to implement a suitable protocol w i t h respect to the
environmental specifications.
A n d r o i d is an open source platform including an operating system,
middleware, user interface and applications. Its popularity has risen and
currently (June 2014) it has the major global market share. A s such, it is
a good target for software development, however, for malicious attacks as
well.
Speaking about cryptographic protocols, w e usually expect a certain
form of randomness to be present. For contemporary computers, their deterministic
character is typical, hence to gain some entropy and produce
perfect randomness can be harder than it seems at first sight. These tasks
are often solved by additional hardware, not suitable for the environment
of small, lightweight mobile devices. O n the other hand, w e are provided
3
w i t h a possibility of utilization of other input hardware, such as a camera
or microphone. We decided to investigate several inputs to find a reasonable
source of entropy and employ it i n a randomness extraction process to
establish the chosen group key agreement protocol.
Chapter 1 introduces the area of randomness extraction, that, w e believe,
is a good method to introduce randomness into the w o r l d of classical
computers. We mention the important terms and definitions and briefly describe
the evolution of this area. This chapter clarifies motivation for the use
of randomness extraction.
Chapter 2 introduces the area of a group key agreement ( G K A ) . We use
the G K A protocols to establish a shared session key i n a secure way. The text
mainly describes protocol concepts and properties to enable understanding
the area as a whole without being distracted by the existing explicit
constructions. A brief tabular overview of protocol representatives is given
w i t h respect to both security features and complexity issues.
In chapter 3, w e briefly introduce A n d r o i d environment, however, the
major a i m of this chapter is to discuss its security features.
The m a i n b o d y of this thesis lies i n chapter 4, w h i c h refers to the theoretical
background presented i n previous chapters, and applies it i n our target
environment. We present successively a design of randomness source,
its utilization by chosen randomness extractor, and decision about a suitable
group key agreement protocol. Further, customization of this protocol,
w i t h respect to the environment, is provided. This chapter also contains an
overview of the implemented application, incorporating all mentioned fea-
tures.
4
Chapter 1
Randomness extraction
Properties of randomized algorithms and cryptographic protocols are very
often proven under the assumption of having an access to a source of true
random data. Replacing it w i t h a data source that produces more predictable
output or, i n a worse case, w i t h a source that is influenced by
an attacker, m a y lead to the loss of these properties. N o w a d a y s , pseudorandom
number generators are broadly used as randomness providers.
Usually, they employ some computational problem, that is believed to be
hard, however, this still means they are secure only from the computational
perspective.
This need of randomness is very unfavourable, taking into account that
contemporary computers are built using deterministically behaving hardware.
Therefore, randomness itself has to be brought mostly by some additional
hardware, most likely based o n the phenomena producing output
containing some entropy. A m o n g such devices, w e can count either
purpose-built hardware measuring some physical phenomena (e.g. thermal
noise, photo-electric effect) or input devices, intended originally for user
interaction, utilized i n this way. Fortunately, mobile devices offer a w i d e
range of hardware that belongs into the latter category.
The output of a randomness source often contains only a limited amount
of entropy. The exact (lower) limit should be determined for every source to
inform us about h o w m u c h of the original information w e can use i n practice.
Also, the overall properties of the source need to be examined, w i t h
the a i m to design an algorithm producing true randomness from the source
output. This is, i n fact, a point where w e employ randomness extractors.
This chapter has introductory character into the area of randomness extractors
i n order to clarify the given terms. Presented results were chosen
according to the contribution for our thesis. For a more extensive overview,
the reader is referred to [33,32].
5
1. R A N D O M N E S S E X T R A C T I O N
1.1 Basic terms
In this section, w e define basic terms related to randomness extraction. Let
us denote the used notation first:
n output length of a weak r a n d o m source
k min-entropy of a weak r a n d o m source distribution
d seed length for a randomness extractor
m output length of a randomness extractor
X output distribution of a weak r a n d o m source
Y distribution of a r a n d o m seed
Um
the uniform distribution over all elements of {0, l } m
s e R S s is randomly chosen from set S
e real number from interval (0,1)
Definition 1.1. (Statistical distance) Two distributions X\, X2 over the same
domain T are e-close if for every event A C T, |X\{A) — X2(A)\ < e. We say
distribution X over {0, l } m
is e-close to uniform if it is e-close tu Um.
The previous definition presents the term of a statistical distance. Its
importance lies i n the fact that b y using it w e are able to determine a class
of the distributions that are e-close to the uniform one (to be discussed i n
section 1.2.1). We are interested i n them mostly w i t h respect to an extractor
output distribution. O n the contrary, the next term is related to the initial
distribution output from a randomness source.
Definition 1.2. (Min-entropy) Let X be a distribution. Min-entropy of X
(denoted by H^X)) is H^X) = minx£Supp(X)(-log(Pr[X = x})), where
Supp(x) denotes the set {x : Pr[X = x] > 0}.
Min-entropy helps us to determine the amount of randomness extractable
from a corresponding source. It depends entirely o n the outcome
w i t h the highest probability to occur, as opposed to the Shannon entropy1
related to the average of outcome probabilities. Therefore, using of m i n entropy
i n the definition of randomness source is natural, because it ensures
us about the worst case of the source behaviour. Regarding a source
described by its min-entropy, w e use a definition from [26] w i t h a slightly
changed notation.
Definition 1.3. (fc-source) A distribution X on {0, l } n
is called a fc-source if
#oo (X) > k.
1. Shannon entropy (denoted by H) is defined for the distribution X with Supp(X) = {x :
Pr[X = x] > 0} as H = - J2^SuPP(x) = x]log(Pr[X = x]).
6
1 . R A N D O M N E S S E X T R A C T I O N
If not mentioned explicitly, w h e n speaking about a weak r a n d o m
source, w e have i n m i n d the source described by its min-entropy, without
further assumptions o n it.
1.1.1 Extractors
Let us n o w define the basic types of randomness extractors.
Definition 1.4. (Deterministic extractor) A function E : {0,1}™ ->• {0, l } m
is
a deterministic (k, e)-extractor if for every distribution X over {0,1}™ w i t h
HOQ(X) > k the distribution E(X) is e-close to Um.
A s seen from the definition, deterministic extractors use only one initial
input - usually data produced b y a weak random source. A l t h o u g h
this is a very desirable property, it is insufficient for the use w i t h i n some
cryptographic techniques w h e n the min-entropy source output serves as
an extractor input. Still, a deterministic extractor can be useful for an arbitrary
cryptographic purpose, however, w e have to be more strict about the
source type. Such an example is v o n N e u m a n n source [39].
W h e n w e want to use the information gained from a weak r a n d o m
source meaningfully, w e have to employ another type of extractor - a
seeded one.
Definition 1.5. (Seeded extractor) A function E : {0,1}™ x {0, l}d
-> {0, l } m
is a seeded (k, e)-extractor if for every distribution X over {0,1}™ w i t h
Hoo(X) > k the distribution E(X, Y) is e-close to uniform, where Y is distributed
like Ud and is independent of X.
Difference to the deterministic extractor lies i n the use of a seed (defined
here as the distribution Y over set {0,1} w i t h length d). We can intuitively
imagine the improvement of outcome randomness properties to be caused
by an addition of r a n d o m sampling to the extraction function.
Usually, w e have an access to a weak r a n d o m source w i t h its given parameters:
source output length (which is the length of extractor's input) and
source min-entropy. We are usually able to choose the parameter of statistical
distance of the extractor output to uniform distribution, but also w e
handle this parameter as given, taking into account that it highly depends
on the use of the output randomness. In these settings, w h e n trying to optimize
the extractor, w e can proceed applying two m a i n strategies. Firstly, it
is a strategy of minimal seed length. Naturally, this one emerges from the fact
that w e have transformed the need of a r a n d o m string of some length m
into the need of random string w i t h smaller length d (extractors satisfying
7
1. R A N D O M N E S S E X T R A C T I O N
this property, namely m > d + 1, are called non-trivial). Secondly, the strategy
is the strategy of maximal output length, using w h i c h w e try to produce
as many output bits as possible.
The notion of a strong extractor brings another improvement into this
area.
Definition 1.6. (Strong extractor) A function E : {0,1}™ x {0, l } d
-> {0, l } m
is a strong (k, e)-extractor if for every X over {0, l } n
w i t h HOQ(X) > k,
Ud o V ) (where Y is distributed like Ud a n d is independent of X
and o is operation of concatenation) is e-close to uniform distribution over
{0, l}d
+m
.
The definition shows the output string again to be e-close to uniform
even if w e make the seed public, w h i c h enables a very useful feature - pregenerating
and setting the seed via a n unsecured channel.
1.2 Important results
1.2.1 e-closeness to uniform distribution
According to definitions, all the extractors have as an output a distribution
that is e-close to the uniform one. Santha a n d Vazirani [31] showed that
these two distributions are indistinguishable, w h e n serving as a n input for
many cryptographic techniques, if e is exponentially small.
1.2.2 Impossibility of non-seeded randomness extraction using
min-entropy source
Another big contribution of [31] was a proof of the impossibility of r a n d o m
data generation using deterministic randomness extractor w i t h an input
taken from source w i t h min-entropy H00(X) < n — 1. Santha and Vazirani
originally used a more restricted class of sources, w h i c h is a proper subclass
of the min-entropy sources class.
Intuition behind the proof is as follows: We have a deterministic extractor
E : {0,1}™ —> {0,1} taking input from the source w i t h the output distribution
X over {0,1}™ and w i t h very h i g h min-entropy H00(X) = n — 1 a n d
outputting a single bit. Without the loss of generality, such a n extractor, has
to produce a fixed bit from set of size at least 2 n _ 1
. Then, there is a source
w i t h mentioned min-entropy and outcomes uniformly distributed over the
sample set producing given bit (as the min-entropy, hence the set size, is
2 n _ 1
) . Therefore, the deterministic extractor w i t h the input taken from the
8
1 . R A N D O M N E S S E X T R A C T I O N
given source has its output fixed to the given bit and produces no randomness
at all.
1.2.3 Bounds
We have mentioned the two m a i n strategies for extractor optimization and
we are naturally interested i n bounds that they are limited by. These bounds
were given i n [28] a n d for a non-trivial extractor w i t h e < \ are as follows:
A m i n i m a l seed length d for successful randomness extraction is log(n—k) +
2 log (\)+O (1). A maximal output length m given the seed length equals k+
d—21og(i)+0(l), w h i c h yields a n entropy loss 2 log(^) — O ( l ) . The entropy
loss denotes the difference between the amount of input randomness (k + d)
and output randomness (m).
It is important to mention that these bounds were proven b y a probabilistic
method a n d not b y a n explicit construction of a certain extractor.
The extractor construction is a w i d e l y researched area b y itself.
Taking into account the strong extractor w e are not able to reach the
same optimal output length k + d — 2 log(^) — O ( l ) . This is obvious, since
according to the definition the output has to be independent o n the seed
of length d. The basic intuition is, then, lower our expectations to m = k —
21og(i) — O ( l ) , w h i c h is actually achievable b y a n explicit construction of
a strong extractor (as seen i n the following section).
1.3 Explicit constructions
We have p r o v i d e d the restricting bounds for randomness extraction. The
next step is find a construction/algorithm that is able to achieve these
bounds. Efficient computability is set to be the determining factor of an
explicit extractor definition.
Definition 1.7. (Explicit extractor) For functions k(n), e(n), d(n), m(n) a
family E = En of functions E : {0,1}™ x {0, l } d
^ -> {0, l } m
^ is a n explicit
(k, e)-extractor if E can be computed i n p o l y n o m i a l time w i t h respect to n
and for every n, En is a (k(n), e(n))-extractor.
A vast number of extractor constructions have been proposed so far.
One of the most important breakthrough is the notion of block-wise source
[35], that enables a rapid decrease of the seed length. Another one is the
Trevisan's extractor [38] that leads to comparison a n d partial u n i o n of the
notions of randomness extraction a n d pseudo-random generation. For the
9
1. R A N D O M N E S S E X T R A C T I O N
purposes of our thesis, w e have decided to describe yet another notion universal
families of hash functions into more detail.
1.3.1 U n i v e r s a l families of hash functions
A very simple, yet powerful, explicit extractor comes from the beginnings
of area exploration a n d uses the notion of a universal family of hash func-
tions:
Definition 1.8. (Universal family of hash functions) A collection H of functions
h : {0,1}™ —> {0, l } m
is a (pairwise independent) universal family of
hash functions if for any x\,x2 G {0,1}™, a n d for any w\ ^ w2 € {0, l } m
,
Prh&RH[h(Xl) = W l n h{x2) = w2] = 2~2m
.
Impagliazzo, L e v i n and L u b y [16] proposed a type of an extractor based
on universal families of hash functions as the first i n the following manner.
Theorem 1.1. Let X be a probability distribution over {0, l } n
with min-entropy
Hoo(X) > k, H = {h\h : {0,1}™ -> {0, l}k
~2e
} be a universal family of hash
functions. Let x be chosenfrom {0,1}™ according to X and h ER H. Then function
E(x, h) = h(x) is a strong (k, 2~e
) randomness extractor.
A s for the real application, w e need to extract randomness repeatedly.
Thus, w e are interested i n text [35] that, among others, proposed the possibility
of reusing the seed.
Theorem 1.2. Let X be a probability distribution on {0,1}™ with H00(X) > k,
H = {h\h : {0,1}™ —> {0, l}k
~2e
} be a universal family of hash functions and
i 6 N A 0 < i < I, where I is a number of extraction repetitions. Let Xi be chosen
from {0, l } n
according to X and h ER H. Then for all ifunction E(xi, h) = h(xi)
is a strong (k, I2~e
) randomness extractor.
We should point out two very useful facts. Firstly, the seed h is chosen
at random, but only once, a n d then, it can be used repeatedly. Secondly,
supposing the output distribution has given the statistical distance to the
uniform one, a number of repetitions influence the output length only log-
arithmically.
In the previous section, w e mention the possibility of achieving a n u p per
b o u n d of strong randomness extraction given an input of length n a n d
min-entropy k, seed length d a n d statistical distance e: m = k — 2 log(^) —
0(1). N o w , w e can compare it to the last presented extractor, that uses the
seed repeatedly R i m e s , to find out, that it outputs k — 2 log(^) — 2 log(/).
10
Chapter 2
Group key agreement
Consider the following situation; a group of participants wants to establish
a shared cryptographic key among them. The key is going to be used for
the message encryption and decryption, therefore, it has to be established
in a secret way, so as no other party learns anything about it, while a n i n secure
communication channel is used. We can solve this problem i n a few
different ways.
The first one achieves the key establishment b y distributing a cryptographic
key chosen by some party (trusted third party, one or more participants)
to all participants. This type is referred to as key distribution and from
our point of view, it suffers from a few imperfections. If the group relies
on a trusted third party to produce the key, then it is not self-reliant, while
self-reliance can be, i n some settings, one of the most wanted properties.
Moreover, if the key is produced b y one (or more) of the participants, the
rest of the group does not have any direct influence o n it. This way, they
cannot be implicitly assured about the key freshness (i.e. the key was never
used before) and unpredictability.
By forcing every participant to a d d its contribution to the resulting key,
we get a scheme of key agreement. The advantage of allowing every participant
to influence the resulting key, is p a i d b y higher computational complexity
for each participant and higher communication complexity overall.
The key agreement is usually implemented as a protocol between more parties
and is defined i n [23] i n the following way.
Definition 2.1. (Key agreement protocol) The key agreement protocol or
mechanism is a technique to make a shared secret available to two or more
parties, i n w h i c h the shared secret is derived b y each of these as a function
of information contributed by, or associated w i t h each of these. It means
that no party can predetermine the resulting value.
A different terms are often used, according to the number of parties
taking part i n the protocol. In the case of two parties, w e may encounter
the term key exchange. If more than two parties occur, the technique m a y
11
2 . G R O U P K E Y A G R E E M E N T
be referred to as a group key agreement. Throughout this chapter w e use the
following notation:
n number of group key agreement participants
Pi protocol participant for 1 < i < n
A , B honest participants of the protocol
C dishonest participant, attacker
G finite cyclic group
9 generator of G
V large safe prime (a prime of format p = 2q + 1, where q is also
prime)
2.1 Diffie-Hellman assumptions
F r o m the theoretical perspective, major breakthrough into this area was
due to Diffie-Hellman's seminal paper [13]. They proposed a mechanism
referred to as public key distribution system that was equal to key agreement
protocol for two parties. The initial idea was make use of finite multiplicative
group of integers i n a w a y that hides the secret transmitted over an
insecure channel. Figure 2.1 describes the Diffie-Hellman protocol.
The protocol utilizes the assumption that the computational problem
of retrieval of a secret h i d d e n by modular exponentiation i n a finite cyclic
group m o d u l o prime number is hard - polynomial-time reducible to discrete
logarithm p r o b l e m 1
. It was originally left open by Diffie and H e l l m a n ,
w i t h the proof proposed later i n [5] for primes p w i t h totient of p — 1 having
only sufficiently small prime factors. Later i n [22] the proof was proposed
for any cyclic group, assuming the existence of smooth numbers i n short
intervals. Basically, this means such groups exist and we are able to utilize
them i n an explicit protocol instance.
This initial problem was later named a Computational Diffie-Hellman
(CDH) problem, to distinguish it from its subsequent modifications. Namely,
Boneh [6] proposed a Decisional Diffie-Hellman (DDH) problem. It is useful to
define assumptions on non-existence of efficient solution for these prob-
lems.
Definition 2.2. ( C D H assumption) Let g be a generator of a finite cyclic
group G and x,y G (0, |G| — 1) be chosen at random. The group G satisfies
1. Discrete logarithm problem for cyclic group G (of size \G\) with generator g can be defined
as finding x G (0, \G\ — 1} given G, g and y G (0, \G\ — 1} such that y = gx
. It is
assumed to be NP-hard, although, no proofs have been given until now.
1 2
2. G R O U P K E Y A G R E E M E N T
the Computational Diffie-Hellman ( C D H ) assumption if there is no probabilistic
polynomial algorithm A able to find gxy
given gx
,gy
6 G.
Definition 2.3. ( D D H assumption) Let g be a generator of a finite cyclic
group G a n d x,y,z G (0, |G| — 1) be chosen at random. The group G
satisfies the Decisional Diffie-Hellman ( D D H ) assumption if there is no
probabilistic polynomial algorithm A, such that \Pr[A(g,G,gx
,gy
,gz
) =
1] — Pr[A(g, G, gx
,gy
,gxy
) = 1] | is not computationally indistinguishable.
Protocol Diffie-Hellman key exchange
C O M P U T A T I O N A L E F F I C I E N C Y : Each party computes 2 modular ex-
ponentiations.
C O M M U N I C A T I O N E F F I C I E N C Y : Each party sends logp bits i n one
round.
SECURITY: The protocol is provably secure against passive adversaries
assuming discrete logarithm problem is hard.
RESULT: A and B both possess the same shared secret key K.
1. S E T U P :
a) Select and publish a prime p and a generator g of the finite cyclic
group Z*.
b) A and B choose respective random numbers a, b such that 1 <
a, b < p — 1.
2. M E S S A G E S :
a) A —>• B : ga
mod p
b) A <— B : gb
mod p
3. A C T I O N S :
a) A computes Ka = ga
mod p and sends it to B.
b) B computes = gb
mod p and sends it to A .
c) Both A a n d B computes the shared key K = gab
mod p b y
raising the received value to their secret a or 6 respectively (i.e.
K = (Ka)b
mod p = (Kb)a
mod p).
Figure 2.1: Diffie-Hellman key exchange protocol.
13
2. G R O U P K E Y A G R E E M E N T
The m a i n w i t h d r a w of the C D H - a s s u m p t i o n lies i n the fact that, although,
an adversary is not able to efficiently find the resulting key, it is
still able to predict some information about it w i t h h i g h probability. In this
sense, the D D H - a s s u m p t i o n means a proper improvement.
It should be explicitly stated that the classes of groups, i n w h i c h the
assumptions h o l d , are not equivalent. A s an example, we can provide a
multiplicative group of integers m o d u l o prime p (Z*), i n w h i c h the C D H assumption
holds, while the D D H - a s s u m p t i o n does not. D D H - a s s u m p t i o n
holds, e.g. i n a subgroup of quadratic residues i n Z * , where p = 2q + 1 and
p, q are primes.
A s we are i n this thesis interested i n group protocols w i t h all participants
forced to contribute to the resulting key, it is natural to ask about results
and assumptions o n the protocols extended i n this way. Let us present
a Group decisional Diffie-Hellman (GDH) assumption definition according to
[37]:
Definition 2.4. ( G D H assumption) Let g be a generator of a finite cyclic
group G and x\, ...,xi, z G (0, |G| — 1) be chosen at random w i t h I e N n
I > 2. The group G satisfies the G r o u p decisional Diffie-Hellman ( G D H )
assumption if there is no probabilistic polynomial algorithm A, such that
\Pr[A(g,G,g^,...,gx
',gz
) = 1] - Pr[A(g, G, g x
' < f ' , flnU **) = l]|i s not
computationally indistinguishable.
Steiner et al. [37] have proved that for the finite cyclic groups, for w h i c h
the D D H - a s s u m p t i o n holds using the Diffie-Hellman key exchange protocol,
the G D H - a s s u m p t i o n holds for a natural extension of this protocol.
In the extension, although the adversary k n o w s g^ies^ for all the
S C {xi\l < i < I}, he is unable to distinguish the resulting key g^h=iXi
from gz
, where z £ (0, |G| — 1) is chosen randomly. This last assumption is
crucial for us, as it is used i n most of the protocols we are interested in.
2.2 O n security and provability
2.2.1 Adversary types
A s we are, i n the optimal case, looking for the formal proof of security,
we have to be sure about the abilities of adversaries. The adversary (or attacker)
is a mechanism that can exhaustively use all its abilities i n a given
environment w i t h the goal to violate the security features (in our case) of
the protocol.
1 4
2. G R O U P K E Y A G R E E M E N T
So far, w e have dealt w i t h the situation i n w h i c h the adversary can
possess all the communication taking place o n the insecure communication
m e d i u m between the protocol parties. This is the naive look at the so
called passive adversary. The passive adversary is, however, a very restricting
model and it even does not contain all the possibilities of a real adversary
as a person.
An active adversary is a n extension of the passive adversary i n the sense
that it can also create, alter or remove the communication taking place o n
the insecure communication m e d i u m (with its natural restrictions). To cope
w i t h the attacks performed b y a n active adversary, w e are usually forced to
introduce an additional security mechanism, such as authentication.
2.2.2 Authentication
In the Diffie-Hellman assumptions section, a certain security level (secure
against passive adversary) of the Diffie-Hellman protocol was stated under
the given assumptions. However, the security is violated quite easily b y
changing the adversary's abilities. So far, w e assumed the adversary to be
only passive. If w e change the adversary model to the active one, w e enable
it, i n the case of D H - p r o t o c o l , to r u n a man-in-the-middle attack success-
fully.
The cause of the insecurity against the adversary, w e just mentioned, lies
in the impossibility of the D H protocol to authenticate participants, hence
to successfully determine the message originators. The authentication is,
however, i n computer science w i d e l y discussed b y itself and the results are
applicable o n key agreement protocols.
The m a i n cryptographic tool to provide authentication is a public key
cryptography. W h i l e many protocols adopt this technique implicitly, a different
insight is brought b y Katz a n d Y u n g [19]. They propose a compiler
that is able to transform any G K A protocol secure against a passive adversary
to a n authenticated G K A protocol secure against a n active adversary,
using a digital signature scheme. A communication increase, comparing to
the initial protocol, is only 0(n) i n one round overall for n being the number
of participants.
We can divide the methods of public key cryptography used for participants
authentication i n G K A protocols into two m a i n areas: certificate-based
and id-based. The certificate-based authentication method m a y implement
such mechanisms as R S A or Diffie-Hellman key pairs. It assumes that the
participants possess mutual public keys that have been pre-distributed before
the actual protocol run. The pre-distribution is either p r o v i d e d b y a
15
2. G R O U P K E Y A G R E E M E N T
trusted third party or by verifying the authenticity of a public key over a
secure channel.
The id-based authentication method improves over that by not needing
the verification/TTP o n the fly. Proposed originally by Shamir [34], it employs
the fact that w e usually k n o w the other party's identity, w h i c h is used
as a public key. To the given public key a secret key is needed to compute,
w h i c h is done by a trusted key generation center. Afterwards, it passes the
secret key to the identity holder. The design of this technique allows that the
key generation center does not have to exist any more after all the parties
have received their secret keys, and the identity holder can use the secret
key (until it has been compromised).
We w o u l d like to assess the key agreement protocols w i t h a few natural
expectations, that could not be fulfilled without the notion of authentica-
tion.
Definition 2.5. (Implicit key authentication) Let P be the set of participants
running an instance of a key agreement protocol w i t h a resulting key K. The
Implicit key authentication is the property of the key agreement protocol,
whereby every p e P is assured that no p £ P may gain an access to K
(with possible exception of identified trusted party).
Definition 2.6. (Key confirmation) Let P be the set of participants running
an instance of a key agreement protocol w i t h a resulting key K. The key
confirmation is the property of the key agreement protocol whereby every
p G P is assured that all p G P have possession of K.
Definition 2.7. (Explicit key authentication) Explicit key authentication is
the property of a key agreement protocol obtained w h e n both the implicit
key authentication and key confirmation hold.
A s the definitions speak for themselves, let us just pinpoint that the key
confirmation does not guarantee that any other party is from acquiring the
key.
2.2.3 Security model
So far, w e have mentioned the D H assumptions under w h i c h formal proofs
of security for key agreement protocols can be given. We stated this security
is achieved against a passive adversary. Later on, w e sketched the desired
properties, taking into account an active adversary.
Throughout the evolution of the key agreement protocols w e can meet
w i t h the imperfection of stating the security of protocols without giving
1 6
2. G R O U P K E Y A G R E E M E N T
a unifiable formal proof. The protocols often proposed proofs of security
against individual attacks using heuristics and a proving system that was
not transferable to other protocols. A major improvement i n this area, w i t h
respect to group of participants, was due to Bresson et al. [11] (later also
regarding dynamically changing groups [10]). Bresson et al. designed a formal
m o d e l for protocols to provide a proof of their properties.
The model determines the participants of the protocol together w i t h
their capabilities using a game-theoretical point of view. The players are
both the parties that want to behave according to the key agreement protocol
and the adversary having its o w n capabilities and goals.
Within this model, it is possible to define the security goals and attempt
to prove their achievement. The two m a i n security goals were proven;
namely the implicit key authentication and key confirmation. The shortened
description of the model could be misleading, hence the reader is referred
to the original paper.
2.2.4 Other security goals
Replay attack
While an isolated instance of a protocol can be perfectly provably secure,
we have to think about the repetition of this task. The same security goals
have to be achievable even if the adversary has knowledge of all previous
protocol runs and can employ a replay attack:
Definition 2.8. (Replay attack) The replay attack is a deception involving
the use of information from previous protocol executions.
To make a protocol secure against the replay attack newly generated
unpredictable data are often present for each protocol run.
K e y compromise impact
A l t h o u g h the m a i n security goals focus on the properties reached while the
players behave solely according to protocol rules, i n reality these rules can
be violated i n certain situations. This can lead to compromising of some of
the keys. Because of the connection to the real life situations, studying of the
impact of these compromises is very interesting, and it brings surprisingly
different results for different protocols. In the section dealing w i t h authentication
w e mentioned the utilization of the asymmetric key cryptography.
For obvious reasons it is practical to use the key pair throughout multiple
protocol instances and therefore, the key-pair is sometimes referred to as
17
2. G R O U P K E Y A G R E E M E N T
a long-term key. A question emerges about the influence of a secret key
disclosure o n the established shared keys. To this influence the notion of
perfect forward secrecy is b o u n d :
Definition 2.9. (Perfect forward secrecy) A protocol is said to fulfil perfect
forward secrecy if the compromise of a long-term key does not compromise
the past session keys, established i n protocols using the compromised longterm
key.
O n the other hand, the disclosure of the established shared key may
occur:
Definition 2.10. (Known-key attack resilience) A protocol is said to be i m mune
against a known-key attack if the compromise of past session keys
does not allow a passive adversary to compromise future session keys as
well as impersonation by an active adversary i n the future.
By C's impersonation of party B w e mean convincing another party that
the C's identity is i n fact B.
2.3 Group protocol specifics
C o m p a r i n g to the initial D H protocol for two parties, where each party
sends one message, the protocol extension to group of parties is m u c h
more complex i n both computational and communicational senses. W h i l e
the computational complexity is highly dependent o n the actual protocol,
communication complexity can be meaningfully bounded.
Becker and Wille i n [4] p r o v i d e d lower bounds o n communication complexity
for group versions of key agreement protocols. Furthermore, for
each b o u n d they explicitly stated a protocol that matches this b o u n d (or
exceeds it b y one).
To present the bounds, w e have to sketch the communication rules first.
(Single) Message sending is an obvious action - one party sends a message
to another. In the protocol the message-sending actions are connected into
rounds, where each participant can send and receive at most one message
during this round. Message broadcast refers to the situation w h e n one party
sends a message to all other parties involved i n the protocol (assuming all
communication channels exist). Broadcasting rounds are, contrary to the
simple ones, not limited by the number of messages sent and received by
one participant i n one round.
Different protocols employ different forms of message sending, h o w ever,
allowing a protocol to use broadcasting is a big step i m p l y i n g the
1 8
2 . G R O U P K E Y A G R E E M E N T
bounds to change. The bounds presented i n [4] for n-party group key agreement
follows:
• System without broadcast needs at least 2n — 2 messages to be sent i n
at least [log2 n] simple rounds.
• System enabling broadcast needs at least n message broadcasts i n 1
broadcast round (i.e. |~log2 n] simple rounds).
Another important difference of the group key agreement protocols to
protocols between only two participants is the possibility of ad hoc participant
addition or deletion. It is desirable to process such an action i n less
computationally demanding manner and, as it turned out, it is also achievable.
In [36] Steiner et al. proposed and proved security of a protocol suite
managing this specific behaviour of group protocols by extending a simple
protocol based on G D H assumption. The original protocol as such is referred
to as the initial key agreement and additional protocols as auxiliary
key agreement. The auxiliary key agreement covers both single member
(addition, exclusion) and subgroup (join, group fusion, exclusion) opera-
tions.
2.4 Overview
Another essential property of each protocol is its topology. It is mainly i m portant
w h e n deciding about a suitable protocol i n a real situation where
participants form a network w i t h its o w n topology. Equality of those two
should assure us that w e do not need additional operations (yielding larger
computational and/or communication complexity) to handle the topological
differences.
According to a topology w e can divide key agreement protocols into
three m a i n groups: ring-based, tree-based and star-based protocols.
2.4.1 Ring-based protocols
A s the name itself indicates, this protocol group works w i t h participants
forming a logical ring. This means that each participant is connected w i t h
exactly two other (left and right neighbour).
The first protocol of this type was [17] by Ingemarsson et al. Contrary to
all protocols presented i n this thesis, it does not use broadcasting.
Burmester and Desmedt [12] later presented more efficient protocol
w i t h constant number of rounds needed. This was later modified b y Katz
1 9
2. G R O U P K E Y A G R E E M E N T
and Yung [19] to perform authentication. Another improvement was accomplished
b y Dutta a n d Barua [14]. They used the Burmester-Desmedt
protocol w i t h the Katz-Yung extension a n d b y change of its design they
achieved higher efficiency.
Steiner et al. i n [37] proposed 3 unauthenticated protocols ( G D H . l ,
G D H . 2 , G D H . 3 ) based o n the G D H assumption. O n e of those protocols was
later turned into an authenticated one b y Ateniese et al. [2].
2.4.2 Tree-based protocols
Tree-based protocols assume that the participant group forms a logical tree.
Their design often uses the advantages of data cumulation i n the root
of each subtree. Becker a n d Wille [4] designed t w o protocols for a group
of 2d
participants - 2r f
-octopus a n d 2r f
-cube. They perform without use of
broadcast.
2.4.3 Star-based protocols
Star-based protocols are actually specialized tree-based protocols w i t h the
depth of a tree equal to one. The protocols often behave i n a n asymmetric
w a y w i t h the major computational a n d communication burden i n the star
center. The role of the participant i n the star centre is referred to as a leader,
the other participants are members.
We compare protocols from 3 different papers, each focusing o n a different
problem. B o y d a n d Nieto proposed i n [8] a protocol achieving very
nice complexities. O n the contrary, the protocol [9] b y Bresson a n d Catalano
can be considered inefficient, but it has a property of explicit key authentication.
A u g o t et al. proposed i n [3] a very efficient protocol w i t h both
authenticated a n d non-authenticated versions, w i t h the authenticated one
constructed using Katz-Yung compiler.
2.4.4 Protocols properties
In order to compare all the mentioned properties w i t h respect to the presented
protocols, w e provide table 2.1. A l l the protocols are based o n D D H assumption
w i t h the exception of [8], that is based o n public key encryption
and a signature scheme security assumption, and [9], that is based o n D D H
and signature scheme security assumption. [37] is explicitly stated to hold
under the assumption of G D H that has been proved to be equal to D D H
assumption.
20
2. G R O U P K E Y A G R E E M E N T
protocol top be sec PFS kk-attack key-conf
[17] Ring no passive - no [12]
Ring yes passive - no [19]
Ring yes active yes no no
[14] Ring yes active yes no no
[37] Ring yes passive - no [4]
Tree no passive - no [8]
Star yes active no no no
[9] Star yes active yes no yes
[3] non-auth Star yes passive - no [3]
auth Star yes active yes no no
Table 2.1: Representative G K A protocols and their security properties, top
- protocol topology; be - use of broadcast; sec - security against the given
adversary type; PFS - perfect forwards secrecy; kk-attack - vulnerable to the
known-key attack; key-conf- key confirmation property
The protocols that are secure only against the passive adversary do not
use any type of authentication, hence it is irrelevant to ask about their
properties w i t h respect to perfect forward secrecy and key confirmation.
It should be also stated that, although most of the protocols i n the table 2.1
are marked not to provide key confirmation, it is not a hard task to transform
any of the authenticated protocols into a protocol able to provide this
property. The transformation can be done by an addition of a final broadcast
round w i t h a signed hash of the resulting key, however, this adds notable
additional complexity.
Table 2.2 collects information about communication and computational
complexity. Rds stands for simple/broadcasting rounds according to the
use of broadcast i n a given protocol. In the case of an asymmetric protocol
behaviour, the data are stated for each participant individually. Field messages
per user are i n the form of (messages,broadcasts).
Regarding the computational complexity field the abbreviations have
the following meaning:
exp
mult
Sg, SV
e, d
modular exponentiation
modular multiplication
signature generation and verification
public key cryptography encryption and decryption
bijective m a p p i n g from a finite cyclic group G of a large prime
order q to Z *
21
2. G R O U P K E Y A G R E E M E N T
protocol rds msg per user computational complexity
[17] n — 1 ( n - 1 , 0 ) n * exp
[12] 2 (0,2) 3 * exp + ( ^ + 3p - 3) * mult
[19] 3 (0,3) 3 * exp + (*f + ^ - 3) * muZi
+ 2 * s s + (2n - 2)s„
[14] 3 (2,1) 3 * exp + (2n — 2) * mwii + 2 * s s
+ (2n - 2) * sv
[37]
G D H . 1
2(n - 1) (0,2) (i + l)*exp for participant Pi
where 0 < i < n
[37]
G D H . 2
n (0,1) (i + l)*exp for participant Pi
where 0 < i < n
[37]
G D H . 3
n+1 (0,2) 2*exp for participant Pn-i,
(n — l)*exp for participant Pn
and 4*exp for participant Pi
where 0 < i < n — 2
[4] 2d
octopus
d
(3(n - 2d
) +
2d
d, 0)
(3(n - 2d
) + 2d
d)*(mb + exp)
[4] 2d
-
cube
d (nd, 0) nd*(mb + exp)
[8] 1 leader:
(0,n + 1),
member: (0, 2)
leader: sg + (n — 1) * e, m e m ber:
Sg + d
[9] 3 (1,2) 3n * (exp + mult) + n * (sg +
Sv)
[3] n o n -
auth
2 leader: (0,1),
member: (1,0)
leader: n*(exp + mult), m e m ber:
2*exp + n*mult
[3] auth 3 leader: (0,2),
member: (1,0)
leader: n*(exp + mult) + (n —
l)*sv + sg, member: 2 * exp +
Sg + sv + n*mult
Table 2.2: Representative G K A protocols a n d their complexities.
22
Chapter 3
Android environment
N o w a d a y s , the w o r d A n d r o i d is mostly perceived as an operating system
intended for mobile devices, however, it should be seen more as a complex
platform. The operating system is just its part such as middleware, user
interface and application programs are.
A n d r o i d is developed as an open-source project by the O p e n H a n d set
Alliance, w h i c h is an association of companies w i t h the m a i n scope
of activity i n mobile devices, telecommunication, etc. This concept enables
A n d r o i d to be trusted by a number of different producers, hence it represents
the major market player, w h e n speaking about mobile devices, w i t h
79% of smartphones market share i n 2013 [1]. O n the other hand, being an
open-source project sometimes yields disintegrity between different producer
versions and may cause difficulties i n application development, or,
in worse case, i n security.
3.1 Architecture
A n d r o i d O S is based o n the customized L i n u x kernel w i t h Java A P I . The
multi-tier architecture contains the following layers (taken from the bottom
up): L i n u x kernel, libraries, A n d r o i d runtime, application framework and
applications.
Kernel provides the usual tasks such as hardware control and process
management (including interprocess communication). However, the process
management itself does not differ m u c h from the one i n a standard
L i n u x kernel (when focusing on the actions and rules), it has a completely
different philosophy. The multi-user system from L i n u x is i n A n d r o i d transformed
into an application system. Rights are transferred from a user to
application, w h i c h directly influences the rights the application's process is
executed with.
The concept of applications separation goes even further. Every application
runs w i t h i n its o w n process using its o w n virtual machine, called
23
3. A N D R O I D E N V I R O N M E N T
Dalvik V M , that was developed to replace Java V M . The replacement has
its origin i n the possibility of focusing o n the mobile device environment,
and i n licence issues. A l l i n all, each process contains D a l v i k V M , core l i braries
(to provide functionality comparable to the one provided by Java
Standard Edition) and the application itself. This all happens i n the layer of
Android runtime.
Libraries are written i n C/C++ programming language and provide
through the A n d r o i d application framework w i t h its Java A P I basic functionality,
such as Web browser engine, database library, etc. A s i d e from this
the application framework provides a rich set of classes offering advanced
functionalities through the Application Manager services. The m a i n areas
they deal w i t h are various data resources, a graphic user interface and management
of the application lifetime.
The upper layer containing applications is very w i d e i n A n d r o i d environment.
Aside from the native applications we can gain more from on-line
distribution centres w i t h Google Play being the official one. Other centres
should be handled carefully as there are numerous cases of malicious applications
distributed by them. Google Play is an on-line service provided
by Google that enables access to a w i d e range of applications and games.
A n y b o d y can register, i n exchange for a small fee, and upload his application
into the system. Subsequently, Google offers a sophisticated system of
analytic and distribution tools to make the application profiting to its publisher.
O n the other side, all users have access to evaluating tools to provide
(to some degree) a natural application filter. This open distributing system
might seem to cause security issues, but due to the security architecture it
has only a minor impact.
3.2 Android security
Thanks to many experiences w i t h operating systems i n the past, A n d r o i d
OS have been designed having security i n m i n d right from the start. This
have yielded some security features being built directly i n the OS. We have
briefly talked about this i n the previous section and we are going to examine
it into details i n this one.
3.2.1 System security
A s already mentioned, A n d r o i d is based o n a L i n u x kernel, therefore, takes
over most of its security features. However, there is one substantial difference
i n the behaviour towards the user system. Every A n d r o i d application
2 4
3. A N D R O I D E N V I R O N M E N T
is given during the installation its rights according to the chosen permis-
sions1
and is seen by the system as a n e w user (using a U n i x point of view).
W h e n starting an application, its process runs using its user ID (hence
rights) and is therefore, by default, completely separate from the other processes
- closed i n a sandbox. The same statement can be given towards the
application's files stored i n a device's internal storage. A n d r o i d uses the
Unix-like filesystem permissions and enables to the developer to explicitly
state access rights to application files.
A Unix-like interprocess communication together w i t h the same rightssystem
are also built-in.
A s i n U n i x , w e have the root permission that enables to perform any
action w i t h any object i n the system. A n d r o i d , by default, uses the root
permissions only i n its kernel and a small subset of core applications. The
system, however, does not forbid to grant the root permissions to any application.
This can be done by the owner of the device i n a quite simple
way, by unlocking the bootloader and installation of an alternate operating
system. O n the other hand, a basic protection against any person w i t h
physical access to the device involves erasing of the user data at the point,
w h e n bootloader is unlocked by an unauthorized person. Still, it is generally
possible to bypass this feature using the security holes [18], [25].
Since A n d r o i d 3.0 (released i n February 2011), the filesystem encryption
option is offered, however not set as default.
3.2.2 Application security
In this case, by application security w e actually mean two things: securing
of the application against attacks from its surrounding environment and
ensuring the application does not have the chance to cause any damage.
The former is assured mostly by the system security already described together
w i t h the Android-specific interprocess communication model. A n droid
permissions and signing of the application by the publisher (which
enables to its user to verify the application's origin and ensures h i m about
its integrity) play a major role i n the latter.
Permissions
Mobile devices contain a lot of different hardware resources that are not
needed by all applications. The same holds for functional and data resources.
The architecture of the operating system enables to assign to each
1. Application permissions are dealt with in the next subsection.
25
3. A N D R O I D E N V I R O N M E N T
application the exact permissions to manage only the resources it directly
needs.
Moreover, this assignment is done by a user i n a very transparent manner
- during an application installation. By dividing the resources into natural
groups, such as network/data connections, camera functions, or personal
data access, also an inexperienced user can decide, i n a more informed
way, about the application's true goals.
The resources the application needs are declared by its developer i n
the A n d r o i d M a n i f e s t . xml file, w h i c h is a component of the application's
source code, as additional application permissions. The principle of
least privilege, saying that an application should ask only for those permissions
it needs for its successful execution, should be committing for all developers.
A correct use of this principle throughout the whole distribution
system should ensure that users are aware of application's u n c o m m o n requirements,
hence they can prevent the threatening infections. However, a
responsible behaviour of the users is i n this case more than doubtful.
Beside the default set of A n d r o i d permissions, an application can define
a custom permission to provide its resources to other applications i n a w a y
the user can decide about.
The resources are i n a Unix-like system mapped o n files that have set its
o w n i n g group and the rights corresponding to it. A n application that has
been granted a certain permission has actually got a membership i n a relevant
group. This way, the access mechanism is preserved o n a sufficiently
low level.
Interprocess communication
Next to the Unix-based interprocess communication (IPC) mechanisms,
A n d r o i d provides its o w n solutions. The following are the mechanisms asking
for a response from another application:
• B i n d e r is a lightweight capability-based remote procedure call
mechanism.
• I n t e n t is a simple message object that can be handed off to the system
that finds an appropriate piece of code able to satisfy the intent.
O n the other end of the IPC, there are four A n d r o i d component types
represented by following Java classes. A n A n d r o i d application consists
mainly from these components (next to a classical Java code).
2 6
3. A N D R O I D E N V I R O N M E N T
• A c t i v i t y represents an application's presentation layer, i n a sense,
that it is equivalent to a single displayed screen.
• S e r v i c e is a code running i n the background, either i n its o w n or
in another application's process. It can provide an interface directly
accessible using B i n d e r .
• B r o a d c a s t R e c e i v e r is an object listening for an appropriate
I n t e n t broadcast across the whole system.
• C o n t e n t P r o v i d e r is a component designed to share data across applications.
A n application can access the data using other application's
C o n t e n t P r o v i d e r via a specified U R I , or define its o w n to
offer the same functionality.
We can set each component's policy i n A n d r o i d M a n i f e s t . xml b y a
set of simple parameters. The basic differentiation determines whether the
component is public or private, i.e. can or cannot be accessed by other applications.
This is set by the e x p o r t e d parameter i n the component's declaration.
W h e n set to t r u e the component can be accessed b y any other
component i n any application on the device. A more fine granularity can
be achieved if e x p o r t e d = f a l s e using the p e r m i s s i o n attribute. Such
a setting enables an access to the component only to applications having
the permission declared i n the component's declaration. In the case of
C o n t e n t P r o v i d e r , the permissions differs for reading and writing, natu-
rally.
The actual w a y of another application/activity invocation can be done
in multiple ways. The most obvious is a use of I n t e n t , either implicit
or explicit. A n explicit I n t e n t is a mechanism to start another component
by its fully qualified name, w h i c h is usually used for the components
in our o w n application, as we have this knowledge. A n implicit I n t e n t
is a rather more sophisticated mechanism, as it only declares an action it
wants to perform, and then asks the A n d r o i d OS for the offer of components/
applications, w h i c h can satisfy this request. Components can declare
that they are able to fulfil various actions i n A n d r o i d M a n i f e s t . xml using
< i n t e n t - f i l t e r x It is easy to design a custom action and combine
it w i t h custom permissions to provide both new functionality and security.
3.3 Security provider
Towards the cryptographic mechanisms, A n d r o i d uses the concept of a Java
Cryptographic service provider (CSP) [27]. Apart from the m a i n goal, it is
27
3. A N D R O I D E N V I R O N M E N T
designed to achieve a h i g h degree of independence between a code using
its services and the provider itself. Namely, the application does not need
to specify, to k n o w i n advance, the exact implementation. It only asks for a
specific service, such as, e.g. a hashing function. The environment i n w h i c h
the application runs usually offers multiple providers able to fulfil the request.
Moreover, these providers are prioritized w i t h respect to the mechanisms.
A system administrator is given the permission to set the priorities.
This enables to easily regain security throughout more applications, w h e n
a security flaw occurs.
There is, of course, also the possibility of asking for a response from
an appropriate provider, however this may break the principle of independence.
O n the other hand, we are able to easily implement custom CSP,
thanks to the well-defined interfaces.
First of all, every C S P has to declare a list of services it offers. These
are then implemented as an extension to Service Provider Interfaces corresponding
to engine classes. A n engine class (e.g. SecureRandom, C i p h e r ,
S i g n a t u r e , M e s s a g e D i g e s t ) is the actual code used by programmers to
deal w i t h cryptographic tasks. A provider does not have to implement all
the engine classes. W i t h respect to this thesis, actually only two of them are
relevant:
3.3.1 SecureRandom
SecureRandom engine class is used to generate random or pseudorandom
numbers. It provides methods to generate and store a wanted
number of bytes into given array ( n e x t B y t e s (byte [ ] b y t e s ) ) , to get
a wanted number of seed bytes (getSeed ( i n t number)), or to reseed
the generator by a given seed (setSeed (byte [ ] seed)).
A l t h o u g h the output gained using SecureRandom should be " r a n d o m
enough", due to the fact there are multiple implementations based o n different
entropy sources processed i n different ways, from time to time, a
violation of the randomness occurs. Analysis i n [20] showed A n d r o i d ' s
OpenSSL enabled to partially predict the output. For an application programmer
a solution of this issue was easy - an explicit reseeding of the generator
after the SecureRandom object creation. Michaelis et al. [24] analysed
four CSPs used b y A n d r o i d OS, w i t h some alarming results. E.g. for
Apache H a r m o n y provider, due to the implementation bugs, the seed space
for one call is limited to 2 6 4
elements, w h i c h is reachable using brute-force
attacks.
28
3. A N D R O I D E N V I R O N M E N T
3.3.2 KeyAgreement
KeyAgreement is used by two or more parties to agree u p o n a shared key
to use for a particular cryptographic operation.
The agreement is divided into a few steps: firstly the object is initialized
( i n i t ( ) ) w i t h the local participant key and additional protocol
parameters. Then all the key components are added, each time using
doPhase (Key key, b o o l e a n l a s t P h a s e ) method, w i t h the last
component i m p l y i n g the l a s t P h a s e parameter set to t r u e (it is set
to f a l s e otherwise). In the end, the key can be retrieved using the
g e n e r a t e S e c r e t () method.
29
Chapter 4
Implementation
O u r m a i n task was to b u i l d an application able to establish a secret shared
key using group key agreement protocol. Moreover, this application contains
a randomness extractor implementation serving as a r a n d o m input
source to the protocol. W h e n choosing the appropriate protocol and extractor,
two m a i n things were borne i n m i n d : properties of contemporary
mobile devices and properties of A n d r o i d operating system.
In our opinion, mobile devices have reached the point w h e n the computational
power is not the m a i n deciding factor from the perspective of
task duration, at least taking into account the tasks w e are dealing with. A s
a m u c h more time-consuming factor can be seen the communication itself,
w i t h complexity growing dependently o n the participants number.
Another interesting factor is a battery-consumption, returning us
slightly back into the area of computational complexity, that is, however,
this time only one of many factors. Shooting pictures or sending traffic via
Bluetooth can turn out to be m u c h more battery-exhausting then some of
the demanding cryptographic operations. A l t h o u g h our application is not
meant to r u n for a long period of time, its behaviour should contribute to
the fairness of sources' use. A s a result, both time- and battery-consumption
affects naturally the protocol choice.
The application has been developed and tested o n contemporary, more
or less, low-end devices:
• Sony XPeria Ray ST18i running A n d r o i d 4.0.4.
• H T C Desire A8181 running A n d r o i d 2.2.2.
It deals w i t h the presented security issues, profiting mainly from theoretical
security models. To provide the complex view, it is convenient to discuss
also the practical part of thing - security of its implementation, w h i c h
is done i n section 4.4.
30
4. I M P L E M E N T A T I O N
4.1 Randomness extraction in Android environment
G r o u p key agreement protocols, as many other cryptographic mechanisms,
need an input providing them w i t h sufficient amount of highquality
randomness. A recommended w a y to obtain this input is to use the
SecureRandom class that w e mention i n section 3.3.1.
Since A n d r o i d 4.2, OpenSSL is a p r i m a r y P r o v i d e r for the
SecureRandom service, w i t h /dev/urandom being the preferable source
of entropy. A n d r o i d provides both Unix-based files containing entropy:
/dev/random and /dev/urandom. The former outputs desired number
of random bits after sufficient amount of entropy has been collected, while
the latter returns them immediately, regardless o n the current entropy level,
/dev/urandom processes its entropy p o o l w i t h S H A hash function, w h i c h
in the case of insufficient entropy yields the r a n d o m properties of the output
to depend also o n the security of S H A algorithm. A l t h o u g h this makes
the service theoretically more vulnerable, efficient attack utilizing this additional
property is, at this moment, not k n o w n .
In this chapter, w e analyse potential entropy sources available through
A n d r o i d ' s Java A P I . We want to handle these sources i n a w a y that is equal
to / dev/ random - providing output once sufficient amount of entropy has
been collected. This way, w e can mutually compare them w i t h respect to
output frequency and randomness quality. The output is then utilized i n
randomness extraction, described into detail i n section 4.1.4.
4.1.1 Sources of entropy
We have investigated the A n d r o i d ' s Java A P I to find the potential entropy
sources w i t h results divisible into following categories:
Into the first category, w e can classify interfaces providing some information
about a device, such as a battery level or signal strength. These
sources are not suitable for us because of three different reasons. They do
not offer a sufficient range of values - battery level acquires integer values
i n the range 0-100, signal strength 0-99; the frequency of change is very
slow; the values are partially obtainable by an attacker (signal strength can
be obtained using a similar device w i t h the same operator i n a physically
close area, signal strength by observing the device's life cycle).
Another possible source of entropy is a touch-screen. Unfortunately, its
utilization requires a big portion of user interaction, w h i c h can be achieved
either through a longer period of time or by an informed user's on-demand
action. O u r application's character prevents from collecting data through
31
4. I M P L E M E N T A T I O N
longer period, and at the same time we do not want to force a user to perform
unnecessary additional tasks, hence w e decided not to employ this
k i n d of source.
Except the touchscreen, there are other input devices regarding contemporary
smartphones that can provide environmental noise, even without
the need of user's interaction. The two most significant ones are probably
a microphone and a camera. We chose the utilization of the camera only, as
according to [21] the microphone has a min-entropy per one sample equal
to 0.5, while this value is exceeded multiple times simply by using a single
pixel o n a camera preview frame.
Device drivers are too low-level for the scope of our thesis, as they are
not directly reachable from the Java A P I . However, native A n d r o i d ' s randomness
services use as an entropy source the Unix-based random files
/dev/random or/and /dev/urandom that utilize the mentioned l o w level
entropy sources. We use the former file, w i t h respect to the equivalence
to the designed camera randomness source, to allow comparison.
4.1.2 Camera as a source of randomness
A n d r o i d OS provides us w i t h A P I operating the camera w r a p p e d i n a
Camera object. It supplies the data stream from the camera i n a form of
preview frames, w i t h the possibility of taking a picture by an appropriate
method invocation. However, a slight complication arises from the fact that
A n d r o i d forces to successfully obtain the camera output only if there is a
preview present on the current screen (which equals the existence of an
S u r f aceView object w i t h i n the active A c t i v i t y ) . F r o m the user experience
perspective, this is not an issue, as the preview can be made almost
invisible by setting its sizes to l x l pixel. O n the other hand, it is somehow
limiting for the application's design, especially w h e n dealing w i t h w r a p ping
the utilized source into a standardized interface implementation, as i n
the case of SecureRandom.
Camera source analysis i n [21] estimates the min-entropy per pixel to
be 3.1979, 3.3277, 3.9276 for the red, green and blue components respectively,
each one being stored i n one byte (hence the optimal min-entropy
w o u l d be 8). Moreover, it mentions no (optimistic) assumptions o n the dependence
between consequent frames and neighbouring pixels. This yields
the necessity of preprocessing of the collected data, i n the case w e want to
get a source w i t h h i g h min-entropy.
We employ the preprocessing strategy designed i n [7] w h i c h we customized
i n parameters settings and applied o n A n d r o i d ' s camera preview
32
4. I M P L E M E N T A T I O N
(with sizes set to 320px times 240px). The initial strategy counts o n a preview
frame to be passed w i t h pixels stored i n 24 bits containing values of
red, green and blue components. A n d r o i d A P I provides a N V 2 1 coding as
default. It stores a l u m a component (brightness) per each pixel i n 8 bits,
together w i t h two colour components stored per each four pixels together.
This yields 12 bits per one pixel. W h e n we refer to a pixel value, from n o w
on w e have i n m i n d the 8 bit value w e get by applying a X O R operation
on the l u m a and both colour components, as all of them can contain some
entropy. Moreover, thanks to the design of preprocessing, the colour components
are never used i n the creating of a result twice. A n important parameter
is also the frequency of frames retrieval. We set this value to be 16
frames per second maximally, however, the actual value can differ depending
o n the device and its p r o v i d e d frame rates. The preprocessing process
follows:
1. Split an obtained frame into squares w i t h a side length equal to lOpx.
2. F r o m each square choose only one pixel, w i t h pixels from neighbouring
squares to be taken from different rows/columns, to prevent the
row dependence typical for camera sensor chips. Moreover, w h e n
choosing the pixel, take into consideration the inter-frame dependence,
hence choose the pixel so that it is different i n the consequent
frames (the same holds also for the colour components). Result is a
square array 32x24 bytes.
3. A p p l y the X O R operation o n the pixels from the same square column.
Result is an array of 32 bytes.
4. A p p l y the X O R operation o n multiple bytes to narrow the resulting
array.
5. A p p l y the X O R operation o n each byte to produce a single bit out of
it.
While points 1 and 2 deal w i t h a decrease of dependent relations, points
3 to 5 concentrates the contained entropy. Actually, point 4 gives us a certain
freedom of choice regarding the resulting length, by determining a number
of columns that are X O R e d together. This way, w e may obtain reasonable
output lengths 4,8,16 and 32 bits, w h e n equal number of columns is X O R e d
for each resulting byte. We have collected a big amount of samples for all
the mentioned lengths, w i t h results written i n table 4.1. The sample space
of binary strings of length 32 consists of 4,294,967,296 values, w h i c h is a
33
4. I M P L E M E N T A T I O N
number that makes an appropriate sample number infeasible to achieve
(when taking into account the actual output rate is approximately 10 frames
per second), hence w e could not estimate its min-entropy. The output data
have been collected on a device w i t h covered lens to prevent environmental
influences.
output length sample space samples collected min-entropy
4 16 1,000,000 3.990
8 256 1,000,000 7.932
16 65,536 1,000,000 14.844
32 4,294,967,296 1,000,000 Table
4.1: Outputs.
We want to emphasize, that the output min-entropy is relatively high for
all sizes. A l t h o u g h the collected samples counts are not large, an expected
behaviour can be seen, as the min-entropy decreases relatively towards the
longer outputs.
NIST testing
We have performed also the tests from the NIST test battery [30] for
(pseudo)random number generators, that assesses quality of randomness
in binary sequences. However, the output lengths have caused only some of
them can give valuable testimony. Namely, w e have performed Frequency,
Block frequency, Cumulative sums, Runs, Longest r u n of ones, Rank, Discrete
Fourier transform, Non-overlapping template matchings, A p p r o x i mate
entropy and Serial tests for 100 bitstreams of length 10,000 * I w i t h
I being the length of output from one sample, Universal statistical test for
10 bitstreams of length 100, 000 * I, and Overlapping template matchings,
Linear complexity, R a n d o m excursions and R a n d o m excursion variant tests
for 4 bitstreams of length I * 250, 000. A l l tests have r u n w i t h level of significance
a = 0.01.
For 4 bit output, all tests have successfully passed, w i t h number of passing
streams w i t h i n the acceptance range. In the case of 8 bit output, from all
tests only one out of 148 Non-overlapping templates has not passed, w i t h
94 out of 100 sequences (96 being the acceptance rate). Similar result has
been found for 16 bit output, where 3 Non-overlapping templates have not
passed w i t h 95 out of 100.
Interesting results have been found for 32-bit output. Frequency, C u mulative
sums and Runs test have not passed quite significantly, crossing
34
4 . I M P L E M E N T A T I O N
this output length out of the relevant candidates for entropy supplier.
For further use i n randomness extraction w e have chosen output length
of 4 bits, w i t h limiting the min-entropy by log2 14, from the reason it has
a very high min-entropy and the result of its NIST testing have come out
perfectly.
4.1.3 / dev/ random utilization
/dev/random file has a major drawback i n its output frequency, comparing
to /dev/urandom. A l t h o u g h the latter is also considered to be
cryptographically secure, it is not recommended to be used for a longterm
key generation. We have collected 65,536 bytes of output data from
/dev/random, mostly to provide comparison to the designed camera
source properties, w i t h following results.
A n output is produced w i t h frequency almost 30 bits per second. M i n entropy
of this source achieves 7.791 bits per 8 bit sample.
Regarding the output frequency and min-entropy, the camera entropy
source is comparable to /dev/random. The m a i n differences are the conditions
under w h i c h both of them collect randomness. W h i l e the camera
source needs to "focus" on data collecting (in a sense of visible screen w i t h
preview), /dev/random profits from the actions performed o n device that
does not have to be related w i t h the current application. F r o m this point of
view, both sources quite nicely complement each other.
4.1.4 Implemented randomness extractor
Contemporary mobile devices provide a sufficient computing power and
storage capacities relatively to the usual cryptographic primitives. This
makes us focus o n the strategy of maximal output w h e n speaking about
randomness extractors. O n the other hand, they implicitly do not have an
on-line secure access to a source of true randomness, and storing of a large
pregenerated r a n d o m sequence w o u l d be impractical i n the means of both
effectiveness and security. This implies the use of a strong extractor that
enables the seed to be reusable.
The wanted properties are reached by the explicit extractor described
in section 1.3.1. Its seed length is far away from the optimal one, w h i c h is
balanced thanks to the storage capacities and the possibility of reusing it
according to theorem 1.2. The output length reaches, i n certain settings, the
optimal value k + d — 2 log \ — 0{l). However, w e have to take into account
35
4. I M P L E M E N T A T I O N
the repetitive factor, that forces to leave out the seed of length d from the
output and subtract 2 log I, w i t h I being the number of repetitions. We get
the optimal value b y presetting the maximal number of repetitions (hence
it is constant and then 2 log I G 0(1)).
The only thing left is to set u p the parameters i n a n efficient way. We
want the output to be e = 2 - 6 4
close to the uniform distribution. The n u m ber
of repetitions 2 2 0
should be large enough w i t h only a fractional impact
on the output length comparing to the one of e. In these settings, w e loose
168 bits from the input min-entropy per each output. The preferable way,
w i t h respect to algorithm efficiency, is to choose the safe prime that determines
the input length to be as large as possible. This way, w e minimize
the impact of the constant value subtraction. O n the other hand, w e have
to have i n m i n d the very limiting nature of the utilized source. A c c o r d i n g
to us, the solution lies i n strict preservation of the wanted output lengths,
determined b y key agreement protocol's requirements. We use the first subsequent
safe primes (p) able to produce values of lengths > 32, 64,128,160,
256, 512, 1024 a n d 2048. A l t h o u g h i n same cases the efficiency is almost
ridiculous, it is still the most time- and battery-saving solution.
The actual class of hash functions serving as a n extractor has been chosen
similarly to [7]. For min-entropy input x of length n = p — 1, seed s of
length d and output of length m, extractor E : {0, l } n
x {0, l } d
—> {0, l } m
is
defined as follows: E(x, s) = ((1 o x).s) o ((1 o x).^1
) o ((1 o x).s2
) o • • • o ((1 o
x ) . s m _ 1
) , where o denotes the operation of concatenation,. the operation of
scalar product and sy
the left shift of binary string s of y positions.
target length n k m efficiency
32 227 215 47 0.141
64 263 249 81 0.243
128 347 329 161 0.369
160 347 329 161 0.461
256 467 443 275 0.548
512 719 683 515 0.712
1024 1283 1220 1052 0.798
2048 2447 2328 2160 0.837
Table 4.2: Implemented randomness extractor parameters (efficiency measured
to the target value).
The extraction design determines the equation for computation of k to
bek = (p —1)/4 * log2 14. Together w i t h the equation m = k — 2(log \ + log I)
36
4. I M P L E M E N T A T I O N
and the wanted m values, w e are able to present the input lengths (table
4.2).
4.2 Group key agreement in Android environment
In chapter 2, w e provide a brief overview of group key agreement protocol
properties, together w i t h a tabular overview of a few protocols. This
chapter focuses on the A n d r o i d environment specifics w i t h respect to the
protocols and deals w i t h an efficient protocol choice and its implementation
specifics.
4.2.1 Communication channels
A s our protocol mediates a communication between multiple devices, first,
we have to investigate the means of achieving this. A g a i n , w e are limited
by the options p r o v i d e d by A n d r o i d Java A P I .
In mobile devices, w e are able to utilize the original functionality: S M S
and M M S sending and Internet access p r o v i d e d by the newer generation
network types, such as E D G E , 3G, etc. The use of these w o u l d mean the
participants to depend on another party (service provider) i n the sense of
technological infrastructure. Moreover, it w o u l d require an additional fee
for services, w h i c h is unnecessary, hence not wanted.
Another option is to use direct connectivity interfaces. In this area, A n droid
provides us w i t h Bluetooth, W i - F i , N F C and U S B technologies.
• USB technology provides fast wired connection between two devices,
w h i c h is, however, i n our case useless. The additional equipment,
a cable, for two-side communication needs i n the case of more participating
devices another support i n a form of a mediating device
(router), as contemporary mobile devices usually does not contain
more then one U S B port.
• N F C (Near Field Communication) is a set of short-range wireless technologies,
typically requiring a distance of 4 c m or less to initiate a connection.
Since A P I level 9, an A n d r o i d Beam feature provides possibility
of device pear to pear communication. Utilization of this channel
has, i n our opinion, two m a i n drawbacks: the market penetration of
suitable devices is not o n an sufficient level, and the communication
distance is too limiting for a group of more than 2 people (they w o u l d
need to perform appropriate actions i n certain order).
37
4. I M P L E M E N T A T I O N
• Wi-Fi Direct Since A P I level 14, A n d r o i d O S includes the possibility
of using the W i - F i Direct technology to directly connect more devices
together. A c c o r d i n g to the standard, devices form a group w i t h one
device being a group owner to w h i c h all the other devices connect
forming a star topology group. This communication channel suits our
purposes well, however, the h i g h A P I level prevents it from the i m -
plementation.
• Wi-Fi access point A n d r o i d O S enables to establish a W i - F i access
point to w h i c h other devices can connect, to form a group w i t h star
topology. A l t h o u g h its A P I is m u c h less developer-friendly than W i Fi
Direct, w i t h most of the parameters (e.g. access point IP address)
hard-coded, w e are still able to obtain the IP address of a particular
mobile device to perform a socket communication. We decided to utilize
an in-advance established network of this k i n d i n our implemen-
tation.
• Bluetooth is probably the most c o m m o n additional communication
technology i n contemporary smartphones. Similarly to the W i - F i technology,
it enables to interconnect devices to form a group w i t h star
topology. W h i l e connecting, A n d r o i d provides its custom functionality
to assure security. Two interconnect, two devices have to be paired
i n advance. If they have not been previously paired, the A n d r o i d
framework w i l l automatically show a pairing request (that may i n clude
some form of visual verification) blocking the calling application,
until a decision about the pairing has been made.
4.2.2 Choice-influencing factors
In the previous section, w e discussed available communication channels
and their properties. The two channels chosen, Bluetooth and W i - F i , both
w o r k over a star topology, w h i c h determines our desired protocol from
the topology perspective. Another aspect determined b y the chosen channels
is the impact of communication complexity. Bluetooth has throughput
3 M b i t / s or 24 Mbit/s for version 2.0 or 3.0 and 4.0 respective. W i - F i
throughput strongly depends on the used standard and lies i n the range of
tens to hundreds of Mbit/s.
While few years ago applications for mobile devices were strongly l i m ited
b y computational power, nowadays, this is not the issue. Contemporary
devices w i t h processor frequency i n order of gigahertz and R A M ca-
3 8
4. I M P L E M E N T A T I O N
pacity i n order of gigabytes perform almost any cryptographic task i n real-
time.
Consider a situation w i t h a group of people, possessing mobile devices,
finding themselves physically o n one place and wanting to establish
a shared key i n a secure way. Being this our scenario, it is unwanted to
include any other party into the protocol, w h i c h yields a requirement of
independence. While this can be an issue i n the case of authenticated protocols
w i t h the authentication provided using public key cryptography, we
employ a method utilizing the physical presence of participants to bypass
it. This method is described i n section 4.2.3.
With just a brief look at the mentioned factors and representative protocols
i n table 2.2, it is clearly seen the complexities do not influence the
protocol's duration i n a w a y that is perceivable by a user. A l t h o u g h they
should not be forgotten, the m a i n deciding factors for us are the ones connected
w i t h the protocol design - topology and third party independence,
together w i t h protocol security features.
We discuss several protocols from the perspective of the mentioned i n fluencing
factors. We picked only protocols w i t h star-based topology from
our overview.
• Boyd-Nieto [8] protocol is based entirely o n public key cryptography
and does not use the Diffie-Hellman assumption i n any form. This
yields the fact it does not achieve perfect forward secrecy. Moreover, it
is inefficient i n a term of communication complexity, where all members
need to perform broadcast messaging, w h i c h evinces i n a linear
growth of messages sent and received by a group leader.
• Bresson-Catalano [9] protocol achieves all desired security properties,
including key confirmation. O n the other hand, it is m u c h less
computationally and communicationally effective, than the A u g o t
protocol. Therefore, we decided to employ only its technique for ensuring
key confirmation and use it i n a more efficient protocol. This is
a simple task, as the key confirmation technique is performed using
only one additional round at the end of a protocol.
• Augot et al. [3] protocol was designed w i t h respect to efficiency being
one of the m a i n goals. It significantly approaches the lower b o u n d for
communication complexity and enables to introduce also the authenticated
version, to provide all the desired security properties, w i t h the
exception of key confirmation (achievable using Bresson-Catalano design).
It was therefore a straight choice for our implementation.
39
4 . I M P L E M E N T A T I O N
4.2.3 Augot protocol and its modifications
We present the A u g o t et al. protocol that was introduced i n its initial paper
in both an authenticated and non-authenticated version. Throughout this
section, we use the following notation:
n number of group key agreement participants
Pi protocol participant, 1 < i < n
M subgroup of protocol participants - members
Mi particular member
L protocol leader (centre i n star topology)
Xi secret random contribution belonging to member M ,
XI secret random contribution belonging to leader
K resulting shared key
G finite cyclic group
9 generator of G
V large safe prime (a prime of format p = 2q + 1, where q is
also prime)
exp modular exponentiation
mult modular multiplication
pubki,pubk[ R S A public key belonging to member Mi, leader, respec-
tively
privi, privi R S A private key belonging to member Mi, leader, respec-
tively
random nonce belonging to member Mi, leader, respec-
tively
In the protocol design, we have applied a simple modification b y cutting
out the group formation procedures. These are presented i n the original
version to determine a group leader and to compute a group topology. We
state that i n our case this is not only unnecessary, but even unwanted. It
can induce a situation i n w h i c h the underlying channel topology does not
match the protocol one, hence cause a needless complexity growth. The
protocol initiator is therefore i n our case equivalent to the group leader.
Authentication
The authenticated version of A u g o t protocol is obtained by using KatzYung
[19] compiler w h i c h transforms any protocol secure against a passive
adversary, into a protocol secure against an active adversary. This is
achieved firstly by the addition of a first round containing all participants'
4 0
4. I M P L E M E N T A T I O N
identities together w i t h their r a n d o m nonces. Secondly, to all each consequent
message the nonces are concatenated and the aggregate is digitally
signed.
Protocol A u g o t protocol, non-authenticated
C O M P U T A T I O N A L E F F I C I E N C Y : Leader: n * (exp + mult), Member:
2 * exp + n * mult
C O M M U N I C A T I O N E F F I C I N E N C Y : Leader: 1 broadcast, Member: 1
message
SECURITY: The protocol is provably secure against passive adversaries
assuming discrete logarithm problem is hard.
RESULT: A l l participants possess identical shared secret key K.
1. S E T U P :
a) Select and publish a prime p and a generator g of the finite cyclic
group Z ; .
b) Leader and each member M« choose r a n d o m number xi, x\ respective,
such that 1 < Xi, xi < p — 1.
2. R O U N D S :
1) Each member responds to leader's initial request by its blinded
secret gXi
mod p to the leader.
2) Leader raises each member's blinded secret to its secret xi (resulting
i n gXiXl
mod p) and broadcasts them along w i t h the
original contributions to the group.
3. K E Y C A L C U L A T I O N : Each member checks its contribution is i n cluded
correctly and then removes its secret x% from gXiXl
to get gXl
.
The group key K is obtained i n the following manner:
K = gXl
* \\M gXiXl
mod p.
Naturally, the issue of public key predistribution arises i n this case. A s
we have stated, our requirement of independence prevent us from use of
any external trusted third party. This is actually the point, where the advance
of a physical presence comes i n use - w e can let the participants distribute
their public keys pubki and visibly verify them according to their
hashes i n a similar w a y as used i n [15]. Moreover, this r o u n d contains each
41
4. I M P L E M E N T A T I O N
participant's random nonce ri, to fulfil the requirements of Katz-Yung compiler.
The first round according to the figure 4.1 arranges distribution of
public keys from each member to the leader. In the second r o u n d , leader
broadcasts nonces a n d public keys of all participants. U n t i l this point, the
communication is not secured i n any way. The final r o u n d enables to verify
the received values. Each participant can visually verify all public keys'
and nonces' hash values, however, assuming honest behaviour of all participants,
only n comparison is needed, forming a "cyclic verification".
pubki\ri
pubki\ri,Vj.Mj G M : pubkj\rj
SHA-256(pubki\ri)r\fj.Mj e M : SHA-256(pub/fej|rj)
Figure 4.1: Public key predistribution protocol using visual verification.
To force any participant to obtain a n invalid public key, the potential
attacker needs to find value v, such that SHA-256(w) = SHA-256(pubki\ri),
w h i c h is believed to be infeasible i n a relevant time for contemporary computers.
The r a n d o m nonce further disables to use rainbow tables to look for
potential pubki values and prevent from impersonation i n the next instances
of protocol, if an alternative successful value v has been computed.
We make use of R S A [29] encryption system, w h e n public key cryptography
is needed. W h e n new protocol instance is invoked, its parameters are
set to determine the length of the used public key. The application checks
in its private storage, whether a key pair w i t h a n appropriate length exists.
If it does, w e use it for the purposes of the current protocol instance, otherwise
it is generated a n d stored to enable its use since. Each participant can
initiate a generation of a fresh key pair i n a n u p c o m i n g protocol instance
w h e n having a feeling the current key has been compromised, to prevent
from impersonation attack.
Complexities of a n authenticated version of A u g o t protocol are written
in table 2.2.
K e y confirmation
Inspired b y the Bresson-Catalano protocol, w e decided to implement an
additional functionality to achieve key-confirmation property. Similarly to
the mentioned protocol design, w e a d d one final round i n w h i c h all participants
broadcast a hash value H of concatenation of current protocol
instance i d pid a n d resulting shared key K. This is done i n a n authenticated
way, meaning H is sent together w i t h its signature SpriVi(H). If all
Pi <—>
Mi > Li
L —> Mi
Vis TD
rij-1
42
4. I M P L E M E N T A T I O N
the broadcasted hash values are verified against their signatures and are
equivalent, the shared key K can be pronounced confirmed.
Vi, < i, j < n n i + j) : Pi — • i>- : H\SpriVi(H)
Table 4.3: Public key predistribution protocol using visual verification.
A s a hash function, w e once again use SHA-256, and as a current protocol
instance i d pid w e use ordered concatenation of all participants r a n d o m
nonces rj, n , respectively.
Speaking about complexities, w e have already mentioned key confirmation
adds one round, i n w h i c h each participant has to perform one broadcast.
Computational complexity consists of one hash computation, one digital
signature and n digital signatures verifications.
Protocol settings
Chosen protocol provides a number of customizable parameters. We designed
our application i n a w a y that the protocol leader is able to set these
parameters according to its w i l l (and propagate these settings during the
initialization phase). We provided the following options:
• Source of randomness: Either the device's native SecureRandom
service determined by the preset preferences can be used, or the i m plemented
randomness extractor, w i t h the entropy input taken from
the camera.
• Communication channel: Bluetooth, or Wi-Fi.
• Protocol version: non-authenticated, authenticated, or authenticated
w i t h key-confirmation.
• Nonce length: 32, 64, or 128 bits.
• Public key length: 1024, or 2048 bits.
• Group key length: 1024, or 2048 bits.
A l l these parameters have their natural impact on the protocol r u n duration,
w h i c h can be simply obtained from the presented complexities. Let us
n o w revise some of them from the user perspective. We have chosen not to
give the precise numbers, as they are influenced significantly by the current
43
4. I M P L E M E N T A T I O N
environment state. Instead, only the approximate ones are given to provide
a relative comparison.
We state that between the communication channel options is only an i n significant
duration difference (fractions of seconds). O n the other hand, the
choice of the randomness source influences the protocol duration substantially.
W h i l e i n the case of the native one the protocol instance lasts from 1
to 4 seconds (measured for 2 a n d 3 devices), using the randomness extractor
w e encounter the duration i n tens of seconds (namely, 20 to 50 seconds
according to the other parameters).
4.3 Application design and user interface
Figure 4.2: Generalized application class diagram.
The design of our application is influenced mainly b y the A n d r o i d O S characteristics.
A n d r o i d provides a strongly recommended w a y to develop an
application using Java A P I extended b y A n d r o i d ' s custom elements (e.g.
components). This way, w e can benefit from other properties A n d r o i d that
environment as a whole offers: easy high-level development using A n d r o i d
S D K and distribution using Google Play.
44
4. I M P L E M E N T A T I O N
We provide a generalized overview of the application design i n Figure
4.2, w i t h each part of the system described separately. For activity components,
also their layouts and an interaction graph are attached.
4.3.1 provider
Following the principles of Java cryptography architecture, w e have decided
to design and implement the security mechanisms provided by the
application using the m o d e l of Cryptographic service provider (also referred
to as Security provider). This increases the potential reusability of
the code, as w e step into a w e l l documented and defined area.
Earlier w e have listed the two areas relevant to our application, that
are dealt w i t h i n Security provider: (pseudo)random number generation
(SecureRandom class) and key agreement (KeyAgreement class). It turns
out, that each have a completely different relation to our application.
KeyAgreement is from our point of v i e w too low-level. It provides
only the basic mathematical background for protocols. Moreover, DiffieHellman-based
mechanisms are implemented by most of the standard
providers, hence it is useless to implement them from scratch, the more,
that w e have to bear i n m i n d also the communication part of the protocol.
O n the contrary, SecureRandom class provides the r a n d o m data, w h i c h
is exactly what the goal of a randomness extractor is. W h i l e the implementations
of the M i n E n t r o p y S o u r c e interface are not directly accessible as
the SecureRandom generator, they serve as an entropy input for the randomness
extractors (represented i n the diagram by R a n d E x t r a c t o r ) . We
have achieved the interface similarity, however, the issues connected w i t h
the entropy collection (using a camera input) forced some additional conditions
to be fulfilled to ensure the proper functionality. These conditions are
discussed i n section 4.1.
4.3.2 gka
gka package covers the whole design of the group key agreement protocols.
Its separation ensures independence o n communication channels and
on the A n d r o i d environment, as the code i n this package does not use
Android-specific libraries.
The basic model is simple - a protocol r u n is modelled as the instance of
an implementation of the G K A P r o t o c o l interface w i t h participants seen as
G K A P a r t i c i p a n t objects. A detailed design description is out of the scope
of this section and is discussed i n section 4.2.
45
4. I M P L E M E N T A T I O N
4.3.3 Communication services
Packages w i f i g k a and b l u e t o o t h g k a encapsulate the communication
w i t h respect to given channels. Each utilizes either Wi-fi or Bluetooth channel
to capture the wanted message packets and transform them into objects
that the protocols, implementing G K A P r o t o c o l interface, can cooperate
with.
The m a i n functionality is provided by the A n d r o i d service
component B l u e t o o t h C o m m u n i c a t i o n S e r v i c e and
W i f i C o m m u n i c a t i o n S e r v i c e respectively that are called o n an i n tention
of the protocol invocation. First of all, they establish a connection
between devices, resulting i n interconnected sockets. In the case of Bluetooth
technology, the devices have to be paired before the communication
starts, w h i c h can be achieved by employing the native pairing mechanism.
The pairing of devices means their owners are explicitly notified about
the intent of binding and u p o n some additional information can authenticate
the other device and decide about the successfulness of the b o n d .
If the sockets are interconnected, the service objects are running i n the
background throughout the whole application life-cycle and facilitate the
communication.
4.3.4 randgkaapp
Figure 4.3: Activity interaction graph
randgkaapp package contains all A c t i v i t y classes i n the application,
hence provide a complete user interface. Figure 4.3 depicts application's
activities together w i t h possible transitions between them. The transitions
are oriented, represented by arrows, however a reverse passage is possible
46
4. I M P L E M E N T A T I O N
using a native A n d r o i d back button.
A c o m m o n application's process starts i n M a i n A c t i v i t y , however using
the method of an implicit intent we are able to provide any other application
w i t h the resulting key easily. We have designed a custom action
(cz . muni . randgka . ACTION_GKA_KEY). O u r application is able to
response to the I n t e n t carrying this action. The appropriate application
process is described by a subgraph determined by the starting Out-node
representing the calling application. This w a y of group key retrieval is very
simple and elegant for any other application's programmer, as it does not
require to include the code w i t h a G K A implementation. Rather the programmer
just creates an appropriate I n t e n t .
M a i n A c t i v i t y (Main)
M a i n A c t i v i t y (Figure 4.4a) serves as an entrance point into the application,
as its exported attribute is set to t r u e (i.e. it can be invoked by any
application). It provides a simple decision point w i t h what functionality to
continue.
« ftQ? .ill S 10:43 I i Q 0 ? .,i R 10:45 I s 10:45 I * O S ^ a
10:46
A ' RandGKAApp I ijpl Randomness Source I ijjl Randomness Extractor I '8fl PublicKeyCryptographyAppAc...
Culpul file (empty - display sequence! Output tile ieimty - d s.;lay secuerce) Randomness Spurce
Randomness Source
randomness extractor
Figure 4.4: Activity screens, from left: a) M a i n A c t i v i t y ,
b) M i n E n t r o p y S o u r c e A c t i v i t y , c) R a n d E x t r a c t o r A c t i v i t y ,
d ) L o n g T e r m K e y A c t i v i t y .
MinEntropySourceActivity (MES)
This A c t i v i t y implementation (Figure 4.4b) provides the functionality of
collecting a specified amount of entropy from the designed source, w h i c h
output is preprocessed i n advance. The outcome can be either directly displayed,
or stored i n a file o n an external storage.
47
4. I M P L E M E N T A T I O N
RandExtractorActivity (RE)
R a n d E x t r a c t o r A c t i v i t y (Figure 4.4c) have the same properties as
M i n E n t r o p y S o u r c e A c t i v i t y w i t h the difference its outcome is processed
using a the implemented randomness extractor.
LongTermKeyActivity (LTK)
To avoid the attack utilizing a compromised long-term key used for authentication,
the user is provided i n this A c t i v i t y (Figure 4.4d) w i t h the
option of a fresh long-term key generation.
i 5 l 0 f a 10:5G * O Q f -il" a 10:5D
101 BluetoothGKAMemberActivity 'fcl GKAProtocolActivity
" ľ L d e r HTC Desire - 0G:23:76:E4:6B:61 A O Non-a uthe-tica ted
© Authentica ted
( ,: Authentica ted + <ey confirma tion
Nonce length (bits)
Channel
Bluetooth
Connect
O Non-a uthe-tica ted
© Authentica ted
( ,: Authentica ted + <ey confirma tion
Nonce length (bits)
Fandomress Source
randomness extra ctor
O Non-a uthe-tica ted
© Authentica ted
( ,: Authentica ted + <ey confirma tion
Nonce length (bits)
J 1 2
A
Gr-L.p key length (bits)
1D24 Á
Pub ic <ey lergth (bits)
1024 .
OKA Key
Protocol Participants
Run Protocol
Figure 4.5: Activity screens regarding G K A protocol , from l eft:
a) G K A D e c i s i o n A c t i v i t y , b) GKAMemberActivity, c) G K A A c t i v i t y .
G K A D e c i s i o n A c t i v i t y (Dec)
This A c t i v i t y (Figure 4.5a) impl ementation provides a simpl e decision
point about the technol ogy used for a group key agreement protocol i n stance
a n d the underl ying topol ogy. A s the impl emented protocoluse a star
topology, the user is provided w i t h options to act either as a group l eader,
or a member. If the Bl uetooth channel is chosen, the appl ication tries to establish
the connection by itsel f. Moreover, each member is asked expl icitl y
about the device it wants to connect to. If the W i ­ F i channel is chosen, the
application onl y checks the presence of the needed W i ­ F i connection w i t h
the appropriate topology (a protocol leader has to provide an access point to
members). The user is also provided w i t h two randomness source options,
either native SecureRandom service, or the impl emented randomness extractor.
A s seen from the appl ication's scheme, this activity also serves as
48
4. I M P L E M E N T A T I O N
a gate for other applications wanting to get a shared key via I n t e n t w i t h
the action set to cz . muni . randgka . ACTION_GKA_KEY.
G K A M e m b e r A c t i v i t y (Mem)
(Figure 4.5b) A member is offered a list of devices he can connect to. Remark
that this is a list of either paired or discovered devices w i t h the Bluetooth
technology nothing to say about the presence of our application's
open socket. To find out its current state, a user has to connect to the given
device first. W h e n the two devices have not been paired before b y the A n droid's
native pairing mechanism, the user is asked to do so after pressing
the Connect button.
G K A A c t i v i t y ( G K A )
G K A A c t i v i t y (Figure 4.5c) displays an overview of the protocol to be executed.
To the member, the protocol parameters are displayed, while to the
leader the possibility to choose them is given. Furthermore, all participating
devices are printed, together w i t h their public keys (with the appropriate
hash values), to provide a basic visual verification. After all participants
have connected, leader can invoke a protocol instance by pressing the " R u n
protocol" button. A shared key is displayed on the same screen. The protocol
can be r u n multiple times using the same settings. If the application
was invoked by another application w i t h the aim of key retrieval, the button
"Retrieve k e y " is displayed, w i t h an obvious purpose, after the successful
protocol instance run.
4.4 Security
Throughout most of this thesis, we deal w i t h the security of group key
agreement from the theoretical point of view. However, w i t h our application
implementation we get into practice, w h i c h has further impacts on
security. In this section, we investigate possible vulnerabilities of the application
and discuss the overall security of it.
Attacker's m a i n goals are actually two: to get a private part of a long
term key and to get a shared key for current session. A shared session key
is b y default stored only i n an operating memory of our application. In the
case of its invocation w i t h the intent to get a shared key by another application,
after the agreement is done, it is passed to the calling application. A
long term key is stored i n both a long term internal memory and an appli-
49
4. I M P L E M E N T A T I O N
cation's operating memory. These are then the "interfaces" a n attacker can
use to obtain its desired values.
We further focus o n application interfaces (borders) to determine the
possibility of their use for a successful attack. For security assessing, w e
have to assume the A n d r o i d principles sketched i n chapter 3 hold, otherwise
w e have nothing to lean on.
4.4.1 Interprocess communication
We p r o v i d e d a scheme of our application together w i t h all components
earlier. A s for n o w , w e state that all but M a i n A c t i v i t y a n d
G K A T e c h D e c i s i o n A c t i v i t y have their e x p o r t e d attributes set to
f a l s e (including both S e r v i c e components). This is important, because
it prevents other application from the direct access to components possessing
sensitive data. The t w o mentioned components serve as the introducing
points into the application run. M a i n A c t i v i t y has no means to access
to sensitive information, G K A T e c h D e c i s i o n A c t i v i t y o n the other hand
returns the shared key the group agreed upon. This is a wanted design feature,
however, w e utilized it to propose a simple attack able to pass the
shared key to a malicious third party.
Intent-using attack
A n attacker can develop a n application copying o u r application's design,
using the same name a n d icon. W h e n it is somehow able to i n stall
it o n the target device, a user cannot tell the difference without
further investigation. The malicious application w h e n passing towards
a group key protocol instance creates a n I n t e n t object w i t h action
cz .muni . randgka . ACTION_GKA_KEY, that invokes o u r application, lets
it execute a n d gets the result. W h i l e possessing the shared key, it can still
appear to be our application, while handling w i t h the key i n any arbitrary
manner.
Intent-using attack prevention
To prevent the designed attack, it should be sufficient to show the user,
if our application was invoked from M a i n A c t i v i t y or b y an implicit
I n t e n t . We simply let this display o n the G K A D e c i s i o n A c t i v i t y screen.
5 0
4. I M P L E M E N T A T I O N
4.4.2 User interface and communication
A n attacker could use the invalid values injection into the application itself
using either a user interface, or communication channels. We state we compare
each input value obtained on these application interfaces against its
valid template to prevent this type of attack.
Security of communication itself is assured by the protocol design.
4.4.3 Storage
Both of the key types used are stored i n an operating memory, w h e n our application
is o n (after they have been obtained). This way, they are protected
against reading by other processes using native Linux-based memory management
principles taken over by A n d r o i d OS.
A long term key is stored i n the device's internal persistent memory using
concept of S h a r e d P r e f erences. This type of A n d r o i d value storage
persist the values i n a file that can be accessed only b y its owner, i n this
case our application. Yet again, the security is based o n L i n u x access rights
model.
From the design point of view, both important values are secured, h o w ever,
we have to bear i n m i n d the real system's implementation vulnerabilities.
The already mentioned attacks obtaining root rights - [25, 18], can
be r u n without attacker to physically possess the device. Against them, w e
cannot defend w i t h i n the scope of our application. The storage variants are
actually equally vulnerable. A notable difference between security achieving
by storing only i n an operating memory and storing i n an internal m e m ory
between two executions can be stated, w h e n there are attacks able to
get the data only from the latter type. Such attacks can be performed using
forensic tools, however the attacker needs to have at least temporarily access
to the target device. To ensure the long term key is not compromised,
user can choose the option of a fresh key use before a new protocol instance
starts.
51
Chapter 5
Conclusion
We studied the area of group key agreement protocols to determine the
most suitable ones for Android-based mobile devices. O u r priority was to
achieve the security properties, namely implicit and explicit key confirmation,
resilience against replay and known-key attacks, perfect forward secrecy
and key confirmation. The used communication technologies (Bluetooth
and Wi-Fi) determined the m a i n design feature - protocol topology.
Both the technologies connect devices into a network w i t h a star topology.
Within the resulting area, w e focused o n the computational and c o m m u n i cation
complexities.
After narrowing the list of candidate protocols to the ones achieving the
wanted security features and w o r k i n g over the star topology, w e decided to
implement A u g o t et al. protocol (mainly for the efficiency reasons). M o r e over,
this protocol provides both authenticated and non-authenticated versions,
w i t h the former one designed according to the Katz-Yung compiler.
O n the contrary, it does not enable to confirm the shared key. We consider
the key confirmation to be the most expensive (from the complexities point
of view) security feature, comparing to the others, however to achieve all
the features, we implemented it, employing the same method as designed
in the Bresson-Catalano protocol (within one additional final round). In the
end, all three mentioned versions were included i n our application.
Part of the thesis was to design an alternative source of randomness. We
utilized a camera to provide a source described by its min-entropy, w h i c h
we determined after the data output analysis and testing. This output is
then involved i n a randomness extraction, to produce theoretically almost
random sequences. Taking into account the output features (frequency, randomness),
w e state our solution operates o n the same qualitative level as
the output of native A n d r o i d randomness provider - /dev/ random. O n
the other hand, for purposes of our application, sources w i t h a m u c h higher
output frequency w o u l d be more suitable, to make the user experience
more comfortable. Therefore, w e employed also the randomness providing
service native to the environment. This way, the application user is able
52
5 . C O N C L U S I O N
to compare the execution times. The ones using the native service are m u c h
lower comparing to the implemented randomness extractor solution, h o w ever,
this comfort is exchanged for the qualitative randomness properties.
5 3
Bibliography
[1] Strategy Analytics. A n d r o i d captured 79% share of global smartphone
shipments i n 2013.
h t t p : / / b l o g s . s t r a t e g y a n a l y t i c s . c o m / W S S / p o s t / 2 0 1 4 /
0 1 / 2 9 / A n d r o i d - C a p t u r e d - 7 9 - S h a r e - o f - G l o b a l Smartphone-Shipments-in-2013
. aspx, 2014.
[2] Giuseppe Ateniese, Michael Steiner, a n d Gene Tsudik. Authenticated
group key agreement and friends. In Proceedings of the 5th ACM Conference
on Computer and Communications Security, C C S '98, pages
17-26, N e w York, N Y , U S A , 1998. A C M .
[3] Daniel A u g o t , Raghav Bhaskar, Valérie Issarny, a n d Daniele Sacchetti.
A n efficient group key agreement protocol for a d hoc networks. In i n
First International IEEE WoWMoM Workshop on Trust, Security and
Privacy for Ubiquitous Computing. Press, 2005.
[4] Klaus Becker a n d U t a Wille. C o m m u n i c a t i o n complexity of group key
distribution. In Proceedings of the 5th ACM Conference on Computer
and Communications Security, C C S '98, pages 1-6, N e w York,
N Y , U S A , 1998. A C M .
[5] Bert Boer. Diffie-hellman is as strong as discrete log for certain primes.
In Shafi Goldwasser, editor, Advances in Cryptology — CRYPTO' 88,
volume 403 of Lecture Notes in Computer Science, pages 530-539.
Springer N e w York, 1990.
[6] D a n Boneh. The decision diffie-hellman problem. In Joe P. Buhler,
editor, Algorithmic Number Theory, volume 1423 of Lecture Notes in
Computer Science, pages 48-63. Springer Berlin Heidelberg, 1998.
[7] Jan Bouda, Jan Krhovják, Václav Matyáš, a n d Petr Svenda. Towards
true r a n d o m number generation i n mobile environments. In LNCS
5838, Identity and Privacy in the Internet Age, pages 179-189, Berlin,
2009. Springer.
54
5. C O N C L U S I O N
[8] C o l i n B o y d a n d Juan M a n u e l Gonzalez Nieto. Round-optimal contributory
conference key agreement. In Y v o G . Desmedt, editor, Public
Key Cryptography — PKC 2003, volume 2567 of Lecture Notes in
Computer Science, pages 161-174. Springer Berlin Heidelberg, 2002.
[9] E m m a n u e l Bresson and Dario Catalano. Constant round authenticated
group key agreement via distributed computation. In Feng Bao, Robert
Deng, a n d Jianying Z h o u , editors, Public Key Cryptography - PKC
2004, volume 2947 of Lecture Notes in Computer Science, pages 115-
129. Springer Berlin Heidelberg, 2004.
[10] E m m a n u e l Bresson, Olivier Chevassut, a n d D a v i d Pointcheval. Provably
authenticated group diffie-hellman key exchange - the dynamic
case. In C o l i n B o y d , editor, Advances in Cryptology - ASIACRYPT
2001, volume 2248 of Lecture Notes in Computer Science, pages 290-
309. Springer Berlin Heidelberg, 2001.
[11] E m m a n u e l Bresson, Olivier Chevassut, D a v i d Pointcheval, a n d JeanJacques
Quisquater. Provably authenticated group diffie-hellman key
exchange. In Proceedings of the 8th ACM Conference on Computer
and Communications Security, C C S '01, pages 255-264, N e w York, N Y ,
U S A , 2001. A C M .
[12] M i k e Burmester a n d Y v o Desmedt. A secure a n d efficient conference
key distribution system (extended abstract). In Advances in Cryptology
- EUROCRYPT '94, Workshop on the Theory and Application
of Cryptographic Techniques, Perugia, Italy May 9-12, 1994, Proceedings,
volume 950 of Lecture Notes in Computer Science, pages 275-
286. Springer, 1994.
[13] W. Diffie a n d M . H e l l m a n . N e w directions i n cryptography, 1976.
[14] R. Dutta a n d R. Barua. Provably secure constant round contributory
group key agreement i n dynamic setting. Information Theory IEEE
Transactions on, 54(5):2007-2025, M a y 2008.
[15] Shkodran G E R G U R I . K e y agreement for mobile phones [online].
Diplomová práce, Masarykova univerzita, Fakulta informatiky, 2011
[cit. 2014-05-08].
[16] R. Impagliazzo, L . A . Levin, a n d M . Luby. Pseudo-random generation
from one-way functions. In Proceedings of the Twenty-first Annual
55
5. C O N C L U S I O N
ACM Symposium on Theory of Computing, S T O C '89, pages 12-24,
N e w York, N Y , U S A , 1989. A C M .
[17] I. Ingemarsson, D . Tang, a n d C . Wong. A conference key distribution
system. IEEE Trans. Inf. Theor., 28(5):714-720, September 2006.
[18] X u x i a n Jiang. Gingermaster: First android malware utilizing a root
exploit o n android 2.3 (gingerbread), h t t p : / /www. esc . ncsu . edu/
f a c u l t y / j i a n g / G i n g e r M a s t e r / , 2011.
[19] Jonathan Katz a n d M o t i Yung. Scalable protocols for authenticated
group key exchange, pages 110-125. Springer-Verlag, 2003.
[20] Soo H y e o n K i m , D a e w a n H a n , a n d D o n g H o o n Lee. Predictability
of android openssl's pseudo r a n d o m number generator. In Proceedings
of the 2013 ACM SIGSAC Conference on Computer & Communications
Security, C C S '13, pages 659-668, N e w York, N Y , U S A , 2013.
A C M .
[21] Jan Krhovják, Petr Svenda, a n d Václav Matyáš. The sources of randomness
i n mobile devices. In Proceeding of the 12th Nordic Workshop
on Secure IT Systems, pages 73-84, K r i n g l a n 1, 103 Reykjavik,
2007. Reykjavik University.
[22] U e l i M . Maurer. Towards the equivalence of breaking the diffiehellman
protocol a n d computing discrete logarithms. In Y v o G .
Desmedt, editor, Advances in Cryptology — CRYPTO '94, volume 839
of Lecture Notes in Computer Science, pages 271-281. Springer Berlin
Heidelberg, 1994.
[23] Alfred J. Menezes, P a u l C . V a n Oorschot, Scott A . Vanstone, a n d R. L .
Rivest. H a n d b o o k of applied cryptography, 1997.
[24] K a i Michaelis, Christopher Meyer, a n d Jorg Schwenk. R a n d o m l y
failed! the state of randomness i n current Java implementations. In
E d D a w s o n , editor, Topics in Cryptology - CT-RSA 2013, volume 7779
of Lecture Notes in Computer Science, pages 129-144. Springer Berlin
Heidelberg, 2013.
[25] Lookout mobile security. Lookout mobile security
technical tear d o w n - droiddream. h t t p s : / /
b l o g . l o o k o u t . c o m / w p - c o n t e n t / u p l o a d s / 2 0 1 1 /
03/COMPLETE-DroidDream-Technical-Tear-Down_
L o o k o u t - M o b i l e - S e c u r i t y . p d f , 2011.
56
5. C O N C L U S I O N
[26] N o a m N i s a n and D a v i d Zuckerman. Randomness is linear i n space.
Journal of Computer and System Sciences, 52:43-52,1993.
[27] Oracle. Java cryptography architecture (jca) reference guide.
h t t p : / / d o c s . o r a c l e . c o m / j a v a s e / 7 / d o c s / t e c h n o t e s /
g u i d e s / s e c u r i t y / c r y p t o / C r y p t o S p e c . h t m l , 2011.
[28] Jaikumar Radhakrishnan and A m n o n Ta-Shma. Bounds for dispersers,
extractors, and depth-two superconcentrators. SIAM JOURNAL ON
DISCRETE MATHEMATICS, 13:2000, 2000.
[29] R. L. Rivest, A . Shamir, and L. A d l e m a n . A method for obtaining
digital signatures and public-key cryptosystems. Commun. ACM,
21(2):120-126, February 1978.
[30] A n d r e w R u k h i n , Juan Soto, James Nechvátal, Miles S m i d , Elaine
Barker, Stefan Leigh, M a r k Levenson, M a r k Vangel, D a v i d Banks,
A l a n Heckert, James Dray, San Vo, and Lawrence E. Bassham III. Nist
special publication 800-22revla: A statistical test suite for r a n d o m
and pseudorandom number generators, h t t p : / / c s r c . n i s t . gov/
g r o u p s / S T / t o o l k i t / r n g / d o c u - m e n t s / S P 8 0 0-2 2 r e v l a . p d f ,
2010.
[31] M . Santha and U . V. Vazirani. Generating quasi-random sequences
from slightly-random sources. In Proceedings of the 25th Annual Symposium
onFoundations of Computer Science, 1984, SFCS '84, pages
434-440, Washington, D C , U S A , 1984. IEEE Computer Society.
[32] Ronen Shaltiel. Recent developments i n explicit constructions of extractors.
Bulletin of the EATCS, 77:67-95, 2002.
[33] Ronen Shaltiel. A n introduction to randomness extractors. In Proceedings
of the 38th International Conference on Automata, Languages and
Programming - Volume Part II, I C A L P ' l l , pages 21-41, Berlin, Heidelberg,
2011. Springer-Verlag.
[34] A d i Shamir. Identity-based cryptosystems and signature schemes. In
Proceedings of CRYPTO 84 on Advances in Cryptology, pages 47-53,
N e w York, N Y , U S A , 1985. Springer-Verlag N e w York, Inc.
[35] A r a v i n d Srinivasan and D a v i d Zuckerman. C o m p u t i n g w i t h very
weak random sources. SIAM Journal on Computing, 28:264-275,1994.
57
5 . C O N C L U S I O N
[36] M . Steiner, G . Tsudik, and M . Waidner. Cliques: a new approach to
group key agreement. In Distributed Computing Systems, 1998. Proceedings.
18th International Conference on, pages 3 8 0 - 3 8 7 , M a y 1998.
[37] Michael Steiner, Gene Tsudik, and Michael Waidner. Diffie-Hellman
key distribution extended to group communication. In Proceedings of
the 3rd ACM Conference on Computer and Communications Security,
C C S ' 9 6 , pages 3 1 - 3 7 , N e w York, N Y , U S A , 1996. A C M .
[38] Luca Trevisan. Construction of extractors using pseudo-random generators
(extended abstract). In Proceedings of the Thirty-first Annual
ACM Symposium on Theory of Computing, S T O C ' 9 9 , pages 1 4 1 - 1 4 8 ,
N e w York, N Y , U S A , 1 9 9 9 . A C M .
[39] John v o n N e u m a n n . Various Techniques U s e d i n Connection w i t h
R a n d o m Digits. /. Res. Nat. Bur. Stand., 1 2 : 3 6 - 3 8 , 1 9 5 1 .
5 8
Appendix A
List of relevant files
Source: h t t p s : / / i s .muni . c z / t h / 3 2 5 2 7 2 / f i_m/
• RandGKA.zip - A n archive containing source codes of
the implemented application, a n d the installation package
(. /RandGKA/bin/RandGKA. apk).
• e n t r o p y S e q . z i p - A n archive containing the collected r a n d o m data
from the designed camera entropy source. File of the form minen_X
regards to the setting of X-bit output per one sample frame.
• NeedingGKAKey. apk - A n installation package of a simple
application calling the designed I n t e n t action
(cz .muni . f i . randgka . ACTION_GKA_KEY) for the key retrieval.
5 9