Switched everything to use cryptography

13 files changed, 258 insertions, 147 deletions

diff --git a/README b/README
index b5ccb697..666a0911 100644
--- a/README
+++ b/README
@@ -25,7 +25,7 @@ channels to remote services across the encrypted tunnel (this is how sftp
 works, for example).
 
 it is written entirely in python (no C or platform-dependent code) and is
-released under the GNU LGPL (lesser GPL). 
+released under the GNU LGPL (lesser GPL).
 
 the package and its API is fairly well documented in the "doc/" folder
 that should have come with this archive.
@@ -36,7 +36,7 @@ Requirements
 
   - Python 2.6 or better <http://www.python.org/> - this includes Python
     3.2 and higher as well.
-  - pycrypto 2.1 or better <https://www.dlitz.net/software/pycrypto/>
+  - Cryptography 0.5.4 or better <https://cryptography.io>
   - ecdsa 0.9 or better <https://pypi.python.org/pypi/ecdsa>
 
 If you have setuptools, you can build and install paramiko and all its
diff --git a/paramiko/dsskey.py b/paramiko/dsskey.py
index 1901596d..87293e3c 100644
--- a/paramiko/dsskey.py
+++ b/paramiko/dsskey.py
@@ -21,20 +21,31 @@ DSS keys.
 """
 
 import os
-from hashlib import sha1
 
-from Crypto.PublicKey import DSA
+from cryptography.exceptions import InvalidSignature
+from cryptography.hazmat.backends import default_backend
+from cryptography.hazmat.primitives import hashes
+from cryptography.hazmat.primitives.asymmetric import dsa
+
+from pyasn1.codec.der import encoder, decoder
+from pyasn1.type import namedtype, univ
 
 from paramiko import util
 from paramiko.common import zero_byte
-from paramiko.py3compat import long
 from paramiko.ssh_exception import SSHException
 from paramiko.message import Message
 from paramiko.ber import BER, BERException
 from paramiko.pkey import PKey
 
 
-class DSSKey (PKey):
+class _DSSSigValue(univ.Sequence):
+    componentType = namedtype.NamedTypes(
+        namedtype.NamedType('r', univ.Integer()),
+        namedtype.NamedType('s', univ.Integer())
+    )
+
+
+class DSSKey(PKey):
     """
     Representation of a DSS key which can be used to sign an verify SSH2
     data.
@@ -98,20 +109,27 @@ class DSSKey (PKey):
         return self.x is not None
 
     def sign_ssh_data(self, data):
-        digest = sha1(data).digest()
-        dss = DSA.construct((long(self.y), long(self.g), long(self.p), long(self.q), long(self.x)))
-        # generate a suitable k
-        qsize = len(util.deflate_long(self.q, 0))
-        while True:
-            k = util.inflate_long(os.urandom(qsize), 1)
-            if (k > 2) and (k < self.q):
-                break
-        r, s = dss.sign(util.inflate_long(digest, 1), k)
+        key = dsa.DSAPrivateNumbers(
+            x=self.x,
+            public_numbers=dsa.DSAPublicNumbers(
+                y=self.y,
+                parameter_numbers=dsa.DSAParameterNumbers(
+                    p=self.p,
+                    q=self.q,
+                    g=self.g
+                )
+            )
+        ).private_key(backend=default_backend())
+        signer = key.signer(hashes.SHA1())
+        signer.update(data)
+        signature = signer.finalize()
+        (r, s), _ = decoder.decode(signature)
+
         m = Message()
         m.add_string('ssh-dss')
         # apparently, in rare cases, r or s may be shorter than 20 bytes!
-        rstr = util.deflate_long(r, 0)
-        sstr = util.deflate_long(s, 0)
+        rstr = util.deflate_long(int(r), 0)
+        sstr = util.deflate_long(int(s), 0)
         if len(rstr) < 20:
             rstr = zero_byte * (20 - len(rstr)) + rstr
         if len(sstr) < 20:
