summary refs log tree commit diff
diff options
context:
space:
mode:
-rw-r--r--.gitignore1
-rw-r--r--MANIFEST.in13
-rwxr-xr-xcontrib/vertobot/bot.pl40
-rw-r--r--contrib/vertobot/cpanfile3
-rw-r--r--scripts-dev/check_event_hash.py2
-rw-r--r--scripts-dev/check_signature.py8
-rw-r--r--scripts-dev/convert_server_keys.py8
-rw-r--r--scripts-dev/hash_history.py4
-rwxr-xr-xscripts/upgrade_db_to_v0.6.0.py15
-rw-r--r--setup.cfg3
-rwxr-xr-xsetup.py42
-rw-r--r--synapse/api/auth.py27
-rw-r--r--synapse/config/key.py35
-rw-r--r--synapse/config/registration.py4
-rw-r--r--synapse/crypto/event_signing.py9
-rw-r--r--synapse/crypto/keyring.py18
-rw-r--r--synapse/handlers/admin.py1
-rw-r--r--synapse/handlers/auth.py52
-rw-r--r--synapse/handlers/message.py9
-rw-r--r--synapse/handlers/register.py19
-rw-r--r--synapse/handlers/sync.py1
-rw-r--r--synapse/http/client.py3
-rw-r--r--synapse/http/matrixfederationclient.py4
-rw-r--r--synapse/http/server.py12
-rw-r--r--synapse/python_dependencies.py12
-rw-r--r--synapse/rest/client/v1/admin.py2
-rw-r--r--synapse/rest/client/v1/directory.py4
-rw-r--r--synapse/rest/client/v1/events.py4
-rw-r--r--synapse/rest/client/v1/initial_sync.py2
-rw-r--r--synapse/rest/client/v1/login.py6
-rw-r--r--synapse/rest/client/v1/presence.py8
-rw-r--r--synapse/rest/client/v1/profile.py4
-rw-r--r--synapse/rest/client/v1/pusher.py4
-rw-r--r--synapse/rest/client/v1/room.py34
-rw-r--r--synapse/rest/client/v1/voip.py4
-rw-r--r--synapse/rest/client/v2_alpha/__init__.py2
-rw-r--r--synapse/rest/client/v2_alpha/account.py4
-rw-r--r--synapse/rest/client/v2_alpha/filter.py4
-rw-r--r--synapse/rest/client/v2_alpha/keys.py9
-rw-r--r--synapse/rest/client/v2_alpha/receipts.py2
-rw-r--r--synapse/rest/client/v2_alpha/sync.py5
-rw-r--r--synapse/rest/client/v2_alpha/tokenrefresh.py56
-rw-r--r--synapse/rest/key/v1/server_key_resource.py6
-rw-r--r--synapse/rest/key/v2/local_key_resource.py6
-rw-r--r--synapse/rest/media/v0/content_repository.py2
-rw-r--r--synapse/rest/media/v1/upload_resource.py2
-rw-r--r--synapse/storage/__init__.py9
-rw-r--r--synapse/storage/_base.py1
-rw-r--r--synapse/storage/event_federation.py2
-rw-r--r--synapse/storage/events.py23
-rw-r--r--synapse/storage/keys.py2
-rw-r--r--synapse/storage/pusher.py2
-rw-r--r--synapse/storage/registration.py74
-rw-r--r--synapse/storage/schema/delta/23/refresh_tokens.sql21
-rw-r--r--synapse/storage/signatures.py2
-rw-r--r--synapse/storage/transactions.py2
-rw-r--r--synapse/types.py4
-rw-r--r--tests/api/test_auth.py26
-rw-r--r--tests/handlers/test_auth.py70
-rw-r--r--tests/rest/client/v1/test_presence.py12
-rw-r--r--tests/rest/client/v1/test_rooms.py42
-rw-r--r--tests/rest/client/v1/test_typing.py6
-rw-r--r--tests/rest/client/v1/utils.py2
-rw-r--r--tests/rest/client/v2_alpha/__init__.py6
-rw-r--r--tests/storage/test_registration.py67
-rw-r--r--tests/utils.py8
-rw-r--r--tox.ini27
67 files changed, 623 insertions, 300 deletions
diff --git a/.gitignore b/.gitignore
index 960183a794..4c336b710d 100644
--- a/.gitignore
+++ b/.gitignore
@@ -42,3 +42,4 @@ build/
 
 localhost-800*/
 static/client/register/register_config.js
+.tox
diff --git a/MANIFEST.in b/MANIFEST.in
index a9b543af82..621e34cb76 100644
--- a/MANIFEST.in
+++ b/MANIFEST.in
@@ -3,13 +3,20 @@ include LICENSE
 include VERSION
 include *.rst
 include demo/README
