ycode]bash

# Recursive Augmented Fernet (RAF) Token
Alleviating the Pain of Stolen Tokens

Reza Rahaeimehr, Augusta University, GA, USA<EMAIL_ADDRESS>
Marten van Dijk, University of Connecticut, CT, USA<EMAIL_ADDRESS>
###### Abstract

A robust authentication and authorization mechanism is imperative in modular
system development, where modularity and modular thinking are pivotal.
Traditional systems often employ identity modules responsible for
authentication and token issuance. Tokens, representing user credentials,
offer advantages such as reduced reliance on passwords, limited lifespan, and
scoped access. Despite these benefits, the "bearer token" problem persists,
leaving systems vulnerable to abuse if tokens are compromised. We propose a
token-based authentication mechanism addressing modular systems’ critical
bearer token problem. The proposed mechanism includes a novel RAF (Recursive
Augmented Fernet) token, a blacklist component, and a policy enforcer
component. RAF tokens are one-time-use tokens, like tickets. They carry
commands, and the receiver of an RAF token can issue new tokens using the
received RAF token. The blacklist component guarantees an RAF token can not be
approved more than once, and the policy enforcer checks the compatibility of
commands carried by an RAF token. We introduce two variations of RAF tokens:
User-tied RAF, offering simplicity and compatibility, and Fully-tied RAF,
providing enhanced security through service-specific secret keys. We
thoroughly discuss the security guarantees, technical definitions, and
construction of RAF tokens backed by game-based proofs. We demonstrate a proof
of concept in the context of OpenStack, involving modifications to Keystone
and creating an RAFT library. The experimental results reveal minimal overhead
in typical scenarios, establishing the practicality and effectiveness of RAF.
Our experiments show that the RAF mechanism beats the idea of using short-life
Fernet tokens while providing much better security.

##  1 Introduction

Modularity and modular thinking and development models are the key to
implementing an extensive system. For a modular system, a proper
authentication and authorization mechanism is essential. Usually, there is a
module, say the identity module, in a modular system that is in charge of
authentication and authorization. Users present their credentials (usually a
username and password) to the identity module and are granted tokens in
exchange. Other modules only serve users who have valid tokens. Tokens are
either a random bit string like a UUID that points to an entry in an
authentication and authorization database, or a crafted piece of data that
carries some authentication and authorization information like Fernet and JWT
tokens (see section 2.2).

Using token instead of username and password has three main advantages:

  * •

Users do not need to use their passwords for every system access.
Consequently, the probability of leaking passwords gets lower.

  * •

Every token has an expiration time. Hence, a stolen token can only be abused
for a limited time.

  * •

It is possible to limit the scope of a token and let the user ask for a less
privileged token. In this case, if an adversary steals the token, she will
have limited access to the resources of the token owner.

The above features allow a user to get a short-life scoped token from the
identity module and delegate the authority to a third trusted party to
accomplish a complicated task within the scope.

##### Problem:

Although the ability to use a token and make requests on behalf of a user
(authorization delegation) is a vital feature for a highly modular system, it
is the source of many vulnerabilities [1]. Adversaries can find bugs in large
scale systems; With the current token mechanisms [2, 3, 4], if an adversary
exploits some of these bugs and finds a way to obtain user tokens, she can do
whatever the owners of the tokens can do. This problem is known as the “bearer
token” problem [1].

Scoping tokens down and reducing their lifetime are two ways that are used to
reduce the impact of the bearer token problem [5]. However, all the typical
token types like UUID, PKI, Fernet, JWT [4] and ticketing systems like
Kerberos [6] have two main shortcomings:

  * •

First, in current mechanisms, the immediate impact of shortening the lifetime
of tokens or reducing the scope of tokens is that users need to renew their
tokens more often. In practice, if we remarkably shorten the lifetime of
tokens and reduce the scope of tokens, the identity module turns into a
bottleneck.

  * •

Second, no matter how much a system shortens the lifetime of tokens or limits
the scope of tokens, a stolen token can be very dangerous. This is because
there is no relation between tokens and commands. For example in OpenStack, if
you get a 1-second life token for deleting a volume in a project and the token
is leaked to an adversary, the adversary can delete all the volumes in the
project during that 1 second.

Considering this problem, system designers make a trade-off between system
performance and security. For example, in OpenStack[7], the default token
lifetime is one hour, and the smallest scope is a project[8]. In summary,
despite shortening the life time or reducing the scope of a token, an
adversary who can corrupt a module and observe a token can do tremendous
damage. Having a bug free system is not realistic, but reducing the effects of
buggy code is possible. Therefore, it is desirable to generalize the
modularity security requirement that is proposed by Maleki et al. [1] as
follow:

##### Modularity Security Requirement:

For a modular system, if an adversary corrupts a module, other modules just do
whatever requested to do by the users, nothing more.

For an instance, in OpenStack, it is desired that, in the event an adversary
compromises the Networking module, he should be unable to create or delete a
VM.

##### Our work:

This work provides the modularity security requirement for modular and
distributed systems by developing the following parts:

  1. 1.

A novel token that we call Recursive Augmented Fernet (RAF) token on top of
which commands can be added to tokens without requiring additional identity
module interaction.

  2. 2.

A blacklist structure that prevents replay attack.

  3. 3.

A policy enforcer component that prevents malicious command execution.

We introduce two subtypes: User-tied RAF (Ut-RAF) that is the best option for
the systems that are currently using Fernet tokens and seeking for more secure
solutions without the need for significant changes, and Fully-tied RAF (Ft-
RAF) that provides better security guarantees. Ft-RAF requires each module to
have a secret key shared with identity module. Hence, it needs a key
distribution/renewal mechanism, which makes it harder to deploy compared to
Ut-RAF. A summary of security analysis of Ut-RAF and Ft-RAF is given in
section 3, and the details can be find in A.

We explain our proposal in the context of OpenStack to show its usability and
performance in practice. OpenStack is one of the world’s most successful open-
source software that has been developed by tens of thousands of contributors
around the world, offers a robust and smooth Infrastructure-as-a-Service
(IaaS) cloud platform, and has been utilized by companies like RedHat,
American Express, IBM, AT&T, Adobe, and Best Buy [9]. Therefore, we firmly
believe that if RAF tokens function effectively in OpenStack, they will easily
integrate with other systems.

Our proposal has two important strength:

First, it allows reducing the lifetime or scope of tokens without interacting
with identity module. It ties tokens to commands and in fact, limits the usage
of tokens only to the commands issued by users and minimizes the impact of
stolen tokens.

Second, it offers to the third-party Fernet-token-base system add-ons the
choice to continue using Fernet and gradually upgrading to RAF (if the system
policy continues accepting Fernet tokens). Note that, in our solution, the
identity module still issues Fernet tokens.

We have implemented a RAF library that allows issuing RAF tokens either based
on Fernet or other RAF tokens. Also, we have modified the identity module of
OpenStack to accept and validate RAF tokens. The experimental results show
that our mechanism adds less than 1 percent overhead to the validation time of
a token, i.e., less than a microsecond. Also, our experiment showed that
generating a RAF token from a long life Fernet token is significantly (more
than 88 times in our experiments) faster compared to getting a new short
lifetime Fernet token from the identity module.

##### Threat Model:

A service111In OpenStack, each module is referred to as a service. Therefore,
in this article, we use the terms ‘module’ and ‘service’ interchangeably. can
be corrupted in two ways:

  * •

Partial corruption: where a service leaks tokens to the adversary, but it does
what is supposed to do.

  * •

Fully corruption: where a service is under control of the adversary and the
adversary can do whatever he wants within the service.

We consider a strong adversary who can fully corrupt some services and observe
all network communications except User- identity module communications. Hence,
user-identity module communications must be confidential and authenticated. In
OpenStack, it is possible to secure User-Service communication by enabling TLS
and having a certificate for each service. But, since service-to-service
communication is not secure, we also assume User-Service communication is not
secure. This allows us to cover a wider range of applications and provide
stronger security.

##### Organization:

We commence with an overview of the history and structure of OpenStack,
elucidating the four popular token formats in Section 2.1. Section 3 provides
details of our tokening mechanism, while Section 4 delves into the security
analysis of RAF. In Section 5, we present a proof of concept for RAF and
describe some of the results obtained from using RAF in our experiments. We
conclude our work with a summary in Section 6.

##  2 Background

###  2.1 OpenStack

In 2010, Rackspace wanted to redesign its Cloud servers offering
infrastructure, while NASA was interested in a similar project. Negotiation
between the two teams led to a shared program called OpenStack. The OpenStack
Foundation was established in September 2012, which has been in charge of
OpenStack since then. In 2019, it had more than 100,000 community members from
187 countries who had collaborated to build one of the most significant open-
source projects in the world [10].

OpenStack is a modular system divided into projects (services) at the highest
level. Every project utilizes third-party plugins that must be open-source as
well. Usually, for a use case, OpenStack supports several plugins that can be
used interchangeably. The following projects are the core of OpenStack:

Keystone

implements Identity API and is in charge of authentication and authorization.

Nova

is the heart of OpenStack and manages computation resources.

Cinder

provides block storage (volumes) mainly used by virtual machines.

Glance

is the imaging service, which maintains data assets like operating systems.

Neutron

enables networking services.

Swift

provides efficient block storage and can be used independently. Hence, some
companies take advantage of Swift for storing data.

Horizon

resembles the dashboard of OpenStack and provides a web interface for clients.
Although Horizon is not the only way for interacting with OpenStack, it is the
simplest way for clients if they want to manage the system manually.

In addition to Horizon, users can send their request to OpenStack via cURL
[11] or OpenStack Client library. cURL allows a person to send an HTTP/HTTPS
request. OpenStack Client library is a tool for developers and enables them to
converts users’ high-level commands to corresponding cURL commands.

Each service implements some Representational State Transfer (REST) APIs,
which are the standard way to communicate with a service in OpenStack. A REST
API is a web service that is callable by HTTP/HTTPS requests. The OpenStack
REST APIs accept parameters in JSON format. To access OpenStack, first, a user
must get a token from Keystone by presenting his/her username and password.
Each token has an expiration time, and the user needs to refresh his token
periodically. The user must put the token in the header of all his requests to
other modules. Whenever a service receives a request, first of all, it checks
the presence of a token in the header. Then, the service validates the token
with Keystone. Sometimes a service needs to make a request to other services
on behalf of the user using the received token. For example, whenever a user
wants to create a virtual machine, in addition to the virtual machine
specification (like the amount of RAM and number of virtual CPU), he must
specify a network. In this case, the user sends his request to Nova. Nova
builds the VM, but it needs to get in touch with Neutron to establish the
connection between the VM and the network. Figure 1 shows the interaction
between a user and some OpenStack modules as described above.

Figure 1: The interaction between a user and the main OpenStack modules.

###  2.2 Token Formats

The four most common types of tokens that also have been used in OpenStack are
as follows:

##### UUID

A UUID token is nothing more than a random string (32 characters in OpenStack)
and carries no information. Consequently, to validate the issued tokens, the
system needs to store them and relative meta-data in a database. Implementing
the UUID token mechanism is straightforward. Its main disadvantage is the
token database. In a practical deployment, a UUID token database grows fast,
and after a while, inserting and retrieving data from the database turns into
a bottleneck for high throughput systems. In addition, the complexity of
establishing multiple identity nodes and scalability are other concerns that
convinced the OpenStack community to look for alternative token mechanisms.

##### PKI and PKIz

PKI token was the first attempt to utilize Public Key Infrastructure in
OpenStack. A PKI token carries some meaningful data like the owner’s
specification, privileges, issue time and expiration time of the token, and
catalog list signed by the private key of the identity service. Therefore, PKI
tokens are very long, and in practice can exceed 8k bytes, which does not fit
in an HTTP header by default. The motivation was to minimize the need for
database access in Keystone. At first glance, Keystone does not need to store
PKI tokens. A PKI token can be verified by anyone who has the public key of
Keystone. OpenStack services do not need to get in touch with Keystone to
discover the privileges of a PKI token. However, in practice, this is not
accurate: A service still needs to check a token with Keystone to see if it is
not revoked; Keystone has to keep the revoked tokens in a database (or similar
structure).

PKIz is the compressed version of PKI that was an effort to make PKI tokens
small. Nevertheless, this technique did not help much, and PKIz tokens were
only 10 percent smaller than PKI tokens in real usages. Because of all the
disadvantages described above, the OpenStack community abandoned the PKI and
PKIz tokens.

##### Fernet

In 2013, Heroku introduced its secure message transmission method that was
called Fernet. They encrypted a message and concatenated the ciphertext with
the HMAC of the ciphertext and called the resultant a Fernet token. In 2015,
the Keystone core team adapted the Fernet token for OpenStack. OpenStack Kilo
is the first release of OpenStack that supports Fernet token, and nowadays, it
is the most used token format.

In OpenStack, Fernet tokens contain a payload that is encrypted and
symmetrically signed by Keystone’s secret key. The payload usually includes
the expiration time of the token, the Id of the owner, an Audit Id, and the
scope of the token. Any Keystone node that has the secret key can validate a
Fernet token and extracts the payload. The main advantage of Fernet tokens is
that there is no need for a database (backend) for storing and validating
them. These features made the Fernet format the most successful token format
in OpenStack.

##### JWS

The OpenStack Stein adapts the JSON Web Signature (JWS) token format that is a
subtype of JSON Web Token (JWT)[4]. Each JWS token contains a header, a
payload, and the signature of the token. The OpenStack uses ES256 JSON Web
Algorithm with a private key for signing JWS tokens. Hence, who has the
corresponding public key can verify a JWS token. We can say that the JWS
format is the updated version of the PKI format. Unlike PKI tokens, JWS tokens
contain little data, and the payload of a JWS token is not encrypted.
Consequently, a JWS token is much shorter than a PKI token. However, it is
still about twice as larger as a Fernet token. Like Fernet tokens, JWS tokens
are ephemeral; this means we do not need to store them in a token database and
replicate the database across all Keystone nodes. There is no apparent
preference between Fernet and JWS.

###  2.3 Fernet Tokens