@@ -132,10 +150,28 @@ class DSSKey (PKey):
         # pull out (r, s) which are NOT encoded as mpints
         sigR = util.inflate_long(sig[:20], 1)
         sigS = util.inflate_long(sig[20:], 1)
-        sigM = util.inflate_long(sha1(data).digest(), 1)
 
-        dss = DSA.construct((long(self.y), long(self.g), long(self.p), long(self.q)))
-        return dss.verify(sigM, (sigR, sigS))
+        sig_asn1 = _DSSSigValue()
+        sig_asn1.setComponentByName('r', sigR)
+        sig_asn1.setComponentByName('s', sigS)
+        signature = encoder.encode(sig_asn1)
+
+        key = dsa.DSAPublicNumbers(
+            y=self.y,
+            parameter_numbers=dsa.DSAParameterNumbers(
+                p=self.p,
+                q=self.q,
+                g=self.g
+            )
+        ).public_key(backend=default_backend())
+        verifier = key.verifier(signature, hashes.SHA1())
+        verifier.update(data)
+        try:
+            verifier.verify()
+        except InvalidSignature:
+            return False
+        else:
+            return True
 
     def _encode_key(self):
         if self.x is None:
@@ -160,14 +196,19 @@ class DSSKey (PKey):
         generate a new host key or authentication key.
 
         :param int bits: number of bits the generated key should be.
-        :param function progress_func:
-            an optional function to call at key points in key generation (used
-            by ``pyCrypto.PublicKey``).
+        :param function progress_func: Unused
         :return: new `.DSSKey` private key
         """
-        dsa = DSA.generate(bits, os.urandom, progress_func)
-        key = DSSKey(vals=(dsa.p, dsa.q, dsa.g, dsa.y))
-        key.x = dsa.x
+        numbers = dsa.generate_private_key(
+            bits, backend=default_backend()
+        ).private_numbers()
+        key = DSSKey(vals=(
+            numbers.public_numbers.parameter_numbers.p,
+            numbers.public_numbers.parameter_numbers.q,
+            numbers.public_numbers.parameter_numbers.g,
+            numbers.public_numbers.y
+        ))
+        key.x = numbers.x
         return key
     generate = staticmethod(generate)
 
diff --git a/paramiko/ecdsakey.py b/paramiko/ecdsakey.py
index e869ee61..9a000682 100644
--- a/paramiko/ecdsakey.py
+++ b/paramiko/ecdsakey.py
@@ -133,9 +133,7 @@ class ECDSAKey (PKey):
 
         @param bits: number of bits the generated key should be.
         @type bits: int
-        @param progress_func: an optional function to call at key points in
-            key generation (used by C{pyCrypto.PublicKey}).
-        @type progress_func: function
+        @param progress_func: Unused.
         @return: new private key
         @rtype: L{RSAKey}
         """
diff --git a/paramiko/kex_gss.py b/paramiko/kex_gss.py
index a319b33b..3c7ebe39 100644
--- a/paramiko/kex_gss.py
+++ b/paramiko/kex_gss.py
@@ -37,7 +37,6 @@ This module provides GSS-API / SSPI Key Exchange as defined in RFC 4462.
 """
 
 
-from Crypto.Hash import SHA
 from paramiko.common import *
 from paramiko import util
 from paramiko.message import Message
diff --git a/paramiko/packet.py b/paramiko/packet.py
index f516ff9b..9599db9b 100644
--- a/paramiko/packet.py
+++ b/paramiko/packet.py
@@ -307,7 +307,7 @@ class Packetizer (object):
                 self._log(DEBUG, 'Write packet <%s>, length %d' % (cmd_name, orig_len))
                 self._log(DEBUG, util.format_binary(packet, 'OUT: '))
             if self.__block_engine_out is not None:
-                out = self.__block_engine_out.encrypt(packet)
+                out = self.__block_engine_out.update(packet)
             else:
                 out = packet
             # + mac
@@ -340,7 +340,7 @@ class Packetizer (object):
         """
         header = self.read_all(self.__block_size_in, check_rekey=True)
         if self.__block_engine_in is not None:
