diff --git a/cracklib.spec b/cracklib.spec
index a4cd7d0..6f60d92 100644
--- a/cracklib.spec
+++ b/cracklib.spec
@@ -5,7 +5,7 @@
 Summary: A password-checking library
 Name: cracklib
 Version: 2.8.13
-Release: 4
+Release: 5
 Group: System Environment/Libraries
 Source0: http://prdownloads.sourceforge.net/cracklib/cracklib-%{version}.tar.gz
 
@@ -53,6 +53,8 @@ BuildRequires: python-devel, words, autoconf, automake, gettext, libtool
 # This one's for gettext's sake.
 BuildRequires: cvs
 Conflicts: cracklib-dicts < 2.8
+# The cracklib-format script calls gzip, but without a specific path.
+Requires: gzip
 
 %description
 CrackLib tests passwords to determine whether they match certain
@@ -223,6 +225,10 @@ EOF
 %{_libdir}/../lib/python*/site-packages/*.py*
 
 %changelog
+* Mon May 18 2009 Nalin Dahyabhai <nalin@redhat.com> - 2.8.13-5
+- add explicit dependency on gzip for the sake of cracklib-format (Daniel
+  Mach, #501278)
+
 * Tue Feb 24 2009 Fedora Release Engineering <rel-eng@lists.fedoraproject.org> - 2.8.13-4
 - Rebuilt for https://fedoraproject.org/wiki/Fedora_11_Mass_Rebuild