classification
Title: secrets.randbelow(-1) hangs
Type: behavior Stage: needs patch
Components: Library (Lib) Versions: Python 3.7, Python 3.6
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: Brian Nenninger, brendan-donegan, brendand, josh.r, python-dev, rhettinger, steven.daprano
Priority: normal Keywords: patch

Created on 2016-12-24 06:24 by Brian Nenninger, last changed 2016-12-30 08:00 by steven.daprano. This issue is now closed.

Files
File name Uploaded Description Edit
issue_29061_randbelow.patch brendan-donegan, 2016-12-24 09:39 review
issue_29061_randbelow_v2.patch brendan-donegan, 2016-12-27 13:00 review
Messages (12)
msg283923 - (view) Author: Brian Nenninger (Brian Nenninger) Date: 2016-12-24 06:24
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)
msg283929 - (view) Author: Brendan Donegan (brendan-donegan) * Date: 2016-12-24 09:17
Reproducible on Linux as well, I think I know where the issue is and will try to submit a patch soon.
msg283931 - (view) Author: Brendan Donegan (brendan-donegan) * Date: 2016-12-24 09:39
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.
msg284076 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2016-12-27 09:13
Brendan, would you please submit a contributor agreement.
msg284082 - (view) Author: Brendan Donegan (brendand) Date: 2016-12-27 10:09
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>
> _______________________________________
>
msg284091 - (view) Author: Brendan Donegan (brendan-donegan) * Date: 2016-12-27 13:00
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
msg284112 - (view) Author: Josh Rosenberg (josh.r) * (Python triager) Date: 2016-12-27 16:38
SystemRandom._randbelow has this problem, perhaps it should be fixed there, not in one of many possible wrappers for it?
msg284113 - (view) Author: Brendan Donegan (brendand) Date: 2016-12-27 16:41
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>
> _______________________________________
>
msg284312 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2016-12-30 05:42
_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 :-)
msg284314 - (view) Author: Roundup Robot (python-dev) (Python triager) Date: 2016-12-30 05:55
New changeset 0509844f38df by Raymond Hettinger in branch '3.6':
Issue #29061:  secrets.randbelow() would hang with a negative input
https://hg.python.org/cpython/rev/0509844f38df
msg284315 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2016-12-30 05:55
Thanks for the bug report and for the patch.
msg284322 - (view) Author: Steven D'Aprano (steven.daprano) * (Python committer) Date: 2016-12-30 08:00
> _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.
History
Date User Action Args
2016-12-30 08:00:14steven.dapranosetmessages: + msg284322
2016-12-30 05:55:46rhettingersetstatus: open -> closed
resolution: fixed
messages: + msg284315
2016-12-30 05:55:15python-devsetnosy: + python-dev
messages: + msg284314
2016-12-30 05:42:21rhettingersetmessages: + msg284312
2016-12-27 16:41:49brendandsetmessages: + msg284113
2016-12-27 16:38:11josh.rsetnosy: + josh.r
messages: + msg284112
2016-12-27 13:00:23brendan-donegansetfiles: + issue_29061_randbelow_v2.patch

messages: + msg284091
2016-12-27 10:09:49brendandsetnosy: + brendand
messages: + msg284082
2016-12-27 09:13:30rhettingersetpriority: high -> normal

messages: + msg284076
2016-12-27 08:35:15rhettingersetassignee: rhettinger
2016-12-24 09:39:22brendan-donegansetfiles: + issue_29061_randbelow.patch
keywords: + patch
messages: + msg283931
2016-12-24 09:17:50brendan-donegansetnosy: + brendan-donegan
messages: + msg283929
2016-12-24 07:36:29ned.deilysetpriority: normal -> high
nosy: + rhettinger, steven.daprano
stage: needs patch

versions: + Python 3.7
2016-12-24 06:24:43Brian Nenningercreate