secrets.randbelow(-1) hangs

[BrianNenninger]

BPO	29061
Nosy	@rhettinger, @stevendaprano, @MojoVampire, @brendan-donegan, @brendan-donegan
Files	issue_29061_randbelow.patch issue_29061_randbelow_v2.patch

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/rhettinger'
closed_at = <Date 2016-12-30.05:55:46.453>
created_at = <Date 2016-12-24.06:24:43.503>
labels = ['3.7', 'type-bug', 'library']
title = 'secrets.randbelow(-1) hangs'
updated_at = <Date 2016-12-30.08:00:14.975>
user = 'https://bugs.python.org/BrianNenninger'

bugs.python.org fields:

activity = <Date 2016-12-30.08:00:14.975>
actor = 'steven.daprano'
assignee = 'rhettinger'
closed = True
closed_date = <Date 2016-12-30.05:55:46.453>
closer = 'rhettinger'
components = ['Library (Lib)']
creation = <Date 2016-12-24.06:24:43.503>
creator = 'Brian Nenninger'
dependencies = []
files = ['46021', '46054']
hgrepos = []
issue_num = 29061
keywords = ['patch']
message_count = 12.0
messages = ['283923', '283929', '283931', '284076', '284082', '284091', '284112', '284113', '284312', '284314', '284315', '284322']
nosy_count = 7.0
nosy_names = ['rhettinger', 'steven.daprano', 'python-dev', 'josh.r', 'brendan-donegan', 'brendand', 'Brian Nenninger']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'needs patch'
status = 'closed'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue29061'
versions = ['Python 3.6', 'Python 3.7']

[BrianNenninger]

secrets.randbelow(-1) causes the interpreter to hang. It should presumably raise an exception like secrets.randbelow(0) does. This is on Mac OS X 10.11.6, shell transcript below.

=========================================================

$ python3
Python 3.6.0 (v3.6.0:41df79263a11, Dec 22 2016, 17:23:13) 
[GCC 4.2.1 (Apple Inc. build 5666) (dot 3)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import secrets
>>> secrets.randbelow(1)
0
>>> secrets.randbelow(0)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/Library/Frameworks/Python.framework/Versions/3.6/lib/python3.6/secrets.py", line 29, in randbelow
    return _sysrand._randbelow(exclusive_upper_bound)
  File "/Library/Frameworks/Python.framework/Versions/3.6/lib/python3.6/random.py", line 232, in _randbelow
    r = getrandbits(k)          # 0 <= r < 2**k
  File "/Library/Frameworks/Python.framework/Versions/3.6/lib/python3.6/random.py", line 678, in getrandbits
    raise ValueError('number of bits must be greater than zero')
ValueError: number of bits must be greater than zero
>>> secrets.randbelow(-1)

(hangs using 100% CPU until aborted)

[brendan-donegan]

Reproducible on Linux as well, I think I know where the issue is and will try to submit a patch soon.

[brendan-donegan]

Ok, here it is. My first code patch in Python.

Basically the existing code was depending on bit_length to DTRT and raise a ValueError, but negative numbers have a positive bit length. Then when it hits:

234 while r >= n:
235 r = getrandbits(k)

It just spins on that as r is always going to be greater than a negative number.

I tried not to be too clever so just put a guard early in the function. This has the added advantage of giving us a clearer error message.

[rhettinger]

Brendan, would you please submit a contributor agreement.

[brendan-donegan]

Hi Raymond,

I have done that when creating the patch and have confirmation in my inbox

• perhaps Ewa hasn't filed it yet?

On Tue, 27 Dec 2016 at 14:43 Raymond Hettinger <report@bugs.python.org>
wrote:

Raymond Hettinger added the comment:

Brendan, would you please submit a contributor agreement.

----------
priority: high -> normal

---

Python tracker <report@bugs.python.org>
<http://bugs.python.org/issue29061\>

---

[brendan-donegan]

Ok, here's a second version of the patch. Normally I don't like testing multiple things in one test but I've gone with what seems to be the convention here in test_secrets.py

[MojoVampire]

SystemRandom._randbelow has this problem, perhaps it should be fixed there, not in one of many possible wrappers for it?

[brendan-donegan]

If I'm not mistaken, _randbelow is defined in Random, which SystemRandom
inherits from. Just for clarity

On Tue, 27 Dec 2016 at 22:08 Josh Rosenberg <report@bugs.python.org> wrote:

Josh Rosenberg added the comment:

SystemRandom._randbelow has this problem, perhaps it should be fixed
there, not in one of many possible wrappers for it?

----------
nosy: +josh.r

---

Python tracker <report@bugs.python.org>
<http://bugs.python.org/issue29061\>

---

[rhettinger]

_randbelow is a private api and it is not broken, it is just being misused by the secrets module. All of the other calls to it are already range checked and it would be inefficient and unnecessary to repeat this the check.

Brendan, thank you for the updated patch. It looks correct. I will apply shortly.

Please do follow-up with Ewa so we can get the asterisk to appear by your name :-)

[python-dev]

New changeset 0509844f38df by Raymond Hettinger in branch '3.6':
Issue bpo-29061: secrets.randbelow() would hang with a negative input
https://hg.python.org/cpython/rev/0509844f38df

[rhettinger]

Thanks for the bug report and for the patch.

[stevendaprano]

_randbelow is a private api and it is not broken, it is just being
misused by the secrets module.

"Misused" seems a bit strong. Should I understand that you dislike the
wrapper around _randbelow? The implementation was given in the PEP, and
I don't remember any objections to it, but if you have an alternative
implementation I'm not wedded to the idea of wrapping _randbelow.

https://www.python.org/dev/peps/pep-0506/#id81

Thanks for the patch Brendan, and thanks Raymond for applying it.