diff --git a/heimdal-7.5.0-explicit-python2.patch b/heimdal-7.5.0-explicit-python2.patch
new file mode 100644
index 0000000..a96b18a
--- /dev/null
+++ b/heimdal-7.5.0-explicit-python2.patch
@@ -0,0 +1,156 @@
+Index: heimdal-3e58559362dd3f485e6d6659d587a9169a131391/lib/hx509/quote.py
+===================================================================
+--- heimdal-3e58559362dd3f485e6d6659d587a9169a131391.orig/lib/hx509/quote.py
++++ heimdal-3e58559362dd3f485e6d6659d587a9169a131391/lib/hx509/quote.py
+@@ -1,4 +1,4 @@
+-#!/usr/bin/python
++#!/usr/bin/python2
+ # -*- coding: utf-8 -*-
+ #
+ # Copyright (c) 2010 Kungliga Tekniska Högskolan
+Index: heimdal-3e58559362dd3f485e6d6659d587a9169a131391/lib/wind/Makefile.am
+===================================================================
+--- heimdal-3e58559362dd3f485e6d6659d587a9169a131391.orig/lib/wind/Makefile.am
++++ heimdal-3e58559362dd3f485e6d6659d587a9169a131391/lib/wind/Makefile.am
+@@ -89,7 +89,7 @@ idn_lookup_SOURCES = idn-lookup.c
+ 
+ LDADD = libwind.la $(LIB_roken)
+ 
+-PYTHON = python
++PYTHON = python2
+ 
+ if !MAINTAINER_MODE
+ skip_python = test -f $@ ||
+Index: heimdal-3e58559362dd3f485e6d6659d587a9169a131391/lib/wind/UnicodeData.py
+===================================================================
+--- heimdal-3e58559362dd3f485e6d6659d587a9169a131391.orig/lib/wind/UnicodeData.py
++++ heimdal-3e58559362dd3f485e6d6659d587a9169a131391/lib/wind/UnicodeData.py
+@@ -1,4 +1,4 @@
+-#!/usr/local/bin/python
++#!/usr/bin/python2
+ # -*- coding: iso-8859-1 -*-
+ 
+ # $Id$
+Index: heimdal-3e58559362dd3f485e6d6659d587a9169a131391/lib/wind/gen-bidi.py
+===================================================================
+--- heimdal-3e58559362dd3f485e6d6659d587a9169a131391.orig/lib/wind/gen-bidi.py
++++ heimdal-3e58559362dd3f485e6d6659d587a9169a131391/lib/wind/gen-bidi.py
+@@ -1,4 +1,4 @@
+-#!/usr/local/bin/python
++#!/usr/bin/python2
+ # -*- coding: iso-8859-1 -*-
+ 
+ # $Id$
+Index: heimdal-3e58559362dd3f485e6d6659d587a9169a131391/lib/wind/gen-combining.py
+===================================================================
+--- heimdal-3e58559362dd3f485e6d6659d587a9169a131391.orig/lib/wind/gen-combining.py
++++ heimdal-3e58559362dd3f485e6d6659d587a9169a131391/lib/wind/gen-combining.py
+@@ -1,4 +1,4 @@
+-#!/usr/local/bin/python
++#!/usr/bin/python2
+ # -*- coding: iso-8859-1 -*-
+ 
+ # $Id$
+Index: heimdal-3e58559362dd3f485e6d6659d587a9169a131391/lib/wind/gen-errorlist.py
+===================================================================
+--- heimdal-3e58559362dd3f485e6d6659d587a9169a131391.orig/lib/wind/gen-errorlist.py
++++ heimdal-3e58559362dd3f485e6d6659d587a9169a131391/lib/wind/gen-errorlist.py
+@@ -1,4 +1,4 @@
+-#!/usr/local/bin/python
++#!/usr/bin/python2
+ # -*- coding: iso-8859-1 -*-
+ 
+ # $Id$
+Index: heimdal-3e58559362dd3f485e6d6659d587a9169a131391/lib/wind/gen-map.py
+===================================================================
+--- heimdal-3e58559362dd3f485e6d6659d587a9169a131391.orig/lib/wind/gen-map.py
++++ heimdal-3e58559362dd3f485e6d6659d587a9169a131391/lib/wind/gen-map.py
+@@ -1,4 +1,4 @@
+-#!/usr/local/bin/python
++#!/usr/bin/python2
+ # -*- coding: iso-8859-1 -*-
+ 
+ # $Id$
+Index: heimdal-3e58559362dd3f485e6d6659d587a9169a131391/lib/wind/gen-normalize.py
+===================================================================
+--- heimdal-3e58559362dd3f485e6d6659d587a9169a131391.orig/lib/wind/gen-normalize.py
++++ heimdal-3e58559362dd3f485e6d6659d587a9169a131391/lib/wind/gen-normalize.py
+@@ -1,4 +1,4 @@
+-#!/usr/local/bin/python
++#!/usr/bin/python2
+ # -*- coding: iso-8859-1 -*-
+ 
+ # $Id$
+Index: heimdal-3e58559362dd3f485e6d6659d587a9169a131391/lib/wind/gen-punycode-examples.py
+===================================================================
+--- heimdal-3e58559362dd3f485e6d6659d587a9169a131391.orig/lib/wind/gen-punycode-examples.py
++++ heimdal-3e58559362dd3f485e6d6659d587a9169a131391/lib/wind/gen-punycode-examples.py
+@@ -1,4 +1,4 @@
+-#!/usr/local/bin/python
++#!/usr/bin/python2
+ # -*- coding: iso-8859-1 -*-
+ 
+ # $Id$
+Index: heimdal-3e58559362dd3f485e6d6659d587a9169a131391/lib/wind/generate.py
+===================================================================
+--- heimdal-3e58559362dd3f485e6d6659d587a9169a131391.orig/lib/wind/generate.py
++++ heimdal-3e58559362dd3f485e6d6659d587a9169a131391/lib/wind/generate.py
+@@ -1,4 +1,4 @@
+-#!/usr/local/bin/python
++#!/usr/bin/python2
+ # -*- coding: iso-8859-1 -*-
+ 
+ # $Id$
+Index: heimdal-3e58559362dd3f485e6d6659d587a9169a131391/lib/wind/rfc3454.py
+===================================================================
+--- heimdal-3e58559362dd3f485e6d6659d587a9169a131391.orig/lib/wind/rfc3454.py
++++ heimdal-3e58559362dd3f485e6d6659d587a9169a131391/lib/wind/rfc3454.py
+@@ -1,4 +1,4 @@
+-#!/usr/local/bin/python
++#!/usr/bin/python2
+ # -*- coding: iso-8859-1 -*-
+ 
+ # $Id$
+Index: heimdal-3e58559362dd3f485e6d6659d587a9169a131391/lib/wind/rfc4518.py
+===================================================================
+--- heimdal-3e58559362dd3f485e6d6659d587a9169a131391.orig/lib/wind/rfc4518.py
++++ heimdal-3e58559362dd3f485e6d6659d587a9169a131391/lib/wind/rfc4518.py
+@@ -1,4 +1,4 @@
+-#!/usr/local/bin/python
++#!/usr/bin/python2
+ # -*- coding: iso-8859-1 -*-
+ 
+ # $Id$
+Index: heimdal-3e58559362dd3f485e6d6659d587a9169a131391/lib/wind/stringprep.py
+===================================================================
+--- heimdal-3e58559362dd3f485e6d6659d587a9169a131391.orig/lib/wind/stringprep.py
++++ heimdal-3e58559362dd3f485e6d6659d587a9169a131391/lib/wind/stringprep.py
+@@ -1,4 +1,4 @@
+-#!/usr/local/bin/python
++#!/usr/bin/python2
+ # -*- coding: iso-8859-1 -*-
+ 
+ # $Id$
+Index: heimdal-3e58559362dd3f485e6d6659d587a9169a131391/lib/wind/util.py
+===================================================================
+--- heimdal-3e58559362dd3f485e6d6659d587a9169a131391.orig/lib/wind/util.py
++++ heimdal-3e58559362dd3f485e6d6659d587a9169a131391/lib/wind/util.py
+@@ -1,4 +1,4 @@
+-#!/usr/local/bin/python
++#!/usr/bin/python2
+ # -*- coding: iso-8859-1 -*-
+ 
+ # $Id$
+Index: heimdal-3e58559362dd3f485e6d6659d587a9169a131391/windows/NTMakefile.w32
+===================================================================
+--- heimdal-3e58559362dd3f485e6d6659d587a9169a131391.orig/windows/NTMakefile.w32
++++ heimdal-3e58559362dd3f485e6d6659d587a9169a131391/windows/NTMakefile.w32
+@@ -120,7 +120,7 @@ RC=rc
+ AWK_CMD=gawk.exe
+ YACC_CMD=bison.exe
+ LEX_CMD=flex.exe
+-PYTHON=python.exe
++PYTHON=python2.exe
+ PERL=perl.exe
+ CMP=cmp.exe
+ MAKECAT=makecat.exe
diff --git a/heimdal.spec b/heimdal.spec
index 9692663..90d0988 100644
--- a/heimdal.spec
+++ b/heimdal.spec
@@ -18,7 +18,7 @@
 
 Name: heimdal
 Version: 7.5.0
