diff --git a/Lib/test/test_httplib.py b/Lib/test/test_httplib.py
index 4755f8b..49263a8 100644
--- a/Lib/test/test_httplib.py
+++ b/Lib/test/test_httplib.py
@@ -4,6 +4,7 @@
 import itertools
 import os
 import array
+import re
 import socket
 import threading
 
@@ -1622,14 +1623,30 @@
         # We feed the server's cert as a validating cert
         import ssl
         support.requires('network')
-        with support.transient_internet('self-signed.pythontest.net'):
+        selfsigned_pythontestdotnet = 'self-signed.pythontest.net'
+        with support.transient_internet(selfsigned_pythontestdotnet):
             context = ssl.SSLContext(ssl.PROTOCOL_TLS_CLIENT)
             self.assertEqual(context.verify_mode, ssl.CERT_REQUIRED)
             self.assertEqual(context.check_hostname, True)
             context.load_verify_locations(CERT_selfsigned_pythontestdotnet)
-            h = client.HTTPSConnection('self-signed.pythontest.net', 443, context=context)
-            h.request('GET', '/')
-            resp = h.getresponse()
+            try:
+                h = client.HTTPSConnection(selfsigned_pythontestdotnet, 443,
+                                           context=context)
+                h.request('GET', '/')
+                resp = h.getresponse()
+            except ssl.SSLError as ssl_err:
+                ssl_err_str = str(ssl_err)
+                # In the error message of [SSL: CERTIFICATE_VERIFY_FAILED] on
+                # modern Linux distros (Debian Buster, etc) default OpenSSL
+                # configurations it'll fail saying "key too weak" until we
+                # address https://bugs.python.org/issue36816 to use a proper
+                # key size on self-signed.pythontest.net.
+                if re.search(r'(?i)key.too.weak', ssl_err_str):
+                    raise unittest.SkipTest(
+                        f'Got {ssl_err_str} trying to connect '
+                        f'to {selfsigned_pythontestdotnet}. '
+                        'See https://bugs.python.org/issue36816.')
+                raise
             server_string = resp.getheader('server')
             resp.close()
             h.close()
diff --git a/Lib/test/test_nntplib.py b/Lib/test/test_nntplib.py
index 8c1032b..618b403 100644
--- a/Lib/test/test_nntplib.py
+++ b/Lib/test/test_nntplib.py
@@ -6,6 +6,7 @@
 import functools
 import contextlib
 import os.path
+import re
 import threading
 
 from test import support
@@ -21,6 +22,13 @@
 TIMEOUT = 30
 certfile = os.path.join(os.path.dirname(__file__), 'keycert3.pem')
 
+if ssl is not None:
+    SSLError = ssl.SSLError
+else:
+    class SSLError(Exception):
+        """Non-existent exception class when we lack SSL support."""
+        reason = "This will never be raised."
+
 # TODO:
 # - test the `file` arg to more commands
 # - test error conditions
@@ -261,14 +269,21 @@
                 return False
             return True
 
-        with self.NNTP_CLASS(self.NNTP_HOST, timeout=TIMEOUT, usenetrc=False) as server:
-            self.assertTrue(is_connected())
-            self.assertTrue(server.help())
-        self.assertFalse(is_connected())
+        try:
+            with self.NNTP_CLASS(self.NNTP_HOST, timeout=TIMEOUT, usenetrc=False) as server:
+                self.assertTrue(is_connected())
+                self.assertTrue(server.help())
+            self.assertFalse(is_connected())
 
-        with self.NNTP_CLASS(self.NNTP_HOST, timeout=TIMEOUT, usenetrc=False) as server:
-            server.quit()
-        self.assertFalse(is_connected())
+            with self.NNTP_CLASS(self.NNTP_HOST, timeout=TIMEOUT, usenetrc=False) as server:
+                server.quit()
+            self.assertFalse(is_connected())
+        except SSLError as ssl_err:
+            # matches "[SSL: DH_KEY_TOO_SMALL] dh key too small"
+            if re.search(r'(?i)KEY.TOO.SMALL', ssl_err.reason):
+                raise unittest.SkipTest(f"Got {ssl_err} connecting "
+                                        f"to {self.NNTP_HOST!r}")
+            raise
 
 
 NetworkedNNTPTestsMixin.wrap_methods()
@@ -294,6 +309,12 @@
             try:
                 cls.server = cls.NNTP_CLASS(cls.NNTP_HOST, timeout=TIMEOUT,
                                             usenetrc=False)
+            except SSLError as ssl_err:
+                # matches "[SSL: DH_KEY_TOO_SMALL] dh key too small"
+                if re.search(r'(?i)KEY.TOO.SMALL', ssl_err.reason):
+                    raise unittest.SkipTest(f"{cls} got {ssl_err} connecting "
+                                            f"to {cls.NNTP_HOST!r}")
+                raise
             except EOF_ERRORS:
                 raise unittest.SkipTest(f"{cls} got EOF error on connecting "
                                         f"to {cls.NNTP_HOST!r}")
diff --git a/Misc/NEWS.d/next/Tests/2019-05-06-18-29-54.bpo-35925.gwQPuC.rst b/Misc/NEWS.d/next/Tests/2019-05-06-18-29-54.bpo-35925.gwQPuC.rst
new file mode 100644
index 0000000..ad8cc8f
--- /dev/null
+++ b/Misc/NEWS.d/next/Tests/2019-05-06-18-29-54.bpo-35925.gwQPuC.rst
@@ -0,0 +1 @@
+Skip httplib and nntplib networking tests when they would otherwise fail due to a modern OS or distro with a default OpenSSL policy of rejecting connections to servers with weak certificates.