-            header = self.__block_engine_in.decrypt(header)
+            header = self.__block_engine_in.update(header)
         if self.__dump_packets:
             self._log(DEBUG, util.format_binary(header, 'IN: '))
         packet_size = struct.unpack('>I', header[:4])[0]
@@ -352,7 +352,7 @@ class Packetizer (object):
         packet = buf[:packet_size - len(leftover)]
         post_packet = buf[packet_size - len(leftover):]
         if self.__block_engine_in is not None:
-            packet = self.__block_engine_in.decrypt(packet)
+            packet = self.__block_engine_in.update(packet)
         if self.__dump_packets:
             self._log(DEBUG, util.format_binary(packet, 'IN: '))
         packet = leftover + packet
diff --git a/paramiko/pkey.py b/paramiko/pkey.py
index 2daf3723..90c45116 100644
--- a/paramiko/pkey.py
+++ b/paramiko/pkey.py
@@ -25,7 +25,8 @@ from binascii import hexlify, unhexlify
 import os
 from hashlib import md5
 
-from Crypto.Cipher import DES3, AES
+from cryptography.hazmat.backends import default_backend
+from cryptography.hazmat.primitives.ciphers import algorithms, modes, Cipher
 
 from paramiko import util
 from paramiko.common import o600, zero_byte
@@ -33,15 +34,25 @@ from paramiko.py3compat import u, encodebytes, decodebytes, b
 from paramiko.ssh_exception import SSHException, PasswordRequiredException
 
 
-class PKey (object):
+class PKey(object):
     """
     Base class for public keys.
     """
 
     # known encryption types for private key files:
     _CIPHER_TABLE = {
-        'AES-128-CBC': {'cipher': AES, 'keysize': 16, 'blocksize': 16, 'mode': AES.MODE_CBC},
-        'DES-EDE3-CBC': {'cipher': DES3, 'keysize': 24, 'blocksize': 8, 'mode': DES3.MODE_CBC},
+        'AES-128-CBC': {
+            'cipher': algorithms.AES,
+            'keysize': 16,
+            'blocksize': 16,
+            'mode': modes.CBC
+        },
+        'DES-EDE3-CBC': {
+            'cipher': algorithms.TripleDES,
+            'keysize': 24,
+            'blocksize': 8,
+            'mode': modes.CBC
+        },
     }
 
     def __init__(self, msg=None, data=None):
@@ -300,7 +311,10 @@ class PKey (object):
         mode = self._CIPHER_TABLE[encryption_type]['mode']
         salt = unhexlify(b(saltstr))
         key = util.generate_key_bytes(md5, salt, password, keysize)
-        return cipher.new(key, mode, salt).decrypt(data)
+        decryptor = Cipher(
+            cipher(key), mode(salt), backend=default_backend()
+        ).decryptor()
+        return decryptor.update(data) + decryptor.finalize()
 
     def _write_private_key_file(self, tag, filename, data, password=None):
         """
@@ -336,7 +350,10 @@ class PKey (object):
                 #data += os.urandom(n)
                 # that would make more sense ^, but it confuses openssh.
                 data += zero_byte * n
-            data = cipher.new(key, mode, salt).encrypt(data)
+            encryptor = Cipher(
+                cipher(key), mode(salt), backend=default_backend()
+            ).encryptor()
+            data = encryptor.update(data) + encryptor.finalize()
             f.write('Proc-Type: 4,ENCRYPTED\n')
             f.write('DEK-Info: %s,%s\n' % (cipher_name, u(hexlify(salt)).upper()))
             f.write('\n')
diff --git a/paramiko/rsakey.py b/paramiko/rsakey.py
index d1f3ecfe..026fde39 100644
--- a/paramiko/rsakey.py
+++ b/paramiko/rsakey.py
@@ -21,22 +21,22 @@ RSA keys.
 """
 
 import os
-from hashlib import sha1
 
