PyORAM/README.rst

   1 PyORAM
   2 ======
   3
   4 .. image:: https://travis-ci.org/ghackebeil/PyORAM.svg?branch=master
   5     :target: https://travis-ci.org/ghackebeil/PyORAM
   6
   7 .. image:: https://ci.appveyor.com/api/projects/status/898bxsvqdch1btv6/branch/master?svg=true
   8     :target: https://ci.appveyor.com/project/ghackebeil/PyORAM?branch=master
   9
  10 .. image:: https://codecov.io/github/ghackebeil/PyORAM/coverage.svg?branch=master
  11     :target: https://codecov.io/github/ghackebeil/PyORAM?branch=master
  12
  13 .. image:: https://img.shields.io/pypi/v/PyORAM.svg
  14     :target: https://pypi.python.org/pypi/PyORAM/
  15
  16 Python-based Oblivious RAM (PyORAM) is a collection of
  17 Oblivious RAM algorithms implemented in Python. This package
  18 serves to enable rapid prototyping and testing of new ORAM
  19 algorithms and ORAM-based applications tailored for the
  20 cloud-storage setting. PyORAM is written to support as many
  21 Python versions as possible, including Python 2.7+, Python
  22 3.3+, and PyPy 2.6+.
  23
  24 This software is copyright (c) by Gabriel A. Hackebeil (gabe.hackebeil@gmail.com).
  25
  26 This software is released under the MIT software license.
  27 This license, including disclaimer, is available in the 'LICENSE' file.
  28
  29 This work was funded by the Privacy Enhancing Technologies
  30 project under the guidance of Professor `Attila Yavuz
  31 <https://web.engr.oregonstate.edu/~yavuza>`_ at Oregon State
  32 University.
  33
  34 Why Python?
  35 -----------
  36
  37 This project is meant for research. It is provided mainly as
  38 a tool for other researchers studying the applicability of
  39 ORAM to the cloud-storage setting. In such a setting, we
  40 observe that network latency far outweighs any overhead
  41 introduced from switching to an interpreted language such as
  42 Python (as opposed to C++ or Java). Thus, our hope is that
  43 by providing a Python-based library of ORAM tools, we will
  44 enable researchers to spend more time prototyping new and
  45 interesting ORAM applications and less time fighting with a
  46 compiler or chasing down segmentation faults.
  47
  48 Installation
  49 ------------
  50
  51 To install the latest release of PyORAM, simply execute::
  52
  53   $ pip install PyORAM
  54
  55 To install the trunk version of PyORAM, first clone the repository::
  56
  57   $ git clone https://github.com/ghackebeil/PyORAM.git
  58
  59 Next, enter the directory where PyORAM has been cloned and run setup::
  60
  61   $ python setup.py install
  62
  63 If you are a developer, you should instead install using::
  64
  65   $ pip install -e .
  66   $ pip install nose2 unittest2
  67
  68 Installation Tips
  69 -----------------
  70
  71 * OS X users are recommended to work with the `homebrew
  72   <http://brew.sh/>`_ version of Python2 or Python3. If you
  73   must use the default system Python, then the best thing to
  74   do is create a virtual environment and install PyORAM into
  75   that. The process of creating a virtual environment that is
  76   stored in the PyORAM directory would look something like::
  77
  78     $ sudo pip install virtualenv
  79     $ cd <PyORAM-directory>
  80     $ virtualenv local_python2.7
  81
  82   If you had already attempted to install PyORAM into the
  83   system Python and encountered errors, it may be necessary
  84   to delete the directories :code:`build` and :code:`dist`
  85   from the current directory using the command::
  86
  87     $ sudo rm -rf build dist
  88
  89   Once this virtual environment has been successfully
  90   created, you can *activate* it using the command::
  91
  92     $ . local_python2.7/bin/activate
  93
  94   Then, proceed with the normal installation steps to
  95   install PyORAM into this environment. Note that you must
  96   *activate* this environment each time you open a new
  97   terminal if PyORAM is installed in this way. Also, note
  98   that use of the :code:`sudo` command is no longer
  99   necessary (and should be avoided) once a virtual
 100   environment is activated in the current shell.
 101
 102 * If you have trouble installing the cryptography package
 103   on OS X with PyPy: `stackoverflow <https://stackoverflow.com/questions/36662704/fatal-error-openssl-e-os2-h-file-not-found-in-pypy/36706513#36706513>`_.
 104
 105 * If you encounter the dreaded "unable to find
 106   vcvarsall.bat" error when installing packages with C
 107   extensions through pip on Windows: `blog post <https://blogs.msdn.microsoft.com/pythonengineering/2016/04/11/unable-to-find-vcvarsall-bat>`_.
 108
 109 Tools Available (So Far)
 110 ------------------------
 111
 112 Encrypted block storage
 113 ~~~~~~~~~~~~~~~~~~~~~~~
 114
 115 * The basic building block for any ORAM implementation.
 116
 117 * Available storage interfaces include:
 118
 119   - local storage using a file, a memory-mapped file, or RAM
 120
 121     + Dropbox
 122
 123   - cloud storage using SFTP (requires SSH access to a server)
 124
 125     + Amazon EC2
 126
 127     + Microsoft Azure
 128
 129     + Google Cloud Platform
 130
 131   - cloud storage using Amazon Simple Storage Service (S3)
 132
 133 * See Examples:
 134
 135   - examples/encrypted_storage_ram.py
 136
 137   - examples/encrypted_storage_mmap.py
 138
 139   - examples/encrypted_storage_file.py
 140
 141   - examples/encrypted_storage_sftp.py
 142
 143   - examples/encrypted_storage_s3.py
 144
 145 Path ORAM
 146 ~~~~~~~~~
 147
 148 * Reference: `Stefanov et al. <http://arxiv.org/abs/1202.5150v3>`_
 149
 150 * Generalized to work over k-kary storage heaps. Default
 151   settings use a binary storage heap and bucket size
 152   parameter set to 4. Using a k-ary storage heap can reduce
 153   the access cost; however, stash size behavior has not been
 154   formally analyzed in this setting.
 155
 156 * Tree-Top caching can be used to reduce data transmission
 157   per access as well as reduce access latency by exploiting
 158   parallelism across independent sub-heaps below the last
 159   cached heap level.
 160
 161 * See Examples:
 162
 163   -  examples/path_oram_ram.py
 164
 165   - examples/path_oram_mmap.py
 166
 167   - examples/path_oram_file.py
 168
 169   - examples/path_oram_sftp.py
 170
 171   - examples/path_oram_s3.py
 172
 173 Performance Tips
 174 ----------------
 175
 176 Setup Storage Locally
 177 ~~~~~~~~~~~~~~~~~~~~~
 178
 179 Storage schemes such as BlockStorageFile ("file"), BlockStorageMMap
 180 ("mmap"), BlockStorageRAM ("ram"), and BlockStorageSFTP ("sftp") all
 181 employ the same underlying storage format. Thus, an oblivious storage
 182 scheme can be initialized locally and then transferred to an external
 183 storage location and accessed via BlockStorageSFTP using SSH login
 184 credentials. See the following pair of files for an example of this:
 185
 186 * examples/path_oram_sftp_setup.py
 187
 188 * examples/path_oram_sftp_test.py
 189
 190 BlockStorageS3 ("s3") employs a different format whereby the
 191 underlying blocks are stored in separate "file" objects.
 192 This design is due to the fact that the Amazon S3 API does
 193 not allow modifications to a specific byte range within a
 194 file, but instead requires that the entire modified file
 195 object be re-uploaded. Thus, any efficient block storage
 196 scheme must use separate "file" objects for each block.
 197
 198 Tree-Top Caching
 199 ~~~~~~~~~~~~~~~~
 200
 201 For schemes that employ a storage heap (such as Path ORAM),
 202 tree-top caching provides the ability to parallelize I/O
 203 operations across the independent sub-heaps below the last
 204 cached heap level. The default behavior of this
 205 implementation of Path ORAM, for instance, caches the top
 206 three levels of the storage heap in RAM, which creates eight
 207 independent sub-heaps across which write operations can be
 208 asynchronous.
 209
 210 If the underlying storage is being accessed through SFTP, the
 211 tree-top cached storage heap will attempt to open an
 212 independent SFTP session for each sub-heap using the same
 213 SSH connection. Typically, the maximum number of allowable
 214 sessions associated with a single SSH connection is limited
 215 by the SSH server. For instance, the default maximum number
 216 of sessions allowed by a server using OpenSSH is 10. Thus,
 217 increasing the number of cached levels beyond 3 when using
 218 a binary storage heap will attempt to generate 16 or more SFTP
 219 sessions and result in an error such as::
 220
 221   paramiko.ssh_exception.ChannelException: (1, 'Administratively prohibited')
 222
 223 There are two options for avoiding this error:
 224
 225 1. If you have administrative privileges on the server, you
 226    can increase the maximum number of allowed sessions for a
 227    single SSH connection. For example, to set the maximum
 228    allowed sessions to 128 on a server using OpenSSH, one
 229    would set::
 230
 231      MaxSessions 128
 232
 233    in :code:`/etc/ssh/sshd_config`, and then run the
 234    command :code:`sudo service ssh restart`.
 235
 236 2. You can limit the number of concurrent devices that will
 237    be created by setting the concurrency level to something
 238    below the last cached level using the
 239    :code:`concurrency_level` keyword. For example, the
 240    settings :code:`cached_levels=5` and
 241    :code:`concurrency_level=0` would cache the top 5 levels
 242    of the storage heap locally, but all external I/O
 243    operations would take place through a single storage
 244    device (e.g., using 1 SFTP session).