-Release: 5%{?dist}
+Release: 6%{?dist}
 Summary: A Kerberos 5 implementation without export restrictions
 License: BSD and MIT
 URL: http://www.h5l.org/
@@ -54,6 +54,8 @@ Source31: %{name}-ipropd-slave-wrapper
 # to know how to interpret the "heimdal-" prefixes.
 Patch1: heimdal-1.6.0-c25f45a-rename-commands.patch
 Patch2: heimdal-7.4.0-237cd892-fixwaitloop.patch
+# Use Python2 explicity.
+Patch3: heimdal-7.5.0-explicit-python2.patch
 
 BuildRequires:  bison
 BuildRequires:  flex
@@ -179,6 +181,7 @@ PATH.
 %setup -b 1 -qn %{name}-%{commit}
 %patch1 -p1 -b .cmds
 %patch2 -p1 -b .fixwaitloop
+%patch3 -p1 -b .python2
 
 %if 0%{?need_autogen}
   ./autogen.sh
@@ -560,6 +563,9 @@ fi
 %{_sysconfdir}/profile.d/%{name}.csh
 
 %changelog
+* Sun Jan 06 2019 Björn Esser <besser82@fedoraproject.org> - 7.5.0-6
+- Add patch to explicitly use python2 binary, fixes FTBFS (#1604316)
+
 * Fri Jul 13 2018 Fedora Release Engineering <releng@fedoraproject.org> - 7.5.0-5
 - Rebuilt for https://fedoraproject.org/wiki/Fedora_29_Mass_Rebuild