-from Crypto.PublicKey import RSA
+from cryptography.exceptions import InvalidSignature
+from cryptography.hazmat.backends import default_backend
+from cryptography.hazmat.primitives import hashes
+from cryptography.hazmat.primitives.asymmetric import rsa, padding
 
 from paramiko import util
-from paramiko.common import max_byte, zero_byte, one_byte
 from paramiko.message import Message
 from paramiko.ber import BER, BERException
 from paramiko.pkey import PKey
-from paramiko.py3compat import long
 from paramiko.ssh_exception import SSHException
 
 SHA1_DIGESTINFO = b'\x30\x21\x30\x09\x06\x05\x2b\x0e\x03\x02\x1a\x05\x00\x04\x14'
 
 
-class RSAKey (PKey):
+class RSAKey(PKey):
     """
     Representation of an RSA key which can be used to sign and verify SSH2
     data.
@@ -48,6 +48,9 @@ class RSAKey (PKey):
         self.d = None
         self.p = None
         self.q = None
+        self.dmp1 = None
+        self.dmq1 = None
+        self.iqmp = None
         if file_obj is not None:
             self._from_private_key(file_obj, password)
             return
@@ -93,9 +96,22 @@ class RSAKey (PKey):
         return self.d is not None
 
     def sign_ssh_data(self, data):
-        digest = sha1(data).digest()
-        rsa = RSA.construct((long(self.n), long(self.e), long(self.d)))
-        sig = util.deflate_long(rsa.sign(self._pkcs1imify(digest), bytes())[0], 0)
+        key = rsa.RSAPrivateNumbers(
+            p=self.p,
+            q=self.q,
+            d=self.d,
+            dmp1=self.dmp1,
+            dmq1=self.dmq1,
+            iqmp=self.iqmp,
+            public_numbers=rsa.RSAPublicNumbers(self.e, self.n)
+        ).private_key(backend=default_backend())
+        signer = key.signer(
+            padding=padding.PKCS1v15(),
+            algorithm=hashes.SHA1(),
+        )
+        signer.update(data)
+        sig = signer.finalize()
+
         m = Message()
         m.add_string('ssh-rsa')
         m.add_string(sig)
@@ -104,13 +120,21 @@ class RSAKey (PKey):
     def verify_ssh_sig(self, data, msg):
         if msg.get_text() != 'ssh-rsa':
             return False
-        sig = util.inflate_long(msg.get_binary(), True)
-        # verify the signature by SHA'ing the data and encrypting it using the
-        # public key.  some wackiness ensues where we "pkcs1imify" the 20-byte
-        # hash into a string as long as the RSA key.
-        hash_obj = util.inflate_long(self._pkcs1imify(sha1(data).digest()), True)
-        rsa = RSA.construct((long(self.n), long(self.e)))
-        return rsa.verify(hash_obj, (sig,))
+        key = rsa.RSAPublicNumbers(
+            self.e, self.n
+        ).public_key(backend=default_backend())
+        verifier = key.verifier(
+            signature=msg.get_binary(),
+            padding=padding.PKCS1v15(),
+            algorithm=hashes.SHA1(),
+        )
+        verifier.update(data)
+        try:
+            verifier.verify()
+        except InvalidSignature:
+            return False
+        else:
+            return True
 
     def _encode_key(self):
         if (self.p is None) or (self.q is None):
@@ -137,30 +161,24 @@ class RSAKey (PKey):
         generate a new host key or authentication key.
 
         :param int bits: number of bits the generated key should be.
-        :param function progress_func:
-            an optional function to call at key points in key generation (used
-            by ``pyCrypto.PublicKey``).
+        :param function progress_func: Unused
         :return: new `.RSAKey` private key
         """