The Fernet format is the base of our solution, and understanding how it works
is essential. Hence, we describe Fernet in more detail here. Keystone needs a
Fernet key to generate Fernet tokens. A Fernet key is a base64 URL safe string
composed of a signing key and an encryption key. If we decode a Fernet key, we
will have a 32-byte array, which the first half (128 bits) is the signing key,
and the second half is the encryption key 222It is possible to use larger key.
Since OpenStack uses a fresh key every 1 hour, the OpenStack community
believes that a 128 bit key for encryption and 128 bit key for HMAC provide
enough security.. Fernet utilizes symmetric-key cryptography as follows:

  1. 1.

SHA256 HMAC for signing.

  2. 2.

AES 128 in CBC mode with a 128-bit Initialization Vector(IV) for encrypting
the payload of a token

If we have a close look into a Fernet token, we can distinguish five parts:

Version:

The first byte of every Fernet token shows the version of the token. The first
version is denoted by 128 (0x80), and since, there is only one version of
Fernet that has been introduced, we can say every Fernet tokens starts with
the number 128.

Timestamp:

The second part of a Fernet token is a 64-bit unsigned big-endian integer that
represents the creation timestamp of the token in Linux time format.

IV:

IV is a 128-bit random string that is used as the initial vector of AES
encryption.

Ciphertext:

OpenStack Stein has ten different payload types including unscoped, domain
scoped, project scoped, trust scoped, federated unscoped, federated project
scoped, federated domain scoped, OAuth scoped, and system scoped. Depending on
the type, the data in the payload of a token varies. The payload of a token at
least contains the type, the owner, the method that was used for
authenticating the token owner, the expiration time, and the audit Id of the
token. The length of a payload must be a multiple of 128 bits. Hence,
OpenStack uses PKCS #7 v1.5 technique [12] to pad the payload. Then, OpenStack
encrypts the payload.

HMAC:

The last part of a Fernet token is the HMAC of all the four previous parts,
which is calculated by using SHA256 HMAC. This part is known as the signature
of a Fernet token.

##  3 Recursive Augmented Fernet (RAF) Mechanism

As mentioned earlier, in the current authentication mechanisms, whenever an
adversary captures a user token, he can do all the things that the owner of
the token can do (the bearer token problem). Recursive Augmented Fernet (RAF)
mechanism is our solution for the bearer this problem. The solution includes:
RAF, a Policy Enforcer(PE) component, and a Blacklist. This section explains
the solution. The main idea is as follows:

  * •

Each user is granted a Fernet token from the identity module as like as common
OpenStack authentication process, i.e., the user presents his credential to
Keystone and Keystone returns a Fernet token after validating the credential.

  * •

The user keeps the Fernet token secret and does not pass the token to other
modules. For every API request, the user generates a new RAF token using the
Fernet token. The RAF token contains enough information about the API and the
user request, and it is unforgeable. The user puts the RAF token in the header
of the API request instead of the Fernet token.

  * •

Whenever a service receives an API request, it takes the RAF token and
validates the RAF with the identity module. Comparing to the Fernet mechanism,
if the RAF was valid, the identity module returns extra information about the
target API and the user request. The PE verifies if the API request matches
with the information returned by the identity module.

  * •

Whenever a service needs to call another service on behalf of the user, it
derives a new RAF token from the token it has received and uses the new token
for its request.

  * •

Each RAF token carries enough information about a user request. Using this
information and a Blacklist, the identity module only verifies a RAF token
pointing to the user request once for each service.

###  3.1 RAF Tokens

The core of our solution is the RAF token. To explain the RAF structure,
first, we define the following terms:

Root Token:

is a Fernet token that a user obtains from Keystone and uses to generate RAFs.
$T_{0}$ represents a root token.

Base-RAF:

is a RAF token derived from a root token by users. $T_{1}$ represents a base-
RAF.

Service-RAF:

is a RAF token that is derived from a base-RAF or another service-RAF.
Service-RAFs are generated by the internal services and denoted by $T_{i}$
where $i>1$.

Parent token:

If a token $T_{i}$ is derived from $T_{i-1}$, we say $T_{i-1}$ is the parent
of $T_{i}$.

Child token:

If a token $T_{i}$ is derived from another token $T_{i-1}$, we say $T_{i}$ is
a child of $T_{i-1}$.

RAF digest:

In a big picture, a Fernet or RAF token $T_{i}$ is a message $m_{i}$
concatenated with the HMAC of the message under a certain key. Hence, we can
represent a token $T_{i}=m_{i}\parallel HMAC(m_{i})$. In our solution, the
$HMAC(m_{i})$ is called the RAF digest of a token and denoted by $H_{i}$.
Hence, we may write $T_{i}=m_{i}\parallel H_{i}$ where $H_{i}=HMAC(m_{i})$.

Parent Message:

If $T_{i}=m_{i}\parallel H_{i}$ was derived from the token
$T_{i-1}=m_{i-1}\parallel H_{i-1}$, then $m_{i-1}$ is the parent message of
$T_{i}$.

####  3.1.1 Structure

We define the following structure for a RAF token:

$V\parallel L^{m}_{i-1}\parallel m_{i-1}\parallel E_{i}\parallel
R_{i}\parallel C_{i}\parallel H_{i},$ (1)

where

Version ($V$):

A byte shows the version of the token. We identify the first version by 0x91.
This field enables a system to support multiple versions of RAFs in the
future.

Length-of-parent-message ($L^{m}_{i-1}$):

To extract the parent message of a token, we need to know its length. This
field of a short integer (2 bytes) determines the length of the parent message
in bytes.

Parent-message ($m_{i-1}$):

The authentication module needs to extract the parent message of a token to
verify the token.

Expiration-Time ($E_{i}$):

It is a 64-bit unsigned big-endian integer, which shows the expiration time of
the token. It is calculated based on the number of seconds past January 1,
1970.

Randomizer ($R_{i}$):

A 64 bit random number used to randomize a RAF token. Without this field,
although it is unlikely, two separate RAF tokens can be identical if the same
user simultaneously issues them using a single Fernet token for the same
purpose with the same parameters.

Command ($C_{i}$):

This is the command that we want to execute using the token.

HMAC ($H_{i}$):

This field is a 256-bit SHA256 HMAC that is used for authenticating the
content of a token. The signing key of the HMAC and the fields included in the
HMAC varies based on the token type explained in the following section.

####  3.1.2 Variations

We introduce two types of RAFT: 1- User-tied RAFT (UT-RAFT) 2- Fully-tied RAFT
(FT-RAFT). The structure of both tokens is the same. But, they use different
signing keys and includes different fields in HMAC as follows:

User-tied RAF:

In this type, to derive a token from a parent token (received token), we take
the first 128 bits of the parent key and use it for signing the new token. The
HMAC field is the HMAC of all the fields prior to it in the token. This
approach guarantees the authenticity of the user command carried in a RAF
token.

Fully-tied RAF:

In this type, the process of issuing a new RAF token for a user is the same as
User-tied version. But, each service has a long-term symmetric key shared with
the identity module and uses this key for signing tokens. The HMAC field is
the HMAC of all the fields prior to it in the token plus the parent key of the
token. Consequently, the RAF token is tied to the command and the service, and
the identity module can verify the authenticity of the user and services who
have contributed in a RAF token.

Figure 2 shows the effect of a leaked token in two types of RAF with an
example. In the example, the user issues the token $T_{1}$ for her command
(request) $C_{1}$ and sends $T_{1}$ to the service $A$. To accomplish $C_{1}$,
$A$ needs to send the $C_{2}$ and $C_{3}$ commands to $B$ and $C$,
respectively. As shown in the picture, $T_{1}$ is leaked to the adversary. In
the Fully-tied RAF, the adversary can not forge any valid RAF token using
$T_{1}$, but in the User-tied RAF, the adversary can forge several valid RAF
tokens. However, the point is that all of them carry $C_{1}$, and if the
adversary put a command that does not align with $C_{1}$, the PE component
(described later in this chapter) will reject the token.

(a) Fully-tied RAF.

(b) User-tied RAF.

Figure 2: The effect of a leaked token in two types of RAF.

The advantage of the fully tied token over the user tied token is that:

  * •

It guarantees stronger security (see section 4).

  * •

It is not (computationaly) possible to forge a RAF token on behalf of a module
unless the module was corrupted.

However, since in fully tied RAF, each module must have a secret key shared
with the identity module, we need to adopt a proper key distribution and key
renewal mechanism, which in turn it induces extra efforts. While we possess
the knowledge of how to perform key renewal [13, 14, 15], the challenge lies
in determining an appropriate key renewal and management strategy for large
communities like OpenStack, which entails reaching a consensus within the
OpenStack community regarding the security posture that the key renewal
methodology should adopt. The user-tied RAF does not require such discussion.
The fully-tied RAF needs an adaptation/extension of a/current key renewal
practice.

####  3.1.3 Generation

Algorithms 1 and 2 show the steps for issuing a user-tied RAF token, and
algorithms 1 and 3 represent the steps for issuing a fully-tied RAF token. In
both RAF variants, users run the same algorithm. As shown in the algorithms,
given a parent token $Token=Pm\parallel Pkey$, a command $Cmd$, the life time
$LifeTime$, and the service keys $KeySet$ (for Fully-tied RAF), we follow the
underneath steps to issue a RAF token:

  1. 1.

Unpack the parent token and get the parent message and parent key.

  2. 2.

Choose the proper signing key

  3. 3.

Put the value 0x91 in the version field.

  4. 4.

Set the Length of the parent message field.

  5. 5.

Set the parent message.

  6. 6.

Add the token life time to the current time and put the result in the
expiration-time field.

  7. 7.

Choose an eight-byte random number for the randomizer field.

  8. 8.

Set the command.

  9. 9.

For user-tied token: Compute the HMAC of all above fields using the parent-
key.

  10. 10.

For fully-tied token: Compute the HMAC of all above fields plus the parent key
using the secret key of the service

  11. 11.

Base64url encode the entire token.

Function  _UserIssue(Key, Pm, Cmd, LifeTime)_

$SignKey=HMAC(Key,Pm)$
$V=0x91$
$L=Length(Pm)$
$E=GetCurrentTime()+LifeTime$
$R\leftarrow Gen(1^{128})$
$Payload=V\parallel L\parallel Pm\parallel E\parallel R\parallel Cmd$
$Signature=HMAC(SignKey,Payload)$
$Token=base64.Encode(Payload\parallel Signature)$
return $Token$

End Function

Algorithm 1  Pseudocode of Issuing a user-tied/fully-tied RAF token by a User.

Function  _ServiceIssue(Key, Token, Cmd, LifeTime)_

if  _$Verify(Key,Token)=1$_ then

$(Pm,PKey)=Unpack(Token)$
$V=0x91$
$L=Length(Pm)$
$E=GetCurrentTime()+LifeTime$
$R\leftarrow Gen(1^{128})$
$Payload=V\parallel L\parallel Pm\parallel E\parallel R\parallel Cmd$
$Signature=HMAC(PKey,Payload)$
$Token=base64.Encode(Payload\parallel Signature)$
return $Token$

else

return $nothing$

end if

End Function

Algorithm 2  Pseudocode of Issuing a user-tied RAF token by Services.

Function  _ServiceIssue(i,KeySet, Token, Cmd, LifeTime)_

if  _Verify( $k_{0}\in KeySet$,Token)=1_ then

$Pm,PKey\leftarrow Unpack(Token)$
$SignKey=k_{i}\in KeySet$
$V=0x91$
$L=Length(Pm)$
$E=GetCurrentTime()+LifeTime$
$R\leftarrow Gen(1^{128})$
$Payload=V\parallel L\parallel Pm\parallel E\parallel R\parallel Cmd$
$Signature=HMAC(SignKey,Payload\parallel PKey)$
$Token=base64.Encode(Payload\parallel Signature)$
return $Token$

else

return $nothing$

end if

End Function

Algorithm 3  Pseudocode of Issuing a fully-tied RAF token by services.

In section 5, we show the implementation of algorithms 1 and 2 in Python code.

####  3.1.4 Verification

Algorithm 4 shows pseudocode of a user-tied RAF token Verification. Given the
secret key of Keystone $k_{keystone}$ and a token, to verify that the token is
a valid user tied token and recover all the commands embedded in the token,
perform the following steps, in order:

  1. 1.

base64url decode the token.

  2. 2.

If the first byte of the token is not 0x91, then the token is not valid.
Therefore, raise an exception error.

  3. 3.

Unpack the token.

  4. 4.

Check the expiration time of the token in $m_{i}$.

  5. 5.

Using the length-of-parent-message field (second and third bytes), retrieve
$m_{i-1}$. If $m_{i-1}$ is a RAF-message (i.e. its first byte is 0x91), check
the expiration time of $m_{i-1}$ and retrieve $m_{i-2}$ from $m_{i-1}$.
Recursively continue this step until you get $m_{0}$ ,which must be a Fernet-
message (i.e. its first byte must be 0x80).

  6. 6.

Calculate $key_{0}=HMAC(k_{keystone},m_{0})$

  7. 7.

Having $key_{0}$, backtrack step 5 and calculate all parent keys
$\\{key_{1},\cdots\,key_{i-1}\\}$ computing $key_{j}=HMAC(key_{j-1},m_{j})$.

  8. 8.

Having $key_{i-1}$, recalculate the HMAC of the given token. If the calculated
HMAC is equal with the HMAC of the given token, then verify the original
Fernet token $m_{0}\parallel key_{0}$.

  9. 9.

Extract the Fernet message from $m_{0}$ and all commands from
$\\{m_{1},\cdots,m_{i}\\}$ and return them.

Function  _Verify(Key, Token)_

$Token=base64.decode(Token)$
$V,L,Pm,E,R,Cmd,Tag\leftarrow Unpack(Token)$
if  _$V=0x91$_ then

$CheckExpirationTime(E)$
$Cmds,PKey=ValidateParent(Key,Pm)$
$AccomulateCommands(Cmds,Cmd)$
if  _$HMAC(PKey,V\parallel L\parallel Pm\parallel E\parallel R\parallel
Cmd)=Tag$_ then

return $Valid,Cmds$

else

return $Invalid$

end if

else

return Invalid;

end if

End Function
Function  _ValidateParent(Key,Message)_

if  _First byte of Message is $0x91$_ then

