Path: csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail From: Chris Angelico Newsgroups: comp.lang.python Subject: Re: How to remove item from heap efficiently? Date: Thu, 14 Jan 2016 03:54:32 +1100 Lines: 30 Message-ID: References: <568EEC40.7070807@mail.de> <568FE797.6090808@mail.de> <5692A795.3070904@mail.de> <5695276A.2020101@mail.de> <7A7E26D9-01E5-4D77-92B4-3491D86E1EA8@gmail.com> <56967DFD.5090408@chamonix.reportlab.co.uk> Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 X-Trace: news.uni-berlin.de 3LgrT2XCcmiKa7tKmR+JBAn5WWl6lkk5zAxK4lXlSbaA== Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.000 X-Spam-Evidence: '*H*': 1.00; '*S*': 0.00; 'cpython': 0.05; 'versions,': 0.05; 'default.': 0.07; 'key.': 0.07; 'strings.': 0.07; 'cc:addr:python-list': 0.09; 'subject:How': 0.09; 'attack.': 0.09; 'integers': 0.09; 'parameter.': 0.09; 'python': 0.10; 'assume': 0.11; 'jan': 0.11; '2.7': 0.13; 'thu,': 0.15; '2016': 0.16; 'accesses': 0.16; 'amortized': 0.16; 'caveats': 0.16; 'from:addr:rosuav': 0.16; 'from:name:chris angelico': 0.16; 'hashes': 0.16; 'heapq': 0.16; 'received:io': 0.16; 'received:psf.io': 0.16; 'subject:item': 0.16; 'subject:remove': 0.16; 'wrote:': 0.16; 'looked': 0.16; "wouldn't": 0.16; 'abuse': 0.18; 'fixed.': 0.18; 'cc:2**0': 0.20; 'cc:addr:python.org': 0.20; '(the': 0.22; 'affects': 0.22; 'amounts': 0.22; 'pass': 0.22; 'am,': 0.23; 'originally': 0.23; 'header:In-Reply-To:1': 0.24; "doesn't": 0.26; 'figure': 0.27; 'message-id:@mail.gmail.com': 0.27; '14,': 0.27; 'said,': 0.27; 'url:moin': 0.27; 'accidentally': 0.29; 'dictionary': 0.29; 'hash': 0.29; 'lot.': 0.29; 'site)': 0.29; 'program,': 0.29; 'url:wiki': 0.30; 'certainly': 0.30; 'guess': 0.31; "can't": 0.32; 'says': 0.32; 'run': 0.33; 'point': 0.33; 'url:python': 0.33; 'server': 0.34; 'info': 0.34; 'received:google.com': 0.35; 'so,': 0.35; 'could': 0.35; 'quite': 0.35; 'something': 0.35; 'but': 0.36; 'there': 0.36; 'url:org': 0.36; 'possible.': 0.36; 'received:209.85': 0.36; "wasn't": 0.36; 'subject:?': 0.36; 'subject:: ': 0.37; 'say': 0.37; 'received:209.85.213': 0.37; 'seem': 0.37; 'received:209': 0.38; 'delete': 0.38; 'skip:p 20': 0.38; 'data': 0.39; 'subject:from': 0.39; 'takes': 0.39; 'build': 0.40; 'still': 0.40; 'some': 0.40; 'easy': 0.60; 'no.': 0.62; 'yes': 0.62; 'times': 0.63; 'within': 0.64; 'obvious': 0.76; 'becker': 0.84; 'chrisa': 0.84; 'to:none': 0.91; 'average': 0.93 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:cc :content-type; bh=MmkVh91qQ/AP4tarG3KlV9AMoVcX4H/oie8qPvAgpSA=; b=0vFR0K8NSvCUZxzTpCdIrWRYjc8MgWu1QfpXqNwcC3Np2mim72djDdtATcxhTJWSYa PDi0ejwdXsopnKcHZo72LmeJ17Ft8UHkPIXdLMCFWhoW3tGQ1BhT9d+nzDMbJDpVjDGa qy9G79tA43//tXMtQBittdaaT4VXAKqtVxkzJ8VlqT7O3yy2TG5bOuDjd6edHOELJv+3 gAAFmkDMBfja73lpoVcblOB7JniNcJZsp5IHXngmWU6JSP29j7wi91nMvWFXJ/HlKHJI AbzbRG0A7Wq8+OFhM60LZ+Ad0s/8XVCYYtlyqscpveXvtbq/IXZASZQiPdFAqnWGkdPW 50Gw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:cc:content-type; bh=MmkVh91qQ/AP4tarG3KlV9AMoVcX4H/oie8qPvAgpSA=; b=ZcjrgHIK5uxuD4xmlizKeitUnDYuhN2dhH8HwYbET1jSzRhYXAf2U6tnawmD+mSIfK YS6Rrsue5OkP9+qDWWksr7e089kZUSDZUvibFmTp0XnDXL+GLbROxuLDA4o46ZvbQ/pi tEJzgcUD15sXvzC2ZsHUC5+7f7u1ElA2Y6C5GCjZNSbJaJzzKqa9qahZZImfZb7z3xhb Y7Y+v8clcMyVE3wFnGaA4izdDEKlwSJVHmJIXNMV+csV51muJGQ1oOrFdpSc4LFYe105 kWgLvuMdZKQNi0rbdkjIi0M0zLoi6Pmxh/e/Qm1yPyZy5vw2P2NQsXxGnufyO/a9zpvX l3XA== X-Gm-Message-State: ALoCoQmlSLIbZB9v9wRiDUBEvtkP4iwIHb+dvtr/jIEJK+GpgjBKcapMldO9UBMhjanpHQw/q6GUrE+yvkM8aU7zsDf444iD9A== X-Received: by 10.50.60.6 with SMTP id d6mr26071903igr.94.1452704072622; Wed, 13 Jan 2016 08:54:32 -0800 (PST) In-Reply-To: <56967DFD.5090408@chamonix.reportlab.co.uk> X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.20+ Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Xref: csiph.com comp.lang.python:101632 On Thu, Jan 14, 2016 at 3:40 AM, Robin Becker wrote: > is this true? I looked at https://wiki.python.org/moin/TimeComplexity and it > says that dict.get which I assume is used for accessing the heapq delete > point can be large (the average time is O(1), but amortized over a lot of > accesses can be O(n)). Apparently the history of sets/gets can affect > individual times quite a lot. I seem to remember there was some kind of > hashing attack against python dicts that would use up large amounts of time, > but I guess that's now fixed. Yes and no. In current CPython versions, the hash attack is made a lot harder by randomizing the hashes of strings; the most obvious attack (sending form data to a web site) is now a lot harder, because you need to figure out what the server process is using as its key. But there are some caveats to it: 1) CPython 2.7 doesn't (I believe) do this by default. You have to set PYTHONHASHSEED=random or pass the -R parameter. 2) This still only affects strings. If you build a dictionary out of integers provided by a potential attacker, the hashes will be consistent. 3) If an attacker can get info from the server in dictionary order, the hash key could be deduced. Since it can't change within one run of a program, this could make attacks possible. So, I wouldn't say it's *fixed*. It's certainly been made a lot less easy to abuse than it originally was. That said, though - even before these fixes, it wasn't something you'd accidentally stumble on. It takes a deliberate attack. ChrisA