-        rsa = RSA.generate(bits, os.urandom, progress_func)
-        key = RSAKey(vals=(rsa.e, rsa.n))
-        key.d = rsa.d
-        key.p = rsa.p
-        key.q = rsa.q
+        numbers = rsa.generate_private_key(
+            65537, bits, backend=default_backend()
+        ).private_numbers()
+        key = RSAKey(vals=(numbers.public_numbers.e, numbers.public_numbers.n))
+        key.d = numbers.d
+        key.p = numbers.p
+        key.q = numbers.q
+        key.dmp1 = numbers.dmp1
+        key.dmq1 = numbers.dmq1
+        key.iqmp = numbers.iqmp
         return key
     generate = staticmethod(generate)
 
     ###  internals...
 
-    def _pkcs1imify(self, data):
-        """
-        turn a 20-byte SHA1 hash into a blob of data as large as the key's N,
-        using PKCS1's \"emsa-pkcs1-v1_5\" encoding.  totally bizarre.
-        """
-        size = len(util.deflate_long(self.n, 0))
-        filler = max_byte * (size - len(SHA1_DIGESTINFO) - len(data) - 3)
-        return zero_byte + one_byte + filler + zero_byte + SHA1_DIGESTINFO + data
-
     def _from_private_key_file(self, filename, password):
         data = self._read_private_key_file('RSA', filename, password)
         self._decode_key(data)
@@ -181,7 +199,9 @@ class RSAKey (PKey):
         self.n = keylist[1]
         self.e = keylist[2]
         self.d = keylist[3]
-        # not really needed
         self.p = keylist[4]
         self.q = keylist[5]
+        self.dmp1 = keylist[6]
+        self.dmq1 = keylist[7]
+        self.iqmp = keylist[8]
         self.size = util.bit_length(self.n)
diff --git a/paramiko/transport.py b/paramiko/transport.py
index 0f747343..50c7a80a 100644
--- a/paramiko/transport.py
+++ b/paramiko/transport.py
@@ -28,6 +28,9 @@ import time
 import weakref
 from hashlib import md5, sha1
 
+from cryptography.hazmat.backends import default_backend
+from cryptography.hazmat.primitives.ciphers import algorithms, Cipher, modes
+
 import paramiko
 from paramiko import util
 from paramiko.auth_handler import AuthHandler
@@ -63,11 +66,6 @@ from paramiko.ssh_exception import (SSHException, BadAuthenticationType,
                                     ChannelException, ProxyCommandFailure)
 from paramiko.util import retry_on_signal, clamp_value
 
-from Crypto.Cipher import Blowfish, AES, DES3, ARC4
-try:
-    from Crypto.Util import Counter
-except ImportError:
-    from paramiko.util import Counter
 
 
 # for thread cleanup