$(V,L,Pm,E,R,Cmd\leftarrow Unpack(Message)$
$CheckExpirationTime(E)$
$Cmds,PKey=ValidateParent(Key,Pm)$
$AccomulateCommands(Cmds,Cmd)$
$Tag=HMAC(PKey,V\parallel L\parallel Pm\parallel E\parallel R\parallel Cmd)$
return $Cmds,Tag$

else

return $"",HMAC(Key,Message)$

end if

End Function

Algorithm 4  Pseudocode of a user-tied RAF token Verification

Verification of a fully-tied RAF token is slightly different from Verification
a user-tied token. In fully-tied RAF, each service also has a secret key, and
service uses its secret key to sign tokens. Algorithm 5 is the pseudocode for
a fully-tied token verification. Given all the secret keys of the
authentication module and other services $KeySet=\\{k_{0},\cdots,k_{n}\\}$ and
a token, to verify that the token is a valid fully tied token and recover all
the commands embedded in the token, perform the following steps, in order:

  1. 1.

base64url decode the token.

  2. 2.

If the first byte of the token is not 0x91, then the token is not valid.
Therefore, raise an exception error.

  3. 3.

Unpack the token.

  4. 4.

Check the expiration time of the token in $m_{i}$.

  5. 5.

Using the length-of-parent-message field (second and third bytes), retrieve
$m_{i-1}$. If $m_{i-1}$ is a RAF-message (i.e. its first byte is 0x91), check
the expiration time of $m_{i-1}$ and retrieve $m_{i-2}$ from $m_{i-1}$.
Recursively continue this step until you get $m_{0}$ ,which must be a Fernet-
message (i.e. its first byte must be 0x80).

  6. 6.

Calculate $tag_{0}=HMAC(k_{0},m_{0})$, where $k_{0}$ is the secret key of
Keystone.

  7. 7.

Having $tag_{0}$, backtrack step 5 and calculate all the tags of ancestor
tokens $\\{tag_{1},\cdots\,tag_{i-1}\\}$ computing
$tag_{j}=HMAC(k_{j},m_{j}\parallel tag_{j-1})$.

  8. 8.

Having $tag_{i-1}$, recalculate the HMAC of the given token. If
$HMAC(k_{i},m_{i}\parallel tag_{i-1})=tag_{i}$, then verify the original
Fernet token $m_{0}\parallel tag_{0}$.

  9. 9.

Extract the Fernet message from $m_{0}$ and all commands from
$\\{m_{1},\cdots,m_{i}\\}$ and return them.

Function  _Verify(KeySet, Token)_

$Token=base64.decode(Token)$
$(V\parallel L\parallel Pm\parallel E\parallel R\parallel Cmd\parallel
Tag)\leftarrow Unpack(Token)$
if  _$V=0x91$_ then

$CheckExpirationTime(E)$
$k_{i}=FindServiceKey(Cmd)$
$Cmds,PTag=ValidateParent(KeySet,Pm)$
$AccomulateCommands(Cmds,Cmd)$
if  _$HMAC(k_{i},V\parallel L\parallel Pm\parallel E\parallel R\parallel
Cmd\parallel PTag)=Tag$_ then

return $Valid,Cmds$

else

return $Invalid$

end if

else

return Invalid;

end if

End Function
Function  _ValidateParent(KeySet,Message)_

if  _First byte of Message is $0x91$_ then

$(V\parallel L\parallel Pm\parallel E\parallel R\parallel Cmd)\leftarrow
Unpack(Message)$
$CheckExpirationTime(E)$
$k_{i}=FindServiceKey(Cmd)$
$Cmds,PTag=ValidateParent(KeySet,Pm)$
$AccomulateCommands(Cmds,Cmd)$
$Tag=HMAC(k_{i},V\parallel L\parallel Pm\parallel E\parallel R\parallel
Cmd\parallel PTag)$
return $Cmds,Tag$

else

return $"",HMAC(k_{0},Message)$

end if

End Function

Algorithm 5  Pseudocode of a fully-tied RAF token verification

###  3.2 Blacklist

The Blacklist not only prevents replay attacks, it also guarantees that each
module serves at most once for every user command. Every RAF token is either a
base-RAF token or has been derived from a base-RAF token. Hence, we can say
every valid RAF token has a unique base-RAF token. We want each base-RAF token
to be a permit for only one task in the system. For example, if a user
generates a base-RAF for accessing an image, we should guarantee that the
image will be accessed at most once using this user-RAF. To do so, we propose
to implement a blacklist mechanism in the token validation process. Each entry
in the blacklist is a tuple $(B,S,E)$ that is added to the list upon a
successful token validation where:

$S$:

is the service who asked the authentication module to validate the token $T$.

$B$:

is the base-RAF of $T$.

$E$:

is the expiration time of $B$.

When $S$ asks the authentication module to validate $T$, it extracts $B$ out
of $T$. It also extracts the expiration time $E$ out of $B$. Since for
executing user commends each module needed at most once, Keystone only
validates a token when its corresponding tuple $(B,S,E)$ was not in the
blacklist. Keystone periodically cleans up the blacklist and keeps only the
tuples that have not been expired. A tuple $(B,S,E)$ is expired when $E$ is
less than system time. Since the lifetime of a RAF token is usually very
short, a lightweight memcache structure works fine.

###  3.3 Policy Enforcer

If the adversary obtains a user tied RAF token, he/she can produce children of
the token. Also, in fully tied RAF, if the adversary knows the secret key of a
module (corrupts the module), he/she can generate children for the tokens sent
to the module. RAF (either user tied or fully tied) excludes an adversary to
produce a token without knowledge of one of its parents/ancestors. The policy
enforcer is used to make sure that the command embedded in a RAF token is
consistent and obeys a proper execution flow (specified by a policy). This
means that even though an adversary can create child tokens, he/she can only
do so using commands that fit the policy enforcer. Figure 3 demonstrates the
idea using OpenStack. Here, the user creates a token $T$ for the “list image"
command and sends it to Glance, which is compromised by the adversary. Hence,
the adversary can create a child token like $T^{\prime}$. If the adversary
adds an arbitrary command like “delete a server" to the new token, and sends
the token to Nova, since the "delete server" command does not relate the “list
image" command, the policy enforcer of Nova will reject the request.

Figure 3: Demonstration of the usage of Policy Enforcer

The policy enforcer completes our solution.

##  4 Security Guarantees

The aim of RAFT tokens is to prevent an adversary from sending a request to a
modular system on behalf of the user. At a high level, a RAF token is an
algorithm that gets a message as an input and outputs a token. Security is
formulated by requiring that no adversary can generate a valid token on any
new message. For user tied RAF token, a new message is considered to be any
message that the message itself or its ancestors was not previously sent by a
user or other modules. For fully tied RAF, only the message itself should not
be previously sent by user or other modules.

In this section we want to define the security that each type of RAF mechanism
provides. In order to do this we take the following steps:

  * •

First, we present the technical definition of what a user/fully tied RAF is.

  * •

Next, we define an experiment as a game between the RAF mechanism and the
adversary. The experiment shows how an adversary interacts with the mechanism
and in which circumstances the adversary may successfully forge a RAF token
and win the game.

  * •

Using this game and the technical definition of RAF mechanism, we provide the
definition of the RAF token security. The definition states that no PPT
adversary should win the game with non-negligible probability.

  * •

Finally, we construct a secure user/fully tied RAF using the algorithms
defined in section 3.1.3 and define a lemma which indicates that our
construction is secure and unforgeable against a chosen-message attack.

The RAF token comes into two flavors, user tied and fully tied RAF token. In
section 4.1 we argue about the security guarantees of user tied RAF mechanism
while in section 4.2 we focus on the security of fully tied RAF.

###  4.1 The Security Analysis of User Tied RAF

A user tied RAF token prevents the adversary from impersonating a legitimate
user. Before defining the security features of this mechanism, we first
provide a technical definition of user tied RAF. Technically, a user tied RAF
is made up of four algorithms $Gen$, $UserIssue$, $ServiceIssue$, and $Ver$.
The algorithm $Gen$ generates a secret key; we assume that upon input the
security parameter $\lambda$, the algorithm $Gen$ outputs a uniformly
distributed string of length $\lambda$. The algorithms $UserIssue$ and
$ServiceIssue$ receive a message/token ($p$/$r$), a command $c$ and a key $k$
as an input and generate a token. $UserIssue$ is used by the user dashboard
while $ServiceIssue$ is used by the other services. Finally, the algorithm
$Ver$ receives a token $r$ and a key $k$ and outputs either 1 (meaning valid)
or 0 (meaning invalid). In the following we have the formal definition:

######  Definition 1.

A User-tied RAF token is a quadruple $\Pi=(Gen,UserIssue,ServiceIssue,Ver)$ of
ppt algorithms where:

  * •

$k\leftarrow Gen(1^{\lambda})$ , where $Gen$ generates a key $k$ with security
parameter $\lambda$

  * •

$r_{0}=(m_{0},t_{0})\leftarrow UserIssue(k,p,c_{0})$, where $UserIssue$
generates a token $r_{0}$ for the root payload $p$ and the command $c_{0}$
with the key $k$.

  * •

$r_{j}=(m_{j},t_{j})\leftarrow ServiceIssue(k,r_{j-1},c_{j})$, where if
$r_{j-1}$ is internally verified by $Ver(k,r_{j-1})$ then $ServiceIssue$
generates a token $r_{j}$ for the input token $r_{j-1}$ and the command
$c_{j}$ with the key $k$; Otherwise it returns nothing.

  * •

$b\leftarrow Ver(k,r_{n}=(m_{n},t_{n}))$, where $Ver$ takes the key $k$ and a
token $r_{n}$. It outputs $b$, with $b=1$ meaning the token is valid and $b=0$
meaning the token is not valid.

  * •

It is called correct if for every $k$ output by $Gen(1^{\lambda})$ and every
token $r$ generated by $UserIssue$ or $ServiceIssue$; it holds $Ver(k,r)=1$.

A user-tied RAF token must provide the following properties:

  * •

Represents a user-command.

  * •

Enables a module to extend a token with a command.

  * •

Prevents an adversary to forge any token except some descendants of the
eavesdropped tokens.

A descendant of a token contains all the commands in the token. If the
adversary adds an irrelevant command to a child token of an eavesdropped
token, it will be rejected by the policy enforcer (see section 3.3) of other
modules. Hence, the ability to forge a child token is tolerated.

Now, we define the following game for a PPT adversary ${\cal A}$, the security
parameter $\lambda$, and a user-tied RAF token
$\Pi=(Gen,UserIssue,ServiceIssue,Ver)$:

######  Game 1.

Forge a User Tied RAF token $ForgeUTT_{{\cal A},\Pi}(\lambda)$:

  1. 1.

$Gen(1^{\lambda})$ generates a key $k$

  2. 2.

The adversary $\cal A$ is given input $1^{\lambda}$ and oracle access to
$Ver(k,.)$, $UserIssue(k,.,.)$, and $ServiceIssue(k,.,.)$ and outputs
$r=(m,t)$. Let $\Phi$ represent the set of all tokens that $\cal A$ has
queried.

  3. 3.

$\cal A$ wins if and only if (1) $Ver(k,r=(m,t))=1$ and (2) $r$ and any of its
ancestors are not in $\Phi$.

  4. 4.

The experiment returns 1 if the adversary wins the game, otherwise it returns
0.

The definition of game 1 covers our goal. It ties a token to the user-command
and allows a service to extend the token with a new command. Since the
adversary has oracle access to $UserIssue$ and $ServiceIssue$, it covers the
situation that the adversary eavesdrops some tokens. It states that no PPT
adversary should be able to generate a valid user-tied RAF token unless he has
seen at least one of its ancestors. This guarantees that the adversary cannot
forge a token with a fake user command.

######  Definition 2.

A user tied token $\Pi=(Gen,UserIssue,ServiceIssue,Ver)$ is unforgeable under
a chosen-message attack, or just secure, if for all PPT adversaries $\cal A$
there exists a negligible function333A function $\displaystyle
f(x):\mathbb{N}\to\mathbb{R}$ is negligible, if for every positive polynomial
$poly(·)$ there exists an integer $N_{poly}>0$ such that for all $x>N_{poly}$;
it holds $\displaystyle|f(x)|<{\frac{1}{{\text{poly}}(x)}}$. negl such that:

$\Pr[ForgeUTT_{{\cal A},\Pi}(\lambda)=1]\leq negl(\lambda).$ (2)

Using definition 1 and algorithms 1, 2, and 4 we construct a user tied RAF
token. We then prove that our construction is a secure user tied RAF.

######  Definition 3.

We say HMAC is secure and indistinguishable from a random function, if for all
probabilistic polynomial-time distinguishers D, there exists a negligible
function $\alpha$ such that:

$\displaystyle|\Pr[D^{HMAC(k,.)}(\lambda)=1]-\Pr[D^{f(.)}(\lambda)=1]|\leq\alpha(\lambda)$
(3)

where $f(.)$ is a random function and $\alpha(\lambda)$ is a negligible
function in $\lambda$.

######  Lemma 1.

Assume that the HMAC used in the Construction 1 is secure and
indistinguishable from a random function. Then, Construction 1 is a secure
user tied token that is unforgable under chosen message attacks.

User Tied RAF

Let HMAC be indistinguishable from a random number. Define
$RAFT=(Gen,UserIssue,ServiceIssue,Ver)$ as follows:

  * •

$Gen(1^{\lambda})$: Upon input $1^{\lambda}$, choose
$k\leftarrow\\{0,1\\}^{\lambda}$

  * •

$UserIssue(k,p,c)$: Upon input key $k$ , payload $p$ and the command $c$
compute $r$ by running Algorithm 1.

  * •

$ServiceIssue(k,r^{\prime},c^{\prime})$: Upon input key
$k\in\\{0,1\\}^{\lambda}$, token $r^{\prime}$ and the command $c^{\prime}$
compute $r$ by running Algorithm 2.

  * •

$Ver(k,r=(m,t))$: Upon input key $k\in\\{0,1\\}^{\lambda}$, token $r$ compute
$b$ by running Algorithm 4.

In this section we only present an informal sketch of the proof of this lemma.
We defer to Appendix A for the full proof.

###### Proof sketch.

Our argument proceeds via a reduction approach. That is, we show how an
adversary breaking construction 1 can be used as a sub routine to violate the
assumption that "HMAC is secure and indistinguishable from a random function."

To be more precise, we first assume, by contradiction, that a polynomial-time
adversary $\cal A$ manages to forge a user tied $RAF$ (breaks construction 1),
i.e. with a non-negligible probability $\epsilon$ s/he is able to win the game
1. Next, we build a new scheme, $RAF^{\prime}$ to be the same as user tied
$RAF$ except that instead of using the $HMAC$ for key $k$ in its algorithms,
i.e. in $UserIssue$ and $Ver$, it uses a random function. We show that this
implies the existence of a polynomial-time algorithm, called distinguisher
$\cal D$, that can distinguish the $HMAC$ from a random one with advantage
$O(\varepsilon)$. This will then imply that $\varepsilon$ must be negligible;
otherwise it will contradict the assumption that $HMAC$ is secure.

More precisely, we show that the user tied $RAF$ is secure and the upper bound
on the probability of forging RAF is about a factor $n$ times $\epsilon$,
where $n$ is the number of commands added in the forged RAFT token. This upper
bound makes sense: Let us consider that a token can at most contain $n$
commands; we can imagine these commands leading to a HMAC chain. In the proof
methodology, the attacker $\cal A$ can be successful in impersonating any spot
in the chain by using the command $c_{i}$. This means that there are $n$
possibilities and thus the upper bound is a factor of $n$. By observing that
$n=poly(\lambda)$ for a PPT adversary $\cal A$ the proof is completed. ∎

Discussion. Lets assume that the HMAC which is used in the implementation has
$\alpha(\lambda)=\frac{1}{2^{\lambda}}$, then the lemma gives a concrete
security statement with
$\epsilon(\lambda)\leq(n+1)\cdot\frac{1}{2^{\lambda}}+\frac{1}{2^{\lambda}-C}$
where $n$ is the number of modules in the system and $C=poly(\lambda)$ is the
adversary’s maximum number of queries. Note that because of the blacklist
component, $n$ can not be more than the number of modules in a system.

We introduce the notation $\alpha_{C}(\lambda)=\frac{1}{2^{\lambda}-C}$. This
implies that $\alpha(\lambda)<\alpha_{C}(\lambda)$. In the case that the
adversary has made $C$ queries to the HMAC(k,.) vs f(.) oracle, then we can
say,
$\epsilon(\lambda)\leq(n+2)\cdot\alpha_{C}(\lambda)=(n+2)\cdot\frac{1}{2^{\lambda}-C}$.
If key $k$ does not change for a long time, this implies that the adversary
can make more queries to the oracle $\cal O$ ($C$ gets too large) and
therefore, $\epsilon$ gets too large, i.e. the adversary’s chance of winning
the game increases. In order to keep $\epsilon$ low, we must implement key
renewal strategy in Keystone. In fact, OpenStack has this strategy implemented
and by default Keystone’s key is changed every one hour.

Statement. The implementation of the discussed and proven secure $RAF$
mechanism provided in section 5, is a one-time token

In order to have a one-time $RAF$ token, we have considered and implemented an
additional component; Blacklist. The blacklist, ensures that each module
cannot request a validation for the same token more than one time.The
blacklist component must be added to the authentication module and functions
as follows: Each time the authentication module receives a token, first, it
checks if the token is valid, i.e. the $Ver$ function outputs $1$, if so, then
it checks if the pair (base-RAF, service id) is in the blacklist. If not, then
the authentication module returns valid, otherwise returns invalid (for more
detail on blacklist functionality see section 3.2).

This indicates that each token with the same base-RAF token can only be
validated once, which implies that the RAF token implementation is a one-time
token.

###  4.2 The Security Analysis of Fully Tied RAF

The fully tied RAF is similar to user tied RAF except it has an additional
feature which prevents the adversary to send a token on behalf of a service.
In other words, if the adversary is able to get access to a fully tied token,
s/he is not able to send a request on behalf of a (uncorrupted) service to
another service.

In this section we show the security guarantees of a fully tied RAF. We first
provide a technical definition of a fully tied RAF token. Next, we define a
game between the adversary and the fully tied RAF: In this game the adversary
is given an oracle access to the RAF function and is able to make queries. At
some point, the adversary generates a token for a message that he has not
queried. The adversary wins the game if the provided token passes the
validation.
We also give the security definition of fully tied RAF and construct a secure
fully tied RAF using the algorithms in section 3.1.3. Finally, we wrap up this
section with a lemma that shows our construction is secure against chosen-
message attack.

######  Definition 4.

A Fully-tied Token is a quadruple $\Pi=(Gen,UserIssue,ServiceIssue,Ver)$ of
ppt algorithms where:

  * •

$K=(k_{0},\cdots,k_{n-1})\leftarrow Gen(1^{\lambda})$ with security parameter
$\lambda$.

  * •

$r_{0}=(m_{0},t_{0})\leftarrow UserIssue(k_{0},p,c_{0})$ generates a token
$r_{0}$ for root payload $p$ and the command $c_{0}$ with key $k_{0}$.

  * •

$r_{j}=(m_{j},t_{j})\leftarrow ServiceIssue(i,K,r_{j-1},c_{j})$ internally
call $Ver(K,r_{j-1})$ and if $r_{j-1}$ is invalid then it returns nothing;
else generates a token $r_{j}$ for the input token $r_{j-1}$, the service id
$i$, and the command $c_{j}$ with the key $k_{i}$. Note that $ServiceIssue$
consists of two phases: 1- Verification: in which it calls $Ver$ algorithm and
verifies the validity of the token $r_{j-1}$. For this part $K$ is needed. 2-
Token generation: computes a token $r_{j}$ using the key of the service with
service id $i$ (i.e. $k_{i}$).

  * •

$b\leftarrow Ver(K,r_{n}=(m_{n},t_{n}))$, where $Ver$ takes a set of keys $K$
and a token $r_{n}$. It outputs $b$, with $b=1$ meaning the token is valid and
$b=0$ meaning the token is not valid.

  * •

It is called correct if for every $K$ output by $Gen(1^{\lambda})$ and every
token $r$ generated by $UserIssue$ or $ServiceIssue$; it holds $Ver(K,r)=1$.

According to the above definition, a fully tied token gets a payload and
extends it with a command. This definition looks similar to definition 1.
However, an important difference exists: here, each module has its own secret
key, while in definition 1, modules do not own/use any secret keys. This
enable modules to add a new command to the token and sign the token with their
secret keys.

We define the following game for a PPT adversary ${\cal A}$, the security
parameter $\lambda$, and a fully-tied token
$\Pi=(Gen,UserIssue,ServiceIssue,Ver)$:

######  Game 2.

Forge a Fully Tied Token or for short ForgeFTT:

  * •

$K=(k_{0},\cdots,k_{n-1})\leftarrow Gen(1^{\lambda})$ where $n=$Number of
Services in the system.

  * •

The adversary $\cal A$ is given input $1^{\lambda}$ and access to oracles:
$Ver(K,.)$, $UserIssue(k_{0},.,.)$, and $ServiceIssue(i,K,.,.)$ and knows keys
$k_{i}$ for $i\in I\subseteq\\{1,\ldots,n\\}$. Let $\Phi$ represent the set of
all tokens that $\cal A$ has requested. Eventually, the adversary outputs
$r=(m,t)$.

  * •

$\cal A$ wins if and only if (1) $Ver(K,r=(m,t))=1$, (2) $r\notin\Phi$, and
(3) $r$ is not an output of $ServiceIssue(i,K,.,.)$ for some $i\in I$.

  * •

The experiment returns 1 if the adversary wins the game, otherwise it returns
0.

This game is exactly the same as game 1 with one extra condition in Step 3,
which is "$r$ is not an output of $ServiceIssue(i,K,.,.)$ for some $i\in I$".

######  Definition 5.

A fully tied token $\Pi=(Gen,UserIssue,ServiceIssue,Ver)$ is unforgeable under
a chosen-message attack, or just secure, if for all PPT adversaries $\cal A$
there exists a negligible function negl such that:

$\Pr[ForgeFTT_{{\cal A},\Pi}(\lambda)=1]\leq negl(\lambda)$ (4)

A secure fully-tied token guarantees the authenticity of the user and service
commands embedded in a token, i.e., not only the adversary can not forge a
token with a fake user-command, he also can not forge a valid token on behalf
of any service, unless he corrupts the service (knows the secret key of the
service).

######  Lemma 2.

Assume that the HMAC used in Construction 2 is secure and indistinguishable
from a random function. Then, Construction 2 is a secure fully tied token that
is unforgable under chosen message attacks.

Fully Tied Token RAF

Let HMAC be indistinguishable from a random number. Define a Fully Tied Token
$\widehat{RAFT}=(Gen,UserIssue,ServiceIssue,Ver)$ as follows:

  * •

$Gen(1^{\lambda})$: Upon input $1^{\lambda}$, choose
$K=(k_{0},k_{1},...,k_{n-1})\leftarrow\\{0,1\\}^{\lambda}$ where $n=$Number of
Services in the system.

  * •

$UserIssue(k_{0},p,c)$: Upon input key $k_{0}\in\\{0,1\\}^{\lambda}$, payload
$p$ and the command $c$ compute $r$ by running Algorithm 1.

  * •

$ServiceIssue(i,K,r^{\prime},c)$: Upon input key
$K=\\{k_{0},k_{1},...,k_{n-1}\\}\leftarrow\\{0,1\\}^{\lambda}$ , token
$r^{\prime}$ and the command $c$ compute $r$ by running Algorithm 3.

  * •

$Ver(K,r=(m,t))$: Upon input key set
$K=\\{k_{0},k_{1},...,k_{n-1}\\}\leftarrow\\{0,1\\}^{\lambda}$, token $r$
compute $b$ by running Algorithm 5.

We defer to Appendix A for the full proof. Here, we simply highlight the main
ideas involved in the proof.

###### Proof sketch.

The intuition behind the proof of this lemma is the same as lemma 1. Here, our
argument also proceeds via reduction approach.

We argue that the only way for an adversary to win the game is to either
generate a valid token which is a result of $UserIssue$ or a valid token which
is the result of $ServiceIssue$. Next, we show that a tokens generated by
$UserIssue$ can be represented as a user tied RAF token with exactly one
command and tokens generated by $serviceIssue$ can be represented by a user
tied RAF token with no command. This argument enables us to use lemma 1 to
prove the security of the fully tied RAF and show its upper bound. ∎

Discussion. For fully tied RAF the upper bound on the probability of
successfully forging a token is much more tight than the upper bound for user
tied RAF. This is reasonable because in this type of RAF mechanism, each
service has its own secret key for applying the $HMAC$. This means even if the
adversary gets access to a valid token, he is not able to generate a valid
token on behalf of an uncorupted service.

##  5 Proof of Concept

To illustrate a proof of concept, we utilize OpenStack as the testbed for our
proposal. We have developed a Python library that enables us to:

  * •

Issue a user-tied RAF token, given a Fernet token or another user-tied RAF
token.

  * •

Validate a user-tied RAF by providing the Fernet key and retrieving all
commands within the user-tied RAF token.

We also modified Keystone to accept and validate user tied RAF tokens. In the
rest of this chapter, we explain the details of our experiments.

###  5.1 Experiment platform

Using KVM, we set up a Virtual Machine (VM) with 4 vCPUs and 8GB vRAM. The
physical host was a DELL XPS 9530 laptop taking advantage of an Intel Core(TM)
i7-4712HQ CPU @ 2.30GHz with 16GB memory and 250GB SSD. The operating system
of the host and virtual machine were Ubuntu 18.04.3 LTS. We had installed
OpenStack Stein on our VM using DevStack script.

###  5.2 RAFT Library

Snippet B represents the user tied RAF library. It contains two classes:

  * •

KeystoneRaft: this class encapsulates several methods to validate RAF tokens.
Some of its important methods are:

    * –

isRAFT: gets a token and returns true if the token was a RAF token.

    * –

CheckExpirationTime: gets a token and checks its expiration time. If the token
is expired, then it raises an exception error.

    * –

GetKey: This method is used internally to find the key of the token.

    * –

ValidateRAFT: gets a RAF token and checks if it is valid or not. If the token
was valid, this function returns all the commands inside the token. Also, it
sets the fernet_token property of the class.

  * •

ClientRaft: this class allows clients and other modules to create a new RAF
token for their requests. The main methods of this class are:

    * –

__init__: this is the constructor of the class and allows us to define the
parent token of the RAF token, which we want to create.

    * –

SetParentToken: Allows to set or change the parent token.

    * –

SetCommand: Is used to set the command that will be a part of the token.

    * –

Finalize: generates and returns a RAF token based on the parent token and the
command that had been set.

###  5.3 The required changes

If you install OpenStack with its default setting, the source code of Keystone
will be at /opt/stack/keystone folder. Let’s call this folder the base folder.
Then, our library must be added to the following folder: base
folder/keystone/token The source code of Fernet token must be at: base
folder/keystone/token/providers/fernet In the fernet folder, there is a file
token_formmater.py, which contains the entry point for the Fernet library. We
added the following code at the library importing section of the file (at the
beginning of the file): import RAFT Then, we modified the validate_token
function of TokenFormatter class, as shown in snippet B. When this function is
called, we first check the input token. If it is a RAF token, then we process
it using an instance of KeystoneRAFT class. Upon successful validation, we
extract the original Fernet token and assign it to the token. In this way, the
rest of the function checks the privileges of the root Fernet token. At the
end of the function, if the input token was a RAF token, we adjust the
expiration time of token according to the shortest expiration time in the RAF
token.

After applying the changes to source code, the Keystone service must be
restarted. Do not restart the virtual machine. If you do so, you need to
uninstall OpenStack and try to install it again. In order to restart the
Keystone service execute the following command in the Linux terminal.
systemctl restart<EMAIL_ADDRESS>
###  5.4 Comparison Between RAF and Fernet Tokens’ Creation and Validation
Time

Table 1 shows the average time (in milliseconds) needed for creation and
verification of a token, deviation, deviation to above, and deviation to
bellow the average. If we use the Fernet token mechanism, the creation and
validation time is always near the average in row 1. In the RAFT mechanism,
whenever a user wants to issue a new command, he needs to create a new RAF
token from a Fernet token. By default, each Fernet token is valid for an hour.
Hence, when the user grants a Fernet token, he can use it to create new RAF
tokens locally for one hour. In the statistic about RAF, we also include the
time of granting a Fernet token.

# |  Token Type | Average | dev. | dev. to above | dev. to bellow
---|---|---|---|---|---
1 |  Fernet | 76.54 | 9.39 | 8 | 0
2 |  RAF, 1¶ | 79.24 | 13.38 | 4 | 2
3 |  RAF, 2 | 56.79 | 3.02 | 12 | 11
4 |  RAF, 10 | 40.83 | 1.57 | 9 | 6
5 |  RAF, 50 | 37.88 | 0.81 | 13 | 15
6 |  RAF, 100 | 37.21 | 0.64 | 13 | 13
¶: The number indicates the number of tokens issued per hour.
Table 1: Execution time in milliseconds for generating and validating of a
token based on 100 sample.

As mentioned earlier, one idea for mitigating the bearer token problem is to
shorten the lifetime of Fernet tokens in a way that there is no time to use it
twice. As our experiment shows, if the user issues more than one command in an
hour (rows 3 to 6), the RAF mechanism works 30 to 50 percent better than the
idea of shortening the lifetime of Fernet tokens.

Table 2 shows the length of the command that we add to a RAF token does not
noticeably effect the average time (in milliseconds) of creation and
verification of a token. For this experiment, we create RAF tokens for
hypothetical commands with 1, 100, 200, and 1000 character length.

# |  Command length | Average | dev. | dev. to above | dev. to bellow
---|---|---|---|---|---
1 |  0 | 40.11 | 5.89 | 8 | 1
2 |  100 | 41.01 | 9.7 | 6 | 0
3 |  200 | 39.34 | 3.94 | 14 | 7
4 |  1000 | 40.78 | 5.02 | 12 | 8
Table 2: The effect of the length of the command (in character) that is added
to a RAF token in generation and verification time in milliseconds based on
100 sample.

###  5.5 Comparison Between RAF and Fernet Tokens’ Creation and Validation
Time

The RAF solution puts a negligible processing overhead over the Fernet
processing time. Since many processes were running on the OpenStack server,
this negligible overhead was not measurable using OpenStack. Hence, we
calculated the overhead locally. In our platform 5.1, issuing 100 RAF tokens
(excluding granting a Fernet token from Keystone) took 8.1 milliseconds, and
verification of just the RAF tokens (excluding the verification of the base
Fernet) took 13.2 milliseconds. These numbers show the extra processing time
needed for a RAF token compare to Fernet token.

Table 3 shows the summary of the first set of our experiments (see the source
code in Snippet B) that focuses on the creation and validation time of user
tied RAF and Fernet token 444The process of issuing and validating a fully
tied RAF token with one command and a user tied RAF token with one command is
exactly the same. The only difference between issuing and validating a fully
tied RAF and a user tied RAF token for more than one commands is that they use
different keys for the HMAC of second and more commands. Hence, we do not
expect any considerable change in the result if we repeat them for fully tied
RAF.. The first set includes the following seven experiments:

  * •

Row #1 shows the execution time for getting 100 Fernet tokens from Keystone.

  * •

Row #2 represent the execution time for getting a Fernet token and generating
100 RAF tokens using the Fernet token.

  * •

Row #3 exposes the execution time for getting and validating of 100 Fernet
tokens.

  * •

Rows #4 to #7 demonstrate the execution time of getting a Fernet token and
issuing 100 RAF tokens with hypothetical commands with 0, 30, 60, and 200
lengths (in character).

To get more reliable results, we repeat each experiment several times, but
because space limitation, we only represent the result of the experiments.

# |  Experiment title | First | Second | Third | Forth | Fifth | Avg
---|---|---|---|---|---|---|---
1 |  Fernet Generation | 4.3519 | 4.3519 | 4.3593 | 4.4529 | 4.4897 | 4.4011
2 |  RAFT Generation | 0.0489 | 0.0519 | 0.0510 | 0.0505 | 0.0481 | 0.0501
3 |  Fernet Generation and validation | 8.9275 | 8.8489 | 8.8471 | 8.5349 | 8.8222 | 8.7961
4 |  RAF token Generation and validation; 0L | 4.6791 | 4.5629 | 4.6725 | 4.6074 | 4.6696 | 4.6383
5 |  RAF token Generation and validation; 30L | 4.6528 | 4.6620 | 4.5986 | 4.6332 | 4.6296 | 4.6353
6 |  RAF token Generation and validation; 60L | 4.6668 | 4.5719 | 4.6438 | 4.7847 | 4.5213 | 4.6377
7 |  RAF token Generation and validation; 200L | 4.6302 | 4.6704 | 4.7203 | 4.5572 | 4.6420 | 4.6440
Table 3: Execution time in seconds for generating and validating of 100 RAF
tokens and Fernet tokens. For creating RAF tokens, we only interact with
Keystone one time and then create 100 RAF tokens locally.

As mentioned earlier, one idea for mitigating the bearer token problem is to
shorten the lifetime of Fernet tokens in a way that there is no time to use it
twice. From row #1 and #2, we can conclude that for token generation, if a
user issues more than one command in a specific period, the RAF solution is
faster than the short-life Fernet token idea. But the creation time is only
one side of the problem. Each token needs to be validate by Keystone. If we
include the validation time (rows #3 to #7), the RAF solution still works at
most 50 percent better if each user issues several commands.

The length of the command that we add to a RAF token has unnoticeable
overhead, as understood from rows #4 to #7. In fact, we repeated the
experiment #4 to #7 much more than five times, and each time we got very close
results.

###  5.6 RAF and Fernet in Action

In the second set of experiments, we examined the effect of using user tied
RAF instead of Fernet tokens in the execution time of four different commands
as follows:

Create volume: is a moderate workload command that creates a volume, i.e., a
permanent memory like a physical disk. Snippet B shows the sample command that
we used for creating a volume. We did not load any image to the volume. If we
want to load an image to the volume, it can be considered as a high load task.

Create VM (server): is a typical command in OpenStack that consumes
significant resources. Snippet B shows the sample command that we used for
creating a VM. In this sample, we used cirros that is an ultra-lightweight
operating system. The cirros operating system (OS) includes a few core
functionalities of a Linux OS and only be used for tests.

Image list: is a light load command that does not need any parameter.

Project list: is another light load command that returns the list of projects
that are available for the owner of the token. This command also does not need
any parameters.

Table 4 represents a comparison between the execution time (in seconds) of the
four different commands using RAF and Fernet tokens. We put the result of five
execution for each command in the table. Based on the result, the overhead of
using RAF instead of Fernet in typical create-server and create-volume
commands is less than 1 percent. Here, we used cirros OS to create a server
that is a very small nonpractical operating system. In a real deployment,
usually creating a VM using an operational OS takes several seconds, and the
RAF overhead is not noticeable in such cases. In general, typical cloud
operations like creating servers, migrating servers, and taking back up of
servers are very time consuming compare to token verification. Hence, we
expect that this overhead will be much less than 1 percent for a real
deployment.

Experiment title | First | Second | Third | Forth | Fifth | Avg | Ratio
---|---|---|---|---|---|---|---
Creating a volume (Fernet) | 0.3243 | 0.3681 | 0.4546 | 0.4396 | 0.4246 | 0.4022 | 1.0078
Creating a volume (RAF) | 0.3583 | 0.4021 | 0.4140 | 0.4313 | 0.4211 | 0.4054
Creating a VM (Fernet) | 0.5208 | 0.5966 | 0.8908 | 2.3995 | 0.6762 | 1.0168 | 1.0030
Creating a VM (RAF) | 0.7032 | 0.7740 | 0.8938 | 2.0452 | 0.6831 | 1.0198
Getting image list (Fernet) | 0.0584 | 0.0571 | 0.0569 | 0.0605 | 0.0526 | 0.0571 | 1.0280
Getting image list (RAF) | 0.0548 | 0.0598 | 0.0616 | 0.0553 | 0.0620 | 0.0595
Getting project list (Fernet) | 0.0293 | 0.0332 | 0.0274 | 0.0296 | 0.0294 | 0.0298 | 1.0326
Getting project list (RAF) | 0.0303 | 0.0323 | 0.0296 | 0.0311 | 0.0305 | 0.0307
Table 4: Comparison between the execution time of four different commands
using RAFT and Fernet tokens

Snippet B shows the source code that we developed for the second set of
experiments.

##  6 Summary

Modularity and modular thinking in developing extensive systems have a pivotal
role. Robust authentication and authorization mechanisms within such modular
frameworks are of importance. This paper focuses on token-based authentication
mechanisms, where users present credentials to obtain tokens for subsequent
interactions with other modules. Tokens have advantages over traditional
username and password authentication, focusing on enhanced security through
reduced password exposure, token expiration, and scoped access. However, they
suffer from a critical vulnerability known as the "bearer token" problem,
where the compromise of user tokens poses significant security risks in
modular systems, leading to a trade-off between system performance and
security.

To address the bearer token problem, the paper introduces a novel token-based
authentication system RAF, which complies with the Modularity Security
Requirement, advocating for a scenario in which, if an adversary corrupts one
module, other modules should only execute user-requested actions without
additional privileges. RAF includes RAF tokens, a Policy Enforcer (PE)
component, and a Blacklist component. The main idea involves users receiving
Fernet tokens from the identity module, generating a RAF token for every
command, embedding the command in the token, and using it instead of Fernet
tokens. The identity module validates RAF tokens in a recursive manner and
extracts all the commands embedded in the token. The PE ensures command
consistency, and the Blacklist prevents replay attacks. RAF tokens have a
determined structure, including commands, and are single-use tokens. Hence, an
RAF token connects the token and the reason for creating the token.

The paper proposes two variations of RAF: User-tied RAF and Fully-tied RAF,
each with distinct security features and requirements. The verification
process and token generation algorithms are detailed. The Blacklist prevents
replay attacks, while the Policy Enforcer ensures command consistency,
completing the solution. The paper discusses the advantages and challenges of
User-tied RAF and Fully-tied RAF, emphasizing security and scalability
considerations.

User-tied RAF tokens are more straightforward to implement and do not require
services to have secret keys. Each module can independently issue RAF tokens
without dependencies on service-specific keys. The absence of service-specific
keys reduces the complexity of key management. They can be quickly adopted in
existing systems without significant changes, making them backward compatible
with systems using traditional Fernet tokens. On the other hand, since they do
not tie tokens to specific services, an adversary who obtains a token can
potentially forge child tokens. However, the Policy Enforcer helps mitigate
this by ensuring command consistency.

Fully-tied RAF tokens provide a higher level of security by tying each token
to a specific service using a service-specific secret key. Fully-tied RAF
ensures that tokens are valid only for the intended service and command.
Hence, it provides additional protection against module corruption. An
adversary cannot forge a valid RAF token on behalf of a module unless the
module itself is compromised. On the other hand, Fully-tied RAF introduces the
challenge of distributing and managing secret keys for each service. The need
for each module to have a secret key shared with the identity module may pose
scalability challenges, particularly in large and dynamic environments.
Consequently, adopting Fully-tied RAF may require significant changes in
existing systems due to the need for service-specific secret keys.

The paper discusses the security guarantees of the two variations of RAF. It
outlines these tokens’ technical definitions, security analyses, and
construction. The security analysis relies on two game-based proofs, assuming
HMAC is a pseudo-random function. Using the games, the paper shows that if
adversaries can break RAF tokens with any probability more than negligible,
they can break the security of HMAC.

The paper demonstrates a proof of concept for User-tied RAF tokens within the
context of OpenStack. The implementation involves modifications to Keystone,
the creation of an RAFT library, and provides details about the experimental
platform and results.

The results include a comparison of the creation and validation times of RAF
and Fernet tokens under various scenarios, as well as the execution time of
specific OpenStack commands using RAF and Fernet tokens. The findings indicate
minimal overhead in typical scenarios, showcasing the viability of RAF tokens.
Additionally, the results highlight the significant advantage of using RAF
over short-life Fernet tokens.

## References

  * [1] K. Hogan, H. Maleki, R. Rahaeimehr, R. Canetti, M. van Dijk, J. Hennessey, M. Varia, and H. Zhang, “On the universally composable security of openstack,” in _Proceedings of the 2019 IEEE Secure Development (SecDev) Conference_. IEEE, 2019.
  * [2] V. U. Srinivasan, R. Angal, and A. Sondhi, “Oauth framework,” Jan. 13 2015, uS Patent 8,935,757.
  * [3] D. Recordon and D. Reed, “Openid 2.0: a platform for user-centric identity management,” in _Proceedings of the second ACM workshop on Digital identity management_. ACM, 2006, pp. 11–16.
  * [4] Auth0, “Json web tokens,” [Accessed Oct., 2019]. [Online]. Available: https://jwt.io
  * [5] M. Jones and D. Hardt, “The oauth 2.0 authorization framework: Bearer token usage,” october, 2012. [Online]. Available: https://tools.ietf.org/pdf/rfc6750.pdf
  * [6] G. Pocentek, “Kerberos authentication for keystone,” february 2018. [Online]. Available: https://www.objectif-libre.com/en/blog/2018/02/26/kerberos-authentication-for-keystone/
  * [7] “Openstack, open source cloud computing infrastructure,” accessed: 2022-04-16. [Online]. Available: https://docs.openstack.org/
  * [8] “Tokens,” accessed: 2022-04-16. [Online]. Available: https://docs.openstack.org/security-guide/identity/tokens.html
  * [9] FeaturedCustomers, “Featured customers that trust openstack,” accessed: 2019-11-15. [Online]. Available: https://www.featuredcustomers.com/vendor/openstack/customers
  * [10] “2019 openstack foundation annual report,” accessed: 2022-04-23. [Online]. Available: https://www.openstack.org/annual-reports/2019-openstack-foundation-annual-report
  * [11] D. Stenberg, “command line tool and library for transferring data with urls,” october, 2019. [Online]. Available: https://curl.haxx.se/
  * [12] B. Kaliski, “Pkcs# 7: Cryptographic message syntax version 1.5,” _The Internet Society (1998)_ , 1998. [Online]. Available: https://tools.ietf.org/html/rfc2315#section-10.3
  * [13] A. Kundu, R. Mahindru, A. Mohindra, V. Salapura, and M. Viswanathan, “Automatic security parameter management and renewal,” Mar. 26 2019, uS Patent App. 10/243,936.
  * [14] C. White and S. Edwards, “Client services for applied key management systems and processes,” May 8 2018, uS Patent 9,967,289.
  * [15] T. Adefarati and R. Bansal, “Integration of renewable distributed generators into the distribution system: a review,” _IET Renewable Power Generation_ , vol. 10, no. 7, pp. 873–884, 2016.

##  Appendix A RAFT Security Guarantees

###  A.1 Proof of Lemma 1

Based on Game 1 we define two other games which we will need for the proof of
Lemma 1:

  * •

Consider $ForgeUTT^{i}_{{\cal A},\Pi}$ to be the notion for forging a token
with exactly $i$ commands. For this, we can define a game that is exactly as
game 1 with one extra condition in Step 3, which is "m contains exactly $i$
commands"

  * •

Consider $ForgeUTT^{\leq i}_{{\cal A},\Pi}$ to be the notion for forging a
token with at most $i$ commands. For this, we can define a game that is
exactly as game 1 with one extra condition in Step 3, which is "m contains at
most $i$ commands"

###### Proof.

The intuition behind the proof of this lemma is that for a PPT adversary,
forging a user tied RAFT without observing any of its ancestors involves
distinguishing the HMAC from a random function.We simplify the descriptions of
algorithms 1, 2, and 4 as follows:

  * •

For the key $k$ and input payload $p$ and the command $c$
$UserIssue(k,p,c)=HMAC(HMAC(k,p),p\parallel c)$

  * •

For the key $k$, input token $r=(m,t)$, and the command $c$

$ServiceIssue(k,r=(m,t),c)=\begin{cases}HMAC(t,m\parallel c)&\quad\text{if
}Ver(k,r)\text{ is valid}\\\ nothing&\quad\text{if }Ver(k,r)\text{ is
invalid}\end{cases}$

  * •

For the key $k$, and the input token $r=(m,t)$, first, $Ver(k,r)$ decomposes
$m$ and gets $\\{p,c_{1},\cdots,c_{n}\\}$, then calculates:

$\displaystyle h_{0}$ $\displaystyle=HMAC(k,p)$ $\displaystyle h_{1}$
$\displaystyle=HMAC(h_{0},p\parallel c_{1})$ $\displaystyle\vdots$
$\displaystyle h_{n}$ $\displaystyle=HMAC(h_{n-1},p\parallel
c_{1}\parallel\cdots\parallel c_{n})$

Then, if $h_{n}=t$, returns valid; otherwise, returns invalid.

Let ${\cal A}$ be a probabilistic polynomial-time adversary and let
$\varepsilon($.$)$ be a function such that:

$\Pr[ForgeUTT_{{\cal A},RAFT}(\lambda)=1]=\varepsilon(\lambda)$ (5)

and let $\Phi$ represent the set of all tokens that $\cal A$ has queried. Now,
we define a new scheme
$RAFT^{\prime}=(UserIssue^{\prime},ServiceIssue^{\prime},Ver^{\prime})$, which
is similar to $RAFT$ except a random function $f(.)$ is replaced with the
first HMACs in $UserIssue$ and $Ver$ algorithms. In other words, HMAC(k,p) is
replaced by f(p).

We show that this implies the existence of a polynomial-time algorithm that
can distinguish the HMAC from a random one with advantage $O(\varepsilon)$.
This will then imply that $\varepsilon$ must be negligible, as required.

We define the notation $RAFT(k,p,c_{1},\ldots,c_{i})$ respectively
$RAFT^{\prime}(k,p,c_{1},\ldots,c_{i})$ to stand for a RAFT/RAFT’ token with
$i$ commands and define $RAFT$ and $RAFT^{\prime}$ as follows:

$RAFT(k,p,c_{1},\ldots,c_{i})=\begin{cases}\leavevmode\resizebox{281.85585pt}{}{$HMAC(RAFT(k,p,c_{1},\ldots,c_{i-1}),p\parallel
c_{1}\parallel\ldots\parallel c_{i})=h_{i}$}&i>0\\\
HMAC(k,p)=h_{0}&i=0\end{cases}$

and

$RAFT^{\prime}(k,p,c_{1},\ldots,c_{i})=\begin{cases}\leavevmode\resizebox{281.85585pt}{}{$HMAC(RAFT^{\prime}(k,p,c_{1},\ldots,c_{i-1}),p\parallel
c_{1}\parallel\ldots\parallel c_{i})=h_{i}$}&i>0\\\ f(p)=h_{0}&i=0\end{cases}$

From $\cal A$ we will now construct a polynomial-time distinguisher $\cal D$
that is given an oracle $\cal O$ that is either of $HMAC(k,.)$ or a random
function $f(.)$. The construction $\cal D$ works as follows:

  * •

Upon input $\lambda$, adversary $\cal D$ passes $\lambda$ to $\cal A$.

  * •

When $\cal A$ queries its oracle $UserIssue(k,.,.)$ with a message
$m^{\prime}=(p^{\prime},c^{\prime})$, $\cal D$ queries $\cal O$ with
$p^{\prime}$ and receives the result $h^{\prime}$. Next, it calculates the
value $t^{\prime}=HMAC(h^{\prime},m^{\prime})$ and hands it to $\cal A$ and
continues.

  * •

When $\cal A$ queries its oracle $Ver(k,.)$ with a message
$r^{\prime\prime}=(m^{\prime\prime},t^{\prime\prime})$, $\cal D$ runs
algorithm 6. Algorithm 6 is exactly the same as algorithm 4 except that
instead of using HMAC to compute $h_{0}$, it uses the oracle $\cal O$. Upon
receiving $b^{\prime\prime}$ from algorithm 6, $\cal D$ hands it to $\cal A$.

  * •

When $\cal A$ queries its oracle $ServiceIssue(k,.,.)$ with a message
$(r^{\prime}=(m^{\prime},t^{\prime}),c^{\prime})$, $\cal D$ runs algorithm 6
with $r^{\prime}$ and gets the response $b^{\prime}$. If $b^{\prime}=0$, $\cal
D$ does nothing. However, if $b^{\prime}=1$, $\cal D$ hands
$HMAC(t^{\prime},m^{\prime}\parallel c^{\prime})$ to $\cal A$ and continues.

At the end, when $\cal A$ outputs $r=(m,t)$, $\cal D$ runs algorithm 6 and
receives $b$. If $b=1$ and $r$ and any of its ancestors are not in $\Phi$,
then $\cal D$ outputs 1. Otherwise it outputs 0.

Function  _Verify(r)_

$(p,c_{0},\cdots,c_{n},t)\leftarrow Unpack(r)$
$i=0$
$h_{0}={\cal O}(p)$
while  _$i\leq n$_ do

$h_{i}=HMAC(h_{i-1},p\parallel c_{0}\parallel\cdots\parallel c_{i})$
$i=i+1$

end while

if  _$h_{n}=t$_ then

return 1;

else

return 0;

end if

End Function

Algorithm 6  Pseudocode of verifying

Since $\cal A$ runs in polynomial time, $D$ also runs in polynomial time. From
the construction of $\cal D$, it is clear that depending on $\cal O$, $\cal A$
either plays $ForgeUTT_{{\cal A},RAFT}$ or $ForgeUTT_{{\cal
A},RAFT^{\prime}}$, and we have:

$\displaystyle\Pr[ForgeUTT_{{\cal A},RAFT}(\lambda)=1]$
$\displaystyle=Pr[D^{HMAC(k,.)}(\lambda)=1]$ (6)
$\displaystyle\Pr[ForgeUTT_{{\cal A},RAFT^{\prime}}(\lambda)=1]$
$\displaystyle=Pr[D^{f(.)}(\lambda)=1]$ (7)

From 3, 6, and 7:

$\displaystyle|\Pr[ForgeUTT_{{\cal A},RAFT}(\lambda)=1]-\Pr[ForgeUTT_{{\cal
A},RAFT^{\prime}}(\lambda)=1]|\leq\alpha(\lambda)$ (8)

The analysis presented so far can be repeated in exactly the same way for the
game $ForgeUTT^{i}$. This gives:

$\displaystyle|\Pr[ForgeUTT^{i}_{{\cal
A},RAFT}(\lambda)=1]-\Pr[ForgeUTT^{i}_{{\cal
A},RAFT^{\prime}}(\lambda)=1]|\leq\alpha(\lambda)$ (9)

Let $\beta(.)$ be a function so that $\Pr[ForgeUTT^{0}_{{\cal
A},RAFT}(\lambda)=1]=\beta(\lambda)$. Since for $i=0$, $RAFT(k,p)=HMAC(k,p)$
and $RAFT^{\prime}(k,p)=f(p)$ this indicates that:

$\displaystyle\Pr[ForgeUTT^{0}_{{\cal
A},RAFT}(\lambda)=1]=\Pr[D^{HMAC(.)}=1]=\beta(\lambda)$

and

$\displaystyle\Pr[ForgeUTT^{0}_{{\cal
A},RAFT^{\prime}}(\lambda)=1]=\Pr[D^{f(.)}=1]=\frac{1}{2^{\lambda}-C}$

where $C=poly(\lambda)$ is the maximum number of queries distinguisher $D$
applies. Therefore,

$\displaystyle\alpha(\lambda)\geq|\Pr[D^{HMAC(.)}=1]-\Pr[D^{f(.)}=1]|\geq\beta(\lambda)-\frac{1}{2^{\lambda}-C}.$

By the assumption that HMAC is secure (i.e. $\alpha(\lambda)$ is negligible)
and because $C=poly(\lambda)$, it follows that $\beta(\lambda)$ is also
negligible in $\lambda$. To be more precise:

$\displaystyle\Pr[ForgeUTT^{0}_{{\cal
A},RAFT}(\lambda)=1]=\beta(\lambda)\leq\alpha(\lambda)+\frac{1}{2^{\lambda}-C}$
(10)

Consider some adversary ${\cal A}_{i+1}$ in $ForgeUTT^{i+1}_{{\cal
A}_{i+1},RAFT^{\prime}}(\lambda)$. This adversary produces a token $r$ with a
chain of ancestors $h_{i}$, where $h_{0}=f(p)$. We can write
$r=([p,c_{1},...,c_{i+1}],t)$ where $t$ is a recursive function $G$ of
$[p,c_{1},...,c_{i+1}]$ and $f(p)$:

$\displaystyle t$ $\displaystyle=$ $\displaystyle
G([p,c_{1},...,c_{i+1}],f(p)),\mbox{ where}$ $\displaystyle G([p,c_{1}],f(p))$
$\displaystyle=$ $\displaystyle HMAC(f(p),p\parallel c_{1}),\mbox{ and}$
$\displaystyle G([p,c_{1},\ldots,c_{i+1}],f(p))$ $\displaystyle=$
$\displaystyle HMAC(G([p,c_{1},...,c_{i}],f(p)),p\parallel
c_{1}\parallel\cdots\parallel c_{i+1}).$

In order to help creating a token $r$ that verifies correctly, only
information about $f(p)$ can help. Since $f$ is a random function,$f(q)$ for
$q\neq p$ does not give any information about $f(p)$, which also means that
$G(.,f(p))$ and $G(.,f(q))$ are statistically independent. Thus, the
information that the distinguisher $\cal D$ provides to the adversary $\cal A$
gives no useful information unless oracle $\cal O$ uses $f(p)$ for its
computations. We can therefore neglect all the oracle accesses that do not
relate to computations with $f(p)$. This gives a new adversary ${\cal A}_{i}$
such that:

$\displaystyle\Pr[ForgeUTT^{i+1}_{{\cal
A}_{i+1},RAFT^{\prime}}(\lambda)=1]=\Pr[ForgeUTT^{i+1}_{{\cal
A}_{i},RAFT^{\prime}}(\lambda)=1]$ (11)

A closer look at the structure of $RAFT$ and $RAFT^{\prime}$ shows that, for
$i\geq 0$,

$\displaystyle\Pr[ForgeUTT^{i+1}_{{\cal
A}_{i},RAFT^{\prime}}(\lambda)=1]=\Pr[ForgeUTT^{i}_{{\cal
A}_{i},RAFT}(\lambda)=1],$ (12)

which follows from the following induction argument: Let $k=f(p)$,
$p^{\prime}=p\parallel c_{1}$, and $c^{\prime}_{j}=c_{j+1}$ for
$j\in\\{1,2,\ldots,i\\}$. As a base case notice that

$\displaystyle RAFT^{\prime}(k,p,c_{1})$ $\displaystyle=$ $\displaystyle
HMAC(f(p),p\parallel c_{1})$ $\displaystyle=$ $\displaystyle
HMAC(k,p^{\prime})$ $\displaystyle=$ $\displaystyle RAFT(k,p^{\prime}).$

Let $i\geq 1$. As an induction hypothesis assume

$RAFT^{\prime}(k,p,c_{1},\ldots,c_{i})=RAFT(k,p^{\prime},c^{\prime}_{1},\ldots,c^{\prime}_{i-1}).$

In exactly the same way as before we can prove the induction step

$\displaystyle RAFT^{\prime}(k,p,c_{1},\ldots,c_{i+1})$ $\displaystyle=$
$\displaystyle HMAC(RAFT^{\prime}(k,p,c_{1},\ldots,c_{i}),p\parallel
c_{1}\parallel c_{2}\parallel\ldots\parallel c_{i+1})$ $\displaystyle=$
$\displaystyle
HMAC(RAFT(k,p^{\prime},c^{\prime}_{1},\ldots,c^{\prime}_{i-1}),p^{\prime}\parallel
c^{\prime}_{1}\parallel\ldots\parallel c_{i})$ $\displaystyle=$ $\displaystyle
RAFT(k,p^{\prime},c^{\prime}_{1},\ldots,c^{\prime}_{i}).$

By using induction in $i$, we conclude that the induction hypothesis holds for
all $i\geq 1$, and (12) follows.

By defining $p_{i}$ and $p_{i}^{\prime}$ as

$\displaystyle p_{i}=\Pr[ForgeUTT^{i}_{{\cal A}_{i},RAFT}(\lambda)=1]\text{
and }p_{i}^{\prime}=\Pr[ForgeUTT^{i}_{{\cal A}_{i},RAFT^{\prime}}(\lambda)=1]$
(13)

we conclude from equations (9) and (13)

$|p_{i}-p_{i}^{\prime}|\leq\alpha(\lambda)$

which in turn proves

$p_{i}\leq\alpha(\lambda)+p_{i}^{\prime}.$

From equations (10) and (13) we have

$p_{0}=\beta(\lambda)$

and from equations (12) and (13) we have:

$p_{i+1}^{\prime}=p_{i}.$

These properties of $p_{i}$ and $p^{\prime}_{i}$ can be combined to prove

$p_{n}\leq\alpha(\lambda)+p^{\prime}_{n}=\alpha(\lambda)+p_{n-1}\leq\ldots\leq
n\cdot\alpha(\lambda)+p_{0}\leq n\cdot\alpha(\lambda)+\beta(\lambda).$

We can now conclude that

$\displaystyle\Pr[ForgeUTT^{\leq n}_{{\cal A}_{i},RAFT}(\lambda)=1]$
$\displaystyle=\max_{i\leq n}\Pr[ForgeUTT^{i}_{{\cal A}_{i},RAFT}(\lambda)=1]$
$\displaystyle\leq\Pr[ForgeUTT^{n}_{{\cal A}_{i},RAFT}(\lambda)=1]$
$\displaystyle\leq n\cdot\alpha(\lambda)+\beta(\lambda).$ (14)

Since the adversary can at most call the oracle $poly(\lambda)$ times,
$n=poly(\lambda)$. In fact, because of the policy enforcer, $n$ can not be
more than the number of modules in a system. Since $\alpha(\lambda)$ and
$\beta(\lambda)$ are negligible functions in $\lambda$ and $n=poly(\lambda)$,
(14) proves the lemma.

∎

###  A.2 Proof of Lemma 2

Based on Game 2 we define two other games which we will need for the proof of
Lemma 2:

  * •

Consider $ForgeFTT^{i}_{{\cal A},\Pi}$ to be the notion for forging a token
with exactly $i$ commands. For this, we can define a game that is exactly as
game 2 with one extra condition in Step 3, which is "m contains exactly $i$
commands"

  * •

Consider $ForgeFTT^{\leq i}_{{\cal A},\Pi}$ to be the notion for forging a
token with at most $i$ commands. For this, we can define a game that is
exactly as game 2 with one extra condition in Step 3, which is "m contains at
most $i$ commands"

###### Proof.

The intuition behind the proof of this lemma is that for a PPT adversary,
forging a fully tied RAFT (i.e. $\widehat{RAFT}$) without observing the input
message before involves distinguishing the HMAC from a random function.

Lets introduce the notation $\widehat{RAFT}(K,p,c_{1},\ldots,c_{i})$ (where
$K=(k_{0},k_{1},\ldots,k_{n-1})$ and $n$ is the number of services) to stand
for a fully tied RAFT token with $i$ commands and define $\widehat{RAFT}$ as
follows:

$\small{\widehat{RAFT}(K,p,c_{1},\ldots,c_{i})=}\begin{cases}HMAC(HMAC(k_{0},p),p\parallel
c_{1})=h_{1}&\small{i=1}\\\
\leavevmode\resizebox{277.15372pt}{}{$HMAC(k_{i-1},p\parallel
c_{1}\parallel\ldots\parallel
c_{i}\parallel\widehat{RAFT}(K,p,c_{1},\ldots,c_{i-1}))=h_{i}$}&\small{n\geq
i>1}\\\ \end{cases}$

Let us also simplify the descriptions of algorithms 1, 3, and 5 as follows:

  * •

For the key $k_{0}$ and input payload $p$ and the command $c$:

$\displaystyle UserIssue(k_{0},p,c)=HMAC(HMAC(k_{0},p),p\parallel
c)=h_{1}=\widehat{RAFT}(K,p,c_{1})$ (15)

  * •

For the key $k_{i-1}$ ($i\in\\{2,\ldots,n\\}$ where $n$ is the number of
services), input token $r=(m,t)=(p\parallel c_{1}\parallel\ldots\parallel
c_{i-1},h_{i-2})$, and the command $c_{i}$:

$\displaystyle ServiceIssue(i-1,K,r=(m,t),c_{i})$
$\displaystyle=HMAC(k_{i-1},m\parallel c_{i}\parallel t)$
$\displaystyle=HMAC(k_{i-1},p\parallel c_{1}\parallel\cdots\parallel
c_{i-1}\parallel h_{i-1})$ $\displaystyle=h_{i}$
$\displaystyle=\widehat{RAFT}(K,p,c_{1},\ldots,c_{i})$ (16)

  * •

For the key set $K=(k_{0},k_{1},\ldots,k_{n-1})$ where $n$ is the number of
services, and the input token $r=(m,t)$, first, $Ver(K,r)$ decomposes $m$ and
gets $\\{p,c_{1},\cdots,c_{i}\\}$, then calculates:

$\displaystyle h_{1}$ $\displaystyle=HMAC(HMAC(k_{0},p),p\parallel c_{1})$
Find corresponding $\displaystyle\textit{ key }k_{1}\textit{ for $c_{2}$}$
$\displaystyle h_{2}$ $\displaystyle=HMAC(k_{1},p\parallel c_{1}\parallel
c_{2}\parallel h_{1})$ Find corresponding $\displaystyle\textit{ key
}k_{2}\textit{ for $c_{3}$}$ $\displaystyle h_{3}$
$\displaystyle=HMAC(k_{2},p\parallel c_{1}\parallel c_{2}\parallel
c_{3}\parallel h_{2})$ $\displaystyle\vdots$ Find corresponding
$\displaystyle\textit{ key }k_{i-1}\textit{ for $c_{i}$}$ Extract
$\displaystyle k_{n}\textit{ from $c_{n}$}$ $\displaystyle h_{i}$
$\displaystyle=HMAC(k_{i-1},p\parallel c_{1}\parallel\cdots\parallel
c_{i}\parallel h_{i-1})$

Then, if $h_{i}=t$, returns valid; otherwise, returns invalid.

Let ${\cal A}$ be a probabilistic polynomial-time adversary and let
$\varepsilon($.$)$ be a function such that:

$\Pr[ForgeFTT_{{\cal A},\widehat{RAFT}}(\lambda)=1]=\varepsilon(\lambda)$ (17)

and let $\Phi$ represent the set of all tokens that $\cal A$ has queried. We
want to show that $\varepsilon(\lambda)$ is negligible.

According to the game 2, the adversary ${\cal A}$ wins the game
$ForgeFTT_{{\cal A},\widehat{RAFT}}$ if he can forge a token that is either an
output of $UserIssue$ or $ServiceIssue$ for the case which the $k_{i}$ is not
leaked.

In other words,

$\displaystyle\Pr[ForgeFTT_{{\cal A},\widehat{RAFT}}(\lambda)=1]$
$\displaystyle=\Pr[ForgeFTT^{1\leq i\leq n}_{{\cal
A},\widehat{RAFT}}(\lambda)=1]$ $\displaystyle=\max_{1\leq i\leq
n}\Pr[ForgingFTT^{i}_{{\cal A},\widehat{RAFT}}(\lambda)=1]$ (18)

where $i\notin I$.

A closer look at the structure of user tied RAFT token ($RAFT$) and fully tied
RAFT token ($\widehat{RAFT}$) shows that, for $i=1$,

$\displaystyle\widehat{RAFT}(K,p,c_{1})=HMAC(HMAC(k_{0},p),p\parallel
c_{1})=RAFT(k_{0},p,c_{1})$ (19)

and for $1<i\leq n$, if we consider $k^{\prime}=k_{i-1}$ and
$p^{\prime}=p\parallel c_{1}\parallel c_{2}\parallel\ldots\parallel
c_{i}\parallel h_{i-1}$ then,

$\displaystyle\widehat{RAFT}(K,p,c_{1},\ldots,c_{i})$
$\displaystyle=HMAC(k_{i-1},p\parallel c_{1}\parallel\ldots\parallel
c_{i}\parallel h_{i-1})$ $\displaystyle=HMAC(k^{\prime},p^{\prime})$
$\displaystyle=RAFT(k^{\prime},p^{\prime})$ (20)

From lemma 1 and equation (19) we have:

$\displaystyle\Pr[ForgingFTT^{1}_{{\cal
A},\widehat{RAFT}}(\lambda)=1]=\Pr[ForgingUTT^{1}_{{\cal
A},RAFT}(\lambda)=1]\leq\alpha(\lambda)+\beta(\lambda)$ (21)

where $\alpha(\lambda)$ and $\beta(\lambda)$ are negligible functions in
$\lambda$ (for more details see equation (10)).

From lemma 1 and equation (20) we have (for $1<i\leq n$):

$\displaystyle\Pr[ForgingFTT^{i}_{{\cal
A},\widehat{RAFT}}(\lambda)=1]=\Pr[ForgingUTT^{0}_{{\cal
A},RAFT}(\lambda)=1]\leq\beta(\lambda)$ (22)

From equations (17), (18), (21) and (22) we have

$\varepsilon(\lambda)=\Pr[ForgeFTT_{{\cal
A},\widehat{RAFT}}(\lambda)=1]\leq\alpha(\lambda)+\beta(\lambda)$ (23)

Since $\alpha(\lambda)$ and $\beta(\lambda)$ are negligible functions in
$\lambda$, (23) proves the lemma. ∎

##  Appendix B Source Code

the sample command for creating a virtual machine that we used in our
experiment

⬇

def get_create_server_sample():

cmd = "compute/v2.1/servers"

data ={

"server": {

"name": "vm_name",

"imageRef": "ce0afaaa-e236-47c6-95e8-47c7694eb74c",

"flavorRef": "1",

"max_count": 1,

"min_count": 1,

"networks": [{"uuid": "5eeb14b4-47a9-44aa-bade-b225b7713a6b"}]

}

}

\parcmd += " " + str(data)

return cmd

the sample command for creating a volume that we used in our experiment

⬇

def get_create_volume_sample():

cmd = "volume/v2/08b72d6e4f2b465d96e9e0db2f10d232/volumes"

data = {

"volume": {

"status": "creating",

"name": "vol_name",

"imageRef": "ce0afaaa-e236-47c6-95e8-47c7694eb74c",

"attach_status": "detached",

"volume_type": "lvmdriver-1",

"size": 1

}

}

cmd += " " + str(data)

return cmd

The python code for extracting the payload of a project scoped token given a
Fernet key and token.

⬇

# this code is adapted from the source code of Keystone Stein

from cryptography.fernet import Fernet

import msgpack

import uuid

\pardef restore_padding(token):

mod_returned = len(token) if mod_returned:

missing_padding = 4 - mod_returned

token += ’=’ * missing_padding

return token

\parkey = "Qh4ZzunoX36Ri0TKVa3bXqzTQKzwqT3G4JfmGw1ZNtU="

f = Fernet(key)

token="gAAAAABdpxhmvMe_byl3qKlJ0KVXizdSyL_38Idxam2ap7O1T9_xzX9eVJ6WCozRKlXjH6oZlDuOyS0nI_57u0G0ceOt7coUtDPPI1TipydgxMekVNtbhdHuR8A9BMvY1pPAVkGV_23Hd_Ste0eiTXP7m_7W77Vj3X2qGkjkeuinyGZsTclYZOc"

print("Token Length = token = restore_padding(token)

serialized_payload = f.decrypt(token.encode(’utf-8’))

print("Payload Length = \parversioned_payload =
msgpack.unpackb(serialized_payload)

version, payload = versioned_payload[0], versioned_payload[1:]

print("version = \par(is_stored_as_bytes, user_id) = payload[0]

if is_stored_as_bytes:

user_id = uuid.UUID(bytes=user_id)

print("User Id = \parprint("Method = \par(is_stored_as_bytes,
project_id)=payload[2]

if is_stored_as_bytes:

project_id = uuid.UUID(bytes=project_id)

\parprint("Project Id = \parprint("Expiration Time print("Audit Id =

The source code of user tied RAFT Library.

⬇

#importing the required library

import os

import time

import six

\parfrom cryptography.hazmat.backends import default_backend

import base64

from cryptography import fernet

from cryptography.hazmat.primitives.hmac import HMAC

from cryptography.hazmat.primitives import hashes

from cryptography import utils

from struct import pack,unpack, unpack_from

\par#KeystoneRAFT is developed to be added to Keystone. It allows Keystone to
verfy RAFT tokens

class KeystoneRAFT(object):

expirationTime = 10

@classmethod

def restore_padding(cls, token):

"""Restore padding based on token size.

\par:param token: token to restore padding on

:type token: six.text_type

:returns: token with correct padding

\par"""

# Re-inflate the padding

mod_returned = len(token) if mod_returned:

missing_padding = 4 - mod_returned

token += ’=’ * missing_padding

return token

\par#the function which is used for initialization of new object

def __init__(self, backend=None):

if backend is None:

backend = default_backend()

self._backend = backend

\pardef isRAFT(self, token):

"""

Checks the first byte of the given token to find out if it is a RAFT or NOT.

Returns True if the

"""

if
six.indexbytes(base64.urlsafe_b64decode(ClientRAFT.restore_padding(token)),0)==
0x91:

return True

else:

return False

\pardef CheckExpirationTime(self,token,pos):

"""

Check the expiration time of a token adn rise an exception if the token is
already expired

"""

exp_time, = unpack_from(">Q",token,pos)

if self.expirationTime > exp_time:

self.expirationTime =exp_time

\parif exp_time < time.time():

raise Exception("the token has expired")

return exp_time

\pardef GetKey(self, token):

"""

This function recursively extracts the parent messages and checks their
expiration time until it gets to the root token.

Then it starts to recalculate the hmac of every parent’s messages.

"""

v, = unpack_from(">B",token,0)

if v==0x91 :

#it must be a RAFT

lenId, = unpack_from(">H",token,1)

OriginalId, = unpack_from(">" + str(lenId)+"s", token,3)

cmd = token[19+lenId:]

self.CheckExpirationTime(token, 3+lenId)

keys, cmds = self.GetKey(OriginalId)

cmds.append(cmd)

sign_key = keys[:16]

h = HMAC(sign_key, hashes.SHA256(), self._backend)

h.update(token)

hmac=h.finalize()

return hmac, cmds

else:

# when we get the root token which is supposed to be Fernet token

sign_key = base64.urlsafe_b64decode(self.SourceKey)[-32:-16]

h = HMAC(sign_key, hashes.SHA256(), self._backend)

h.update(token)

signature = h.finalize()

self.fernetToken = base64.urlsafe_b64encode(token+signature)

return signature,[]

return ""

\pardef ValidateRAFT(self, token):

"""

This function get a token and using GetKey function rebulds the HMAC of the
message part of the token.

If calculated HMAC fits with the token signature, then the token is valid;
Otherwise the function raises an exception error

"""

token = self.restore_padding(token)

token = base64.urlsafe_b64decode(token)

v, = unpack_from(">B",token,0)

self.SourceKey = ’Qh4ZzunoX36Ri0TKVa3bXqzTQKzwqT3G4JfmGw1ZNtU=’

# self.SourceKey = fernet_utils.load_keys()

if v==0x91 :

lenId, = unpack_from(">H",token,1)

OriginalId, = unpack_from(">"+str(lenId)+"s",token,3)

self.expirationTime = self.CheckExpirationTime(token, 3+lenId)

cmd = token[19+lenId:-32]

print(cmd)

keys,cmds = self.GetKey(OriginalId)

cmds.append(cmd)

sign_key = keys[:16]

h = HMAC(sign_key, hashes.SHA256(), self._backend)

h.update(token[:-32])

hmac=h.finalize()

if hmac== token[-32:]:

#print("It is valid")

return True,cmds

else:

raise Exception("Error: Not a RAFT token (MAC)")

else:

raise Exception("Error: Not a RAFT token (Format)")

return ""

\par\par\par#ClientRaft is used for creating a new RAFT from either a Fernet
or other RAFT.

class ClientRAFT(object):

_lifeTime = 1 #feault lifetime for a RAFT

#the function which is used for initialization of new object

def __init__(self, parent_token=None, backend=None):

if backend is None:

backend = default_backend()

self._backend = backend

\parif parent_token is not None:

self.SetParentToken(parent_token)

\par@classmethod

def restore_padding(cls, token):

"""Restore padding based on token size.

\par:param token: token to restore padding on

:type token: six.text_type

:returns: token with correct padding

\par"""

# Re-inflate the padding

mod_returned = len(token) if mod_returned:

missing_padding = 4 - mod_returned

token += ’=’ * missing_padding

return token

\pardef SetParentToken(self,parent_token):

"""

Allows to define/redfine the parent token of this object

"""

parent_token= self.restore_padding(parent_token)

self._parentToken = base64.urlsafe_b64decode(parent_token)

#the last 32 bytes of the parent token is the HMAC, which the first 16 bytes
of it is the signing of current token

self._signKey = self._parentToken[-32:-16]

self._encryptionKey = self._parentToken[-16:]

self._id = self._parentToken[:-32]

\pardef SetCommand(self, command):

"""

Specifinying a command that is supposed to be added to the parent token

"""

self._command = command

\par\pardef Finalize(self, life_time = None):

"""

Packs all the items needed to be in the token,

specifies the lifetime,

calculates the HMAC of the packed message,

and convert the result to a base64 string, which is the new RAFT token

"""

if life_time is not None:

self._lifeTime = life_time

\parself._NewToken = pack(">BH" +

str(len(self._id))+"s",

0x91,

len(self._id),

self._id)

self._command=pack(">Q8s"+str(len(self._command))+"s",
int(time.time())+self._lifeTime,os.urandom(8),self._command)
#bytearray(self._command,"utf8")

self._NewToken+=self._command

self.h = HMAC(self._signKey, hashes.SHA256(), self._backend)

self.h.update(self._NewToken)

self._NewToken += self.h.finalize()

return base64.urlsafe_b64encode(self._NewToken).rstrip(b’=’)

\par

The validate_token function of the TokenFormatter class after applying the
required changes.

⬇

def validate_token(self, token):

# The following code is added to check if the token is RAFT, then process the
RAFT using our library

try:

raftFlag = False

kr = RAFT.KeystoneRAFT()

if kr.isRAFT(token):

raftFlag = True

kr.ValidateRAFT(token)

token = kr.fernetToken

except Exception as ex:

template = "An exception of type {0} occurred. Arguments:\n{1!r}"

message = template.format(type(ex).__name__, ex.args)

#End of processing a RAFT.

\par#The old code for processing Fernet Token

serialized_payload = self.unpack(token)

versioned_payload = msgpack.unpackb(serialized_payload)

version, payload = versioned_payload[0], versioned_payload[1:]

for payload_class in _PAYLOAD_CLASSES:

if version == payload_class.version:

(user_id, methods, system, project_id, domain_id,

expires_at, audit_ids, trust_id, federated_group_ids,

identity_provider_id, protocol_id, access_token_id,

app_cred_id) = payload_class.disassemble(payload)

break

else:

raise exception.ValidationError(_(

’This is not a recognized Fernet payload version: version)

\parif isinstance(system, bytes):

system = system.decode(’utf-8’)

\parissued_at = TokenFormatter.creation_time(token)

issued_at = ks_utils.isotime(at=issued_at, subsecond=True)

\par# The following code, adjusts the expiration time if the token was RAFT

\parif raftFlag:

expires_at = kr.expirationTime

expires_at = BasePayload._convert_float_to_time_string(expires_at)

\parexpires_at = timeutils.parse_isotime(expires_at)

expires_at = ks_utils.isotime(at=expires_at, subsecond=True)

# end of expiration adjustment

\parreturn (user_id, methods, audit_ids, system, domain_id, project_id,

trust_id, federated_group_ids, identity_provider_id,

protocol_id, access_token_id, app_cred_id, issued_at,

expires_at)

The source code of the first set of our experiments.

⬇

import requests

import os

import time

import json

from RAFT import ClientRAFT,KeystoneRAFT

\parbase_url = "http://192.168.122.29" #The IP address of our OpenStack server

\pardef get_scoped_token(username, password, domain,project_name):

data= {

"auth": {

"identity": {

"methods": ["password"],

"password": {

"user": {

"domain": {

"name": domain

},

"name": username,

"password": password

}

}

},

"scope": {

"project": {

"domain": {

"name": "Default"

},

"name": project_name

}

}

}

}

url = base_url + "/identity/v3/auth/tokens"

r = requests.post(url,json=data)

return r.headers["X-Subject-Token"]

\pardef check_token(token):

url = base_url + "/identity/v3/auth/tokens"

h = {"X-Auth-Token" : token,"X-Subject-Token" : token}

r = requests.get(url, headers=h)

return r

\pardef firstExp1():

print("Creating 100 Fernet tokens")

start_time= time.time()

for i in range(0,100):

fernet_token = get_scoped_token("admin","123","Default","admin")

execution_time = time.time() - start_time

print(execution_time)

\pardef firstExp2():

print("Creating 100 RAFTs + a Fernet token")

start_time= time.time()

fernet_token = get_scoped_token("admin","123","Default","admin")

for i in range(0,100):

raft_builder = ClientRAFT(fernet_token)

raft_builder.SetCommand("")

raft_builder.Finalize()

execution_time = time.time() - start_time

print(execution_time)

\pardef firstExp3():

print("Creating and validating 100 Fernet tokens")

start_time= time.time()

for i in range(0,100):

fernet_token = get_scoped_token("admin","123","Default","admin")

check_token(fernet_token)

execution_time = time.time() - start_time

print(execution_time)

\pardef firstExp4():

print("Creating and validating 100 RAFTs with no command")

start_time= time.time()

fernet_token = get_scoped_token("admin","123","Default","admin")

for i in range(0,100):

raft_builder = ClientRAFT(fernet_token)

raft_builder.SetCommand("")

raft_token= raft_builder.Finalize(1)

check_token(raft_token)

execution_time = time.time() - start_time

print(execution_time)

\pardef firstExp5to7(CmdLength):

print("Creating and validating 100 RAFTs with a hypothetical 200 characters
command")

start_time= time.time()

fernet_token = get_scoped_token("admin","123","Default","admin")

cmd = "a" * CmdLength

for i in range(0,100):

raft_builder = ClientRAFT(fernet_token)

raft_builder.SetCommand(cmd)

raft_token= raft_builder.Finalize(10)

check_token(raft_token)

execution_time = time.time() - start_time

print(execution_time)

\pardef firstExpIssueTime():

print("Locally Creating 100 RAFTs experiment")

fernet_token = get_scoped_token("admin","123","Default","admin")

cmd = "a" * 20

start_time= time.time()

for i in range(0,100):

raft_builder = ClientRAFT(fernet_token)

raft_builder.SetCommand(cmd)

raft_token= raft_builder.Finalize(10)

execution_time = time.time() - start_time

print(execution_time)

\pardef firstExpVerificationTime():

print("Locally creating and validation 100 RAFTs experiment")

fernet_token = get_scoped_token("admin","123","Default","admin")

cmd = "a" * 20

total_time = 0

for i in range(0,100):

raft_builder = ClientRAFT(fernet_token)

raft_builder.SetCommand(cmd)

raft_token= raft_builder.Finalize(10)

start_time= time.time()

kv = KeystoneRAFT();

kv.ValidateRAFT(raft_token)

execution_time = time.time() - start_time

total_time+=execution_time

print(total_time)

Examining the overhead of using RAFT with some commands

⬇

import requests

import os

import time

import json

import expCommandLength

from RAFT import ClientRAFT,KeystoneRAFT

\parbase_url = "http://192.168.122.29" # the IP address of our OpenStack
server

\pardef get_project_list(token):

url = base_url + "/identity/v3/projects"

h = {"X-Auth-Token" : token,"X-RAFT-Token" : token}

r = requests.get(url,headers=h)

if r.status_code == 200:

return r.content

else:

print(r.content)

return None

\pardef create_VM(token, vm_name):

url = base_url + "/compute/v2.1/servers"

h = {"X-Auth-Token" : token,"X-RAFT-Token" : token, "Accept":
"application/json", "Content-Type": "application/json", "User-Agent": "python-
novaclient"}

data ={

"server": {

"name": vm_name,

"imageRef": "ce0afaaa-e236-47c6-95e8-47c7694eb74c",

"flavorRef": "1",

"max_count": 1,

"min_count": 1,

"networks": [{"uuid": "5eeb14b4-47a9-44aa-bade-b225b7713a6b"}]

}

}

r = requests.post(url,json=data,headers=h)

return r

\par# the default values used in the following function are only valid in our
server.

def create_Volume(token, volume_name, vol_size=1 ,
project_id="08b72d6e4f2b465d96e9e0db2f10d232" , imageId=
"ce0afaaa-e236-47c6-95e8-47c7694eb74c" ):

url = base_url + "/volume/v2/" + project_id + "/volumes"

h = {"X-Auth-Token" : token,"X-RAFT-Token" : token, "Accept":
"application/json", "Content-Type": "application/json", "User-Agent": "python-
novaclient"}

data = {

"volume": {

"status": "creating",

"name": volume_name,

"imageRef": imageId,

"attach_status": "detached",

"volume_type": "lvmdriver-1",

"size": vol_size

}

}

\parr = requests.post(url,json=data,headers=h)

return r

\pardef get_imagelist(token):

url = base_url + "/image/v2/images"

h = {"X-Auth-Token" : token,"X-RAFT-Token" : token}

r = requests.get(url,headers=h)

if r.status_code == 200:

j = json.loads(r.content)

return j

else:

print(r.content)

return None

\pardef SecondExp1():

print("Creating a Volume using Fernet")

for j in range(0,5):

fernet_token = get_scoped_token("admin","123","Default","admin")

start_time= time.time()

for i in range(0,1):

create_Volume(fernet_token, "vreza"+str(i))

execution_time = time.time() - start_time

print(execution_time)

\pardef SecondExp2():

print("Creating a Volume using RAFT")

for j in range(0,5):

fernet_token = get_scoped_token("admin","123","Default","admin")

start_time= time.time()

for i in range(0,1):

raft_builder = ClientRAFT(fernet_token)

raft_builder.SetCommand(expCommandLength.get_create_volume_sample())

raft_token= raft_builder.Finalize(100)

create_Volume(raft_token, "vreza"+str(i))

execution_time = time.time() - start_time

print(execution_time)

\pardef SecondExp3():

print("Creating a Virtual Machine using Fernet")

for j in range(0,5):

fernet_token = get_scoped_token("admin","123","Default","admin")

start_time= time.time()

for i in range(0,1):

create_VM(fernet_token, "vm"+str(j))

execution_time = time.time() - start_time

print(execution_time)

\pardef SecondExp4():

print("Creating a Virtual Machine using RAFT")

for j in range(0,5):

fernet_token = get_scoped_token("admin","123","Default","admin")

start_time= time.time()

for i in range(0,1):

raft_builder = ClientRAFT(fernet_token)

raft_builder.SetCommand(expCommandLength.get_create_server_sample())

raft_token= raft_builder.Finalize(100)

create_VM(raft_token, "vm"+str(j))

execution_time = time.time() - start_time

print(execution_time)

\pardef SecondExp5():

print("Getting image list using Fernet")

for j in range(0,5):

fernet_token = get_scoped_token("admin","123","Default","admin")

start_time= time.time()

for i in range(0,1):

get_imagelist(fernet_token)

execution_time = time.time() - start_time

print(execution_time)

\pardef SecondExp6():

print("Getting image list using RAFT")

for j in range(0,5):

fernet_token = get_scoped_token("admin","123","Default","admin")

start_time= time.time()

for i in range(0,1):

raft_builder = ClientRAFT(fernet_token)

raft_builder.SetCommand(expCommandLength.get_image_list_command())

raft_token= raft_builder.Finalize(2)

get_imagelist(raft_token)

execution_time = time.time() - start_time

print(execution_time)

\pardef SecondExp7():

print("Getting project list using Fernet")

for j in range(0,5):

fernet_token = get_scoped_token("admin","123","Default","admin")

start_time= time.time()

for i in range(0,1):

get_project_list(fernet_token)

execution_time = time.time() - start_time

print(execution_time)

\pardef SecondExp8():

print("Getting project list using RAFT")

for j in range(0,5):

fernet_token = get_scoped_token("admin","123","Default","admin")

start_time= time.time()

for i in range(0,1):

raft_builder = ClientRAFT(fernet_token)

raft_builder.SetCommand(expCommandLength.get_project_command())

raft_token= raft_builder.Finalize(2)

get_project_list(raft_token)

execution_time = time.time() - start_time

print(execution_time)

\par\par\par\par