Python is built natively in a docker container (based on ubuntu bionic) that lacks openssl.

979e9e009b08">pydev@979e9e009b08:~/build/python-native$ ./python
Python 3.8.0a3+ (heads/master-dirty:d6bf6f2, Apr  6 2019, 14:43:30)
[GCC 7.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import hashlib
ERROR:root:code for hash md5 was not found.
Traceback (most recent call last):
  File "/home/pydev/cpython/Lib/hashlib.py", line 244, in <module>
    globals()[__func_name] = __get_hash(__func_name)
  File "/home/pydev/cpython/Lib/hashlib.py", line 113, in __get_builtin_constructor
    raise ValueError('unsupported hash type ' + name)
ValueError: unsupported hash type md5
ERROR:root:code for hash sha1 was not found.
Traceback (most recent call last):
  File "/home/pydev/cpython/Lib/hashlib.py", line 244, in <module>
    globals()[__func_name] = __get_hash(__func_name)
  File "/home/pydev/cpython/Lib/hashlib.py", line 113, in __get_builtin_constructor
    raise ValueError('unsupported hash type ' + name)
ValueError: unsupported hash type sha1
ERROR:root:code for hash sha224 was not found.
Traceback (most recent call last):
  File "/home/pydev/cpython/Lib/hashlib.py", line 244, in <module>
    globals()[__func_name] = __get_hash(__func_name)
  File "/home/pydev/cpython/Lib/hashlib.py", line 113, in __get_builtin_constructor
    raise ValueError('unsupported hash type ' + name)
ValueError: unsupported hash type sha224
ERROR:root:code for hash sha256 was not found.
Traceback (most recent call last):
ERROR:root:code for hash sha256 was not found.
Traceback (most recent call last):
  File "/home/pydev/cpython/Lib/hashlib.py", line 244, in <module>
    globals()[__func_name] = __get_hash(__func_name)
  File "/home/pydev/cpython/Lib/hashlib.py", line 113, in __get_builtin_constructor
    raise ValueError('unsupported hash type ' + name)
ValueError: unsupported hash type sha256
ERROR:root:code for hash sha384 was not found.
Traceback (most recent call last):
  File "/home/pydev/cpython/Lib/hashlib.py", line 244, in <module>
    globals()[__func_name] = __get_hash(__func_name)
  File "/home/pydev/cpython/Lib/hashlib.py", line 113, in __get_builtin_constructor
    raise ValueError('unsupported hash type ' + name)
ValueError: unsupported hash type sha384
ERROR:root:code for hash sha512 was not found.
Traceback (most recent call last):
  File "/home/pydev/cpython/Lib/hashlib.py", line 244, in <module>
    globals()[__func_name] = __get_hash(__func_name)
  File "/home/pydev/cpython/Lib/hashlib.py", line 113, in __get_builtin_constructor
    raise ValueError('unsupported hash type ' + name)
ValueError: unsupported hash type sha512
ERROR:root:code for hash blake2b was not found.
Traceback (most recent call last):
  File "/home/pydev/cpython/Lib/hashlib.py", line 244, in <module>
    globals()[__func_name] = __get_hash(__func_name)
  File "/home/pydev/cpython/Lib/hashlib.py", line 113, in __get_builtin_constructor
    raise ValueError('unsupported hash type ' + name)
ValueError: unsupported hash type blake2b
ERROR:root:code for hash blake2s was not found.
Traceback (most recent call last):
  File "/home/pydev/cpython/Lib/hashlib.py", line 244, in <module>
    globals()[__func_name] = __get_hash(__func_name)
  File "/home/pydev/cpython/Lib/hashlib.py", line 113, in __get_builtin_constructor
    raise ValueError('unsupported hash type ' + name)
ValueError: unsupported hash type blake2s
ERROR:root:code for hash sha3_224 was not found.
Traceback (most recent call last):
  File "/home/pydev/cpython/Lib/hashlib.py", line 244, in <module>
    globals()[__func_name] = __get_hash(__func_name)
  File "/home/pydev/cpython/Lib/hashlib.py", line 113, in __get_builtin_constructor
    globals()[__func_name] = __get_hash(__func_name)
  File "/home/pydev/cpython/Lib/hashlib.py", line 113, in __get_builtin_constructor
    raise ValueError('unsupported hash type ' + name)
ValueError: unsupported hash type sha3_224
ERROR:root:code for hash sha3_256 was not found.
Traceback (most recent call last):
  File "/home/pydev/cpython/Lib/hashlib.py", line 244, in <module>
    globals()[__func_name] = __get_hash(__func_name)
  File "/home/pydev/cpython/Lib/hashlib.py", line 113, in __get_builtin_constructor
    raise ValueError('unsupported hash type ' + name)
ValueError: unsupported hash type sha3_256
ERROR:root:code for hash sha3_384 was not found.
Traceback (most recent call last):
  File "/home/pydev/cpython/Lib/hashlib.py", line 244, in <module>
    globals()[__func_name] = __get_hash(__func_name)
  File "/home/pydev/cpython/Lib/hashlib.py", line 113, in __get_builtin_constructor
    raise ValueError('unsupported hash type ' + name)
ValueError: unsupported hash type sha3_384
ERROR:root:code for hash sha3_512 was not found.
Traceback (most recent call last):
  File "/home/pydev/cpython/Lib/hashlib.py", line 244, in <module>
    globals()[__func_name] = __get_hash(__func_name)
  File "/home/pydev/cpython/Lib/hashlib.py", line 113, in __get_builtin_constructor
    raise ValueError('unsupported hash type ' + name)
ValueError: unsupported hash type sha3_512
ERROR:root:code for hash shake_128 was not found.
Traceback (most recent call last):
  File "/home/pydev/cpython/Lib/hashlib.py", line 244, in <module>
    globals()[__func_name] = __get_hash(__func_name)
  File "/home/pydev/cpython/Lib/hashlib.py", line 113, in __get_builtin_constructor
    raise ValueError('unsupported hash type ' + name)
ValueError: unsupported hash type shake_128
ERROR:root:code for hash shake_256 was not found.
Traceback (most recent call last):
  File "/home/pydev/cpython/Lib/hashlib.py", line 244, in <module>
    globals()[__func_name] = __get_hash(__func_name)
  File "/home/pydev/cpython/Lib/hashlib.py", line 113, in __get_builtin_constructor
    raise ValueError('unsupported hash type ' + name)
ValueError: unsupported hash type shake_256
>>>

Changeset 5ec33a1c25a586552751ca35c85ab7ecb6b06ec3 appends to the new detect_openssl_hashlib() method, the detection for the _sha256, _sha512, _md5, ... extension modules. These modules were detected unconditionnaly before this change and are not detected anymore now when openssl is not supported by the platform.

Working on a PR

Steps to reproduce (requires docker support, about 500 MB and only few minutes):

1. Create the file named 'Dockerfile' whose content is:

####################################
FROM ubuntu

RUN apt-get update && DEBIAN_FRONTEND=noninteractive apt-get install -y \
    bash \
    build-essential \
    git \
    sed \
    && rm -rf /var/lib/apt/lists/*

# Run as user 'pydev'.
RUN groupadd pydev && useradd --no-log-init -m -g pydev pydev
USER pydev:pydev
ENV HOME=/home/pydev
WORKDIR $HOME
####################################

2. Create the ubuntu:bpo-36544 image

    $ docker build --tag=ubuntu:bpo-36544 .

3. Run the image and enters bash as user pydev

    $ docker run -it ubuntu:bpo-36544

    As user pydev, build python and import hashlib:

        5a8ffc33955d">pydev@5a8ffc33955d:~$ git clone -b master --single-branch --depth 1 https://github.com/python/cpython.git
        70e0722a76f2">pydev@70e0722a76f2:~$ cd cpython/ && ./configure && make
        70e0722a76f2">pydev@70e0722a76f2:~/cpython$ ./python -c "import hashlib"

Check that PR 12708 fixes the bug:

Run the ubuntu:bpo-36544 image and enters bash as user pydev

    $ docker run -it ubuntu:bpo-36544

    As user pydev, clone python and fetch PR 12708, build python and import hashlib:

        e4cfd6f74c2b">pydev@e4cfd6f74c2b:~$ git clone -b master --single-branch --depth 1 https://github.com/python/cpython.git
        e4cfd6f74c2b">pydev@e4cfd6f74c2b:~$ cd cpython/ && ./configure && make
        e4cfd6f74c2b">pydev@e4cfd6f74c2b:~/cpython$ git fetch --depth 1 origin pull/12708/head:pr_12708 && git checkout pr_12708
        e4cfd6f74c2b">pydev@e4cfd6f74c2b:~/cpython$ make
        e4cfd6f74c2b">pydev@e4cfd6f74c2b:~/cpython$ ./python -c "import hashlib"

New changeset 2ee077f7955e0349074f16a7afee40b4914619f7 by Miss Islington (bot) (xdegaye) in branch 'master':
bpo-36544 : Fix regression introduced in bpo-36146 (GH-12708)
https://github.com/python/cpython/commit/2ee077f7955e0349074f16a7afee40b4914619f7

Xavier de Gaye: Oops! I also saw such errors but I didn't understand them. Thanks for the fix!

I wrote PR 12750 to fix another minor issue which isn't directly related to your fix (nor to my previous refactoring).

Thanks Victor for the refactoring of setup.py. That was badly needed indeed.