@@ -89,6 +87,9 @@ class Transport (threading.Thread):
     multiplexed across a single session (and often are, in the case of port
     forwardings).
     """
+    _ENCRYPT = object()
+    _DECRYPT = object()
+
     _PROTO_ID = '2.0'
     _CLIENT_ID = 'paramiko_%s' % paramiko.__version__
 
@@ -100,16 +101,57 @@ class Transport (threading.Thread):
     _preferred_compression = ('none',)
 
     _cipher_info = {
-        'aes128-ctr': {'class': AES, 'mode': AES.MODE_CTR, 'block-size': 16, 'key-size': 16},
-        'aes256-ctr': {'class': AES, 'mode': AES.MODE_CTR, 'block-size': 16, 'key-size': 32},
-        'blowfish-cbc': {'class': Blowfish, 'mode': Blowfish.MODE_CBC, 'block-size': 8, 'key-size': 16},
-        'aes128-cbc': {'class': AES, 'mode': AES.MODE_CBC, 'block-size': 16, 'key-size': 16},
-        'aes256-cbc': {'class': AES, 'mode': AES.MODE_CBC, 'block-size': 16, 'key-size': 32},
-        '3des-cbc': {'class': DES3, 'mode': DES3.MODE_CBC, 'block-size': 8, 'key-size': 24},
-        'arcfour128': {'class': ARC4, 'mode': None, 'block-size': 8, 'key-size': 16},
-        'arcfour256': {'class': ARC4, 'mode': None, 'block-size': 8, 'key-size': 32},
+        'aes128-ctr': {
+            'class': algorithms.AES,
+            'mode': modes.CTR,
+            'block-size': 16,
+            'key-size': 16
+        },
+        'aes256-ctr': {
+            'class': algorithms.AES,
+            'mode': modes.CTR,
+            'block-size': 16,
+            'key-size': 32
+        },
+        'blowfish-cbc': {
+            'class': algorithms.Blowfish,
+            'mode': modes.CBC,
+            'block-size': 8,
+            'key-size': 16
+        },
+        'aes128-cbc': {
+            'class': algorithms.AES,
+            'mode': modes.CBC,
+            'block-size': 16,
+            'key-size': 16
+        },
+        'aes256-cbc': {
+            'class': algorithms.AES,
+            'mode': modes.CBC,
+            'block-size': 16,
+            'key-size': 32
+        },
+        '3des-cbc': {
+            'class': algorithms.TripleDES,
+            'mode': modes.CBC,
+            'block-size': 8,
+            'key-size': 24
+        },
+        'arcfour128': {
+            'class': algorithms.ARC4,
+            'mode': None,
+            'block size': 8,
+            'key-size': 16
+        },
+        'arcfour256': {
+            'class': algorithms.ARC4,
+            'mode': None,
+            'block size': 8,
+            'key-size': 32
+        },
     }
 
+
     _mac_info = {
         'hmac-sha1': {'class': sha1, 'size': 20},
         'hmac-sha1-96': {'class': sha1, 'size': 12},
@@ -1501,22 +1543,34 @@ class Transport (threading.Thread):
             sofar += digest
         return out[:nbytes]
 
-    def _get_cipher(self, name, key, iv):
+    def _get_cipher(self, name, key, iv, operation):
         if name not in self._cipher_info:
             raise SSHException('Unknown client cipher ' + name)
         if name in ('arcfour128', 'arcfour256'):
             # arcfour cipher
-            cipher = self._cipher_info[name]['class'].new(key)
+            cipher = Cipher(
+                self._cipher_info[name]['class'](key),
+                None,
+                backend=default_backend()
+            )
+            if operation is self._ENCRYPT:
+                engine = cipher.encryptor()
+            else:
+                engine = cipher.decryptor()
             # as per RFC 4345, the first 1536 bytes of keystream
             # generated by the cipher MUST be discarded
-            cipher.encrypt(" " * 1536)
-            return cipher
-        elif name.endswith("-ctr"):
-            # CTR modes, we need a counter
-            counter = Counter.new(nbits=self._cipher_info[name]['block-size'] * 8, initial_value=util.inflate_long(iv, True))
-            return self._cipher_info[name]['class'].new(key, self._cipher_info[name]['mode'], iv, counter)
+            engine.encrypt(" " * 1536)
+            return engine
         else:
-            return self._cipher_info[name]['class'].new(key, self._cipher_info[name]['mode'], iv)
+            cipher = Cipher(
+                self._cipher_info[name]['class'](key),
+                self._cipher_info[name]['mode'](iv),
+                backend=default_backend(),
+            )
+            if operation is self._ENCRYPT:
+                return cipher.encryptor()
+            else:
+                return cipher.decryptor()
 
     def _set_forward_agent_handler(self, handler):
         if handler is None:
@@ -1872,7 +1926,7 @@ class Transport (threading.Thread):
         else:
             IV_in = self._compute_key('B', block_size)
             key_in = self._compute_key('D', self._cipher_info[self.remote_cipher]['key-size'])
-        engine = self._get_cipher(self.remote_cipher, key_in, IV_in)
+        engine = self._get_cipher(self.remote_cipher, key_in, IV_in, self._DECRYPT)
         mac_size = self._mac_info[self.remote_mac]['size']
         mac_engine = self._mac_info[self.remote_mac]['class']
         # initial mac keys are done in the hash's natural size (not the potentially truncated
@@ -1899,7 +1953,7 @@ class Transport (threading.Thread):
         else:
             IV_out = self._compute_key('A', block_size)
             key_out = self._compute_key('C', self._cipher_info[self.local_cipher]['key-size'])
-        engine = self._get_cipher(self.local_cipher, key_out, IV_out)
+        engine = self._get_cipher(self.local_cipher, key_out, IV_out, self._ENCRYPT)
         mac_size = self._mac_info[self.local_mac]['size']
         mac_engine = self._mac_info[self.local_mac]['class']
         # initial mac keys are done in the hash's natural size (not the potentially truncated
diff --git a/paramiko/util.py b/paramiko/util.py
index d029f52e..f966099d 100644
--- a/paramiko/util.py
+++ b/paramiko/util.py
@@ -281,37 +281,6 @@ def retry_on_signal(function):
                 raise
 
 
-class Counter (object):
-    """Stateful counter for CTR mode crypto"""
-    def __init__(self, nbits, initial_value=long(1), overflow=long(0)):
-        self.blocksize = nbits / 8
-        self.overflow = overflow
-        # start with value - 1 so we don't have to store intermediate values when counting
-        # could the iv be 0?
-        if initial_value == 0:
-            self.value = array.array('c', max_byte * self.blocksize)
-        else:
-            x = deflate_long(initial_value - 1, add_sign_padding=False)
-            self.value = array.array('c', zero_byte * (self.blocksize - len(x)) + x)
-
-    def __call__(self):
-        """Increament the counter and return the new value"""
-        i = self.blocksize - 1
-        while i > -1:
-            c = self.value[i] = byte_chr((byte_ord(self.value[i]) + 1) % 256)
-            if c != zero_byte:
-                return self.value.tostring()
-            i -= 1
-        # counter reset
-        x = deflate_long(self.overflow, add_sign_padding=False)
-        self.value = array.array('c', zero_byte * (self.blocksize - len(x)) + x)
-        return self.value.tostring()
-
-    def new(cls, nbits, initial_value=long(1), overflow=long(0)):
-        return cls(nbits, initial_value=initial_value, overflow=overflow)
-    new = classmethod(new)
-
-
 def constant_time_bytes_eq(a, b):
     if len(a) != len(b):
         return False
diff --git a/setup.py b/setup.py
index 003a0617..91e9640c 100644
--- a/setup.py
+++ b/setup.py
@@ -24,7 +24,7 @@ connections between python scripts.  All major ciphers and hash methods
 are supported.  SFTP client and server mode are both supported too.
 
 Required packages:
-    pyCrypto
+    Cryptography
 
 To install the `in-development version
 <https://github.com/paramiko/paramiko/tarball/master#egg=paramiko-dev>`_, use
@@ -41,8 +41,9 @@ try:
     from setuptools import setup
     kw = {
         'install_requires': [
-            'pycrypto >= 2.1, != 2.4',
+            'cryptography >= 0.5.4',
             'ecdsa >= 0.11',
+            'pyasn1',
         ],
     }
 except ImportError:
diff --git a/tests/test_client.py b/tests/test_client.py
index 6fda7f5e..b585fa0f 100644
--- a/tests/test_client.py
+++ b/tests/test_client.py
@@ -20,6 +20,7 @@
 Some unit tests for SSHClient.
 """
 