+include demo/demo.tls.dh
+include demo/*.py
+include demo/*.sh
 
 recursive-include synapse/storage/schema *.sql
 recursive-include synapse/storage/schema *.py
 
-recursive-include demo *.dh
-recursive-include demo *.py
-recursive-include demo *.sh
 recursive-include docs *
 recursive-include scripts *
+recursive-include scripts-dev *
 recursive-include tests *.py
+
+recursive-include static *.css
+recursive-include static *.html
+recursive-include static *.js
+
+prune demo/etc
diff --git a/contrib/vertobot/bot.pl b/contrib/vertobot/bot.pl
index 0430a38aa8..31eed40925 100755
--- a/contrib/vertobot/bot.pl
+++ b/contrib/vertobot/bot.pl
@@ -126,12 +126,26 @@ sub on_unknown_event
         if (!$bridgestate->{$room_id}->{gathered_candidates}) {
             $bridgestate->{$room_id}->{gathered_candidates} = 1;
             my $offer = $bridgestate->{$room_id}->{offer};
-            my $candidate_block = "";
+            my $candidate_block = {
+                audio => '',
+                video => '',
+            };
             foreach (@{$event->{content}->{candidates}}) {
-                $candidate_block .= "a=" . $_->{candidate} . "\r\n";
+                if ($_->{sdpMid}) {
+                    $candidate_block->{$_->{sdpMid}} .= "a=" . $_->{candidate} . "\r\n";
+                }
+                else {
+                    $candidate_block->{audio} .= "a=" . $_->{candidate} . "\r\n";
+                    $candidate_block->{video} .= "a=" . $_->{candidate} . "\r\n";
+                }
             }
-            # XXX: collate using the right m= line - for now assume audio call
-            $offer =~ s/(a=rtcp.*[\r\n]+)/$1$candidate_block/;
+
+            # XXX: assumes audio comes first
+            #$offer =~ s/(a=rtcp-mux[\r\n]+)/$1$candidate_block->{audio}/;
+            #$offer =~ s/(a=rtcp-mux[\r\n]+)/$1$candidate_block->{video}/;
+
+            $offer =~ s/(m=video)/$candidate_block->{audio}$1/;
+            $offer =~ s/(.$)/$1\n$candidate_block->{video}$1/;
             
             my $f = send_verto_json_request("verto.invite", {
                 "sdp" => $offer,
@@ -172,22 +186,18 @@ sub on_room_message
     warn "[Matrix] in $room_id: $from: " . $content->{body} . "\n";    
 }
 
-my $verto_connecting = $loop->new_future;
-$bot_verto->connect(
-    %{ $CONFIG{"verto-bot"} },
-    on_connect_error => sub { die "Cannot connect to verto - $_[-1]" },
-    on_resolve_error => sub { die "Cannot resolve to verto - $_[-1]" },        
-)->then( sub { 
-    warn("[Verto] connected to websocket");
-    $verto_connecting->done($bot_verto) if not $verto_connecting->is_done;
-});
-
 Future->needs_all(
     $bot_matrix->login( %{ $CONFIG{"matrix-bot"} } )->then( sub {
         $bot_matrix->start;
     }),
     
-    $verto_connecting,
+    $bot_verto->connect(
+        %{ $CONFIG{"verto-bot"} },
+        on_connect_error => sub { die "Cannot connect to verto - $_[-1]" },
+        on_resolve_error => sub { die "Cannot resolve to verto - $_[-1]" },        
+    )->on_done( sub { 
+        warn("[Verto] connected to websocket");
+    }),
 )->get;
 
 $loop->attach_signal(
diff --git a/contrib/vertobot/cpanfile b/contrib/vertobot/cpanfile
index c29fcaa6f6..800dc288ed 100644
--- a/contrib/vertobot/cpanfile
+++ b/contrib/vertobot/cpanfile
@@ -11,7 +11,4 @@ requires 'YAML', 0;
 requires 'JSON', 0;
 requires 'Getopt::Long', 0;
 
-on 'test' => sub {
-	requires 'Test::More', '>= 0.98';
-};
 
diff --git a/scripts-dev/check_event_hash.py b/scripts-dev/check_event_hash.py
index 679afbd268..7ccae34d48 100644
--- a/scripts-dev/check_event_hash.py
+++ b/scripts-dev/check_event_hash.py
@@ -1,5 +1,5 @@
 from synapse.crypto.event_signing import *
-from syutil.base64util import encode_base64
+from unpaddedbase64 import encode_base64
 
 import argparse
 import hashlib
diff --git a/scripts-dev/check_signature.py b/scripts-dev/check_signature.py
index 59e3d603ac..079577908a 100644
--- a/scripts-dev/check_signature.py
+++ b/scripts-dev/check_signature.py
@@ -1,9 +1,7 @@
 
-from syutil.crypto.jsonsign import verify_signed_json
-from syutil.crypto.signing_key import (
-    decode_verify_key_bytes, write_signing_keys
-)
-from syutil.base64util import decode_base64
+from signedjson.sign import verify_signed_json
+from signedjson.key import decode_verify_key_bytes, write_signing_keys
+from unpaddedbase64 import decode_base64
 
 import urllib2
 import json
diff --git a/scripts-dev/convert_server_keys.py b/scripts-dev/convert_server_keys.py
index a1ee39059c..151551f22c 100644
--- a/scripts-dev/convert_server_keys.py
+++ b/scripts-dev/convert_server_keys.py
@@ -4,10 +4,10 @@ import sys
 import json
 import time
 import hashlib
-from syutil.base64util import encode_base64
-from syutil.crypto.signing_key import read_signing_keys
-from syutil.crypto.jsonsign import sign_json
-from syutil.jsonutil import encode_canonical_json
+from unpaddedbase64 import encode_base64
+from signedjson.key import read_signing_keys
+from signedjson.sign import sign_json
+from canonicaljson import encode_canonical_json
 
 
 def select_v1_keys(connection):
diff --git a/scripts-dev/hash_history.py b/scripts-dev/hash_history.py
index bdad530af8..616d6a10e7 100644
--- a/scripts-dev/hash_history.py
+++ b/scripts-dev/hash_history.py
@@ -6,8 +6,8 @@ from synapse.crypto.event_signing import (
     add_event_pdu_content_hash, compute_pdu_event_reference_hash
 )
 from synapse.api.events.utils import prune_pdu
-from syutil.base64util import encode_base64, decode_base64
-from syutil.jsonutil import encode_canonical_json
+from unpaddedbase64 import encode_base64, decode_base64
+from canonicaljson import encode_canonical_json
 import sqlite3
 import sys
 
diff --git a/scripts/upgrade_db_to_v0.6.0.py b/scripts/upgrade_db_to_v0.6.0.py
index f466ca510e..cd4be28b86 100755
--- a/scripts/upgrade_db_to_v0.6.0.py
+++ b/scripts/upgrade_db_to_v0.6.0.py
@@ -4,7 +4,7 @@ from synapse.storage._base import SQLBaseStore
 from synapse.storage.signatures import SignatureStore
 from synapse.storage.event_federation import EventFederationStore
 
-from syutil.base64util import encode_base64, decode_base64
+from unpaddedbase64 import encode_base64, decode_base64
 
 from synapse.crypto.event_signing import compute_event_signature
 
@@ -13,12 +13,10 @@ from synapse.events.utils import prune_event
 
 from synapse.crypto.event_signing import check_event_content_hash
 
-from syutil.crypto.jsonsign import (
-    verify_signed_json, SignatureVerifyException,
-)
-from syutil.crypto.signing_key import decode_verify_key_bytes
+from signedjson.sign import verify_signed_json, SignatureVerifyException
+from signedjson.key import decode_verify_key_bytes
 
-from syutil.jsonutil import encode_canonical_json
+from canonicaljson import encode_canonical_json
 
 import argparse
 # import dns.resolver
@@ -26,7 +24,6 @@ import hashlib
 import httplib
 import json
 import sqlite3
-import syutil
 import urllib2
 
 
@@ -324,8 +321,6 @@ if __name__ == "__main__":
     )
     args = parser.parse_args()
 
-    signing_key = syutil.crypto.signing_key.read_signing_keys(
-        args.signing_key
-    )
+    signing_key = signedjson.key.read_signing_keys(args.signing_key)
 
     main(args.database, args.server_name, signing_key[0])
diff --git a/setup.cfg b/setup.cfg
index abb649958e..ba027c7d13 100644
--- a/setup.cfg
+++ b/setup.cfg
@@ -3,9 +3,6 @@ source-dir = docs/sphinx
 build-dir  = docs/build
 all_files  = 1
 
-[aliases]
-test = trial
-
 [trial]
 test_suite = tests
 
diff --git a/setup.py b/setup.py
index 16ccc0f1b8..0e3f2f18d5 100755
--- a/setup.py
+++ b/setup.py
@@ -16,7 +16,8 @@
 
 import glob
 import os
-from setuptools import setup, find_packages
+from setuptools import setup, find_packages, Command
+import sys
 
 
 here = os.path.abspath(os.path.dirname(__file__))
@@ -37,6 +38,39 @@ def exec_file(path_segments):
     exec(code, result)
     return result
 
+
+class Tox(Command):
+    user_options = [('tox-args=', 'a', "Arguments to pass to tox")]
+
+    def initialize_options(self):
+        self.tox_args = None
+
+    def finalize_options(self):
+        self.test_args = []
+        self.test_suite = True
+
+    def run(self):
+        #import here, cause outside the eggs aren't loaded
+        try:
+            import tox
+        except ImportError:
+            try:
+                self.distribution.fetch_build_eggs("tox")
+                import tox
+            except:
+                raise RuntimeError(
+                    "The tests need 'tox' to run. Please install 'tox'."
+                )
+        import shlex
+        args = self.tox_args
+        if args:
+            args = shlex.split(self.tox_args)
+        else:
+            args = []
+        errno = tox.cmdline(args=args)
+        sys.exit(errno)
+
+
 version = exec_file(("synapse", "__init__.py"))["__version__"]
 dependencies = exec_file(("synapse", "python_dependencies.py"))
 long_description = read_file(("README.rst",))
@@ -47,14 +81,10 @@ setup(
     packages=find_packages(exclude=["tests", "tests.*"]),
     description="Reference Synapse Home Server",
     install_requires=dependencies['requirements'](include_conditional=True).keys(),
-    setup_requires=[
-        "Twisted>=15.1.0", # Here to override setuptools_trial's dependency on Twisted>=2.4.0
-        "setuptools_trial",
-        "mock"
-    ],
     dependency_links=dependencies["DEPENDENCY_LINKS"],
     include_package_data=True,
     zip_safe=False,
     long_description=long_description,
     scripts=["synctl"] + glob.glob("scripts/*"),
+    cmdclass={'test': Tox},
 )
diff --git a/synapse/api/auth.py b/synapse/api/auth.py
index 1e3b0fbfb7..65ee1452ce 100644
--- a/synapse/api/auth.py
+++ b/synapse/api/auth.py
@@ -20,7 +20,7 @@ from twisted.internet import defer
 from synapse.api.constants import EventTypes, Membership, JoinRules
 from synapse.api.errors import AuthError, Codes, SynapseError
 from synapse.util.logutils import log_function
-from synapse.types import UserID, ClientInfo
+from synapse.types import UserID
 
 import logging
 
@@ -322,9 +322,9 @@ class Auth(object):
         Args:
             request - An HTTP request with an access_token query parameter.
         Returns:
-            tuple : of UserID and device string:
-                User ID object of the user making the request
-                ClientInfo object of the client instance the user is using
+            tuple of:
+                UserID (str)
+                Access token ID (str)
         Raises:
             AuthError if no user by that token exists or the token is invalid.
         """
@@ -354,16 +354,13 @@ class Auth(object):
 
                 request.authenticated_entity = user_id
 
-                defer.returnValue(
-                    (UserID.from_string(user_id), ClientInfo("", ""))
-                )
+                defer.returnValue((UserID.from_string(user_id), ""))
                 return
             except KeyError:
                 pass  # normal users won't have the user_id query parameter set.
 
-            user_info = yield self.get_user_by_token(access_token)
+            user_info = yield self.get_user_by_access_token(access_token)
             user = user_info["user"]
-            device_id = user_info["device_id"]
             token_id = user_info["token_id"]
 
             ip_addr = self.hs.get_ip_from_request(request)
@@ -375,14 +372,13 @@ class Auth(object):
                 self.store.insert_client_ip(
                     user=user,
                     access_token=access_token,
-                    device_id=user_info["device_id"],
                     ip=ip_addr,
                     user_agent=user_agent
                 )
 
             request.authenticated_entity = user.to_string()
 
-            defer.returnValue((user, ClientInfo(device_id, token_id)))
+            defer.returnValue((user, token_id,))
         except KeyError:
             raise AuthError(
                 self.TOKEN_NOT_FOUND_HTTP_STATUS, "Missing access token.",
@@ -390,26 +386,23 @@ class Auth(object):
             )
 
     @defer.inlineCallbacks
-    def get_user_by_token(self, token):
+    def get_user_by_access_token(self, token):
         """ Get a registered user's ID.
 
         Args:
             token (str): The access token to get the user by.
         Returns:
-            dict : dict that includes the user, device_id, and whether the
-                user is a server admin.
+            dict : dict that includes the user and the ID of their access token.
         Raises:
             AuthError if no user by that token exists or the token is invalid.
         """
-        ret = yield self.store.get_user_by_token(token)
+        ret = yield self.store.get_user_by_access_token(token)
         if not ret:
             raise AuthError(
                 self.TOKEN_NOT_FOUND_HTTP_STATUS, "Unrecognised access token.",
                 errcode=Codes.UNKNOWN_TOKEN
             )
         user_info = {
-            "admin": bool(ret.get("admin", False)),
-            "device_id": ret.get("device_id"),
             "user": UserID.from_string(ret.get("name")),
             "token_id": ret.get("token_id", None),
         }
diff --git a/synapse/config/key.py b/synapse/config/key.py
index 0494c0cb77..23ac8a3fca 100644
--- a/synapse/config/key.py
+++ b/synapse/config/key.py
@@ -13,14 +13,17 @@
 # See the License for the specific language governing permissions and
 # limitations under the License.
 
-import os
 from ._base import Config, ConfigError
-import syutil.crypto.signing_key
-from syutil.crypto.signing_key import (
-    is_signing_algorithm_supported, decode_verify_key_bytes
-)
-from syutil.base64util import decode_base64
+
 from synapse.util.stringutils import random_string
+from signedjson.key import (
+    generate_signing_key, is_signing_algorithm_supported,
+    decode_signing_key_base64, decode_verify_key_bytes,
+    read_signing_keys, write_signing_keys, NACL_ED25519
+)
+from unpaddedbase64 import decode_base64
+
+import os
 
 
 class KeyConfig(Config):
@@ -83,9 +86,7 @@ class KeyConfig(Config):
     def read_signing_key(self, signing_key_path):
         signing_keys = self.read_file(signing_key_path, "signing_key")
         try:
-            return syutil.crypto.signing_key.read_signing_keys(
-                signing_keys.splitlines(True)
-            )
+            return read_signing_keys(signing_keys.splitlines(True))
         except Exception:
             raise ConfigError(
                 "Error reading signing_key."
@@ -112,22 +113,18 @@ class KeyConfig(Config):
         if not os.path.exists(signing_key_path):
             with open(signing_key_path, "w") as signing_key_file:
                 key_id = "a_" + random_string(4)
-                syutil.crypto.signing_key.write_signing_keys(
-                    signing_key_file,
-                    (syutil.crypto.signing_key.generate_signing_key(key_id),),
+                write_signing_keys(
+                    signing_key_file, (generate_signing_key(key_id),),
                 )
         else:
             signing_keys = self.read_file(signing_key_path, "signing_key")
             if len(signing_keys.split("\n")[0].split()) == 1:
                 # handle keys in the old format.
                 key_id = "a_" + random_string(4)
-                key = syutil.crypto.signing_key.decode_signing_key_base64(
-                    syutil.crypto.signing_key.NACL_ED25519,
-                    key_id,
-                    signing_keys.split("\n")[0]
+                key = decode_signing_key_base64(
+                    NACL_ED25519, key_id, signing_keys.split("\n")[0]
                 )
                 with open(signing_key_path, "w") as signing_key_file:
-                    syutil.crypto.signing_key.write_signing_keys(
-                        signing_key_file,
-                        (key,),
+                    write_signing_keys(
+                        signing_key_file, (key,),
                     )
diff --git a/synapse/config/registration.py b/synapse/config/registration.py
index 67e780864e..62de4b399f 100644
--- a/synapse/config/registration.py
+++ b/synapse/config/registration.py
@@ -32,9 +32,11 @@ class RegistrationConfig(Config):
             )
 
         self.registration_shared_secret = config.get("registration_shared_secret")
+        self.macaroon_secret_key = config.get("macaroon_secret_key")
 
     def default_config(self, config_dir, server_name):
         registration_shared_secret = random_string_with_symbols(50)
+        macaroon_secret_key = random_string_with_symbols(50)
         return """\
         ## Registration ##
 
@@ -44,6 +46,8 @@ class RegistrationConfig(Config):
         # If set, allows registration by anyone who also has the shared
         # secret, even if registration is otherwise disabled.
         registration_shared_secret: "%(registration_shared_secret)s"
+
+        macaroon_secret_key: "%(macaroon_secret_key)s"
         """ % locals()
 
     def add_arguments(self, parser):
diff --git a/synapse/crypto/event_signing.py b/synapse/crypto/event_signing.py
index 6633b19565..64e40864af 100644
--- a/synapse/crypto/event_signing.py
+++ b/synapse/crypto/event_signing.py
@@ -15,11 +15,12 @@
 # limitations under the License.
 
 
-from synapse.events.utils import prune_event
-from syutil.jsonutil import encode_canonical_json
-from syutil.base64util import encode_base64, decode_base64
-from syutil.crypto.jsonsign import sign_json
 from synapse.api.errors import SynapseError, Codes
+from synapse.events.utils import prune_event
+
+from canonicaljson import encode_canonical_json
+from unpaddedbase64 import encode_base64, decode_base64
+from signedjson.sign import sign_json
 
 import hashlib
 import logging
diff --git a/synapse/crypto/keyring.py b/synapse/crypto/keyring.py
index aa74d4d0cb..a692cdbe55 100644
--- a/synapse/crypto/keyring.py
+++ b/synapse/crypto/keyring.py
@@ -14,20 +14,20 @@
 # limitations under the License.
 
 from synapse.crypto.keyclient import fetch_server_key
+from synapse.api.errors import SynapseError, Codes
+from synapse.util.retryutils import get_retry_limiter
+from synapse.util import unwrapFirstError
+from synapse.util.async import ObservableDeferred
+
 from twisted.internet import defer
-from syutil.crypto.jsonsign import (
+
+from signedjson.sign import (
     verify_signed_json, signature_ids, sign_json, encode_canonical_json
 )
-from syutil.crypto.signing_key import (
+from signedjson.key import (
     is_signing_algorithm_supported, decode_verify_key_bytes
 )
-from syutil.base64util import decode_base64, encode_base64
-from synapse.api.errors import SynapseError, Codes
-
-from synapse.util.retryutils import get_retry_limiter
-from synapse.util import unwrapFirstError
-
-from synapse.util.async import ObservableDeferred
+from unpaddedbase64 import decode_base64, encode_base64
 
 from OpenSSL import crypto
 
diff --git a/synapse/handlers/admin.py b/synapse/handlers/admin.py
index 1c9e7152c7..d852a18555 100644
--- a/synapse/handlers/admin.py
+++ b/synapse/handlers/admin.py
@@ -34,6 +34,7 @@ class AdminHandler(BaseHandler):
 
         d = {}
         for r in res:
+            # Note that device_id is always None
             device = d.setdefault(r["device_id"], {})
             session = device.setdefault(r["access_token"], [])
             session.append({
diff --git a/synapse/handlers/auth.py b/synapse/handlers/auth.py
index 602c5bcd89..1ab19cd1a6 100644
--- a/synapse/handlers/auth.py
+++ b/synapse/handlers/auth.py
@@ -26,6 +26,7 @@ from twisted.web.client import PartialDownloadError
 
 import logging
 import bcrypt
+import pymacaroons
 import simplejson
 
 import synapse.util.stringutils as stringutils
@@ -279,7 +280,10 @@ class AuthHandler(BaseHandler):
             user_id (str): User ID
             password (str): Password
         Returns:
-            The access token for the user's session.
+            A tuple of:
+              The user's ID.
+              The access token for the user's session.
+              The refresh token for the user's session.
         Raises:
             StoreError if there was a problem storing the token.
             LoginError if there was an authentication problem.
@@ -287,11 +291,10 @@ class AuthHandler(BaseHandler):
         user_id, password_hash = yield self._find_user_id_and_pwd_hash(user_id)
         self._check_password(user_id, password, password_hash)
 
-        reg_handler = self.hs.get_handlers().registration_handler
-        access_token = reg_handler.generate_token(user_id)
         logger.info("Logging in user %s", user_id)
-        yield self.store.add_access_token_to_user(user_id, access_token)
-        defer.returnValue((user_id, access_token))
+        access_token = yield self.issue_access_token(user_id)
+        refresh_token = yield self.issue_refresh_token(user_id)
+        defer.returnValue((user_id, access_token, refresh_token))
 
     @defer.inlineCallbacks
     def _find_user_id_and_pwd_hash(self, user_id):
@@ -326,6 +329,45 @@ class AuthHandler(BaseHandler):
             raise LoginError(403, "", errcode=Codes.FORBIDDEN)
 
     @defer.inlineCallbacks
+    def issue_access_token(self, user_id):
+        access_token = self.generate_access_token(user_id)
+        yield self.store.add_access_token_to_user(user_id, access_token)
+        defer.returnValue(access_token)
+
+    @defer.inlineCallbacks
+    def issue_refresh_token(self, user_id):
+        refresh_token = self.generate_refresh_token(user_id)
+        yield self.store.add_refresh_token_to_user(user_id, refresh_token)
+        defer.returnValue(refresh_token)
+
+    def generate_access_token(self, user_id):
+        macaroon = self._generate_base_macaroon(user_id)
+        macaroon.add_first_party_caveat("type = access")
+        now = self.hs.get_clock().time_msec()
+        expiry = now + (60 * 60 * 1000)
+        macaroon.add_first_party_caveat("time < %d" % (expiry,))
+        return macaroon.serialize()
+
+    def generate_refresh_token(self, user_id):
+        m = self._generate_base_macaroon(user_id)
+        m.add_first_party_caveat("type = refresh")
+        # Important to add a nonce, because otherwise every refresh token for a
+        # user will be the same.
+        m.add_first_party_caveat("nonce = %s" % (
+            stringutils.random_string_with_symbols(16),
+        ))
+        return m.serialize()
+
+    def _generate_base_macaroon(self, user_id):
+        macaroon = pymacaroons.Macaroon(
+            location=self.hs.config.server_name,
+            identifier="key",
+            key=self.hs.config.macaroon_secret_key)
+        macaroon.add_first_party_caveat("gen = 1")
+        macaroon.add_first_party_caveat("user_id = %s" % (user_id,))
+        return macaroon
+
+    @defer.inlineCallbacks
     def set_password(self, user_id, newpassword):
         password_hash = bcrypt.hashpw(newpassword, bcrypt.gensalt())
 
diff --git a/synapse/handlers/message.py b/synapse/handlers/message.py
index f12465fa2c..23b779ad7c 100644
--- a/synapse/handlers/message.py
+++ b/synapse/handlers/message.py
@@ -183,7 +183,7 @@ class MessageHandler(BaseHandler):
 
     @defer.inlineCallbacks
     def create_and_send_event(self, event_dict, ratelimit=True,
-                              client=None, txn_id=None):
+                              token_id=None, txn_id=None):
         """ Given a dict from a client, create and handle a new event.
 
         Creates an FrozenEvent object, filling out auth_events, prev_events,
@@ -217,11 +217,8 @@ class MessageHandler(BaseHandler):
                     builder.content
                 )
 
-        if client is not None:
-            if client.token_id is not None:
-                builder.internal_metadata.token_id = client.token_id
-            if client.device_id is not None:
-                builder.internal_metadata.device_id = client.device_id
+        if token_id is not None:
+            builder.internal_metadata.token_id = token_id
 
         if txn_id is not None:
             builder.internal_metadata.txn_id = txn_id
diff --git a/synapse/handlers/register.py b/synapse/handlers/register.py
index 86390a3671..56d125f753 100644
--- a/synapse/handlers/register.py
+++ b/synapse/handlers/register.py
@@ -25,7 +25,6 @@ import synapse.util.stringutils as stringutils
 from synapse.util.async import run_on_reactor
 from synapse.http.client import CaptchaServerHttpClient
 
-import base64
 import bcrypt
 import logging
 import urllib
@@ -91,7 +90,7 @@ class RegistrationHandler(BaseHandler):
             user = UserID(localpart, self.hs.hostname)
             user_id = user.to_string()
 
-            token = self.generate_token(user_id)
+            token = self.auth_handler().generate_access_token(user_id)
             yield self.store.register(
                 user_id=user_id,
                 token=token,
@@ -111,7 +110,7 @@ class RegistrationHandler(BaseHandler):
                     user_id = user.to_string()
                     yield self.check_user_id_is_valid(user_id)
 
-                    token = self.generate_token(user_id)
+                    token = self.auth_handler().generate_access_token(user_id)
                     yield self.store.register(
                         user_id=user_id,
                         token=token,
@@ -161,7 +160,7 @@ class RegistrationHandler(BaseHandler):
                 400, "Invalid user localpart for this application service.",
                 errcode=Codes.EXCLUSIVE
             )
-        token = self.generate_token(user_id)
+        token = self.auth_handler().generate_access_token(user_id)
         yield self.store.register(
             user_id=user_id,
             token=token,
@@ -208,7 +207,7 @@ class RegistrationHandler(BaseHandler):
         user_id = user.to_string()
 
         yield self.check_user_id_is_valid(user_id)
-        token = self.generate_token(user_id)
+        token = self.auth_handler().generate_access_token(user_id)
         try:
             yield self.store.register(
                 user_id=user_id,
@@ -273,13 +272,6 @@ class RegistrationHandler(BaseHandler):
                     errcode=Codes.EXCLUSIVE
                 )
 
-    def generate_token(self, user_id):
-        # urlsafe variant uses _ and - so use . as the separator and replace
-        # all =s with .s so http clients don't quote =s when it is used as
-        # query params.
-        return (base64.urlsafe_b64encode(user_id).replace('=', '.') + '.' +
-                stringutils.random_string(18))
-
     def _generate_user_id(self):
         return "-" + stringutils.random_string(18)
 
@@ -322,3 +314,6 @@ class RegistrationHandler(BaseHandler):
             }
         )
         defer.returnValue(data)
+
+    def auth_handler(self):
+        return self.hs.get_handlers().auth_handler
diff --git a/synapse/handlers/sync.py b/synapse/handlers/sync.py
index 353a416054..9914ff6f9c 100644
--- a/synapse/handlers/sync.py
+++ b/synapse/handlers/sync.py
@@ -28,7 +28,6 @@ logger = logging.getLogger(__name__)
 
 SyncConfig = collections.namedtuple("SyncConfig", [
     "user",
-    "client_info",
     "limit",
     "gap",
     "sort",
diff --git a/synapse/http/client.py b/synapse/http/client.py
index 49737d55da..4b8fd3d3a3 100644
--- a/synapse/http/client.py
+++ b/synapse/http/client.py
@@ -15,9 +15,10 @@
 
 from synapse.api.errors import CodeMessageException
 from synapse.util.logcontext import preserve_context_over_fn
-from syutil.jsonutil import encode_canonical_json
 import synapse.metrics
 
+from canonicaljson import encode_canonical_json
+
 from twisted.internet import defer, reactor
 from twisted.web.client import (
     Agent, readBody, FileBodyProducer, PartialDownloadError,
diff --git a/synapse/http/matrixfederationclient.py b/synapse/http/matrixfederationclient.py
index 854e17a473..1c9e552788 100644
--- a/synapse/http/matrixfederationclient.py
+++ b/synapse/http/matrixfederationclient.py
@@ -25,13 +25,13 @@ from synapse.util.async import sleep
 from synapse.util.logcontext import preserve_context_over_fn
 import synapse.metrics
 
-from syutil.jsonutil import encode_canonical_json
+from canonicaljson import encode_canonical_json
 
 from synapse.api.errors import (
     SynapseError, Codes, HttpResponseException,
 )
 
-from syutil.crypto.jsonsign import sign_json
+from signedjson.sign import sign_json
 
 import simplejson as json
 import logging
diff --git a/synapse/http/server.py b/synapse/http/server.py
index b60e905a62..50feea6f1c 100644
--- a/synapse/http/server.py
+++ b/synapse/http/server.py
@@ -21,8 +21,8 @@ from synapse.util.logcontext import LoggingContext, PreserveLoggingContext
 import synapse.metrics
 import synapse.events
 
-from syutil.jsonutil import (
-    encode_canonical_json, encode_pretty_printed_json, encode_json
+from canonicaljson import (
+    encode_canonical_json, encode_pretty_printed_json
 )
 
 from twisted.internet import defer
@@ -33,6 +33,7 @@ from twisted.web.util import redirectTo
 import collections
 import logging
 import urllib
+import ujson
 
 logger = logging.getLogger(__name__)
 
@@ -270,12 +271,11 @@ def respond_with_json(request, code, json_object, send_cors=False,
     if pretty_print:
         json_bytes = encode_pretty_printed_json(json_object) + "\n"
     else:
-        if canonical_json:
+        if canonical_json or synapse.events.USE_FROZEN_DICTS:
             json_bytes = encode_canonical_json(json_object)
         else:
-            json_bytes = encode_json(
-                json_object, using_frozen_dicts=synapse.events.USE_FROZEN_DICTS
-            )
+            # ujson doesn't like frozen_dicts.
+            json_bytes = ujson.dumps(json_object, ensure_ascii=False)
 
     return respond_with_json_bytes(
         request, code, json_bytes,
diff --git a/synapse/python_dependencies.py b/synapse/python_dependencies.py
index d7e3a686fa..8ec272fd5f 100644
--- a/synapse/python_dependencies.py
+++ b/synapse/python_dependencies.py
@@ -18,13 +18,15 @@ from distutils.version import LooseVersion
 logger = logging.getLogger(__name__)
 
 REQUIREMENTS = {
-    "syutil>=0.0.7": ["syutil>=0.0.7"],
+    "unpaddedbase64>=1.0.1": ["unpaddedbase64>=1.0.1"],
+    "canonicaljson>=1.0.0": ["canonicaljson>=1.0.0"],
+    "signedjson>=1.0.0": ["signedjson>=1.0.0"],
     "Twisted>=15.1.0": ["twisted>=15.1.0"],
     "service_identity>=1.0.0": ["service_identity>=1.0.0"],
     "pyopenssl>=0.14": ["OpenSSL>=0.14"],
     "pyyaml": ["yaml"],
     "pyasn1": ["pyasn1"],
-    "pynacl>=0.0.3": ["nacl>=0.0.3"],
+    "pynacl>=0.3.0": ["nacl>=0.3.0"],
     "daemonize": ["daemonize"],
     "py-bcrypt": ["bcrypt"],
     "frozendict>=0.4": ["frozendict"],
@@ -33,6 +35,7 @@ REQUIREMENTS = {
     "ujson": ["ujson"],
     "blist": ["blist"],
     "pysaml2": ["saml2"],
+    "pymacaroons-pynacl": ["pymacaroons"],
 }
 CONDITIONAL_REQUIREMENTS = {
     "web_client": {
@@ -53,11 +56,6 @@ def github_link(project, version, egg):
     return "https://github.com/%s/tarball/%s/#egg=%s" % (project, version, egg)
 
 DEPENDENCY_LINKS = {
-    "syutil": github_link(
-        project="matrix-org/syutil",
-        version="v0.0.7",
-        egg="syutil-0.0.7",
-    ),
     "matrix-angular-sdk": github_link(
         project="matrix-org/matrix-angular-sdk",
         version="v0.6.6",
diff --git a/synapse/rest/client/v1/admin.py b/synapse/rest/client/v1/admin.py
index 2ce754b028..504b63eab4 100644
--- a/synapse/rest/client/v1/admin.py
+++ b/synapse/rest/client/v1/admin.py
@@ -31,7 +31,7 @@ class WhoisRestServlet(ClientV1RestServlet):
     @defer.inlineCallbacks
     def on_GET(self, request, user_id):
         target_user = UserID.from_string(user_id)
-        auth_user, client = yield self.auth.get_user_by_req(request)
+        auth_user, _ = yield self.auth.get_user_by_req(request)
         is_admin = yield self.auth.is_server_admin(auth_user)
 
         if not is_admin and target_user != auth_user:
diff --git a/synapse/rest/client/v1/directory.py b/synapse/rest/client/v1/directory.py
index 6758a888b3..4dcda57c1b 100644
--- a/synapse/rest/client/v1/directory.py
+++ b/synapse/rest/client/v1/directory.py
@@ -69,7 +69,7 @@ class ClientDirectoryServer(ClientV1RestServlet):
 
         try:
             # try to auth as a user
-            user, client = yield self.auth.get_user_by_req(request)
+            user, _ = yield self.auth.get_user_by_req(request)
             try:
                 user_id = user.to_string()
                 yield dir_handler.create_association(
@@ -116,7 +116,7 @@ class ClientDirectoryServer(ClientV1RestServlet):
             # fallback to default user behaviour if they aren't an AS
             pass
 
-        user, client = yield self.auth.get_user_by_req(request)
+        user, _ = yield self.auth.get_user_by_req(request)
 
         is_admin = yield self.auth.is_server_admin(user)
         if not is_admin:
diff --git a/synapse/rest/client/v1/events.py b/synapse/rest/client/v1/events.py
index 77b7c25a03..582148b659 100644
--- a/synapse/rest/client/v1/events.py
+++ b/synapse/rest/client/v1/events.py
@@ -34,7 +34,7 @@ class EventStreamRestServlet(ClientV1RestServlet):
 
     @defer.inlineCallbacks
     def on_GET(self, request):
-        auth_user, client = yield self.auth.get_user_by_req(request)
+        auth_user, _ = yield self.auth.get_user_by_req(request)
         try:
             handler = self.handlers.event_stream_handler
             pagin_config = PaginationConfig.from_request(request)
@@ -71,7 +71,7 @@ class EventRestServlet(ClientV1RestServlet):
 
     @defer.inlineCallbacks
     def on_GET(self, request, event_id):
-        auth_user, client = yield self.auth.get_user_by_req(request)
+        auth_user, _ = yield self.auth.get_user_by_req(request)
         handler = self.handlers.event_handler
         event = yield handler.get_event(auth_user, event_id)
 
diff --git a/synapse/rest/client/v1/initial_sync.py b/synapse/rest/client/v1/initial_sync.py
index 4a259bba64..4ea4da653c 100644
--- a/synapse/rest/client/v1/initial_sync.py
+++ b/synapse/rest/client/v1/initial_sync.py
@@ -25,7 +25,7 @@ class InitialSyncRestServlet(ClientV1RestServlet):
 
     @defer.inlineCallbacks
     def on_GET(self, request):
-        user, client = yield self.auth.get_user_by_req(request)
+        user, _ = yield self.auth.get_user_by_req(request)
         with_feedback = "feedback" in request.args
         as_client_event = "raw" not in request.args
         pagination_config = PaginationConfig.from_request(request)
diff --git a/synapse/rest/client/v1/login.py b/synapse/rest/client/v1/login.py
index 2444f27366..e580f71964 100644
--- a/synapse/rest/client/v1/login.py
+++ b/synapse/rest/client/v1/login.py
@@ -86,13 +86,15 @@ class LoginRestServlet(ClientV1RestServlet):
                 user_id, self.hs.hostname
             ).to_string()
 
-        user_id, token = yield self.handlers.auth_handler.login_with_password(
+        auth_handler = self.handlers.auth_handler
+        user_id, access_token, refresh_token = yield auth_handler.login_with_password(
             user_id=user_id,
             password=login_submission["password"])
 
         result = {
             "user_id": user_id,  # may have changed
-            "access_token": token,
+            "access_token": access_token,
+            "refresh_token": refresh_token,
             "home_server": self.hs.hostname,
         }
 
diff --git a/synapse/rest/client/v1/presence.py b/synapse/rest/client/v1/presence.py
index 78d4f2b128..a770efd841 100644
--- a/synapse/rest/client/v1/presence.py
+++ b/synapse/rest/client/v1/presence.py
@@ -32,7 +32,7 @@ class PresenceStatusRestServlet(ClientV1RestServlet):
 
     @defer.inlineCallbacks
     def on_GET(self, request, user_id):
-        auth_user, client = yield self.auth.get_user_by_req(request)
+        auth_user, _ = yield self.auth.get_user_by_req(request)
         user = UserID.from_string(user_id)
 
         state = yield self.handlers.presence_handler.get_state(
@@ -42,7 +42,7 @@ class PresenceStatusRestServlet(ClientV1RestServlet):
 
     @defer.inlineCallbacks
     def on_PUT(self, request, user_id):
-        auth_user, client = yield self.auth.get_user_by_req(request)
+        auth_user, _ = yield self.auth.get_user_by_req(request)
         user = UserID.from_string(user_id)
 
         state = {}
@@ -77,7 +77,7 @@ class PresenceListRestServlet(ClientV1RestServlet):
 
     @defer.inlineCallbacks
     def on_GET(self, request, user_id):
-        auth_user, client = yield self.auth.get_user_by_req(request)
+        auth_user, _ = yield self.auth.get_user_by_req(request)
         user = UserID.from_string(user_id)
 
         if not self.hs.is_mine(user):
@@ -97,7 +97,7 @@ class PresenceListRestServlet(ClientV1RestServlet):
 
     @defer.inlineCallbacks
     def on_POST(self, request, user_id):
-        auth_user, client = yield self.auth.get_user_by_req(request)
+        auth_user, _ = yield self.auth.get_user_by_req(request)
         user = UserID.from_string(user_id)
 
         if not self.hs.is_mine(user):
diff --git a/synapse/rest/client/v1/profile.py b/synapse/rest/client/v1/profile.py
index 1e77eb49cf..fdde88a60d 100644
--- a/synapse/rest/client/v1/profile.py
+++ b/synapse/rest/client/v1/profile.py
@@ -37,7 +37,7 @@ class ProfileDisplaynameRestServlet(ClientV1RestServlet):
 
     @defer.inlineCallbacks
     def on_PUT(self, request, user_id):
-        auth_user, client = yield self.auth.get_user_by_req(request)
+        auth_user, _ = yield self.auth.get_user_by_req(request)
         user = UserID.from_string(user_id)
 
         try:
@@ -70,7 +70,7 @@ class ProfileAvatarURLRestServlet(ClientV1RestServlet):
 
     @defer.inlineCallbacks
     def on_PUT(self, request, user_id):
-        auth_user, client = yield self.auth.get_user_by_req(request)
+        auth_user, _ = yield self.auth.get_user_by_req(request)
         user = UserID.from_string(user_id)
 
         try:
diff --git a/synapse/rest/client/v1/pusher.py b/synapse/rest/client/v1/pusher.py
index c83287c028..3aabc93b8b 100644
--- a/synapse/rest/client/v1/pusher.py
+++ b/synapse/rest/client/v1/pusher.py
@@ -27,7 +27,7 @@ class PusherRestServlet(ClientV1RestServlet):
 
     @defer.inlineCallbacks
     def on_POST(self, request):
-        user, client = yield self.auth.get_user_by_req(request)
+        user, token_id = yield self.auth.get_user_by_req(request)
 
         content = _parse_json(request)
 
@@ -65,7 +65,7 @@ class PusherRestServlet(ClientV1RestServlet):
         try:
             yield pusher_pool.add_pusher(
                 user_name=user.to_string(),
-                access_token=client.token_id,
+                access_token=token_id,
                 profile_tag=content['profile_tag'],
                 kind=content['kind'],
                 app_id=content['app_id'],
diff --git a/synapse/rest/client/v1/room.py b/synapse/rest/client/v1/room.py
index b4a70cba99..c9c27dd5a0 100644
--- a/synapse/rest/client/v1/room.py
+++ b/synapse/rest/client/v1/room.py
@@ -62,7 +62,7 @@ class RoomCreateRestServlet(ClientV1RestServlet):
 
     @defer.inlineCallbacks
     def on_POST(self, request):
-        auth_user, client = yield self.auth.get_user_by_req(request)
+        auth_user, _ = yield self.auth.get_user_by_req(request)
 
         room_config = self.get_room_config(request)
         info = yield self.make_room(room_config, auth_user, None)
@@ -125,7 +125,7 @@ class RoomStateEventRestServlet(ClientV1RestServlet):
 
     @defer.inlineCallbacks
     def on_GET(self, request, room_id, event_type, state_key):
-        user, client = yield self.auth.get_user_by_req(request)
+        user, _ = yield self.auth.get_user_by_req(request)
 
         msg_handler = self.handlers.message_handler
         data = yield msg_handler.get_room_data(
@@ -143,7 +143,7 @@ class RoomStateEventRestServlet(ClientV1RestServlet):
 
     @defer.inlineCallbacks
     def on_PUT(self, request, room_id, event_type, state_key, txn_id=None):
-        user, client = yield self.auth.get_user_by_req(request)
+        user, token_id = yield self.auth.get_user_by_req(request)
 
         content = _parse_json(request)
 
@@ -159,7 +159,7 @@ class RoomStateEventRestServlet(ClientV1RestServlet):
 
         msg_handler = self.handlers.message_handler
         yield msg_handler.create_and_send_event(
-            event_dict, client=client, txn_id=txn_id,
+            event_dict, token_id=token_id, txn_id=txn_id,
         )
 
         defer.returnValue((200, {}))
@@ -175,7 +175,7 @@ class RoomSendEventRestServlet(ClientV1RestServlet):
 
     @defer.inlineCallbacks
     def on_POST(self, request, room_id, event_type, txn_id=None):
-        user, client = yield self.auth.get_user_by_req(request)
+        user, token_id = yield self.auth.get_user_by_req(request)
         content = _parse_json(request)
 
         msg_handler = self.handlers.message_handler
@@ -186,7 +186,7 @@ class RoomSendEventRestServlet(ClientV1RestServlet):
                 "room_id": room_id,
                 "sender": user.to_string(),
             },
-            client=client,
+            token_id=token_id,
             txn_id=txn_id,
         )
 
@@ -220,7 +220,7 @@ class JoinRoomAliasServlet(ClientV1RestServlet):
 
     @defer.inlineCallbacks
     def on_POST(self, request, room_identifier, txn_id=None):
-        user, client = yield self.auth.get_user_by_req(request)
+        user, token_id = yield self.auth.get_user_by_req(request)
 
         # the identifier could be a room alias or a room id. Try one then the
         # other if it fails to parse, without swallowing other valid
@@ -250,7 +250,7 @@ class JoinRoomAliasServlet(ClientV1RestServlet):
                     "sender": user.to_string(),
                     "state_key": user.to_string(),
                 },
-                client=client,
+                token_id=token_id,
                 txn_id=txn_id,
             )
 
@@ -289,7 +289,7 @@ class RoomMemberListRestServlet(ClientV1RestServlet):
     @defer.inlineCallbacks
     def on_GET(self, request, room_id):
         # TODO support Pagination stream API (limit/tokens)
-        user, client = yield self.auth.get_user_by_req(request)
+        user, _ = yield self.auth.get_user_by_req(request)
         handler = self.handlers.room_member_handler
         members = yield handler.get_room_members_as_pagination_chunk(
             room_id=room_id,
@@ -317,7 +317,7 @@ class RoomMessageListRestServlet(ClientV1RestServlet):
 
     @defer.inlineCallbacks
     def on_GET(self, request, room_id):
-        user, client = yield self.auth.get_user_by_req(request)
+        user, _ = yield self.auth.get_user_by_req(request)
         pagination_config = PaginationConfig.from_request(
             request, default_limit=10,
         )
@@ -341,7 +341,7 @@ class RoomStateRestServlet(ClientV1RestServlet):
 
     @defer.inlineCallbacks
     def on_GET(self, request, room_id):
-        user, client = yield self.auth.get_user_by_req(request)
+        user, _ = yield self.auth.get_user_by_req(request)
         handler = self.handlers.message_handler
         # Get all the current state for this room
         events = yield handler.get_state_events(
@@ -357,7 +357,7 @@ class RoomInitialSyncRestServlet(ClientV1RestServlet):
 
     @defer.inlineCallbacks
     def on_GET(self, request, room_id):
-        user, client = yield self.auth.get_user_by_req(request)
+        user, _ = yield self.auth.get_user_by_req(request)
         pagination_config = PaginationConfig.from_request(request)
         content = yield self.handlers.message_handler.room_initial_sync(
             room_id=room_id,
@@ -402,7 +402,7 @@ class RoomMembershipRestServlet(ClientV1RestServlet):
 
     @defer.inlineCallbacks
     def on_POST(self, request, room_id, membership_action, txn_id=None):
-        user, client = yield self.auth.get_user_by_req(request)
+        user, token_id = yield self.auth.get_user_by_req(request)
 
         content = _parse_json(request)
 
@@ -427,7 +427,7 @@ class RoomMembershipRestServlet(ClientV1RestServlet):
                 "sender": user.to_string(),
                 "state_key": state_key,
             },
-            client=client,
+            token_id=token_id,
             txn_id=txn_id,
         )
 
@@ -457,7 +457,7 @@ class RoomRedactEventRestServlet(ClientV1RestServlet):
 
     @defer.inlineCallbacks
     def on_POST(self, request, room_id, event_id, txn_id=None):
-        user, client = yield self.auth.get_user_by_req(request)
+        user, token_id = yield self.auth.get_user_by_req(request)
         content = _parse_json(request)
 
         msg_handler = self.handlers.message_handler
@@ -469,7 +469,7 @@ class RoomRedactEventRestServlet(ClientV1RestServlet):
                 "sender": user.to_string(),
                 "redacts": event_id,
             },
-            client=client,
+            token_id=token_id,
             txn_id=txn_id,
         )
 
@@ -497,7 +497,7 @@ class RoomTypingRestServlet(ClientV1RestServlet):
 
     @defer.inlineCallbacks
     def on_PUT(self, request, room_id, user_id):
-        auth_user, client = yield self.auth.get_user_by_req(request)
+        auth_user, _ = yield self.auth.get_user_by_req(request)
 
         room_id = urllib.unquote(room_id)
         target_user = UserID.from_string(urllib.unquote(user_id))
diff --git a/synapse/rest/client/v1/voip.py b/synapse/rest/client/v1/voip.py
index 11d08fbced..0a863e1c61 100644
--- a/synapse/rest/client/v1/voip.py
+++ b/synapse/rest/client/v1/voip.py
@@ -28,7 +28,7 @@ class VoipRestServlet(ClientV1RestServlet):
 
     @defer.inlineCallbacks
     def on_GET(self, request):
-        auth_user, client = yield self.auth.get_user_by_req(request)
+        auth_user, _ = yield self.auth.get_user_by_req(request)
 
         turnUris = self.hs.config.turn_uris
         turnSecret = self.hs.config.turn_shared_secret
@@ -40,7 +40,7 @@ class VoipRestServlet(ClientV1RestServlet):
         username = "%d:%s" % (expiry, auth_user.to_string())
 
         mac = hmac.new(turnSecret, msg=username, digestmod=hashlib.sha1)
-        # We need to use standard base64 encoding here, *not* syutil's
+        # We need to use standard padded base64 encoding here
         # encode_base64 because we need to add the standard padding to get the
         # same result as the TURN server.
         password = base64.b64encode(mac.digest())
diff --git a/synapse/rest/client/v2_alpha/__init__.py b/synapse/rest/client/v2_alpha/__init__.py
index 33f961e898..5831ff0e62 100644
--- a/synapse/rest/client/v2_alpha/__init__.py
+++ b/synapse/rest/client/v2_alpha/__init__.py
@@ -21,6 +21,7 @@ from . import (
     auth,
     receipts,
     keys,
+    tokenrefresh,
 )
 
 from synapse.http.server import JsonResource
@@ -42,3 +43,4 @@ class ClientV2AlphaRestResource(JsonResource):
         auth.register_servlets(hs, client_resource)
         receipts.register_servlets(hs, client_resource)
         keys.register_servlets(hs, client_resource)
+        tokenrefresh.register_servlets(hs, client_resource)
diff --git a/synapse/rest/client/v2_alpha/account.py b/synapse/rest/client/v2_alpha/account.py
index 522a312c9e..b5edffdb60 100644
--- a/synapse/rest/client/v2_alpha/account.py
+++ b/synapse/rest/client/v2_alpha/account.py
@@ -55,7 +55,7 @@ class PasswordRestServlet(RestServlet):
 
         if LoginType.PASSWORD in result:
             # if using password, they should also be logged in
-            auth_user, client = yield self.auth.get_user_by_req(request)
+            auth_user, _ = yield self.auth.get_user_by_req(request)
             if auth_user.to_string() != result[LoginType.PASSWORD]:
                 raise LoginError(400, "", Codes.UNKNOWN)
             user_id = auth_user.to_string()
@@ -119,7 +119,7 @@ class ThreepidRestServlet(RestServlet):
             raise SynapseError(400, "Missing param", Codes.MISSING_PARAM)
         threePidCreds = body['threePidCreds']
 
-        auth_user, client = yield self.auth.get_user_by_req(request)
+        auth_user, _ = yield self.auth.get_user_by_req(request)
 
         threepid = yield self.identity_handler.threepid_from_creds(threePidCreds)
 
diff --git a/synapse/rest/client/v2_alpha/filter.py b/synapse/rest/client/v2_alpha/filter.py
index 703250cea8..f8f91b63f5 100644
--- a/synapse/rest/client/v2_alpha/filter.py
+++ b/synapse/rest/client/v2_alpha/filter.py
@@ -40,7 +40,7 @@ class GetFilterRestServlet(RestServlet):
     @defer.inlineCallbacks
     def on_GET(self, request, user_id, filter_id):
         target_user = UserID.from_string(user_id)
-        auth_user, client = yield self.auth.get_user_by_req(request)
+        auth_user, _ = yield self.auth.get_user_by_req(request)
 
         if target_user != auth_user:
             raise AuthError(403, "Cannot get filters for other users")
@@ -76,7 +76,7 @@ class CreateFilterRestServlet(RestServlet):
     @defer.inlineCallbacks
     def on_POST(self, request, user_id):
         target_user = UserID.from_string(user_id)
-        auth_user, client = yield self.auth.get_user_by_req(request)
+        auth_user, _ = yield self.auth.get_user_by_req(request)
 
         if target_user != auth_user:
             raise AuthError(403, "Cannot create filters for other users")
diff --git a/synapse/rest/client/v2_alpha/keys.py b/synapse/rest/client/v2_alpha/keys.py
index 718928eedd..a1f4423101 100644
--- a/synapse/rest/client/v2_alpha/keys.py
+++ b/synapse/rest/client/v2_alpha/keys.py
@@ -18,7 +18,8 @@ from twisted.internet import defer
 from synapse.api.errors import SynapseError
 from synapse.http.servlet import RestServlet
 from synapse.types import UserID
-from syutil.jsonutil import encode_canonical_json
+
+from canonicaljson import encode_canonical_json
 
 from ._base import client_v2_pattern
 
@@ -63,7 +64,7 @@ class KeyUploadServlet(RestServlet):
 
     @defer.inlineCallbacks
     def on_POST(self, request, device_id):
-        auth_user, client_info = yield self.auth.get_user_by_req(request)
+        auth_user, _ = yield self.auth.get_user_by_req(request)
         user_id = auth_user.to_string()
         # TODO: Check that the device_id matches that in the authentication
         # or derive the device_id from the authentication instead.
@@ -108,7 +109,7 @@ class KeyUploadServlet(RestServlet):
 
     @defer.inlineCallbacks
     def on_GET(self, request, device_id):
-        auth_user, client_info = yield self.auth.get_user_by_req(request)
+        auth_user, _ = yield self.auth.get_user_by_req(request)
         user_id = auth_user.to_string()
 
         result = yield self.store.count_e2e_one_time_keys(user_id, device_id)
@@ -180,7 +181,7 @@ class KeyQueryServlet(RestServlet):
 
     @defer.inlineCallbacks
     def on_GET(self, request, user_id, device_id):
-        auth_user, client_info = yield self.auth.get_user_by_req(request)
+        auth_user, _ = yield self.auth.get_user_by_req(request)
         auth_user_id = auth_user.to_string()
         user_id = user_id if user_id else auth_user_id
         device_ids = [device_id] if device_id else []
diff --git a/synapse/rest/client/v2_alpha/receipts.py b/synapse/rest/client/v2_alpha/receipts.py
index 40406e2ede..52e99f54d5 100644
--- a/synapse/rest/client/v2_alpha/receipts.py
+++ b/synapse/rest/client/v2_alpha/receipts.py
@@ -39,7 +39,7 @@ class ReceiptRestServlet(RestServlet):
 
     @defer.inlineCallbacks
     def on_POST(self, request, room_id, receipt_type, event_id):
-        user, client = yield self.auth.get_user_by_req(request)
+        user, _ = yield self.auth.get_user_by_req(request)
 
         yield self.receipts_handler.received_client_receipt(
             room_id,
diff --git a/synapse/rest/client/v2_alpha/sync.py b/synapse/rest/client/v2_alpha/sync.py
index f2fd0b9f32..cac28b47b6 100644
--- a/synapse/rest/client/v2_alpha/sync.py
+++ b/synapse/rest/client/v2_alpha/sync.py
@@ -87,7 +87,7 @@ class SyncRestServlet(RestServlet):
 
     @defer.inlineCallbacks
     def on_GET(self, request):
-        user, client = yield self.auth.get_user_by_req(request)
+        user, token_id = yield self.auth.get_user_by_req(request)
 
         timeout = parse_integer(request, "timeout", default=0)
         limit = parse_integer(request, "limit", required=True)
@@ -125,7 +125,6 @@ class SyncRestServlet(RestServlet):
 
         sync_config = SyncConfig(
             user=user,
-            client_info=client,
             gap=gap,
             limit=limit,
             sort=sort,
@@ -152,7 +151,7 @@ class SyncRestServlet(RestServlet):
                 sync_result.private_user_data, filter, time_now
             ),
             "rooms": self.encode_rooms(
-                sync_result.rooms, filter, time_now, client.token_id
+                sync_result.rooms, filter, time_now, token_id
             ),
             "next_batch": sync_result.next_batch.to_string(),
         }
diff --git a/synapse/rest/client/v2_alpha/tokenrefresh.py b/synapse/rest/client/v2_alpha/tokenrefresh.py
new file mode 100644
index 0000000000..901e777983
--- /dev/null
+++ b/synapse/rest/client/v2_alpha/tokenrefresh.py
@@ -0,0 +1,56 @@
+# -*- coding: utf-8 -*-
+# Copyright 2015 OpenMarket Ltd
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#     http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+from twisted.internet import defer
+
+from synapse.api.errors import AuthError, StoreError, SynapseError
+from synapse.http.servlet import RestServlet
+
+from ._base import client_v2_pattern, parse_json_dict_from_request
+
+
+class TokenRefreshRestServlet(RestServlet):
+    """
+    Exchanges refresh tokens for a pair of an access token and a new refresh
+    token.
+    """
+    PATTERN = client_v2_pattern("/tokenrefresh")
+
+    def __init__(self, hs):
+        super(TokenRefreshRestServlet, self).__init__()
+        self.hs = hs
+        self.store = hs.get_datastore()
+
+    @defer.inlineCallbacks
+    def on_POST(self, request):
+        body = parse_json_dict_from_request(request)
+        try:
+            old_refresh_token = body["refresh_token"]
+            auth_handler = self.hs.get_handlers().auth_handler
+            (user_id, new_refresh_token) = yield self.store.exchange_refresh_token(
+                old_refresh_token, auth_handler.generate_refresh_token)
+            new_access_token = yield auth_handler.issue_access_token(user_id)
+            defer.returnValue((200, {
+                "access_token": new_access_token,
+                "refresh_token": new_refresh_token,
+            }))
+        except KeyError:
+            raise SynapseError(400, "Missing required key 'refresh_token'.")
+        except StoreError:
+            raise AuthError(403, "Did not recognize refresh token")
+
+
+def register_servlets(hs, http_server):
+    TokenRefreshRestServlet(hs).register(http_server)
diff --git a/synapse/rest/key/v1/server_key_resource.py b/synapse/rest/key/v1/server_key_resource.py
index 71e9a51f5c..6df46969c4 100644
--- a/synapse/rest/key/v1/server_key_resource.py
+++ b/synapse/rest/key/v1/server_key_resource.py
@@ -16,9 +16,9 @@
 
 from twisted.web.resource import Resource
 from synapse.http.server import respond_with_json_bytes
-from syutil.crypto.jsonsign import sign_json
-from syutil.base64util import encode_base64
-from syutil.jsonutil import encode_canonical_json
+from signedjson.sign import sign_json
+from unpaddedbase64 import encode_base64
+from canonicaljson import encode_canonical_json
 from OpenSSL import crypto
 import logging
 
diff --git a/synapse/rest/key/v2/local_key_resource.py b/synapse/rest/key/v2/local_key_resource.py
index 33cbd7cf8e..ef7699d590 100644
--- a/synapse/rest/key/v2/local_key_resource.py
+++ b/synapse/rest/key/v2/local_key_resource.py
@@ -16,9 +16,9 @@
 
 from twisted.web.resource import Resource
 from synapse.http.server import respond_with_json_bytes
-from syutil.crypto.jsonsign import sign_json
-from syutil.base64util import encode_base64
-from syutil.jsonutil import encode_canonical_json
+from signedjson.sign import sign_json
+from unpaddedbase64 import encode_base64
+from canonicaljson import encode_canonical_json
 from hashlib import sha256
 from OpenSSL import crypto
 import logging
diff --git a/synapse/rest/media/v0/content_repository.py b/synapse/rest/media/v0/content_repository.py
index e77a20fb2e..c28dc86cd7 100644
--- a/synapse/rest/media/v0/content_repository.py
+++ b/synapse/rest/media/v0/content_repository.py
@@ -66,7 +66,7 @@ class ContentRepoResource(resource.Resource):
     @defer.inlineCallbacks
     def map_request_to_name(self, request):
         # auth the user
-        auth_user, client = yield self.auth.get_user_by_req(request)
+        auth_user, _ = yield self.auth.get_user_by_req(request)
 
         # namespace all file uploads on the user
         prefix = base64.urlsafe_b64encode(
diff --git a/synapse/rest/media/v1/upload_resource.py b/synapse/rest/media/v1/upload_resource.py
index 031bfa80f8..6abaf56b25 100644
--- a/synapse/rest/media/v1/upload_resource.py
+++ b/synapse/rest/media/v1/upload_resource.py
@@ -70,7 +70,7 @@ class UploadResource(BaseMediaResource):
     @request_handler
     @defer.inlineCallbacks
     def _async_render_POST(self, request):
-        auth_user, client = yield self.auth.get_user_by_req(request)
+        auth_user, _ = yield self.auth.get_user_by_req(request)
         # TODO: The checks here are a bit late. The content will have
         # already been uploaded to a tmp file at this point
         content_length = request.getHeader("Content-Length")
diff --git a/synapse/storage/__init__.py b/synapse/storage/__init__.py
index f154b1c8ae..77cb1dbd81 100644
--- a/synapse/storage/__init__.py
+++ b/synapse/storage/__init__.py
@@ -54,7 +54,7 @@ logger = logging.getLogger(__name__)
 
 # Remember to update this number every time a change is made to database
 # schema files, so the users will be informed on server restarts.
-SCHEMA_VERSION = 22
+SCHEMA_VERSION = 23
 
 dir_path = os.path.abspath(os.path.dirname(__file__))
 
@@ -94,9 +94,9 @@ class DataStore(RoomMemberStore, RoomStore,
         )
 
     @defer.inlineCallbacks
-    def insert_client_ip(self, user, access_token, device_id, ip, user_agent):
+    def insert_client_ip(self, user, access_token, ip, user_agent):
         now = int(self._clock.time_msec())
-        key = (user.to_string(), access_token, device_id, ip)
+        key = (user.to_string(), access_token, ip)
 
         try:
             last_seen = self.client_ip_last_seen.get(key)
@@ -120,7 +120,6 @@ class DataStore(RoomMemberStore, RoomStore,
                 "user_agent": user_agent,
             },
             values={
-                "device_id": device_id,
                 "last_seen": now,
             },
             desc="insert_client_ip",
@@ -132,7 +131,7 @@ class DataStore(RoomMemberStore, RoomStore,
             table="user_ips",
             keyvalues={"user_id": user.to_string()},
             retcols=[
-                "device_id", "access_token", "ip", "user_agent", "last_seen"
+                "access_token", "ip", "user_agent", "last_seen"
             ],
             desc="get_user_ip_and_agents",
         )
diff --git a/synapse/storage/_base.py b/synapse/storage/_base.py
index 1444767a52..ce71389f02 100644
--- a/synapse/storage/_base.py
+++ b/synapse/storage/_base.py
@@ -181,6 +181,7 @@ class SQLBaseStore(object):
         self._transaction_id_gen = IdGenerator("sent_transactions", "id", self)
         self._state_groups_id_gen = IdGenerator("state_groups", "id", self)
         self._access_tokens_id_gen = IdGenerator("access_tokens", "id", self)
+        self._refresh_tokens_id_gen = IdGenerator("refresh_tokens", "id", self)
         self._pushers_id_gen = IdGenerator("pushers", "id", self)
         self._push_rule_id_gen = IdGenerator("push_rules", "id", self)
         self._push_rules_enable_id_gen = IdGenerator("push_rules_enable", "id", self)
diff --git a/synapse/storage/event_federation.py b/synapse/storage/event_federation.py
index dda3027b61..989ad340b0 100644
--- a/synapse/storage/event_federation.py
+++ b/synapse/storage/event_federation.py
@@ -17,7 +17,7 @@ from twisted.internet import defer
 
 from ._base import SQLBaseStore
 from synapse.util.caches.descriptors import cached
-from syutil.base64util import encode_base64
+from unpaddedbase64 import encode_base64
 
 import logging
 from Queue import PriorityQueue, Empty
diff --git a/synapse/storage/events.py b/synapse/storage/events.py
index e3eabab13d..fba837f461 100644
--- a/synapse/storage/events.py
+++ b/synapse/storage/events.py
@@ -24,7 +24,7 @@ from synapse.util.logcontext import preserve_context_over_deferred
 from synapse.util.logutils import log_function
 from synapse.api.constants import EventTypes
 
-from syutil.jsonutil import encode_json
+from canonicaljson import encode_canonical_json
 from contextlib import contextmanager
 
 import logging
@@ -33,6 +33,13 @@ import ujson as json
 logger = logging.getLogger(__name__)
 
 
+def encode_json(json_object):
+    if USE_FROZEN_DICTS:
+        # ujson doesn't like frozen_dicts
+        return encode_canonical_json(json_object)
+    else:
+        return json.dumps(json_object, ensure_ascii=False)
+
 # These values are used in the `enqueus_event` and `_do_fetch` methods to
 # control how we batch/bulk fetch events from the database.
 # The values are plucked out of thing air to make initial sync run faster
@@ -253,8 +260,7 @@ class EventsStore(SQLBaseStore):
                 )
 
                 metadata_json = encode_json(
-                    event.internal_metadata.get_dict(),
-                    using_frozen_dicts=USE_FROZEN_DICTS
+                    event.internal_metadata.get_dict()
                 ).decode("UTF-8")
 
                 sql = (
@@ -329,12 +335,9 @@ class EventsStore(SQLBaseStore):
                     "event_id": event.event_id,
                     "room_id": event.room_id,
                     "internal_metadata": encode_json(
-                        event.internal_metadata.get_dict(),
-                        using_frozen_dicts=USE_FROZEN_DICTS
-                    ).decode("UTF-8"),
-                    "json": encode_json(
-                        event_dict(event), using_frozen_dicts=USE_FROZEN_DICTS
+                        event.internal_metadata.get_dict()
                     ).decode("UTF-8"),
+                    "json": encode_json(event_dict(event)).decode("UTF-8"),
                 }
                 for event, _ in events_and_contexts
             ],
@@ -353,9 +356,7 @@ class EventsStore(SQLBaseStore):
                     "type": event.type,
                     "processed": True,
                     "outlier": event.internal_metadata.is_outlier(),
-                    "content": encode_json(
-                        event.content, using_frozen_dicts=USE_FROZEN_DICTS
-                    ).decode("UTF-8"),
+                    "content": encode_json(event.content).decode("UTF-8"),
                 }
                 for event, _ in events_and_contexts
             ],
diff --git a/synapse/storage/keys.py b/synapse/storage/keys.py
index ffd6daa880..344cacdc75 100644
--- a/synapse/storage/keys.py
+++ b/synapse/storage/keys.py
@@ -19,7 +19,7 @@ from synapse.util.caches.descriptors import cachedInlineCallbacks
 from twisted.internet import defer
 
 import OpenSSL
-from syutil.crypto.signing_key import decode_verify_key_bytes
+from signedjson.key import decode_verify_key_bytes
 import hashlib
 
 
diff --git a/synapse/storage/pusher.py b/synapse/storage/pusher.py
index 08ea62681b..00b748f131 100644
--- a/synapse/storage/pusher.py
+++ b/synapse/storage/pusher.py
@@ -18,7 +18,7 @@ from twisted.internet import defer
 
 from synapse.api.errors import StoreError
 
-from syutil.jsonutil import encode_canonical_json
+from canonicaljson import encode_canonical_json
 
 import logging
 import simplejson as json
diff --git a/synapse/storage/registration.py b/synapse/storage/registration.py
index 586628579d..c9ceb132ae 100644
--- a/synapse/storage/registration.py
+++ b/synapse/storage/registration.py
@@ -51,6 +51,28 @@ class RegistrationStore(SQLBaseStore):
         )
 
     @defer.inlineCallbacks
+    def add_refresh_token_to_user(self, user_id, token):
+        """Adds a refresh token for the given user.
+
+        Args:
+            user_id (str): The user ID.
+            token (str): The new refresh token to add.
+        Raises:
+            StoreError if there was a problem adding this.
+        """
+        next_id = yield self._refresh_tokens_id_gen.get_next()
+
+        yield self._simple_insert(
+            "refresh_tokens",
+            {
+                "id": next_id,
+                "user_id": user_id,
+                "token": token
+            },
+            desc="add_refresh_token_to_user",
+        )
+
+    @defer.inlineCallbacks
     def register(self, user_id, token, password_hash):
         """Attempts to register an account.
 
@@ -146,26 +168,65 @@ class RegistrationStore(SQLBaseStore):
             user_id
         )
         for r in rows:
-            self.get_user_by_token.invalidate((r,))
+            self.get_user_by_access_token.invalidate((r,))
 
     @cached()
-    def get_user_by_token(self, token):
+    def get_user_by_access_token(self, token):
         """Get a user from the given access token.
 
         Args:
             token (str): The access token of a user.
         Returns:
-            dict: Including the name (user_id), device_id and whether they are
-                an admin.
+            dict: Including the name (user_id) and the ID of their access token.
         Raises:
             StoreError if no user was found.
         """
         return self.runInteraction(
-            "get_user_by_token",
+            "get_user_by_access_token",
             self._query_for_auth,
             token
         )
 
+    def exchange_refresh_token(self, refresh_token, token_generator):
+        """Exchange a refresh token for a new access token and refresh token.
+
+        Doing so invalidates the old refresh token - refresh tokens are single
+        use.
+
+        Args:
+            token (str): The refresh token of a user.
+            token_generator (fn: str -> str): Function which, when given a
+                user ID, returns a unique refresh token for that user. This
+                function must never return the same value twice.
+        Returns:
+            tuple of (user_id, refresh_token)
+        Raises:
+            StoreError if no user was found with that refresh token.
+        """
+        return self.runInteraction(
+            "exchange_refresh_token",
+            self._exchange_refresh_token,
+            refresh_token,
+            token_generator
+        )
+
+    def _exchange_refresh_token(self, txn, old_token, token_generator):
+        sql = "SELECT user_id FROM refresh_tokens WHERE token = ?"
+        txn.execute(sql, (old_token,))
+        rows = self.cursor_to_dict(txn)
+        if not rows:
+            raise StoreError(403, "Did not recognize refresh token")
+        user_id = rows[0]["user_id"]
+
+        # TODO(danielwh): Maybe perform a validation on the macaroon that
+        # macaroon.user_id == user_id.
+
+        new_token = token_generator(user_id)
+        sql = "UPDATE refresh_tokens SET token = ? WHERE token = ?"
+        txn.execute(sql, (new_token, old_token,))
+
+        return user_id, new_token
+
     @defer.inlineCallbacks
     def is_server_admin(self, user):
         res = yield self._simple_select_one_onecol(
@@ -180,8 +241,7 @@ class RegistrationStore(SQLBaseStore):
 
     def _query_for_auth(self, txn, token):
         sql = (
-            "SELECT users.name, users.admin,"
-            " access_tokens.device_id, access_tokens.id as token_id"
+            "SELECT users.name, access_tokens.id as token_id"
             " FROM users"
             " INNER JOIN access_tokens on users.name = access_tokens.user_id"
             " WHERE token = ?"
diff --git a/synapse/storage/schema/delta/23/refresh_tokens.sql b/synapse/storage/schema/delta/23/refresh_tokens.sql
new file mode 100644
index 0000000000..437b1ac1be
--- /dev/null
+++ b/synapse/storage/schema/delta/23/refresh_tokens.sql
@@ -0,0 +1,21 @@
+/* Copyright 2015 OpenMarket Ltd
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+CREATE TABLE IF NOT EXISTS refresh_tokens(
+    id INTEGER PRIMARY KEY,
+    token TEXT NOT NULL,
+    user_id TEXT NOT NULL,
+    UNIQUE (token)
+);
diff --git a/synapse/storage/signatures.py b/synapse/storage/signatures.py
index 4f15e534b4..ab57b92174 100644
--- a/synapse/storage/signatures.py
+++ b/synapse/storage/signatures.py
@@ -17,7 +17,7 @@ from twisted.internet import defer
 
 from _base import SQLBaseStore
 
-from syutil.base64util import encode_base64
+from unpaddedbase64 import encode_base64
 from synapse.crypto.event_signing import compute_event_reference_hash
 
 
diff --git a/synapse/storage/transactions.py b/synapse/storage/transactions.py
index c8c7e6591a..15695e9831 100644
--- a/synapse/storage/transactions.py
+++ b/synapse/storage/transactions.py
@@ -18,7 +18,7 @@ from synapse.util.caches.descriptors import cached
 
 from collections import namedtuple
 
-from syutil.jsonutil import encode_canonical_json
+from canonicaljson import encode_canonical_json
 import logging
 
 logger = logging.getLogger(__name__)
diff --git a/synapse/types.py b/synapse/types.py
index e190374cbd..9cffc33d27 100644
--- a/synapse/types.py
+++ b/synapse/types.py
@@ -209,7 +209,3 @@ class RoomStreamToken(namedtuple("_StreamToken", "topological stream")):
             return "t%d-%d" % (self.topological, self.stream)
         else:
             return "s%d" % (self.stream,)
-
-
-# token_id is the primary key ID of the access token, not the access token itself.
-ClientInfo = namedtuple("ClientInfo", ("device_id", "token_id"))
diff --git a/tests/api/test_auth.py b/tests/api/test_auth.py
index 4f83db5e84..22fc804331 100644
--- a/tests/api/test_auth.py
+++ b/tests/api/test_auth.py
@@ -40,21 +40,19 @@ class AuthTestCase(unittest.TestCase):
         self.store.get_app_service_by_token = Mock(return_value=None)
         user_info = {
             "name": self.test_user,
-            "device_id": "nothing",
             "token_id": "ditto",
-            "admin": False
         }
-        self.store.get_user_by_token = Mock(return_value=user_info)
+        self.store.get_user_by_access_token = Mock(return_value=user_info)
 
         request = Mock(args={})
         request.args["access_token"] = [self.test_token]
         request.requestHeaders.getRawHeaders = Mock(return_value=[""])
-        (user, info) = yield self.auth.get_user_by_req(request)
+        (user, _) = yield self.auth.get_user_by_req(request)
         self.assertEquals(user.to_string(), self.test_user)
 
     def test_get_user_by_req_user_bad_token(self):
         self.store.get_app_service_by_token = Mock(return_value=None)
-        self.store.get_user_by_token = Mock(return_value=None)
+        self.store.get_user_by_access_token = Mock(return_value=None)
 
         request = Mock(args={})
         request.args["access_token"] = [self.test_token]
@@ -66,11 +64,9 @@ class AuthTestCase(unittest.TestCase):
         self.store.get_app_service_by_token = Mock(return_value=None)
         user_info = {
             "name": self.test_user,
-            "device_id": "nothing",
             "token_id": "ditto",
-            "admin": False
         }
-        self.store.get_user_by_token = Mock(return_value=user_info)
+        self.store.get_user_by_access_token = Mock(return_value=user_info)
 
         request = Mock(args={})
         request.requestHeaders.getRawHeaders = Mock(return_value=[""])
@@ -81,17 +77,17 @@ class AuthTestCase(unittest.TestCase):
     def test_get_user_by_req_appservice_valid_token(self):
         app_service = Mock(token="foobar", url="a_url", sender=self.test_user)
         self.store.get_app_service_by_token = Mock(return_value=app_service)
-        self.store.get_user_by_token = Mock(return_value=None)
+        self.store.get_user_by_access_token = Mock(return_value=None)
 
         request = Mock(args={})
         request.args["access_token"] = [self.test_token]
         request.requestHeaders.getRawHeaders = Mock(return_value=[""])
-        (user, info) = yield self.auth.get_user_by_req(request)
+        (user, _) = yield self.auth.get_user_by_req(request)
         self.assertEquals(user.to_string(), self.test_user)
 
     def test_get_user_by_req_appservice_bad_token(self):
         self.store.get_app_service_by_token = Mock(return_value=None)
-        self.store.get_user_by_token = Mock(return_value=None)
+        self.store.get_user_by_access_token = Mock(return_value=None)
 
         request = Mock(args={})
         request.args["access_token"] = [self.test_token]
@@ -102,7 +98,7 @@ class AuthTestCase(unittest.TestCase):
     def test_get_user_by_req_appservice_missing_token(self):
         app_service = Mock(token="foobar", url="a_url", sender=self.test_user)
         self.store.get_app_service_by_token = Mock(return_value=app_service)
-        self.store.get_user_by_token = Mock(return_value=None)
+        self.store.get_user_by_access_token = Mock(return_value=None)
 
         request = Mock(args={})
         request.requestHeaders.getRawHeaders = Mock(return_value=[""])
@@ -115,13 +111,13 @@ class AuthTestCase(unittest.TestCase):
         app_service = Mock(token="foobar", url="a_url", sender=self.test_user)
         app_service.is_interested_in_user = Mock(return_value=True)
         self.store.get_app_service_by_token = Mock(return_value=app_service)
-        self.store.get_user_by_token = Mock(return_value=None)
+        self.store.get_user_by_access_token = Mock(return_value=None)
 
         request = Mock(args={})
         request.args["access_token"] = [self.test_token]
         request.args["user_id"] = [masquerading_user_id]
         request.requestHeaders.getRawHeaders = Mock(return_value=[""])
-        (user, info) = yield self.auth.get_user_by_req(request)
+        (user, _) = yield self.auth.get_user_by_req(request)
         self.assertEquals(user.to_string(), masquerading_user_id)
 
     def test_get_user_by_req_appservice_valid_token_bad_user_id(self):
@@ -129,7 +125,7 @@ class AuthTestCase(unittest.TestCase):
         app_service = Mock(token="foobar", url="a_url", sender=self.test_user)
         app_service.is_interested_in_user = Mock(return_value=False)
         self.store.get_app_service_by_token = Mock(return_value=app_service)
-        self.store.get_user_by_token = Mock(return_value=None)
+        self.store.get_user_by_access_token = Mock(return_value=None)
 
         request = Mock(args={})
         request.args["access_token"] = [self.test_token]
diff --git a/tests/handlers/test_auth.py b/tests/handlers/test_auth.py
new file mode 100644
index 0000000000..978e4d0d2e
--- /dev/null
+++ b/tests/handlers/test_auth.py
@@ -0,0 +1,70 @@
+# -*- coding: utf-8 -*-
+# Copyright 2015 OpenMarket Ltd
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#     http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+import pymacaroons
+
+from mock import Mock, NonCallableMock
+from synapse.handlers.auth import AuthHandler
+from tests import unittest
+from tests.utils import setup_test_homeserver
+from twisted.internet import defer
+
+
+class AuthHandlers(object):
+    def __init__(self, hs):
+        self.auth_handler = AuthHandler(hs)
+
+
+class AuthTestCase(unittest.TestCase):
+    @defer.inlineCallbacks
+    def setUp(self):
+        self.hs = yield setup_test_homeserver(handlers=None)
+        self.hs.handlers = AuthHandlers(self.hs)
+
+    def test_token_is_a_macaroon(self):
+        self.hs.config.macaroon_secret_key = "this key is a huge secret"
+
+        token = self.hs.handlers.auth_handler.generate_access_token("some_user")
+        # Check that we can parse the thing with pymacaroons
+        macaroon = pymacaroons.Macaroon.deserialize(token)
+        # The most basic of sanity checks
+        if "some_user" not in macaroon.inspect():
+            self.fail("some_user was not in %s" % macaroon.inspect())
+
+    def test_macaroon_caveats(self):
+        self.hs.config.macaroon_secret_key = "this key is a massive secret"
+        self.hs.clock.now = 5000
+
+        token = self.hs.handlers.auth_handler.generate_access_token("a_user")
+        macaroon = pymacaroons.Macaroon.deserialize(token)
+
+        def verify_gen(caveat):
+            return caveat == "gen = 1"
+
+        def verify_user(caveat):
+            return caveat == "user_id = a_user"
+
+        def verify_type(caveat):
+            return caveat == "type = access"
+
+        def verify_expiry(caveat):
+            return caveat == "time < 8600000"
+
+        v = pymacaroons.Verifier()
+        v.satisfy_general(verify_gen)
+        v.satisfy_general(verify_user)
+        v.satisfy_general(verify_type)
+        v.satisfy_general(verify_expiry)
+        v.verify(macaroon, self.hs.config.macaroon_secret_key)
diff --git a/tests/rest/client/v1/test_presence.py b/tests/rest/client/v1/test_presence.py
index 089a71568c..91547bdd06 100644
--- a/tests/rest/client/v1/test_presence.py
+++ b/tests/rest/client/v1/test_presence.py
@@ -70,15 +70,13 @@ class PresenceStateTestCase(unittest.TestCase):
             return defer.succeed([])
         self.datastore.get_presence_list = get_presence_list
 
-        def _get_user_by_token(token=None):
+        def _get_user_by_access_token(token=None):
             return {
                 "user": UserID.from_string(myid),
-                "admin": False,
-                "device_id": None,
                 "token_id": 1,
             }
 
-        hs.get_v1auth().get_user_by_token = _get_user_by_token
+        hs.get_v1auth().get_user_by_access_token = _get_user_by_access_token
 
         room_member_handler = hs.handlers.room_member_handler = Mock(
             spec=[
@@ -159,11 +157,9 @@ class PresenceListTestCase(unittest.TestCase):
             )
         self.datastore.has_presence_state = has_presence_state
 
-        def _get_user_by_token(token=None):
+        def _get_user_by_access_token(token=None):
             return {
                 "user": UserID.from_string(myid),
-                "admin": False,
-                "device_id": None,
                 "token_id": 1,
             }
 
@@ -173,7 +169,7 @@ class PresenceListTestCase(unittest.TestCase):
             ]
         )
 
-        hs.get_v1auth().get_user_by_token = _get_user_by_token
+        hs.get_v1auth().get_user_by_access_token = _get_user_by_access_token
 
         presence.register_servlets(hs, self.mock_resource)
 
diff --git a/tests/rest/client/v1/test_rooms.py b/tests/rest/client/v1/test_rooms.py
index c83348acf9..34ab47d02e 100644
--- a/tests/rest/client/v1/test_rooms.py
+++ b/tests/rest/client/v1/test_rooms.py
@@ -54,14 +54,12 @@ class RoomPermissionsTestCase(RestTestCase):
 
         hs.get_handlers().federation_handler = Mock()
 
-        def _get_user_by_token(token=None):
+        def _get_user_by_access_token(token=None):
             return {
                 "user": UserID.from_string(self.auth_user_id),
-                "admin": False,
-                "device_id": None,
                 "token_id": 1,
             }
-        hs.get_v1auth().get_user_by_token = _get_user_by_token
+        hs.get_v1auth().get_user_by_access_token = _get_user_by_access_token
 
         def _insert_client_ip(*args, **kwargs):
             return defer.succeed(None)
@@ -441,14 +439,12 @@ class RoomsMemberListTestCase(RestTestCase):
 
         self.auth_user_id = self.user_id
 
-        def _get_user_by_token(token=None):
+        def _get_user_by_access_token(token=None):
             return {
                 "user": UserID.from_string(self.auth_user_id),
-                "admin": False,
-                "device_id": None,
                 "token_id": 1,
             }
-        hs.get_v1auth().get_user_by_token = _get_user_by_token
+        hs.get_v1auth().get_user_by_access_token = _get_user_by_access_token
 
         def _insert_client_ip(*args, **kwargs):
             return defer.succeed(None)
@@ -521,14 +517,12 @@ class RoomsCreateTestCase(RestTestCase):
 
         hs.get_handlers().federation_handler = Mock()
 
-        def _get_user_by_token(token=None):
+        def _get_user_by_access_token(token=None):
             return {
                 "user": UserID.from_string(self.auth_user_id),
-                "admin": False,
-                "device_id": None,
                 "token_id": 1,
             }
-        hs.get_v1auth().get_user_by_token = _get_user_by_token
+        hs.get_v1auth().get_user_by_access_token = _get_user_by_access_token
 
         def _insert_client_ip(*args, **kwargs):
             return defer.succeed(None)
@@ -614,15 +608,13 @@ class RoomTopicTestCase(RestTestCase):
 
         hs.get_handlers().federation_handler = Mock()
 
-        def _get_user_by_token(token=None):
+        def _get_user_by_access_token(token=None):
             return {
                 "user": UserID.from_string(self.auth_user_id),
-                "admin": False,
-                "device_id": None,
                 "token_id": 1,
             }
 
-        hs.get_v1auth().get_user_by_token = _get_user_by_token
+        hs.get_v1auth().get_user_by_access_token = _get_user_by_access_token
 
         def _insert_client_ip(*args, **kwargs):
             return defer.succeed(None)
@@ -721,14 +713,12 @@ class RoomMemberStateTestCase(RestTestCase):
 
         hs.get_handlers().federation_handler = Mock()
 
-        def _get_user_by_token(token=None):
+        def _get_user_by_access_token(token=None):
             return {
                 "user": UserID.from_string(self.auth_user_id),
-                "admin": False,
-                "device_id": None,
                 "token_id": 1,
             }
-        hs.get_v1auth().get_user_by_token = _get_user_by_token
+        hs.get_v1auth().get_user_by_access_token = _get_user_by_access_token
 
         def _insert_client_ip(*args, **kwargs):
             return defer.succeed(None)
@@ -848,14 +838,12 @@ class RoomMessagesTestCase(RestTestCase):
 
         hs.get_handlers().federation_handler = Mock()
 
-        def _get_user_by_token(token=None):
+        def _get_user_by_access_token(token=None):
             return {
                 "user": UserID.from_string(self.auth_user_id),
-                "admin": False,
-                "device_id": None,
                 "token_id": 1,
             }
-        hs.get_v1auth().get_user_by_token = _get_user_by_token
+        hs.get_v1auth().get_user_by_access_token = _get_user_by_access_token
 
         def _insert_client_ip(*args, **kwargs):
             return defer.succeed(None)
@@ -945,14 +933,12 @@ class RoomInitialSyncTestCase(RestTestCase):
 
         hs.get_handlers().federation_handler = Mock()
 
-        def _get_user_by_token(token=None):
+        def _get_user_by_access_token(token=None):
             return {
                 "user": UserID.from_string(self.auth_user_id),
-                "admin": False,
-                "device_id": None,
                 "token_id": 1,
             }
-        hs.get_v1auth().get_user_by_token = _get_user_by_token
+        hs.get_v1auth().get_user_by_access_token = _get_user_by_access_token
 
         def _insert_client_ip(*args, **kwargs):
             return defer.succeed(None)
diff --git a/tests/rest/client/v1/test_typing.py b/tests/rest/client/v1/test_typing.py
index 7d8b1c2683..1c4519406d 100644
--- a/tests/rest/client/v1/test_typing.py
+++ b/tests/rest/client/v1/test_typing.py
@@ -61,15 +61,13 @@ class RoomTypingTestCase(RestTestCase):
 
         hs.get_handlers().federation_handler = Mock()
 
-        def _get_user_by_token(token=None):
+        def _get_user_by_access_token(token=None):
             return {
                 "user": UserID.from_string(self.auth_user_id),
-                "admin": False,
-                "device_id": None,
                 "token_id": 1,
             }
 
-        hs.get_v1auth().get_user_by_token = _get_user_by_token
+        hs.get_v1auth().get_user_by_access_token = _get_user_by_access_token
 
         def _insert_client_ip(*args, **kwargs):
             return defer.succeed(None)
diff --git a/tests/rest/client/v1/utils.py b/tests/rest/client/v1/utils.py
index 579441fb4a..c472d53043 100644
--- a/tests/rest/client/v1/utils.py
+++ b/tests/rest/client/v1/utils.py
@@ -37,7 +37,7 @@ class RestTestCase(unittest.TestCase):
         self.mock_resource = None
         self.auth_user_id = None
 
-    def mock_get_user_by_token(self, token=None):
+    def mock_get_user_by_access_token(self, token=None):
         return self.auth_user_id
 
     @defer.inlineCallbacks
diff --git a/tests/rest/client/v2_alpha/__init__.py b/tests/rest/client/v2_alpha/__init__.py
index de5a917e6a..ef972a53aa 100644
--- a/tests/rest/client/v2_alpha/__init__.py
+++ b/tests/rest/client/v2_alpha/__init__.py
@@ -43,14 +43,12 @@ class V2AlphaRestTestCase(unittest.TestCase):
             resource_for_federation=self.mock_resource,
         )
 
-        def _get_user_by_token(token=None):
+        def _get_user_by_access_token(token=None):
             return {
                 "user": UserID.from_string(self.USER_ID),
-                "admin": False,
-                "device_id": None,
                 "token_id": 1,
             }
-        hs.get_auth().get_user_by_token = _get_user_by_token
+        hs.get_auth().get_user_by_access_token = _get_user_by_access_token
 
         for r in self.TO_REGISTER:
             r.register_servlets(hs, self.mock_resource)
diff --git a/tests/storage/test_registration.py b/tests/storage/test_registration.py
index 2702291178..0cce6c37df 100644
--- a/tests/storage/test_registration.py
+++ b/tests/storage/test_registration.py
@@ -17,7 +17,9 @@
 from tests import unittest
 from twisted.internet import defer
 
+from synapse.api.errors import StoreError
 from synapse.storage.registration import RegistrationStore
+from synapse.util import stringutils
 
 from tests.utils import setup_test_homeserver
 
@@ -27,6 +29,7 @@ class RegistrationStoreTestCase(unittest.TestCase):
     @defer.inlineCallbacks
     def setUp(self):
         hs = yield setup_test_homeserver()
+        self.db_pool = hs.get_db_pool()
 
         self.store = RegistrationStore(hs)
 
@@ -46,13 +49,11 @@ class RegistrationStoreTestCase(unittest.TestCase):
             (yield self.store.get_user_by_id(self.user_id))
         )
 
-        result = yield self.store.get_user_by_token(self.tokens[0])
+        result = yield self.store.get_user_by_access_token(self.tokens[0])
 
         self.assertDictContainsSubset(
             {
-                "admin": 0,
-                 "device_id": None,
-                 "name": self.user_id,
+                "name": self.user_id,
             },
             result
         )
@@ -64,16 +65,66 @@ class RegistrationStoreTestCase(unittest.TestCase):
         yield self.store.register(self.user_id, self.tokens[0], self.pwhash)
         yield self.store.add_access_token_to_user(self.user_id, self.tokens[1])
 
-        result = yield self.store.get_user_by_token(self.tokens[1])
+        result = yield self.store.get_user_by_access_token(self.tokens[1])
 
         self.assertDictContainsSubset(
             {
-                "admin": 0,
-                 "device_id": None,
-                 "name": self.user_id,
+                "name": self.user_id,
             },
             result
         )
 
         self.assertTrue("token_id" in result)
 
+    @defer.inlineCallbacks
+    def test_exchange_refresh_token_valid(self):
+        uid = stringutils.random_string(32)
+        generator = TokenGenerator()
+        last_token = generator.generate(uid)
+
+        self.db_pool.runQuery(
+            "INSERT INTO refresh_tokens(user_id, token) VALUES(?,?)",
+            (uid, last_token,))
+
+        (found_user_id, refresh_token) = yield self.store.exchange_refresh_token(
+            last_token, generator.generate)
+        self.assertEqual(uid, found_user_id)
+
+        rows = yield self.db_pool.runQuery(
+            "SELECT token FROM refresh_tokens WHERE user_id = ?", (uid, ))
+        self.assertEqual([(refresh_token,)], rows)
+        # We issued token 1, then exchanged it for token 2
+        expected_refresh_token = u"%s-%d" % (uid, 2,)
+        self.assertEqual(expected_refresh_token, refresh_token)
+
+    @defer.inlineCallbacks
+    def test_exchange_refresh_token_none(self):
+        uid = stringutils.random_string(32)
+        generator = TokenGenerator()
+        last_token = generator.generate(uid)
+
+        with self.assertRaises(StoreError):
+            yield self.store.exchange_refresh_token(last_token, generator.generate)
+
+    @defer.inlineCallbacks
+    def test_exchange_refresh_token_invalid(self):
+        uid = stringutils.random_string(32)
+        generator = TokenGenerator()
+        last_token = generator.generate(uid)
+        wrong_token = "%s-wrong" % (last_token,)
+
+        self.db_pool.runQuery(
+            "INSERT INTO refresh_tokens(user_id, token) VALUES(?,?)",
+            (uid, wrong_token,))
+
+        with self.assertRaises(StoreError):
+            yield self.store.exchange_refresh_token(last_token, generator.generate)
+
+
+class TokenGenerator:
+    def __init__(self):
+        self._last_issued_token = 0
+
+    def generate(self, user_id):
+        self._last_issued_token += 1
+        return u"%s-%d" % (user_id, self._last_issued_token,)
diff --git a/tests/utils.py b/tests/utils.py
index eb035cf48f..3766a994f2 100644
--- a/tests/utils.py
+++ b/tests/utils.py
@@ -44,6 +44,8 @@ def setup_test_homeserver(name="test", datastore=None, config=None, **kargs):
         config.signing_key = [MockKey()]
         config.event_cache_size = 1
         config.disable_registration = False
+        config.macaroon_secret_key = "not even a little secret"
+        config.server_name = "server.under.test"
 
     if "clock" not in kargs:
         kargs["clock"] = MockClock()
@@ -275,12 +277,10 @@ class MemoryDataStore(object):
             raise StoreError(400, "User in use.")
         self.tokens_to_users[token] = user_id
 
-    def get_user_by_token(self, token):
+    def get_user_by_access_token(self, token):
         try:
             return {
                 "name": self.tokens_to_users[token],
-                "admin": 0,
-                "device_id": None,
             }
         except:
             raise StoreError(400, "User does not exist.")
@@ -378,7 +378,7 @@ class MemoryDataStore(object):
     def get_ops_levels(self, room_id):
         return defer.succeed((5, 5, 5))
 
-    def insert_client_ip(self, user, device_id, access_token, ip, user_agent):
+    def insert_client_ip(self, user, access_token, ip, user_agent):
         return defer.succeed(None)
 
 
diff --git a/tox.ini b/tox.ini
new file mode 100644
index 0000000000..3f0649b628
--- /dev/null
+++ b/tox.ini
@@ -0,0 +1,27 @@
+[tox]
+envlist = packaging, py27, pep8
+
+[testenv]
+deps =
+    coverage
+    Twisted>=15.1
+    mock
+setenv =
+    PYTHONDONTWRITEBYTECODE = no_byte_code
+commands =
+    coverage run --source=synapse {envbindir}/trial {posargs:tests}
+    coverage report -m
+install_command =
+    pip install --process-dependency-links --pre {opts} {packages}
+
+[testenv:packaging]
+deps =
+    check-manifest
+commands =
+    check-manifest
+
+[testenv:pep8]
+basepython = python2.7
+deps =
+    flake8
+commands = flake8 synapse