diff --git a/cryptography/fernet.py b/cryptography/fernet.py
index cdb9bdc..153f398 100644
--- a/cryptography/fernet.py
+++ b/cryptography/fernet.py
@@ -90,7 +90,7 @@
         except (TypeError, binascii.Error):
             raise InvalidToken
 
-        if six.indexbytes(data, 0) != 0x80:
+        if not data or  six.indexbytes(data, 0) != 0x80:
             raise InvalidToken
 
         try:
diff --git a/tests/test_fernet.py b/tests/test_fernet.py
index 0683d95..0b4e3e8 100644
--- a/tests/test_fernet.py
+++ b/tests/test_fernet.py
@@ -86,15 +86,20 @@
             f.decrypt(token.encode("ascii"), ttl=ttl_sec)
 
     def test_invalid_start_byte(self, backend):
-        f = Fernet(Fernet.generate_key(), backend=backend)
+        f = Fernet(base64.urlsafe_b64encode(b"\x00" * 32), backend=backend)
         with pytest.raises(InvalidToken):
             f.decrypt(base64.urlsafe_b64encode(b"\x81"))
 
     def test_timestamp_too_short(self, backend):
-        f = Fernet(Fernet.generate_key(), backend=backend)
+        f = Fernet(base64.urlsafe_b64encode(b"\x00" * 32), backend=backend)
         with pytest.raises(InvalidToken):
             f.decrypt(base64.urlsafe_b64encode(b"\x80abc"))
 
+    def test_non_base64_token(self, backend):
+        f = Fernet(base64.urlsafe_b64encode(b"\x00" * 32), backend=backend)
+        with pytest.raises(InvalidToken):
+            f.decrypt(b"\x00")
+
     def test_unicode(self, backend):
         f = Fernet(base64.urlsafe_b64encode(b"\x00" * 32), backend=backend)
         with pytest.raises(TypeError):