+import gc
 import socket
 from tempfile import mkstemp
 import threading
@@ -29,8 +30,9 @@ import warnings
 import os
 import time
 from tests.util import test_path
+
 import paramiko
-from paramiko.common import PY2, b
+from paramiko.common import PY2
 from paramiko.ssh_exception import SSHException
 
 
@@ -287,14 +289,10 @@ class SSHClientTest (unittest.TestCase):
         self.tc.close()
         del self.tc
 
-        # hrm, sometimes p isn't cleared right away.  why is that?
-        #st = time.time()
-        #while (time.time() - st < 5.0) and (p() is not None):
-        #    time.sleep(0.1)
-
-        # instead of dumbly waiting for the GC to collect, force a collection
-        # to see whether the SSHClient object is deallocated correctly
-        import gc
+        # force a collection to see whether the SSHClient object is deallocated
+        # correctly
+        gc.collect()
+        gc.collect()
         gc.collect()
 
         self.assertTrue(p() is None)
diff --git a/tests/test_packetizer.py b/tests/test_packetizer.py
index 8faec03c..ccfe26bd 100644
--- a/tests/test_packetizer.py
+++ b/tests/test_packetizer.py
@@ -23,9 +23,10 @@ Some unit tests for the ssh2 protocol in Transport.
 import unittest
 from hashlib import sha1
 
-from tests.loop import LoopSocket
+from cryptography.hazmat.backends import default_backend
+from cryptography.hazmat.primitives.ciphers import algorithms, Cipher, modes
 
-from Crypto.Cipher import AES
+from tests.loop import LoopSocket
 
 from paramiko import Message, Packetizer, util
 from paramiko.common import byte_chr, zero_byte
@@ -43,8 +44,12 @@ class PacketizerTest (unittest.TestCase):
         p = Packetizer(wsock)
         p.set_log(util.get_logger('paramiko.transport'))
         p.set_hexdump(True)
-        cipher = AES.new(zero_byte * 16, AES.MODE_CBC, x55 * 16)
-        p.set_outbound_cipher(cipher, 16, sha1, 12, x1f * 20)
+        encryptor = Cipher(
+            algorithms.AES(zero_byte * 16),
+            modes.CBC(x55 * 16),
+            backend=default_backend()
+        ).encryptor()
+        p.set_outbound_cipher(encryptor, 16, sha1, 12, x1f * 20)
 
         # message has to be at least 16 bytes long, so we'll have at least one
         # block of data encrypted that contains zero random padding bytes
@@ -66,8 +71,12 @@ class PacketizerTest (unittest.TestCase):
         p = Packetizer(rsock)
         p.set_log(util.get_logger('paramiko.transport'))
         p.set_hexdump(True)
-        cipher = AES.new(zero_byte * 16, AES.MODE_CBC, x55 * 16)
-        p.set_inbound_cipher(cipher, 16, sha1, 12, x1f * 20)
+        decryptor = Cipher(
+            algorithms.AES(zero_byte * 16),
+            modes.CBC(x55 * 16),
+            backend=default_backend()
+        ).decryptor()
+        p.set_inbound_cipher(decryptor, 16, sha1, 12, x1f * 20)
         wsock.send(b'\x43\x91\x97\xbd\x5b\x50\xac\x25\x87\xc2\xc4\x6b\xc7\xe9\x38\xc0\x90\xd2\x16\x56\x0d\x71\x73\x61\x38\x7c\x4c\x3d\xfb\x97\x7d\xe2\x6e\x03\xb1\xa0\xc2\x1c\xd6\x41\x41\x4c\xb4\x59')
         cmd, m = p.read_message()
         self.assertEqual(100, cmd)
@@ -82,8 +91,12 @@ class PacketizerTest (unittest.TestCase):
         p = Packetizer(wsock)
         p.set_log(util.get_logger('paramiko.transport'))
         p.set_hexdump(True)
-        cipher = AES.new(zero_byte * 16, AES.MODE_CBC, x55 * 16)
-        p.set_outbound_cipher(cipher, 16, sha1, 12, x1f * 20)
+        encryptor = Cipher(
+            algorithms.AES(zero_byte * 16),
+            modes.CBC(x55 * 16),
+            backend=default_backend()
+        ).encryptor()
+        p.set_outbound_cipher(encryptor, 16, sha1, 12, x1f * 20)
 
         # message has to be at least 16 bytes long, so we'll have at least one
         # block of data encrypted that contains zero random padding bytes
diff --git a/tox-requirements.txt b/tox-requirements.txt
index 26224ce6..3a834b7f 100644
--- a/tox-requirements.txt
+++ b/tox-requirements.txt
@@ -1,2 +1,3 @@
 # Not sure why tox can't just read setup.py?
-pycrypto
+cryptography >= 0.5.4
+pyasn1